Перестановочные шифры

Размещено на http://www.allbest.ru/

Введение

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

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

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

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

1. Перестановочные шифры

Перестановочный шифр с фиксированным периодом n подразумевает разбиение исходного текста на блоки по n символов и использование для каждого такого блока некоторой перестановки E. Ключом такого шифра является используемая при шифровании перестановочная матрица P или вектор t, указывающий правило перестановки. Таким образом, общее число возможных ключей определяется длиной блока n и равно n!. При дешифрации используется матрица обратной перестановки D, являющаяся обратной к матрице P по умножению, то есть D*P=I, где I - единичная матрица.

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

узкая пергаментная лента наматывалась по спирали на цилиндрическую палочку;

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

Таким образом, длина блока n определялась длиной и диаметром палочки, а само шифрование заключалось в перестановке символов исходного текста в соответствии с длиной окружности палочки. Например, используя палочку, по длине окружности которой помещается 4 символа, а длина палочки позволяет записать 6 символов, исходный текст: «это шифр древней спарты» превратится в шифрограмму: «эфвптрнао ер дйтшр ыиес». Длина блока n = 23, а вектор t, указывающий правило перестановки, для этого шифра может быть записан следующим образом: t = {1, 7, 13, 19, 2, 8, 14, 20, 3, 9, 15, 21, 4, 10, 16, 22, 5, 11, 17, 23, 6, 12, 18}.

1.1 Простой столбцевой перестановочный шифр

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

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

· узкая пергаментная лента наматывалась по спирали на цилиндрическую палочку;

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

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

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

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

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

1.2 Криптоанализ с автоключом

Криптоанализ измененной системы AUTOCLAVE проще, чем для первоначальной. Аналитику достаточно только угадать или найти длину ключа d. Тогда он может взять первую и d+1 буквы из криптотекста. Тогда, по построению, для d+1 буквы ключом является первая, следовательно из квадрата Виженера можно определить букву, стоящую на d+1 месте в открытом тексте. Подобным образом может быть раскрыт весь текст сообщения, кроме первых d букв. Первая версия данной системы, где ключом служит сдвиг исходного сообщения, неуязвима против такой простой криптоатаки.

Для раскрытия первой версии AUTOCLAVE может быть использован метод Казиски. Пусть слово ИЛИ появляется дважды в исходном сообщении и расстояние между этими появлениями равно удвоенному смещению. Тогда найдется последовательность из трех букв, например КАН, расположенная посредине между появлениями ИЛИ. Таким образом, имеется следующая часть исходного сообщения:… ИЛИ… КАН… ИЛИ…

В процессе шифрования получаем: Сообщение … ИЛИ… КАН… ИЛИ…

Автоключ … ИЛИ… КАН…

Шифротекст … ЬЛЩ… ЬЛЩ…

Таким образом, ЬЛЩ появляется дважды в криптотексте и расстояние между ними в точности равно периоду, в то время как для системы Виженера данный метод давал числа лишь кратные периоду. После того, как смещение известно, ключевое слово находится с помощью исчерпывающего поиска, основанного на подсчете частот индивидуальных букв. При получении ключевого слова все становится очевидным. Имеется n возможных набором для первой буквы ключевого слова. Когда этот выбор произведен, из него определяется первая буква сообщения, которая в свою очередь, определяет d+1, и так далее. Поэтому выбор первой буквы дает 1, d+1, 2d+1,… буквы сообщения. Варианты, приводящие к последовательностям невозможных распределений, могут быть отброшены. Таки способом находится первая буква. Остальные d-1 букв определяются аналогично.

1.3 Блочные шифры

Блочный шифр - разновидность симметричного шифра, оперирующего группами бит фиксированной длины - блоками, характерный размер которых меняется в пределах 64 - 256 бит. Если исходный текст (или его остаток) меньше размера блока, перед шифрованием его дополняют. Фактически, блочный шифр представляет собой подстановку на алфавите блоков, которая, как следствие, может быть моно- или полиалфавитной. Блочный шифр является важной компонентой многих криптографических протоколов и широко используется для защиты данных, передаваемых по сети.

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

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

Режим электронной шифровальной книги. Режим электронной шифровальной книги (electronic codebook, ECB) - это наиболее очевидный способ использовать блочный шифр: блок открытого текста заменяется блоком шифротекста. Так как один и тот же блок открытого текста заменяется одним и тем же блоком шифротекста, то теоретически возможно создать шифровальную книгу блоков открытого текста и соответствующих шифротекстов. Однако, если размер блока - 64 бита, то кодовая книга будет состоять из 264 записей - слишком много для предварительного вычисления и хранения. И не забывайте, для каждого ключа понадобится отдельная шифровальная книга.

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

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

Если криптоаналитик знает, что блок открытого текста «5е081Ьс5» при шифровании превращается в блок шифротекста «7еа593а4,» то он может мгновенно расшифровать этот блок шифротекста, в каком-бы другом с сообщении он не появился. Если в шифрованном сообщении много повторов, которые имеют тенденцию занимать одинаковое место в различных сообщениях, криптоаналитик может получить много информации. Он может попытаться статистически вскрыть используемый открытый текст, независимо от силы блочного шифра.

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

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

Набивка. Большинство сообщений точно не делятся на 64-битные (или любого другого размера) блоки шифрования, в конце обычно оказывается укороченный блок. ЕСВ требует использовать 64-битные блоки. Способом решения этой проблемы является набивка.

Последний блок дополняется (набивается) некоторым регулярным шаблоном - нулями, единицами, чередующимися нулями и единицами - для получения полного блока. При необходимости удалить набивку после дешифрирования запишите количество байтов набивки в последний байт последнего блока. Например, пусть размер блока - 64 бита, и последний блок состоит из 3 байтов (24 бит). Для дополнения блока до 64 бит требуется пять байтов, добавьте четыре байта нулей и последний байт с числом 5. После дешифрирования удалите последние 5 байтов последнего расшифрованного блока. Чтобы этот метод работал правильно, каждое сообщение должно быть дополнено. Даже если открытый текст содержит целое число блоков, вам придется добавить один полный блок. С другой стороны, можно использовать символ конца файла для обозначения последнего байта открытого текста и дополнить этот символ ег.

Р «_] - последний полный блок открытого текста, а Р» - последний, короткий блок открытого текста. С «_; - последний полный блок шифротекста, и С» - последний, короткий блок шифротекста. С' - это промежуточный результат, не являющийся ч а-стью переданного шифротекста.

1.4 Режим сцепления блоков шифра

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

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

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

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

2. Подстановочные шифры

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

2.1 Одноалфавитные шифры

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

В шифре Цезаря каждая буква замещается на букву, находящуюся k символами правее по модулю равному количеству букв в алфавите. (Согласно Светонию у Цезаря k=3 n=50)

Ck(j)=(j+k) (mod n),

n - количество букв в алфавите;

Очевидно, что обратной подстановкой является:

Ck-1 (j)=Сn-k=(j+n-k) (mod n);

Аффинная криптосистема. Обобщением системы Цезаря является аффинная криптосистема. Она определяется двум числами a и b, где 0<=a, b<=n-1. n - как и раньше, является мощностью алфавита. Числа a и n должны быть взаимно просты.

Соответствующими заменами являются:

Aa, b(j)=(a*j+b) (mod n)

A-1a, b(j)=(j-b)*a-1 (mod n)

Обратную замену также можно получить, просто поменяв местами строки в таблице замен.

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

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

Каждая буква может быть представлена парой букв, указывающих строку и столбец, в которых расположена данная буква. Так представления букв В, Г, П, У будут АВ, АГ, ВГ, ГБ соответственно, а сообщение ПРИКЛАДНАЯ МАТЕМАТИКА зашифруется как:

ВГВДБВБДБЕАААДВБААЕБ ЕЕВАААГААЕВАААГАБВБДААЕЕ.

Шифр Цезаря с ключевым словом. В данной разновидности шифра Цезаря ключ задается числом k (0<=k<=n-1) и коротким ключевым словом или предложением. Выписывается алфавит, а под ним, начиная с k-й позиции, ключевое слово. Оставшиеся буквы записываются в алфавитном порядке после ключевого слова. В итоге мы получаем подстановку для каждой буквы. Требование, чтобы все буквы ключевого слова были различными не обязательно - можно записывать ключевое слово без повторения одинаковых букв. Количество ключей в системе Цезаря с ключевым словом равно n!.

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

Более эффективны обобщения подстановки Цезаря - шифр Хилла(Hill) и шифр Плэйфер (Playfair, в переводе «честная игра»). Они основаны на подстановке не отдельных символов, а 2-грамм (шифр Плэйфер) или n-грамм (шифр Хилла). При более высокой криптостойкости они значительно сложнее для реализации и требуют достаточно большого количества ключевой информации.

Метод вскрытия одноалфавитных систем. При своей простоте в реализации одноалфавитные системы легко уязвимы. Определим количество различных систем в аффинной системе. Каждый ключ полностью определен парой целых чисел a и b, задающих отображение ax+b. Для а существует j(n) возможных значений, где j(n) - функция Эйлера, возвращающая количество взаимно простых чисел с n, и n значений для b, которые могут быть использованы независимо от a, за исключением тождественного отображения (a=1 b=0), которое мы рассматривать не будем. Таким образом, получается j(n)*n-1 возможных значений, что не так уж и много: при n=33 в качестве a могут быть 20 значений (1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32), тогда общее число ключей равно 20*33-1=659. Перебор такого количества ключей не составит труда при использовании компьютера. Но существуют методы упрощающие этот поиск и которые могут быть использованы при анализе более сложных шифров.

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

шифр одноалфавитный афинный перестановочный

2.2 Алгоритм шифрования информации методом Вернама для симметричных систем

Полиалфавитные подстановочные шифры были изобретены Лином Баттистой (Lean Battista) в 1568 году. Основная идея многоалфавитных систем состоит в том, что на протяжении всего текста одна и та же буква может быть зашифрована по-разному. Т.е. замены для буквы выбираются из многих алфавитов в зависимости от положения в тексте. Это является хорошей защитой от простого подсчета частот, так как не существует единой маскировки для каждой буквы в криптотексте. В данных шифрах используются множественные однобуквенные ключи, каждый из которых используется для шифрования одного символа открытого текста. Первым ключом шифруется первый символ открытого текста, вторым - второй, и т.д. После использования всех ключей они повторяются циклически.

Шифр Вернама. Шифр Вернама, или одноразовый блокнот, был изобретен в 1917 году Мейджором Джозефом Моборном (Major Joseph Mauborn) и Гильбертом Вернамом (Gilbert Vernam) из AT&T (American Telephone&Telegraph). В классическом понимании одноразовый блокнот является большой неповторяющейся последовательностью символов ключа, распределенных случайным образом. Первоначально это была одноразовая лента для телетайпов. Отправитель использовал каждый символ ключа для шифрования только одного символа открытого текста. Шифрование представляет собой сложение по модулю n (мощность алфавита) символа открытого текста и символа ключа из одноразового блокнота. Каждый символ ключа используется только один раз и для единственного сообщения, иначе даже если использовать блокнот размером в несколько гигабайт, при получении криптоаналитиком нескольких текстов с перекрывающимися ключами он сможет восстановить исходный текст. Он сдвинет каждую пару шифротекстов относительно друг друга и подсчитает число совпадений в каждой позиции если шифротексты смещены правильно, соотношение совпадений резко возрастет. С этой точки зрения криптоанализ не составит труда. Если же ключ не повторяется и случаен, то криптоаналитик, перехватывает он тексты или нет, всегда имеет одинаковые знания. Случайная ключевая последовательность, сложенная с неслучайным открытым текстом, дает совершенно случайный криптотекст, и никакие вычислительные мощности не смогут это изменить.

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

Главным недостатком данной системы является то, что для каждого бита переданной информации должен быть заранее подготовлен бит ключевой информации, причем эти биты должны быть случайными. При шифровании большого объема данных это является серьезным ограничением. Поэтому данная система используется только для передачи сообщений наивысшей секретности. По слухам «горячая линия» между США и СССР шифровалась с помощью одноразового блокнота. Многие сообщения советских шпионов были зашифрованы с использованием одноразовых блокнотов. Эти сообщения нераскрыты сегодня, и не будут раскрыты никогда если не найдется способа вернуться в прошлое и достать эти блокноты.

Чтобы обойти проблему предварительной передачи секретного ключа большого объема, инженеры и изобретатели придумали много остроумных схем генерации очень длинных потоков псевдослучайных цифр из нескольких коротких потоков в соответствии с некоторым алгоритмом. Получателя шифрованного сообщения при этом необходимо снабдить точно таким же генератором, как и у отправителя. Но такие алгоритмы добавляющих регулярности в шифротекст, обнаружение которых может помочь аналитику дешифровать сообщение. Один из основных методов построения подобных генераторов заключается в использовании двух или более битовых лент, считанные с которых данные побитно складываются для получения «смешанного» потока. Например, простая одноразовая лента может быть заменена двумя циклическими лентами, длины которых являются простыми или взаимно простыми числами. Так как в этом случае длины лент не имеют общих множителей, полученный из них поток имеет период повторения, равный произведению их длин: две ленты, имеющие длину 1000 и 1001 соответственно, дают в результате составной поток с периодом 1000x1001=1001000 цифр. Ленты циркулируют через сумматор, который складывает по модулю два считанные с них цифры. Выход сумматора служит ключом, используемым для зашифрования сообщения. Поэтому важно, чтобы составной поток превышал по длине все вместе взятые сообщения, которые могут быть переданы за разумный период времени. Поскольку побитовый сумматор является линейным устройством, он изначально криптографически слаб, но может быть усилен большим количеством различных способов. Другой способ - указание местонахождения ключа как места в книге, например, Дональд Э. Кнут Искусство Программирования Том 2. Получисленные алгоритмы. Третье издание. стр. 83, 3-й абзац. Все символы, входящие в алфавит, начиная с этого места используются как одноразовый ключ для какого-либо сообщения. Но в данном случае ключ не будет случайным и может быть использована информация о частотах распределения букв.

Как не удивительно, но класс шифров Вернама - единственный класс шифров, для которого может быть доказана (и была доказана Шенноном) невскрываемость в абсолютном смысле этого термина.

Шифр Виженера. Одной из старейших и наиболее известных многоалфавитных криптосистем является система Виженера, названная в честь французского криптографа Блейза Виженера(Vigenere), в М.Н. Аршинов, Л.Е. Садовский Коды и математика данный шифр назван шифром Тритемиуса. Этот метод был впервые опубликован в 1586 году. В данном шифре ключ задается набором из d букв. Такие наборы подписываются с повторением под сообщением, а, затем, полученную последовательность складывают с открытым текстом по модулю n (мощность алфавита). Т.е. получается следующая формула:

Vigd(mi)=(mi+ki mod d) (mod n)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Шифр с автоключом. Дальнейшей модификацией системы Виженера является система шифров с автоключом (auto-key), приписываемая математику XVI в. Дж. Кардано, AUTOCLAVE. Шифрование начинается с помощью «первичного ключа» (который является настоящим ключом в нашем смысле) и продолжается с помощью сообщения или криптограммы, смещенной на длину первичного ключа, затем производится сложение по модулю, равному мощности алфавита. Например:

Сообщение: П Р И В Е Т П Р И М А Т У

Первичный ключ: В Г П У

Автоключ: П Р И В Е Т П Р И

Шифротекст: С У Ч Х Ф В Ч Т Н Ю П В Ы

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

Метод Казиски. Примерно в 1860 г. немецким криптоаналитиком Ф.У. Казиски (Kasisky) был изобретен метод вскрытия систем с неизвестным периодом с помощью обнаружения одинаковых слов в криптотексте. Допустим, слово ЫВАП появляется дважды с 13 буквами между двумя появлениями. Это может быть случайно, а может означать тот факт, что одинаковая часть сообщения зашифрована начиная с той же позиции ключа. Тогда расстояние между двумя Ы равно 16 и кратно длине ключа. поэтому возможная длина ключа равна 2, 4, 8, 16. Когда получается несколько таких предположений о длине ключа, некоторые из которых могут оказаться неправильными, то можно будет сделать верное предположение о длине ключа. Более длинные повторяющиеся слова предпочтительнее. Также преимуществом для криптоаналитика является повторение слов более одного раза.

Заключение

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

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

Список литературы

1) У. Диффи и М.Э. Хеллман. Новые направления в криптографии, 1976

2) Т.Л. Партыка, И.И. Попов. Информационная безопасность. М.: Форум-Инфра, 2007

Размещено на Allbest.ru