<< Предыдущая

стр. 8
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

ет, что прямоугольник образован строками 2 и 4, а также столбцами 1 левой таблицы и 5 правой таб-
лицы. Следовательно, в биграмму шифртекста входят буква О, расположенная в столбце 5 и строке
2 правой таблицы, и буква В, расположенная в столбце 1 и строке 4 левой таблицы, т.е. получаем
биграмму шифртекста ОВ.
Если обе буквы биграммы сообщения лежат в одной строке, то и буквы шифртекста берут из
этой же строки. Первую букву биграммы шифртекста берут из левой таблицы в столбце, соответст-
вующем второй букве биграммы сообщения. Вторая же буква биграммы шифртекста берется из пра-
вой таблицы в столбце, соответствующем первой букве биграммы сообщения. Поэтому би-грамма
сообщения ТО превращается в биграмму шифртекста ЖБ. Аналогичным образом шифруются все
биграммы сообщения:
Сообщение ПР ИЛ ЕТ АЮ _Ш ЕС ТО ГО
Шифртекст ПЕ ОВ ЩН ФМ ЕШ РФ БЖ ДЦ

Шифрование методом "двойного квадрата" дает весьма устойчивый к вскрытию и простой в
применении шифр. Взламывание шифртекста "двойного квадрата" требует больших усилий, при этом
длина сообщения должна быть не менее тридцати строк.
Одноразовая система шифрования
Почти все применяемые на практике шифры характеризуются как условно надежные, по-
скольку они могут быть в принципе раскрыты при наличии неограниченных вычислительных возмож-
ностей. Абсолютно надежные шифры нельзя разрушить даже при использовании неограниченных
вычислительных возможностей. Существует единственный такой шифр, применяемый на практике, –
одноразовая система шифрования. Характерной особенностью одноразовой системы шифрования
является одноразовое использование ключевой последовательности.
Одноразовая система шифрует исходный открытый текст
X = (X0, X1, …, Xn–1)
в шифртекст
Y = (Y0, Y1, …, Yn–1)
посредством подстановки Цезаря
Yi = (Xi + Ki) mod m, 0 ? i < n, (2.11)
где Ki – i -й элемент случайной ключевой последовательности.
Ключевое пространство K одноразовой системы представляет собой набор дискретных слу-
чайных величин из Zm и содержит mn значений.
Процедура расшифрования описывается соотношением
Xi = (Yi – Ki) mod m, (2.12)
где Ki – i-й элемент той же самой случайной ключевой последова-тельности.
Одноразовая система изобретена в 1917 г. американцами Дж.Моборном и Г.Вернамом [113].
Для реализации этой системы подстановки иногда используют одноразовый блокнот. Этот блокнот
составлен из отрывных страниц, на каждой из которых напечатана таблица со случайными числами
(ключами) Ki. Блокнот выполняется в двух экземплярах: один используется отправителем, а другой –
получателем. Для каждого символа Xi сообщения используется свой ключ Ki из таблицы только один
раз. После того как таблица использована, она должна быть удалена из блокнота и уничтожена.
Шифрование нового сообщения начинается с новой страницы.
Этот шифр абсолютно надежен, если набор ключей Ki действительно случаен и непредсказу-
ем. Если криптоаналитик попытается использовать для заданного шифртекста все возможные набо-
ры ключей и восстановить все возможные варианты исходного текста, то они все окажутся равнове-
роятными. Не существует способа выбрать исходный текст, который был действительно послан. Тео-
ретически доказано, что одноразовые системы являются нераскрываемыми системами, поскольку их
шифртекст не содержит достаточной информации для восстановления открытого текста.
Казалось бы, что благодаря данному достоинству одноразовые системы следует применять
во всех случаях, требующих абсолютной информационной безопасности. Однако возможности при-
менения одноразовой системы ограничены чисто практическими аспектами. Существенным момен-
том является требование одноразового использования случайной ключевой последовательности.
Ключевая последовательность с длиной, не меньшей длины сообщения, должна передаваться полу-
чателю сообщения заранее или отдельно по некоторому секретному каналу. Это требование не будет
слишком обременительным для передачи действительно важных одноразовых сообщений, например,
по горячей линии Вашингтон – Москва. Однако такое требование практически неосуществимо для
современных систем обработки информации, где требуется шифровать многие миллионы символов.
В некоторых вариантах одноразового блокнота прибегают к более простому управлению клю-
чевой последовательностью, но это приводит к некоторому снижению надежности шифра. Например,
ключ определяется указанием места в книге, известной отправителю и получателю сообщения. Клю-
чевая последовательность начинается с указанного места этой книги и используется таким же обра-
зом, как в системе Вижинера. Иногда такой шифр называют шифром с бегущим ключом. Управление
ключевой последовательностью в таком варианте шифра намного проще, так как длинная ключевая
последовательность может быть представлена в компактной форме. Но с другой стороны, эти ключи
не будут случайными. Поэтому у криптоаналитика появляется возможность использовать информа-
цию о частотах букв исходного естественного языка.
Шифрование методом Вернама
Система шифрования Вернама является в сущности частным случаем системы шифрования
Вижинера при значении модуля m = 2. Конкретная версия этого шифра, предложенная в 1926 г. Гил-
бертом Вернамом, сотрудником фирмы AT&T США, использует двоичное представление символов
исходного текста.
Каждый символ исходного открытого текста из английского алфавита {A, B, C, D, ..., Z}, рас-
ширенного шестью вспомогательными символами (пробел, возврат каретки и т.п.), сначала кодиро-
вался в 5-битовый блок (b0 , b1,..., b 4 ) телеграфного кода Бодо.
Случайная последовательность двоичных ключей k0, k1, k2, … заранее записывалась на бу-
мажной ленте.
Схема передачи сообщений с использованием шифрования методом Вернама показана на
рис. 2.11. Шифрование исходного текста, предварительно преобразованного в последовательность
двоичных символов x, осуществлялось путем сложения по модулю 2 символов x с последовательно-
стью двоичных ключей k.
Символы шифртекста
y = x ? k. (2.13)
Последовательность
ключей



k k


y=x?k y?k=x
x ? ?
Исходный Шифртекст Восстановленный
ЕK DK
текст текст

Рис. 2.11. Схема шифрования и расшифрования сообщений
по методу Вернама
Расшифрование состоит в сложении по модулю 2 символов у шифртекста с той же последо-
вательностью ключей k:
y ? k = x ? k ? k = x. (2.14)
При этом последовательности ключей, использованные при шифровании и расшифровании,
компенсируют друг друга (при сложении по модулю 2), и в результате восстанавливаются символы x
исходного текста.
При разработке своей системы Вернам проверял ее с помощью закольцованных лент, уста-
новленных на передатчике и приемнике для того, чтобы использовалась одна и та же последова-
тельность ключей.
Следует отметить, что метод Вернама не зависит от длины последовательности ключей и,
кроме того, он позволяет использовать случайную последовательность ключей. Однако при реализа-
ции метода Вернама возникают серьезные проблемы, связанные с необходимостью доставки полу-
чателю такой же последовательности ключей, как у отправителя, либо с необходимостью безопасно-
го хранения идентичных последовательностей ключей у отправителя и получателя. Эти недостатки
системы шифрования Вернама преодолены при шифровании методом гаммирования.




2.5. Шифрование методом гаммирования
Под гаммированием понимают процесс наложения по определенному закону гаммы шифра
на открытые данные. Гамма шифра – это псевдослучайная последовательность, выработанная по
заданному алгоритму для зашифрования открытых данных и расшифрования зашифрованных дан-
ных.
Процесс зашифрования заключается в генерации гаммы шифра и наложении полученной
гаммы на исходный открытый текст обратимым образом, например с использованием операции сло-
жения по модулю 2.
Следует отметить, что перед зашифрованием открытые данные разбивают на блоки Т0(i) оди-
наковой длины, обычно по 64 бита. Гамма шифра вырабатывается в виде последовательности
блоков Гш(i) аналогичной длины.
Уравнение зашифрования можно записать в виде
Тш(i) = Гш(i) ? Т0(i), i = 1 … M, (2.15)
где Тш – i-й блок шифртекста; Гш – i-й блок гаммы шифра; Т0(i) – i-й блок открытого текста; M – ко-
(i) (i)

личество блоков открытого текста.
Процесс расшифрования сводится к повторной генерации гаммы шифра и наложению этой
гаммы на зашифрованные данные. Уравнение расшифрования имеет вид
Т0(i) = Гш(i) ? Тш(i). (2.16)
Получаемый этим методом шифртекст достаточно труден для раскрытия, поскольку теперь
ключ является переменным. По сути дела гамма шифра должна изменяться случайным образом для
каждого шифруемого блока. Если период гаммы превышает длину всего шифруемого текста и зло-
умышленнику неизвестна никакая часть исходного текста, то такой шифр можно раскрыть только пря-
мым перебором всех вариантов ключа. В этом случае криптостойкость шифра определяется длиной
ключа.
Методы генерации псевдослучайных последовательностей чисел
При шифровании методом гаммирования в качестве ключа используется случайная строка
битов, которая объединяется с открытым текстом, также представленным в двоичном виде (напри-
мер, А = 00000, В = 00001, С = 00010 и т.д.), с помощью побитового сложения по модулю 2, и в ре-
зультате получается шифрованный текст. Генерирование непредсказуемых двоичных последова-
тельностей большой длины является одной из важных проблем классической криптографии. Для ре-
шения этой проблемы широко используются генераторы двоичных псевдослучайных
последовательностей.
Генерируемые псевдослучайные ряды чисел часто называют гаммой шифра или просто гам-
мой (по названию буквы ? греческого алфавита, часто используемой в математических формулах
для обозначения случайных величин).
Обычно для генерации последовательности псевдослу-чайных чисел применяют компьютер-
ные программы, которые, хотя и называются генераторами случайных чисел, на самом деле выдают
детерминированные числовые последовательности, которые по своим свойствам очень похожи на
случайные [32].
К криптографически стойкому генератору псевдослучайной последовательности чисел (гаммы
шифра) предъявляются три основных требования:
• период гаммы должен быть достаточно большим для шифрования сообщений различной длины;
• гамма должна быть практически непредсказуемой, что означает невозможность предсказать сле-
дующий бит гаммы, даже если известны тип генератора и предшествующий кусок гаммы;
• генерирование гаммы не должно вызывать больших технических сложностей.
Длина периода гаммы является самой важной характеристикой генератора псевдослучайных
чисел. По окончании периода числа начнут повторяться, и их можно будет предсказать. Требуемая
длина периода гаммы определяется степенью закрытости данных. Чем длиннее ключ, тем труднее
его подобрать. Длина периода гаммы зависит от выбранного алгоритма получения псевдослучайных
чисел.
Второе требование связано со следующей проблемой: как можно достоверно убедиться, что
псевдослучайная гамма конкрет-ного генератора является действительно непредсказуемой? Пока не
существуют такие универсальные и практически проверяемые критерии и методики. Чтобы гамма
считалась непредсказуемой, т.е. истинно случайной, необходимо, чтобы ее период был очень боль-
шим, а различные комбинации битов определенной длины были равномерно распределены по всей
ее длине.
Третье требование обусловливает возможность практической реализации генератора про-
граммным или аппаратным путем с обеспечением необходимого быстродействия.
Один из первых способов генерации псевдослучайных чисел на ЭВМ предложил в 1946 г.
Джон фон Нейман. Суть этого способа состоит в том, что каждое последующее случайное число об-
разуется возведением в квадрат предыдущего числа с отбрасыванием цифр младших и старших раз-
рядов. Однако этот способ оказался ненадежным и от него вскоре отказались.
Из известных процедур генерации последовательности псевдослучайных целых чисел наибо-
лее часто применяется так называемый линейный конгруэнтный генератор. Этот генератор выраба-
тывает последовательность псевдослучайных чисел Y1, Y2, …, Yi–1, Yi, …, используя соотношение
Yi = (a?Yi–1 + b) mod m, (2.17)
где Yi – i-е (текущее) число последовательности; Yi–1 – предыдущее число последовательности; a,b и
m – константы; m – модуль; a – множитель (коэффициент); b – приращение; Y0 – порождающее число
(исходное значение).
Текущее псевдослучайное число Yi получают из предыдущего числа Yi–1 умножением его на
коэффициент a, сложением с приращением b и вычиcлением остатка от деления на модуль m. Дан-
ное уравнение генерирует псевдослучайные числа с периодом повторения, который зависит от выби-
раемых значений параметров a,b и m и может достигать значения m. Значение модуля m берется
равным 2n либо равным простому числу, например m=231–1. Приращение b должно быть взаимно
простым c m, коэффициент a должен быть нечетным числом.
Конгруэнтные генераторы, работающие по алгоритму, предложенному Национальным бюро
стандартов США, используются, в частности, в системах программирования. Эти генераторы имеют
длину периода 224 и обладают хорошими статистическими свойствами. Однако такая длина периода
мала для криптографических применений. Кроме того, доказано, что последовательности, генери-
руемые конгруэнтными генераторами, не являются криптографически стойкими.
Существует способ генерации последовательностей псевдослучайных чисел на основе ли-
нейных рекуррентных соотношений [69].
Рассмотрим рекуррентные соотношения и их разностные уравнения:
k
? h jai+ j = 0,
j=0
k ?1
ai+k = ? ? h jai+ j , (2.18)
j =0

где h0 ? 0, hk = 1 и каждое hi принадлежит полю GF(q).
Решением этих уравнений является последовательность элементов a 0 , a1, a 2 ,... поля GF(q)
(см. Приложение). Соотношение (2.18) определяет правило вычисления ak по известным значениям
величин a0 , a1, a 2 ,..., ak ?1 . Затем по известным значениям a0 , a1, a 2 ,..., ak находят ak +1 и т.д. В резуль-
тате по начальным значениям a0 , a1, a 2 ,..., ak ?1 можно построить бесконечную последовательность,
причем каждый ее последующий член определяется из k предыдущих. Последовательности такого
вида легко реализуются на компьютере, при этом реализация получается особенно простой, если все
hi и ai принимают значения 0 и 1 из поля GF(2).

На рис. 2.12 показана линейная последовательная переключательная схема, которая может
быть использована для вычисления суммы (2.18) и, следовательно, для вычисления значения ak по
значениям k предыдущих членов последовательности. Исходные величины a0 , a1, a 2 ,..., ak ?1 поме-
щаются в разряды сдвигового регистра, последовательные сдвиги содержимого которого соответст-
вуют вычислению последовательных символов, при этом




Выходной
a i+k-1 a i+k-2 a i+2 a i+1 ai бит




hk–1 hk–2 h2 h1 h0




Обозначения:

Сумматор по модулю 2

Цепь (отвод) с коэффициентом передачи
h h, h = 0 или 1

a Запоминающая ячейка, хранящая а, т.е. на
выходе ячейки a= 0 или a=1


Рис. 2.12. Генератор с регистром сдвига

выход после i-го сдвига равен ai . Данное устройство называют генератором последовательности
чисел, построенным на базе сдвигового регистра с линейной обратной связью.
Решения линейных рекуррентных соотношений, реализуемые генератором с регистром сдви-
га, описываются следующей теоремой. Пусть многочлен
k
h (X) = ? hj Xj,
j=0

где X – формальная переменная; hj – коэффициент при Xj, принимающий значение 0 или 1; h0 ? 0, hk
= 1, и пусть n – наименьшее целое положительное число, для которого многочлен Xn – 1 делится на
h(X). Кроме того, многочлен
g(X) = (Xn – 1)/h(X).
Тогда решения рекуррентных соотношений
k
? h j a i+ j = 0
j=0

в виде последовательности элементов a0 , a1, ai ,..., an?1 периодичны с периодом n и совокупность, со-
ставленная из первых периодов всех возможных решений, рассматриваемых как многочлены по мо-

<< Предыдущая

стр. 8
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>