ти прості числа Р і Q випадково, по 50 десяткових знаків кожне. Вважалося, що такі великі числа дуже важко розкласти на прості співмножники при криптоанализе. Райвест вважав, що розкладання на прості множники числа з майже що 130 десяткових цифр, наведеного в їх публікації, зажадає більше 40 квадрильйонів років машинного часу. Але математики Ленстра з фірми Bellcore та Манасію з фірми DEC розклали число з 155 десяткових цифр на прості співмножники всього за 6 тижнів, з'єднавши для цього +1000 ЕОМ, що знаходяться в різних країнах світу. Вибране число, зване дев'ятий числом Ферма, з 1983 року перебувало в списку чисел, розкладання яких вважалося найбільш бажаним. Це число взято тому, що воно вважалося нерозкладним при суще?? твующей обчислювальній техніці і достатньо великим для того, щоб його можна вважати безпечним для формування N в RSA. Як заявив Ленстра, провідний в Bellcore дослідження по електронній захисту інформації та розкладанню великих чисел, їх метою було показати розробникам і користувачам криптографічних систем, з якими загрозами вони можуть зустрітися і наскільки обережні повинні бути при виборі алгоритмів шифрування. На думку Ленстра та Манасії, їхня робота компрометує і створює велику загрозу застосуванням криптографічних систем RSA.
Слід врахувати, що робота з удосконалення методів і техніки розкладання великих чисел тільки почалася і буде продовжена. Ті ж Ленстра та Манасію в 1991 році знайшли дільник тринадцятого числа Ферма, яке складається приблизно з 2500 десяткових розрядів. Тепер розробникам криптографічних алгоритмів з відкритим ключем на базі RSA доводиться, як чуми уникати застосування розкладені чисел довжиною менш 200 десяткових розрядів. Найостанніші публікації пропонують для цього застосовувати числа в 250 і навіть 300 десяткових розрядів. А так як для шифрування кожного блоку інформації доводиться відповідне число зводити в колосально велику ступінь по модулю N, то для сучасних комп'ютерів це завдання на межі можливого. Тому для практичної реалізації шифрування RSA радіоелектроніки почали розробляти спеціальні процесори, які дозволили б виконувати операції RSA досить швидко. Кращими з серійно випускаються кристалів є процесори фірми CYLINK, які дозволяють виконувати зведення в ступінь цілого числа з 307 десяткових знаків за частки секунди.
10.1 Шифр ??ЕльГамаля
криптографії постійно вели пошуки більш ефективних систем відкритого шифрування, і в 1985 році ЕльГамаль запропонував наступну схему на основі піднесення до степеня за модулем великого простого числа. Для цього задається велике просте число Р. Повідомлень представляються цілими числами S з інтервалу (1, Р). Оригінальний протокол передачі повідомлення S виглядає у варіанті Шаміра, одного з авторів RSA, так:
. Відправник А і одержувач В знають лише Р. А генерує випадкове число X з інтервалу (1, Р) і В теж генерує випадкове число Y з того ж інтервалу.
. А шифрує повідомлення Si=Sx MOD P і посилає В.
. У шифрує його своїм ключем 82=8/MOD P і посилає 82 до А.
. А знімає свій ключ S3=S2 x MOD P і повертає 83 до В.
. Одержувач В розшифровує повідомлення: S=S3" Y MOD P.
Цей протокол можна застосувати, наприклад, для таких несподіваних цілей, як гра в очко або блекджек по телефону. Круп'є шифрує карти своїм ключем і передає їх гравцеві. Гравець вибирає навмання одну з карт, шифрує карти своїм ключем і повертає їх круп'є. Круп'є знімає з обраної карти свій ключ і відсилає її гравцеві. Знявши з цієї картки свій ключ гравець дізнається її номінал і приймає рішення: спасувати, тягнути ще або розкриватися. Тепер, хоча колода знаходиться у круп'є, але він не може її розкрити, так як карти зашифровані ключем гравця. Круп'є вибирає свою карту аналогічно гравцеві. В системі ЕльГамаля велика ступінь захисту, ніж у алгоритму RSA досягається з тим же за розміром N, що дозволяє майже на порядок збільшити швидкість шифрування і розшифрування. Крипостійкість системи ЕльГамаля заснована на тому, що можна легко обчислити ступінь цілого числа, тобто призвести множення його самого на себе будь-яке число раз так само, як і при операціях зі звичайними числами. Однак важко знайти показник ступеня, в яку потрібно звести задане число, щоб отримати інше, теж задане. У загальному випадку ця задача дискретного логарифмування здається більш важкою, ніж розкладання великих чисел на прості співмножники, на підставі чого можна припустити, що складнощі розтину систем RSA і ЕльГамаля будуть схожими. З точки зору практичної реалізації, як програмним, так і апаратним способом відчутної різниці між цими двома стандартами немає. Однак у криптостійкості вони помітно різняться. Якщо розглядати завдання розкладання довільного цілого числа довжиною в 512 біт на прості множники і задачу ...
