Наведемо простий приклад на малих простих числах Р = 211 і Q = 223. У цьому випадку N = 47053 і М = 46620. Виберемо відкритий ключ шифрування D = 16813 і обчислимо секретний ключ розшифрування Е = 19837. Тепер, взявши за повідомлення назву методу RSA, переведемо його в число. Для цього будемо вважати букву R рівній 18, S рівній 19, А рівною 1 за порядковим номером їх положення в англійському алфавіті. На представлення кожної букви відведемо по 5 біт числа, що представляє відкритий текст. У цьому випадку слову RSA відповідає наступне число: = ((1 * 32) +19) * 32 +18 = 1650
За допомогою відкритого ключа отримуємо шифровку:
S '= (S ** D) MOD N = 1650 ** 16813 MOD 47053 = 3071
Одержувач розшифровує її за допомогою секретного ключа:
S = (S '** E) MOD N = 3071 ** 19837 MOD 47053 = 1650
Автори RSA у прикладі зі своєї першої публікації використовували D = 9007 та N = 11438162575788886766923577997614661201021829672124236256256184 29357069352457338978305971235639587050589890751475992900268795 43541.
Прийнявши за вихідний відкритий текст фразу з "Юлія Цезаря" Шекспіра: ITS ALL GREEK TO ME, представлену цілим числом S = 920190001121200071805051100201501305, вони отримали таку
Навіщо наведені ці довгі набори цифр, взяті з книги американського математика Мартіна Гарднера, читач дізнається нижче. Крипостійкість системи RSA заснована на тому, що М не може бути просто обчислена без знання простих співмножників Р і Q, а знаходження цих співмножників з N вважалася важко вирішуваною завданням. Проте недавні роботи з розкладання великих чисел на співмножники показали, що для цього можуть бути використані різні і навіть абсолютно несподівані кошти. Спочатку автори RSA пропонували вибрати прості числа Р і Q випадково, по 50 десяткових знаків кожне. Вважалося, що такі великі числа дуже важко розкласти на прості співмножники при криптоанализе. Райвест вважав, що розкладання на прості множники числа з майже що 130 десяткових цифр, наведеного в їх публікації, зажадає більше 40 квадрильйонів років машинного часу. Але математики Ленстра з фірми Bellcore та Манасію з фірми DEC розклали число з 155 десяткових цифр на прості співмножники всього за 6 тижнів, з'єднавши для цього 1000 ЕОМ, що знаходяться в різних країнах світу. Вибране число, зване дев'ятим числом Ферма, з 1983 року перебувало в списку чисел, розкладання яких вважалося найбільш бажаним. Це число взято тому, що воно вважалося нерозкладним при існуючій обчислювальній техніці і достатньо великим для того, щоб його можна вважати безпечним для формування N в RSA. Як заявив Ленстра, провідний в Bellcore дослідження електронною захисту інформації та розкладанню великих чисел, їх метою було показати розробникам і користувачам криптографічних систем, з якими загрозами вони можуть зустрітися і наскільки обережні повинні бути п...
