Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)
.pdf171
Пусть П(<1)=( П (<!,=),П(<1,(Ф)) - разбиение множества пар {1,2,...,М}х{1,2,...,Ы}, индуцированное разбиением К.(с1). Введем обозначе
ние: П(а=)=|{Оо'}бП(а,=),
Положим, Р (П (ф ))= ^ ^ ^ —^ - вероятность случайного и равнове
роятного выбора пары индексов (У'}из множества П(<1,=).
Ранее отмечалось, что величина ИБШ(В(ЪГ)) последовательности ЬьЬг,...,Ьк совпадает с вероятностью Рв(Ц=^-,ё) совпадения шифрованных букв на случайно и равновероятно выбранных двух различных местах, рас стояние между которыми кратно <1. Поэтому
Е(ИБШ(В(Н)) = Ру(ЪГ Ъ,,с1)= ^ Р(А)Р(О)Рв 0 у =Ъ г ,с!) =
Ае1м,Ое11
=х Р(А)Р(0)^в(ь] =ьг /а |р а г » Р (< ||р а л Ь
Ае1м,Се11
- Е Р(А)Р(0)[рв(а;+Т) |
= аг + Т г /ё|рЦГ))Р((1|рО,з'))]= |
||
АеУ,Ое11 |
|
|
|
= Р(Л|РОо')) |
Е |
Р(А)Р(С)[Рв (а) = а г /<1|раТ)]= |
|
|
Ае1ы,0б11 |
|
|
- р(Ф Щ ')) |
Е Е р(А )р(0 )1р в ( а , = а г /<1 |р ( Ш ] - |
||
|
А «1" ОвЦ |
|
|
-В Д р О Л ) |
Е р(А)[р в ( а ,= а г / а | р ( ш ] 2 ; Р (С ). |
||
|
А еУ |
|
Оец |
= Р(Ф 0,Л ) X Р{А)[рв {а} = аг 1а I р 0 \ л ] =
Ае 1ы
=р(ФСЛ) X р(А)[рв(а] =«/)]=
Ае1"
- в д р о л у Е ^ - 1-" -^ - 2 |
N ( N - 1 ) |
у р * . |
У ' N ( N - 1 ) % ' |
У ' |
|
Теорема доказана. |
|
|
172
Обозначим через К.'=(М' ьМ'г,...,N'0 - произвольное разбиение мно
жества {1,2,...,М}, а через П(К.')=(П (К.',=),П(К.',*)), разбиение множества пар (1.2......N1x11.2......N1. индуцированное разбиением К.’ (данное понятие определено выше). Разбиению П(Р') поставим в соответствие подмножество
1ДП(К.')) множества ключей К=1к. Последовательность |
у \, у 2,. • •, УN из Iм |
принадлежит 1ДП(В')) тогда и только тогда, когда у г у |
для любой пары |
(У } е П (К.',=). Рассмотрим пересечение К.' п К(б) разбиения |
Р'=(К'ьЫ'2,...,Н'к) и введенного при доказательстве теоремы 3 разбиения
К(б)=(Ы|,И2,...,N,0 множества {1 ,2,...,И}, где |
0 о+б,]'+2б,...}, )е {1 ,2,...,б}. |
Разбиение К.' п В(б)~(п1,П2,...,п,) состоит из непустых блоков вида N^ 0 ^ , |
где)' е {1Д ... ,к}У е {1 ,2,... ,6}. Этому разбиению соответствует разбиение
П(К' Г\ К(б))=(П((К.' О К(б),=)),П((К.' п К.(б), Ф)) множества пар
{1,2,...,Ы}х{1,2,...,М}\{(У)у€ 1,И }. Напомним, что разбиению К.(б) соответ ствует П(б)=(П(б,=),П(б,( Ф)) - разбиение множества пар
{1 ,2,...,М}х{1,2,...,М}\{(У)у€ 1, N }, индуцированное разбиением К.(б).
Положим Р(п (а . . ) ) . № У |
- у |
- |
1 ^ 1 (| ^ 1 - -0 , - |
N ( N - 1 ) |
“ |
N ( N - 1) |
вероятность случайного и равновероятного выбора пары индексов {У'}из
множества П(б,=), а Р (С /,/) е П(К'пК(с1) = ^ |
• |
с |
N ( N - 1 ) |
Пусть шифртекст В=В(Л) получается шифрованием случайного текста А=А(М) (выборки из распределения Р0) с помощью равновероятного выбора ключа <3=0(М) из ЩЩР')). Подсчитаем вероятность Ру(Ъ|=Ь|,б) совместного события: при случайном и равновероятном выборе различных позиций) и)' с
расстоянием, кратным б, элементы Ц и |
случайного шифртекста В совпадут. |
|
Имеем |
|
|
Е(ИБШ(В(Ы)) = РУ(Ъ;=М) = X |
Р(А )Р (0)Р в (Ь] = Ь г ,ё ), |
|
Ае1м,Ое1Г |
|
|
где Рв(Ь,,Ъ|,б) - вероятность совпадения шифрованных букв |
в шифртек |
сте В=ЬьЬ2,...,Ьы, на случайно и равновероятно выбранных двух различных
местах У ', расстояние между которыми кратно б. Шифртекст В получен из открытого текста А с помощью гаммы О.
Последние равенства можно продолжить:
2 Р(А)Р(С)рв (Ъ; = ъ г ,а)=
Аб1м,с еи
г
173
- |
2 |
Р(А)Р(0)Р в(Ъ; = Ьу, а, а Л е П (Г ,=)) + |
Ае1ы,ОеО
+2 р(А)Р(0)Рв(ь, = ьг ,а, а ,г ) е п (к -,* » -
Аб1ы,Оеи
X р(А)р<а)рв(Ь; =ьг /а|рС|,|),аГ)бП(К',=)жа|ра1).а1)еП(к-,=))+
Ае1ы,Ски
+^ т т р,щ =ь,м\ш )и,т т ,*Ж А& ,пил)ьт ,*))
леЛса/
Напомним, что Ь^=а^ур Ъу=ау+уу и при выполнении условия (Ц')е П(К.',=) все ключи - гаммы из 11(П(К')) таковы, что уу=уу. Следователь но, первую сумму предыдущего выражения можно преобразовать так:
^Р(А)Р(0)Рв(^ =ат /ё|раХШ )еЩ Я\=)]Р(д|раХШ )еЩ Я\=))=
Ае1м,Сёи
‘ К Л \ М , Л Ш ' ) е Л ( К , = ) ) ' Е |
= ^ ( А / . Л .О .Л е Д Я > ))= |
Ае1" |
|
=ру | /чл/ш.л6 ж*»)Е р*,
/е/ Для случайно и равновероятно выбранной гамме из ЩЩР')) вероятность со бытия
(у,=1, уу=Г) равна Р(у)=1)Р(уу=Г) для любых 1,Г, причем Р(УйО= у у | Для
любого 1 е I (см. лемму 4). Поэтому вторую сумму рассматриваемого выра
жения можно привести к виду
ВДр(Ш Ш >Ц К >)) X Р(А)В(0(Рв(а,+у;=а,.+г,./а|рйОШ')€ПД',=‘)).
Ае^ОеП
Кроме того,
т ш )и л еЩ д )Т ,^ р ,(а 1+г1=агп г1л\ыл)ил*т,*)>
,сш
~Р(<11р О . Г Ш Л € Л (Л \* ))А
174
Получаем промежуточный результат: |
|
|
Е<ИБШ(В(М)) = Ру(ЪГ М )= |
Р(с11р и , Г ) , и , Л е Щ К ' = ) ) ^ |
Р> + |
|
/е / |
|
|
|
1 |
|
+ Р{4 I Р и , Г Ш Л е Я(Д',*))— . |
|
|
! |
' * |
Продолжим выкладки: |
|
|
н а I м . п и , л е щ я \= ) ) = р ( и ,г е |
|
|
_ ^ |
I п с I (I I “ 1 ) |
|
с = 1 |
Я ( Я - 1) |
|
Для подсчета вероятности Р(й? | р 0 , / ) , 0 \ Л е П ( К ' Л ) переобозначим разбиение К' г»К.(<1)= (пьП2,...,п(), состоящее из непустых блоков ви да п % где | 'е {1,2,... ,к}, зе {1,2, . Именно, пусть ( п ( п 2], . . и/а )) -
семейство непустых блоков пт> из системы (П|,п2,...,п()входящие в блок N3,
)<= {1,2,...,б}. Тогда .
Р{41рО\Л,и,Л е я(Д > ))= Р(О о')еп(вд=), 0 0 ')€П(К',^))=
4 \
Окончательно получаем |
|
г |
\ |
|
|
|
|
||
Е(ИБШ(В(Ы)) = РУ(ЬГ Ъ>А)= Р(й | р ( Ш |
,( Ш € П (К \= )) |
2 |
|
|
I ? ! |
у |
|||
|
|
|
^161 |
|
|
+ Р ( < ) |р ( Ш , ( Ш е П ( Я > ) / ‘ |
|
||
|
|
|
ч Л / |
|
_ у |
I П с I (I П с I ~~0 ( у р2 |
V |
|
|
% |
N ( N - 1 ) |
' |
|
|
+- 1 |
1 |
чл |
|
|
|
|
|
||
/ | |
щ м - |
с- 1 |
|
|
175
Таким образом доказана
Теорема 4. Пусть шифртекст В=В(Л) получается шифрованием слу
чайного текста А=А(И) (выборки из распределения Р0) с помощью равнове роятного выбора ключа 0=0(М) из 11(П(К.')). Тогда вероятность РУ(^=Ь],(1) того, что при случайном и равновероятном выборе различных позиций] и]' у них расстояние будет кратно с! и элементы Ъ, и Ъу случайного шифртекста В совпадут, равна величине
1 |
N ( N - 1 ) |
|
|
1 |
1 |
а |
((Л |
+т т ; . , , . , |
, ' Е ( |
" /( " / - ! ) )• |
|
| / | Щ М - 1) # |
с = 1 |
При указанной вероятностной модели получения шифртекста данная вероят ность совпадает с математическим ожиданием Е(ИБШ(В,б)) случайной вели чины ИБШ(В,с1).
Из полученного выражения для вероятности Ру(^=Ъ^,с1) следует, чхо она зависит не только от мощностей блоков разбиения К' (как это имело ме сто для вероятности РУ(Ъ|=Ъ^), но и от мощностей блоков пересечения разбие ний К' и К.(<1). Поэтому такая большая многозначность определения периода в шифре гаммирования по шифртексту, как в первом методе Вольфа Фридмана,
впредлагаемом методе БШ отсутствует.
Вслучае К.'=К.(с1) имеем к=с1=1, Ы'!==Ы|=^, 1}=1. Формула для Ру(Ц=Ь},с1) принимает вид
где Н=кс1+г. Ранее эта формула была получена в теореме 3.
Возможности использования т-грамм шифрованного текста.
Основная идея одного из направлений повышения надежности пред ставленных методов определения периода гаммы в шифре гаммирования со стоит в представлении последовательностей алфавита I в виде последователь ностей т-грамм алфавита I.
176
Через Р0(ш) обозначим вероятностное распределение на 1ш, опреде ленное вероятностями РОьЬ,...Дш) появления т-грамм 11,12,. • •Дт =М в со держательных открытых текстах; через А(Ы,ш)=М|,М2 Ммбудем обозначать реализацию случайной выборки объема N из распределения Р0(т). Последо вательность т-грамм М|,М2 Мыпри необходимости мы будем рассматри вать и как последовательность А(№п)=М1М2.. Мы=а1,а2,...,аыт символов алфа вита I длины №п (Ц Ц +1 - конкатенация слов М] и М^+1). Пусть
В(Ы)=В(А(Ы),0(К))=ЬьЬ2>...ЬЫт,
где Ъ}=щ+ у ^(то<111|), ] е {1 ,2,... ,№п}.
Последовательность В(Ы) будем трактовать как шифрованный текст, полученный зашифрованием текста А(1Ч) на ключе-гамме С(Ы) в шифре гам мирования (Х=1Ыт,К= II,У= 1Мт, 1),
®[Э1,а2>...ал т; У \ , У 2, -■ Nт ):=3ЬI ,Ь2 Ьмт .
Представляя гамму 0(Ыт)= у \,у г,...,у цткак последовательность т - грамм Г1,Г2,...,Гм, а шифртекст Ь,,Ь2 Ьыт как последовательность т-грамм
В ЬВ 2, . . .,Вм, можно говорить теперь о том, что мы зашифровали выборку М„М2,.. Мына ключе Г|,Г2,...,Гы, получив шифрованный текст - последова тельность т-грамм ВьВ2,...,Вм. Задача определения периода последователь ности т-грамм Г=Г1,Г2,...,Гы может решаться теперь полностью аналогично
рассмотренной ранее задаче определения периода гаммы при т=1. При этом надо иметь в виду, что если период последовательности Г равен Б, то период <1 последовательности О(N01) является делителем числа пЮ.
Очевидно, модель получения содержательных текстов в виде выборки т-гамм является значительным уточнением начальной модели получения со держательных текстов. Но надо иметь в виду, что, имея текст длины N (вы борку объема N1) в алфавите I, при переходе к т-граммам нам приходится ра
ботать с длиной текста И /т (объем выборки уменьшается в т-раз) и, следова тельно, уменьшается степень приближения значения индекса совпадения (ин декса БШ) шифртекста к значениям теоретических расчетов (аналогично тому как уменьшается точность приближения относительной частоты встречаемо-
177
сти буквы в содержательном тексте к ее вероятности с уменьшением длины текста).
Определенным выходом из этой ситуации является рассмотрение всех ш-грамм 1^ +1,...,^+(т-1) последовательности 1Ь12, ..Ды длины N в алфавите I (таких ш-грамм всего N-(111-1). При этом нам ниже придется проводить расче
ты впредположении, что эти т-граммы получены независимо друг от друга, что не соответствует действительности (например, очевидно, что ш=граммы
..,1|+(т-|)и ^+|,...,^+(т-1),1|+т зависимы). Тем не менее, такая неразумность
объяснима тем, что при большом N и небольшом ш большинство пар ш-грамм состоит из независимых ш-грамм. И остается надежда, что такой слабой зави симостью можно пренебречь. Проверка же применимости получаемых при этом предположении теоретических результатов осуществляется в таких слу чаях экспериментальным путем.
Обозначим через /% множество всех локально периодических после довательностей периода <1.
Теорема 3'. Пусть шифртекст В=В(т,Ы) получается шифрованием случайного текста А=А(^)=аьа2,...,ам, т-граммы которого являлись выбор кой из распределения Р0(ш), с помощью равновероятного выбора ключа
0=С(Ы) из 1^ . Причем, <1>ш. Тогда вероятность
Ру(Ь^+|,...,Ьз+т=^ ^ +1,...,^ +т;<1) того, что при случайном и равновероятном выборе различных позиций) и)' с расстоянием кратным (1 т-граммы Ь^+1,...,1}+т; ЪрЪр+1,...,Ър+т случайного шифртекста В совпадут, равна вели
чине
При указанной вероятностной модели получения шифртекста данная вероятность совпадает с математическим ожиданием Е(ИБШ(В(ш,Ы)) слу чайной величины ИБШ(В(т,Ы).
ДОКАЗАТЕЛЬСТВО. Множеству /% =11 соответствует разбиение
ЩНМ,, N2,...,N<0множества {1 ,2,...,N 1 , где Ц)+сУ+2с1,...} ,)е {1,2,. .
Пусть П(ф=(П(с1,=),П(с1,( Ф)) - разбиение множества пар
{1,2,...,М}х{1,2,...,М}\ {(У),,)’б 1, N }, индуцированное разбиением К(ф.
178
Положим, Р(П(<1,=))=-^^— - вероятность случайного и равнове
роятного выбора пары индексов (У'} из множества П(<1,=).
Ранее отмечалось, что индекс БШ(В(гп,Н)) последовательности ЪьЪг,...,Ьм совпадает с вероятностью Рв(Ь^+ь...,Ъ^т=Ъ^чь...,Ь^ +т;<1) совпа
дения шифрованных букв на случайно и равновероятно выбранных двух раз личных местах, расстояние между которыми кратно <1. Поэтому
Е(ИБШ(В(т,К)) = Ру(Ь^+1,...,Ь]+<т.1)=Ь^-+1,...,Ьг+(т-1);Ф =
X р(А)р(^)рв(^ |
=Ьу,...,Ьу+(т_1),ё), |
Аб1ы ,Се11 |
|
где Рв(Ь^+1,... ,^+т = ЪуЪу+1,... ,Ъ; +т ><1) - вероятность совпадения шифрованных
т-грамм в шифртексте В=ЪьЪ2,...,Ьк на случайно и равновероятно выбран ных двух различных местах У ', расстояние между которыми кратно <1. Шиф
ртекст В получен из открытого текста А на ключе - гамме Ое\]=1% .
Последние равенства можно продолжить:
X Р(А)Р(0)Рв(Ьр...,ЬЖт_1) =Ьг,...,Ьг+(т_1),ё)=
Ае1м,Сеи
^р(А)Р(а)Рв(^,...,ьМт 1) =ь|,...,Ь;Ч<т_1),/а|рО,|))Р(>)|раО=
Ае1м,Об11
р(4|р(Ш |
X |
р(А)Р(С)РА(а^,...,а^т 1) |
с1| р(У'))= |
Ае1к ,Сеи |
|
||
т р и л |
Т . |
р м р л |
Се(/ |
|
АеГр |
|
Так как по условию <1 > т то при случайном выборе т-грамм
X р ( А ) р л ( ^ , . . . , а М т _п = а/,...,а/+(т_1),/^|/ЧЛЛ)=
Ае1\
X , Р(А)Р а (з 9”*>*у+(т —1) —а у,..., а |
1)) — |
р (а12>а2»**’»аш) |
Ае1ы, |
(а12,а2,...,ат ) е Г |
|
Следовательно,
179
Ру(Ъ^+1,... Д^+(т_1) Ь^Ь^+1,...9Ъ^+(т_1),(1)
_ № ■ = ) ! .. V Р 2,
~ К ф - 1 ) |
, |
^ |
|
<а,г'*2" |
|
||
4 |
’ |
(а12.а2,-,ат)б1 |
|
|
|
||
|
_ (к + 1 )кг + к(к - |
1)(с( - г ) |
^ |
п2 |
|||
|
|
|
м ы - п |
|
|
^ |
- (а|2’“2’-"а”)• |
|
|
|
^ |
|
|
(а12,а2,...,ат)е/ |
|
Доказательство теоремы 3' закончено.
Возможности переноса изложенных результатов на шифры поточ ной замены (ПЗ).
В данном пункте, как и ранее, под открытым текстом мы будем пони мать выборку из распределения Р0=(РьР2,...,Р|1|), где Р; - вероятность буквы) (ее номера) в содержательном тексте.
Пусть К - некоторое множество подстановок на I. Рассмотрим шифр ПЗ (Х=1м, Км, У, 1), где шифрованный текст В=(ЬьЬ2,...,Ьы)=ДА,ст) получается из открытого текста А=аьа2,...,аыс помощью ключа а=стьст2,...,амбКм сле
дующим образом: Ь]=а](а]),)е{1,...,Ы }.
Пусть <1 - период последовательности 0=01,02,.. .,стн (см. определение 2), в
случае ее локальной периодичности. Задача состоит в определении периода (1 последовательности а или же установления его отсутствия по известному шифрованному тексту В. Легко проверить, что значение индекса совпадения
(Ю) последовательности 3 = 11,12,...,1ц е Iм •
1)
1С(3>
^N ( N - 1 )
(?1 - частота встречаемости буквы 1 в последовательности 3 = 11,12,...,1ы)
совпадает с индексом совпадения последовательностй
сг(3 )=а(11),а(12),...,а(1н) при любой подстановке а на I. Предположим допол
нительно, что |К|=|1| и нижние строки множества К подстановок образуют ла тинский квадрат, т. е. множества переходов любых двух различных подстано вок не пересекаются (это условие обеспечивает несложное доказательство аналога леммы 4 для рассматриваемого здесь шифра). Тогда полученные ра нее результаты по применению индекса совпадения для определения периода гаммы шифра гаммирования полностью переносятся и на рассматриваемый шифр поточной замены. Несложно проверяется и совпадение индекса БШ по следовательности 3 =11,12,-..Ды с индексом БШ последовательности
180
ст(3 )=ст(11),а(12),...,ст(1ы), откуда следует справедливость полученных ранее
утверждений для индекса БШ и для шифра ПЗ. Трактуя уравнение а+у=Ь как уравнение Тт(а)=Ь, где Т - подстановка вида Т(|)=з+1 (то<1(|1|), заключаем, что шифр гаммирования является частным случаем шифра ПЗ с множеством клю чей Км, где К=(Т, Т2,...,Т|11), Т1'1 - тождественная подстановка на I.
Задача дешифрования шифра поточной замены при известном пе риоде ключевой последовательности.
Рассмотрим шифр ПЗ (Х=1М,КЬ1,У,1), где шифрованный текст В=(Ъ|,Ъ2,...,Ъы)=Г(А,ст) получается из открытого текста А=а1,а2,...,ак с помо щью ключа - последовательности ст=аьСТ2,...,сты периода <1. Мы будем пред
полагать, что нижние строки множества К подстановок образуют латинский квадрат |К|=|1|. Задача состоит в определении открытого текста А по извест ному шифрованному тексту В и известному периоду с! ключа о.
Метод протяжки вероятного слова. Пусть Ъ1,Ь2,...,Ъм - известный
шифртекст, ИНссН-г. Рассмотрим две его подпоследовательности.
Ь(, Ьг... ,Ь|,... |
,Ь{к-1)(]+г,- |
^1+л, Ьз+а,*• ■*Ь|+с),... |
, Ь^+г |
Выберем так называемое «множество вероятных слов» - слова, кото рые по нашему мнению, могут быть началом искомого открытого текста. Для опробуемого такого слова а'ьа'2,.:.,а',, предполагая, что оно является нача лом искомого открытого текста, находим первые а|,СТ2,...,ог, подстановок
ключа (пользуясь тем, что множество К известно и тем, что нижние строки этого множества образуют латинский квадрат. Действительно, уравнение ст(а)=Ь при известных а и Ь однозначно разрешимо относительно ст из К. Пра вильность угадывания вероятного слова а'ьа'2,...,а\ проверяется теперь на
«читаемости» расшифрованного текста сгГЧЬц-а), СТ2'1(Ъ2+(1),..., стг'сь.+а).
Если последовательность этих букв принимается как случайный (не читаемый) текст, то опробуется следующее вероятное слово. В случае же «чи таемости» этой последовательности полагают, что
СчСЬнсО, 0*2(62+01)5••-5 ^(Ъ +кО ^ &1+(1, 3 .2 +сЬ• • •5 а 1+с! 5 —
и стараются построить возможные продолжения |
этого отрезка |
открытого текста по смыслу первых его Xбукв а ^ |
а2+С1,..., а^. Затем опробо |
вать каждое такое продолжение а^+ь.-.^+а+с, т. е. найти с помощью Ъж1+1,...,Ъ1+с1+си этого продолжения последовательность подстановок
~ аж, -• - ,с*1+с, а затем для нее и расшифрованный отрезок текста