Алгоритм и схема криптосистемы передачи информации с использованием комбинации шифров простой и сложной замены для телефонной сети общего пользования

2

Курсовая работа

по дисциплине

Криптографические методы защиты информации

Тема: Алгоритм и схема криптосистемы передачи информации с использованием комбинации шифров простой и сложной замены для телефонной сети общего пользования

1. Основные понятия и определения

Большинство средств защиты информации базируется на использовании криптографических шифров и процедур шифрования - расшифрования. В соответствии со стандартом ГОСТ 28147-89 под шифром понимают совокупность обратимых преобразований множества открытых данных на множество зашифрованных данных, задаваемых ключом и алгоритмом криптографического преобразования.

Ключ - это конкретное секретное состояние некоторых параметров алгоритма криптографического преобразования данных, обеспечивающее выбор только одного варианта из всех возможных для данного алгоритма.

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

К шифрам, используемым для криптографической защиты информации, предъявляется ряд требований:

*достаточная криптостойкость (надежность закрытия данных);

*простота процедур шифрования и расшифрования;

*незначительная избыточность информации за счет шифрования;

*нечувствительность к небольшим ошибкам шифрования и др.

В той или иной мере этим требованиям отвечают:

*шифры перестановок;

*шифры замены;

*шифры гаммирования;

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

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

Шифрование заменой (подстановкой) заключается в том, что символы шифруемого текста заменяются символами того же или другого алфавита в соответствии с заранее обусловленной схемой замены.

Шифрование гаммированием заключается в том, что символы шифруемого текста складываются с символами некоторой случайной последовательности, именуемой гаммой шифра. Стойкость шифрования определяется в основном длиной (периодом) неповторяющейся части гаммы шифра. Поскольку с помощью ЭВМ можно генерировать практически бесконечную гамму шифра, то данный способ является одним из основных для шифрования информации в автоматизированных системах.

Шифрование аналитическим преобразованием заключается в том, что шифруемый текст преобразуется по некоторому аналитическому правилу (формуле).

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

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

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

S ={а₀, а₁, а₂, . . . , а_m-1}. (1.1)

Объединяя по определенному правилу буквы из алфавита S, можно создать новые алфавиты:

*алфавит S², содержащий m² биграмм

a₀a₀, a₀a₁, ..., а_m-1а_m-1; (1.2)

*алфавит S³, содержащий m³ триграмм

a₀a₀a₀, a₀a₀a₁,..., а_m-1а_m-1а_m-1. (1.3)

В общем случае, объединяя по n букв, получаем алфавит Sⁿ, содержащий mⁿ n-грамм .

Например, английский алфавит

S ={ABCDEFGH…WXYZ} (1.4)

объемом m=26 букв позволяет сгенерировать посредством операции конкатенации алфавит из 26²=676 биграмм

АА, АВ, …, XZ, ZZ, (1.5)

алфавит из 26³= 17576 триграмм

ААА, ААВ, … , ZZX, ZZZ и т.д. (1.6)

При выполнении криптографических преобразований полезно заменить буквы алфавита целыми числами 0,1,2,3,… . Это позволяет упростить выполнение необходимых алгебраических манипуляций. Например, можно установить взаимно однозначное соответствие между русским алфавитом

S_pyc = {АБВГДЕ … ЮЯ} (1.7)

и множеством целых

; (1.8)

между английским алфавитом

S_англ= {ABCDEF…YZ} (1.9)

и множеством целых

(1.10)

(см. табл. 2.1 и 2.2).

В дальнейшем будет обычно использоваться алфавит

, (1.11)

содержащий m «букв» (в виде чисел).

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

Таблица 1.1. Соответствие между русским алфавитом и множеством целых

Буква	Число	Буква	Число	Буква	Число	Буква	Число
А	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	О	14	Ц	22	Ю	30
З	7	П	15	Ч	23	Я	31

Таблица 1.2. Соответствие между английским алфавитом и множеством целых

Буква	Число	Буква	Число	Буква	Число
А	0	J	9	S	18
В	1	К	10	T	19
С	2	L	11	U	20
D	3	М	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 буквами из алфавита можно рассматривать как n-грамму , где , 0 ? i < n, для некоторого целого n=1,2,3,… .

Через будем обозначать множество n-грамм, образованных из букв множества .

Криптографическое преобразование Е представляет собой совокупность преобразований

Е = {Е ⁽ⁿ⁾: 1 ? n < ?}, (1.12)

(1.13)

Преобразование Е⁽ⁿ⁾ определяет, как каждая n-грамма открытого текста заменяется n-граммой шифртекста , т.е. , причем , при этом обязательным является требование взаимной однозначности преобразования Е⁽ⁿ⁾ на множестве .

Криптографическая система может трактоваться как семейство криптографических преобразований

, (1.14)

помеченных параметром К, называемым ключом.

Множество значений ключа образует ключевое пространство .

Далее рассматриваются традиционные (классические) методы шифрования, отличающиеся симметричной функцией шифрования. К ним относятся шифры перестановки, шифры простой и сложной замены, а также некоторые их модификации и комбинации. Следует отметить, что комбинации шифров перестановок и шифров замены образуют все многообразие применяемых на практике симметричных шифров.

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

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

О важности информации в современном мире наиболее показательно свидетельствуют следующие факты:

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

· Во-вторых, сложилась и необычайно окрепла индустрия информационных услуг - информация стала обыкновенным товаром, то есть объектом купли-продажи. Многие фирмы преуспевают только благодаря тому, что могут получить важные для их деятельности сведения всего на несколько часов или суток раньше своих конкурентов.

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

Особый, нематериальный характер информации делает исключительно легким ее копирование и модифицирование, в силу чего она становится соблазнительным объектом различного рода злоупотреблений. Кроме того, довольно типичной является ситуация, когда нужную кому-либо информацию ее владельцы не согласились бы продать ни за какие деньги, и единственный способ ее получить - это украсть. Указанные причины привели к возникновению целой отрасли человеческой деятельности, основное назначение которой - добывать информацию любыми возможными и невозможными способами, - конечно же, речь идет о разведке. Профессия шпиона наряду с другими, прекрасно всем известными, является одной из древнейших на планете. С другой стороны, статистика неумолимо свидетельствует, что все большая доля всех преступлений совершается в сфере информационных технологий “белыми” и “синими воротничками”, использующими “бреши” информационных систем в своих корыстных целях. Действительно, сейчас, чтобы ограбить банк, не нужно бульдозером проламывать стены хранилищ и резать автогеном сейфы, достаточно узнать код, управляющий доступом к одному из банковских счетов. Все, что для этого требуется, - это компьютер и доступ к банковской сети, ну и конечно, некоторое количество серого вещества в черепной коробке. Прискорбно, но факт - число преступлений с использованием “высоких технологий” растет быстрыми темпами.

Высокая уязвимость информационных технологий к различным злоумышленным действиям породила острую необходимость в средствах противодействия этому, что привело к возникновению и развитию области защиты информации (ЗИ) как неотъемлемой части информационной индустрии. Древнейшей задачей сферы ЗИ является защита передаваемых сообщений от несанкционированного ознакомления с их содержимым, имеются свидетельства понимания людьми этой проблемы еще в древнем Египте и Вавилоне. Информация о способах ее решения в античном мире дошла до нас в виде ссылок на так называемый “код Цезаря” - простейший шифр, применяемый сначала Юлием Цезарем, а впоследствии и другими римскими императорами, для защиты своей переписки от излишне любопытных глаз. Однако вплоть до современности тайнопись была не ремеслом, а искусством, и как наука, криптография сложилась лишь в настоящем веке. Но еще долгое время после этого шифровальные отделы были исключительной прерогативой дипломатических и разведывательных служб, ситуация кардинально изменилась только в последние десятилетия.

В настоящее время понятие “защита информации” (ЗИ) объединяет в себе множество самых различных значений - от резервирования питания для защиты информации от разрушения при возможных сбоях в питающей сети и охранников в дверях компьютерного зала, препятствующих входу посторонних лиц и выносу сотрудниками носителей информации, до генераторов помех, “глушащих” уносящие информацию излучения. Из всего многообразия методов ЗИ нас с вами интересуют лишь те, которые никак не связаны с характеристиками ее материальных носителей, а основаны на манипулировании самой информацией и используют лишь ее имманентные свойства. Эти методы относятся к ведению криптографии, которая переживает сейчас настоящий бум. На сегодняшний день известно большое количество задач, относящихся к сфере ЗИ, - такое обилие обусловлено тем, что информационные взаимодействия, развиваясь, приобретают все более сложный характер, соответственно становятся более разнообразными и изощренными угрозы в их сторону, а это в свою очередь приводит к возникновению новых задач. Если раньше все потребности в защите информации сводились к обеспечению секретности и подлинности передаваемых сообщений, то есть к их защите от чтения и внесения изменений посторонними лицами, то сейчас актуально гораздо большее число проблем. Среди новых задач можно отметить лишь две, наиболее известные: рассылка секретных ключей по незащищенным каналам связи (открытое распределение ключей) и подтверждение авторства сообщений (цифровая подпись). А ведь существует большое количество менее известных, но не менее важных задач ЗИ.

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

В данной работе для шифрования цифровых данных телефонной сети общего пользования мы рассмотрим алгоритм DES, и докажем его криптостойкость.

2. Шифры простой замены

При шифровании заменой (подстановкой) символы шифруемого текста заменяются символами того же или другого алфавита с заранее установленным правилом замены. В шифре простой замены каждый символ исходного текста заменяется символами того же алфавита одинаково на всем протяжении текста. Часто шифры простой замены называют шифрами одноалфавитной подстановки.

Полибианский квадрат

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

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

Концепция полибианского квадрата оказалась плодотворной и нашла применение в криптосистемах последующего времени.

Система шифрования Цезаря

Шифр Цезаря является частным случаем шифра простой замены (одноалфавитной подстановки). Свое название этот шифр получил по имени римского императора Гая Юлия Цезаря, который использовал этот шифр при переписке с Цицероном (около 50 г. до н.э.).

При шифровании исходного текста каждая буква заменялась на другую букву того же алфавита по следующему правилу. Заменяющая буква определялась путем смещения по алфавиту от исходной буквы на К букв. При достижении конца алфавита выполнялся циклический переход к его началу. Цезарь использовал шифр замены при смещении К = 3. Такой шифр замены можно задать таблицей подстановок, содержащей соответствующие пары букв открытого текста и шифртекста. Совокупность возможных подстановок для К=3 показана в табл. 2.

Таблица 2 Одноалфавитные подстановки (К = 3, m = 26)

A ? D	J ? M	S?? V
B ? E	K ? N	T?? W
С?? F	L ? O	U ? X
D?? G	M ? P	V?? Y
Е?? H	N ? Q	W?? Z
F ? I	O ? R	X?? A
G?? J	P ? S	Y?? B
Н?? K	Q ? T	Z?? C
I?? L	R ? U

Например, послание Цезаря VENI VIDI VICI

(в переводе на русский означает "Пришел, Увидел, Победил"), направленное его другу Аминтию после победы над понтийским царем Фарнаком, сыном Митридата, выглядело бы в зашифрованном виде так: YHQL YLGL YLFL

Выполним математический анализ шифра простой замены (подстановки) на основе понятий, введенных в начале главы.

Симметричная группа () обладает следующими свойствами:

1.Замкнутость.

2.Ассоциативность. Оба способа заключения в скобки произведения подстановок дают одинаковый результат.

3.Существование единичного элемента. Подстановка является единственным единичным элементом группы () по умножению для всех ().

4. Существование обратных элементов. Для каждой подстановки имеется взаимно однозначно определенная обратная подстановка.

Указанные свойства являются аксиомами группы. Ключ К подстановки для алфавита представляет собой последовательность элементов симметричной группы из :

Подстановка, определяемая ключом К, является криптографическим преобразованием Е_К, которое шифрует n-грамму

(x₀, x₁, x₂, ..., x_n-1) (3.8)

открытого текста в n-грамму

(y₀, y₁, y₂, ..., y_n-1) (3.9)

шифртекста, где y _i = ?_i ( x_i), 0 ? i < n, (3.10)

для каждого n, n = 1, 2, 3, ... .

Криптографическое преобразование Ек называется одно-алфавитной подстановкой, если значение ?_i одинаково для каждого i, i = 0,1,2,...; в противном случае преобразование Ек называется многоалфавитной подстановкой.

На рис.2 представлена схема реализации подстановки Ек.



Рис. 2. Схема подстановки Ек

Отметим характерные особенности подстановки Е_К:

* открытый текст шифруется побуквенно (буква за буквой);

* i-я буква y _i шифртекста является функцией только i-й компоненты ?_i ключа К и i-й буквы х_i открытого текста;

* шифрование n-граммы (x₀,x₁,x₂,...,x_n-1) производится в соответствии с формулой

(y₀,y₁,y₂,...,y_n-1) = Е_К (x ₀,x ₁,x₂,...,x_n-1) (3.11)

Система Цезаря представляет собой одноалфавитную подстановку, которая шифрует n-грамму (x₀,x₁,x₂,...,x_n-1) открытого текста в n-грамму (y₀,y₁,y₂,...,y_n-1) шифртекста согласно следующему правилу:

y _i = Е_К (х_i), 0 ? i < n, (3.12)

Е_К : j ? (j + К) (mod n), 0 ? К < m, (3.13)

где j - числовой код буквы открытого текста; j + К - числовой код соответствующей буквы шифртекста.

В отличие от шифра Цезаря, описанного в начале этого подраздела, система шифрования Цезаря образует по существу семейство одноалфавитных подстановок для выбираемых значений ключа К, причем 0 ? К < m.

Достоинством системы шифрования Цезаря является простота шифрования и расшифрования. К недостаткам системы Цезаря следует отнести следующие:

* подстановки, выполняемые в соответствии с системой Цезаря, не маскируют частот появления различных букв исходного открытого текста;

* сохраняется алфавитный порядок в последовательности заменяющих букв; при изменении значения К изменяются только начальные позиции такой последовательности;

* число возможных ключей К мало;

* шифр Цезаря легко вскрывается на основе анализа частот появления букв в шифртексте.

Криптоаналитическая атака против системы одноалфавитной замены начинается с подсчета частот появления символов: определяется число появлений каждой буквы в шифртексте. Затем полученное распределение частот букв в шифртексте сравнивается с распределением частот букв в алфавите исходных сообщений, например в английском. Буква с наивысшей частотой появления в шифртексте заменяется на букву с наивысшей частотой появления в английском языке и т.д. Вероятность успешного вскрытия системы шифрования повышается с увеличением длины шифртекста.

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

Аффинная система подстановок Цезаря 

В системе шифрования Цезаря использовались только аддитивные свойства множества целых . Однако символы множества можно также умножать по модулю m. Применяя одновременно операции сложения и умножения по модулю m над элементами множества , можно получить систему подстановок, которую называют аффинной системой подстановок Цезаря.

Определим преобразование в такой системе:

(3.14)

(3.15)

(3.16)

где а,b - целые числа, 0 ? a,b < m, НОД (a,m) = 1.

В данном преобразовании буква, соответствующая числу t, заменяется на букву, соответствующую числовому значению (at+b) по модулю m.

Следует заметить, что преобразование E_a,b(t) является взаимно однозначным отображением на множестве Z_m только в том случае, если наибольший общий делитель чисел а и 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

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

А

B

C

D

Е

F

Q

Н

I

J

К

L

М

N

0

Р

Q

R

S

T

U

V

W

Х

Y

Z

F

I

L

O

R

U

Х

А

D

Q

J

М

Р

S

V

Y

В

Е

Н

K

N

Q

Т

W

Z

C

Исходное сообщение HOPE преобразуется в шифртекст AVYR

Достоинством аффинной системы является удобное управление ключами - ключи шифрования и расшифрования представляются в компактной форме в виде пары чисел (а, b). Недостатки аффинной системы аналогичны недостаткам системы шифрования Цезаря.

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

Система Цезаря с ключевым словом 

Система шифрования Цезаря с ключевым словом является одноалфавитной системой подстановки. Особенностью этой системы является использование ключевого слова для смещения и изменения порядка символов в алфавите подстановки.

Выберем некоторое число k, 0 ? k < 25, и слово или короткую фразу в качестве ключевого слова. Желательно, чтобы все буквы ключевого слова были различными. Пусть выбраны слово DIPLOMAT в качестве ключевого слова и число k = 5.

Ключевое слово записывается под буквами алфавита, начиная с буквы, числовой код которой совпадает с выбранным числом k:

0

1

2

3

4

5

10

15

20

25

А

B

C

D

Е

F

Q

Н

I

J

К

L

М

N

0

Р

Q

R

S

T

U

V

W

Х

Y

Z

D

I

P

L

O

M

A

T

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

5

А

B

C

D

Е

F

Q

Н

I

J

К

L

М

N

0

Р

Q

R

S

T

U

V

W

Х

Y

Z

V

W

Х

Y

Z

D

I

P

L

O

M

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 г. аббат из Германии Иоганн Трисемус написал печатную работу по криптологии под названием "Полиграфия". В этой книге он впервые систематически описал применение шифрующих таблиц, заполненных алфавитом в случайном порядке. Для получения такого шифра замены обычно использовались таблица для записи букв алфавита и ключевое слово (или фраза). В таблицу сначала вписывалось по строкам ключевое слово, причем повторяющиеся буквы отбрасывались. Затем эта таблица дополнялась не вошедшими в нее буквами алфавита по порядку.

Поскольку ключевое слово или фразу легко хранить в памяти, то такой подход упрощал процессы шифрования и расшифрования. Поясним этот метод шифрования на примере. Для русского алфавита шифрующая таблица может иметь размер 4х8. Выберем в качестве ключа слово БАНДЕРОЛЬ. Шифрующая таблица с таким ключом показана на рис. 3.

Б	А	Н	Д	Е	Р	О	Л
Ь	В	Г	Ж	3	И	Й	К
М	П	С	Т	У	Ф	Х	Ц
Ч	Ш	Щ	Ы	Ъ	Э	Ю	Я

Рис. 3. Шифрующая таблица с ключевым словом БАНДЕРОЛЬ

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

Например, при шифровании с помощью этой таблицы сообщения ВЫЛЕТАЕМПЯТОГО получаем шифртекст ПДКЗЫВЗЧШЛЫЙСЙ

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

Биграммный шифр Плейфейра 

Шифр Плейфейра, изобретенный в 1854 г., является наиболее известным биграммным шифром замены. Он применялся Великобританией во время первой мировой войны. Основой шифра Плейфейра является шифрующая таблица со случайно расположенными буквами алфавита исходных сообщений.

Для удобства запоминания шифрующей таблицы отправителем и получателем сообщений можно использовать ключевое слово (или фразу) при заполнении начальных строк таблицы. В целом структура шифрующей таблицы системы Плейфейра полностью аналогична структуре шифрующей таблицы Трисемуса. Поэтому для пояснения процедур шифрования и расшифрования в системе Плейфейра воспользуемся шифрующей таблицей Трисемуса из предыдущего раздела (см. рис 3).

Процедура шифрования включает следующие шаги:

1. Открытый текст исходного сообщения разбивается на пары букв (биграммы). Текст должен иметь четное количество букв и в нем не должно быть биграмм, содержащих две одинаковые буквы. Если эти требования не выполнены, то текст модифицируется даже из-за незначительных орфографических ошибок.

2. Последовательность биграмм открытого текста преобразуется с помощью шифрующей таблицы в последовательность биграмм шифртекста по следующим правилам:

2а. Если обе буквы биграммы открытого текста не попадают на одну строку или столбец (как, например, буквы А и Й в табл. на рис.8), тогда находят буквы в углах прямоугольника, определяемого данной парой букв. (В нашем примере это буквы АЙОВ. Пара букв АЙ отображается в пару 0В. Последовательность букв в биграмме шифртекста должна быть зеркально расположенной по отношению к последовательности букв в биграмме открытого текста).

2б. Если обе буквы биграммы открытого текста принадлежат одному столбцу таблицы, то буквами шифртекста считаются буквы, которые лежат под ними. (Например, биграмма НС дает биграмму шифртекста ГЩ.) Если при этом буква открытого текста находится в нижней строке, то для шифртекста берется соответствующая буква из верхней строки того же столбца. (Например, биграмма ВШ дает биграмму шифртекста ПА.)

2в. Если обе буквы биграммы открытого текста принадлежат одной строке таблицы, то буквами шифртекста считаются буквы, которые лежат справа от них. (Например, биграмма НО дает биграмму шифртекста ДЛ.) Если при этом буква открытого текста находится в крайнем правом столбце, то для шифра берут соответствующую букву из левого столбца в той же строке. (Например, биграмма ФЦ дает биграмму шифртекста ХМ.).

Зашифруем текст ВСЕ ТАЙНОЕ СТАНЕТ ЯВНЫМ

Разбиение этого текста на биграммы дает ВС ЕТ АЙ НО ЕС ТА НЕ ТЯ ВН ЫМ

Данная последовательность биграмм открытого текста преобразуется с помощью шифрующей таблицы (см. рис.3) в следующую последовательность биграмм шифртекста ГП ДУ ОВ ДЛ НУ ПД ДР ЦЫ ГА ЧТ

При расшифровании применяется обратный порядок действий.

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

Криптосистема Хилла

Алгебраический метод, обобщающий аффинную подстановку Цезаря

(3.17)

(3.18)

для определения n-грамм, был сформулирован Лестером С.Хиллом.

Множество целых , для которого определены операции сложения, вычитания и умножения по модулю m, является примером кольца. Кольцо R представляет собой алгебраическую систему, в которой определены операции сложения, вычитания и умножения пар элементов. Эта алгебраическая система обладает рядом свойств:

* элементы кольца R образуют коммутативную группу относительно операции сложения; кроме того, существуют единичный и обратный элементы относительно операции сложения;

* умножение и сложение удовлетворяют ассоциативному и дистрибутивному законам.

Мультипликативное обратное a^-1 элемента a кольца может существовать не всегда. Например, если модуль m = 26, то значения 2^-1(mod 26) и 13^-l(mod 26) не могут существовать.

* Если модуль m является простым числом p, то существует обратная величина любого ненулевого элемента t из (при m = p), поскольку значения t (mod m), 2t (mod m), 3t (mod m),.... (p-1) t (mod m) различаются, если 1 ? t ? p-1.

Множество , где p - простое число, является примером алгебраической системы, называемой конечным полем. Ненулевые элементы образуют мультипликативную группу.

Множество всех n-грамм с компонентами из кольца образует векторное пространство над кольцом . Каждая n-грамма называется вектором. В векторном пространстве для векторов определены операции сложения и вычитания по модулю n, а также скалярное умножение вектора на элемент t кольца . Сложение и скалярное умножение являются операциями, удовлетворяющими коммутативному, ассоциативному и дистрибутивному законам. Вектор является линейной комбинацией векторов 0 ? i ? L если

(3.19)

Линейное преобразование является отображением:

, (3.20)

, (3.21)

которое удовлетворяет условию линейности

(3.22)

для всех s, t в и в .

Линейное преобразование может быть представлено матрицей размером nхn вида

, (3.23)

причем

(3.24)

(3.25)

Базисом для векторного пространства является набор векторов из которые линейно независимы и порождают . Каждый базис для содержит n линейно независимых векторов. Любой набор из n векторов, которые линейно независимы над является базисом.

Пусть является линейным преобразованием, описываемым матрицей (3.23), причем

(3.26)

Если векторы линейно независимы над , тогда их образы линейно независимы над только в том случае, если определитель матрицы , обозначаемый как , не делится на любое простое p , которое делит m. В этом случае преобразование называется обратимым (или невырожденным) линейным преобразованием, имеющим обратное преобразование :

, (3.27)

, (3.28)

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

Например, когда m=26 и матрица преобразования

(3.29)

то определитель этой матрицы

, (3.30)

. (3.31)

Поэтому существует обратное преобразование . Нетрудно убедиться, что

(3.32)

удовлетворяет соотношению

(3.33)

Пусть является линейным преобразованием на с матрицей

. (3.34)

Используем это преобразование для определения биграммной подстановки в английском алфавите {ABCDEFGH…XYZ}.

Сначала разобьем n-грамму открытого текста на биграммы, причем выберем n кратным 2, например, 12-грамма PAYMOREMONEY делится на шесть биграмм: PA YM OR ЕМ ON EY

Затем в каждой биграмме открытого текста заменим каждую букву ее числовым эквивалентом из таблицы:

Преобразование биграмм открытого текста в биграммы шифртекста осуществляется в соответствии с уравнением

(3.35)

(3.36)

где и - вектор-столбцы биграмм шифртекста и открытого текста соответственно.

Получаем



(3.37)

Заменяя в биграммах шифртекста числа на соответствующие буквы согласно табл.1.2, получаем 12-грамму шифртекста: ТЕ ЕЕ PJ WQ DP GY

Для расшифрования биграмм шифртекста и восстановления биграмм открытого текста необходимо выполнить обратное преобразование согласно уравнению . В рассмотренном примере матрицы преобразования имели размер 2х2 и шифровались биграммы (пары) букв. Хотя буква Е может быть зашифрована по-разному в различных парах исходного сообщения, одна и та же пара, например ЕМ, будет шифроваться всегда одинаково на протяжении всего исходного текста.

Система Хилла является одноалфавитной в широком смысле слова.

Система омофонов

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

Данные о распределениях вероятностей букв в русском и английском текстах приведены в табл.4 и 5. Буквы в таблицах указаны в порядке убывания вероятности их появления в тексте. Например, русская буква Е встречается в 36 раз чаще, чем буква Ф, а английская буква Е встречается в 123 раза чаще, чем буква Z.

Шифруя букву исходного сообщения, выбирают случайным образом одну из ее замен. Замены (часто называемые омофонами) могут быть представлены трехразрядными числами от 000 до 999. Например, в английском алфавите букве Е присваиваются 123 случайных номера, буквам В и G - по 16 номеров, а буквам J и Z - по 1 номеру. Если омофоны (замены) присваиваются случайным образом различным появлениям одной и той же буквы, тогда каждый омофон появляется в шифртексте равновероятно. 

Таблица 3. Распределение вероятностей букв в русских текстах

Буква	Вероятность	Буква	Вероятность	Буква	Вероятность	Буква	Вероятность
Пробел	0,175	Р	0,040	Я	0,018	X	0,009
О	0,090	В	0,038	Ы	0.016	Ж	0,007
Е	0,072	Л	0,035	3	0,016	Ю	0,006
А	0,062	K	0,028	Ъ	0,014	Ш	0,006
И	0,062	M	0,026	Б	0,014	Ц	0,004
Н	0,053	Д	0,025	Г	0,013	Щ	0,003
Т	0,053	П	0,023	Ч	0,012	Э	0,003
C	0,045	У	0,021	Й	0,010	Ф	0,002

Таблица 4. Распределение вероятностей букв в английских текстах

Буква	Вероятность	Буква	Вероятность	Буква	Вероятность
Е	0,123	L	0,040	В	0,016
Т	0,096	D	0,036	G	0,016
А	0,081	С	0,032	V	0,009
O	0,079	U	0,031	К	0,005
N	0,072	Р	0,023	Q	0,002
I	0,071	F	0,023	X	0,002
S	0,066	М	0,022	J	0,001
R	0,060	W	0,020	Z	0,001
Н	0,051	Y	0,019

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

3. Шифры сложной замены

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

При r-алфавитной подстановке символ x₀ исходного сообщения заменяется символом y₀ из алфавита В₀, символ x₁ -символом y₁ из алфавита B₁, и так далее, символ x_r-1 заменяется символом y_r-1 из алфавита B_r-1, символ x_r заменяется символом y_r снова из алфавита В_о, и т.д.

Общая схема многоалфавитной подстановки для случая г = 4 показана на рис. 4.

Входной символ:	X0	X1	X2	X3	X4	X5	X6	X7	X8	X9
Алфавит подстановки:	В0	B1	B2	В3	В0	B1	B2	В3	В0	B1

Рис. 4. Схема г-алфавитной подстановки для случая г = 4

Эффект использования многоалфавитной подстановки заключается в том, что обеспечивается маскировка естественной статистики исходного языка, так как конкретный символ из исходного алфавита А может быть преобразован в несколько различных символов шифровальных алфавитов В_j. Степень обеспечиваемой защиты теоретически пропорциональна длине периода г в последовательности используемых алфавитов В_j.

Многоалфавитные шифры замены предложил и ввел в практику криптографии Леон Батист Альберти, который также был известным архитектором и теоретиком искусства. Его книга "Трактат о шифре", написанная в 1566 г., представляла собой первый в Европе научный труд по криптологии. Кроме шифра многоалфавитной замены, Альберти также подробно описал устройства из вращающихся колес для его реализации. Криптологи всего мира почитают Л.Альберти основоположником криптологии.

Шифр Гронсфельда

Этот шифр сложной замены, называемый шифром Гронсфельда, представляет собой модификацию шифра Цезаря числовым ключом. Для этого под буквами исходного сообщения записывают цифры числового ключа. Если ключ короче сообщения, то его запись циклически повторяют. Шифртекст получают примерно, как в шифре Цезаря, но отсчитывают по алфавиту не третью букву (как это делается в шифре Цезаря), а выбирают ту букву, которая смещена по алфавиту на соответствующую цифру ключа. Например, применяя в качестве ключа группу из четырех начальных цифр числа e (основания натуральных логарифмов), а именно 2718, получаем для исходного сообщения ВОСТОЧНЫЙ ЭКСПРЕСС следующий шифртекст:

Сообщение

В

О

С

Т

О

Ч

Н

Ы

Й

Э

К

С

П

Р

Е

С

С

Ключ

2

7

1

8

2

7

1

8

2

7

1

8

2

7

1

8

2

Шифртекст

Д

Х

Т

Ь

Р

Ю

О

Г

Л

Д

Л

Щ

С

Ч

Ж

Щ

У

Чтобы зашифровать первую букву сообщения В, используя первую цифру ключа 2 , нужно отсчитать вторую по порядку букву от В в алфавите

В	Г	Д
	1	2

получается первая буква шифр-текста Д.

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

Шифр Гронсфельда представляет собой по существу частный случай системы шифрования Вижинера.

Система шифрования Вижинера

Система Вижинера впервые была опубликована в 1586 г. и является одной из старейших и наиболее известных многоалфавитных систем. Свое название она получила по имени французского дипломата XVI века Блеза Вижинера, который развивал и совершенствовал криптографические системы. Система Вижинера подобна такой системе шифрования Цезаря, у которой ключ подстановки меняется от буквы к букве. Этот шифр многоалфавитной замены можно описать таблицей шифрования, называемой таблицей (квадратом) Вижинера. На рис.5 и 6 показаны таблицы Вижинера для русского и английского алфавитов соответственно. Таблица Вижинера используется для зашифрования и расшифрования. Таблица имеет два входа:

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

* крайний левый столбец ключа.

Последовательность ключей обычно получают из числовых значений букв ключевого слова.

При шифровании исходного сообщения его выписывают в строку, а под ним записывают ключевое слово (или фразу). Если ключ оказался короче сообщения, то его циклически повторяют. В процессе шифрования находят в верхней строке таблицы очередную букву исходного текста и в левом столбце очередное значение ключа. Очередная буква шифртекста находится на пересечении столбца, определяемого шифруемой буквой, и строки, определяемой числовым значением ключа.

Пусть ключевая последовательность имеет длину r, тогда ключ r-алфавитной подстановки есть r-строка

(4.1)

Система шифрования Вижинера преобразует открытый текст в шифртекст с помощью ключа согласно правилу

(4.2)

(4.3)

Рис. 5. Таблица Вижинера для русского алфавита



Рис. 6. Таблица Вижинера для английского алфавита

Рассмотрим пример получения шифртекста с помощью таблицы Вижинера. Пусть выбрано ключевое слово АМБРОЗИЯ. Необходимо зашифровать сообщение ПРИЛЕТАЮ СЕДЬМОГО.

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

Сообщение

П

Р

И

Л

Е

Т

А

Ю

С

Е

Д

Ь

М

О

Г

О

Ключ

А

М

Б

Р

О

З

И

Я

А

М

Б

Р

О

З

И

Я

Шифртекст

П

Ъ

Й

Ы

У

Щ

И

Э

С

С

Е

К

Ь

Х

Л

Н

Шифр "двойной квадрат" Уитстона

В 1854 г. англичанин Чарльз Уитстон разработал новый метод шифрования биграммами, который называют "двойным квадратом". Свое название этот шифр получил по аналогии с полибианским квадратом. Шифр Уитстона открыл новый этап в истории развития криптографии. В отличие от полибианского шифр "двойной квадрат" использует сразу две таблицы, размещенные по одной горизонтали, а шифрование идет биграммами, как в шифре Плейфейра. Эти не столь сложные модификации привели к появлению на свет качественно новой криптографической системы ручного шифрования. Шифр "двойной квадрат" оказался очень надежным и удобным и применялся Германией даже в годы второй мировой войны.

Поясним процедуру шифрования этим шифром на примере. Пусть имеются две таблицы со случайно расположенными в них русскими алфавитами (рис.7). Перед шифрованием исходное сообщение разбивают на биграммы. Каждая биграмма шифруется отдельно. Первую букву биграммы находят в левой таблице, а вторую букву - в правой таблице. Затем мысленно строят прямоугольник так, чтобы буквы биграммы лежали в его противоположных вершинах. Другие две вершины этого прямоугольника дают буквы биграммы шифртекста.

Рис. 7. Две таблицы со случайно расположенными символами русского алфавита для шифра "двойной квадрат"

Предположим, что шифруется биграмма исходного текста ИЛ. Буква И находится в столбце 1 и строке 2 левой таблицы. Буква Л находится в столбце 5 и строке 4 правой таблицы. Это означает, что прямоугольник образован строками 2 и 4, а также столбцами 1 левой таблицы и 5 правой таблицы. Следовательно, в биграмму шифртекста входят буква О, расположенная в столбце 5 и строке 2 правой таблицы, и буква В, расположенная в столбце 1 и строке 4 левой таблицы, т.е. получаем биграмму шифртекста 0В.

Если обе буквы биграммы сообщения лежат в одной строке, то и буквы шифртекста берут из этой же строки. Первую букву биграммы шифртекста берут из левой таблицы в столбце, соответствующем второй букве биграммы сообщения. Вторая же буква биграммы шифртекста берется из правой таблицы в столбце, соответствующем первой букве биграммы сообщения. Поэтому биграмма сообщения ТО превращается в биграмму шифртекста ЖБ. Аналогичным образом шифруются все биграммы сообщения:

Сообщение ПР ИЛ ЕТ АЮ _Ш ЕС ТО ГО

Шифртекст ПЕ 0В ЩН ФМ ЕШ РФ БЖ ДЦ

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

Одноразовая система шифрования

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

Одноразовая система шифрует исходный открытый текст

(4.4)

в шифртекст

(4.5)

посредством подстановки Цезаря

, (4.6)

где К_i - i-й элемент случайной ключевой последовательности.

Ключевое пространство одноразовой системы представляет собой набор дискретных случайных величин из и содержит mⁿ значений.

Процедура расшифрования описывается соотношением

, (4.7)

где К_i - i-й элемент той же самой случайной ключевой последовательности.

Одноразовая система изобретена в 1917 г. американцами Дж.Моборном и Г.Вернамом. Для реализации этой системы подстановки иногда используют одноразовый блокнот. Этот блокнот составлен из отрывных страниц, на каждой из которых напечатана таблица со случайными числами (ключами) К_i. Блокнот выполняется в двух экземплярах: один используется отправителем, а другой - получателем. Для каждого символа X_i сообщения используется свой ключ К_i из таблицы только один раз. После того как таблица использована, она должна быть удалена из блокнота и уничтожена. Шифрование нового сообщения начинается с новой страницы.

Этот шифр абсолютно надежен, если набор ключей К_i действительно случаен и непредсказуем. Если криптоаналитик попытается использовать для заданного шифртекста все возможные наборы ключей и восстановить все возможные варианты исходного текста, то они все окажутся равновероятными. Не существует способа выбрать исходный текст, который был действительно послан. Теоретически доказано, что одноразовые системы являются нераскрываемыми системами, поскольку их шифртекст не содержит достаточной информации для восстановления открытого текста.

Казалось бы, что благодаря данному достоинству одноразовые системы следует применять во всех случаях, требующих абсолютной информационной безопасности. Однако возможности применения одноразовой системы ограничены чисто практическими аспектами. Существенным моментом является требование одноразового использования случайной ключевой последовательности. Ключевая последовательность с длиной, не меньшей длины сообщения, должна передаваться получателю сообщения заранее или отдельно по некоторому секретному каналу. Это требование не будет слишком обременительным для передачи действительно важных одноразовых сообщений, например, по горячей линии Вашингтон - Москва. Однако такое требование практически неосуществимо для современных систем обработки информации, где требуется шифровать многие миллионы символов.

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

Шифрование методом Вернама

Система шифрования Вернама является в сущности частным случаем системы шифрования Вижинера при значении модуля m = 2. Конкретная версия этого шифра, предложенная в 1926 г. Гилбертом Вернамом, сотрудником фирмы AT&T США, использует двоичное представление символов исходного текста.

Каждый символ исходного открытого текста из английского алфавита {А, В, С, D, ..., Z}, расширенного шестью вспомогательными символами (пробел, возврат каретки и т.п.), сначала кодировался в 5-битовый блок (b₀, b₁, …, b₄) телеграфного кода Бодо.

Случайная последовательность двоичных ключей k₀,k₁,k₂,... заранее записывалась на бумажной ленте.

Схема передачи сообщений с использованием шифрования методом Вернама показана на рис.8. Шифрование исходного текста, предварительно преобразованного в последовательность двоичных символов x, осуществлялось путем сложения по модулю 2 символов x с последовательностью двоичных ключей k.

Символы шифртекста

y=x Еk (8)

Рис. 8. Схема шифрования и расшифрования сообщений по методу Вернама

Расшифрование состоит в сложении по модулю 2 символов у шифртекста с той же последовательностью ключей k:

y Е k = x Е k Е k = x. (4.8)

При этом последовательности ключей, использованные при шифровании и расшифровании, компенсируют друг друга (при сложении по модулю 2), и в результате восстанавливаются символы x исходного текста.

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

Следует отметить, что метод Вернама не зависит от длины последовательности ключей и, кроме того, он позволяет использовать случайную последовательность ключей. Однако при реализации метода Вернама возникают серьезные проблемы, связанные с необходимостью доставки получателю такой же последовательности ключей, как у отправителя, либо с необходимостью безопасного хранения идентичных последовательностей ключей у отправителя и получателя. Эти недостатки системы шифрования Вернама преодолены при шифровании методом гаммирования.

Роторные машины

В 20-х годах XX века были изобретены электромеханические устройства шифрования, автоматизирующие процесс шифрования. Принцип работы таких машин основан на многоалфавитной замене символов исходного текста по длинному ключу согласно версии шифра Вижинера. Большинство из них - американская машина SIGABA (М-134), английская TYPEX, немецкая ENIGMA, японская PURPLE были роторными машинами.

Главной деталью роторной машины является ротор (или колесо) с проволочными перемычками внутри. Ротор имеет форму диска (размером с хоккейную шайбу). На каждой стороне диска расположены равномерно по окружности m электрических контактов, где m - число знаков алфавита (в случае латинского алфавита m = 26). Каждый контакт на передней стороне диска соединен с одним из контактов на задней стороне, как показано на рис.9. В результате электрический сигнал, представляющий знак, будет переставлен в соответствии с тем, как он проходит через ротор от передней стороны к задней. Например, ротор можно закоммутировать проволочными перемычками для подстановки G вместо A, U вместо В, L вместо С и т.д.