Отчетность по практической работе

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

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

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

Рис. 4.1

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

Содержание заданий

Задание 1

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

Задание 2

Используя шифр «двойной квадрат» Уитстона и шифрую- щие таблицы, представленные на рис. 4.1, выполните шифрова- ние сообщения из задания практической работы 3.

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

1. 
   Чем шифры сложной замены отличаются от шифров прос- той замены?
   
2. 
   Что используется в качестве ключа в системе Вижинера?
   
3. 
   Как осуществляется шифрование текста с использованием системы Вижинера?
   
4. 
   Какие требования предъявляются к шифруемому тексту при использовании шифра «двойной квадрат» Уитстона?
   
5. 
   Как осуществляется шифрование текста с использованием шифра «двойной квадрат» Уитстона?
   

Отчетность по практической работе

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

ПРАКТИЧЕСКАЯ РАБОТА 5

РЕАЛИЗАЦИЯ ЭЛЕМЕНТОВ КРИПТОСИСТЕМЫ RSA


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

Теоретические сведения

RSA относится к так называемым асимметричным алгорит- мам, у которых ключ шифрования не совпадает с ключом рас-

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

Описание RSA

Алгоритм RSA состоит из следующих пунктов:

1. 
   Выбрать простые числа p и q.
   
2. 
   Вычислить n = pq.
   
3. 
   Вычислить m = (p – 1) · (q – 1).
   
4. 
   Выбрать число d взаимно простое с m.
   
5. 
   Выбрать число e так, чтобы ed = 1 (mod m).
   

Числа e и d являются ключами RSA. Шифруемые данные необходимо разбить на блоки – числа от 0 до n – 1. Шифрование и расшифровка данных производятся следующим образом:

• 
  шифрование: b = a^e (mod n);
  
• 
  расшифрование: a = b^d (mod n).
  

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

Нахождение простых чисел

В первом пункте алгоритма RSA сказано, что необходимо выбрать два простых числа p и q. Простой способ – деление предполагаемого простого числа на все числа меньшие его (не работоспособен уже с 32-битными числами, поскольку требуется большое количество времени на выполнение).
В данном случае, для выработки простых чисел используют вероятностные методы, но они не дают полной гарантии, что найденное число простое. Однако при достаточно небольшом количестве операций можно получить высокую вероятность, что найденное число является простым.

Алгоритм поиска простых чисел

1. 
   N – нечетное число. Найти s и t, удовлетворяющие урав- нению: N – 1 = 2^s · t.
   
2. 
   Случайным образом выбрать число a, 1 < a < N.
   
3. 
   Если N делится на a, перейти к пункту 6.
   
4. 
   Если условие at = 1 (mod N) выполняется, перейти к пунк- ту 2.
   
5. 
   Если найдется такое k, 0  k < s, что a^2kt = –1 (mod N), пе- рейти к пункту 2.
   
6. 
   Число N – составное: выбрать другое нечетное число N,
   

перейти к пункту 1.
Если для какого-либо числа N проверено m чисел a, то ма- тематически доказанная вероятность того, что число является составным будет равняться 4 – m (но вероятность намного мень- ше этого значения). Исходя из этого, для числа N, состоящего из p бит, проверить p различных значений a. Если во время этого не обнаружится, что N – число составное, то вероятно, что оно яв- ляется простым.

Нахождение взаимно простых чисел

На шаге 4 алгоритма RSA необходимо найти число d взаим- но простое с m, то есть не имеющее общих делителей с ним, кроме единицы. Число d должно быть меньше m, таким образом, разрядность числа d равна сумме бит в числах p и q. Для нахож- дения взаимно простых чисел используется алгоритм Евклида, который находит наибольший общий делитель двух чисел. Если найденный делитель больше единицы, то необходимо выбрать другое число d и повторить проверку.

Алгоритм Евклида

1. 
   Исходные числа a и b.
   
2. 
   Вычислить r – остаток от деления a на b: a = bq + r.
   
3. 
   Если r = 0, то b – искомое число (наибольший общий де- литель), конец.
   
4. 
   Если пункт 3 не выполняется, заменить пару чисел <a, b>
   

парой <b, r>, перейти к пункту 2.
При вычислении наибольшего общего делителя с помощью алгоритма Евклида будет выполнено не более 5p операций деле- ния с остатком, где p есть количество цифр в десятичной записи меньшего из чисел a и b.

Решение уравнения ax + by = 1

В 5-м пункте алгоритма RSA предполагается нахождение такого числа e, чтобы ed = 1 (mod m). Для этого нужно использо-

вать модифицированный алгоритм Евклида, который работает только если числа d и m взаимно просты. Вычисление числа e сводится к решению уравнения mx + de = 1 в натуральных чис- лах. Число x не существенно.

Алгоритм решения уравнения ax + by = 1

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

жүктеу/скачать 1,61 Mb.

Достарыңызбен бөлісу: