Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
39
Лекция 3. Традиционные симметричные криптосистемы.
3.1. Принципы криптографической защиты информации.
Криптография представляет собой совокупность методов
преобразования данных, направленных на то, чтобы сделать эти
данные бесполезными для противника. Такие преобразования по-
зволяют решить две главные проблемы защиты данных: проблему
конфиденциальности (путем лишения противника возможности
извлечь информацию из канала связи) и проблему целостности
(путем лишения противника возможности изменить сообщение так,
чтобы изменился его смысл, или ввести ложную информацию в
канал связи).
Проблемы конфиденциальности и целостности информации
тесно связаны между собой, поэтому методы решения одной из них
часто применимы для решения другой.
Обобщенная схема криптографической системы, обеспечи-
вающей шифрование передаваемой информации, показана на
рис.3.1. Отправитель генерирует открытый текст исходного
сообщения М, которое должно быть передано законному получа-
телю по незащищенному каналу. За каналом следит перехватчик
с целью перехватить и раскрыть передаваемое сообщение. Для
того чтобы перехватчик не смог узнать содержание сообщения М,
отправитель шифрует его с помощью обратимого преобразования
ек и получает шифртекст (или криптограмму) С=ЕК(М), который
отправляет получателю.
Законный получатель, приняв шифртекст С, расшифровывает
его с помощью обратного преобразования D=ЕK-1 и получает ис-
ходное сообщение в виде открытого текста М:
DK(С)=ЕK-1 (ЕK (М)) = М.
Рис.3.1. Обобщенная схема криптосистемы
Преобразование ЕK выбирается из семейства криптографиче-
ских преобразований, называемых криптоалгоритмами. Параметр,
с помощью которого выбирается отдельное используемое преоб-
разование, называется криптографическим ключом К. Криптоси-
стема имеет разные варианты реализации: набор инструкций, ап-
паратные средства, комплекс программ компьютера, которые по-
зволяют зашифровать открытый текст и расшифровать шифртекст
различными способами, один из которых выбирается с помощью
конкретного ключа К.
Говоря более формально, криптографическая система-это
однопараметрическое семейство (ЕK)K K обратимых преобразований
ЕK :М С
из пространства M сообщений открытого текста в пространство С
шифрованных текстов. Параметр К (ключ) выбирается из конечного
множества К, называемого пространством ключей.
Вообще говоря, преобразование шифрования может быть
симметричным или асимметричным относительно преобразования
расшифрования. Это важное свойство функции преобразования
определяет два класса криптосистем:
• симметричные (одноключевые) криптосистемы;
• асимметричные (двухключевые) криптосистемы (с открытым
ключом).
Схема симметричной криптосистемы с одним секретным клю-
чом была показана на рис.3.1. В ней используются одинаковые сек-
ретные ключи в блоке шифрования и блоке расшифрования.
Обобщенная схема асимметричной криптосистемы с двумя
разными ключами К1 и К2
показана на рис. 3.2. В этой криптосистеме
- один из ключей является открытым, а другой - секретным.
Рис. 3.2. Обобщенная схема асимметричной криптосистемы с открытым ключом
В симметричной криптосистеме секретный ключ надо переда-
вать отправителю и получателю по защищенному каналу распро-
странения ключей, например такому, как курьерская служба. На
рис. 3.1 этот канал показан "экранированной" линией. Существуют и
другие способы распределения секретных ключей, они будут рас-
смотрены позднее. В асимметричной криптосистеме передают по
незащищенному каналу только открытый ключ, а секретный ключ
сохраняют на месте его генерации.
На рис.3.3 показан поток информации в криптосистеме в слу-
чае активных действий перехватчика. Активный перехватчик не
только считывает все шифртексты, передаваемые по каналу, но
может также пытаться изменять их по своему усмотрению.
Любая попытка со стороны перехватчика расшифровать шифр-
текст С для получения открытого текста М или зашифровать свой
собственный текст М' для получения правдоподобного шифртекста
С', не имея подлинного ключа, называется криптоаналитической
атакой.
Если предпринятые криптоаналитические атаки не достигают
поставленной цели и криптоаналитик не может, не имея подлинно-
го ключа, вывести М из С или С' из М', то полагают, что такая крип-
тосистема является криптостойкой.
Рис.3.3. Поток информации в криптосистеме при активном перехвате сообщений
Криптоанализ - это наука о раскрытии исходного текста за-
шифрованного сообщения без доступа к ключу. Успешный анализ
может раскрыть исходный текст или ключ. Он позволяет также об-
наружить слабые места в криптосистеме, что, в конечном счете,
ведет к тем же результатам.
Фундаментальное правило криптоанализа, впервые сформу-
лированное голландцем А. Керкхоффом еще в XIX веке заключается в том, что стойкость шифра (криптосистемы) должна опреде-
ляться только секретностью ключа. Иными словами, правило Керк-
хоффа состоит в том, что весь алгоритм шифрования, кроме
значения секретного ключа, известен криптоаналитику противника.
Это обусловлено тем, что криптосистема, реализующая семейство
криптографических преобразований, обычно рассматривается как
открытая система. Такой подход отражает очень важный принцип
технологии защиты информации: защищенность системы не долж-
на зависеть от секретности чего-либо такого, что невозможно бы-
стро изменить в случае утечки секретной информации. Обычно
криптосистема представляет собой совокупность аппаратных и
программных средств, которую можно изменить только при значи-
тельных затратах времени и средств, тогда как ключ является лег-
ко изменяемым объектом. Именно поэтому стойкость криптосисте-
мы определяется только секретностью ключа.
Другое почти общепринятое допущение в криптоанализе со-
стоит в том, что криптоаналитик имеет в своем распоряжении
шифртексты сообщений.
Существует четыре основных типа криптоаналитических атак.
Конечно, все они формулируются в предположении, что криптоана-
литику известны применяемый алгоритм шифрования и шифртек-
сты сообщений. Перечислим эти криптоаналитические атаки.
1. Криптоаналитическая атака при наличии только извест-
ного шифртекста. Криптоаналитик имеет только шифртексты C1 ,
C2,...,Ci нескольких сообщений, причем все они зашифрованы с
использованием одного и того же алгоритма шифрования ЕK Рабо-
та криптоаналитика заключается в том, чтобы раскрыть исходные
тексты M1, M2, ..., Mi по возможности большинства сообщений или,
еще лучше, вычислить ключ К, использованный для шифрования
этих сообщений, с тем, чтобы расшифровать и другие сообщения,
зашифрованные этим ключом.
2. Криптоаналитическая атака при наличии известного от-
крытого текста. Криптоаналитик имеет доступ не только к шиф-
ртекстам C1, С2, ..., Ci нескольких сообщений, но также к откры-
тым текстам M1, М2,.... Mi этих сообщений. Его работа заключается
в нахождении ключа К, используемого при шифровании этих сооб-
щений, или алгоритма расшифрования DK любых новых сообще-
ний, зашифрованных тем же самым ключом.
3. Криптоаналитическая атака при возможности выбора
открытого текста. Криптоаналитик не только имеет доступ к шифр-
текстам C1, С2,...,Сi и связанным с ними открытым текстам M1,
M2,..., Mi нескольких сообщений, но и может по желанию выбирать
открытые тексты,, которые затем получает в зашифрованном виде.
Такой криптоанализ получается более мощным по сравнению с
криптоанализом с известным открытым текстом, потому что крип-
тоаналитик может выбрать для шифрования такие блоки открытого
текста, которые дадут больше информации о ключе. Работа крип-
тоаналитика состоит в поиске ключа К, использованного для шиф-
рования сообщений, или алгоритма расшифрования DK новых со-
общений, зашифрованных тем же ключом.
4. Криптоаналитическая атака с адаптивным выбором от-
крытого текста. Это - особый вариант атаки с выбором открытого
текста. Криптоаналитик может не только выбирать открытый текст,
который затем шифруется, но и изменять свой выбор в зависимо-
сти от результатов предыдущего шифрования. При криптоанализе
с простым выбором открытого текста криптоаналитик обычно мо-
жет выбирать несколько крупных блоков открытого текста для их
шифрования; при криптоанализе с адаптивным выбором открытого
текста он имеет возможность выбрать сначала более мелкий проб-
ный блок открытого текста, затем выбрать следующий блок в зави-
симости от результатов первого выбора, и т.д. Эта атака предос-
тавляет криптоаналитику еще больше возможностей, чем преды-
дущие типы атак.
Кроме перечисленных основных типов криптоаналитических
атак, можно отметить, по крайней мере, еще два типа.
5. Криптоаналитическая атака с использованием выбран-
ного шифртекста. Криптоаналитик может выбирать для расшиф-
рования различные шифртексты C1,С2,...,Сi и имеет доступ к рас-
шифрованным открытым текстам M1,M2,....Mi. Например, криптоа-
налитик получил доступ к защищенному от несанкционированного
вскрытия блоку, который выполняет автоматическое расшифрова-
ние. Работа криптоаналитика заключается в нахождении ключа.
Этот тип криптоанализа представляет особый интерес для раскры-
тия алгоритмов с открытым ключом.
6. Криптоаналитическая атака методом полного перебора
всех возможных ключей. Эта атака предполагает использование
криптоаналитиком известного шифртекста и осуществляется по-
средством полного перебора всех возможных ключей с проверкой,
является ли осмысленным получающийся открытый текст. Такой
подход требует привлечения предельных вычислительных ресур-
сов и иногда называется силовой атакой.
Существуют и другие, менее распространенные, криптоанали-
тические атаки.
3.2. Основные понятия и определения
Большинство средств защиты информации базируется на ис-
пользовании криптографических шифров и процедур шифрования-
расшифрования. В соответствии со стандартом ГОСТ 28147-89 под
шифром понимают совокупность обратимых преобразований мно-
жества открытых данных на множество зашифрованных данных,
задаваемых ключом и алгоритмом криптографического преобразо-
вания.
Ключ - это конкретное секретное состояние некоторых пара-
метров алгоритма криптографического преобразования данных,
обеспечивающее выбор только одного варианта из всех возмож-
ных для данного алгоритма [1].
Основной характеристикой шифра является криптостой-
кость, которая определяет его стойкость к раскрытию методами
криптоанализа. Обычно эта характеристика определяется интерва-
лом времени, необходимым для раскрытия шифра.
К шифрам, используемым для криптографической защиты
информации, предъявляется ряд требований:
• достаточная криптостойкость (надежность закрытия данных);
• простота процедур шифрования и расшифрования;
• незначительная избыточность информации за счет шифрования;
• нечувствительность к небольшим ошибкам шифрования и др.
В той или иной мере этим требованиям отвечают:
• шифры перестановок;
• шифры замены;
• шифры гаммирования;
• шифры, основанные на аналитических преобразованиях шиф-
руемых данных.
Шифрование перестановкой заключается в том, что символы
шифруемого текста переставляются по определенному правилу в
пределах некоторого блока этого текста. При достаточной длине блока, в пределах которого осуществляется перестановка, и сложном неповторяющемся порядке перестановки можно достигнуть приемлемой для простых практических приложений стойкости шифра.
Шифрование заменой (подстановкой) заключается в том, что
символы шифруемого текста заменяются символами того же или
другого алфавита в соответствии с заранее обусловленной схемой
замены.
Шифрование гаммированием заключается в том, что символы
шифруемого текста складываются с символами некоторой случай-
ной последовательности, именуемой гаммой шифра. Стойкость
шифрования определяется в основном длиной (периодом) непо-
вторяющейся части гаммы шифра. Поскольку с помощью ЭВМ
можно генерировать практически бесконечную гамму шифра, то
данный способ является одним из основных для шифрования ин-
формации в автоматизированных системах.
Шифрование аналитическим преобразованием заключается в
том, что шифруемый текст преобразуется по некоторому аналити-
ческому правилу (формуле).
Например, можно использовать правило умножения вектора
на матрицу, причем умножаемая матрица является ключом шиф-
рования (поэтому ее размер и содержание должны храниться в
секрете), а символами умножаемого вектора последовательно
служат символы шифруемого текста. Другим примером может слу-
жить использование так называемых однонаправленных функций
для построения криптосистем с открытым ключом.
Процессы шифрования и расшифрования осуществляются в
рамках некоторой криптосистемы. Характерной особенностью сим-
метричной криптосистемы является применение одного и того же
секретного ключа как при шифровании, так и при расшифровании
сообщений.
Как открытый текст, так и шифртекст образуются из букв, вхо-
дящих в конечное множество символов, называемых алфавитом.
Примерами алфавитов являются конечное множество всех заглав-
ных букв, конечное множество всех заглавных и строчных букв и
цифр и т. п. В общем виде некоторый алфавит £ можно представить так:
= {a0,a1,a2, …,am-1}.
Объединяя по определенному правилу буквы из алфавита ,
можно создать новые алфавиты:
• алфавит 2 содержащий m2 биграмм a0a0, a0a1, ...., am-1am-1;
• алфавит 3, содержащий m3 триграмм a0a0a0, a0a0a1,...,am-1 am-1 am-1.
В общем случае, объединяя по п букв, получаем алфавит n,
содержащий mn n-грамм [2].
Например, английский алфавит
= {ABCDEFGH ... WXYZ}
объемом m =26 букв позволяет сгенерировать посредством опера-
ции конкатенации алфавит из 262 = 676 биграмм
AA,AB,...,XZ,ZZ,
алфавит из 263 = 17576 триграмм
ААА, ААВ, .... ZZX, ZZZ и т.д.
При выполнении криптографических преобразований полезно
заменить буквы алфавита целыми числами 0,1, 2,3,.... Это позво-
ляет упростить выполнение необходимых алгебраических манипу-
ляций. Например, можно установить взаимно однозначное соот-
ветствие между русским алфавитом
рус.={АБВГДЕ...ЮЯ}
и множеством целых
Z32={0,1,2,3,...,31};
между английским алфавитом
англ. = {ABCDEF ... YZ}
и множеством целых
Z;26={0,1,2,3,...,25}
(см. табл. 3.1 и 3.2).
В дальнейшем будет обычно использоваться алфавит
m={0,1,2,3,...,m-1},
содержащий m "букв" (в виде чисел).
Замена букв традиционного алфавита числами позволяет бо-
лее четко сформулировать основные концепции и приемы крипто-
графических преобразований. В то же время в большинстве иллю-
страций будет использоваться алфавит естественного языка.
Таблица 3.1
Соответствие между русским алфавитом и множеством целых
Z32 = {0, 1, 2, 3, .. , 31}
|
Буква |
Число |
Буква |
Число |
Буква |
Число |
Буква |
Число |
|
А |
0 |
И |
8 |
Р |
16 |
Ш |
24 |
|
Б |
1 |
и |
9 |
С |
17 |
Щ |
25 |
|
В |
2 |
к |
10 |
Т |
18 |
ь |
26 |
|
Г |
3 |
л |
11 |
У |
19 |
ы |
27 |
|
Д |
4 |
м |
12 |
Ф |
20 |
ъ |
28 |
|
Е |
5 |
н |
13 |
х |
21 |
э |
29 |
|
Ж |
6 |
0 |
14 |
ц |
22 |
ю |
30 |
|
3 |
7 |
п |
15 |
ч |
23 |
я |
31 |
Таблица 3.2
Соответствие между английским алфавитом и множеством целых
Z26 = {0, 1, 2,3, ., 25}
|
Буква |
Число |
Буква |
Число |
Буква |
Число |
|
А |
0 |
J |
9 |
S |
18 |
|
В |
1 |
К |
10 |
т |
19 |
|
С |
2 |
L |
11 |
u |
20 |
|
D |
3 |
M |
12 |
V |
21 |
|
Е |
4 |
N |
13 |
w |
22 |
|
F |
5 |
0 |
14 |
X |
23 |
|
G |
6 |
Р |
15 |
Y |
24 |
|
Н |
7 |
Q |
16 |
z |
25 |
|
I |
8 |
R |
17 |
Текст с n буквами из алфавита Zm можно рассматривать как
n-грамму
Х= (x0, x1, x2, ..., xn-1),
где xi Zm, 0 < i < n, для некоторого целого n =1, 2, 3, ... .
Через m,n будем обозначать множество n-грамм, образован-
ных из букв множества Zm.
Криптографическое преобразование Е представляет собой
совокупность преобразований
Е=Е(n) : 1 n
E(n) : m,n m,n (3.1)
Преобразование Е(n) определяет, как каждая n-грамма откры-
того текста x Zm,n заменяется n-граммой шифртекста y, т.е.
у =E(n) (x ), причем x, y Zm,n ;
при этом обязательным является требование взаимной однозначности преобразования E(n) на множестве m,n.
Криптографическая система может трактоваться как семейство криптографических преобразований
Е = { ЕK : К К }, (3.2)
помеченных параметром К, называемым ключом.
Множество значений ключа образует ключевое пространство К.
Далее рассматриваются традиционные (классические) методы
шифрования, отличающиеся симметричной функцией шифрова-
ния. К ним относятся шифры перестановки, шифры простой и
сложной замены, а также некоторые их модификации и комбина-
ции. Следует отметить, что комбинации шифров перестановок и
шифров замены образуют все многообразие применяемых на прак-
тике симметричных шифров
Приводимые сведения о шифрах каждой группы даются по
возможности в хронологическом порядке, что позволяет постепен-
но вводить читателя в сферу криптографии. Как известно, доволь-
но трудно понять концептуальную схему науки, ее модели и методы
исследования, если не иметь хотя бы общего представления об
истории развития этой науки.
3.3. Шифры перестановки
При шифровании перестановкой символы шифруемого текста
переставляются по определенному правилу в пределах блока этого
текста. Шифры перестановки являются самыми простыми и, веро-
ятно, самыми древними шифрами.
Шифрующие таблицы
С начала эпохи Возрождения (конец XIV столетия) начала
возрождаться и криптография. Наряду с традиционными примене-
ниями криптографии в политике, дипломатии и военном деле появ-
ляются и другие задачи - защита интеллектуальной собственности
от преследований инквизиции или заимствований злоумышленни-
ков В разработанных шифрах перестановки того времени приме-
няются шифрующие таблицы, которые в сущности задают правила
перестановки букв в сообщении.
В качестве ключа в шифрующих таблицах используются:
• размер таблицы;
• слово или фраза, задающие перестановку;
• особенности структуры таблицы.
Одним из самых примитивных табличных шифров перестанов-
ки является простая перестановка, для которой ключом служит
размер таблицы. Этот метод шифрования сходен с шифром скита-
ла. Например, сообщение
ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ
записывается в таблицу поочередно по столбцам. Результат заполнения таблицы из 5 строк и 7 столбцов показан на рис. 3.4.
|
Т |
Н |
П |
в |
Е |
г |
л |
|
Е |
А |
Р |
А |
д |
0 |
Н |
|
Р |
Т |
и |
Е |
ь |
в |
0 |
|
М |
0 |
Б |
Т |
м |
п |
Ч |
|
И |
Р |
ы |
С |
0 |
0 |
Ь |
Рис. 3.4. Заполнение таблицы из 5 строк и 7 столбцов
После заполнения таблицы текстом сообщения по столбцам
для формирования шифртекста считывают содержимое таблицы
по строкам. Если шифртекст записывать группами по пять букв,
получается такое шифрованное сообщение:
ТНПВЕ ГЛЕАР АДОНР ТИЕЬВ ОМОБТ МПЧИР ЫСООЬ
Естественно, отправитель и получатель сообщения должны
заранее условиться об общем ключе в виде размера таблицы
Следует заметить, что объединение букв шифртекста в 5-буквен-
ные группы не входит в ключ шифра и осуществляется для удобст-
ва записи не смыслового текста. При расшифровании действия вы-
полняют в обратном порядке.
Несколько большей стойкостью к раскрытию обладает метод
шифрования, называемый одиночной перестановкой по ключу.
Этот метод отличается от предыдущего тем, что столбцы таблицы
переставляются по ключевому слову, фразе или набору чисел дли-
ной в строку таблицы.
Применим в качестве ключа, например, слово
ПЕЛИКАН,
а текст сообщения возьмем из предыдущего примера На рис. 3.5
показаны две таблицы, заполненные текстом сообщения и ключе-
вым словом, при этом левая таблица соответствует заполнению до
перестановки, а правая таблица - заполнению после перестановки.
Рис. 3.5. Таблицы, заполненные ключевым словом и текстом сообщения
В верхней строке левой таблицы записан ключ, а номера под
буквами ключа определены в соответствии с естественным поряд-
ком соответствующих букв ключа в алфавите. Если бы в ключе
встретились одинаковые буквы, они бы были понумерованы слева
направо. В правой таблице столбцы переставлены в соответствии
с упорядоченными номерами букв ключа.
При считывании содержимого правой таблицы по строкам и
записи шифртекста группами по пять букв получим шифрованное
сообщение:
ГНВЕП ЛТООА ДРНЕВ ТЕЬИО РПОТМ БЧМОР СОЫЬИ
Для обеспечения дополнительной скрытности можно повторно
зашифровать сообщение, которое уже прошло шифрование. Такой
метод шифрования называется двойной перестановкой. В случае
двойной перестановки столбцов и строк таблицы перестановки оп-
ределяются отдельно для столбцов и отдельно для строк. Сначала
в таблицу записывается текст сообщения, а потом поочередно пе-
реставляются столбцы, а затем строки. При расшифровании поря-
док перестановок должен быть обратным.
Пример выполнения шифрования методом двойной переста-
новки показан на рис. 3.6. Если считывать шифртекст из правой
таблицы построчно блоками по четыре буквы, то получится сле-
дующее:
ТЮАЕ ООГМ РЛИП ОЬСВ
Ключом к шифру двойной перестановки служит последова-
тельность номеров столбцов и номеров строк исходной таблицы (в
нашем примере последовательности 4132 и 3142 соответственно).
Рис. 3.6 Пример выполнения шифрования методом двойной перестановки
Число вариантов двойной перестановки быстро возрастает
при увеличении размера таблицы:
• для таблицы 3х3 36 вариантов;
• для таблицы 4х4 576 вариантов;
• для таблицы 5х5 14400 вариантов.
Однако двойная перестановка не отличается высокой стойко-
стью и сравнительно просто "взламывается" при любом размере
таблицы шифрования
Применение магических квадратов
В средние века для шифрования перестановкой применялись и магические квадраты.
Магическими квадратами называют квадратные таблицы с вписанными в их клетки последовательными натуральными числами, начиная от 1, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число.
Шифруемый текст вписывали в магические квадраты в соот-
ветствии с нумерацией их клеток Если затем выписать содержи-
мое такой таблицы по строкам, то получится шифртекст, сформи-
рованный благодаря перестановке букв исходного сообщения. В те
времена считалось, что созданные с помощью магических квадра-
тов шифртексты охраняет не только ключ, но и магическая сила.
Пример магического квадрата и его заполнения сообщением
ПРИЛЕТАЮ ВОСЬМОГО
показан на рис. 3.7.
Рис 3.7. Пример магического квадрата 4х4 и его заполнения сообщением
ПРИЛЕТАЮ ВОСЬМОГО
Шифртекст, получаемый при считывании содержимого правой
таблицы по строкам, имеет вполне загадочный вид:
ОИРМ ЕОСЮ ВТАЬ ЛГОП
Число магических квадратов быстро возрастает с увеличением
размера квадрата Существует только один магический квадрат
размером 3х3 (если не учитывать его повороты). Количество маги-
ческих квадратов 4х4 составляет уже 880, а количество магических
квадратов 5х5-около 250000.
Магические квадраты средних и больших размеров могли слу-
жить хорошей базой для обеспечения нужд шифрования того вре-
мени, поскольку практически нереально выполнить вручную пере-
бор всех вариантов для такого шифра.
3.4. Шифры простой замены
При шифровании заменой (подстановкой) символы шифруемо-
го текста заменяются символами того же или другого алфавита с
заранее установленным правилом замены. В шифре простой заме-
ны каждый символ исходного текста заменяется символами того же
алфавита одинаково на всем протяжении текста. Часто шифры
простой замены называют шифрами одноалфавитной подстановки.
Система шифрования Цезаря
Шифр Цезаря является частным случаем шифра простой за-
мены (одноалфавитной подстановки). Свое название этот шифр
получил по имени римского императора Гая Юлия Цезаря, который
использовал этот шифр при переписке с Цицероном (около 50г.
до н.э).
При шифровании исходного текста каждая буква заменялась
на другую букву того же алфавита по следующему правилу. Заме-
няющая буква определялась путем смещения по алфавиту от ис-
ходной буквы на К букв. При достижении конца алфавита выпол-
нялся циклический переход к его началу Цезарь использовал
шифр замены при смещении К=3. Такой шифр замены можно за-
дать таблицей подстановок, содержащей соответствующие пары
букв открытого текста и шифртекста Совокупность возможных
подстановок для К= 3 показана в табл 3.3
Например, послание Цезаря
VENI VIDI VICI
(в переводе на русский означает "Пришел, Увидел, Победил"), на-
правленное его другу Аминтию после победы над понтийским ца-
рем Фарнаком, сыном Митридата, выглядело бы в зашифрованном
виде так:
YHQL YLGL YLFL
Таблица 3.3
Одноалфавитные подстановки (К = 3. m = 26)
Выполним математический анализ шифра простой замены
(подстановки) на основе понятий, введенных в начале лекции [3] .
Подстановка в алфавите Zm является взаимно однозначным
: отображением из m на m:
: : t (t),
которое заменяет букву t открытого текста на букву (t) шифртек-
ста Множество всех подстановок на Zm называется симметричной
группой Zm и обозначается SYM (Zm ).
Симметричная группа SYM (Zm ) обладает следующими свойствами:
1. Замкнутость. Произведение подстановок 12 является
подстановкой:
: Zm 2 Zm 1 Zm
: t1, (2 (t)).
2. Ассоциативность. Оба способа заключения в скобки про-
изведения подстановок 123:
1 (23) = (12) 3
дают одинаковый результат.
3. Существование единичного элемента. Подстановка , определенная как
(t)=t, 0<t<m.
является единственным единичным элементом группы SYM (Zm )
по умножению:
= для всех SYM (Zm ).
4. Существование обратных элементов. Для каждой подстановки п имеется взаимно однозначно определенная обратная подстановка, обозначаемая -1, которая удовлетворяет соотношению:
-1 = .
Указанные свойства являются аксиомами группы.
Ключ К подстановки для алфавита Zm представляет собой
последовательность элементов симметричной группы из Zm :
К=( 0, 1,…, n-1,…), n SYM(Zm ), 0 n < .
Подстановка, определяемая ключом К, является криптогра-
фическим преобразованием Ек, которое шифрует n-грамму (x0, x1,
x2,...,xn-1) открытого текста в n-грамму (y0,y1,y2,…,yn-1) шифртек-
ста, где.
уi= i(xi), 0 i n,
для каждого n, n=1,2, 3,....
Криптографическое преобразование Ек называется одноалфавитной подстановкой, если значение л, одинаково для каждого i, i=0,1,2,…; в противном случае преобразование Ек называется многоалфавитной подстановкой.
На рис. 3.8 представлена схема реализации подстановки Ек.
Рис. 3.8. Схема подстановки Ек
Отметим характерные особенности подстановки ЕК:
• открытый текст шифруется побуквенно (буква за буквой);
• i-я буква уi, шифртекста является функцией только i-й компоненты i, ключа К и i-й буквы хi, открытого текста;
• шифрование n-граммы (X0, X1,.X2, ...,Xn-1) производится в соответствии с формулой
(у0, у1, у2,...,уn-1) = Ек (х0, х1, х2,…, хn-1).
Система Цезаря представляет собой одноалфавитную подстановку, которая шифрует n-грамму (х0,х1,х2,…,хn-1) открытого текста в n-грамму (у0, у1,y2,…,у n-1) шифртекста согласно следующему правилу:
уi = ЕK (хi), 0<i<n, (3.3)
ЕK : j ( j + К ) (mod n), 0 < К < m,
где j-числовой код буквы открытого текста; (j+K)-числовой код соответствующей буквы шифртекста.
В отличие от шифра Цезаря, описанного в начале этого под-
раздела, система шифрования Цезаря образует по существу се-
мейство одноалфавитных подстановок для выбираемых значений
ключа К, причем 0 К < m.
Достоинством системы шифрования Цезаря является просто-
та шифрования и расшифрования. К недостаткам системы Цезаря
следует отнести следующие:
• подстановки, выполняемые в соответствии с системой Цезаря,
не маскируют частот появления различных букв исходного от-
крытого текста;
• сохраняется алфавитный порядок в последовательности заме-
няющих букв; при изменении значения К изменяются только на-
чальные позиции такой последовательности;
• число возможных ключей К мало;
• шифр Цезаря легко вскрывается на основе анализа частот появления букв в шифртексте.
Криптоаналитическая атака против системы одноалфавитной
замены начинается с подсчета частот появления символов: опре-
деляется число появлений каждой буквы в шифртексте. Затем по-
лученное распределение частот букв в шифртексте сравнивается
с распределением частот букв в алфавите исходных сообщений,
например в английском. Буква с наивысшей частотой появления в
шифртексте заменяется на букву с наивысшей частотой появления
в английском языке и т.д. Вероятность успешного вскрытия систе-
мы шифрования повышается с увеличением длины шифртекста.
Концепция, заложенная в систему шифрования Цезаря, ока-
залась весьма плодотворной, о чем свидетельствуют ее многочис-
ленные модификации. Несколько таких модификаций будут рас-
смотрены ниже.
Аффинная система подстановок Цезаря
В системе шифрования Цезаря использовались только адди-
тивные свойства множества целых Zm. Однако символы множест-
ва Zm можно также умножать по модулю m. Применяя одновре-
менно операции сложения и умножения по модулю m над элемен-
тами множества Zm можно получить систему подстановок, кото-
рую называют аффинной системой подстановок Цезаря.
Определим преобразование в такой системе:
Еa,b : Zm,Zm,
Ea,b: t Ea,b (t),
Ea,b(t)=at+b(mod m), (3.4)
где a, b - целые числа, 0 a, b < m, НОД (а, m) = 1.
В данном преобразовании буква, соответствующая числу t,
заменяется на букву, соответствующую числовому значению
(at + b) по модулю m.
Следует заметить, что преобразование Еa,b(t) является вза-
имно однозначным отображением на множестве Zm только в том
случае, если наибольший общий делитель чисел а и m, обозна-
чаемый как НОД (а, m), равен единице, т.е. а и m должны быть
взаимно простыми числами.
Например, пусть m = 26, а = 3, b = 5. Тогда, очевидно, НОД
(3,26)=1, и мы получаем следующее соответствие между число-
выми кодами букв:
|
t |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
|
3t+5 |
5 |
8 |
11 |
14 |
17 |
20 |
23 |
0 |
3 |
6 |
9 |
12 |
15 |
18 |
21 |
24 |
1 |
4 |
7 |
10 |
13 |
16 |
19 |
22 |
25 |
2 |
Преобразуя числа в буквы английского языка, получаем сле-
дующее соответствие для букв открытого текста и шифртекста:
|
А |
В |
С |
D |
Е |
F |
G |
Н |
| |
J |
К |
L |
М |
N |
0 |
Р |
Q |
R |
S |
т |
U |
V |
W |
Х |
Y |
Z |
|
F |
I |
L |
0 |
R |
U |
Х |
А |
D |
G |
J |
М |
Р |
S |
V |
Y |
В |
Е |
Н |
к |
N |
Q |
Т |
W |
Z |
с |
Исходное сообщение HOPE преобразуется в шифртекст AWR
Достоинством аффинной системы является удобное управле-
ние ключами - ключи шифрования и расшифрования представля-
ются в компактной форме в виде пары чисел (а,b). Недостатки
аффинной системы аналогичны недостаткам системы шифрова-
ния Цезаря.
Аффинная система использовалась на практике несколько ве-
ков назад, а сегодня ее применение ограничивается большей ча-
стью иллюстрациями основных криптологических положений.
Система Цезаря с ключевым словом
Система шифрования Цезаря с ключевым словом является
одноалфавитной системой подстановки. Особенностью этой сис-
темы является использование ключевого слова для смещения и
изменения порядка символов в алфавите подстановки [4].
Выберем некоторое число k, 0 k < 25, и слово или короткую фразу в качестве ключевого слова. Желательно, чтобы все буквы ключевого слова были различными. Пусть выбраны слово DIPLOMAT в качестве ключевого слова и число к = 5.
Ключевое слово записывается под буквами алфавита, начиная с буквы, числовой код которой совпадает с выбранным числом к:
0 1 2 3 4 5 10 15 20 25
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
D I Р LОМ А Т
Оставшиеся буквы алфавита подстановки записываются после ключевого слова в алфавитном порядке:
5
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
V W Х Y Z D I P LOM A T B C E F G H J K N Q R S U
Теперь мы имеем подстановку для каждой буквы произволь-
ного сообщения.
Исходное сообщение SEND MORE MONEY
шифруется как HZBY TCGZ TCBZS
Следует отметить, что требование о различии всех букв клю-
чевого слова не обязательно. Можно просто записать ключевое
слово (или фразу) без повторения одинаковых букв. Например,
ключевая фраза
КАК ДЫМ ОТЕЧЕСТВА НАМ СЛАДОК И ПРИЯТЕН
и число k = 3 порождают следующую таблицу подстановок:
0 3
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь ЫЪ Э Ю Я
ЪЭ ЮК А Д Ы МО Т Е Ч С В Н Л И П Р Я Б Г Ж З Й У ФХ Ц Ш Щ Ь
Несомненным достоинством системы Цезаря с ключевым сло-
вом является то, что количество возможных ключевых слов прак-
тически неисчерпаемо. Недостатком этой системы является воз-
можность взлома шифртекста на основе анализа частот появле-
ния букв.
Шифрующие таблицы Трисемуса
В 1508г. аббат из Германии Иоганн Трисемус написал печат-
ную работу по криптологии под названием "Полиграфия". В этой
книге он впервые систематически описал применение шифрующих
таблиц, заполненных алфавитом в случайном порядке [5]. Для
получения такого шифра замены обычно использовались таблица
для записи букв алфавита и ключевое слово (или фраза). В табли-
цу сначала вписывалось по строкам ключевое слово, причем по-
вторяющиеся буквы отбрасывались. Затем эта таблица дополня-
лась не вошедшими в нее буквами алфавита по порядку. Посколь-
ку ключевое слово или фразу легко хранить в памяти, то такой
подход упрощал процессы шифрования и расшифрования.
Поясним этот метод шифрования на примере. Для русского
алфавита шифрующая таблица может иметь размер 4х8. Выберем
в качестве ключа слово БАНДЕРОЛЬ. Шифрующая таблица с та-,
ким ключом показана на рис. 3.9.
|
Б |
А |
Н |
Д |
Е |
Р |
О |
Л |
|
Ь |
В |
Г |
Ж |
З |
И |
Й |
К |
|
М |
П |
С |
Т |
У |
Ф |
Х |
Ц |
|
Ч |
Ш |
Щ |
Ы |
Ъ |
Э |
Ю |
Я |
Рис. 3.9. Шифрующая таблица с ключевым словом БАНДЕРОЛЬ
Как и в случае полибианского квадрата, при шифровании на-
ходят в этой таблице очередную букву открытого текста и записы-
вают в шифртекст букву, расположенную ниже ее в том же столб-
це. Если буква текста оказывается в нижней строке таблицы, тогда
для шифртекста берут самую верхнюю букву из того же столбца,
Например, при шифровании с помощью этой таблицы сооб-
щения
ВЫЛЕТАЕМПЯТОГО
получаем шифртекст
ПДКЗЫВЗЧШЛЫЙСЙ
Такие табличные шифры называются монограммными, так как
шифрование выполняется по одной букве. Трисемус первым заме-
тил, что шифрующие таблицы позволяют шифровать сразу по две
буквы. Такие шифры называются биграммными.
Биграммный шифр Плейфейра
Шифр Плейфейра, изобретенный в 1854г., является наиболее
известным биграммным шифром замены. Он применялся Велико-
британией во время первой мировой войны. Основой шифра
Плейфейра является шифрующая таблица со случайно располо-
женными буквами алфавита исходных сообщений.
Для удобства запоминания шифрующей таблицы отправите-
лем и получателем сообщений можно использовать ключевое сло-
во (или фразу) при заполнении начальных строк таблицы. В целом
структура шифрующей таблицы системы Плейфейра полностью
аналогична структуре шифрующей таблицы Трисемуса. Поэтому
для пояснения процедур шифрования и расшифрования в системе
Плейфейра воспользуемся шифрующей таблицей Трисемуса из
предыдущего раздела (см. рис.3.9).
Процедура шифрования включает следующие шаги.
1. Открытый текст исходного сообщения разбивается на пары
букв (биграммы). Текст должен иметь четное количество букв и
в нем не должно быть биграмм, содержащих две одинаковые
буквы. Если эти требования не выполнены, то текст модифици-
руется даже из-за незначительных орфографических ошибок.
2. Последовательность биграмм открытого текста преобразуется с
помощью шифрующей таблицы в последовательность биграмм
шифртекста по следующим правилам:
2а.Если обе буквы биграммы открытого текста не попадают на
одну строку или столбец (как, например, буквы А и И в табл.
на рис. 3.6), тогда находят буквы в углах прямоугольника, оп-
ределяемого данной парой букв. (В нашем примере это-
буквы АЙОВ. Пара букв АЙ отображается в пару 0В. После-
довательность букв в биграмме шифртекста должна быть
зеркально расположенной по отношению к последователь-
ности букв в биграмме открытого текста.)
2б.Если обе буквы биграммы открытого текста принадлежат од-
ному столбцу таблицы, то буквами шифртекста считаются
буквы, которые лежат под ними. (Например, биграмма НС дает биграмму шифртекста ГЩ.) Если при этом буква открытого
текста находится в нижней строке, то для шифртекста берется
соответствующая буква из верхней строки того же столбца.
(Например, биграмма ВШ дает биграмму шифртекста ПА.)
2в.Если обе буквы биграммы открытого текста принадлежат одной строке таблицы, то буквами шифртекста считаются буквы, которые лежат справа от них. (Например, биграмма НО дает биграмму шифртекста ДЛ.) Если при этом буква открытого текста находится в крайнем правом столбце, то для
шифра берут соответствующую букву из левого столбца в той же строке. (Например, биграмма ФЦ дает биграмму шифртекста ХМ.)
Зашифруем текст
ВСЕ ТАЙНОЕ СТАНЕТ ЯВНЫМ
Разбиение этого текста на биграммы дает
ВС ЕТ АЙ НО ЕС ТА НЕ ТЯ ВН ЫМ
Данная последовательность биграмм открытого текста преобразу-
ется с помощью шифрующей таблицы (см. рис. 3.9) в следующую
последовательность биграмм шифртекста:
ГП ДУ 0В ДЛ НУ ПД ДР ЦЫ ГА ЧТ
При расшифровании применяется обратный порядок действий.
Следует отметить, что шифрование биграммами резко повы-
шает стойкость шифров к вскрытию. Хотя книга И. Трисемуса "По-
лиграфия" была относительно доступной, описанные в ней идеи
получили признание лишь спустя три столетия. По всей вероятно-
сти, это было обусловлено плохой осведомленностью криптогра-
фов о работах богослова и библиофила Трисемуса в области
криптографии.
Криптосистема Хилла
Алгебраический метод, обобщающий аффинную подстановку
Цезаря
Ea,b : Zm Zm,
Еa,b (t) = t at + b (mod m)
для определения п-грамм, был сформулирован Лестером С.Хиллом.
Множество целых Zm, для которого определены операции сло-
жения, вычитания и умножения по модулю m, является примером
кольца. Кольцо R представляет собой алгебраическую систему, в которой определены операции сложения, вычитания и умноже-
ния пар элементов. Эта алгебраическая система обладает рядом
свойств:
• элементы кольца R образуют коммутативную группу относитель-
но операции сложения; кроме того, существуют единичный и об-
ратный элементы относительно операции сложения;
• умножение и сложение удовлетворяют ассоциативному и дист-
рибутивному законам.
Мультипликативное обратное -1 элемента а кольца может
существовать не всегда. Например, если модуль m = 26, то значе-
ния 2-1(mod 26) и 13-1(mod 26) не могут существовать.
Если модуль m является простым числом р, то существует
обратная величина любого ненулевого элемента t из Zp (при m = р),
поскольку значения
t (mod m), 2 t (mod m), 3 t (mod m),..., (p-1) t (mod m)
различаются, если 1 t р -1.
Множество Zp, где р - простое число, является примером ал-
гебраической системы, называемой конечным полем. Ненулевые
элементы Zp образуют мультипликативную группу.
Множество всех n-грамм x= (x0, x1, x2,.... xn-1) с компонентами
из кольца Zm, образует векторное пространство Zm,n над кольцом
Zm. Каждая n-грамма х называется вектором. В векторном про-
странстве Zm,n для векторов x определены операции сложения и
вычитания по модулю n, а также скалярное умножение вектора на
элемент t кольца Zm,n. Сложение и скалярное умножение являются
операциями, удовлетворяющими коммутативному, ассоциативно-
му и дистрибутивному законам. Вектор х является линейной ком-
бинацией векторов
Линейное преобразование Т может быть представлено матрицей размером nхn вида
Базисом для векторного пространства Zm,n является набор векторов из {x(i) : 0 i < L}, которые линейно независимы и порождают Zm,n. Каждый базис для Zm,n содержит п линейно независимых векторов. Любой набор из n векторов, которые линейно независимы над Zm,n. является базисом.
Пусть Т является линейным преобразованием, описываемым
матрицей (3.7), причем T :Zm,n Zm,n.
Если векторы {х(i) : 0 i < n} линейно независимы над Zm,n, .то-
гда их образы {Т(x(i) : 0 i < n } линейно независимы над Zm,n толь-
ко в том случае, если определитель матрицы Т, обозначаемый как
det (Т ), не делится на любое простое р, которое делит m. В этом
случае преобразование Т называется обратимым (или невырож-
денным) линейным преобразованием, имеющим обратное преоб-
разование Т-1:
T-1:Zm,n Zm,n
TT-1 = T-1T = I, (3.5)
где I - единичная матрица. Кроме того, Т-1 также является линейным преобразованием.
Например, когда m = 26 и матрица преобразования
то определитель этой матрицы
det (T ) =9=1(mod 2),
det (Т ) =9=9 (mod 13).
Поэтому существует обратное преобразование Т-1. Нетрудно убедиться, что
Используем это преобразование Т для определения биграм-
мной подстановки в английском алфавите {ABCDEFGH..XYZ}. Сна-
чала разобьем n-грамму открытого текста на биграммы, причем
выберем n кратным 2. Например, 12-грамма PAYMOREMONEY
делится на шесть биграмм:
PA YM OR ЕМ ON EY
Затем в каждой биграмме открытого текста заменим каждую букву ее числовым эквивалентом из таблицы:
РА 15 0; YM 24 12; OR 14 17;
EM 4 12; ON 14 13; EY 4 24;
Преобразование биграмм х, открытого текста в биграммы у,
шифртекста осуществляется в соответствии с уравнением
у, =T xj (mod26) или
где xj и уj - вектор-столбцы биграмм шифртекста и открытого текста соответственно.
Получаем
Заменяя в биграммах шифртекста числа на соответствующие
буквы согласно табл. 3.2, получаем 12-грамму шифртекста
ТЕ ЕЕ PJ WQ DP GY
Для расшифрования биграмм уj шифртекста и восстановле-
ния биграмм хj открытого текста необходимо выполнить обратное
преобразование T -1 согласно уравнению
хj = Т-1 уj.
В рассмотренном примере матрицы преобразования имели
размер 2х2 и шифровались биграммы (пары) букв. Хотя буква Е
может быть зашифрована по-разному в различных парах исходно-
го сообщения, одна и та же пара, например ЕМ, будет шифровать-
ся всегда одинаково на протяжении всего исходного текста.
Система Хилла является одноалфавитной в широком смысле
слова.
3.5. Шифры сложной замены
Шифры сложной замены называют многоалфавитными, так
как для шифрования каждого символа исходного сообщения при-
меняют свой шифр простой замены. Многоалфавитная подстанов-
ка последовательно и циклически меняет используемые алфавиты.
При r-алфавитной подстановке символ x0 исходного сообще-
ния заменяется символом у0 из алфавита В0, символ x1-символом
y1 из алфавита B1, и так далее, символ xr-1 заменяется символом
уr-1 из алфавита Br-1, символ xr заменяется символом уr снова из
алфавита Во, и т. д.
Общая схема многоалфавитной подстановки для случая r=4 показана на рис. 3.10.
|
Входной символ: |
Х0 |
X1 |
Х2 |
Х3 |
Х4 |
X5 |
Х6 |
Х7 |
Х8 |
Х9 |
|
Алфавит подстановки: |
Во |
B1 |
B2 |
В3 |
Во |
В1 |
В2 |
Bз |
Во |
В1 |
Рис. 3.10. Схема г-алфавитной подстановки для случая г = 4
Эффект использования многоалфавитной подстановки заклю-
чается в том, что обеспечивается маскировка естественной стати-
стики исходного языка, так как конкретный символ из исходного
алфавита А может быть преобразован в несколько различных
символов шифровальных алфавитов Bj. Степень обеспечиваемой
защиты теоретически пропорциональна длине периода r в после-
довательности используемых алфавитов Bj.
Многоалфавитные шифры замены предложил и ввел в прак-
тику криптографии Леон Батист Альберти, который также был из-
вестным архитектором и теоретиком искусства. Его книга "Трактат
о шифре", написанная в 1566г., представляла собой первый в Ев-
ропе научный труд по криптологии. Кроме шифра многоалфавит-
ной замены, Альберти также подробно описал устройства из вра-
щающихся колес для его реализации. Криптологи всего мира почи-
тают Л.Альберти основоположником криптологии[5].
Система шифрования Вижинера
Система Вижинера впервые была опубликована в 1586г. и является одной из старейших и наиболее известных многоалфавитных систем. Свое название она получила по имени французского дипломата XVI века Блеза Вижинера, который развивал и совершенствовал криптографические системы.
Система Вижинера подобна такой системе шифрования Цезаря, у которой ключ подстановки меняется от буквы к букве. Этот шифр многоалфавитной замены можно описать таблицей шифрования, называемой таблицей (квадратом) Вижинера. На рис. 3.11 и 3.12 показаны таблицы Вижинера для русского и английского алфавитов соответственно.
Таблица Вижинера используется для зашифрования и расшифрования. Таблица имеет два входа:
• верхнюю строку подчеркнутых символов, используемую для считывания очередной буквы исходного открытого текста;
• крайний левый столбец ключа.
Последовательность ключей обычно получают из числовых значений букв ключевого слова.
При шифровании исходного сообщения его выписывают в строку, а под ним записывают ключевое слово (или фразу). Если ключ оказался короче сообщения, то его циклически повторяют. В процессе шифрования находят в верхней строке таблицы очеред-
|
, |
а |
б |
в |
i; |
а |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
п |
р |
с |
т |
У |
Ф |
х |
м |
ч |
ш |
UJ |
ь |
ы |
ъ |
э |
ю |
я |
|
Ключ |
||||||||||||||||||||||||||||||||
|
0 |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
|
1 |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
|
2 |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
х |
ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
|
3 |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
|
4 |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
|
5 |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
д |
|
6 |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
|
7 |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
|
8 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
х |
ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
|
9 |
и, |
к |
л |
м |
н |
0 |
п |
р |
с |
т |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
|
10 |
к |
л |
м |
н |
0 |
п |
р |
с |
т |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
|
11 |
л |
м |
н |
0 |
п |
р |
с |
т |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
|
12 |
м |
н |
0 |
п |
р |
с |
т |
У |
Ф |
х |
ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
|
13 |
н |
0 |
п |
р |
с |
т |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
|
14 |
0 |
п |
р |
с |
т |
У |
Ф |
х |
ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
д |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
|
15 |
п |
Р |
с |
т |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
|
16 |
р |
с |
т |
У |
Ф |
х |
ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
п |
|
17 |
с |
т |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
|
18 |
т |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
|
19 |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
п |
р |
с |
т |
|
20 |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
|
21 |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
|
22 |
ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
Р |
с |
т |
У |
Ф |
х |
|
23 |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
Р |
с |
т |
у |
Ф |
х |
Ц |
|
24 |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
х |
Ц |
ч |
|
25 |
Щ |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
х |
Ц |
ч |
ш |
|
26 |
ь |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
х |
ц |
ч |
ш |
Щ |
|
27 |
ы |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
х |
ц |
ч |
ш |
Щ |
ь |
|
28 |
ъ |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
|
29 |
э |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
У |
Ф |
х |
ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
|
30 |
ю |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
П |
р |
с |
т |
у |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
|
31 |
я |
а |
б |
в |
г |
А |
е |
ж |
3 |
и |
и |
к |
л |
м |
н |
0 |
п |
р |
с |
т |
у |
Ф |
х |
Ц |
ч |
ш |
Щ |
ь |
ы |
ъ |
э |
ю |
Рис.3.11. Таблица Вижинера для русского алфавита.
|
А |
в |
С |
D |
E |
F |
G |
H |
1 |
J, |
К |
I; |
M |
N |
Q |
p |
Q |
В |
S |
Т |
У |
v |
W |
x |
Y |
z |
|
|
Ключ |
||||||||||||||||||||||||||
|
0 |
А |
в |
С |
D |
E |
F |
G |
H |
J |
К |
L |
M |
N |
0 |
p |
Q |
R |
S |
Т |
U |
v |
W |
Л |
Y |
z |
|
|
1 |
В |
с |
D |
E |
с |
G |
H |
J |
К |
L |
M |
N |
0 |
P |
Q |
R |
S |
T |
U |
V |
w |
x |
у |
7 |
A |
|
|
2 |
С |
D |
E |
p |
G |
H |
J |
К |
L |
M |
N |
0 |
p |
Q |
R |
S |
Т |
u |
v |
w |
x |
Y |
7 |
A |
В |
|
|
3 |
D |
Е |
F |
G |
H |
I |
J |
К |
L |
M |
N |
0 |
P |
Q |
R |
S |
Т |
U |
v |
w |
x |
Y |
Z |
A |
В |
С |
|
4 |
Е |
F |
G |
H |
J |
К |
L |
M |
N |
0 |
P |
Q |
R |
S |
Т |
u |
v |
w |
x |
Y |
7 |
A |
В |
С |
D |
|
|
5 |
F |
G |
H |
J |
К |
L |
M |
N |
0 |
P |
Q |
R |
S |
Т |
u |
v |
w |
x |
Y |
Z |
A |
В |
с |
D |
E |
|
|
6 |
G |
H |
J |
К |
L |
M |
N |
0 |
P |
Q |
R |
S |
Т |
U |
v |
w |
x |
Y |
Z |
A |
В |
С |
D |
E |
F |
|
|
7 |
Н |
I |
J |
К |
L |
M |
N |
0 |
P |
Q |
R |
S |
Т |
u |
v |
w |
x |
Y |
7 |
A |
В |
С |
D |
E |
с |
G |
|
8 |
J |
К |
L |
M |
N |
0 |
P |
Q |
R |
S |
Т |
U |
v |
w |
x |
Y |
Z |
A |
В |
С |
D |
E |
p |
G |
H |
|
|
9 |
J |
К |
L |
M |
N |
0 |
P |
Q |
R |
S |
Т |
U |
v |
w |
x |
Y |
Z |
A |
В |
С |
D |
E |
F |
G |
H |
1 |
|
10 |
К |
L |
M |
N |
0 |
p |
Q |
R |
S |
Т |
U |
v |
w |
x |
Y |
Z |
A |
В |
p |
D |
E |
F |
G |
H |
1 |
J |
|
11 |
L |
M |
N |
0 |
p |
Q |
R |
S |
Т |
U |
v |
w |
x |
Y |
Z |
A |
В |
С |
D |
E |
F |
G |
H |
1 |
J |
К |
|
12 |
М |
N |
0 |
P |
Q |
R |
S |
Т |
U |
v |
w |
x |
Y |
Z |
A |
В |
С |
D |
E |
F |
G |
H |
J |
К |
L |
|
|
13 |
N |
0 |
P |
r\ |
R |
S |
Т |
U |
v |
w |
x |
Y |
Z |
A |
В |
С |
D |
E |
F |
G |
H |
1 |
J |
К |
L |
M |
|
14 |
0 |
P |
Q |
R |
S |
Т |
U |
v |
w |
x |
Y |
Z |
A |
В |
С |
D |
E |
F |
G |
H |
1 |
J |
К |
L |
M |
N |
|
15 |
Р |
Q |
R |
S |
Т |
U |
v |
w |
x |
Y |
Z |
A |
В |
С |
D |
E |
F |
G |
H |
1 |
J |
К |
L |
M |
N |
0 |
|
16 |
Q |
R |
S |
Т |
U |
v |
w |
x |
Y |
Z |
A |
В |
С |
D |
E |
F |
G |
H |
1 |
J |
К |
L |
M |
N |
0 |
P |
|
17 |
R |
S |
Т |
U |
v |
w |
x |
Y |
Z |
A |
В |
С |
D |
E |
F |
G |
H |
1 |
J |
К |
L |
M |
N |
0 |
P |
Q |
|
18 |
S |
Т |
U |
v |
w |
x |
Y |
Z |
A |
В |
С |
D |
E |
F |
G |
H |
J |
К |
L |
M |
N |
0 |
P |
Q |
|R |
|
|
19 |
Т |
U |
v |
w |
x |
Y |
Z |
A |
В |
С |
D |
E |
F |
G |
H |
1 |
J |
К |
L |
M |
N |
0 |
P |
Q |
R |
с |
|
20 |
u |
v |
w |
x |
Y |
Z |
A |
В |
С |
D |
E |
F |
G |
H |
1 |
J |
К |
L |
M |
N |
0 |
P |
Q |
R |
S |
Т |
|
21 |
v |
w |
x |
Y |
Z |
A |
В |
С |
D |
E |
F |
G |
H |
J |
К |
L |
M |
N |
0 |
P |
Q |
R |
g |
Т |
u |
|
|
22 |
w |
x |
Y |
Z |
A |
В |
С |
D |
E |
F |
G |
H |
1 |
J |
К |
L |
M |
N |
0 |
P |
Q |
R |
0 |
Т |
U |
v |
|
23 |
x |
Y |
Z |
A |
В |
С |
D |
E |
F |
G |
H |
J |
К |
L |
M |
N |
0 |
P |
Q |
R |
S |
Т |
U |
v |
w |
|
|
24 |
Y |
Z |
A |
В |
С |
D |
E |
F |
G |
H |
J |
К |
L |
M |
N |
0 |
P |
Q |
R |
0 |
Т |
U |
v |
w |
x |
|
|
25 |
z |
A |
В |
С |
D |
E |
F |
G |
H |
J |
К |
L |
M |
N |
0 |
P |
Q |
R |
S |
т |
U |
v |
w |
x |
Y |
Рис. 3.12. Таблица Вижинера для английского алфавита.
ную букву исходного текста и в левом столбце очередное значение
ключа. Очередная буква шифртекста находится на пересечении
столбца, определяемого шифруемой буквой, и строки, определяе-
мой числовым значением ключа.
Пусть ключевая последовательность имеет длину г, тогда ключ r-алфавитной подстановки есть r-строка.
= (0,1,…,r-1), (3.6)
(у0,у1,…,уn-1) = (0(х0),1(х1),…,n-1(xn-1)), (3.7)
где i = (i mod r)
Рассмотрим пример получения шифртекста с помощью таб-
лицы Вижинера. Пусть выбрано ключевое слово АМБРОЗИЯ. Не-
обходимо зашифровать сообщение ПРИЛЕТАЮ СЕДЬМОГО.
Выпишем исходное сообщение в строку и запишем под ним
ключевое слово с повторением. В третью строку будем выписы-
вать буквы шифртекста, определяемые из таблицы Вижинера.
Сообщение П Р И Л Е Т А Ю С Е Д Ь М О Г О
Ключ А М Б РО З И Я А М Б Р О З И Я
Шифртекст П Ъ ЙЫУ ЩИ Э С С Е К Ь Х Л Н
Шифр "двойной квадрат" Уитстона
В 1854г. англичанин Чарльз Уитстон разработал новый метод
шифрования биграммами, который называют "двойным квадра-
том". Свое название этот шифр получил по аналогии с полибиан-
ским квадратом. Шифр Уитстона открыл новый этап в истории раз-
вития криптографии. В отличие от полибианского шифр "двойной
квадрат" использует сразу две таблицы, размещенные по одной
горизонтали, а шифрование идет биграммами, как в шифре Плей-
фейра. Эти не столь сложные модификации привели к появлению
на свет качественно новой криптографической системы ручного
шифрования. Шифр "двойной квадрат" оказался очень надежным и
удобным и применялся Германией даже в годы второй мировой
войны.
Поясним процедуру шифрования этим шифром на примере. Пусть имеются две таблицы со случайно расположенными в них русскими алфавитами (рис. 3.13). Перед шифрованием исходное сообщение разбивают на биграммы. Каждая биграмма шифруется отдельно. Первую букву биграммы находят в верхней таблице, а вторую букву - в нижней таблице. Затем мысленно строят прямо-угольник так, чтобы буквы биграммы лежали в его противоположных вершинах. Другие две вершины этого прямоугольника дают буквы биграммы шифртекста. Предположим, что шифруется биграмма исходного текста ИЛ. Буква И находится в столбце 1 и строке 2 левой таблицы. Буква Л находится в столбце 5 и строке 4 правой таблицы. Это означает, что прямоугольник образован строками 2 и 4, а также столбцами 1 левой таблицы и 5 правой таблицы. Следовательно, в биграмму шифртекста входят буква О, расположенная в столбце 5 и строке 2
правой таблицы, и буква В, расположенная в столбце 1 и строке 4 левой таблицы, т.е. получаем биграмму шифртекста OВ.
|
Щ |
Н |
ю |
р |
|
|
и |
т |
Ь |
Ц |
Б |
|
я |
м |
Е |
. |
С |
|
в |
ы |
П |
ч |
|
|
: |
д |
У |
0 |
К |
|
3 |
э |
Ф |
г |
Ш |
|
х |
А |
, |
л |
Ъ |
|
И |
Ч |
Г |
я |
т |
|
, |
ж |
Ь |
м |
0 |
|
3 |
ю |
Р |
в |
Щ |
|
ц |
П |
Е |
л |
|
|
Ъ |
А |
Н |
. |
х |
|
э |
К |
с |
Ш |
д |
|
Б |
Ф |
У |
ы |
Рис. 3.13. Две таблицы со случайно расположенными символами
русского алфавита для шифра "двойной квадрат"
Если обе буквы биграммы сообщения лежат в одной строке,
то и буквы шифртекста берут из этой же строки. Первую букву би-
граммы шифртекста берут из левой таблицы в столбце, соответст-
вующем второй букве биграммы сообщения. Вторая же буква би-
граммы шифртекста берется из правой таблицы в столбце, соот-
ветствующем первой букве биграммы сообщения. Поэтому би-
грамма сообщения ТО превращается в биграмму шифртекста ЖБ.
Аналогичным образом шифруются все биграммы сообщения:
Сообщение ПР ИЛ ЕТ АЮ _Ш ЕС ТО ГО
Шифртекст ПЕ OВ ЩН ФМ ЕШ РФ БЖ ДЦ
Шифрование методом "двойного квадрата" дает весьма ус-
тойчивый к вскрытию и простой в применении шифр. Взламывание
шифртекста "двойного квадрата" требует больших усилий, при
этом длина сообщения должна быть не менее тридцати строк.
Шифрование методом Вернама
Система шифрования Вернама является в сущности частным случаем системы шифрования Вижинера при значении модуля m =2. Конкретная версия этого шифра, предложенная в 1926 г. Гилбертом Вернамом, сотрудником фирмы АТ&Т США, использует двоичное представление символов исходного текста.
Каждый символ исходного открытого текста из английского алфавита {A,B,C,D,…,Z}, расширенного шестью вспомогательными символами (пробел, возврат каретки и т.п.), сначала кодировался в 5-ти битовый блок (b0, b1,…,b4) телеграфного кода Бодо.
Случайная последовательность двоичных ключей k0, k1, k2,… заранее записывалась на бумажной ленте.
Схема передачи сообщений с использованием шифрования методом Вернама показана на рис. 3.14. Шифрование исходного текста, предварительно преобразованного в последовательность двоичных символов х, осуществлялось путем сложения по модулю 2 символов х с последовательностью двоичных ключей k. Символы шифртекста
y = x k. (3.10)
Рис. 3.14. Схема шифрования и расшифрования сообщений
по методу Вернама
Расшифрование состоит в сложении по модулю 2 символов у
шифртекста с той же последовательностью ключей k:
yk = xkk = x. (3.11)
При этом последовательности ключей, использованные при
шифровании и расшифровании, компенсируют друг друга (при
сложении по модулю 2), и в результате восстанавливаются симво-
лы х исходного текста.
При разработке своей системы Вернам проверял ее с помо-
щью закольцованных лент, установленных на передатчике и при-
емнике для того, чтобы использовалась одна и та же последова-
тельность ключей.
Следует отметить, что метод Вернама не зависит от длины
последовательности ключей и, кроме того, он позволяет использо-
вать случайную последовательность ключей. Однако при реализа-
ции метода Вернама возникают серьезные проблемы, связанные с
необходимостью доставки получателю такой же последовательно-
сти ключей, как у отправителя, либо с необходимостью безопасно-
го хранения идентичных последовательностей ключей у отправи-
теля и получателя. Эти недостатки системы шифрования Вернама
преодолены при шифровании методом гаммирования.
3.6. Шифрование методом гаммирования
Под гаммированием понимают процесс наложения по опре-
деленному закону гаммы шифра на открытые данные Гамма
шифра - это псевдослучайная последовательность, выработанная
по заданному алгоритму для зашифрования открытых данных и
расшифрования зашифрованных данных
Процесс зашифрования заключается в генерации гаммы шиф-
ра и наложении полученной гаммы на исходный открытый текст
обратимым образом, например с использованием операции сло-
жения по модулю 2.
Следует отметить, что перед зашифрованием открытые дан-
ные разбивают на блоки Т0(i) одинаковой длины, обычно по 64 бита.
Гамма шифра вырабатывается в виде последовательности блоков
Гш(i) аналогичной длины.
Уравнение зашифрования можно записать в виде
Tш(i) = Гш (i) Tо (i), i=1...M, (3.12)
где Тш(i) - i-й блок шифртекста; Гш(i) – i-й блок гаммы шифра; Т0(i) – i-й
блок открытого текста; М - количество блоков открытого текста.
Процесс расшифрования сводится к повторной генерации
гаммы шифра и наложению этой гаммы на зашифрованные дан-
ные. Уравнение расшифрования имеет вид
Т0(i) = Гш(i) Тш(i) . (3.13)
Получаемый этим методом шифртекст достаточно труден для
раскрытия, поскольку теперь ключ является переменным По сути
дела гамма шифра должна изменяться случайным образом для
•каждого шифруемого блока. Если период гаммы превышает длину
всего шифруемого текста и злоумышленнику неизвестна никакая
часть исходного текста, то такой шифр можно раскрыть только
прямым перебором всех вариантов ключа. В этом случае крипто-
стойкость шифра определяется длиной ключа.
Методы генерации псевдослучайных последовательностей чисел
При шифровании методом гаммирования в качестве ключа
используется случайная строка битов, которая объединяется с от-
крытым текстом, также представленным в двоичном виде (напри-
мер, А= 00000, В =00001, С =00010 и т.д ), с помощью побитового
сложения по модулю 2, и в результате получается шифрованный
текст Генерирование непредсказуемых двоичных последователь-
ностей большой длины является одной из важных проблем клас-
сической криптографии. Для решения этой проблемы широко ис-
пользуются генераторы двоичных псевдослучайных последова-
тельностей.
Генерируемые псевдослучайные ряды чисел часто называют
гаммой шифра или просто гаммой (по названию буквы у греческого
алфавита, часто используемой в математических формулах для
обозначения случайных величин).
Обычно для генерации последовательности псевдослучай-
ных чисел применяют компьютерные программы, которые, хотя и
называются генераторами случайных чисел, на самом деле выда-
ют детерминированные числовые последовательности, которые по
своим свойствам очень похожи на случайные [5].
К криптографически стойкому генератору псевдослучайной
последовательности чисел (гаммы шифра) предъявляются три ос-
новных требования:
• период гаммы должен быть достаточно большим для шифрова-
ния сообщений различной длины;
• гамма должна быть практически непредсказуемой, что означает
невозможность предсказать следующий бит гаммы, даже если
известны тип генератора и предшествующий кусок гаммы;
• генерирование гаммы не должно вызывать больших технических
сложностей.
Длина периода гаммы является самой важной характеристи-
кой генератора псевдослучайных чисел. По окончании периода
числа начнут повторяться, и их можно будет предсказать. Требуе-
мая длина периода гаммы определяется степенью закрытости
данных. Чем длиннее ключ, тем труднее его подобрать. Длина пе-
риода гаммы зависит от выбранного алгоритма получения псевдо-
случайных чисел.
Второе требование связано со следующей проблемой: как
можно достоверно убедиться, что псевдослучайная гамма конкрет-
ного генератора является действительно непредсказуемой? Пока
не существуют такие универсальные и практически проверяемые
критерии и методики. Чтобы гамма считалась непредсказуемой,
т.е истинно случайной, необходимо, чтобы ее период был очень
большим, а различные комбинации битов определенной длины
были равномерно распределены по всей ее длине.
Третье требование обусловливает возможность практической
реализации генератора программным или аппаратным путем с
обеспечением необходимого быстродействия.
Один из первых способов генерации псевдослучайных чисел
на ЭВМ предложил в 1946г. Джон фон Нейман. Суть этого способа
состоит в том, что каждое последующее случайное число образу-
ется возведением в квадрат предыдущего числа с отбрасыванием
цифр младших и старших разрядов Однако этот способ оказался
ненадежным и от него вскоре отказались.
Из известных процедур генерации последовательности псев-
дослучайных целых чисел наиболее часто применяется так назы-
ваемый линейный конгруэнтный генератор Этот генератор выра-
батывает последовательность псевдослучайных чисел Y1,Y2,...,Yi-1,
yi, . ., используя соотношение
Yi = (aYi-1+b)mod m, (3.14)
где Yi - i-e (текущее) число последовательности; Yi-1 – предыдущее число последовательности; а, Ь и m-константы; m-модуль, а- множитель (коэффициент); b-приращение, Y0 - порождающее число (исходное значение).
Текущее псевдослучайное число Yi получают из предыдущего
числа Yi-1 умножением его на коэффициент а, сложением с при-
ращением b и вычислением остатка от деления на модуль m Дан-
ное уравнение генерирует псевдослучайные числа с периодом по-
вторения, который зависит от выбираемых значений параметров
а, b и m и может достигать значения m. Значение модуля m берет-
ся равным 2n либо равным простому числу, например m=231-1,
Приращение b должно быть взаимно простым с m, коэффициент а
должен быть нечетным числом.
Конгруэнтные генераторы, работающие по алгоритму, пред-
ложенному Национальным бюро стандартов США, используются, в
частности, в системах программирования Эти генераторы имеют
длину периода 224 и обладают хорошими статистическими свойст-
вами Однако такая длина периода мала для криптографических
применений Кроме того, доказано, что последовательности, гене-
рируемые конгруэнтными генераторами, не являются криптогра-
фически стойкими
Существует способ генерации последовательностей псевдо-
случайных чисел на основе линейных рекуррентных соотноше-
ний.
Рассмотрим рекуррентные соотношения и их разностные
уравнения:
где h0 0, hk =1 и каждое hi принадлежит полю GF(q)
Решением этих уравнений является последовательность эле-
ментов a0,a1,a2,... поля GF(q). Это соотношение
определяет правило вычисления ak по известным значениям
величин a0,a1,a2, ...,ak-1. Затем по известным значениям a0,a1,
а2,..., ak находят аk+1 и т.д. В результате по начальным значениям a0, a1, a2,.... ak-1 можно построить бесконечную последователь-
ность, причем каждый ее последующий член определяется из k
предыдущих. Последовательности такого вида легко реализуются
на компьютере, при этом реализация получается особенно про-
стой, если все hi и аi принимают значения 0 и 1 из поля GF(2).
На рис. 3.15 показана линейная последовательная переключа-
тельная схема, которая может быть использована для вычисления
суммы (аi+k) и, следовательно, для вычисления значения ak по
значениям k предыдущих членов последовательности. Исходные
величины а0, a1, a2, ...,ak-1 помещаются в разряды сдвигового реги-
стра, последовательные сдвиги содержимого которого соответст-
вуют вычислению последовательных символов, при этом
Рис.3.15. Генератор с регистром сдвига
выход после 1-го сдвига равен ai. Данное устройство называют ге-
нератором последовательности чисел, построенным на базе сдви-
гового регистра с линейной обратной связью.
Решения линейных рекуррентных соотношений, реализуемые
генератором с регистром сдвига, описываются следующей теоре-
мой. Пусть многочлен
где Х - формальная переменная; h j - коэффициент при Х j, принимающий значение 0 или 1; h0 0, hk = 1, и пусть n - наименьшее целое положительное число, для которого многочлен Xn-1 делится на h(X). Кроме того, многочлен
g (X)=(Xn-1)/h(X).
Тогда решения рекуррентных соотношений
в виде последовательности элементов а0, a1, ai,..., an-1 периодичны
с периодом n и совокупность, составленная из первых периодов
всех возможных решений, рассматриваемых как многочлены по
модулю (xn-1), т.е.
а(x)= а0 xn-1 +а1 xn-2 +...+an-2 x +аn-1,
совпадает с идеалом, порожденным многочленом g(x) в алгебре
многочленов по модулю, (xn-1). Доказательство этой теоремы
можно найти в литературе [6].
Заметим, что если при таком определении многочлена а(x)
элементы a0,a1,a2,... вычисляются в порядке возрастания номе-
ров, то коэффициенты многочлена а(x) вычисляются, начиная с
коэффициентов при степенях высших порядков. Следует также
k
отметить, что вид многочлена h(x)= hj.xj определяет конфигура-
j=0
цию обратных связей (отводов) hj; в генераторе со сдвиговым реги-
стром. Другими словами, если у многочлена h(x) коэффициент
hj=1, это означает, что отвод hj в схеме генератора присутствует,
если же у многочлена h(x) коэффициент hj=0, то отвод hj; в схеме
генератора отсутствует. В [7] показано, что в качестве h(x) необ-
ходимо выбирать неприводимый примитивный многочлен
При таком выборе многочлена h(x) со старшей
степенью m, генератор обеспечивает выдачу псевдослучайной по-
следовательности двоичных чисел с максимально возможным пе-
риодом 2m-1.
Рассмотрим в качестве примера трехразрядный сдвиговый ре-
гистр с линейной обратной связью (рис. 3.16), построенный в соот-
ветствии с неприводимым примитивным многочленом
h(X)=XЗ+X2+1,
где коэффициенты h3=1, h2=1, h1=0, h0=1.
Гш
Рис. 3.16. Трехразрядный регистр сдвига с обратными связями
(генератор гаммы шифра Гш)
Пусть ключом является 101. Регистр начинает работать с этого
состояния; последовательность состояний регистра приведена на
рис. 3.16. Регистр проходит через все семь ненулевых состояний и
снова возвращается в свое исходное состояние 101. Это - наи-
более длинный период данного регистра с линейной обратной свя-
зью. Такая последовательность называется последовательнос-
тью максимальной длины для сдвигового регистра (Maximal
Lenght Shift Register Sequence-MLSRS). Питерсон и Уэлдон.
показали, что при любом целом m существует m-битовая последо-
вательность MLSRS с периодом 2m-1. В частности, при т=100
последовательность будет иметь период 2100-1 и не повторится
1016 лет при передаче ее по линии связи со скоростью 1 Мбит/с.
В нашем примере выходной последовательностью (гаммой
шифра) ГШ сдвигового регистра с обратной связью является по-
следовательность 1010011, которая циклически повторяется. В этой
последовательности имеется четыре единицы и три нуля, и их
распределение настолько близко к равномерному, насколько это
возможно в последовательности, имеющей длину 7. Если рассмот-
реть пары последовательных битов, то пары 10 и 01 появляются по
два раза, а пары 00 и 11-один раз, что опять оказывается на-
столько близким к равномерному распределению, насколько это
возможно. В случае последовательности максимальной длины для
m-разрядного регистра это свойство равнораспределенности рас-
пространяется на тройки, четверки и т.д. битов, вплоть до m-би-
товых групп. Благодаря такой близости к равномерному распреде-
лению последовательности максимальной длины часто использу-
ются в качестве псевдослучайных последовательностей в крипто-
графических системах, которые имитируют работу криптостойкой
системы одноразового шифрования.
Хотя такая криптографическая система осуществляет имита-
цию заведомо криптостойкой системы одноразового шифрования,
сама она не отличается стойкостью и может быть раскрыта за не-
сколько секунд работы компьютера при условии наличия известно-
го открытого текста [8].
Если отводы регистра с обратной связью зафиксированы, то
для нахождения начального состояния регистра достаточно знать
m битов открытого текста. Чтобы найти m битов ключевого потока,
m битов известного открытого текста складывают по модулю 2 с
соответствующими m битами шифртекста. Полученные m битов
дают состояние сдвигового регистра с обратной связью в обратном
направлении на некоторый момент времени. Затем, моделируя
работу регистра назад, можно определить его исходное состояние.
Если отводы регистра с обратной связью не фиксированы, а
являются частью ключа, то достаточно 2m битов известного от-
крытого текста, чтобы сравнительно быстро определить располо-
жение отводов регистра и его начальное состояние. Пусть S(i)-
вектор-столбец, состоящий из m символов 0 и 1, который опреде-
ляет состояние регистра в i-й момент времени. Тогда
S(i+1)=AS(i)mod 2,
где А - матрица размером mxm, определяющая положение отво-
дов регистра с обратной связью.
Для трехразрядного регистра (рис. 3.16)
Матрица А всегда имеет следующую структуру: в ее первой
строке отражена последовательность отводов в регистре, непо-
средственно под главной диагональю располагаются единицы, а в
остальных позициях располагаются нули.
2m битов известного открытого текста позволяют вычислить
2m последовательных битов ключевого потока. Для упрощения
обозначений предположим, что это - первые 2m битов ключевого
потока. Следовательно,
• S(1) - первая группа m известных битов ключевого потока;
• S(2) - следующая группа (начиная с номера 2) из m известных
битов ключевого потока;
• S(m+1) - последняя группа из m известных битов ключевого потока.
Далее можно образовать две матрицы размером mxm:
которые связаны соотношением
X(2)=AX(1)mod 2.
Можно показать, что для любой последовательности макси-
мальной длины матрица Х(1) всегда несингулярна, поэтому матри-
цу А можно вычислить как
A=X(2)[X(1)]-1 mod 2..
Обращение матрицы Х(1) требует (самое большее) порядка
m3 операций, поэтому легко выполняется при любом разумном
значении m.
Для криптографии последовательности максимальной длины
MLSRS можно сделать более криптостойкими, используя нелиней-
ную логику. В частности, предложен вариант, в котором в ка-
честве ключевого потока используется нелинейно "фильтрован-
ное" содержимое сдвигового регистра, а для получения последо-
вательности максимальной длины - линейная обратная связь, как показано на рис. 3.17.
м
Рис 3.17 Линейный сдвиговый регистр с нелинейными
логическими цепями на выходе
Функция f должна выбираться так, чтобы обеспечить хороший
баланс между нулями и единицами, а фильтрованная последова-
тельность имела распределение, близкое к равномерному Необ-
ходимо также, чтобы фильтрованная последовательность имела
большой период. Если (2m-1) является простым числом (как в
примере при m=3 имеем 23-1=7), то фильтрованная последова-
тельность может иметь период (2m-1) (при выборе структуры
сдвигового регистра в соответствии с неприводимым примитивным
многочленом h(x) степени m).
К таким значениям m относятся, в частности, следующие
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281,
а полученные таким образом простые числа называются просты-
ми числами Мерсенна.
Несмотря на то, что фильтрованную выходную последова-
тельность обычно нельзя получить с помощью m-разрядного сдви-
гового регистра с линейной обратной связью, ее всегда можно по-
лучить с помощью сдвигового регистра большей длины с линейной
обратной связью [9]. Регистр длиной (2m-1) всегда позволит это
сделать, а иногда пригоден и более короткий регистр
Еще более привлекательно использование в цепи обратной
связи нелинейной логики, однако теория таких схем недостаточно
хорошо освещена (в открытой литературе).
Упражнение к лекции 3.
1. ГОСТ 28147-89. Система обработки информации. Защита
криптографическая. Алгоритм криптографического преобразования.
2. Хэйт Т. Размышления об электронных платежах // Сети и системы связи.-1996.-№4.-С.118-121.
3. Konheim A.G. Cryptography.A Primer.-John Wiley&Sons, Inc.,1981.-432 p.
4. Саломаа А. Криптография с открытым ключом: Пер. с англ.- М.: Мир, 1996.-304 с.
5. Жельников В. Криптография от папируса до компьютера.- M.-.ABF, 1997.-336 с.
6. Питерсон У,, Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ.-М.: Мир, 1976.-594 с.
7. Мельников Ю.Н. Электронная цифровая подпись. Возможности защиты // Конфидент.-1995.-№ 6.-С. 35-47.
8. Диффи У., Хеллман М.Э. Защищенность и имитостойкость: Введение в криптографию//ТИИЭР.-1979.-Т. 67. №3.-С.71-109.
9. Месси Дж. Л. Введение в современную криптологию // ТИИЭР.- 1988.-Т.76, №5.-С.24-42.