<< Предыдущая

стр. 12
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

JOKOAXLQ lAXJVJZKOG WONOJTL UOKSTAIWUW YVJ
GONOLVCIAD TAG WZCCVJXIAD OAXJOCJOAOZJITL WXZGOAXW
TAG WXTYY, TAG TIUW XV CLTQ T WIDAIYIKTAX JVLO lA
XSO GONOLVCUOAX VY SIDS-XOKSAVLVDQ lAGZWXJQ
I A XSO JODIVA.
XSO GOCTJXUOAX STW T LTJDO CJVDJTUUO VY JOWOTJKS
WZCCVJXOG MQ lAGZWXJQ, XSO OZJVCOTA ZAIVA, TAG
ZE DVNOJAUOAX JOWOTJKS OWXTMLIWSUOAXW TAG
CZMLIK KVJCVJTXIVAW. T EOQ OLOUOAX VY XSIWIW
XSO WXJVAD LIAEW XSTX XSO GOCTJXUOAX STW HIXS
XSO KVUCZXOJ, KVUUZAIKTXIVAW, UIKJVOLOKXJVAIKW
TAG UOGIT lAGZWXJIOW lA XSO MJIWXVL JODIVA.
XSO TKTGOUIK JOWOTJKS CJVDJTUUO IW VJDTAIWOG
lAXV WONOA DJVZCW, LTADZTDOW TAG TJKSIXOKXZJO,
GIDIXTL UOGIT, UVMILO TAG HOTJTMLO KVUCZXIAD,
UTKSIAO LOTJAIAD, RZTAXZU KVUCZXIAD, WQWXOU
NOJIYIKTXIVA, TAG KJQCXVDJTCSQ TAG lAYVJUTXIVA
WOKZJIXQ.
3.3. Шифр замены

Вычислим частоту встречаемости отдельных букв в этом ши-
фротексте (см. табл. 3.3).
Таблица 3.3. Частоты встречаемости букв в шифротексте примера
Буква Частота Буква
Буква Частота Частота
Гс
В
А 8,6995 0,0000 3,0493
Е
D F
0,2690 0,0000
3,1390
Н I
3,6771 0,6278 7,8923
G
К 3,5874
7,0852 L
4,6636
J
N
М 1,0762
0,8968 11,479
0
Р 1,3452 R 0,0896
0,1793 Q
т и
3,5874 8,0717 4,1255
S
W X
V 7,2645 6,6367 8,0717
Z 2,7802
1Y 1,6143

Кроме того, наиболее употребительные биграммы в шифров­
ке — это
ТА, АХ, IA, VA, WX, XS, AG, ОА, J 0 , JV,
а
ОАХ, TAG, IVA, XSO, KVU, TXI, UOA, AXS —
чаще всего встречаюш;иеся триграммы.
Поскольку буква «О» в нашем образце имеет самую высокую ча­
стоту, а именно 11,479, можно предположить, что она соответству­
ет букве «е» открытого текста. Посмотрим, что это может означать
р,ля наиболее обш;их триграмм шифротекста.
- Триграмма ОАХ шифротекста соответствует «е**» исходного
сообш;ения.
- Триграмма XSO шифротекста соответствует «**е» исходного
сообщения.
Вспомним теперь часто употребляемые триграммы в англий­
ском языке (стр. 73) и выберем из них те, которые начинаются или
оканчиваются на букву «е»: ent, eth и the. Заметим, что первая из
популярнейших триграмм шифротекста оканчивается буквой «X»,
а вторая с нее начинается. Аналогичным свойством обладают вы­
бранные триграммы открытого текста: ent и the. У них есть общая
буква «t». В связи с этим можно с большой долей вероятности за­
ключить, что имеет место соответствие
X = t, S = h, А
п.
Даже после столь небольшого анализа мы намного облегчили по­
нимание открытого текста, скрытого в шифровке. Ограничившись
Глава 3. Исторические шифры

двумя первыми предложениями, произведем в них замены наиден­
ных соответствий, считая, что нашли их правильно.
the MJIWtVL JeDIVn hTW Vne VY eZJVCeW LTJDeWt
KVnKentJTtIV nW VY hIDh teKhnVLVDQ InGZWtJQ.
KVUCZteJW, KVUUZnIKTtlVnW TnG UIKJVeLeKtJVnIKW
TJe HeLL JeCJeWenteG, TLVnDWIGe GIDItTL UeGIT,
KVUCZteJ DTUeW TnG eLeKtJVnIK KVUUeJKe.
Напомним, что такое продвижение в дешифровании произошло по­
сле замен:
0 = е, X = t, S = h, A = n.
Теперь мы сжульничаем и воспользуемся тем, что в криптограмме
оставлены промежутки между словами. Поскольку буква «Т» появля­
ется в шифровке как отдельное слово, она может замещать лишь
одну из двух букв открытого текста: «i» или «а». Частота буквы «Т»
в шифротексте — 8,0717, а среднестатистические частоты букв «i»
и «а» равны, соответственно, 7,0 и 8,2 (см. табл. 3.1). Следовательно,
скорее всего
Т = а.
Мы уже рассмотрели самую встречаемую триграмму в шифров­
ке, так что перенесем наше внимание к следующей по популярности
триграмме. Таковой является триграмма TAG. Произведя извест­
ные замены, увидим, что она означает триграмму an* открытого
текста. Отсюда вполне обоснованно можно сделать вывод: G = d,
поскольку триграмма and — одно из наиболее употребительных бу­
квосочетаний английского языка.
При всех сделанных предположениях о соответствии букв ча­
стично дешифрованный кусок шифровки имеет вид:
the MJIWtVL JeDIVn haW Vne VY eZJVCeW LaJDeWt
KVnKentJatIV nW VY hIDh teKhnVLVDQ IndZWtJQ.
KVUCZteJW, KVUUZnIKatlVnW and UIKJVeLeKtJVnIKW
aJe HeLL JeCJeWented, aLVnDWIde dIDItaL Uedia,
KVUCZteJ, DaUeW and eLeKtJVnIK KVUUeJKe.
Такой результат получился после шести замен:
0 = е, X = t, S = h, A = n, Т = а, G = d.
На этом этапе исследуем двубуквенные слова, попадающиеся в
криптограмме.
3.4- Шифр Виоюенера

IX. Это слово, как мы знаем, означает *t. Значит, буква шифра «I»
может замеш;ать либо «а», либо «i», т.к. только два двубуквен-
ных слова английского языка оканчиваются на «t»: «at» и «it».
Однако мы уже убедились, что буква «а» открытого текста
замеш;ается буквой «Т», так что остается одна возможность:
I = i.
XV соответствует сочетанию «t*» открытого текста, откуда V = о.
VY можно заменить на «о*». Поэтому буква «Y» шифровки может
замеш;ать лишь «f», «п» или «г». Но мы уже знаем букву шифро-
текста, подменяюп1;ую собой «п», и у нас остается только две
возможности д^ля выбора. Частота встречаемости символа «Y»
в криптограмме — 1,6, в то время как вероятность встретить
букву «f» в английском тексте равна 2,2, а букву «г»— 6,0. Так
что возможно, имеет место соответствие У = f.
IW должно означать «i*». Таким образом, «W» замещает одну из
четырех букв: «f», «п», «s» или «t». Так как пары для символов
«f», «и» и «t» нам известны, то W = s.
Итак, после вычисленных замен:
О ::= е, X = t, S = h, А = n, Т = а,
G = d, I = i, V = o, Y = f, W=s
первые два предложения шифротекста выглядят так:
the MJistoL JeDion has one of eZJoCe^s LaJDest
KonKentJations of hiDh teKhnoLoDQ indZstJQ.
KoUCZteJs, KoUUZniKations and UiKJoeLeKtJoniKs
aJe HeLL JeCJesented, aLonDside diDitaL Uedia,
KoUCZteJ DaUes and eLeKtJoniK KoUUeJKe.
Даже с половиной определенных букв теперь не очень сложно
понять подлежаш;ий открытый текст, взятый с веб-сайта факульте­
та вычислительной математики Бристольского университета. Мы
оставляем читателю выявить все оставшиеся буквы и восстановить
текст полностью.


3.4. Шифр Виженера
Основной недостаток шифров сдвига и замены заключается в том,
что каждая буква открытого текста при шифровании заменяется
раз и навсегда фиксированным символом. Поэтому при взломе ши­
фра эффективно работает статистика подлежащего языка. Напри-
Глава 3. Исторические шифры

мер, не составляет труда определить, за каким знаком в шифровке
скрывается буква «Е». С начала XIX века разработчики шифров
пытались преодолеть такую связь между открытым текстом и его
шифрованным вариантом.
Шифр замены, описанный в предыдуш;ем параграфе, относится
к так называемым моноалфавитным шифрам замены, в которых
используется только один упорядоченный набор символов, подменя-
юш;ий собой стандартный алфавит. Один из путей решения указан­
ной проблемы состоит в том, чтобы брать несколько наборов симво­
лов вместо стандартного алфавита и шифровать буквы открытого
текста, выбирая соответствуюш;ие знаки из разных наборов в опре­
деленной последовательности. Шифры такого типа носят название
полиалфавитных шифров замены.
Например, можно рассмотреть такое соответствие:
abcdefghijklmnopqr s tuvwxyz
TMKGOYDSIPELUAVCRJWXZNHBQF
D C B A H G F E M L K J I Z Y X W V U T S R Q P ON,
в котором первая строка — английский алфавит, а вторая и тре­
тья — первый и второй алфавиты шифротекста. В этой ситуации
буквы открытого текста, стояш;ие на нечетных позициях, замеш;а-
ются соответствуюш;ими буквами второй строки, а стоящие на чет­
ных — третьей. Таким образом, исходное слово hello в шифротек-
сте будет выглядеть как SHLJV. При этом буква «1», встречаюш;ая-
ся два раза, замеш;ается разными символами. Итак, мы суш;ественно
усложнили применение статистических методов при атаке на шифр.
Если теперь применить наивный частотный анализ, то мы не смо­
жем найти символ шифра, подменяющий собой самую популярную
английскую букву «е».
В этом примере мы, по существу, за один шаг шифруем две бу­
квы. Следовательно, мы имеем дело с блочным шифром, блок кото­
рого равен двум английским буквам. На практике можно использо­
вать не два, а вплоть до пяти различных алфавитов шифротекста,
многократно увеличивая пространство ключей. Действительно, лег­
ко подсчитать, что если мы берем символы из пяти замещающих
наборов, то число возможных ключей равно (26!)^ ^ 2^^^. Однако
пользователю необходимо помнить, что в этом случае ключ — по­
следовательность из 26-5 = 130 букв. Естественно, чтобы усложнить
жизнь Еве, вскрывающей шифр, необходимо скрыть количество ис­
пользуемых алфавитов, считал его частью ключа. Но для среднего
пользователя начала XIX века такая система шифрования казалась
3.4- Шифр Виоюенера

слишком громоздкой, поскольку ключ был слишком большим, чтобы
запомнить его.
Несмотря на указанный недостаток, самые известные шифры
XIX столетия основывались именно на описанном принципе. Шифр
Виэюенера был одним из вариантов полиалфавитного шифра заме­
ны, но имел несложный для запоминания ключ. С одной стороны,
шифр Виженера является полиалфавитным блочным шифром, но его
можно также отнести и к поточным шифрам, естественно обобш;а-
юш;им шифр сдвига.
Как блочный шифр алгоритм Виженера относится к полиалфа­
витным шифрам, множество замеш;аюш;их наборов которого огра­
ничивается 26 циклическими сдвигами стандартного алфавита. Ес­
ли, например, в нем применяются 5 замеш;ающих алфавитов, то про­
странство ключей сводится к 26^ ^ 2^^ возможностям, а в качестве
ключа можно запомнить 5 чисел между О и 25.
Однако описание шифра Виженера как поточного шифра более
естественно. Как и в случае шифра сдвига, мы снова перенумеруем
буквы, начиная с 0. Секретный ключ здесь — это короткая последо­
вательность букв (т.е. слово, часто называемое лозунгом)^ которое
повторяется снова и снова, формируя поток ключей. Кодирование
заключается в сложении букв открытого текста с буквами потока
ключей (воспринимаемых как числа). Например, если ключом явля­
ется слово sesame^ то шифрование выглядит так:

thisi sat estme s sage
+
sesamese same se same
"LLASUWSXWSFQWWKASI.
Заметим, что и в этом примере буква «а» замеп];ается различными
символами в зависимости от того, на каком месте открытого текста
она стоит.
Шифр Виженера все же не очень сложно взломать, опираясь
на статистику подлежаш;его языка. Как только мы узнаем длину
ключевого слова, нам останется несколько раз применить тактику
взлома шифра сдвига.
В качестве примера рассмотрим следующую криптограмму:
UTPDHUG NYH USVKCG МУСЕ FXL KQIB. WX RKU GI TZN,
RLS BHZLXMSNP KDKS; СЕВ Ш HKEWIBA, YYM SRB PER
SBS, JV UPL О UVADGR HRRWXF. JV ZTVOOV УН ZCQU У
UKWGEB, PL UQFB Р FOUKCG, TBF RQ VHCF R KPG, 0U
КЕТ ZCQU MAW QKKW ZGSY, ЕР PGM QKETK UQEB DER EZRN,
MCYE, MG UCTESVA, WP КЕТ ZCQU MAW KOIJS, LCOV
Глава 3. Исторические шифры

NTHDNV JPNUJVB Ш GGV RWX ONKCGTHKFL XG VKD, ZJM
VG CCI MVGD JPNUJ, RLS EWVKJT ASGUCS MVGD; DDK
VG NYH PWUV CCHIIY RD DBQN RWTH PFRWBBI VTTK
VCGNTGSF FL IAWU XJDUS, HFP VHSF, RR LAWEY QDFS
RVMEES FZB СНН JRTT MVGZP UBZN FD ATIIYRTK WP КЕТ
HIVJCI; TBF BLDPWPX RWTH ULAW TG VYCHX KQLJS US
DCGCW OPPUPR, VG KFDNUJK GI JIKKC PL KGCJ lAOV
KFTR GJFSAW KTZLZES WG RWXWT VWTL WP XPXGG, CJ
EPOS VYC BTZCUW XG ZGJQ PMHTRAIBJG WMGEG. JZQ DPB
JVYGM ZCLEWXR:CEB lAOV NYH JIKKC TGCWXE UHE JZK.
WX VCULD YTTKETK WPKCGVCWIQT PWVY QEBFKKQ, QNH
NZTTWIREL IAS VERPE ODJRXGSPTC EKWPTGEES, GMCG
TTVVPLTEEJ; YCW WV NYH TZYRWH LOKU MU AWO, KEPM
VG BLTP VQN RD DSGG AWKWUKKPL KGCJ, XY GPP KPG
ONZTT ICUJCHLSE KET DBQHJTWUG. DYN MVCK ZT MEWCW
HTWE ED JL, GPU YAE CH LQ! PGR UE, YH MWPP RXE
CDJCGOSE, XMS UZGJQJL, SXVPN HBG!
Существует способ, с помощью которого можно определить дли­
ну лозунга, генерирующего поток ключей. Этот способ называют
тестом Казисского. Его идея основана на периодичности пото­
ка ключей. Кроме того, в естественном языке существуют часто
встречаемые буквосочетания: биграммы и триграммы. Учитывая
это, возникает надежда, что повторяющиеся наборы символов в ши-
фротексте — след повторений популярных биграмм и триграмм
открытого текста. Расстояние между повторениями в таком слу­

<< Предыдущая

стр. 12
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>