р 916448608052668426673542420740167 48
с 646257207078668756963515500561387 43
т 827148008064569388460004021780158 60
у 344667653365560677715506360000748 19
ф 600005006002206040354000000100002 4
х 433004003011056053130020001000008 6
ц 506006007000003000040000000500005 6
ч 701008007061062010730001300130004 12
ш 500006007033034030340000000040005 3
щ 600007006000020020040000000040101 3
ъ 000004000000000000000000000000032 1
ы 147357151755621555600705410100018 18
ь 010003071060471006400001610000628 12
э 004001000265210201704300000000001 4
ю 050020120410000003700006170010307 6
я 015256250223650144700443040000649 18
789787588386899989877678511218260 138
200 наиболее частых паролей
ДАА ЛВС ADVENTURE AFGAN ALEX
ALEXEY ALIEN ALPHA ANDREI ANDREY
ANN ANTON APPLE BAND BANK
BARON BEAR BEAT BEATLES BEST
BETA BLACK BLUE BOARD BORIS
BOY CAN CASTLE CAT CENTER
CHANCE CHAOS CHERRY CLUB COCKTAIL
COMPUTER CROSS DATA DEATH DECEMBER
DELTA DENIS DEVIL DIMA DMITRIY
DM1 TRY DOG DOOR DRAGON DREAM
EAGLE EAST EASY ELENA EUGENE
EYE FIELD FILTER FINISH FLOWER
FORCE FRIEND FUN GEORGE GIRL
GOLF GREAT GREEN GRAY HAND
HELL HELLO HELP HERO HOCKEY
HORSE HOUSE IGOR ILYA INFO
IRENE IRON JAZZ JOB JULIA
JURY KILLER KIRILL KNIGHT KOSTYA
LAND LARRY LAST LEGAL LENIN
LIGHT LITTLE LONG LORD LOVE
MAD MAGIC MAJOR MARK MARKET
MASTER MEGA METAL MICHAEL MIKE
MISTER MOSCOW MUSIC NATALIA NETWORK
NICE NIGHT NORMAL NORTH OLD
OLEG OMEGA PANEL PARADISE PASSWORD
PAVEL PETER PHILIP PHONE PILOT
PIZZA POLICE PRINCE PROTECT QUEST
RAIN RANGER REAL RED REMOTE
RISK RIVER ROBOT ROMAN ROOM
ROSE RUSLAN RUSSIA SASHA SCHOOL
SECRET SECURE SERGE SERGEI SERGEY
SERVICE SEX SHADOW SHARK SHIT
SHOP SIMPLE SKY SLAVA SMILE
SOUND SOUTH SPY SQUARE STANDARD
STAR STATION STREET SUCCESS SUMMER
SUPER SWEET SYSTEM TARGET TEAM
TIGER TIME TOY TRADE TRUE
UNKNOWN VALENTIN VICTOR VISIT VLAD
VLADIMIR WATER WEST WHITE WILD
WIND WOLF YURI YURIK ZONE
Задачи и упражнения
Для тех, кого увлекло содержимое этой книги и кто хочет
закрепить полученные знания, предлагается ряд задач,
самостоятельное решение которых поможет несколько глубже понять
криптографическую стряпню и теорию. Задачи повышенной сложности
отмечены знаком Т.
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 Ортогональной матрицей называется такая
матрица Р, которая при умножении на себя
транспонированную дает диагональную Р*Р'=Е.
Например, следующая матрица ортогональна:
O11
Рассмотрите возможность применения ортого-
нальных матриц для шифров взбивания.
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
символов алфавита.
Библиография
1. Albert, Burton, Jr. Codes for Kids (Whitman, 1976)
2. Albert, Burton, Jr. More Codes for Kids
(Whitman, 1979)
3. B.Beckett. Introduction to cryptology (Blackwell
Scientific Publications, 1988)
4. Babson, Walt. All Kinds of Codes (Scholastic, 1976)
5. Barker, Wayne G., Manual of Cryptography (1981)
6. Ban-on, John, KGB: The Secret Work of Soviet
Secret Agents (1973)
7. Brassaid G. Modem Kryptology. Springer-Veriag (1988)
8. Bruce Schneier, "Applied Cryptography: Protocols,
Algorithms, and Source Code in C", John Wiley &
Sons (1993)
9. Clark, R.W. The Man Who Broke Purple: A Life
of the World's Greatest Cryptologist, Colonel
William F. Friedman (Little, 1977)
10. Banning, Dorothy E., Cryptography and
Protection (1982)
II. Dulles, Alien A., The Craft of Intelligence (1963)
12. Friedman, W.F., Elements ofCryptanalysis (1976)
13. Gardner, Martin, Codes, Ciphers, and Secret
Writing (1984)
14. Gleason, Norma. Cryptograms and Spygrams
(Dover, 1981)
15. Harris, Christopher, et al., Hazardous Waste:
Confronting the Challenge (1987)
16. Kahn, David, Kahn on Codes (Macrnillan, 1983)
17. Kahn, David. Kahn on Codes: New Secrets of
Cryptology (Macrnillan, 1983)
18. Kahn, David. The Codebreakers: The Story of
Secret Writing (Macrnillan, 1967)
19. Konheim, A.G. Cryptography: A Primer (Wiley, 1981)
20. Laflin, John. Codes and Ciphers: Secret Writing
Through the Ages (Harper, 1964)
21. Landreth, Bill, A Hacker's Guide to Computer
Security, (Microsoft Press, 1985)
22. Levy, Steven. Hackers: Heroes of the Computer
Revolution. (Doubleday, 1984)
23. Lysing, Henry. Secret Writing: An Introduction to
Cryptograms, Ciphers, and Codes (Dover, 1974)
24. Mayer, Carl, and Matyas, Stephen, Cryptography:
New Dimensions in Computer Security (1982)
25. Parker, Donn B. Crime By Computer. (Charles
Scribner's Sons, 1976)
26. Pierce, С. C" Crypto-privacy (1988)
27. Sarnoff, Jane and Ruffins, Reynold. The Code and
Cipher Book (Scribner, 1975)
28. Seberry J., Pieprzyk J., Cryptography. An intro-
duction to computer security. (Prentice Hall, 1989)
29. Sinkov, Abraham, Cryptanalysis: A Mathematical
Approach (1980)
30. Smith, L.D. Cryptography: The Science of Secret
Writing (Dover, 1955)
31. Wmterbotham, Frederick W., The Ultra Secret (1982)
32. Wohlstetter, Roberta, Pearl Harbor: Warning and
Decision (1962)
33. Wolfe, James R., Secret Writing: The Craft of the
Cryptographer (1970)
34. Zim, H.S. Codes and Secret Writing (Morrow, 1948)
Дата добавления: 2015-08-28; просмотров: 25 | Нарушение авторских прав
| <== предыдущая лекция | | | следующая лекция ==> |