Что такое алгоритм RSA?

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

Алгоритм RSA назван в честь тех, кто изобрел его в 1978 году: Рон Ривест , Ади Шамир и Леонард Адлеман.

На следующем рисунке показано, как работает асимметричная криптография:

Как это работает

Алгоритм RSA обеспечивает максимальную безопасность ключей на приведенном выше рисунке. Следующие шаги показывают, как это работает:

1. Генерация ключей

  1. Выберите два больших простых числа, x x x и y y y. Простые числа должны быть большими, чтобы их было сложно вычислить.
  2. Вычислить n =x∗y n = x * y n = x ∗ y.
  3. Вычислить totient функция strong> ; ϕ ( n ) = ( x — 1 ) ( y — 1 ) phi (n) = (x-1) (y-1) ϕ (n) = (x − 1) (y − 1).
  4. Выберите целое число e e e, такой что e e e является co-prime в ϕ ( n ) phi (n) ϕ (n) и 1 e ϕ ( n ) 1 1 ( n , e ) (n, e) (n, e) составляет открытый ключ.

Примечание. Два целых числа взаимно просты, если единственное положительное целое число, которое их разделяет, 1.

  1. Вычислить d d d такой, что e . d=1 ed = 1 ed = 1 m o d mod mod ϕ (n) phi (n) аннотация> ϕ (n).

d d d можно найти с помощью расширенного алгоритма Евклида . Пара ( n , d ) (n, d) (n, d) составляет закрытый ключ.

2. Шифрование

Учитывая открытый текст P P P, представленный в виде числа, зашифрованный текст C C C рассчитывается как:

C = P e C = P ^ {e} C = P e m o d мод семантика > mod nn п.

3. Расшифровка

Использование закрытого ключа ( n , d ) (n, d) семантика > (n, d), открытый текст можно найти с помощью:

P = C d P = C ^ {d} P = C d modmod mod nn п.

Псевдокод

Рассмотрим пример алгоритма RSA через следующий псевдокод:

  int x = 61, int y = 53; int n = x * y;//n = 3233  .//вычислить totient, phiint phi = (x-1) * (y-1);//phi = 3120.int e = fin  dCoprime (phi);//найти 'e', ​​которое> 1 и является простым числом с phi.//e = 17 удовлетворяет текущим значениям.//Используя расширенный алгоритм Евклида, найти 'd', который удовлетворяет//это уравнение: d = (1 mod (phi))/e;//d = 2753 для примеров значений. public_key = (e = 17, n = 3233); private_key = (d = 2753, n = 3233);//Учитывая открытый текст P = 123, зашифрованный текст C будет: C = (123 ^ 17)% 3233 = 855; //Для расшифровки зашифрованного текста C: P = (855 ^ 2753)% 3233 = 123;  

Оцените статью
nanomode.ru
Добавить комментарий