Якщо S - повідомлення, довжина якого, обумовлена ??за значенням виражається їм цілого числа, повинна бути в інтервалі (1, N), то воно перетворюється на шифровку зведенням у ступінь D по модулю N і відправляється одержувачу S '= (S ** D) MODN.
. Отримувач повідомлення розшифровує його, зводячи в ступінь Е за модулем N, так як S=(S ** E) MOD N=(S ** (D * E)) MOD N.
Таким чином, відкритим ключем служить пара чисел NіD, а секретним ключем число Є. Сенс цієї системи шифрування стає прозорим, якщо згадати про малу теорему Ферма, яка стверджує, що при простому числі Р і будь-якому цілому числі К, яке менше Р, справедливо тотожність До ** (P - 1)=1 MOD Р. Ця теорема дозволяє визначати, чи є якесь число простим або ж складеним.
Крипостійкість системи RSA заснована на тому, що Мені може бути просто обчислена без знання простих співмножників Р і Q, а знаходження цих співмножників з N вважалася важко вирішуваною завданням. Проте недавні роботи з розкладання великих чисел на співмножники показали, що для цього можуть бути використані різні і навіть абсолютно несподівані кошти.
Слід врахувати, що робота з удосконалення методів і техніки розкладання великих чисел тільки почалася і буде продовжена. Для практичної реалізації шифрування RSA радіоелектроніки почали розробляти спеціальні процесори, які дозволили б виконувати операції RSA досить швидко. Кращими з серійно випускаються кристалів є процесори фірми CYLINK, які дозволяють виконувати зведення в ступінь цілого числа з 307 десяткових знаків за частки секунди. Надзвичайно слабке швидкодію криптографічних систем на основі RSA лише обмежує область їх застосування, але зовсім не перекреслює їх цінність. [4]
.2 Шифр ??Ель Гамаля
криптографія постійно вели пошуки більш ефективних систем відкритого шифрування, і в 1985 році Ель Гамаль запропонував наступну схему на основі піднесення до степеня за модулем великого простого числа. Для цього задається велике просте число Р. Повідомлення представляються цілими числами S з інтервалу (1, Р). Оригінальний протокол передачі повідомлення S виглядає у варіанті Шаміра, одного з авторів RSA, так:
. Відправник А і одержувач В знають лише Р. А генерує випадкове число Х з інтервалу (1, Р) і В теж генерує випадкове число Y з того ж інтервалу.
. А шифрує повідомлення S1=S ** X MOD Р і посилає В.
. У шифрує його своїм ключем S2=S1 ** Y MOD Р і посилає S2 до А.
. А «знімає» свій ключ S3=S2 ** (-X) MOD Р і повертає S3 до В.
. Одержувач В розшифровує повідомлення: S=S3 ** (-Y) MOD Р.
В системі Ель Гамаля велика ступінь захисту, чому алгоритму RSA досягається з тим же за розміром N, що дозволяє майже на порядок збільшити швидкість шифрування і розшифрування. Крипостійкість системи Ель Гамаля заснована на тому, що можна легко обчислити ступінь цілого числа, тобто призвести множення його самого на себе будь-яке число раз так само, як і при операціях із звичайними числами. Однак важко знайти показник ступеня, в яку потрібно звести задане число, щоб отримати інше, теж задане. У загальному випадку ця задача дискретного логарифмування здається більш важкою, ніж розкладання великих чисел на прості співмножники, на підставі чого можна припустити, що с...
