XstK (x,n;y);
z
←
x;
y
←
1;
Repeat
If (n mod 2) = 1
then
y
←
y*z;
z
←
z*z;
n
←
n div 2;
Until n = 0
Return (y)
End
Одержимо функцію трудомісткості даного алгоритму, використовуючи введені раніше позначення і прийняту методику рахунків елементарних операцій у формальній системі процедурно-орієнтованої мови високого рівня:
Fa(n) = 2 + β(n)*(2+2+2+1) + β
1
(n)*(2)= 7*β(n) + 2*β1(n)+2 (11.2)
Кількість проходів циклу визначається кількістю бітів у двійковому поданні n – β(n), а кількість повторень операції y
←
y*z – кількістю одиниць в цьому поданні – β
1
(n), що й відображає формула 11.2.
Визначимо трудомісткість алгоритму для особливих значень n, такими особливими значеннями є випадки, коли n=2
k
або n=2
k
– 1:
– в випадку коли n=2
k
, то β
1
(n)=1 і Fa(n)= 7*β(n) + 4;
– в випадку коли n=2
k
-
1, то β
1
(n)= β(n) і Fa(n)= 9*β(n) + 2.
z
←
x;
y
←
1;
Repeat
If (n mod 2) = 1
then
y
←
y*z;
z
←
z*z;
n
←
n div 2;
Until n = 0
Return (y)
End
Одержимо функцію трудомісткості даного алгоритму, використовуючи введені раніше позначення і прийняту методику рахунків елементарних операцій у формальній системі процедурно-орієнтованої мови високого рівня:
Fa(n) = 2 + β(n)*(2+2+2+1) + β
1
(n)*(2)= 7*β(n) + 2*β1(n)+2 (11.2)
Кількість проходів циклу визначається кількістю бітів у двійковому поданні n – β(n), а кількість повторень операції y
←
y*z – кількістю одиниць в цьому поданні – β
1
(n), що й відображає формула 11.2.
Визначимо трудомісткість алгоритму для особливих значень n, такими особливими значеннями є випадки, коли n=2
k
або n=2
k
– 1:
– в випадку коли n=2
k
, то β
1
(n)=1 і Fa(n)= 7*β(n) + 4;
– в випадку коли n=2
k
-
1, то β
1
(n)= β(n) і Fa(n)= 9*β(n) + 2.
88
Якщо показник ступеня заздалегідь невідомий, то можна отримати середню оцінку, в припущенні, що подання числа n займає не більше k двійкових розрядів, тобто n <2k або log2n
s
(N) = β(N)/2, где N=2
k
-1, звідки:
Fa(n)
≤
7*β(N) + 2*β
s
(N)+2 = 8*β(N) + 2 =8*([log
2
(n)]+1)+2 = 8*k +2.
Таким чином, кількість операцій, виконуваних швидким алгоритмом зведення в ступінь, лінійно залежить від кількості бітів у двійковому поданні показника ступеня.
Введення спеціальних функцій β
1
(n) і β(n) дозволило отримати точне значення функції трудомісткості цього алгоритму.
11.2
Відомості з теорії простих чисел
а) Порівняння
Кажуть, що два числа a і b можна порівняти по модулю c, якщо вони дають при діленні на c рівні залишки.
Операція отримання залишку від ділення a на c записується у вигляді: а modc = d, що еквівалентно поданням: a = k * c + d;
Порівнянність двох чисел по модулю означає, що: а modc = b modc і записується як (a
≡
b) modc
Приклади: (13
≡
6) mod7, (17
≡
22) mod5
Якщо, а modc = 0, то, число а ділиться на c без залишку: (a
≡
0)modc
б) Прості числа
Число p називається простим, якщо вона не має інших дільників, крім одиниці і самого себе. Очевидно, що в якості можливих дільників є сенс перевіряти тільки прості числа, менші або рівні квадратному кореню з числа, що перевіряється.
Безліч простих дільників, доказ належить Евкліду:
Нехай p1, ..., pk, – всі прості числа, але тоді число
89 а = (p1 * p2 * ... * pk + 1) у залишку від ділення на будь-яке з них дає одиницю a mod pi = 1
і отже є простим.
в) Функція π (n)
Функція π (n) в теорії простих чисел позначає кількість простих чисел, не переважаючих n.
Наприклад π (12) = 5, оскільки існує 5 простих чисел, не переважаючих
12, а саме: 2,3,5,7,11.
Асимптотична поведінка функції π (n) було отримано наприкінці XIX століття [5] і пов'язане з функцій інтегрального логарифма:
Для великих n –
π
(n)
≈
li(n)
≈
n / ln n.
Отриманий результат означає, що прості числа не так вже «рідкісні», ймовірність того, що серед взятих випадково ln n чисел, що не перевершують n, одне з них просте, достатньо велика.
Відзначимо, що це використовується при пошуку великих простих чисел в ймовірнісному тесті Міллера-Рабіна [5].
11.3
Питання для самоконтролю
1)
Функції підрахунку кількості бітів і кількості одиниць в двійковому поданні числа та їх властивості.
2)
Алгоритм швидкого зведення в ступінь.
3
) Аналіз трудомісткості алгоритму швидкого зведення в ступінь;
4
) Поняття напівгрупи, моноїд і групи, приклади груп.
5)
Порівняння та відомості з теорії простих чисел.
90
12.
КРИПТОСИСТЕМА RSA
І
ТЕОРІЯ
АЛГОРИТМІВ
12.1
Мультиплікативна група відрахувань за модулем n
Розглянемо деякі групи, утворені на множині відрахувань за модулем n:
Нехай n – ціле додатне число, тоді множина залишків від ділення будь-якого цілого додатного числа на n називається множиною відрахувань за модулем n
і позначається як Zn:
Z
n
= { 0, 1, 2,…, n-1}
Якщо як групову операцію розглянути операцію додавання за модулем n:
(+ modn), то множина Zn утворює з цією операцією і нулем, в якості
«
одиниці», групу {Z
n
, + modn, 0}, яку називають адитивною групою відрахувань за модулем n.
Зворотним елементом для a
∈
Zn буде елемент a
-1
= (n – a) modn
Якщо як групову операцію розглянути операцію множення за модулем n:
(*modn), то множина Z'n утворює з цією операцією і одиницею групу {Z'
n
,
*modn, 1},
яку називають мультиплікативною групою відрахувань за модулем n, що позначається звичайно як Zn*.
Зворотний елемент в групі Zn* існує, тільки якщо НСД (z, n) = 1
Кількість чисел, взаємопростих з n, і, отже, кількість елементів в групі Zn* може бути отримано за формулою Ейлера [5, 9]:
Z
n
*
=
ϕ
(n) = n*П (1-1/p
i
),
де p
i
– прості дільники числа n.
Наприклад:
ϕ
(15) = 15*(1-1/3)(1-1/5) = 15*2/3*4/5=8
Якщо число n – просте число, тобто n = p, то
ϕ
(p) = p(1-1/p) = (p-1).
Знаходження зворотного елементу для деякого елемента мультиплікативною групи по множенню зазвичай виконується за допомогою розширеного алгоритму Евкліда [5].
Зауважимо, що теорема про єдинство зворотного елемента в групі Zn* , а 1 і (n – 1) є зворотними самі собі, тобто:
1*1 = 1modn
і (n-1)*(n-1) = (n
2
– 2n +1)modn = 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 с.
1 2 3 4 5 6 7 8