Домашно по криптография

Пак е това време на годината!

Йей, време за домашни!
Задачите на курса по криптография са забележимо по-трудни от средното ниво във ФМИ. В смисъл, ще оставят твоята чувствителна душа в руини.
Но съществува определен вид хора, за които трудното предизвикателство е нещо по-приятно от карамелов сладолед върху гърдите на Адриана Лима.
Ако ти си от тях, тук ще ти хареса.

Както винаги, Не бъди идиот.
Тук има решения на задачи, но наистина ли искаш да ги препишеш?
Така де, ако просто събираш кредити от курсове, защо въобще записваш нещо трудно като Криптография? Ходи на UML и си живей живота.
Моля, използвай тази страница само за проверка дали решенията ти са верни.

Приложените програми са написани на Python. Езикът за програмиране може да се изтегли от http://www.python.org, а онлайн интерпретатор може да бъде намерен на http://codepad.org.

Условията

Задача 1

Даде е шифър на Playfair с ключ:

H O W M A
N Y E L K
S B C D F
G I/J P Q R
T U V X Z

Шифрирайте текста: APATIENTBETTERDRIVER
Дешифрирайте текста: BRUTVNGAKWUGOGKPAWPKQGMBVBUGWC

Не съм гледал кода, обаче "print pf.decrypt(pf.encrypt("APATIENTBETTERDRIVER"))" при мен извежда "APATIENTBETXTERDRIVERX" т.е. има няква грешка някъде.
Анонимен

Кодът е верен, шифрирането е вярно, излишни X-ове се появяват на местата, където има повтарящи се букви, както и в края на текста, ако се е оказал с нечетна дължина.
Това е особеност на шифрирането - както може би е очевидно, предназначено е за употреба от човешки същества, не машини. It's not a bug, it's a feature.

Ха, добре ;) аз явно не бях прочел че трябва да се слага X до две равни букви :) и задачката щеше да ми се размине :)


Задача 2

Даден е криптотекстът UZHBAY, получен чрез шифриране с шифър на L. Hill с ключ:

(1)
\begin{pmatrix} 15 & 9 & 25 \\ 0 & 3 & 5 \\ 10 & 25 & 0 \\ \end{pmatrix}

Дешифрирайте, ако е известно, че е използвано кодирането $A \to 0, B \to 1, \cdots Z \to 25$.


Задача 3

Да се намери минималният период на линейна рекурентна редица над GF(2), удовлетворяваща рекурентното уравнение:

(2)
\begin{equation} a_{n+7} = a_{n+6} + a_{n+5} + a_{n+1} + a_{n} \end{equation}

и имаща начално състояние $(0,0, \cdots, 1)$


Задача 4

Даден е шифър на Feistel с n=2, h=6 и ключ подбран така, че:

(3)
\begin{align} f(k_1) = \begin{pmatrix} 00 & 01 & 10 & 11 \\ 10 & 10 & 00 & 01 \\ \end{pmatrix} \\ \end{align}
(4)
\begin{align} f(k_2) = \begin{pmatrix} 00 & 01 & 10 & 11 \\ 01 & 10 & 10 & 00 \\ \end{pmatrix} \end{align}
(5)
\begin{align} f(k_3) = \begin{pmatrix} 00 & 01 & 10 & 11 \\ 11 & 00 & 01 & 10 \\ \end{pmatrix} \end{align}
(6)
\begin{align} f(k_4) = \begin{pmatrix} 00 & 01 & 10 & 11 \\ 11 & 10 & 11 & 01 \\ \end{pmatrix} \end{align}
(7)
\begin{align} f(k_5) = \begin{pmatrix} 00 & 01 & 10 & 11 \\ 11 & 00 & 00 & 10 \\ \end{pmatrix} \end{align}
(8)
\begin{align} f(k_6) = \begin{pmatrix} 00 & 01 & 10 & 11 \\ 11 & 11 & 01 & 10 \\ \end{pmatrix} \end{align}

Да се шифрира съобщението (0100).
Да се дешифрира шифрираното съобщение(трябва да се получи същият отговор).


Задача 5

Да означим с $DES_K(x)$ образа на 64-битовия блок $x$ при трансформация с $DES$ с ключ $K$. Докажете, че за всяко $K \in \{ 0, 1 \}^{56}$ и всяко $x \in \{ 0, 1 \}^{64}$ е в сила:

(9)
\begin{align} DES_K(x) = \overline{DES_{\overline{K}}(\overline{x})} \end{align}

Как може да се експлоатира това свойство за ускоряването на пълното изчерпване на ключовете при криптоанализ с известен открит текст.

Задача 6

Дадена е RSA с параметри n = 899, e = 611. Разложете n на прости множители и пресметнете d. Дешифрирайте криптотекста 106 680 303, като имате предвид, че при шифрирането буквите на открития текст са преобразувани по следното правило: на всяка двойка букви x,y е съпоставено числото $\alpha(x) + \alpha(y) * 26$, където $\alpha(A) = 0, \alpha(B) = 1, \cdots, \alpha(Z) = 25$


Задача 7

Да се докаже, че съществуват безбройно много съставни числа $n$, за които е изпълнено:
(а) $2^{n-1} \equiv 1 \mod n$
(б) $3^{n-1} \equiv 1 \mod n$


Задача 9

Дадена е криптосистема RSA с модул n = pq криптираща експонента e. Да се докаже, че текстовете, които се криптират в себе си(т.е. за които $m^e \equiv m (mod \quad n)$ са точно:
(1 + gcd(e-1, p-1) * (1 + gcd(e-1,q-1))


Задача 12

Потребителите A и B използват схемата на Diffie и Hellman, използваща дискретен логаритъм за да уговорят таен ключ. Те използват крайното поле $GF(2^{10}) = \mathbb{F}_2[x] / (x^{10} + x^3 + 1)$. Потребителят B публикува $c_B = 0100010100$, което представя елемента на полето $x + x^5 + x^7$. Ако тайният ключ на A е $x_A = 2$, какъв е ключът, който A и B ще използват при комуникацията помежду си?


Задача 14

Дадени са простото число p=101, примитивният елемент $\alpha$ = 2 и $x_U$ = 43. Използвайки схемата на ElGamal, намерете валиден подпис за съобщението m=26. Проверете валидността на генерирания подпис.


Задача 15

Да се пресметне (чрез алгоритъма на Pohlig-Hellman) $\log_3 135$ в полето $GF(353)$.


Задача 16

Дадени са свръхнарастващият вектор {2, 3, 7, 13, 27, 53, 106, 213, 425, 851}, модулът m = 1529 и t = 64. Шифрирайте съобщението "LONDON". Използвайте кодирането:

A 00011 H 01100 O 10100 V 11011
B 00101 I 01101 P 10101 W 11100
C 00110 J 01110 Q 10110 X 11101
D 00111 K 01111 R 10111 Y 11110
E 01001 L 10001 S 11000 Z 11111
F 01010 M 10010 T 11001
G 01011 N 10011 U 11010

Задача 17

Криптосистема, основаваща се на задачата за раницата има за публичен ключ вектора:
(381, 424, 2313, 2527, 2535, , 3832, 3879, 4169)
Той е получен чрез умножаване на елементите на свръхнарастваща редица с 4673 и редуциране на резултата по модул 5011. Дешифрирайте съобщението 1656.


Задача 18

Дадена е (k,n)-прагова схема над $Z_{31}$, при която k = 4, n = 6. Известно е, че дяловете на потребителите A, B, C, D са съответно (11,14),(7,20),(13,10),(21,6). Да се намери тайният ключ, разпределен между участниците.


Задача N


Utils

В програмите, изпълняващи горните задачи, голяма част от кодът се повтаря (egcd го има в кажи-речи всяка). Общите помощни функции ще бъдат отделени в този файл, наречен utils.py:


Естествено, горният код няма претенции за съвършенство. Ако нещо в него изглежда грешно или не оптимално - моля, поправи го.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License