Размещено на http://www.allbest.ru/

Содержание

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

Выбираются два простых (!) числа p и q

Вычисляется их произведение n=(p*q)

Выбирается произвольное число e (e<n), такое, что

НОД(e,(p-1)(q-1))=1,

то есть e должно быть взаимно простым с числом (p-1)(q-1).

Методом Евклида решается в целых числах (!) уравнение

e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y - метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах.

Два числа (e,n) - публикуются как открытый ключ.

Число d хранится в строжайшем секрете - это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n).

1.1.2 Шифрование/расшифрование

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

Отправитель разбивает свое сообщение на блоки, равные k=[log2(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.

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

ci=((mi)e)modn.

Блоки ci и есть зашифрованное сообщение, и их можно спокойно передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по ci прочесть исходные сообщения mi он не может никак, кроме как полным перебором mi.

А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число d. Достаточно давно была доказана теорема Эйлера, частный случай которой утверждает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство

(x(p-1)(q-1))modn = 1.

Для дешифрования RSA-сообщений воспользуемся этой формулой.

Возведем обе ее части в степень (-y):

(x(-y)(p-1)(q-1))modn = 1(-y)= 1.

Теперь умножим обе ее части на x:

(x(-y)(p-1)(q-1)+1)modn = 1*x = x.

А теперь вспомним как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида d такое, что

e*d+(p-1)(q-1)*y=1,

то есть

e*d=(-y)(p-1)(q-1)+1.

А следовательно в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e*d). Получаем (xe*d)modn = x. То есть для того чтобы прочесть сообщение ci=((mi)e)modn достаточно возвести его в степень d по модулю m:

((ci)d)mod n = ((mi)e*d)mod n = mi.

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

1.2 Алгоритм Эль-Гамаля

1.2.1 Общие сведения

Криптографы со своей стороны вели поиски более эффективных систем открытого шифрования и в 1985 году Т. Эль-Гамаль (США) предложил следующую схему на основе возведения в степень по модулю большого простого числа P.

Задается большое простое число P и целое числоA, 1<A<P. Сообщения представляются целыми числами M из интервала 1<M<P.

1.2.2 Шифрование сообщений

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

абоненты знают числа A и P;

абоненты генерируют независимо друг от друга случайные числа:

Ka, Kb удовлетворяющих условию: 1<K<P получатель вычисляет и передаёт отправителю число B, определяемое последовательностью:

В = AKbmоd(P)

отправитель шифрует сообщение M и отправляет полученную последовательность получателю

C = M * BKamоd(P)

получатель расшифровывает полученное сообщение

D = (AKa)-Kbmоd(P)

M = C * D mоd(P)

В этой системе открытого шифрования та же степень защиты, что для алгоритма RSA с модулем N из 200знаков, достигается уже при модуле P из 150 знаков. Это позволяет в 5-7раз увеличить скорость обработки информации. Однако, в таком варианте открытого шифрования нет подтверждения подлинности сообщений.

1.2.3 Подтверждение подлинности отправителя

Для того, чтобы обеспечить при открытом шифровании по модулю простого числа P также и процедуру подтверждения подлинности отправителя Т. Эль-Гамаль предложил следующий протокол передачи подписанного сообщения M:

абоненты знают числа A и P;

отправитель генерирует случайное число и хранит его в секрете:

Ka удовлетворяющее условию: 1<Ka<P вычисляет и передаёт получателю число B, определяемое последователньостью:

В = AKamоd(P)

Для сообщения M(1<M<P): выбирает случайное число L(1<L<P), удовлетворяющее условию (L, P - 1) = 1 вычисляет число

R = ALmоd(P)

решает относительно S

M=Ka*R+L*S mоd(P)

передаёт подписанное сообщение [M,R,S] получатель проверяет правильность подписи

A M = (BR) * (RS) mоd(P)

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

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

шифрование алгоритм криптозащита

При ведении деловой переписки, при заключении контрактов подпись ответственного лица является непременным атрибутом документа, преследующим несколько целей:

- Гарантирование истинности письма путем сличения подписи с имеющимся образцом;

- Гарантирование авторства документа (с юридической точки зрения)

Выполнение данных требований основывается на следующих свойствах подписи:

- подпись аутентична, то есть с ее помощью получателю документа можно доказать, что она принадлежит подписывающему;

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

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

- Документ с подписью является неизменяемым.

- Подпись неоспорима.

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

Развитие современных средств безбумажного документооборота, средств электронных платежей немыслимо без развития средств доказательства подлинности и целостности документа. Таким средством является электронно-цифровая подпись (ЭЦП), которая сохранила основные свойства обычной подписи.

2.1 Система цифровой подписи Шнорра

Система цифровой подписи Шнорра подобна системе цифровой подписи Эль-Гамаля.

Пусть p - простое число, q - простой делитель (p ?)1, а g - элемент порядка q в GF(p) (степени этого элемента по модулю p порождают q различных элементов поля), 0 < k < q - случайное число, 0 < z < q - секретный ключ, y= mod р - открытый ключ. Уравнения выработки подписи имеют вид

r = modp, e = h(X,r), s = (ze + k)mod q .

Подписью является (e,s). В этом случае получатель вычисляет modp и вычисляет хэш-функцию

e'= h (X,modp).

Если e '=e, то подпись признается корректной.

Цифровые подписи, построенные по системе Шнорра, короче, чем в системе Эль- Гамаля или RSA.

2.2 Стандарт цифровой подписи DSA

Стандарт DSS (Digital Signature Standard) принят в США в 2000 г. Согласно этому стандарту подпись может формироваться по одному из трех алгоритмов:

1. DSA (Digital Signature Algorithm), основанному на проблеме вычисления логарифма в конечном поле.

2. ANSI X9.31 (RSA DSA).

3. ANSI X9.63, основанному на проблеме вычисления логарифма в группе точек эллиптической кривой над конечным полем.

Алгоритм DSA включает следующие этапы

1. Предварительный этап - выбор параметров Выбираются следующие параметры: p - простое число в диапазоне < p< , 512 < l < 1024 - кратно 64, < q< - простой делитель p?1, g - элемент порядка q в GF(p), выбирается в виде , где б - примитивный элемент.

Выбирается секретный ключ 0 < z < q и вычисляется открытый ключ для проверки подписи y=mod р.

2. Формирование цифровой подписи

Вычисляется значение хэш-функции от сообщения h(X) . При этом используется алгоритм безопасного хэширования SHA-1 (Secure Hashing Algorithm). Значение h(X) имеет длину 160 бит. Далее отправитель выбирает случайное значение 0 < k < q и вычисляет modq. Затем вычисляется пара значений

r= (modp)(modq);

s=(h(X)+zr)(mod q).

Пара значений (r,s) является цифровой подписью под сообщением X . После выработки подписи значение k уничтожается. 3. Верификация цифровой подписи

Получатель вычисляет

и сравнивает полученное значение с r. Подпись считается корректной, если полученный результат совпадает с r.

Рассмотрим вычисляемое выражение

При любом уровне стойкости (любой паре чисел p, g от 512 до 1024 бит), числа z, q,r,s имеют длину 160 бит, что сокращает длину цифровой подписи до 320 бит.

3. Практические задания

1. Расшифруйте следующие сообщения, зашифрованные шифром Цезаря, и определите ключ n, 0<n<33, если известно, что исходные сообщения составлены из алфавита

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

ЮВПЛШУХ

Метод Цезаря заключается в том, что каждая буква зашифрованного текста смещается на n количество букв по алфавиту вправо либо влево. В данной задаче ключ n=11 влево.

Ответ: УЧЕБНИК

2. Сложите по модулю 2:

- двоичные числа 10101100 и 11001010 ;

- десятичные числа 15 и 10 ;

- шестнадцатеричные числа 0В 5 и 37.

Примечание: десятичные и шестнадцатеричные числа необходимо сначала перевести в двоичный вид.

Операция сложения по модулю 2 в алгебре и логике называется "исключающее ИЛИ" XOR. При сложении двух двоичных знаков получается 0, если исходные двоичные цифры одинаковы, и 1, если цифры разные.

10101100 XOR 11001010 =01100110

Ответ: 01100110

Переведем десятичные числа в двоичные:

15=1111; 10=1010

1111 ХОR 1010 = 0101

Ответ: 0101

Переведем шестнадцатеричные числа в двоичные

0В 5=000010110101; 37=00110111

10110101 ХОR 00110111=10000010

Ответ: 10000010

Список литературы

1. Баричев С.Г., Гончаров В.В., Серов Р.Е. Основы современной криптографии - [Электронный ресурс] режим доступа: http://www.ict.edu.ru/ft/002447/crypto1-3.pdf

2. Криптография - [Электронный ресурс] режим доступа: (http://www.citforum.ru/internet/securities/crypto.shtml)

3. Криптографические алгоритмы с открытым ключом - [Электронный ресурс] режим доступа: http://argosoft.webservis.ru/Base/RSAintro.html#Криптографические алгоритмы с открытым ключом

4. "Программирование РАН", N 5 (сентябрь-октябрь), 1994, стр. 17-22 [Электронный ресурс] режим доступа: http://www1.tepkom.ru/users/ant/Articles/Pkcstand.html

5. Теоретические основы - Безопасность информационных систем - Криптографические системы - [Электронный ресурс] режим доступа: http://argosoft.webservis.ru/Base/Crypt.html#Механизмы шифрования

6. Совpеменные кpиптогpафические методы защиты инфоpмации - Системы с откpытым ключом [Электронный ресурс] режим доступа: http://ppt.newmail.ru/crypto04.htm#Heading20

Размещено на Allbest.ru