Лемма 2.1

Пример 2.4

Подсчет числа совпадений

Рассмотрим шифртекст , полученный при шифровании шифром Виженера с ключом открытого текста на английском языке.

Основой взлома шифра Виженера является определение длины ключа .

При проведении анализа будем предполагать, что источник открытых текстов генерирует отдельные буквы, причем вероятность появления каждой буквы задана в табл. 1.1 и не зависит от предшествующего текста или буквы (см. пример 1.1). Кроме того, предположим, что буквы из ключа представляют собой независимые случайные величины, равномерно распределенные на множестве (т.е. вероятность того, что окажется некоторой наперед заданной буквой, равна 1/26).

Обозначим через и подстроки строки , состоящие из крайних левых символов и, соответственно, из крайних правых символов , т.е.

и .

Затем подсчитаем количество совпадений символов строк и , т.е. таких координат , что . В лемме 2.1 будет показано, что математическое ожидание доли этих совпадений (т.е. их количества, деленного на , — длину строки) равно , если делит , и равно , если не делит .

Приведем пример того, как можно использовать эту разницу в математических ожиданиях для определения длины неизвестного ключа.

Рассмотрим криптограмму

С помощью функций StringTake, StringLength, Characters и Table пакета "Mathematica" легко вычислить количество совпадений символов строк и для каждого значения :

ciphertext =

"ubsyvkmhvyrrtsbbcrdsndwrtshxmbufrmxgabnvmirceweruca

mlyzbrvfwivvmlyzwapsryogsslechbgcubsvyczqrcwrmhvcxgo

oyvcydspomtqfpyqkgbcmerucadlcaflrsuqjrbhceqesfcehuoq

mdstorcdoymeqqwaglgovggsmdabbigztbbqyfwbxwmgfpowgzty

eilosrkgfahuovqfogswruqnvpwfvrnmpqqgsslatgrmqubsvycz

qrswcjdeowqqroihqdspdibffnxwgztbbqyfwbxus";

L = StringLength[ciphertext];

Table[N[Count[Characters[StringTake[ciphertext, i]]

- Characters[StringTake[ciphertext, -i]], 0]/i,1],

{i, L - 20, L – 1}]

{0.03,0.04,0.08,0.02,0.05,0.04,0.04,0.03,0.06,0.07,0.06,0.04,0.02,0.05,0.08,0.04,0.05,0.02,0.01,0.05}

Наибольшие величины оказались в позициях этого списка с номерами и , а это показывает, что длина ключа равна . И на самом деле, при шифровании был использован шестибуквенный ключ .

Это можно проверить с помощью следующего аналога шифрования Виженера из примера 2.3:

SubTwoLetters[a_, b_]:=

FromCharacterCode[

Mod[(ToCharacterCode[a]-97)-(ToCharacterCode[b]-97),26]+97]

ciphertext =

"ubsyvkmhvyrrtsbbcrdsndwrtshxmbufrmxgabnvmircewerucamly

zbrvfwivvmlyzwapsryogsslechbgcubsvyczqrcwrmhvcxgooyv

cydspomtqfpyqkgbcmerucadlcaflrsuqjrbhceqesfcehuoqmds

torcdoymeqqwaglgovggsmdabbigztbbqyfwbxwmgfpowgztyeil

osrkgfahuovqfogswruqnvpwfvrnmpqqgsslatgrmqubsvyczqrs

wcjdeowqqroihqdspdibffnxwgztbbqyfwbxus";

key = "monkey";

plaintext = "";

Do [plaintext = plaintext <>

SubTwoLetters[StringTake[ciphertext, { i}],

StringTake[key,

{ Mod[i - 1, StringLength[key]] + 1} ]],

{ i, 1, StringLength[ciphertext]} ];

plaintext

informationtheorytreatstheunidirectionalikformationchannelbywhichaninfotmationsourceinfluencesstatisticallyareceivercommunpcationtheoryhoweverdescribesthemoregeneralcaseinwhichtwoormoreinformationsourcesinfluenceeachotherstatisticallythedirectionofthisinfluenceisexpressedbydsrectedtransinformationqu

Пусть шифртекст получен при шифровании открытого текста шифром Виженера с ключом длины . Пусть текст порожден источником открытых текстов из примера 1.1. Иначе говоря, буквы в представляют собой независимые случайные величины, распределение вероятностей которых определяется в соответствии с табл. 1.1. Кроме того, пусть буквы из ключа — это независимые случайные величины, равномерно распределенные на множестве (т.е. вероятность того, что окажется некоторой наперед заданной буквой, равна 1/26). Тогда для каждой пары ,

(2.1)

Доказательство. Если делится на , то тогда и только тогда, когда . Это непосредственно следует из формулы (2.1), поскольку . Таким образом,

Если не делится на , то по формуле (2.1) тогда и только тогда, когда . Из неравенства следует, что совпадает с с вероятностью 1/26. Отсюда

.

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