Одноразовое заполнение

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

Рис. 5 Система одноразового шифрования

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

3. Задания

1. Используя перестановочный шифр с глубиной сетки 8, закодируйте сообщение: “Takeover announcement will be made at noon tomorrow” (Объявление о слиянии компании будет сделано завтра утром).

2. Повторите кодирование, используя перестановочный шифр с ключевым словом “COLUMNAR” (которое используется для определения упорядочивания по столбцам).

3. Используя шифр Цезаря со сдвигом 4, закодируйте сообщение: “Now is the time for all good men to come to the aid of the part” (Для всех хороших людей настало время прийти на помощь партии).

4. Дешифруйте сообщение:

KWWS://ZZZ.DQtHQQD-PRGHOV.FRP/VHFUHt/LQGHA.htPO.

5. Используя шифр Виженера и ключевое слово “hide”, закодируйте”We must meet under the clock” (Мы должны встретиться под часами).

6. Используя поточный шифр и начальный ключ “D”, закодируйте сообщение: “The documents will be sent tomorrow” (Документы будут посланы завтра).

4. Контрольные вопросы

1. Какие системы называются системами шифрования с частными ключами?

2. Какие виды систем с частными ключами вы знаете?

3. В чем заключается подстановка Виженера?

Лабораторная работа № 3

Криптосистемы с общим ключом

1. Цель работы

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

2. Краткие теоретические сведения

Двумя наиболее популярными алгоритмами криптографических схем с открытым ключом являются алгоритмы RSA и Деффи-Хеллмана.

Алгоритм RSA

Данный алгоритм был предложен в 1977 году. RSA представляет собой блочный шифр, в котором открытый и шифрованный текст представляют целыми числами из диапазона от 0 до n-1 для некоторого n. Шифрование и дешифрование для блока открытого текста M и блока шифрованного текста C можно представить в виде следующих формул: . Как отправитель, так и получатель должны знать значения n и e, но только получателю известно значение d. Т.е., данная схема является алгоритмом шифрования с открытым ключом KU={e, n} и личным ключом KR={d, n}. Для данного алгоритма должны выполнятся следующие условия.

1. Должны существовать такие значения e, d и n, при которых для всех M<n.

2. Должны относительно легко вычисляться и С для всех значений M<n.

3. Должно быть практически невозможно определить d по имеющимся e и n.

Алгоритм. Выбираются два простых ключа p и q, и вычисляется их произведение n, которое будет служить модулем сравнения при шифровании и дешифровании. Затем рассматривается величина , называемая функцией Эйлера, значение которой равно числу положительных целых чисел, не превышающих n и взаимно простых с n. После этого выбирается целое значение e, взаимно простое с (это значит, что наибольшим общим делителем этих чисел является 1). Затем вычисляется значение d, являющееся мультипликативным обратным значения e по модулю ( ).

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

1. Выбираются два простых числа, p=7 и q=17.

2. Вычисляется n=p*q=7*17=119.

3. Вычисляется .

4. Выбирается e, взаимно простое с и меньше, чем ; в данном случае e=5.

5. Определяется такое d, что d*e=1 mod 96 и d<96. Соответствующим значением будет d=77, так как 77*5=385=4*96+1.

В результате получают открытый ключ KU={5,119} и личный ключ KR={77,119}. Рассмотрим пример с вводимым текстом M=19. при шифровании 19 возводится в пятую степень, что в результате дает 2476099. В результате деления на 119 определяется остаток равный 66. Поэтому шифрованным текстом будет 66.

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

Рис. 6 Пример шифрования с использованием алгоритма RSA

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