Реалізація бродкаст атаки RSA E=3

Припустімо, що ви програміст на Javascript. Тобто ви використовуєте простий ручний RSA для шифрування без доповнення.

Припустімо, що вас можуть змусити тричі зашифрувати один і той самий відкритий текст за трьома різними відкритими ключами. Ви можете; це траплялося.

Тоді зловмисник може тривіально розшифрувати ваше повідомлення за допомогою:

  1. Захоплення будь-яких 3 зашифрованих текстів і відповідних їм pubkeys
  2. Використання CRT для визначення числа, представленого трьома зашифрованими текстами (які є залишками, модифікованими їхніми відповідними pubkeys)
  3. Витягання кубічного кореня з отриманого числа

CRT каже, що ви можете взяти будь-яке число і представити його як комбінацію ряду залишків mod ряду модулів. У випадку трьох залишків ви маєте:

result =
  (c_0 * m_s_0 * invmod(m_s_0, n_0)) +
  (c_1 * m_s_1 * invmod(m_s_1, n_1)) +
  (c_2 * m_s_2 * invmod(m_s_2, n_2)) mod N_012

де

 c_0, c_1, c_2 є трьома відповідними залишками mod
 n_0, n_1, n_2

 m_s_n (for n in 0, 1, 2) є добутком модулів
 ОКРІМ n_n --- де, m_s_1 є n_0 * n_2

 N_012 є добутком усіх трьох модулів

Щоб розшифрувати RSA за допомогою простого кубічного кореня, пропустіть кінцеву операцію модуля; просто візьміть необроблений накопичений результат і возведіть його в кубічний корінь.