Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
78
Основные понятия
где ф — функция Эгтера. Предстаешь ключ к є К в еиде к = (к3,кр), где к3=(п,Ь) и kp=(n,p,q,a)— ключи зашифрования и расшифрования соответственно. Правила зашифрования и расшифрования шифра RSA определим для х є X и у є Y формулами:
Екз(х) = хь modп, Dk^(y) = уа то&п. (2)
Аббревиатура RSA определяется начальными буквами фамилий создателей этого шифра — Rivest, Shamir, Adleman. Корректность формул (2) следует из малой теоремы Ферма (подробнее это сделано в § 11.1).
Введенные определения и термины не исчерпывают полный перечень необходимых нам понятий, которые будут вводиться далее по необходимости.
§ 2.5. Модели открытых текстов
Введенная нами математическая модель шифра Eb (см. § 2.4) содержит вероятностные распределения P(X) и P(K) на множествах открытых текстов и ключей соответственно. Если P(K) определяется свойствами устройств, служащих для генерации ключей (которые могут быть случайными или псевдослучайными), то P(X) определяется частотными характеристиками самих текстов, подлежащих шифрованию. Характер таких текстов может быть различный: это могут быть обычные литературные тексты, формализованные данные межмашинного обмена и т. д. Так или иначе, открытые тексты обладают многими закономерностями, некоторые из которых наследуются шифрованными текстами. Именно это является определяющим фактором, влияющим на надежность шифрования.
79
Г лава 2
Математические модели открытого текста
Потребность в математических моделях открытого текста продиктована, прежде всего, следующими соображениями. Во-первых, даже при отсутствии ограничений на временные и материальные затраты по выявлению закономерностей, имеющих место в открытых текстах, нельзя гарантировать того, что такие свойства указаны с достаточной полнотой. Например, хорошо известно, что частотные свойства текстов в значительной степени зависят от их характера. Поэтому при математических исследованиях свойств шифров прибегают к упрощающему моделированию, в частности, реальный открытый текст заменяется его моделью, отражающей наиболее важные его свойства. Во-вторых, при автоматизации методов криптоанализа, связанных с перебором ключей, требуется “научить” ЭВМ отличать открытый текст от случайной последовательности знаков. Ясно, что соответствующий критерий может выявить лишь адекватность последовательности знаков некоторой модели открытого текста.
Один из естественных подходов к моделированию открытых текстов связан с учетом их частотных характеристик, приближения для которых можно вычислить с нужной точностью, исследуя тексты достаточной длины (см. Приложение 1). Основанием для такого подхода является устойчивость частот А:-грамм или целых словоформ реальных языков человеческого общения (то есть отдельных букв, слогов, слов и некоторых словосочетаний). Основанием для построения модели может служить также и теоретико-информационный подход, развитый в работах К. Шеннона [ШенбЗ]^
Учет частот к -грамм приводит к следующей модели открытого текста. Пусть P^(A) представляет собой массив, состоящий из приближений для вероятностей p(bxb2..bk) появления А;-грамм ЪхЬ2...Ьк в открытом тексте, ^eN, А = {a]9...9an} — алфавит открытого текста, Ь{ є A9 і = I9 к. 80
Основные понятия
Тогда источник “открытого текста” генерирует последовательность с|5с2,...,с*,сЛ+1,... знаков алфавита А, в которой
А;-грамма C1C2.. .Ck появляется с вероятностью
р(схс2...ск) є Р(к)(А) , следующая А-грамма C2C3...с*+1 появляется с вероятностью р(с2съ...ск+х) G Р(к)(А) и т. д. Назовем построенную модель открытого текста вероятностной моделью к-го приближения.
Таким образом, простейшая модель открытого текста -вероятностная модель первого приближения - представляет собой последовательность знаков C1,C2,..., в которой каждый знак CiJ = 1,2,..., появляется с вероятностью p(ct)G Piu(A)9 независимо от других знаков. Будем называть также эту модель позначной моделью открытого текста. В такой модели открытый текст с1с2...с/ имеет вероятность
p(cxc2...ct) = \\р(с,).
/=1
В вероятностной модели второго приближения первый знак C1 имеет вероятность p(cx)gP{X)(A), а каждый следующий знак C1 зависит от предыдущего и появляется с вероятностью
P(C1-IC1)
р(с,/с,_ ,) = -
р(с,-1)
где P(C1^C1)еР{2)(A), р(с^)єРт(А), і = 2,3,.... Други-
ми словами, модель открытого текста второго приближения представляет собой простую однородную цепь Маркова. В такой модели открытый текст C1C2...^ имеет вероятность
81
І лава 2
і
p(c{c2...ct) = p(c{) • Yl p(c, /c,_, ).
1=2
Модели открытого текста более высоких приближений учитывают зависимость каждого знака от большего числа предыдущих знаков. Ясно, что, чем выше степень приближения, тем более “читаемыми” являются соответствующие модели. Проводились эксперименты по моделированию открытых текстов с помощью ЭВМ.
Приведем примеры “открытых текстов”, выработанных компьютером на основе частотных характеристик (алфавита со знаком пробела) собрания сочинений Р. Желязны объемом 10652970 байтов:
