Практическая работа защита инфы

Практическая работа №1. Алгоритм шифрования RSA

Любое ассиметричное шифрование предполагает наличие пары ключей, а именно открытого и закрытого. [ Cкачайте файл, чтобы посмотреть картинку ] Выше представлена схема взаимодействия объектов в ассиметричной системе шифрования. Генератор дает нам пару ключей открытый ([Ea,N]) и закрытый ([Da,N]), открытый ключ передается абоненту который шифрует сообщение и отправляет зашифрованое сообщение (Ea(DATA)) получатель его расшифровывает закрытым ключом ([Da,N]) и получает исходное сообщение. Алгоритм RSA основывается на использовании односторонних функций шифрования которые обладают свойством:
Если x известно, то f(x) вычислить относительно просто
Если y известно, то f(x) вычислить практически невозможно
В основу криптографической системы с открытым ключом RSA положена задача умножения и разложения простых чисел на множители, которая является вычислительно однонаправленной задачей.
Алгоритм создания открытого и закрытого ключей
1. Выбираются 2 простых числа p и q. 2. Вычисляется их произведение N=p*q 3. Вычисляется значение функции Эйлера f(p,q)=(p-1)*(q-1) 4. Выбирается простое число e которое взаимопростое с f(p,q) 5. Выбирается число d удовлетворяющее условию e*d mod f(p,q)=1 6. Пара [e,N] – открытый ключ шифрования 7. Пара [в,N] – закрытый ключ шифрования Пример: шифрование слова БЛОГИ, для начала, создаем пару ключей.
1. p=3 q=11 2. N=33 3. F(p,q)=20 4. D=3 5. 7*3 mod 20 =1, e=7
Шифруем слово
Получаем цифровой эквивалент слова БЛОГИ с помощью вычисления их порядковых номеров в алфавите Цифровой эквивалент = 2(Б) 13(Л) 16(О) 4(Г) 10(И). Шифрование производится по формуле yi=xie mod N, где xi цифровой эквивалент букве, остальные значения получены выше. y1=27 mod 33=128 mod 33= 29 y2=137 mod 33=62748517 mod 33= 7 y3=167 mod 33=268435456 mod 33= 25 y4=47 mod 33=16384 mod 33= 16 y5=107 mod 33=10000000 mod 33= 10 И так мы получили зашифрованное сообщение, теперь нам предстоит его расшифровать это не столь сложная задача когда мы знаем закрытый ключ;
Дешифрация
Расшифрование производится по формуле xi=yid mod N В итоге мы получаем: x1=293 mod 33=24389 mod 33= 2 x2=73 mod 33=343 mod 33= 13 x3=253 mod 33=15625 mod 33= 16 x4=163 mod 33=4096 mod 33= 4 x5=103 mod 33=1000 mod 33= 10 Как видно если сравнить xi c порядковыми номерами букв мы получим слово БЛОГИ.








Практическая работа №2. Алгоритм шифрования Эль-Гамаля
 Схема была предложена Тахером Эль-Гамалем в 1984 году. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и обеспечения аутентификации. Стойкость данного алгоритма базируется на сложности решения задачи дискретного логарифмирования.
Суть задачи заключается в следующем. Имеется уравнение
gx mod p = y.          (8.6)
Требуется по известным g, y и p найти целое неотрицательное число x (дискретный логарифм).
Порядок создания ключей приводится в следующей таблице.
Таблица 8.7. Процедура создания ключей
[ Cкачайте файл, чтобы посмотреть картинку ]
Для шифрования каждого отдельного блока исходного сообщения должно выбираться случайное число k (1 < k < p – 1). После чего шифрограмма генерируется по следующим формулам
a = gk mod p,          (8.7)
b = (yk Т) mod p,          (8.8)
где Т – исходное сообщение;
(a, b) – зашифрованное сообщение.
Дешифрование сообщения выполняется по следующей формуле
T = (b (ax)-1) mod p          (8.9)
или
T = (b ap-1-x) mod p,          (8.10)
где (ax)-1 – обратное значение числа ax по модулю p.
Пример шифрования и дешифрования по алгоритму Эль-Гамаля при k = 7 приведен в таблице, хотя для шифрования каждого блока (в нашем случае буквы) исходного сообщения надо использовать свое случайное число k.
Первая часть шифрованного сообщения – a = 57 mod 23 = 17.
ax = 173 = 4917, (ax)-1 = 5 (4913 * 5 mod 23 = 1) или ap-1-x = 1723-1-3 = 239072435685151324847153.
Таблица 8.8. Пример шифрования по алгоритму Эль-Гамаля (при k = const)
[ Cкачайте файл, чтобы посмотреть картинку ]
Ввиду того, что число k является произвольным, то такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, т.к. у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение Т и ключ не определяют шифртекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины k для шифровки различных сообщений Т и Т’. Если использовать одинаковые k, то для соответствующих шифртекстов (a, b) и (a’, b’) выполняется соотношение b (b’)-1 = Т (Т’)-1 (mod p). Из этого выражения можно легко вычислить Т, если известно Т’.
Пример. Предположим злоумышленник перехватил зашифрованное сообщение С = ((a1, b1), (a2, b2), , (an, bn)), для которого использовалось одно и тоже случайное число k. Он знает один из блоков Ti = f(Ci) или при известном открытом ключе (y, g, p) ему удалось подобрать k’, которое совпало с используемым при шифровании k. Например по второму варианту, для шифрования символа Х (Т' = 22) злоумышленник использовал k’ = 7 (равное k). Тогда, b(X) = b’ = (107 * 22) mod 23 = 9, (b’)-1 = 18. Расшифрование перехваченного сообщения приведено в следующей таблице.

Таблица 8.9. Пример расшифрования перехваченного сообщения
[ Cкачайте файл, чтобы посмотреть картинку ]









































Практическая работа №3.
Электронная подпись на основе алгоритма RSA
Пусть, как и раньше, пользователь А хочет передать пользователю В сообщение, состоящее из нескольких блоков mi. Перед началом сеанса связи абоненты генерируют открытые и закрытые ключи, обозначаемые, как указано в следующей таблице:

Открытый ключ
Закрытый ключ

Пользователь А
NA, dA
eA

Пользователь Б
NБ, dБ


В результате каждый пользователь имеет свои собственные открытый (состоящий из двух частей) и закрытый ключи. Затем пользователи обмениваются открытыми ключами. Это подготовительный этап протокола.
Основная часть протокола состоит из следующих шагов.
Сначала пользователь А вычисляет числа [ Cкачайте файл, чтобы посмотреть картинку ], то есть шифрует сообщение своим закрытым ключом. В результате этих действий пользователь А подписывает сообщение.
Затем пользователь А вычисляет числа [ Cкачайте файл, чтобы посмотреть картинку ], то есть шифрует то, что получилось на шаге 1 открытым ключом пользователя Б. На этом этапе сообщение шифруется, чтобы никто посторонний не мог его прочитать.
Последовательность чисел gi передается к пользователю Б.
Пользователь Б получает gi и вначале вычисляет последовательно числа [ Cкачайте файл, чтобы посмотреть картинку ], используя свой закрытый ключ. При этом сообщение расшифровывается.
Затем Б определяет числа [ Cкачайте файл, чтобы посмотреть картинку ], используя открытый ключ пользователя А. За счет выполнения этого этапа производится проверка подписи пользователя А.
В результате абонент Б получает исходное сообщение и убеждается в том, что его отправил именно абонент А. Данная схема позволяет защититься от нескольких видов возможных нарушений, а именно:
пользователь А не может отказаться от своего сообщения, если он признает, что секретный ключ известен только ему;
нарушитель без знания секретного ключа не может ни сформировать, ни сделать осмысленное изменение сообщения, передаваемого по линии связи.
Схема цифровой подписи RSA
[ Cкачайте файл, чтобы посмотреть картинку ]
Рис. 1.  Общая идея схемы цифровой подписи RSA
Подписание и подтверждение сайтов используют ту же самую функцию, но с различными параметрами. Верификатор сравнивает сообщение и вывод функции для сравнения. Если результат истинен, сообщение принято.
Генерация ключей
Генерация ключей в схеме цифровой подписи RSА точно такая же, как и генерация ключей в криптографической системе RSА. Алиса выбирает два простых числа p и q и вычисляет n = p x q. Алиса вычисляет [ Cкачайте файл, чтобы посмотреть картинку ]. Затем она выбирает e, для общедоступного ключа и вычисляет d для частного ключа, такое, что [ Cкачайте файл, чтобы посмотреть картинку ] Алиса сохраняет d и публично объявляет n и e.
В схеме цифровой подписи RSA. d является частным;. e и. n - общедоступными.
Подписание и проверка
[ Cкачайте файл, чтобы посмотреть ссылку ] показывает схему цифровой подписи RSA.
[ Cкачайте файл, чтобы посмотреть картинку ]
Рис. 2.  Схема цифровой подписи RSA
Подписание. Алиса на основе сообщения создает подпись, используя частный (секретный) ключ, S = Md mod n, и передает сообщение и подпись Бобу.
Проверка. Боб получает М и S. Он применяет общедоступный ключ Алисы к подписи, чтобы создать копию сообщения М' = Se mod n. Боб сравнивает значение М' со значением М. Если два значения совпадают, Боб принимает сообщение. Чтобы доказать правильность этой процедуры, мы применяем критерии проверки:
[ Cкачайте файл, чтобы посмотреть картинку ]
Последняя конгруэнтность справедлива, потому что [ Cкачайте файл, чтобы посмотреть картинку ](см. теорему Эйлера в [ Cкачайте файл, чтобы посмотреть ссылку ]).
Пример
Для безопасности подписи значения p и q должны быть очень большими. Как тривиальный пример, предположим, что Алиса выбирает p = 823 и q = 953 и вычисляет n = 784319. Значение [ Cкачайте файл, чтобы посмотреть картинку ]- 782544. Теперь она выбирает e = 313 и вычисляет d = 160009. В этой точке генерация ключей закончена. Теперь вообразим, что Алиса хочет передать сообщение со значением M = 19070 Бобу. Она использует свой частный ключ 160009 для того, чтобы подписать сообщение:
M = 19070 -> S = (19070160009) mod 784319 = 210625 mod 784319
Алиса передает сообщение и подпись Бобу. Боб получает сообщение и подпись. Он вычисляет
[ Cкачайте файл, чтобы посмотреть картинку ]
Боб принимает сообщение, потому что он проверил подпись Алисы.


Практическая работа №4.
Цифровая подпись на основе алгоритма Эль-Гамаля
Принцип создания и проверки подписи
Алгоритм Эль-Гамаля также можно использовать для формирования цифровой подписи. Группа пользователей выбирает общие параметры Р и А. Затем каждый абонент группы выбирает свое секретное число Хi, 1 < Хi< Р-1, и вычисляет соответствующее ему открытое число [ Cкачайте файл, чтобы посмотреть картинку ]. Таким образом, каждый пользователь получает пару (закрытый ключ; открытый ключ) = (Хi, Yi). Открытые ключи пользователей могут храниться в общей базе системы распределения ключей и при необходимости предоставляться всем абонентам системы.
Сообщение, предназначенное для подписи, должно быть представлено в виде числа, меньшего модуля Р. При большом размере сообщение разбивается на блоки необходимого размера. В некоторых случаях подписывается не само сообщение, а значение хеш-функции от него. В любом варианте цифровая подпись вычисляется в зависимости от некоторого числа m (m < P).
Пусть пользователь 1 хочет подписать свое сообщение цифровой подписью и передать его пользователю 2. В этом случае алгоритм действий следующий.
Первый пользователь выбирает случайное секретное число k, взаимно простое с Р-1, и вычисляет число [ Cкачайте файл, чтобы посмотреть картинку ]
Затем с помощью расширенного алгоритма Евклида необходимо найти значение b в следующем уравнении:
m = (X1 * a +k * b) mod (P-1)
Пара чисел (a, b) будет цифровой подписью сообщения m.
Сообщение m вместе с подписью (a, b) отправляется пользователю 2.
Пользователь 2 получает сообщение m и с использованием открытого ключа первого абонента Y1 вычисляет два числа по следующим формулам: [ Cкачайте файл, чтобы посмотреть картинку ]Если с1 = с2, то цифровая подпись первого пользователя верная. Для подписывания каждого нового сообщения должно каждый раз выбираться новое значение k.
Подписи, созданные с использованием алгоритма Эль-Гамаля, называются рандомизированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будут создаваться разные подписи (a,b), поскольку каждый раз будет использоваться новое значение k. Подписи, созданные с применением алгоритма RSA, называются детерминированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будет создаваться одна и та же подпись.
Пример вычисления и проверки цифровой подписи
Пусть абоненты, обменивающиеся через Интернет зашифрованными сообщениями, имеют следующие общие параметры: Р = 11, А = 7.
Один из пользователей этой системы связи хочет подписать свое сообщение m=5 цифровой подписью, сформированной по алгоритму Эль-Гамаля. Вначале он должен выбрать себе закрытый ключ, например, Х1=3 и сформировать открытый ключ Y1 = 73 mod 11 = 2. Открытый ключ может быть передан всем заинтересованным абонентам или помещен в базу данных открытых ключей системы связи.
Затем пользователь выбирает случайное секретное число k, взаимно простое с Р-1. Пусть k=9 ( 9 не имеет общих делителей с 10 ). Далее необходимо вычислить число
[ Cкачайте файл, чтобы посмотреть картинку ]
После этого с помощью расширенного алгоритма Евклида находится значение b в уравнении:
[ Cкачайте файл, чтобы посмотреть картинку ]
Решением последнего уравнения будет значение b=9.
Таким образом, пара чисел (8, 9) будет цифровой подписью сообщения m=5.
Если любой другой пользователь сети желает проверить цифровую подпись в сообщении, он должен получить из базы данных открытый ключ первого пользователя (он равен 2 ), вычислить два числа с1 и с2 и сравнить их.
[ Cкачайте файл, чтобы посмотреть картинку ]
Так как с1 = с2, то цифровая подпись первого пользователя в сообщения m=5 верная.

Общая идея схемы цифровой подписи RSA Схема цифровой подписи RSA Заголовок 1 Заголовок 3 Заголовок 4 Заголовок 515

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

  • doc 26447960
    Размер файла: 191 kB Загрузок: 0

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