Вероятности биграмм в тексте
Вероятности биграмм в тексте
АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШПТЬЫЬЭЮЯ Процент
А 278677774777883767826677550000679 71
Б 711016226056357275070541055722035 13
В 805048037167568466660301300820048 38
Г 601165006045448070060012000000004 10
Д 816348107047178465271333400640457 25
Е 556786664778896588933656560011559 73
Ж 600067217050271012130000000020002 8
3 846264116155667150060021002620046 14
И 667668577776885578815777630100679 64
и 003030000036540006600012300000008 11
к 815116527127058076670060100000007 29
л 841218618044167003363003110680786 31
м 757228017044768513161000000730068 32
н 903368119060178005765253000850467 50
о 288886776878876788832567650015259 89
п 700008047036148494562010000453044 28
р 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
Задачи и упражнения
Для тех, кого увлекло содержимое этой книги и кто хочет
закрепить полученные знания, предлагается ряд задач,
самостоятельное решение которых поможет несколько глубже понять
криптографическую стряпню и теорию. Задачи повышенной сложности
отмечены знаком Т.
- Докажите, что каждая подгруппа циклической группы сама будет
циклической.
- Будут ли циклическими группы по умножению целых чисел, вычисляемых
по модулям 5,6,7,8?
Как цикличность связана со значением модуля?
- Перестановка двух элементов множества называется транспозицией.
Как любую перестановку заменить последовательностью транспозиций?
Сколько транспозиций понадобится, если переставляется n элементов?
- Любая перестановка Р может быть разложена на непересекающиеся циклы
элементов, переходящих друг в друга. Так, цикл (х, у, z) означает, что
у=Рх, z=Py и x=Pz. Докажите, что существует целое число k, такое, что
при любом х из переставляемого множества, выполняется (P**k)*x=x
- Вычислите максимальное значение k в предыдущей задаче для
перестановки множества из 10 элементов.
- Найдите условие, при котором для перестановки Р и любого элемента
х будет справедливо (Р**2)*х=х. Что означает это свойство перестановки
для криптографии?
- Для контроля качества шифрования и расшифровывания в текст сообщения
включают так называемую сигнатуру, находящуюся в определенном месте,
например, в начале. Если сигнатура фиксированная, например
- "ENCRYPTION PROG", то не ослабляет ли это шифр? Как повлияет на
криптографическую стойкость шифра сигнатура в виде суммы XOR,
выполненная по всем символам текста?
- Выпишите все невырожденные матрицы 2х2 над GF(2). Какова их доля от
общего числа матриц 2х2? Какое число невырожденных матриц над GF(2)
размера 16х16?
- Проверьте, образуют ли поле остатки от деления на многочлен
х**4+х**2+1.
- Докажите, что при положительных целых числах k, m и n число
k**n-1 тогда и только тогда делится на k**m-1, когда n делится на m.
- Докажите, что многочлен х**5+х**4+х**3+1 имеет порядок 13.
- Докажите, что многочлен х**4+х+1 примитивен над GF(2).
- Сравните мультипликативные группы, порожденные вычетами
по неприводимым над GF(2) многочленам х**3+х**2+1 и х**3+х+1.
- Т Доказать, что если многочлен р(х)**n примитивен над GF(2),
то многочлен р(х)**k примитивен тогда и только тогда, когда число
k взаимно просто с 2**n-1. Оцените число примитивных многочленов над
GF(2**n).
- T Докажите, что любой многочлен р(х), удовлетворяющий уравнению
р(х)**L=1, где L=2 , является степенью примитивного.
- Вычислите первые десять членов всех последовательностей,
удовлетворяющих следующему рекуррентному соотношению
Si+S(i-2)+S(i-3).
- Проверьте, что для предыдущей задачи последовательность,
начинающаяся с 101, может быть образована как сумма двух
последовательностей, начинающихся с 110 и с 011.
- Запрограммируйте генератор случайных чисел с многочленом х**9+х**4+1
и проверьте длину его периода.
- Просчитайте автокорреляционную функцию для ряда псевдослучайных чисел
из предыдущей задачи.
- Покажите, что многочлен х**4+х**3+х**2+х+1 неприводим над GF(2).
Каковы длины его последовательностей?
- Напишите программу, генерирующую случайным образом три заглавные
русские буквы с кодами 128-159 в альтернативной кодировке ASCII.
Сколько таких трехбуквенных сочетаний всего возможно? Сколько сочетаний
из первой тысячи можно принять за осмысленные слова из текста? Оцените
количество информации, содержащееся в одной букве такого слова.
- TY Как изменится вероятность встречи осмысленных сочетаний из трех
букв, если буквы выдавать с теми вероятностями, с которыми они встречаются
в тексте? Попробуйте применить эту программу для генерации ключей,
представляющих осмысленные слова? Насколько при этом увеличится скорость
их перебора?
- Напишите программу, проверяющую файл на наличие в нем осмысленного
текста по критерию, что символ пробела с кодом 32 должен встречаться не
реже, чем через 20 позиций строки. Оцените качество этого критерия.
- Напишите программу, проверяющую файл на наличие в нем осмысленного
текста по критерию, что пары символов ASCII с кодами 13,10 должны
встречаться не реже, чем через 82 позиции, чтобы правильно формировались
строки.
- Оцените качество этого критерия и сравните его с критерием предыдущей
задачи.
- Биграммы th в английском языке и ст в русском самые частые, что
позволяет находить тексты в теле программ ЕХЕ или СОМ. Постройте
критерий выделения осмысленного текста по частоте какой-нибудь из
этих биграмм и оцените его качество.
- Приняв, что слова в русском языке состоят из 7 букв, оцените число
слов русского языка по количеству информации, содержащейся в одной букве,
приведенной для биграмм. Сравните полученное число с числом слов в
большом орфографическом словаре, считая, что там дана лишь двадцатая
часть словоформ.
- T Попробуйте вскрыть шифровку двойной пeрестановки
ОГО-ТИТ-Р.С-ЕКМСЛ.ИИСЬ-ВЯ.
- Сколько ключей можно составить из книги среднего объема, если за ключ
брать ее текст, начиная с произвольного места? А сколько ключей будет,
если текст брать лишь с начала строки?
- Придумайте ключевое слово из 10 разных букв (наподобие РЕСПУБЛИКА) для
кодирования цифр буквами. Насколько это легко было сделать?
- Почему шифровка несмыслового текста считается очень устойчивой к
вскрытию подбором ключа? Насколько эффективна шифровка ключей и в каких
случаях?
- Найдите период последовательности генератора случайных чисел в
используемой системе программирования.
- Найдите первые пять значений ее автокорреляционной функции по полному
периоду.
- Как проверить практически примитивность многочлена?
- Найдите многочлен, порождающий двоичную последовательность
...001101011101001000110111101...
- Какая должна быть информационная длина ключа, чтобы шифровку, сделанную
им, нельзя было сломать на вашем компьютере за 5 рабочих дней
с вероятностью 0.999? Сколько букв смыслового пароля этой длине ключа
соответствует?
- Какие периоды могут порождаться многочленом х**9+х**2+1, если
рассмотреть разложение 2**9-1 на простые множители?
- T Ортогональной матрицей называется такая матрица Р, которая при
умножении на себя транспонированную дает диагональную Р*Р'=Е.
Например, следующая матрица ортогональна:
111
O11
101
110
Рассмотрите возможность применения ортогональных матриц для шифров взбивания.
- T Пусть есть шифр, при котором каждая буква алфавита может переходить
по неизвестному ключу в одну из k букв. Насколько увеличится при этом
количество информации, приходящейся на одну букву шифровки по сравнению
с исходным текстом?
- При каких k из предыдущей задачи текст шифровки можно прочесть, если
для более-менее уверенного чтения текста человеком ему нужна избыточность
хотя бы 20%?
- T Рассмотрите алгоритм перестановки, когда случайным образом сначала
переставляются соседние элементы массива, затем через 1, потом через 3 и
так далее. Любую ли перестановку он может реализовать?
- Что означает отличие значения автокорреляционной функции
последовательности от 0 при сдвиге k?
- Эргодичность числового ряда практики обычно связывают со стремлением
автокорреляционной функции к 0 при увеличении сдвига? Приведите примеры
числовых рядов из действительных чисел, для которых это не выполняется.
Всегда ли это связано с эргодичностью числового ряда?
- Проверьте, что рекуррентность X(n+1)=Xn*SQR(k), где k=2,3,5,
вычисляемая на калькуляторе или ЭВМ, всегда сходится к коротким циклам.
Учтите, что подход к циклу может быть много длиннее самого цикла.
- Будет ли шифр побайтного шифрования Sn+1=Tn XOR Yn XOR Sn, где
tn - очередной символ исходного текста, Yn - гамма и Sn+1 с Sn - байты
шифровки размножать сбои? Будет ли это размножение катастрофическим,
то есть продолжающимся до конца текста шифра?
- Будет ли шифр из примера 45 катастрофически размножать сбои, если
вместо всего байта Sn брать лишь случайные четыре его бита?
- Напишите программу генерации случайных чисел по таймеру, прерывая им
суммирование единиц по модулю 2. Оцените качество получаемых
при этом случайных чисел. Это можно сделать, например, так:
ON TIMER(I) GOSUB Random
TIMER ON
M%=0: DO: M% = M% XOR 1: LOOP
Random:
PRINT M%;
RETURN
- Проверьте перемешивание массива тасовкой на случайность, выполняя
фиксированное число тасовок.
- Прочтите в статистической литературе о критерии хи-квадрат и
примените его в программе для распознавания русского текста.
- T Какова вероятность того, что в хорошо перетасованной колоде хоть
одна из карт окажется на своем прежнем месте? Как эта вероятность
зависит от числа карт в колоде? Как можно это применить для оценки
качества случайной перестановки?
- Напишите программу, имитирующую шифр Энигмы.
- T Какова вероятность того, что в перетасованной колоде хотя бы две
карты будут следовать в том же порядке, как и в исходной.
- T Если считать, что избыточность текста сообщения помогает при
вскрытии ключа, то оцените длину сообщения достаточную для вскрытия
простой замены символов. При этом объем информации от избыточности
сообщения должен превысить объем информации, содержащейся в ключе,
заданном перестановкой 32 символов алфавита.
