Алгоритм шифрования rsa

Алгоритм шифрования RSA
Самой первой криптосистемой с открытым ключом из предложенных в открытой литературе (1978 г.), была система Райвеста, Шамира и Эдлмана. Она стала известна под названием RSA. Схема RSA получила самое широкое признание и реализована практически во всех приложениях шифрования с открытым ключом. RSA представляет собой блочный шифр, в котором открытый и шифрованный текст представляется целыми числами из диапазона от 0 до n-1 для некоторого n.
Рассмотрим как работает этот алгоритм [CRYP05].
Выбор p, q. Чтобы зашифровать и расшифровать что-то, необходима пара ключей — открытый и личный. Для того чтобы их изготовить, понадобится пара простых чисел p и q. Простыми называются числа, которые делятся без остатка только на себя и на единицу. Число 11 — простое, а 4 — нет, так как делится кроме единицы и четверки еще и на 2. Итак, выбираем пару простых чисел p=3, q=7.
Вычисление n. Следующий этап в изготовлении ключей — полу­чение числа n, равного произведению p и q: n=p*q=3*7=21. Это число называют модулем сравнения при шифровании и расшифровке.
Вычисление Φ (n). Теперь нужно вычислить величину Φ (n), называемую функцией Эйлера по формуле: (p-1)*(q-1)=2*6=12. Это число не простое, и его в нашем случае можно разложить на простые множители _(n)=12=2*2*3.
Выбор e. Следующий шаг — подбор числа е, которое должно соответствовать двум критериям: быть меньше n и не иметь общих множителей с Φ (n), то есть в разложении на простые множители числа e не должно быть ни двойки, ни тройки. Этим требованиям удовлетворяет число 5 — оно меньше n, и к тому же простое, то есть ни на какие сомножители не разлагается. Итак, е=5.
Вычисление d. И последнее, надо найти число d такое, что e*d-1 делится _ (n). Тогда получается, что d=17, то есть e*d-1=5*17-1=84, а 84/12=7 — то есть действительно делится.
Открытый и личный ключ. Теперь у нас есть и открытый ключ, пара чисел (n,e) — (21,5), и пара чисел (n,d) — (21,17) — личный ключ.
Открытый текст. Далее предположим, что эта пара принадлежит Серёге. Натали, обладая серёгиным открытым ключом, может послать ему в зашифрованном виде количество стуков в дверь — число 3.