Алгоритм 2

1. Построить начальный вариант ключа k на основе сравне­ния частот знаков криптограммы и открытого текста.

2. Положить v = f (D_k (y)).

3. Положить k ¢ = k.

4. Поменять местами в нижней строке подстановки k ¢ неко­торую пару букв, скажем и .

5. Положить у ¢ = f (D_k ¢ (y)).

6. Если v ¢ < v, то положить k = k ¢, v ¢ = v и перейти к 4.

7. Перейти к шагу 3.

Алгоритм заканчивается, когда условие v ¢ < v не выпол­няется в течение некоторого числа итераций, например 100.

Переход на шаге 4 от k к k ¢, связанный с транспозицией пары символов, имеет под собой следующее основание. На шаге 5 вычисляется величина

,

где — матрица, полученная из матрицы путем перестановки в ней столбцов с номерами и , а также строк с теми же номерами.

В силу отмеченного свойства на шаге 5 алгоритма ненужно проводить трудоемкую операцию вычисления матрицы биграмм непосредственно по «расшифрованно­му» тексту D_k ¢(у). Достаточно вычислить лишь матрицу , а на следующих шагах алгоритма производить в ней одноименные перестановки строк и столбцов.

Выбор транспозиции (, ) на шаге 4 можно произво­дить, например, следующим естественным образом. Пусть — вектор, образованный буквами криптограммы, упорядоченными по убыванию частот. Тогда после­довательность транспозиций можно выбрать такой:

В авторской работе показано, что алгоритм 2 является достаточно эффективным.

Частота встречаемости знаков^*

В алфавитном порядке:

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ы

Ь

Ъ

Э

Ю

Я

В порядке убывания частот встречаемости:

О

Е

А

И

Н

Т

С

Р

В

Л

К

М

Д

П

У

Я

З

Ы

Б

Г

Ч

Й

Х

Ж

Ь

Ъ

Ш

Ю

Ц

Щ

Э

Ф

Частота встречаемости биграмм^*

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ы

Ь

Э

Ю

Я

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ы

Ь

Э

Ю

Я

^*величины указаны в условных единицах пропорционально частотам встречаемости в процентах (см. Алферов и др. «Криптографические методы защиты информации», Приложение 1)

Пример

Пусть имеется следующий шифртекст:

л млсфафшрн ълт кэмэуци; кмехен гэор уе ълтэ хфа: з ъуэа з уфдрж сфх лдэуци ьщэ яфъзх оф гэоз сшлыфа; зъэх уеошеьф - оэщур кеьфъзх, уемэьф - щсексл ыфьфшзх. хеа длъэще: хеа мэчзи тшфъзх, шлщемсе уе ьэхьня щзъзх; хеа уе уэьэъфаця ъфшфюсея щмэъц уэьзъеууця кьэшэи; зктлчсе хеа уе слшрзя уфюсея щхфзх тэк фсфу, тэк ъьэшэи; хеа мэщ з ъфм ьзъэузи офмуц; хеа ф кешэ ошзямцулх ьфмуц уе тшэы оэщдеуци з олщхфи, з хшзъгехр ьзхнкэи ошэсшещуця дшэъфи зк ьфъ ьцяфънх нщуця, з щ узаз ънърсе зя афшщсфи; хеа сфшфмэьзд азафяфъфа омэунэх ышфкуфыф гешн; хеа ь фтмесея оэшэъ уешфъфа дэшэк мэще, дэшэк афшн сфмълу уэщэх тфыехцшн; ь хэаузгэ хеа гешэьуе хлюзх, е тлшци ьфмс эи ьэшуф щмлюзх; хеа щхлое щ тетфж ныфи зъэх, тшэъэх щеае щфтфи, хеа гешр себэи уеъ кмехфа деяуэх; хеа шлщщсзи ъля... хеа шлщрж оеяуэх! з хеа н тцм, з аэъ н озм; л афшн ьзъэм ълт кэмэуци; офъ уза щзъэм, з сфх лдэуци щьфз ауэ щсексз ыфьфшзм. фъул н офауж. щсексл пхл офьэъеж хэоэшр н щьэхл. ъэме ъеьуф азульчзя ъуэи. ошзъеурн щхешзуц ымлтфсфи. ь хфмоэ афылдзя щцуфьэи, щ ъшлкрназ ь ышзъузгэ ьцщфсфи ьмеъзазш щфмугэ озшфьем. аэурчлж ъфдр фу ьцъеьем ке сункн яшетшфыф шлщмеуе, з аэъ зк хнюсфыф щхесеуе ке зя къфшфьрэ ьцозьем. уэ щсфшф эмз ошэъсз уечз. уэ щсфшф ъьзыемзщр сшлыфа сфьчз, щэшэтшнуцэ дечз щ сзонбза озьфа з ьзуфа. фуз ьэщэмрэ ь щэшъгэ мзмз. чзоэме оэуе оф сшена. зя ьеюуф дечузсз уфщзмз з узксф смеунмзщр ыфщхна.

Подсчитав частоты встречаемости букв в шифртексте и упорядочив их по убыванию, сопоставим их с эталонными частотами и получим следующую гипотезу о замене:

Шифр-текст

ф

э

е

з

у

х

ш

ъ

щ

а

ь

м

с

л

о

н

к

и

ц

я

т

р

ы

д

г

ч

ж

ю

б

п

в

й

Эталон

о

е

а

и

н

т

с

р

л

в

к

м

п

д

у

я

з

ы

г

б

ь

ч

й

х

ж

ш

ц

ю

щ

ф

э

ъ

Выполнив замену, получим следующий текст:

д мдпокотчя рдь земенгы; змасая жеуч на рдье сок: и рнек и нохчц пос дхенгы вле борис уо жеуи птдйок; ирес наутаво - уелнч заворис, намево - лпазпд йовотис. сак хдрела: сак мешиы ьторис, тдлампа на весвяб лирис; сак на неверокгб ротоюпаб лмерг невираннгб зветеы; изьдшпа сак на пдтчиб ноюпаб лсоис ьез опон, ьез рветеы; сак мел и ром вирениы уомнг; сак о зате утибмгндс вомнг на ьтей уелхангы и удлсоы, и стиржасч висязеы утепталнгб хтероы из вор вгборяс ялнгб, и л ники рярчпа иб котлпоы; сак потомевих кикоборок уменяес йтознойо жатя; сак в оьмапаб уетер наторок хетез мела, хетез котя помрдн нелес ьойасгтя; в секниже сак жатевна сдюис, а ьдтгы вомп еы ветно лмдюис; сак лсдуа л ьаьоц яйоы ирес, ьтерес лака лоьоы, сак жатч пащеы нар змасок хабнес; сак тдллпиы рдб... сак тдлчц уабнес! и сак я ьгм, и кер я уим; д котя вирем рдь земенгы; уор ник лирем, и пос дхенгы лвои кне лпазпи йовотим. орнд я уокнц. лпазпд фсд уоверац сеуетч я лвесд. рема равно киндвшиб рнеы. утиранчя лсатинг ймдьопоы. в сомуе койдхиб лгновеы, л ртдзчеяки в йтирниже вглопоы вмарикит ломнже уитовам. кенчшдц рохч он вгравам за пнязя бтаьтойо тдлмана, и кер из сяюпойо лсапана за иб зротовче вгуивам. не лпото еми утерпи наши. не лпото рвийамилч птдйок повши, летеьтянге хаши л пиуящик уивок и винок. они велемче в летрже мими. шиуема уена уо птаяк. иб ваюно хашнипи нолими и низпо пманямилч йолсяк.

По критерию «читаемости» можно принять следующие гипотезы, предлагаемые в процессе проверки орфографии редактором MS Word:

намево=> наЛево

пнязя => Князя

низпо => низКо

ваюно => ваЖно

После замены получим следующий текст:

д ЛдКокотчя рдь зеЛенгы; зЛасая жеуч на рдье сок: и рнек и нохчц Кос дхенгы вле борис уо жеуи Ктдйок; ирес наутаво - уелнч заворис, наЛево - лКазКд йовотис. сак хдрела: сак Лешиы ьторис, тдлаЛКа на весвяб лирис; сак на неверокгб ротоЖКаб лЛерг невираннгб зветеы; изьдшКа сак на Кдтчиб ноЖКаб лсоис ьез оКон, ьез рветеы; сак Лел и роЛ вирениы уоЛнг; сак о зате утибЛгндс воЛнг на ьтей уелхангы и удлсоы, и стиржасч висязеы утеКталнгб хтероы из вор вгборяс ялнгб, и л ники рярчКа иб котлКоы; сак КотоЛевих кикоборок уЛеняес йтознойо жатя; сак в оьЛаКаб уетер наторок хетез Лела, хетез котя КоЛрдн нелес ьойасгтя; в секниже сак жатевна сдЖис, а ьдтгы воЛК еы ветно лЛдЖис; сак лсдуа л ьаьоц яйоы ирес, ьтерес лака лоьоы, сак жатч Кащеы нар зЛасок хабнес; сак тдллКиы рдб... сак тдлчц уабнес! и сак я ьгЛ, и кер я уиЛ; д котя виреЛ рдь зеЛенгы; уор ник лиреЛ, и Кос дхенгы лвои кне лКазКи йовотиЛ. орнд я уокнц. лКазКд фсд уоверац сеуетч я лвесд. реЛа равно киндвшиб рнеы. утиранчя лсатинг йЛдьоКоы. в соЛуе койдхиб лгновеы, л ртдзчеяки в йтирниже вглоКоы вЛарикит лоЛнже уитоваЛ. кенчшдц рохч он вграваЛ за Князя бтаьтойо тдлЛана, и кер из сяЖКойо лсаКана за иб зротовче вгуиваЛ. не лКото еЛи утерКи наши. не лКото рвийаЛилч Ктдйок Ковши, летеьтянге хаши л Киуящик уивок и винок. они велеЛче в летрже ЛиЛи. шиуеЛа уена уо Ктаяк. иб ваЖно хашниКи нолиЛи и низКо КЛаняЛилч йолсяк.

Выдвинем новые гипотезы:

КЛаняЛилч => КЛаняЛиСЬ

зЛасая => зЛаТая

ноЖКаб => ноЖКаХ

зеЛенгы = > зеЛенЫЙ

После замены получаем текст (жирным шрифтом выделены слова, которые, предположительно, дешифрованы верно):

д ЛдКокотЬя рдь зеЛенЫЙ; зЛаТая жеуЬ на рдье Ток: и рнек и нохЬц КоТ дхенЫЙ вСе ХориТ уо жеуи Ктдйок; иреТ наутаво - уеСнЬ завориТ, наЛево - СКазКд йовотиТ. Так хдреСа: Так ЛешиЙ ьториТ, тдСаЛКа на веТвяХ СириТ; Так на неверокЫХ ротоЖКаХ СЛерЫ невираннЫХ зветеЙ; изьдшКа Так на КдтЬиХ ноЖКаХ СТоиТ ьез оКон, ьез рветеЙ; Так ЛеС и роЛ вирениЙ уоЛнЫ; Так о зате утиХЛЫндТ воЛнЫ на ьтей уеСханЫЙ и удСТоЙ, и ТтиржаТЬ виТязеЙ утеКтаСнЫХ хтероЙ из вор вЫХоряТ яСнЫХ, и С ники рярЬКа иХ котСКоЙ; Так КотоЛевих кикоХорок уЛеняеТ йтознойо жатя; Так в оьЛаКаХ уетер наторок хетез ЛеСа, хетез котя КоЛрдн неСеТ ьойаТЫтя; в Текниже Так жатевна ТдЖиТ, а ьдтЫЙ воЛК еЙ ветно СЛдЖиТ; Так СТдуа С ьаьоц яйоЙ иреТ, ьтереТ Сака СоьоЙ, Так жатЬ КащеЙ нар зЛаТок хаХнеТ; Так тдССКиЙ рдХ... Так тдСЬц уаХнеТ! и Так я ьЫЛ, и кер я уиЛ; д котя виреЛ рдь зеЛенЫЙ; уор ник СиреЛ, и КоТ дхенЫЙ Свои кне СКазКи йовотиЛ. орнд я уокнц. СКазКд фТд уоверац ТеуетЬ я СвеТд. реЛа равно киндвшиХ рнеЙ. утиранЬя СТатинЫ йЛдьоКоЙ. в ТоЛуе койдхиХ СЫновеЙ, С ртдзЬеяки в йтирниже вЫСоКоЙ вЛарикит СоЛнже уитоваЛ. кенЬшдц рохЬ он вЫраваЛ за Князя Хтаьтойо тдСЛана, и кер из ТяЖКойо СТаКана за иХ зротовЬе вЫуиваЛ. не СКото еЛи утерКи наши. не СКото рвийаЛиСЬ Ктдйок Ковши, СетеьтянЫе хаши С Киуящик уивок и винок. они веСеЛЬе в Сетрже ЛиЛи. шиуеЛа уена уо Ктаяк. иХ ваЖно хашниКи ноСиЛи и низКо КЛаняЛиСЬ йоСТяк.

Далее примем следующие гипотезы:

оьЛаКаХ => оБЛаКаХ

ветно => веРно

СЛдЖиТ => СЛУЖиТ

ьЫЛ => БЫЛ

виреЛ => виДеЛ

СКазКд => СКазКУ

СиреЛ => СиДеЛ

СоЛнже => СоЛнЦе

Получим:

У ЛУКокоРЬя ДУБ зеЛенЫЙ; зЛаТая ЦеуЬ на ДУБе Ток: и Днек и нохЬц КоТ УхенЫЙ вСе ХоДиТ уо Цеуи КРУйок; иДеТ науРаво - уеСнЬ завоДиТ, наЛево - СКазКУ йовоРиТ. Так хУДеСа: Так ЛешиЙ БРоДиТ, РУСаЛКа на веТвяХ СиДиТ; Так на невеДокЫХ ДоРоЖКаХ СЛеДЫ невиДаннЫХ звеРеЙ; изБУшКа Так на КУРЬиХ ноЖКаХ СТоиТ Без оКон, Без ДвеРеЙ; Так ЛеС и ДоЛ виДениЙ уоЛнЫ; Так о заРе уРиХЛЫнУТ воЛнЫ на БРей уеСханЫЙ и уУСТоЙ, и ТРиДЦаТЬ виТязеЙ уРеКРаСнЫХ хРеДоЙ из воД вЫХоДяТ яСнЫХ, и С ники ДяДЬКа иХ коРСКоЙ; Так КоРоЛевих кикоХоДок уЛеняеТ йРознойо ЦаРя; Так в оБЛаКаХ уеРеД наРоДок хеРез ЛеСа, хеРез коРя КоЛДУн неСеТ БойаТЫРя; в ТекниЦе Так ЦаРевна ТУЖиТ, а БУРЫЙ воЛК еЙ веРно СЛУЖиТ; Так СТУуа С БаБоц яйоЙ иДеТ, БРеДеТ Сака СоБоЙ, Так ЦаРЬ КащеЙ наД зЛаТок хаХнеТ; Так РУССКиЙ ДУХ... Так РУСЬц уаХнеТ! и Так я БЫЛ, и кеД я уиЛ; У коРя виДеЛ ДУБ зеЛенЫЙ; уоД ник СиДеЛ, и КоТ УхенЫЙ Свои кне СКазКи йовоРиЛ. оДнУ я уокнц. СКазКУ фТУ уовеДац ТеуеРЬ я СвеТУ. ДеЛа Давно кинУвшиХ ДнеЙ. уРиДанЬя СТаРинЫ йЛУБоКоЙ. в ТоЛуе койУхиХ СЫновеЙ, С ДРУзЬеяки в йРиДниЦе вЫСоКоЙ вЛаДикиР СоЛнЦе уиРоваЛ. кенЬшУц ДохЬ он вЫДаваЛ за Князя ХРаБРойо РУСЛана, и кеД из ТяЖКойо СТаКана за иХ зДоРовЬе вЫуиваЛ. не СКоРо еЛи уРеДКи наши. не СКоРо ДвийаЛиСЬ КРУйок Ковши, СеРеБРянЫе хаши С Киуящик уивок и винок. они веСеЛЬе в СеРДЦе ЛиЛи. шиуеЛа уена уо КРаяк. иХ ваЖно хашниКи ноСиЛи и низКо КЛаняЛиСЬ йоСТяк.

Гипотезы об оставшихся заменах:

к => м

у => п

х => ч

ц => ю

й => г

ф => э

В итоге получаем текст:

У ЛУКоМоРЬя ДУБ зеЛенЫЙ; зЛаТая ЦеПЬ на ДУБе ТоМ: и ДнеМ и ноЧЬЮ КоТ УЧенЫЙ вСе ХоДиТ По ЦеПи КРУГоМ; иДеТ наПРаво - ПеСнЬ завоДиТ, наЛево - СКазКУ ГовоРиТ. ТаМ ЧУДеСа: ТаМ ЛешиЙ БРоДиТ, РУСаЛКа на веТвяХ СиДиТ; ТаМ на невеДоМЫХ ДоРоЖКаХ СЛеДЫ невиДаннЫХ звеРеЙ; изБУшКа ТаМ на КУРЬиХ ноЖКаХ СТоиТ Без оКон, Без ДвеРеЙ; ТаМ ЛеС и ДоЛ виДениЙ ПоЛнЫ; ТаМ о заРе ПРиХЛЫнУТ воЛнЫ на БРеГ ПеСЧанЫЙ и ПУСТоЙ, и ТРиДЦаТЬ виТязеЙ ПРеКРаСнЫХ ЧРеДоЙ из воД вЫХоДяТ яСнЫХ, и С ниМи ДяДЬКа иХ МоРСКоЙ; ТаМ КоРоЛевиЧ МиМоХоДоМ ПЛеняеТ ГРозноГо ЦаРя; ТаМ в оБЛаКаХ ПеРеД наРоДоМ ЧеРез ЛеСа, ЧеРез МоРя КоЛДУн неСеТ БоГаТЫРя; в ТеМниЦе ТаМ ЦаРевна ТУЖиТ, а БУРЫЙ воЛК еЙ веРно СЛУЖиТ; ТаМ СТУПа С БаБоЮ яГоЙ иДеТ, БРеДеТ СаМа СоБоЙ, ТаМ ЦаРЬ КащеЙ наД зЛаТоМ ЧаХнеТ; ТаМ РУССКиЙ ДУХ... ТаМ РУСЬЮ ПаХнеТ! и ТаМ я БЫЛ, и МеД я ПиЛ; У МоРя виДеЛ ДУБ зеЛенЫЙ; ПоД ниМ СиДеЛ, и КоТ УЧенЫЙ Свои Мне СКазКи ГовоРиЛ. оДнУ я ПоМнЮ. СКазКУ ЭТУ ПовеДаЮ ТеПеРЬ я СвеТУ. ДеЛа Давно МинУвшиХ ДнеЙ. ПРиДанЬя СТаРинЫ ГЛУБоКоЙ. в ТоЛПе МоГУЧиХ СЫновеЙ, С ДРУзЬеяМи в ГРиДниЦе вЫСоКоЙ вЛаДиМиР СоЛнЦе ПиРоваЛ. МенЬшУЮ ДоЧЬ он вЫДаваЛ за Князя ХРаБРоГо РУСЛана, и МеД из ТяЖКоГо СТаКана за иХ зДоРовЬе вЫПиваЛ. не СКоРо еЛи ПРеДКи наши. не СКоРо ДвиГаЛиСЬ КРУГоМ Ковши, СеРеБРянЫе Чаши С КиПящиМ ПивоМ и виноМ. они веСеЛЬе в СеРДЦе ЛиЛи. шиПеЛа Пена По КРаяМ. иХ ваЖно ЧашниКи ноСиЛи и низКо КЛаняЛиСЬ ГоСТяМ.

Таким образом, первоначальная гипотеза оказалась верна лишь на 30 % (11 букв оказались на своих местах), однако, текст удалось восстановить «вручную» по критерию «читаемости».