Ответы к заданиям — Криптография

Загляни сюда только после того, как сам(а) попробовал(а) решить!

Везде, где речь о буквах, — русский алфавит, 33 буквы (А=0, …, Я=32).

Урок 1. Шифр Цезаря

1. УПЧ — М(13)+7=20=У, И(9)+7=16=П, Р(17)+7=24=Ч.
2. ЩШКОНЙ — П(16)+10=26=Щ, О(15)+10=25=Ш, Б(1)+10=11=К, Е(5)+10=15=О, Д(4)+10=14=Н, А(0)+10=10=Й.
3. МИР — вычитаем 7: У(20)−7=13=М, П(16)−7=9=И, Ч(24)−7=17=Р.
4. ЧИСЛО — вычитаем 4: Ы(28)−4=24=Ч, М(13)−4=9=И, Х(22)−4=18=С, П(16)−4=12=Л, Т(19)−4=15=О.
5. ЛОГИКА (ключ 5). При переборе ключей 3…7 осмысленное слово даёт только k=5: Р(17)−5=12=Л, У(20)−5=15=О, З(8)−5=3=Г, Н(14)−5=9=И, П(16)−5=11=К, Е(5)−5=0=А.
6. Ключ 8. Самая частая буква Ц (номер 23) соответствует О (номер 15), значит сдвиг $=23-15=8$.
7. У русского алфавита (33 буквы) — 32 осмысленных ключа; у английского (26 букв) — 25 (сдвиг 0 не считается).
8. Одним ключом $(k+m)\mathrm{mod}33$. Два последовательных сдвига складываются в один; чтобы расшифровать, надо снять суммарный сдвиг.

Урок 2. Шифр Виженера

1. УУЫА — Г(3)+Р(17)=20=У; О(15)+Е(5)=20=У; Р(17)+К(11)=28=Ы; А(0)+А(0)=0=А.
2. КИЮЮШ — Т(19)+Ш(25)=44≡11=К; А(0)+И(9)=9=И; Й(10)+Ф(21)=31=Ю; Н(14)+Р(17)=31=Ю; А(0)+Ш(25)=25=Ш.
3. МАТЕМАТИКА — ключ КОД повторяется К-О-Д-К-О-Д-К-О-Д-К; вычитаем сдвиги 11,15,4,… из Ч,О,Ц,П,Ы,Д,Э,Ч,О,К.
4. ООРВ. Ключ ВОД под МАМА даёт В-О-Д-В. Первая М: 13+2=15=О. Вторая М: 13+4=17=Р. Одинаковые М превратились в разные буквы (О и Р), потому что попали под разные буквы ключа (В и Д) — в этом и суть многоалфавитности.
5. Распадается на 5 шифров Цезаря; в каждую «стопку» попадёт $40:5=$ 8 букв.
6. Длина ключа — делитель 12, кроме 1: 2, 3, 4, 6 или 12.
7. У Цезаря сдвиг один на весь текст, поэтому частоты букв просто «съезжают», но горб самой частой буквы сохраняется — его сразу видно. У Виженера сдвигов несколько, они перемешивают частоты и сглаживают горб; частотный анализ заработает лишь после того, как найдена длина ключа и текст разбит на «стопки» с одним сдвигом в каждой.
8. В шифр Цезаря. Ключ из одной буквы задаёт один-единственный сдвиг для всего текста.

Урок 3. Простые числа

1. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 — простые до 50.
2. $84=2^2\cdot 3\cdot 7$ (84 = 2·42 = 2·2·21 = 2·2·3·7).
3. $561=3\cdot 11\cdot 17$ (561 : 3 = 187 = 11 · 17).
4. 91 — составное: $91=7\cdot 13$. 101 — простое: не делится ни на одно простое до $\sqrt{101}\approx 10$ (2, 3, 5, 7).
5. Достаточно проверять делители до $\sqrt{199}\approx 14,1$, то есть простые 2, 3, 5, 7, 11, 13.
6. Простых от 1 до 20 — восемь: 2, 3, 5, 7, 11, 13, 17, 19.
7. $31$ не делится ни на 2, ни на 3, ни на 5 (везде остаток 1). Это показывает, что построенное в доказательстве Евклида число даёт новый простой делитель вне исходного списка (здесь само 31 — простое) — значит, список простых не может быть полным.
8. Если считать 1 простым, к любому разложению можно было бы приписывать сколько угодно единиц: $6=2\cdot 3=1\cdot 2\cdot 3=1\cdot 1\cdot 2\cdot 3=\dots$ — единственность пропала бы.

Урок 4. Модульная арифметика

1. $(23+19)\mathrm{mod}7=42\mathrm{mod}7=$ 0.
2. $(8\cdot 9)\mathrm{mod}5=72\mathrm{mod}5=$ 2.
3. $(9+20)\mathrm{mod}12=29\mathrm{mod}12=$ 5 часов.
4. 7 — обратный к 4 по модулю 9, потому что $4\cdot 7=28=3\cdot 9+1\equiv 1(\mathrm{mod}9)$.
5. У 6 нет обратного по модулю 9, потому что $\gcd (6,9)=3\ne 1$. Все кратные 6 по модулю 9 дают только 0, 6, 3 — единицы среди них нет.
6. $2^{10}=1024$, а $1024\mathrm{mod}1000=$ 24.
7. 4. Так как $3^6\equiv 1(\mathrm{mod}7)$, а $100=6\cdot 16+4$, то $3^{100}\equiv (3^6{)}^{16}\cdot 3^4\equiv 1\cdot 3^4=81\equiv 4(\mathrm{mod}7)$.
8. Если $a\equiv b(\mathrm{mod}m)$, то $m$ делит $a-b$. Тогда $a^2-b^2=(a-b)(a+b)$ тоже делится на $m$ (первый множитель делится), значит $a^2\equiv b^2(\mathrm{mod}m)$. ∎

Урок 5. Обмен ключами Диффи–Хеллмана

1. Смешать две краски легко, а разделить смесь обратно на исходные цвета практически невозможно. Эта «односторонность» и позволяет обмениваться смесями открыто, не выдавая секретных красок.
2. $A=5^2\mathrm{mod}23=25\mathrm{mod}23=$ 2.
3. $B=5^2\mathrm{mod}23=$ 2; общий секрет $=B^a\mathrm{mod}23=2^2\mathrm{mod}23=$ 4 (то же даёт $A^b=2^2=4$).
4. Открыто: $p$, $g$, $A$, $B$. Секретны и подслушивающему неизвестны $a$, $b$ и сам общий секрет.
5. Задача дискретного логарифма (найти показатель $a$ по известным $g$, $p$ и $A=g^a\mathrm{mod}p$).
6. При большом $p$ дискретный логарифм невозможно вычислить перебором за разумное время, тогда как при $p=23$ секрет находится мгновенно. Большое $p$ и обеспечивает стойкость.
7. Оба вычисляют одно и то же число $g^{ab}\mathrm{mod}p$: Алиса как $(g^b{)}^a$, Боб как $(g^a{)}^b$. Поскольку $(g^b{)}^a=g^{ab}=(g^a{)}^b$, результаты совпадают.
8. Идея атаки «человек посередине»: злоумышленник перехватывает канал и договаривается по Диффи–Хеллману отдельно с Алисой и отдельно с Бобом, выдавая себя каждому за другого. Тогда у него общий секрет с обоими, и он читает (и подменяет) все сообщения. Защита — подтверждать личность собеседника (например, цифровой подписью из урока 7).

Урок 6. Идея RSA

Ключи из урока: $n=33$, $e=7$, $d=3$.

1. $n=3\cdot 11=$ 33; $\phi =(3-1)(11-1)=2\cdot 10=$ 20.
2. $7\cdot 3=21=20+1\equiv 1(\mathrm{mod}20)$ — значит, 7 и 3 взаимно обратны по модулю 20. ✓
3. $c=8^7\mathrm{mod}33=$ 2.
4. $m=2^3\mathrm{mod}33=8$ — исходное число вернулось. ✓ (Проверка: $8^7\mathrm{mod}33=2$, затем $2^3=8$.)
5. $c=10^7\mathrm{mod}33=$ 10. Забавно: число зашифровалось само в себя (это редкая «неподвижная точка»; в настоящем RSA с большими числами такое почти не встречается и не вредит стойкости).
6. При $p=5$, $q=11$: $n=55$, $\phi =4\cdot 10=$ 40.
7. Все вычисления идут по модулю $n$, поэтому результат — это остаток от 0 до $n-1$. Если $m\ge n$, разные сообщения давали бы одинаковый остаток, и однозначно расшифровать было бы нельзя.
8. Чтобы найти $d$, нужен $\phi =(p-1)(q-1)$, а для него — разложить $n$ на простые $p$ и $q$. Факторизация большого $n$ практически невыполнима, поэтому $d$ вычислить не удаётся, хотя открытый ключ $(n,e)$ у всех на виду.

Урок 7. Хэши, пароли и цифровая подпись

1. Главное отличие: шифрование обратимо (расшифровал ключом — вернул данные), а хэш односторонний — по нему исходные данные восстановить нельзя.
2. Односторонность, лавинный эффект (малое изменение входа полностью меняет хэш) и стойкость к коллизиям (трудно найти два входа с одинаковым хэшем).
3. Потому что при краже базы утекут только хэши, а из них пароли не восстановить. Сайт проверяет вход, сравнивая хэши, и сам пароль хранить не обязан.
4. Соль — случайная строка, добавляемая к паролю перед хэшированием, своя у каждого пользователя. Она защищает от заранее заготовленных таблиц хэшей («радужных таблиц») для популярных паролей.
5. Потому что к каждому «qwerty» добавляется своя случайная соль, и после хэширования получаются разные строки. Одинаковые пароли в базе выглядят по-разному.
6. Создают подпись закрытым ключом автора, а проверяют — его открытым ключом.
7. Не пройдёт. Изменённый текст даёт другой хэш, а подпись сделана под старым хэшем. При проверке два хэша не совпадут, и подпись будет признана недействительной.
8. Хэш — короткий и фиксированной длины, его быстро посчитать и подписать одной операцией, тогда как подписывать длинный документ целиком медленно и неудобно. При этом хэш надёжно «представляет» весь документ: изменение любой буквы меняет хэш, так что защита целостности сохраняется.