Шифрование методом RSA.

Шифрование c открытым ключом

RSA (Rivest-Shamir-Adleman)

Алгоритм RSA -- ассиметричный, т. е. для шифрования и расшифрования используются разные ключи. Любой из ключей может быть открытым, т. е. кто угодно сможет зашифровать текст, но расшифровать -- только тот, кто знает секретный или, наоборот, прочитать текст может каждый, но зашифровать -- только один человек (системы подтверждения подлинности; программы, зашифрованный код которых нельзя изменить, даже зная алгоритм шифрования).

Вот краткое изложение алгоритма:

1. Выбираются два простых числа -- P и Q;
2. N := P * Q;
3. M := (P-1) * (Q-1);
4. Выбирается число D, взаимно простое с M, т. е. НОД(D,M) = 1;
5. Выбирается число E, так чтобы (E * D) = 1 (mod M);
6. Теперь пара (E,N) -- открытый ключ, (D,N) -- закрытый.

Шифрование происходит так:

1. Данные разбиваются на блоки (С) , каждый из которых может быть представлен числом от 0 до N-1;
2. Для шифрования полагаем C := (B^E) mod N;
3. Для дешифрования полагаем B := (C^D) mod N.

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

Так как криптостойкость основана сложности разложения на множители, рекомендуется использовать в качестве ключей достаточно большие числа -- 256--512 двоичных разрядов. В альтернативном методе шифрования DES для достижения надежности необходимо применять около 700 двоичных разрядов.

На сегодняшний день RSA является самым распространенным криптографическим алгоритмом с открытым ключом.

См. также Шифрование с открытым ключом