Самой первой криптосистемой с открытым ключом из предложенных в открытой литературе (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.

Шифрование. Пусть m=3. Чтобы зашифровать это число, Натали должна проделать вычисления согласно формуле:

c=m^emodn, где m — шифруемое сообщение, (n,e) — открытый ключ Серёги, с — зашифрованное сообщение.

В нашем случае m^e = 3⁵ =243. Тогда с=243 mod 21. Это есть остаток от деления 243 на 21 и равный 12. Итак, зашифрованное число стуков в дверь равно 12. Вот его посылаем Серёге.

Расшифровка. Для расшифровки сообщения Серёга использует формулу:

m=c^dmodn, где с — зашифрованное сообщение, m — расшифрованное сообщение, (n,d) — личный ключ Серёги (21,17).

Чтобы расшифровать сообщение, придется возвести с в 17-ю степень 12¹⁷ = 2218611106740436992.

Колоссальное число, но остаток от деления 2218611106740436992 на 21 равно 3 — Серега расшифровал сообщение от Натали.

Открытый текст. Теперь идя к ней в гости, он знает сколько раз ему стучать в дверь – три раза.