Криптосистема Рабіна

У січні 1979 року Міхаель Рабін опублікував опис своєї системи. Було доведено, що відновлення початкового тексту з зашифрованого настільки ж важко, як факторизація великих чисел. Система Рабіна стала першою асиметричною криптосистемою, для якої було виконано такий доказ. Складність відновлення пов'язана з трудністю вилучення квадратного кореня за модулем складеного числа ${\displaystyle N=p\cdot q}$. Завдання факторизації і завдання по вилученню квадратного кореня еквівалентні, тобто:

• знаючи прості дільники числа ${\displaystyle N}$ можна витягувати квадратний корінь по модулю ${\displaystyle N}$;
• вміючи витягувати квадратний корінь по модулю ${\displaystyle N}$, можна розкласти ${\displaystyle N}$ на прості множники.

Система Рабіна, як і будь-яка асиметрична криптосистема, використовує відкритий і закритий ключі. Відкритий ключ використовується для шифрування повідомлень і може бути опублікований для загального огляду. Закритий ключ необхідний для розшифровки і повинен бути відомий тільки одержувачам зашифрованих повідомлень.

Процес генерації ключів наступний:

• вибираються два випадкових числа ${\displaystyle p}$ і ${\displaystyle q}$ з урахуванням таких вимог:
  • числа повинні бути великими (див. розрядність):
  • числа повинні бути простими;
  • повинна виконуватися умова: ${\displaystyle P\equiv Q\equiv 3\mod 4}$.

Виконання цих вимог сильно прискорює процедуру вилучення коренів за модулем р і q;

• обчислюється число ${\displaystyle n=p\cdot q}$;
• число n — відкритий ключ; числа ${\displaystyle p}$ і ${\displaystyle q}$ — закритий.

Приклад. Нехай ${\displaystyle p=7}$ і ${\displaystyle q=11}$. Тоді ${\displaystyle n=p\cdot q=7\cdot 11=77}$. Число ${\displaystyle n=77}$ — відкритий ключ, а числа ${\displaystyle p=7}$ і ${\displaystyle q=11}$ — закритий. Одержувач повідомляє відправникам число 77. Відправники шифрують повідомлення, використовуючи число 77, і відправляють одержувачу. Одержувач розшифровує повідомлення за допомогою чисел 7 і 11. Наведені ключі погані для практичного використання, так як число 77 легко розкладається на прості множники (7 і 11).

Початкове повідомлення m (текст) шифрується за допомогою відкритого ключа — числа n за такою формулою:

c = m² mod n.

Завдяки використанню множення по модулю швидкість шифрування системи Рабина більше, ніж швидкість шифрування за методом RSA, навіть якщо в останньому випадку вибрати невелике значення експоненти.

Приклад (продовження). Нехай вихідним текстом m = 20. Тоді зашифрованим текстом буде: c = m² mod n = 20² mod 77 = 400 mod 77 = 15.

Для розшифровки повідомлення необхідно закритий ключ — числа p і q . Процес розшифровки виглядає наступним чином:

• спочатку, використовуючи алгоритм Евкліда, з рівняння ${\displaystyle y_{p}\cdot p+y_{q}\cdot q=1}$ знаходять числа ${\displaystyle y_{p}}$ і ${\displaystyle y_{q}}$;
• далі, використовуючи китайську теорему про залишки, обчислюють чотири числа:

${\displaystyle {\begin{matrix}r&=&(y_{p}\cdot p\cdot m_{q}+y_{q}\cdot q\cdot m_{p})\,{\bmod {\,}}n\\-r&=&n-r\\s&=&(y_{p}\cdot p\cdot m_{q}-y_{q}\cdot q\cdot m_{p})\,{\bmod {\,}}n\\-s&=&n-s\end{matrix}}}$

Одне з цих чисел є істинним відкритим текстом m .

Приклад (закінчення). В результаті розшифровки отримуємо: ${\displaystyle m\in \{64,\mathbf {20} ,13,57\}}$. Бачимо, що один з коренів є вихідним текстом m .

• Асиметричні алгоритми шифрування
• Ранцева криптосистема Меркле — Геллмана