Задачи и упражнения
Для тех, кого увлекло содержимое этой книги и кто хочет закрепить полученные знания, предлагается ряд задач, самостоятельное решение которых поможет несколько глубже понять криптографическую стряпню и теорию. Задачи повышенной сложности отмечены знаком Т.
1. Докажите, что каждая подгруппа циклической группы сама будет циклической.
2. Будут ли циклическими группы по умножению целых чисел, вычисляемых по модулям 5,6,7,8? Как цикличность связана со значением модуля? 3. Перестановка двух элементов множества называется транспозицией. Как любую перестановку заменить последовательностью транспозиций? Сколько транспозиций понадобится, если переставляется n элементов?
4. Любая перестановка Р может быть разложена на непересекающиеся циклы элементов, переходящих друг в друга. Так, цикл (х, у, z) означает, что у=Рх, z=Py и x=Pz. Докажите, что существует целое число k, такое, что при любом х из переставляемого множества, выполняется
(P**k)*x=x
5. Вычислите максимальное значение k в предыдущей задаче для перестановки множества из 10 элементов.
6. Найдите условие, при котором для перестановки Р и любого элемента х будет справедливо (Р**2)*х=х. Что означает это свойство перестановки для криптографии?
7. Для контроля качества шифрования и расшифровывания в текст сообщения включают так называемую сигнатуру, находящуюся в определенном месте, например, в начале. Если сигнатура фиксированная, например - "ENCRYPTION PROG", то не ослабляет ли это шифр? Как повлияет на криптографическую стойкость шифра сигнатура в виде суммы XOR, выполненная по всем символам текста?
8. Выпишите все невырожденные матрицы 2х2 над GF(2). Какова их доля от общего числа матриц 2х2? Какое число невырожденных матриц над GF(2) размера 16х16?
9. Проверьте, образуют ли поле остатки от деления на многочлен х**4+х**2+1.
10. Докажите, что при положительных целых числах k, m и n число k**n-1 тогда и только тогда делится на k**m-1, когда n делится на m.
11. Докажите, что многочлен х**5+х**4+х**3+1 имеет порядок 13.
12. Докажите, что многочлен х**4+х+1 примитивен над GF(2).
13. Сравните мультипликативные группы, порожденные вычетами по неприводимым над GF(2) многочленам х**3+х**2+1 и х**3+х+1.
14. Т Доказать, что если многочлен р(х)**n примитивен над GF(2), то многочлен р(х)**k примитивен тогда и только тогда, когда число k взаимно просто с 2**n-1. Оцените число примитивных многочленов над GF(2**n).
15. T Докажите, что любой многочлен р(х), удовлетворяющий уравнению р(х)**L=1, где L=2 , является степенью примитивного.
16. Вычислите первые десять членов всех последовательностей, удовлетворяющих следующему рекуррентному соотношению Si+S(i-2)+S(i-3).
17. Проверьте, что для предыдущей задачи последовательность, начинающаяся с 101, может быть образована как сумма двух последовательностей, начинающихся с 110 и с 011.
18. Запрограммируйте генератор случайных чисел с многочленом х**9+х**4+1 и проверьте длину его периода.
19. Просчитайте автокорреляционную функцию для ряда псевдослучайных чисел из предыдущей задачи.
20. Покажите, что многочлен х**4+х**3+х**2+х+1 неприводим над GF(2). Каковы длины его последовательностей?
21. Напишите программу, генерирующую случайным образом три заглавные русские буквы с кодами 128-159 в альтернативной кодировке ASCII. Сколько таких трехбуквенных сочетаний всего возможно? Сколько сочетаний из первой тысячи можно принять за осмысленные слова из текста? Оцените количество информации, содержащееся в одной букве такого слова.
22. TYКак изменится вероятность встречи осмысленных сочетаний из трех букв, если буквы выдавать с теми вероятностями, с которыми они встречаются в тексте? Попробуйте применить эту программу для генерации ключей, представляющих осмысленные слова? Насколько при этом увеличится скорость их перебора?
23. Напишите программу, проверяющую файл на наличие в нем осмысленного текста по критерию, что символ пробела с кодом 32 должен встречаться не реже, чем через 20 позиций строки. Оцените качество этого критерия.
24. Напишите программу, проверяющую файл на наличие в нем осмысленного текста по критерию, что пары символов ASCII с кодами 13,10 должны встречаться не реже, чем через 82 позиции, чтобы правильно формировались строки.
25. Оцените качество этого критерия и сравните его с критерием предыдущей задачи.
26. Биграммы th в английском языке и ст в русском самые частые, что позволяет находить тексты в теле программ ЕХЕ или СОМ. Постройте критерий выделения осмысленного текста по частоте какой-нибудь из этих биграмм и оцените его качество.
27. Приняв, что слова в русском языке состоят из 7 букв, оцените число слов русского языка по количеству информации, содержащейся в одной букве, приведенной для биграмм. Сравните полученное число с числом слов в большом орфографическом словаре, считая, что там дана лишь двадцатая часть словоформ.
28. T Попробуйте вскрыть шифровку двойной перестановки ОГО-ТИТ-Р.С-ЕКМСЛ.ИИСЬ-ВЯ. 29. Сколько ключей можно составить из книги среднего объема, если за ключ брать ее текст, начиная с произвольного места? А сколько ключей будет, если текст брать лишь с начала строки?
30. Придумайте ключевое слово из 10 разных букв (наподобие РЕСПУБЛИКА) для кодирования цифр буквами. Насколько это легко было сделать?
31. Почему шифровка несмыслового текста считается очень устойчивой к вскрытию подбором ключа? Насколько эффективна шифровка ключей и в каких случаях?
32. Найдите период последовательности генератора случайных чисел в используемой системе программирования.
33. Найдите первые пять значений ее автокорреляционной функции по полному периоду.
34. Как проверить практически примитивность многочлена?
35. Найдите многочлен, порождающий двоичную последовательность
...001101011101001000110111101...
36. Какая должна быть информационная длина ключа, чтобы шифровку, сделанную им, нельзя было сломать на вашем компьютере за 5 рабочих дней с вероятностью 0.999? Сколько букв смыслового пароля этой длине ключа соответствует?
37. Какие периоды могут порождаться многочленом х**9+х**2+1, если рассмотреть разложение 2**9-1 на простые множители?
38. T Ортогональной матрицей называется такая матрица Р, которая при умножении на себя транспонированную дает диагональную Р*Р'=Е. Например, следующая матрица ортогональна:
111
O11
101
110
Рассмотрите возможность применения ортого- нальных матриц для шифров взбивания.
39. T Пусть есть шифр, при котором каждая буква алфавита может переходить по неизвестному ключу в одну из k букв. Насколько увеличится при этом количество информации, приходящейся на одну букву шифровки по сравнению с исходным текстом?
40. При каких k из предыдущей задачи текст шифровки можно прочесть, если для более-менее уверенного чтения текста человеком ему нужна избыточность хотя бы 20%?
41. T Рассмотрите алгоритм перестановки, когда случайным образом сначала переставляются соседние элементы массива, затем через 1, потом через 3 и так далее. Любую ли перестановку он может реализовать?
42. Что означает отличие значения автокорреляционной функции последовательности от 0 при сдвиге k?
43. Эргодичность числового ряда практики обычно связывают со стремлением автокорреляционной функции к 0 при увеличении сдвига? Приведите примеры числовых рядов из действительных чисел, для которых это не выполняется. Всегда ли это связано с эргодичностью числового ряда?
44. Проверьте, что рекуррентность X(n+1)=Xn*SQR(k), где k=2,3,5, вычисляемая на калькуляторе или ЭВМ, всегда сходится к коротким циклам. Учтите, что подход к циклу может быть много длиннее самого цикла.
45. Будет ли шифр побайтного шифрования Sn+1=Tn XOR Yn XOR Sn, где tn - очередной символ исходного текста, Yn - гамма и Sn+1 с Sn - байты шифровки размножать сбои? Будет ли это размножение катастрофическим, то есть продолжающимся до конца текста шифра?
46. Будет ли шифр из примера 45 катастрофически размножать сбои, если вместо всего байта Sn брать лишь случайные четыре его бита?
47. Напишите программу генерации случайных чисел по таймеру, прерывая им суммирование единиц по модулю 2. Оцените качество получаемых при этом случайных чисел. Это можно сделать, например, так:
ON TIMER(I) GOSUB Random
TIMER ON
M%=0: DO: M% = M% XOR 1: LOOP
Random:
PRINT M%;
RETURN
46. Проверьте перемешивание массива тасовкой на случайность, выполняя фиксированное число тасовок.
47. Прочтите в статистической литературе о критерии хи-квадрат и примените его в программе для распознавания русского текста.
48. T Какова вероятность того, что в хорошо перетасованной колоде хоть одна из карт окажется на своем прежнем месте? Как эта вероятность зависит от числа карт в колоде? Как можно это применить для оценки качества случайной перестановки?
49. Напишите программу, имитирующую шифр Энигмы.
50. T Какова вероятность того, что в перетасованной колоде хотя бы две карты будут следовать в том же порядке, как и в исходной.
51. T Если считать, что избыточность текста сообщения помогает при вскрытии ключа, то оцените длину сообщения достаточную для вскрытия простой замены символов. При этом объем информации от избыточности сообщения должен превысить объем информации, содержащейся в ключе, заданном перестановкой 32 символов алфавита.
