Рацеев.Лабораторные по криптографии


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
1
из
24


ЛАБОРАТОРНЫЕ

РАБОТЫ

по курсу

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


Лабораторная работа 1.


Тема: симметричные криптосистемы.

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

1.

Разработать алгоритмы шифрования и
расшифрования
открытого текста

из
алфавита
A
=
Z
n

на заданном ключе с помощью метода, указанного в варианте.

2.

Определить алфавит

A

криптосистемы (открытого текста и шиф
ртекста). Если
алфавит

A

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

A

в
соответствие символы из

алфавита
Z
n

(
n



основание алфавита).

3.

Написать
функцию

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

4.

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

5.

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


Варианты заданий.


1.

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

2.

Шифр сдвига с числовым ключом
. Алфавит
A


ASCII..

3.

Шифр сдвига с символьным ключом. Алфавит
A



ла
тинские буквы и символ
пробела.

4.

Аффинный шифр.

5.

Преобразование биграмм аффинным шифром.

(не путать с аффинным блочным
шифром)

6.

Преобразование триграмм аффинным шифром.

(не путать с аффинным

блочным
шифром)

7.

Шифр Виженера

с ключевым словом
.

Алфавит
A



латинские буквы и символ
пробела.

8.

Ш
ифр Виженера с числовым ключом. Алфавит
A


ASCII
.

9.

Многопетлевые подстановки. Алфавит
A



латинские буквы и символ пробела.

10.

Многопетлевые подстановки. Алфавит
A



ASCII.

11.

Аффинный блочный шифр

для 3
-
грамм
.

12.

Аффинный блочный шифр для 4
-
грамм.

Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
2
из
24

13.

Шифр Хилла для 3
-
грамм.

14.

Шифр гаммирования с линейным конгруэнтным генератором ключей. Алфавит
A



латинские буквы и символ пробела.

15.

Шифр гаммирования с линейным конгруэнтным г
енератором ключей. Алфавит
A



ASCII.

16.

Шифр перестановки.

17.

Шифр пропорциональной замены (шифр омофонов).



Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
3
из
24

Лабораторная работа 2.


Тема: криптоанализ симметричных криптосистем.


Провести эксперимент по опр
еделению практической стойкости

алгоритма,
разраб
отанного в лабораторной работе №1.


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

текстов и соответствующий набор шифрованных текстов.

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

Использовать
методы:


-

анализа статистических свойств шифртекста (частот появления букв).



-

силовую атаку (полный перебор ключей).




-

другие (если есть более эффективные)


С помощью программы, реализующей выбранный алгори
тм крип
тоана
лиза
провести
эксперимент

по вскрытию шифртекс
тов различного размера.


При использовании статистического к
риптоанализа исполь
зовать табли
цы,
приведенные в
приложении

1

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


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


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


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



Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
4
из
24

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


Тема:
поточные шифры
.

Шифр Вернама. Моделирование работы

разрядного скремблера.



Простейшей и в то же время наиболее надежной из всех схем шифрования является
так называемая
схема однократного гаммирования,

изобретение, которое чаще всего
связывают с именем Г.С. Вернама.


Гаммирование


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


В данной лабораторной работе алфавитом
A
, в котором записываются открытые и
шифрованные тексты
,

является поле
Z
2
, то есть открытые и шифрованные тек
сты
рассматриваются как двоичные последовательности.

В этом случае "наложение"
гаммы
-

не что иное, как выполнение операции сложения



по модулю 2 (
xor
),
которая, например, в языке программирования Си обозначается знаком ^.


Стандартные операции над би
тами:
0


0 = 0, 0


1 = 1, 1


0 = 1, 1


1= 0
.



Скремблером

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


Рассмотрим
сдвиговый регистр с обратной связью

(Linear Feedbac
k Shift Register,
сокращенно LFSR)


логическое устройство, схема которого изобра
жена на рис. 3.1.


Сдвиговый регистр представляет собой последовательность битов. (Количество
битов опред
е
ляется
длиной

сдвигового регистра. Если длина равна
n

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

бит.



Рис. 3.1. Схема LFSR



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

Ульяновский государственный университет

Форма


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





Форма А



Страница
5
из
24

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

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

(ПНД)
.


Чтобы построить 
-
разрядный скремблер, создающий ПНД, поль
зуются
примитивными многочленами.

Примитивный (базовый) многочлен степени


по
модулю
2


это неприводимый многочлен, который является делителем
, но не
является делителем

для всех
, являющихся делителями
.
Неприводимый
многочлен степени


нельзя представить в виде
произведения

многочленов кроме него
самого и единичного.


Найденный примитивный многочлен степени

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


Приведем пример 7 разрядного скремблера, генерирующего последовательность с
периодом равным
:
. Начальное значение (начальный ключ) возьмем
равным
. Для этого сдвигового регистра н
о
вый

бит генерируется с
помощью XOR седьмого и третьего битов (см. рис 3.2).



Рис. 3.2. Схема LFSR для многочлена
,

начальное состояние
.

Требуется

1.

Напис
ать функцию генерации
ключей шифра

с помощью
n
-
разрядного
скремблера (значение
n

зависит от степени многочлена
, указанного в варианте
)
.

2.

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

Z
2
.

3.

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


Варианты заданий.




Скремблер

1


2


3


4


5


Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
6
из
24





6


7


8


9


10


11


12


13


14


15


16


17


18


19


20


Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
7
из
24


Лабораторная работа 4.


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




Блочный шифр


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


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


Идея, лежащая в основе составных (или композиционных
) блочных шифров,
состоит в построении криптостойкой системы путем многократного применения
относительно простых криптографических преобразований, в качестве которых
К.Шеннон предложил использовать преобразования подстановки (sustituti) и
перестановки (
perutti), схемы, реализующие эти преобразования, называются SP
-
сетями.


Многократное использование этих преобразований (рис. 4.1) позволяет обеспечить
два свойства, которые должны быть присущи стойким шифрам: рассеивание
(diusi) и перемешивани
е (cusi) (рис. 4.2). Рассеивание предполагает
распространение влияния одного знака открытого текста, а также одного знака ключа
на значительное количество знаков шифртекста. Наличие у шифра этого свойства
позволяет:



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



не позволяет восстанавливать неизвестный ключ по частям.


Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
8
из
24





Цель перемешивания


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


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


Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
9
из
24




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

блока определить в 64, 128 или
256 бита.


Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
10
из
24

Лабораторная работа
5
.


Российский стандарт шифрования ГОСТ 28147
-
89


Цель работы
:

о
знакомиться с шифрованием и рас
шифрованием информации
при п
о
мощи алгоритма ГОСТ 28147
-
89.

Алгоритм шифрования ГОСТ 28147
-
89


ГОСТ 28147
-
89


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


ГОСТ предусматривает 3

основных

режима шифрования (
простая замена,
гаммирование, гаммирование с обратной связью)
, а также

режим выработки
имитовставки.
Режим простой замены в основном

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


Алгоритм построен по тому же принципу, что и DES


это классический блочный
шифр с секретным ключом


однако отличается о
т DES'а большей длиной ключа,
большим количеством раундов, и более простой схемой п
о
строения самих раундов.
Ниже приведены его основные параметры, для удо
б
ства
-

в сравнении с параметрами
DES'а:


Параметры

ГОСТ

DES

1. Размер блока шифрования

64 бита

64 би
та

2. Длина ключа

256 бит

56 бит

3. Число раундов

32

16

4. Узлы замен (S
-
блоки)

не фиксированы

фиксированы

5. Длина ключа для одного раунда

32 бита

48 бит

6. Схема выработки раундового ключа

простая

сложная

7. Начальная и конечная перестановки
битов

нет

есть



В силу намного большей длины ключа ГОСТ гораздо устойчивей DES'а к вскрытию
п
у
тем полного перебора по множеству возможных значений ключа.


Для шифрования блок текста сначала разбивается на левую половину

и правую

половину
.
В
-
ом раунде

алгорит
ма ГОСТ выполняю
тся сл
е
дующи
е

преобразования
:

Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
11
из
24




Функция

f

действует по следующему правилу
. Сначала правый блок

складывается по
модулю 2
32

с подкл
ю
чом
. Полученное 32
-
битовое сообщение
делится на восемь 4
-
битовых частей. Каждое из этих 4
-
битовых чисел преобразуется
соответству
ю
щим S
-
блоком в другое 4
-
битовое число. П
о
этому любой S
-
блок

определяется некоторой 16
-
битовой перестановкой на множестве из 16 элементов 0, 1,
..., 15.
Например, в

Центробанке

использовались

следующие S
-
блоки:


= (4 10 9 2 13 8 0 14 6 11 1 12 7 15 5 3),


= (14 11 4 12 6 13 15 10 2 3 8 I 0 7 5 9),

= (5 8 1 13 10 3 4 2 14 15 12 7 6 0 9 11),

= (7 13 10 I 0 8 9 15 14 4 6 12 11 2 5 3),

= (6 12 7 1

5 15 13 8 4 10 9 14 0 3 11 2),


= (4 11 10 0 7 2 1 13 3 6 8 5 9 12 15 14),

= (13 11 4 1 3 15 5 9 0 10 14 7 6 8 2 12),

= (l 15 13 0 5 7 10 4
9 2 3 14 6 11 8 12).


После преобразования S
-
блоками полученное 32
-
битовое сообщение сдвигается
цикл
и
чески влево на 11 позиций.


Ключевое расписание. Исходный 256
-
битовый ключ делится на восемь 32
-
битовых
подключей
, они используются в 32 тактах в следующем п
о
рядке: 1 2 3 4 5 6 7
8 1 2 3 4 5 6 7 8 1 2 3 4

5 6 7 8 8 7 6 5 4 3 2 1. При рас
шифр
о
вании порядок
использования подключей меняе
т
ся на противоположный.


Варианты заданий.

1. Реализовать шифр Г
ОСТ 28147
-
89 в режиме простой замены.

2. Реализовать шифр ГОСТ 28147
-
89 в режиме гамм
и
рования.

3. Реализовать шифр ГОСТ 28147
-
89 в режиме гаммирования с обратной связью
.

4. Реализовать шифр ГОСТ 28147
-
89 в режиме выработки имотовставки

(имитовставка выра
батывается с помощью «усеченного» 16
-
раундового алгоритма
ГОСТ, при этом вектор имитовставки


это 32 младших бита последнего блока

шифртекста
)
.

Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
12
из
24


Лабораторная работа 6

Генерация простого большого числа.


Цель работы


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


Указание к работе

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

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

Конкретно для реализации алгоритма
RSA

используются

большие простые
числа. Простых чисел не так мало, как кажется, например, существует приблизител
ьно
10
151

простых чисел длиною от 1 бита до 512 включительно. Для чисел близких
n
,
вероятность того, что выбранное число окажется простым, равна 1/
ln

n
. Поэтому
полное число простых чисел, меньших
n

равно
n
/
ln

n
. Считается, что вероятность
выбора двумя лю
дьми одного и того же большого простого числа пренебрежимо мала.

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

Повсеместно используемым является алгоритм, разработанный Майклом
Рабином по идеям Гари Миллера.


Те
ст
Rabin
-
Miller

Выберите для проверки случайное число

p
. Вычислите

b

как наибольшее число
делений
p
-
1 на 2 т.е. 2
b



наибольшая степень числа 2, на которое делится
p
-
1. Затем
вычислите
m
, такое, что
p
=
1+2
b

m



Выберите случайное число
a
, меньшее

p
.



Уста
новите

j
0 и
z
=
a
m

mod

p



Если
z
1 или если

z
=
p
-
1, то
p

проходит проверку и может быть простым
числом.



Если
j
>0 и
z
1, то
p

не является простым числом.



Установите
j
=
j
+1.


Если
j

b

и
z

p
-
1, установите
z
=
z
2

mod

p

и вернитесь на

.


Если
z
=
p
-
1, то
p

пр
оходит проверку и может быть простым числом.

Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
13
из
24



Если

j
=
b

и
z

p
-
1, то
p

не является простым числом.

Повторить эту проверку нужно

t

раз.


Доказано, что в этом тесте вероятность прохождения проверки составным
числом убывает быстрее, чем в прочих. Гарантируется
, что 75% возможных значений
а
окажутся показателями того, что выбранное число
p

составное. Это значит, что
вероятность принять составное число
p

за простое не превышает величины (¼)
t
.


Генерация простого числа



Сгенерируйте случайное
n
-
битовое число

p
.



Установите его старший и младший биты равными 1. Старший бит будет
гарантировать требуемую длину искомого числа, а младший бит обеспечивает
его нечетность.



Убедитесь, что
p

не делится на небольшие простые числа: 3, 5, 7, 11 и т.д.
Наиболее эффективной

является проверка на делимость для всех простых чисел,
меньших 2000.



Выполните тест
Rabin
-
Miller

минимум 5 раз.

Если
p

не прошло хотя бы одну проверку из


или

, оно не является простым.

Проверка, что случайное нечетное
p

не делится на 3, 5 и 7 отсекает 54%
нечетных чисел. Проверка делимости на все простые числа, меньшие 256 отсекает
80% составных нечетных чисел.

Даже, если составное число «просочилось» через этот алгоритм, это будет сразу
же замечено, т.к. шифрование и де
шифрование не будут работать.


Задание

Реализовать программу, генерирующую простые числа.

1.

Предусмотреть возможность выдачи всех простых чисел в заданном диапазоне.

2.

Выдавать время, затраченное на вычисление простых чисел.


Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
14
из
24

Лабораторная работа
7

Построени
е первообразного корня по модулю
n

Цель работы


Ознакомится с теоремой Эйлера, а также построить первообразные корни по
модулю
n
.

Указание к работе


В силу теоремы Эйлера, для любых взаимно простых
а

и
n

выполняется
соотношение:

a

(
n
)


1
mod

n
,


(9.1)

где

(
n
)

обозначает функцию Эйлера, значение которой равно числу положительных
целых значений, меньших
n

и взаимно простых с
n
.
Для простого числа
p



(
p
)=
p
-
1,

Если предположить, что два числа
p

и
q


просты
е, тогда для
n
=
p

*
q


функция Эйлера
будет иметь вид


(
n
)=

(
p

*
q

)=

(
p

)*

(
q

)=[(
p
-
1)
p

-
1
]*[(
q
-
1)
q

-
1
].
(9.2)



Рассмотрим более общее соотношение, чем (9.1). Говорят, что число
a
, взаимно
простое с модулем
n
,
принадлежит показателю

m
, есл
и
m



такое наименьшее
натуральное число, что выполняется сравнение

a
m



1
mod

n
. (9.3)

Если
а

и
n

являются взаимно простыми, то существует, по крайней мере, одно число
m
=

(
n
)
, удовлетворяющее (9.3). Наименьшее
из положительных чисел
m
,
для которых
выполняется (9.3), является длиной периода последовательности, генерируемой
степенями
а
.

Справедливы следующие свойства.

Свойство 1.

Числа
a
0
,
a
1
,… ,
a
m
-
1

попарно несравнимы по модулю
n
. Действительно,
a
l



a
k

mod

n
,
l


k



a
l
-
k



1
mod

n
, где
l



k



,
l



k


m
.

Свойство 2.

a




a




mod

n










mod

m
. Разделим

,





на
m

с остатками



=
mq

+
r
,


’ 
mq
’ 
r

. Тогда
a




a






a
mq
+
r



a
mq
’
r




a
r



a
r



r
’
r
. Отсюда
вытекает следующее свойство.

Свойс
тво 3.

m
|

(
n
)
. Число, принадлежащее показателю

(
n
)
, называется
первообразным корнем

по модулю
n
.

Свойство 4.

По любому простому модулю
p

существует первообразный корень.
Первообразные корни существуют по модулям 2, 4,
p

, 2
p

,

где
p



нечетное простое,





.

Свойство 5.

Пусть
c

=

(
n
)

и
q
1
,
q
2
,…,
q
k



различные простые делители числа
c
. Число
a
, взаимно простое с модулем
n
, будет первообразным корнем тогда и только тогда,
когда не выполнено ни одно из следующих сравнений:




Необходимость следует из того, что
a

(
n
)


1
mod

n

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

не удовлетворяет ни одному
из сравнений, и пусть
a

принадлежит показателю
m


c
. Тогда
m
|
c


c
=
mn
.
Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
15
из
24

Обозначим ч
ерез
q

простой делитель
u
. Тогда легко получить противоречие:

a
c/q
= a
mu/q

=( a
m
)
u/q


1 mod n
.



Если некоторая последовательность имеет длину

(
n
),

тогда целое число
а

генерирует своими степенями множество всех ненулевых вычетов по модулю
n
.
Такое
цел
ое число называют первообразным корнем числа
а
по модулю

n
. Количество их
равно для числа
n


(
n
-
1),
(9.4)

где


-

функция Эйлера.



Пример (
Проверка Свойства 5.
).

Пусть
n
41. Имеем
c

=

(41)

= 40 = 2
3



5. Итак,
первообразный корень не должен удовлетворять двум сравнениям


a
8


1(
mod
41),
a
20


1(
mod
41).


Испытаем

числа

2, 3, 4, …: 2
8



10, 2
20



1
, 3
8



1
, 4
8



18
, 4
20



1
, 5
8



18
, 5
20



1
, 6
8



10, 6
20



40.
Отсюда видим, что 6 является
наименьшим первообразным корнем по
модулю 41.


Задание

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


Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
16
из
24

Лабораторная работа
8

Обмен ключами по схеме Диффи
-
Хеллмана


Цель работы



Освоить обмен ключами по схеме Диффи
-
Хеллмана, изучая проблему
первообразных корней.

Указание к работе


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


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


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



Рис.

Обмен ключами по схеме Диффи
-

Хеллмана
.


Алгоритм заключается в следующем:

1.

Глобальные открытые элем
енты:

q

-

простое число

a

-

первообразный корень
q

2.

Вычисление ключа абонентом
A
:



абонент
A

абонент
B

Y
B

Y
A

Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
17
из
24



выбирается секретное число
X
A

(
X
A

q
)



вычисление открытого

значения
Y
A
:


3.

Вычисление ключа абонентом
B
:



выбирается секретное число
X
B

(
X
B

q
)



вычисл
ение открытого

значения
Y
B
:


4.

Вычисление секретного ключа абонентом
A
:

5.

Вычисление секретного ключа абонентом
B
:

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

Пример:

Пусть
q

 97 и
a

= 5

Абонент
A
: Сгенерировал случайное число
X
A

= 36

Абонент
B
: Сгенерировал случайное число
X
B

= 58

Эти элементы они держат в секрете. Далее каждый из них вычисляет новый
элемент:
,


Потом они обмениваются этими э
лементами по каналу связи. Теперь абонент
A
,
получив
Y
B

и зная свой секретный элемент
X
A
, вычисляет общий ключ:
.

Аналогично поступает абонент
B
:

Задание


Реализовать программу, генерирующую алгори
тм
обмена ключей по схеме Диффи
-
Хеллмана.


Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
18
из
24

Лабораторная работа
9


Шифр
RSA

Цель работы



Освоить методику работы ассиметричных алгоритмов шифрования, где существует
два ключа
-

один для шифрования, другой для
рас
шифрования.

Указание к работе


Алго
ритм
RSA

был разработан в 1977 году Роном Ривестом, Ади Шамиром и
Леном Адлеманом и опубликованный в 1978 году. С тех пор алгоритм Rivest
-
Shamir
-
Ade (RSA) широко применяется практически во всех приложениях,
использующих криптографию с открытым ключом.

Алгоритм RSA состоит из трех этапов:

I.

Вычисление ключей

Важным моментом в этом криптоалгоритме является создание пары ключей:
открытого и закрытого. Для алгоритма RSA этап создания ключей состоит из
следующих операций:

1.

Выбираются два простых РАЗЛИЧНЫХ ч
исла p и q. Вычисляется их
произведение p*q, называемое модулем.

2.

Вычисляется функция Эйлера Ф()(p
-

1)*(q
-

1).

3.

Выбирается произвольное число e (e ), такое, что 1 e Ф(
n
) и не имеет общих
делителей кроме 1 (взаимно простое) с числом

(p
-

1)*(q
-

1).

4.

Вычисляется d методом Евклида таким образом, что (e*d
-

1) делится на (p
-

1)*(q
-

1).

5.

Два числа (е, )
-

публикуются как открытый ключ.

6.

Число d хранится в секрете
-

закрытый ключ есть пара (d, ), который позволит
читать все послани
я, зашифрованные с помощью пары чисел (е, ).

II.

Шифрование

Шифрование с помощью этих чисел производится так:



Отправитель разбивает свое сообщение

на блоки
. Значение
,
поэтому длина
блока

в битах не больше [
2
()] бит, где квадратные
скобки обозначают, взятие целой части от дробного числа.

Например, если
n
21, то максимальная длина блока [
2
(21)][4.39…]4
бита.

Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
19
из
24



Подобный блок может быть интерпретирован
как число из диапазона (0;2
k
-
1).
Для каждого такого числа
m
i

вычисляется выражение (
c
i



зашифрованное
сообщение):
.

Необходимо добавлять нулевые биты слева в двоичное представление блока
до размера [
2
()] бит.

III.

Рас
шифрование


Чтобы получить открытый текст
надо каждый блок рас
шифровать отдельно:

Пример:

Выбрать два простых числа: р  7, q  17.

Вычислить   p·q  7 · 17  119.

Вычислить Ф()  (p
-

1)·(q
-

1) = 96.

Выбрать е так, чтобы е было взаимнопростым с Ф()  96 и меньше, чем Ф(): е  5.

Определить d так, чтобы d·e ≡ 1 d 96 и d  96.

d  77, так как 77 · 5  385  4 · 96  1.

Результирующие ключи открытый {5, 119} и закрытый ключ {77, 119}.

Например, треб
уется зашифровать сообщение М  19.

19
5

 66 (d 119); С  66.

Для
рас
шифрования вычисляется 66
77

(mod 119) = 19.

Задание

Реализовать программу, работающую по алгоритму RS
A

Программа должна уметь
работать с текстом произвольной длины.

Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
20
из
24

Лабораторная работ
а 11


Алгоритм шифрования Эль Гамал
я



Асимметричная схема Эль Гамаль, предложенная автором (E G),
использует операцию возведения в степень по модулю простого числа. При этом
трудноразрешимой задачей для злоумышленника является отыскание не числа,
кот
орое возведено в степень, а то, в какую степень возведено известное число. Эта
задача носит название проблемы
дискретного логарифма.





На этапе выработки ключей:


1. Выбирается произвольное (правда достаточно большое) простое число р.


2. Для этого про
стого числа определяется любой
образующий элемент

(англ.
primitive

root
)


т. е. такое число а, при многократном возведении которого в степень
по модулю р (а
1

mod p,
a
2

mod

p
, …) , будут перебираться (в произвольном порядке, но
обязательно по одному разу)

все числа от 1 до (
p
-
1) включительно.


3. Генерируется произвольное случайное число х (0х
p
)


это и есть

закрытый ключ.


4. Вычисляется значение
b

=
a
x

mod

p



комбинация (, p, ) представляет собой
открытый ключ получателя.



На этапе шифрования:


1
. Отправитель генерирует произвольное случайное число y (0
y

p
).


2. Помещает в начале шифрограммы число (
y

mod

p
) .


3.
Вычисляет

величину

k = (b
y

mod p) = ((a
x

mod p)
y

mod p).


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


5. Надежно стирает числа y и  из оперативной памяти и других мест, куда они
могли случайно попасть.



На этапе дешифрования:


1. По приходу зашифрованного сообщения по
лучатель отделяет от пакета
величину (
y

mod

p
) и вычисляет на ее основе ((
a
y
mod

p
)
x

mod

p
)


математика
доказывает, что полученное число будет равно тому самому , которое вычислил
отправитель, так как в данной формуле операнды
x

и
y

можно менять местами
.

2. Выделив из  туже самую часть, что и отправитель, получатель дешифрует весь
идущий далее пакет симметричным алгоритмом.



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

обозримое время определить, в какую именно степень было возведено основание. В
схеме Эль Гамаль потенциальный злоумышленник может получить значения , p, (
x

d p) и (
y

d p). Однако из
-
за сложности определения чисел х и y

"в чистом виде"
Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
21
из
24

у него не оказывается возможности вычислить значение   (
a
xy

d p), которое так
необходимо для прочтения шифровки.


По криптостойкости с схеме Эль Гамаль 512
-
битное число p приравнивается к
56
-
битному симметричному ключу, размер которог
о в настоящее время недостаточен
для надежного шифрования. Поэтому на практике применяются р длиной в 768, 1024
и 1536 бит.


Пример.

В качестве простого числа, порождающего циклическую группу,
выберем р  11, за образующий элемент примем число а  7 (при

возведении 7 в
степень 1, 2, 3 и т. д. по модулю 11 последовательно проходят все 10 значений [7, 5, 2,
3, 10, 4, 6, 9, 8, 1] ). Секретным ключом х выберем 6, параметр
b

принимает значение
b

= (
a
x

mod

p
) = (7
6

mod

11 )  4. В целом ключ принимает вид (а
 7, р  11,   4).


Предположим, что некий абонент хочет передать сообщение. Он выбрал
случайное число, не превосходящее р, например, у  9. В начало шифрограммы
помещается число (
a
y

mod

p
) = 7
9

mod

11)  8. Кроме того, на основе у и открытого
ключа о
тправитель вычисляет   
y

mod

p

= 4
9
mod

11  3. Выбрав значение 3 или
какие
-
либо его биты в качестве симметричного ключа, отправитель шифрует
передаваемые данные и стирает величины 9 и 3 со своих накопителей.


Получатель по приходу пакета для вычислени
я   (
a
y

mod

p
)
x

mod

p

возводит
число 8 из заголовка шифрограммы в степень секретного ключа и получает   8
6

mod

11 = 3


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

Задание

Реализовать программу, работающую по алгори
тму
Эль Гамаль
.

Программа должна
уметь работать с текстом произвольной длины.

Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
22
из
24

Лабораторная ра
бота 1
1

Электронн
ая цифровая подпись Эль

Гамаля

Теоретическая часть.


Пусть для абонента A имеем секретный ключ
x
A
и открытый
ключ
y
A

=


x
A
. Подписью аб
о
нента
A

п
од документом
M
, где
M



p

служит пара чисел
(
r
,
s
), где 0



r



p



1 и 0



s



p



1, которая удовлетвор
я
ет уравнению


M

=

y
A
r
r
s

(
mod

p
).

Это

уравнение проверки подписи абонента

A.

Данная система ЭЦП основана на том,
что только действител
ь
ный владелец

секретного ключа
a
может выработать пару
чисел (
r
,

s
), удовлетворяющую уравнению проверки подписи, по следующему
алгоритму:

1.

Сгенерировать случайное число
k
, удовлетворяющее условию:


0



k



p



1 и НОД(
k
,

p



1)

=

1.

2.

Вычислить
r

=


k

(
m
od

p
).

3.

Вычис
лить
s

из уравнения
M

=

x
A
r

+

ks

(mod

(
p



1)).

Из теории чисел известно, что последнее уравнение имеет решение для s, если
НОД(
k
,

p



1)

=

1. Это уравн
е
ние легко получить путем подстановки в уравнение
проверки подписи значения
r

=


k

mod

p:


M

=


x
A
r

k
s

=

y
A
r
r
s

(mod

p
).

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

Особенностью данной ЭЦП являе
тся то, что одно и то же значение
k

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

k
должны храниться в секрете. Обычно после выработки по
дписи они уничтожаются.

Задание

Используя заданные значения простого числа
p

и параметра

, сформировать
секре
т
ный ключ
x
A
, вычислить соответствующий ему открытый ключ
y
A

и вычислить
значение электронной подписи для 10 различных сообщений, фиксируя получа
емые
значения параметров
k, r

=


k
,
s
,

M
,

y
A
r
,
r
s
,
y
A
r
r
s

(
m
od

p
). Осущ
е
ствить проверку
подписи по открытому ключу. Результаты оформить в виде таблицы.

Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
23
из
24


Приложение 1.

Приложение
1: Таблица вероятностей букв в русских текстах.

буква

пробел

о

е
или

ё

а

и

н

т

с

р

в

л

вер
-
ть

0,175

0,09
0

0,072

0,062

0,062

0,053

0,053

0,045

0,040

0,038

0,035

буква

к

м

д

п



у

я

з

ы

б

вер
-
ть

0,028

0,02
6

0,025

0,023

0,021

0,018

0,016

0,016

0,014

0,014

0,013

буква

ъ
или
ь

г

х

ж

ш

ю

ц

щ

э

ф


вер
-
ть

0,012

0,01
0

0,009

0,007

0,0
06

0,006

0,004

0,003

0,003

0,002



Приложение
2. Таблица вероятностей букв в английских текстах.

буква

пр
-
л

е

t

а

о

n

i

s

r

вер
-
ть

0,185

0,097

0,076

0,064

0,062

0,057

0,056

0,052

0,047

буква

h

l

d

с

u

p

f

м

w

вер
-
ть

0,04

0,031

0,028

0,025

0,018

0,018

0
,018

0,017

0,016

буква

y

в

g

v

к

q

x

j

z

вер
-
ть

0,015

0,013

0,013

0,007

0,039

0,002

0,002

0,001

0,001



Федеральное агентство по образованию

Ульяновский государственный университет

Форма


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





Форма А



Страница
24
из
24

ЛИТЕРАТУРА

1.

Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы
криптогр
а
фии.


М.: Гелиос АРВ, 2001.

2.

Зубов А.Ю. Криптографические методы

защиты информации. Совершенные
ши
ф
ры.
--

М.: Гелиос АРВ, 2005.

3.

Нечаев В.И.

Элементы криптографии.


М.: Высшая школа, 1999.

4.

Рябко Б.Я., Фионов А.Н. Криптографические методы защиты информации.


М.:
Горячая линия


Телеком, 2005.

5.

Фомичев В.М. Дискретная ма
тематика и криптология.


М.: ДИАЛОГ
-
МИФИ,
2003.

6.

Фомичев В.М. Методы дискретной математики в криптологии.


М.: ДИАЛОГ
-
МИФИ, 2010.


Приложенные файлы

  • pdf 1277039
    Размер файла: 900 kB Загрузок: 0

Добавить комментарий