Статья Автор: Лебедев Дмитрий

Шифрование RSA. Основные этапы

Поясним на примере основные моменты шифрования с открытым ключем.
Пусть абонент Винни  передает сообщение абоненту Пяточок.
1. Абонент Пяточок выбирает два различных простых числа \(p,\ q\)  и полагает \(n=p\cdot q\)
(для примера положит \(p=13, q=17 => n=13\cdot17=221\))
2.1 Абонент Пятачок находит значение функции Эйлера \(\varphi(n)\). 
(Функция Эйлера - количество натуральных чисел, меньших \(n\) и взаимно простых с \(n\).
В нашем случае \(\varphi(n)=(p-1)\cdot(q-1)=12\cdot16=192\) )
2.2 Абонент Пятачок выбирает число \(e, 0<e<\varphi(n)\ такое,\ что\ (e,\varphi(n))=1 \), то есть
\(e,\varphi(n)\) взаимнопросты.
Число \(192=2^6\cdot3\), поэтому выбор у Пяточка большой (любое нечетное и некратное 3 число от 1 до 191)
Пусть это будет число 101.
Пару чисел \((n,e) = (221,101)\)  абонент Пятачок объявлет открытым ключом.
2.3 Для пары чисел \((n,e) \) абонент Пятачок находит число \(d\ такое,\ что\ d\cdot e\ \equiv\ 1\ (mod\ \varphi(n))\) 
Значение числа d объявляется секретным ключом.
Задача нахождения числа d по значениям чисел n,e достаточно трудоемкая и решается с помощью 
расширенного алгоритма Евклида. Для небольших значений n, e значение числа d можно определить простым перебором.
Напишите фрагмент программы, которая находит значение d по значениям n,e (n,e не превосходят 1000) 


3. Абонент Винни задает сообщение \(m,\ 0\ \leq\ m\ \leq\ n-1, \) создает шифрованное сообщение \(E(m)\ \equiv m^e\ (mod\ n)\)
и посылает его по открытому каналу связи Пяточку.
Напишите программу, которая по значениям чисел n,e и m определяет значение E(m). 
Определите значение E(32) для n=221, e=101
Для решения задачи воспользуйтесь стандарной функцией pow, которая при вызове 
pow(m,e,n) возвращает значение me % n


4. Абонент Пятачок с помощью секретного ключа d дешифрируе его следующим образом
\(D(E(m))\ \equiv\ (m^e)^d\ \equiv m^{ed}\ \equiv \ m \ (mod\ n)\)
Напишите код программы, которая проверяет правильность работы
алгоритма шифрования с открытым ключом.


Для доказательство правильности работы  работы алгоритма с открытым ключом (RSA) достаточно установить, что
\(D(E(m))\ \equiv\ m\ или\ m^{ed}\ \equiv\ m\ (mod\ n) \)
Это доказывается с использованием условий, наложенных на p,q,n,e,d, теоремы Эйлера и малой теоремы Ферма.
Заметим, что секретным ключом является наборчисел \((p,\ q,\ \varphi(n),\ d)\), а открытый ключ составляет пара чисел \((n,\ e)\)
Напишите программу, которая по значениям  p,q получает "словарь шифрования" D:
 \(\begin{cases} {D[m]=E(m),\ если\ 0\leq m<p\cdot q\\ D[p\cdot q]=e -\ открытый\ ключ} \end{cases}\)
Надо написать только код подпрограммы RSA(p,q), возвращающей "словарь шифрования"
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать