Алгоритм RSA

Шифрование сообщения

Алиса передает свой открытый ключ ( n {\displaystyle n\,} & e {\displaystyle e\,} ) Бобу и держит свой закрытый ключ в секрете. Боб хочет отправить Алисе сообщение M.

Сначала он превращает M в число m {\displaystyle m} меньшее, чем n {\displaystyle n} , используя согласованный обратимый протокол, известный как схема подстановки. Затем он вычисляет шифротекст c {\displaystyle c\,} , соответствующий:

c = m e mod n {\displaystyle c=m^{e}\mod {n}}

Это можно сделать быстро, используя метод экспоненты через квадрат. Затем Боб отправляет Алисе сообщение c {\displaystyle c\,} .

Расшифровка сообщения

Алиса может восстановить m {\displaystyle m\,} из c {\displaystyle c\,} , используя свой закрытый ключ d {\displaystyle d\,} в следующей процедуре:

m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}}}}

Учитывая m {\displaystyle m\,} , она может восстановить исходные отдельные простые числа, применяя китайскую теорему об остатке к этим двум конгруэнциям, получается

m e d ≡ m mod p q {\displaystyle m^{ed}\equiv m{\bmod {pq}}} .

Таким образом,

c d ≡ m mod n {\displaystyle c^{d}\equiv m{\bmod {n}}} .

Рабочий пример

Здесь приведен пример шифрования и расшифровки RSA. Используемые здесь параметры искусственно малы, но вы также можете использовать OpenSSL для генерации и изучения реальной пары ключей.

1. Выберите два случайных простых числа.
2.  : p = 61 {\displaystyle p=61} и q = 53 ; {\displaystyle q=53;} Вычислите n = p q {\displaystyle n=pq\,}
3.  : n = 61 ∗ 53 = 3233 {\displaystyle n=61*53=3233}
4. Вычислите суммарный коэффициент ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)\,}.
5.  : ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120}
6. Выберите e > 1 {\displaystyle e>1} простое 3120.
7.  : e = 17 {\displaystyle e=17}
8. Выберем d {\displaystyle d\,} таким образом, чтобы d e mod ϕ ( n ) ≡ 1 {\displaystyle de{\bmod {\phi (n)}}\equiv 1\,}.
9.  : d = 2753 {\displaystyle d=2753}
10.  : 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {\displaystyle 17*2753=46801=1+15*3120} .

Открытым ключом является ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). Для набивного сообщения m {\displaystyle m\,} функция шифрования c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}} становится:

c = m 17 mod 3 233 {\displaystyle c=m^{17}{\bmod {3}}233\,}

Закрытым ключом является ( n = 3233 {\displaystyle n=3233} , d = 2753 {\displaystyle d=2753} ). Функция расшифровки m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} становится:

m = c 2753 mod 3 233 {\displaystyle m=c^{2753}{\bmod {3}}233\,}

Например, чтобы зашифровать m = 123 {\displaystyle m=123} , мы вычисляем

c = 123 17 mod 3 233 = 855 {\displaystyle c=123^{17}{\bmod {3}}233=855}

Для расшифровки c = 855 {\displaystyle c=855} , мы вычисляем

m = 855 2753 mod 3 233 = 123 {\displaystyle m=855^{2753}{\bmod {3}}233=123}

Оба этих вычисления могут быть эффективно вычислены с помощью алгоритма квадрата и умножения для модульной экспоненты [en].

Вывод уравнения RSA из теоремы Эйлера

RSA можно легко вывести, используя теорему Эйлера и функцию Эйлера для тотализатора.

Начнем с теоремы Эйлера,

m ϕ ( n ) ≡ 1 (mod n ) {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}}}.

мы должны показать, что расшифровка зашифрованного сообщения с помощью правильного ключа даст исходное сообщение. Учитывая набивку сообщения m, шифротекст c вычисляется следующим образом

c ≡ m e ( mod n ) {\displaystyle c\equiv m^{e}{\pmod {n}}}}}

Подставляя в алгоритм расшифровки, мы имеем

c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}}}

Мы хотим показать, что это значение также конгруэнтно m. Значения e и d были выбраны для насыщения,

e d ≡ 1 ( mod ϕ ( n ) ) {\displaystyle ed\equiv 1{\pmod {\phi (n)}}}

То есть, существует некоторое целое число k, такое, что

e d = k × ϕ ( n ) + 1 {\displaystyle ed=k\times \phi (n)+1}

Теперь мы подставляем в зашифрованное и затем расшифрованное сообщение,

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {\displaystyle {\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\\\&\equiv m\times m^{k\phi (n)}\\\\&\equiv m\times \left(m^{\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}}}

Применим теорему Эйлера и получим результат.

m × ( 1 ) k ≡ m (mod n ) {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}}}}

Схемы вставки

При практическом использовании RSA должна сочетаться с некоторой схемой подстановки, чтобы никакие значения M не приводили к небезопасным шифротекстам. RSA, используемый без набивки, может иметь некоторые проблемы:

• Значения m = 0 или m = 1 всегда дают шифротексты, равные 0 или 1 соответственно, что обусловлено свойствами экспоненты.
• При шифровании с малыми шифрующими экспонентами (например, e = 3) и малыми значениями m, (немодульный) результат m e {\displaystyle m^{e}} может быть строго меньше модуля n. В этом случае шифротексты могут быть легко расшифрованы путем извлечения корня eth из шифротекста без учета модуля.
• Шифрование RSA - это детерминированный алгоритм шифрования. В нем нет случайного компонента. Поэтому злоумышленник может успешно провести атаку с выбором открытого текста против криптосистемы. Они могут составить словарь, зашифровав вероятные открытые тексты под открытым ключом и сохранив полученные шифротексты. Затем атакующий может наблюдать за каналом связи. Как только они увидят шифротексты, совпадающие с теми, которые содержатся в их словаре, злоумышленники могут использовать этот словарь для того, чтобы узнать содержание сообщения.

На практике первые две проблемы могут возникнуть при отправке коротких ASCII-сообщений. В таких сообщениях m может быть конкатенацией одного или нескольких символов, закодированных в ASCII. Сообщение, состоящее из одного символа ASCII NUL (числовое значение которого равно 0), будет закодировано как m = 0, что даст шифротекст 0 независимо от того, какие значения e и N используются. Аналогично, один символ ASCII SOH (числовое значение которого равно 1) всегда будет давать шифротекст 1. Для систем, в которых обычно используются небольшие значения e, например 3, все односимвольные сообщения ASCII, закодированные по этой схеме, будут небезопасны, поскольку наибольшее значение m будет равно 255, а 255³ меньше любого разумного модуля. Такие открытые тексты могут быть восстановлены простым извлечением кубического корня из шифротекста.

Чтобы избежать этих проблем, практические реализации RSA обычно внедряют некоторую форму структурированной, рандомизированной подстановки в значение m перед его шифрованием. Эта подстановка гарантирует, что m не попадет в диапазон небезопасных открытых текстов, и что данное сообщение после подстановки будет зашифровано в один из большого числа различных возможных шифртекстов. Последнее свойство может увеличить стоимость атаки по словарю за пределы возможностей разумного злоумышленника.

Такие стандарты, как PKCS, были тщательно разработаны для надежной защиты сообщений перед шифрованием RSA. Поскольку в этих схемах открытый текст m покрывается некоторым количеством дополнительных битов, размер не покрытого битами сообщения M должен быть несколько меньше. Схемы набивки RSA должны быть тщательно разработаны, чтобы предотвратить сложные атаки. Это может быть облегчено предсказуемой структурой сообщения. В ранних версиях стандарта PKCS использовались специальные конструкции, которые позже были признаны уязвимыми для практической адаптивной атаки с выбором шифротекста. Современные конструкции используют безопасные методы, такие как оптимальное асимметричное шифрование (Optimal Asymmetric Encryption Padding, OAEP), для защиты сообщений и предотвращения этих атак. Стандарт PKCS также имеет схемы обработки, разработанные для обеспечения дополнительной безопасности подписей RSA, например, схема вероятностной подписи RSA (RSA-PSS).

Подписание сообщений

Предположим, что Алиса использует открытый ключ Боба, чтобы отправить ему зашифрованное сообщение. В сообщении она может выдавать себя за Алису, но у Боба нет возможности проверить, что сообщение действительно от Алисы, поскольку любой может использовать открытый ключ Боба для отправки ему зашифрованных сообщений. Таким образом, чтобы проверить происхождение сообщения, RSA можно также использовать для подписи сообщения.

Предположим, Алиса хочет отправить Бобу подписанное сообщение. Она создает хэш-значение сообщения, увеличивает его до степени d по модулю n (как при расшифровке сообщения) и прикрепляет его в качестве "подписи" к сообщению. Когда Боб получает подписанное сообщение, он увеличивает подпись до степени e mod n (как и при шифровании сообщения) и сравнивает полученное хэш-значение с реальным хэш-значением сообщения. Если эти два значения совпадают, он знает, что автор сообщения обладал секретным ключом Алисы и что с тех пор сообщение не было подделано.

Обратите внимание, что безопасные схемы подстановки, такие как RSA-PSS, так же важны для безопасности подписания сообщений, как и для их шифрования, и что один и тот же ключ никогда не должен использоваться как для шифрования, так и для подписания.