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




Скачать 116.49 Kb.
НазваниеЛабораторная работа №4
Дата публикации12.03.2014
Размер116.49 Kb.
ТипЛабораторная работа
skachate.ru > Информатика > Лабораторная работа

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

Алгоритм RSA.


Цель: Так как лабораторная работа разделена на варианты, то у данной работы две цели:

  1. Научиться работать с алгоритмами на основе открытого ключа без использования специальных библиотек на подобии CryptoAPI

  2. Построить сеть Фейстиля

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

  2. Задача2: Написать программу, реализующую шифрование и дешифрование по алгоритму сети Фейстиля.


Отчёт: Отчёт по лабораторной работе должен содержать:

  1. цель работы;

  2. постановка задачу;

  3. исходный текст программы (ключевые в прямом и переносном смысле моменты с подробными комментариями).


Дополнительную информацию можно найти на сайте http://algolist.da.ru, http://algolist.manual.ru
^

Краткая теория к заданию 1



Алгоритмы с открытым ключом

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

В 1976 году два исследователя из Стэнфордского университета, Диффи (Diffie) и Хеллман (Hellman), предложили радикально новую криптосистему, в которой ключ шифрования и ключ дешифрации были различными, кроме того, ключ де­шифрации нельзя было получить из ключа шифрования. Предложенные ими ал­горитм шифрования Е и алгоритм дешифрации D (оба параметризованные клю­чом) должны были удовлетворять следующим трем требованиям:

  1. D(E(P)) = Р.

  2. Крайне сложно вывести D из Е.

  3. Е нельзя взломать при помощи произвольного открытого текста.

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

Этот метод работает следующим образом. Некто, например Алиса, желая по­лучать секретные сообщения, сначала формирует два алгоритма, удовлетворяю­щие перечисленным выше требованиям. Затем алгоритм шифрования и его ключ открыто объявляются, отсюда название — шифрование с открытым ключом. Это можно сделать, разместив открытый ключ, например, на домашней странич­ке Алисы. Для обозначения алгоритма шифрования, параметризованного откры­тым ключом Алисы, мы будем использовать запись EА. По аналогии (секретный) алгоритм дешифрации, параметризованный персональным ключом Алисы, мы будем обозначать DA. Боб делает то же самое, открыто объявляя Eв, но храня в тайне DB.

Теперь посмотрим, сможем ли мы решить проблему установки надежного ка­нала между Алисой и Бобом, которые ранее никогда не встречались. Оба ключа шифрования Алисы и Боба, ЕА и Ew являются открытыми. (Вообще, все пользо­ватели сети могут, становясь пользователями, опубликовать свои ключи шифро­вания.) Теперь Алиса берет свое первое сообщение Р, вычисляет ЕВ(Р) и посыла­ет его Бобу. Боб расшифровывает его с помощью своего секретного ключа DB, то есть вычисляет DB(EB(P)) = Р. Больше никто не может прочитать это зашифрованное сообщение ЕВ(Р), так как предполагается, что система шифрования дос­таточно надежна, а получить ключ DB на основании известного ключа Eв очень трудно. Посылая ответ, Боб передает EA(R). Таким образом, Алиса и Боб получа­ют надежный секретный канал связи.

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

^ Алгоритм RSA

Единственная загвоздка состоит в том, чтобы найти алгоритмы, удовлетворяю­щие всем трем требованиям. Поскольку преимущества шифрования с открытым ключом очевидны, многие исследователи неустанно работали над созданием по­добных алгоритмов, и некоторые из них уже опубликованы. Один хороший метод был разработан группой исследователей Массачусетского технологического ин­ститута (Rivest и др., 1978). Он назван по начальным буквам фамилий трех разра­ботчиков: RSA (Rivest, Shamir, Adleman). Этот метод вот уже четверть века вы­держивает попытки взлома и считается очень прочным. На его основе построены многие практические системы безопасности. Главный недостаток RSA заключа­ется в том, что для обеспечения достаточного уровня защищенности требуется ключ длиной, по крайней мере, 1024 бита (против 128 бит в алгоритмах с симмет­ричными ключами). Из-за этого алгоритм работает довольно медленно.

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

  1. Выберем два больших простых числа р и q (обычно длиной 1024 бита).

  2. Сосчитаем n=pq и z=(p-1)(q - 1)

  3. Выберем число d, являющееся взаимно простым с числом z.

  4. Найдем такое число е, что остаток от деления произведения ed на число z ра­вен 1.

Вычислив заранее эти параметры, можно начинать шифрование. Сначала ра­зобьем весь открытый текст (рассматриваемый в качестве битовой строки) на блоки так, чтобы каждое сообщение Р попадало в интервал 0 < Р < п. Это не­сложно сделать, если разбить открытый текст на блоки по k бит, где kмакси­мальное целое число, для которого 2k < п.

Чтобы зашифровать сообщение Р, вычислим С = Рe (mod n). Чтобы расшиф­ровать С, сосчитаем Р = Cd (mod n). Можно доказать, что для всех значений Р в указанном диапазоне функции шифрования и дешифрации являются взаимно обратными. Чтобы выполнить шифрование, нужны е и п. Для дешифрации требуются d и п. Таким образом, открытый ключ состоит из пары , п), а закрытый ключ — из пары (d, n).

Надежность метода обеспечивается сложностью нахождения множителей больших чисел. Если бы криптоаналитик мог разложить на множители (откры­тое) число п, он мог бы тогда найти значения р и q, а следовательно, и число z. После этого числа е и d можно найти при помощи алгоритма Евклида. К сча­стью, математики пытались решить проблему разложения на множители боль­ших чисел по меньшей мере 300 лет, и накопленный опыт позволяет предполо­жить, что эта проблема чрезвычайно трудна.

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

Тривиальный учебный пример работы алгоритма RSA приведен на рис. 8.14. Для этого примера мы выбрали p = 3, q=11, что дает значения п = 33, а z = 20. Число d можно выбрать равным 7, так как числа 20 и 7 не имеют общих делителей. При таком выборе значение е можно найти, решив уравнение 7е = 1 (mod 20), от­куда следует, что е = 3. Зашифрованный текст С получается из открытого сооб­щения Р по формуле С = Р3 (mod 33). Получатель расшифровывает сообщение по формуле Р = С7 (mod 33). В качестве примера на рисунке показано шифрова­ние слова «SUZANNE».



Поскольку выбранные для данного примера простые числа так малы, Р долж­но быть менее 33, поэтому каждый блок открытого текста может содержать лишь одну букву. В результате получается моноалфавитный подстановочный шифр, что не очень впечатляет. Если бы мы вместо этого выбрали числа р и q порядка 2512, тогда число п было бы около 21024. В этом случае каждый блок мог бы содер­жать до 1024 бит, или 128 восьмиразрядных символов, против 8 символов шиф­ра DES или 16 AES.

Следует отметить, что использование алгоритма RSA в описанном ранее виде аналогично использованию симметричного алгоритма в режиме ЕСВ (Electronic Code Book — электронный шифроблокнот), в котором одинаковые блоки на вхо­де преобразуются в одинаковые блоки на выходе. Таким образом, для шифрова­ния данных требуется сцепление блоков в каком-либо виде. Однако на практике алгоритм RSA с открытым ключом используется только для передачи одноразово­го секретного ключа, после чего применяется какой-нибудь алгоритм с симмет­ричным ключом типа AES или тройного DES. Система RSA слишком медленная, чтобы шифровать большие объемы данных, однако она широко применяется для распространения ключей.

Краткая теория к заданию 2


^ Сеть Фе́йстеля (конструкция Фейстеля) — разновидность блочного шифра с определенной итерированной структурой. Многие современные блочные шифры используют сеть Фейстеля в качестве основы.

В 1973 году Хорст Фейстель (Horst Feistel) в журнале Scientific American опубликовал статью «Cryptography and Computer Privacy», в которой раскрыл некоторые важные аспекты шифрования, а также ввел конструкцию, названную впоследствии сетью Фейстеля. Эта схема была использована в проекте Lucifer фирмы IBM, над которым работали Фейстель и Дон Копперсмит (Don Coppersmith). Этот проект был скорее экспериментальным, но стал базисом для Data Encryption Standard (DES). Итеративная структура алгоритма позволяла упростить его реализацию в аппаратных средах.


Алгоритм:

  • блок открытого текста делится на 2 равные части (L0, R0)

  • в каждом раунде вычисляется (i=1..n– номер раунда)

,

где f – некоторая функция, а Ki-1 ключ i-го раунда. Результатом выполнения n раундов является (Ln, Rn) . Но обычно в n-ом раунде перестановка Ln и Rn не производится, что позволяет использовать ту же процедуру и для расшифрования, просто инвертировав порядок использования раундовой ключевой информации:



Шифрование



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


Задание


  1. Написать программу реализующую сеть Фе́йстеля. На вход программы подается произвольный файл (длина файла кратна размеру блока – 64 бита), на выходе файл следующего формата:




Поле

Длина

Описание

SIGNATURA

7

Строка из символов “CRYPBLK1” предназначенная для проверки принадлежности файла данной программе

dbFuncf

1

Тип функции f (номер варианта)

dbRounds

1

Число раундов (1–64)

dbBlockSize

1

Размер блока в битах 16–128 (по умолчанию 64)

dwKeySize

2

Длина ключа в битах (8–2048)

pbSesKey

256

Блоб ключа

dwFileSize

4

Размер файл

PbFile

dwFileSize

Блоб зашифрованого файла

Ключ создается случайным образом и помещается в файл.
^ Порядок и назначение передаваемых параметров в программу

crypt [command] filename

filename – имя файла для дешифрования / шифрования

доступные команды

-e– зашифровать файл

Варианты заданий (определяется согласно порядковому номеру в списке):



Размер блока

Функция f

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

1

64

L+K

3

2

64

LK

7

3

64

L~K

8

4

64

L+~K

2

5

64

crot(L,8)+K

9

6

64

crot(L,8)K

23

7

64

crot(L,-8)+K

43

8

64

crot(L,-8)K

22

9

64

crot(L+~K,1)

55

10

64

crot(L~K,1)

11

11

64

crot(L,1)+K

35

12

64

crot(L,1)K

32

13

64

crot(L,-1)+K

41

14

64

crot(L,-1)K

22

15

64

crot(L+K,1)

27

16

64

crot(LK,1)

17

17

64

L+K+51966

12

18

64

LK+64206

37

19

64

L~K+48879

25

20

64

crot(L,-8)+crot(K,8)

33

Где:

~ – побитовое отрицание (NOT, инверсия битов);

 – сложение по модулю 2а (XOR);

crot(a,b) ­– циклический сдвиг битов числа a на b битов вправо.

Похожие:

Лабораторная работа №4 iconЛабораторная работа № Установка и настройка ос семейства Windows...
Лабораторная работа № Изучение сетевых средств операционной системы ms windows. Диагностика сети средствами операционной системы....
Лабораторная работа №4 iconЛабораторная работа №3 Лабораторная работа №3 " анализ сетевого траффика "
Знакомство со структурой тср/ip-пакетов и с составом его отдельных частей – заголовочной части, блока данных и трейлером
Лабораторная работа №4 iconКонтрольная работа №1 Контрольная работа №2 Лабораторная работа №1...
Для допуска к сдаче экзамена за первый семестр студент должен иметь оценки «зачтено» за все письменные работы этого семестра
Лабораторная работа №4 iconКонтрольная работа №1 Контрольная работа №2 Лабораторная работа №1...
Для допуска к сдаче экзамена за первый семестр студент должен иметь оценки «зачтено» за все письменные работы этого семестра
Лабораторная работа №4 iconЛабораторная работа №5. Эксперимент лабораторная работа №6 Раздел...
Цель: Выявление типов поведения студентов (коллег) в дискуссии (наблюдение по схеме Р. Бейлза)
Лабораторная работа №4 iconЛабораторная работа №1 «Экономическое обоснование нир»
Лабораторная работа № Экономическая оценка нир (Определение текущих затрат на проведение нир)
Лабораторная работа №4 iconЛабораторная работа по теме «Тема 10. Лабораторная работа «Текстовые файлы»
Цель лабораторной работы состоит в изучении средств vb и средств vs для работы с текстовыми файлами
Лабораторная работа №4 iconЛабораторная работа № Групповые политики 50 Лабораторная работа №10....
Предлагаемый лабораторный практикум дополняет лекционный курс по дисциплине «Сетевое администрирование на основе Microsoft Windows...
Лабораторная работа №4 iconЛабораторная работа № Операционная система Microsoft
Лабораторная работа № Операционная система Microsoft Windows и ее стандартные приложения
Лабораторная работа №4 iconЛабораторная работа выполняется на отдельных листах. Первым является...
Студенты выполняют лабораторную работу во внеаудиторное время. Задания по лабораторной работе носят комплексный характер и предполагают...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница