Page 18 - 4395

властивості алгоритму (за винятком криптостійкості) проявляються і
при малих р і q, до 2-х знаків. Але и за такого різкого зменшення
обчислювальної роботи при шифруванні і дешифруванні доводиться
мати справу з 4-значними числами, піднесеними до 4-значного

степеня. У цьому випадку звичайні вбудовані функції більшості мов
програмування незастосовні. Необхідно використовувати спеціальні
алгоритми, простішими з яких є бінарні методи.

Бінарний метод ґрунтується на двійковому зображенні
показника степеня. Є два варіанти цього методу залежно від того, як
переглядають біти показника степеня. Перший – бінарний метод
зліва направо, а другий – бінарний метод справа наліво. Зрозуміло,

що перший метод переглядає біти зліва направо, тоді як другий –
справа наліво. Обидва методи та їх порівняльну характеристику
наведено у додатку А.

Створення ключів включає такі завдання:
 визначити два прості числа р і q;
 вибрати е і обчислити d.

Перш за все, розглянемо проблеми, пов'язані з вибором р і q.
Оскільки значення n = p · q буде відоме будь-якому потенційному
супротивникові, для запобігання розкриттю р і q ці прості числа

мають бути вибрані з достатньо великої множини, тобто р і q мають
бути великими числами. З іншого боку, метод, використовуваний для
пошуку великого простого числа, має бути достатньо ефективним.
У даний час невідомі алгоритми, які створюють довільно великі

прості числа. Процедура, яку використовують для цього, вибирає
випадкове непарне число з необхідного діапазону і перевіряє, чи є
воно простим. Якщо число не є простим, то знову вибирається

випадкове число до того часу, поки не буде знайдено просте.
Були розроблені різні тести для визначення того, чи є число
простим. Ці тести є ймовірнісними, тобто тест показує, що дане
число є простим з певною ймовірністю. Незважаючи на це вони

можуть виконуватися таким чином, що зроблять вірогідність
близькою до 1. Якщо n "провалює" тест, то воно не є простим. Якщо
n "пропускає" тест, то n може як бути, так і не бути простим. Якщо n

пропускає багато таких тестів, то можна з високою мірою
достовірності сказати, що n є простим. Це достатньо довга
процедура, але вона виконується відносно рідко: тільки при

створенні нової пари (KU, KR).
На складність обчислень також впливає те, яка кількість чисел

18