Криптосистемы с открытым ключом. Методы ЭЦП

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

Министерство образования и науки Российской Федерации

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

Кафедра автоматики и вычислительной техники

Дисциплина: «Компьютерные модели управления информационными системами»

Работа

Криптосистемы с открытым ключом. Методы ЭЦП

Выполнил:

Кузнецов С.В.

Студент группы ИСС-11 Института МЕиКН

Шифр 4М09

Проверил:

проф. Горбунов В.А.

Вологда

2023



Цель работы: изучить математические методы, положенные в основу СОК, на примере криптосистемы RSA; познакомиться с алгоритмом цифровой подписи.

Теория

Шифрование с открытым ключом (СОК)

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

На основании теоремы Рабина доказано, что разложение на простые множители двух больших чисел эквивалентно раскрытию ключа для шифра RSA и практически невозможно в реальном времени с учетом возможностей современных ЭВМ.

Криптосистема RSA разработана в 1977 году и получила название в честь ее создателей: Рона Ривеста, Ади Шамира и Леонарда Эйдельмана.

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

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

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

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

Рассмотрим один из таких алгоритмов - алгоритм RSA для некоторого пользователя Аi.

Пользователь выбирает пару различных простых чисел pi и gi.

Находит произведение ri = pi*gi и функцию Эйлера ц(ri) -- число взаимно-простых с ri натуральных чисел, меньших ri, включая 0 и 1: ц(ri) = (p-1)(g-1)

Находит открытый ключ сi -- взаимно-простое с ц(ri) и меньшее его.

Находит закрытый ключ di -- произвольное решение сравнения di * ci 1(mod(ц(ri)) и меньшее ц(ri).

Публикует открытый ключ -- пару {сi, ri}, которые доступны для любого пользователя.

Для отправления сообщения w абоненту Ai его нужно зашифровать открытым ключом {сi, ri}: w' = wc (mod ri,) < ri.

Получив сообщение, Аi дешифрует его своим секретным ключом {di, ri}: w = (w)d (mod ri,).

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

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

Алгоритм RSA используется в банковских компьютерных сетях, особенно для работы с удаленными клиентами (обслуживание кредитных карточек). В настоящее время алгоритм RSA используется во многих стандартах, среди которых SSL, S-HHTP, S-MIME, S/WAN, STT и РСТ.

Цифровая (электронная) подпись

Для организации многосторонней секретной связи используется шифр с открытым ключом. Кодирование сообщения А заключается в преобразовании F: А> Ad(modp), где пара (d, p) называется ключом.

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

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

А> (Al)d(mod p) = Ald(mod p) = Adl(mod p) = (Ad)l(mod p) A.

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

Отправитель кодирует сообщение А закрытым ключом С = Ad(mod p) и посылает получателю информацию, т. е. пару (d, p) в виде подписанного сообщения. Получатель, получив это сообщение, декодирует подпись сообщения открытым ключом (l, р), т.е. находит A' = С'(mod p).

Если А = А', то письмо дошло правильно и без помех или оно было отправлено в нешифрованном виде. Если А А', то сообщение при передаче было искажено, т. е. произошла потеря информации.

В теории вычетов доказывается, что при отсутствии помех и выполнения некоторых условий (взаимной простоты чисел d, l, р) результат А = А' достигается всегда.

Практика

Задача1: Используя открытый ключ {3,22} и закрытый ключ {7,22} зашифровать и расшифровать слово МОСКВА:

Заменим буквы алфавита цифрами, соответствующими их порядковому номеру в алфавите, исключив буквы Ё и Ъ. Получим сообщение:

МОСКВА = (13, 15, 18, 11, 3, 1)

Зашифруем сообщение с помощью открытого ключа {3, 22} для того, чтобы послать его абоненту А.

Используем преобразование:

w' = wc (mod ri,) < ri.

w'1 = (133)(mod22) = 2197mod22 = 19

w'2 = (153)(mod22) = 3375mod22 = 9

w'3 = (183)(mod22) = 5832mod22 = 2

w'4 = (113)(mod22) = 1331mod22 = 11

w'5 = (33)(mod22) = 27mod22 = 5

w'6 = (13)(mod22) = 1mod22 = 1

Получили сообщение w' = (19, 9, 2, 11, 5, 1).

Абонент A расшифрует это сообщение (19, 9, 2, 11, 5, 1) с помощью закрытого ключа {7, 22}:

Используем преобразование: w = (w)d (mod ri,).

w''1 = (197)(mod22) = 893871739mod22 = 13

w''2 = (97)(mod22) = 4 782 969mod22 = 15

w''3 = (27)(mod22) = 128mod22 = 18

w''4 = (117)(mod22) = 19487171mod22 = 11

w''5 = (57)(mod22) = 78125mod22 = 3

w''6 = (17)(mod22) = 1mod22 = 1

Проверим результат из условия: w = w

(13, 15, 18, 11, 3, 1) > МОСКВА

Задача 2: Зашифровать и расшифровать сообщения согласно варианту 8:

№ варианта	Исходные данные (простые числа p и g)		Сообщение
3	p = 5, g = 17	А) ТЕОРИЯ Б) СЫЩИК	В) Криптография изучает методы шифрования

Имеем pi =5,gi = 17. Тогда ri = 5 * 17 = 85, ц(ri) = (5-1)(17-1) = 64.

Выберем в качестве сi число, взаимно-простое с 64 - сi = 3.

Выберем di из сравнения (3 * di) l(mod 64). Таким (минимальным) числом является d i =43. Получили открытый ключ {сi, ri} - {3, 85}, закрытый ключ {di, ri} - {43, 85},

Заменим буквы алфавита цифрами, соответствующими их порядковому номеру в алфавите, исключив буквы Ё и Ъ. Получим сообщения:

А) ТЕОРИЯ > (19, 6, 15, 17, 9, 31);

Б) СЫЩИК > (18, 28, 26, 9, 11);

В) Криптография изучает методы шифрования > (11, 17, 9, 16, 19, 15, 4, 17, 1, 21, 9, 31), (9, 8, 20, 24, 1, 6, 19), (13, 6, 19, 15, 5, 28), (25, 9, 21, 17, 15, 3, 1, 14, 9, 31).

Зашифруем сообщения с помощью открытого ключа {3, 85}.

Используем преобразование: w' = wc (mod ri,) < ri.

A) w'1 = (193)(mod85) = 6859mod85 = 59, w'2 = (63)(mod85) = 216mod85= 46, w'3 = (153)(mod85) = 3375 mod85 = 60. w'4 = (173)(mod85) = 4913mod85 = 68.

w'5 = (93)(mod85) = 729 mod85 = 49. w'6 = (313)(mod85) = 29791 mod85 = 41.

Получили сообщение w' = (59, 46, 60, 68, 49, 41).

Б) w'1 = (183)(mod85) = 5832mod85 = 52, w'2 = (283)(mod85) = 21952mod85= 22, w'3 = (263)(mod85) = 17576 mod85 = 66. w'4 = (93)(mod85) = 729 mod85 = 49. w'5 = (113)(mod85) = 1331mod85= 56.

Получили сообщение w' = (52, 22, 66, 49, 56)

В) w1'1 = (113)(mod85) = 1331mod85= 56, w1'2 = (173)(mod85) = 4913mod85 = 68, w1'3 = (93)(mod85) = 729 mod85 = 49. w1'4 = (163)(mod85) = 4096 mod85 = 16. w1'5 = (193)(mod85) = 6859mod85 = 59. w1'6 = (153)(mod85) = 3375 mod85 = 60. w1'7 = (43)(mod85) = 64mod85= 64. w1'8 = (173)(mod85) = 4913mod85 = 68. w1'9 = (13)(mod85) = 1mod85= 1. w1'10 = (213)(mod85) = 9261mod85= 81. w1'11 = (93)(mod85) = 729 mod85 = 49. w1'12 = (313)(mod85) = 29791 mod85 = 41.

Получили сообщение w1' = (56, 68, 49, 16, 59, 60, 64, 68, 1, 81, 49, 41).

w2'1 = (93)(mod85) = 729 mod85 = 49, w2'2 = (83)(mod85) = 512mod85= 2, w2'3 = (203)(mod85) = 8000 mod85 = 10. w2'4 = (243)(mod85) = 13824 mod85 = 54. w2'5 = (13)(mod85) = 1mod85= 1. w2'6 = (63)(mod85) = 216mod85= 46.

w2'7 = (193)(mod85) = 6859mod85 = 59.

Получили сообщение w2' = (49, 2, 10, 54, 1, 46, 59).

w3'1 = (133)(mod85) = 2197mod85 = 72

w3'2 = (63)(mod85) = 216mod85= 46

w3'3 = (193)(mod85) = 6859mod85 = 59.

w3'4 = (153)(mod85) = 3375 mod85 = 60.

w3'5 = (53)(mod85) = 125mod85= 40.

w3'6 = (283)(mod85) = 21952mod85= 22.

Получили сообщение w3' = (72, 46, 59, 60, 40).

w4'1 = (253)(mod85) = 15625mod85 = 70,

w4'2 = (93)(mod85) = 729 mod85 = 49,

w4'3 = (213)(mod85) = 9261 mod85 = 81.

w4'4 = (173)(mod85) = 4913mod85 = 68.

w4'5 = (153)(mod85) = 3375 mod85 = 60.

w4'6 = (33)(mod85) = 27mod85= 27.

w4'7 = (13)(mod85) = 1mod85= 1.

w4'8 = (143)(mod85) = 2744mod85= 24.

w4'9 = (93)(mod85) = 729 mod85 = 49.

w4'10 = (313)(mod85) = 29791 mod85 = 41.

Получили сообщение w4' = (70, 49, 81, 68, 60, 27, 1, 24, 49, 41).

Расшифруем полученные коды сообщений с помощью закрытого ключа {43, 85}:

Используем преобразование: w = (w)d (mod ri,).

А) w1 = (5943)(mod 85) = 19,

w2 = (4643)(mod 85) = 6,

w3 = (6043)(mod 85) = 15,

w4 = (6843)(mod 85) = 17,

w5 = (4943)(mod 85) = 9,

w6 = (4143)(mod 85) = 31.

Проверим результат из условия: w = w

(19, 6, 15, 17, 9, 31) > ТЕОРИЯ

Б) w''1 = (5243)(mod85) = 52,

w''2 = (2243)(mod85) = 22,

w''3 = (6643)(mod85) = 66.

w''4 = (4943)(mod85) = 49.

w''5 = (5643)(mod85) = 56.

Проверим результат из условия: w = w

(52, 22, 66, 49, 56) > СЫЩИК

В) w1'1 = (5643)(mod85) = 11,

w1''2 = (6843)(mod85) = 17,

w1''3 = (4943)(mod85) = 9.

w1''4 = (1643)(mod85) = 16.

w1''5 = (5943)(mod85) = 19.

w1''6 = (6043)(mod85) = 15,

w1''7 = (6443)(mod85) = 4,

w1''8 = (6843)(mod85) = 17.

w1''9 = (143)(mod85) = 1.

w1''10 = (8143)(mod85) = 21.

w1''11 = (4943)(mod85) = 9,

w1''12 = (4143)(mod85) = 31.

w2''1 = (2943)(mod85) = 9,

w2''2 = (243)(mod85) = 8,

w2''3 = (1043)(mod85) = 20.

w2''4 = (5443)(mod85) = 24.

w2''5 = (143)(mod85) = 1.

w2''6 = (4643)(mod85) = 6,

w2''7 = (5943)(mod85) = 19.

w3''1 = (7243)(mod85) = 13,

w3''2 = (4643)(mod85) = 6,

w3''3 = (5943)(mod85) = 19.

w3''4 = (6043)(mod85) = 15.

w3''5 = (4043)(mod85) = 5.

w3''6 = (2243)(mod85) = 28.

w4''1 = (7043)(mod85) = 25,

w4''2 = (4943)(mod85) = 9,

w4''3 = (8143)(mod85) = 21.

w4''4 = (6843)(mod85) = 17.

w4''5 = (6043)(mod85) = 15.

w4''6 = (2743)(mod85) = 3,

w4''7 = (143)(mod85) = 1,

w4''8 = (2443)(mod85) = 14.

w4''9 = (4943)(mod85) = 9.

w4''10 = (4143)(mod85) = 31.

Проверим результат из условия: w = w

(11, 17, 9, 16, 19, 15, 4, 17, 1, 21, 9, 31), (9, 8, 20, 24, 1, 6, 19), (13, 6, 19, 15, 5, 28), (25, 9, 21, 17, 15, 3, 1, 14, 9, 31) > Криптография изучает методы шифрования

Задание 3: Зашифруем сообщение «Россия» напарнику.

Возьмем pi =2, gi = 11. Тогда ri = 2 * 11 = 22, ц(ri) = (3-1)(11-1) = 10.

Выберем в качестве сi число, взаимно-простое с 20 - сi = 3.

Выберем di из сравнения (3 * di) l(mod 20). Таким (минимальным) числом является d i = 7. Получили открытый ключ {сi, ri} - {3, 22}, закрытый ключ {di, ri} - {7, 22}.

Заменим буквы алфавита цифрами, соответствующими их порядковому номеру в алфавите. Получим следующие коды:

РОССИЯ > (17, 15, 18, 18, 9, 31)

Зашифруем сообщения с помощью открытого ключа {3, 22}.

Используем преобразование: w' = wc (mod ri,) < ri.

w'1 = (173)(mod22) = 4913mod22 = 7,

w'2 = (153)(mod22) = 3375mod22= 9,

w'3 = (183)(mod22) = 5832 mod22 = 2.

w'4 = (183)(mod22) = 5832 mod22 = 2.

w'5 = (93)(mod22) = 729 mod22 = 3.

w'6 = (313)(mod22) = 29791 mod22 = 3.

Получили сообщение w' = (7, 9, 2, 2, 3, 3).

Расшифруем полученные коды сообщений с помощью закрытого ключа {7, 22}:

Используем преобразование: w = (w)d (mod ri,).

w1 = (77)(mod 22) = 823543mod22 = 17,

w2 = (97)(mod 22) = 4782969mod22 = 15,

w3 = (27)(mod 22) = 128mod22 = 18,

w4 = (27)(mod 22) = 128mod22 = 18,

w5 = (37)(mod 22) = 2187mod22 = 9,

w6 = (37)(mod 22) = 2187mod22 = 9.

Проверим результат из условия: w = w

(17, 15, 18, 18, 9, 31) > РОССИЯ



Вывод

криптосистема цифровой подпись

Я изучил теоретический и практический материал по математические методам, заложенным в основу СОК, на примере криптосистемы RSA; познакомился с алгоритмом цифровой подписи.

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