Реалізація RSA

У реалізації RSA є дві неприємні речі. Обидві вони включають генерацію ключів; фактичне шифрування/дешифрування в RSA тривіальне.

По-перше, вам потрібно згенерувати випадкові прості числа. Ви не можете просто домовитися про просте число заздалегідь, як у DH. Ви можете написати цей алгоритм самостійно, але я просто змухлюю та використовую для роботи бібліотеку BN від OpenSSL.

По-друге, вам потрібна операція “invmod” (мультиплікативна інверсія), яка не є операцією, яка вшита в вашу мовою. Алгоритм складається лише з пари рядків, але я завжди втрачаю годину, щоб змусити його запрацювати.

Я рекомендую вам не турбуватися про primegen, але знайдіть час, щоб ваш власний алгоритм EGCD та invmod запрацював.

Тепер:

Згенеруйте 2 випадкових простих числа. Для початку ми використаємо невеликі числа, щоб ви могли просто вибрати їх із таблиці простих чисел. Назвіть їх «p» і «q».
Нехай n дорівнює p * q. Ваша математика RSA є модулем n.
Нехай et буде (p-1)*(q-1) (“totient”). Це значення потрібне лише для кейгена.
Нехай e дорівнює 3.
Обчисліть d = invmod(e, et). invmod(17, 3120) дорівнює 2753.
Ваш відкритий ключ [e, n]. Ваш закритий ключ [d, n].
Для шифрування: c = m ** e%n. Щоб розшифрувати: m = c ** d%n
Перевірте це числом, наприклад «42».
Повторіть з великими простими числами (збережіть e=3).

Нарешті, щоб зашифрувати рядок, зробіть щось дивне, наприклад перетворіть рядок у шістнадцяткову форму та поставте «0x» на її початку, щоб перетворити її на число. Математиці байдуже, наскільки тупо ви її годуєте.