мільйонну частку секунди, нам буде потрібно 10294 років на здійснення операції розшифрування в алгоритмі RSA. p> Однак навіть на нашому невеликому прімерчік легко побачити, як можна було б скоротити кількість множень:
х = 123,2 = х В· х (mod 511) = 310,4 = x2 * x2 (mod 511) = 32,5 = x В· x4 (mod 511) = 359.
Тут нам потрібно було тільки три твори, а не 4, як раніше. Зверніть увагу на те, що двійкове подання числа 5 має вигляд: '101b ', тобто
це тризначне число,
його вага Хеммінга дорівнює h = 2. (Де вага Хемінга кол-во 1 в бінарному представленні числа)
Тому ми виробили 1 = h - 1 множення загального вигляду і 2 = t - 1 зведення в квадрат. Такий підрахунок залишається справедливим і в загальному випадку: зведення в ступінь по модулю цілого числа може бути здійснено за допомогою h - 1 множень і t - 1 зведення в квадрат,
де t - кількість знаків у двійковому поданні показника, ah - його вага Хеммінга. Усереднений вага Хемінга цілого числа дорівнює половині кількості його двійкових знаків, тобто t/2. Тому середнє число множень і возведений в квадрат при обчисленні експоненти в кільці відрахувань одно t + t/2 - 1. Це означає, що при зведенні в 1024-бітову ступінь потрібно не більше 2048 множень, а середнє число операцій і того менше - 1535. p> Метод, за допомогою якого досягається така економія операцій носить спеціальну назву: метод двійкового потенціювання. Працює він, по черзі зчитуючи знаки двійкового подання показника, починаючи з молодшого розряду. br/>
1.3 Формування і перевірка ЕЦП
Вибір параметрів системи:
Вибирається просте p і просте q, таке, що q | p-1 (p? 21024, q> = 2130)
Вибирається елемент?, такий, що? q = 1 (mod p)
Параметри (p, q,?) вільно публікуються
Вибирається параметр t, t> 40 q <2t (t-рівень секретності)
Вибір параметрів доводить боку
Нехай кожна доводить сторона A вибирає секрет a (закритий ключ), такий, що 1 <= a <= q-1 і обчислює v =?-q (mod p), де v-відкритий ключ.
Передані повідомлення: B: x =? r (mod p) B: e (де 1 <= e <= 2t
Основні действіявибірает випадкове r (1
Сторона B відсилає випадкове e з діапазону від 1 до q-1 (виклик) повертає B y = (a * e + r) (mod q) перевіряє, чи дійсно z = x, де z =? r * ve ( mod p) і, якщо це так, то ідентифікація вважається успішною.
Приклад:
Вибирається просте р = 48731 і просте q = 443 ()
Обчислюється? з умови? q = 1 (mod p), в даному випадку? = 11444
Тоді системними параметрами будуть (48731,443,11444), at = 8
Сторона А вибирає закритий ключ a = 357 і обчислює відкритий ключ v =?-a (mod p) = 7355
Сторона А випадковим чином вибирає доказ r = 274 і відсилає x =? r (mod p) = 37123 стороні B
У відсилає A виклик e = 129отсилает B y = (a * e + r) (mod q) = 255...
