ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 2334
Скачиваний: 1
91
Ці числа називаються тривіальними коріннями з одиниці за модулем n.
Розглянемо, наприклад, Z
7
*
= { 1, 2, 3, 4, 5, 6 }.
Зворотним елементом до 2
буде 4, тобто 2
-1
= 4 mod7,
оскільки 2*4 = 8 mod7 = 1.
Зворотним елементом до 3 буде 5, тобто 3
-1
= 5 mod7,
оскільки 3*5 =15 mod7 = 1.
12.2
Ступені елементів в Zn* і пошук великих простих чисел
Оскільки групова операція множення за модулем (*modn) застосована до
будь-якої пари чисел з Zn*, то можна визначити ступені елементів:
(a*a) modn = a
2
;
(a
2
* a) modn =a
3
.
Для ступенів елементів в групі Zp*, справедлива мала теорема Ферма:
Якщо p – просте число, то для кожного елемента справедливо
порівняння:
∀
а
∈
Z
p
*
: a
p-1
≡
1 modp
Наприклад, для Z
7
*
вірно: 5
6
≡
4
6
≡
3
6
≡
2
6
≡
1mod7
Узагальненням малої теореми Ферма для будь-якого (не обов'язково
простого) n є теорема Ейлера (Ферма-Ейлера):
∀
а
∈
Z
n
*
: a
φ(n)
≡
1 modn
На теоремі Ферма-Ейлера заснований спеціальний алгоритм пошуку
великих простих чисел – ймовірнісний тест Міллера-Рабіна [5].
Нагадаємо, що кількість простих чисел, що не перевершують х – функція π(x)
має наступну асимптотичну оцінку: π (x) » x/lnx. Це призводить до оцінки
1/lnn
для ймовірності того, що навмання (випадково) взяте число n є простим.
Ідея ймовірнісного тесту Міллера-Рабіна полягає в наступному:
92
Генерується випадкове число n і вибирається деякий а
∈
{2, .... n-2},
тоді
за теоремою Ферма-Ейлера:
Якщо (a
n-1
) modn
≠
1, то, очевидно, що число n – складене;
Якщо (a
n-1
) modn
= 1, то, можливо необхідно перевірити інше а.
Ймовірність помилки тесту експоненціально падає з ростом успішних
перевірок з різними значеннями а
∈
{2, .... n-2},
реально виконується близько
декількох десятків перевірок [5].
12.3
Криптосистема RSA
Запропонована в 1977 році РІВЕРСТ, Шамілем і Адлеманом (R. Rivest, A.
Shamir, L. Adleman)
криптосистема з відкритим ключем – RSA може бути
коротко описана наступним чином [9]:
а) Знаходимо два великих простих числа p і q (тест Міллера – Рабіна)
б) Обчислюємо n = p * q; n ≈ 2512 – 2768.
в) За побудовою
ϕ
(n) =p*q*(1-1/q)*(1-1/p) = (p-1)*(q-1).
г) Обираємо число e, таке, що: НСД (е,
ϕ
(n)) = 1.
д) Знаходимо число f зворотне до e за модулем j(n) за допомогою
розширеного алгоритму Евкліда
f = e
-1
mod
ϕ
(n) , тобто ( e*f
≡
1) mod
ϕ
(n) ,
або e*f = k*
ϕ
(n)+1.
Шифрування
Розбиваємо повідомлення на блоки M
i
β
(M
i
) =
β
(n)-1
і обчислюємо
C
i
=M
i
e
modn
Дешифрування
За прийнятим повідомленням Ci обчислюємо (всі операції по modn):
C
i
f
modn = (M
e
)
f
= M
e*f
= M
k*
ϕ
(n)+ 1
= M*(M
ϕ
(n)
)
k
= M
i
93
12.4
Крипостійкість RSA і складність алгоритмів факторизації
Оскільки значення e і n відомі, то задача розтину криптосистеми
зводиться до обчислення f, такого, що (e*f
≡
1) mod
ϕ
(n)
На сьогодні теоретично не доведено, що для визначення f необхідно
розкласти n на множники, проте, якщо такий алгоритм буде знайдений, то на
його основі можна побудувати швидкий алгоритм розкладання числа на
прості множники [11].
Тому криптостійкість RSA визначається сьогодні алгоритмічною
складністю завдання факторизації – завдання розкладання числа на прості
множники. Відзначимо, що за останні 20 років алгоритмічний прогрес в цій
області значно перевищує зростання продуктивності процесорів.
На сьогодні в області важко розв'язуваних завдань прийнята наступна
одиниця виміру тимчасової складності завдання – 1 MY.
1 MY –
це задача, для вирішення якої необхідна робота комп'ютера, що
виконує 1 млн. операцій в секунду протягом одного року.
У 1977 році Р. Ріверст прогнозував на основі кращого в той час алгоритму
розв'язання задачі факторизації методом еліптичних кривих тимчасову
складність факторизації складного числа довжиною в 129 десяткових цифр
(129D) – n
≈
10
129
в 4* 10
16
років [9]. Однак цей модуль був розкладений на
множники за 5000 MY (з використанням мережі Інтернет) в 1994 році
алгоритмом, що використовує метод квадратичного решета.
Модуль RSA 140D був факторизований в 1999 році алгоритмом, що
використовує метод узагальненого числового сита за 2000 MY. Більш
докладні відомості про тимчасову складність завдання факторизації і декілька
проектів по факторизації модулів RSA наведені в [9].
Найкращий сьогодні алгоритм факторизації, що використовує метод
узагальненого числового сита має наступну тимчасову оцінку:
T(n) = O ( e (ln n)
1/3
* (ln ln n)
2/3
) ;
Відзначимо, що саме успіхи асимптотичного і експериментального
аналізу алгоритмів дозволяють не тільки прогнозувати часову складність
розкриття криптосистеми RSA, забезпечуючи тим самим її криптостійкість,
але і розраховувати довжину модуля (кількість бітів у двійковому поданні
94
числа n) необхідну для ефективного шифрування з прогнозованим часом
розкриття.
12.5
Питання для самоконтролю
1) Мультиплікативна група відрахувань по модулю N і її властивості.
2) Ступені елементів і теорема Ферма-Ейлера.
3) Ідея імовірнісного тесту Міллера-Рабіна для пошуку великих простих
чисел.
4) Криптосистема RSA.
5) Застосування теорії алгоритмів до аналізу крипостійкості RSA.
95
ЛІТЕРАТУРА
1.
Ахо, А. Структуры данных и алгоритмы / Ахо А., Хопкрофт Дж.,
Ульман Дж. – М.: Издательский дом «Вильямс», 2001. –384 с.
2.
Вирт Н. Алгоритмы и структуры данных / Н. Вирт – 2-ое изд., испр. –
СПб.: Невский диалект, 2001. – 352 с.
3.
Карпов, Ю.Г. Теория автоматов / Ю.Г. Карпов – СПб.: Питер, 2002. –
224 с.
4.
Кнут, Д. Искусство программирования. Тома 1, 2, 3. 3-е изд. / Д. Кнут.
Уч. пос. – М.: Изд. дом "Вильямс", 2001. – 385 с.
5.
Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон,
Р. Ривест – М.: МЦНМО, 2001. – 960 с.
6.
Макконнел Дж. Анализ алгоритмов. Вводный курс / Макконнел Дж. –
М.: Техносфера, 2002. –304 с.
7.
Новиков, Ф.А. Дискретная математика для программистов /
Ф.А. Новиков – СПб.: Питер, 2001. – 304 с.
8.
Романовский, И.В. Дискретный анализ. Учебное пособие для
студентов, специализирующихся по прикладной математике /
И.В. Романовский – Издание 2-ое, исправленное. – СПб.; Невский
диалект, 2000. – 240 с.
9.
Чмора, А.Л. Современная прикладная криптография / А.Л. Чмора – М.:
Гелиос АРВ, 2001. – 256 с.