2.8. Криптосистема RSA
Поняття групи вважається основним у математиці XX століття. Групи широко застосовують у фізиці (від кристалографії до теорії елементарних частинок), хімії, біології, теорії інформації. Нові методи захисту від несанкціонованого доступу називають груповими, оскільки вони базуються на понятті групи. Яскравим прикладом є криптосистема RSA, запропонована 1977 р. американськими дослідниками Рівер-
стом, Шаміром та Адлеманом (Riverst R.L., Shamir A., Adleman L.). Суть її наступного.
Знаходяться два великі прості числа десяткових знаків) p і g . Обчислюється їх добуток n = pg. Тоді (властивості 3, 1 функції Ейлера)
ϕ ( n ) = ϕ ( p g ) = ϕ ( p ) ϕ ( p ) = ( p − 1 ) ( g − 1 ) . Фіксується натуральне число e, 0 e n, НОД (e, ϕ(n)) = 1. Пара (e, n) називається відкритим ключем. Переда-
інформація перекладається в цифрову форму (у першоджерелі літери латинського алфавіту замінюються двозначними числами: "a" = 01, "b" = 02 і так
далі, пробіл = 00), шифрується
у вигляді числа c – повідомлення, 0 c n ,
НОД ( c , n ) = 1. Тоді c є оборотним елементом кільця Z/nZ, тобто елементом
абелевої групи (Z/nZ)* порядку
ϕ (n). Повідомлення шифрується та передається
числом m ≡ ce (mod n). Таким чином, m є ступінь числа з кільцем Z/nZ. Адресат отримує повідомлення m. Він, як і всі, знає величини n та e. Він
також повинен знати секретний ключ – таке натуральне число
e d ≡ 1 ( mod ϕ ( n )) . За визначенням це означає, що e d = 1 + ϕ ( n ) q для деко-
торого цілого q. Тоді m d = c ed = c 1 + ϕ (n) r = (c ϕ (n)) r c = 1 c = c.
Перехоплювач, щоб розшифрувати повідомлення m повинен розкласти n на множники: n = pq . Тодіобчислюється ϕ ( n ) і легко знаходиться по відкритому
ключу e. Саме розкладання ключа n на множники і становить основну складність пропонованої криптосистеми. Як було зазначено у першому розділі, розкладання натурального числа на множники є, мабуть, експоненціальним щодо n завданням, еквівалентним перебору всіх можливих кандидатів на дільники.
2.9. Кільця. Підкільця та ідеали кілець
Визначення 2.18. Кільцем називається непорожня множина K з двома бінарними операціями алгебри додавання (+) і множення ( ); щодо операції додавання K є абелевою групою, а множення та додавання пов'язані законами дистрибутивності:
(a + b) c = a c + b c; a (b + c) = ab + ac для довільних a, b, c K.
Приклад 2.24. ( Z , +, ) - Кільце цілих чисел.
Приклад 2.25. ( Z / nZ , +, ) – кільце класів відрахувань за модулем n > 1. Приклад 2.26. Безліч всіх квадратних матриць даного порядку n з
раціональними, речовими або комплексними коефіцієнтами щодо операцій матричного складання та множення. Загальноприйняті позначення цих кілець: M n (Q), M n (R), M n (C) відповідно.
Різноманіття кілець надзвичайно широке. За кількістю елементів кільця поділяються на кінцеві (приклад 2.25) та нескінченні (приклади 2.24, 2.26). Основна класифікація кілець ведеться за властивостями множення.
Визначення 2.19. Кільце K називається асоціативним кільцем, якщо
певна на ньому операція множення має властивість: (ab) c = a (bc) для довільних a, b, c K.
Кільце K називається кільцем з одиницею, якщо воно асоціативно і має нейтральний елемент щодо операції множення.
Кільце K називається коммутативним, якщо ba = ab для довільних a, b K.
Теорема 2.16. Нехай K - асоціативне кільце з одиницею. Безліч K* оборотних щодо множення елементів кільця K є група (її називають мультиплікативною групою кільця K).
Приклад 2.27. Легко бачити, що в кільці цілих чисел оборотні щодо множення лише два числа: 1 і Отже, Z * = < 1, − 1 >.
Приклад 2.28. Mn(R) * = GL n(R).
Приклад 2.29. Мультиплікативна група ( Z / nZ )* кільця класів відрахувань Z / nZ по модулю n складається з ϕ ( n ) класів, породжених цілими числами, взаємно простими з модулем.
Визначення 2.20. Якщо кільце K з одиницею мультиплікативна група K * = K \ < 0 >, то кільце K називають тілом або алгеброю з поділом. Ком-
мутативне тіло називають полем.
Приклад 2.30. Наступні кільця є полями: а) Q – кільце раціональних чисел;
б) R – кільце дійсних чисел;
в) C – кільце комплексних чисел;
г) Z / pZ - кільце класів відрахувань за простим модулем p .
Визначення 2.21. Підкільце кільця K – це підгрупа адитивної групи ( K, + ) , що є кільцем, тобто замкнута щодо операції множення в кільці K.
Приклад 2.31. ( nZ , +, ) - підкільце кільця Z цілих чисел; Z – підкільце кільця Q раціональних чисел; Q – підкільце кільця R дійсних чисел. Перше – це кільце без одиниці, хоча саме кільце Z з одиницею.
Підкільця, в загальному випадку, практично не успадковують властивості кілець. Тому теоретично кілець найбільше значення мають підкільця спеціального виду – ідеали.
Визначення 2.22. Підкільце J кільця K називається лівим ідеалом кільця K, якщо для будь-якого k K і для кожного j J твір jk J , то
є Jk J. Якщо ж kJ J для всіх елементів k K , то називають Jправим ідеалом. Двосторонній ідеал - ідеал, що є одночасно і лівим і правим ідеалом.
Зрозуміло, що у комутативному кільці всі ідеали двосторонні.
Приклад 2.32. mZ = < mg g Z – двосторонній ідеал кільця цілих чи-
сіл Z для будь-якого натурального m. Очевидно, mZ ≠ Z якщо m > 1. Ясно, що
2 z > 4 z > 8 z > 16 z &K 2 z > 6 z > 12 z >K .
Приклад 2.33. У кільці Z / nZ зі складовим модулем n = pq, p & gt; 1, q > 1, легко бачити, що безліч класів відрахувань < p , 2 p , K , ) p ,0 >замкнуто від-
щодо операцій складання та множення класів відрахувань і, отже, утворює підкільце. Позначимо його через J p. Легко бачити, що J p – ідеал.
Аналогічно ідеалом є множина J q = < q , 2 q , K , ( p − 1 ) q ,0 >.
Приклад 2.34. У будь-якому кільці K безліч K формально також є ідеалами кільця K . Їх називають невласними, чи тривіальними, на відміну інших – власних ідеалів.
Теорема 2.17. 1. Перетин ідеалів даного кільця K є ідеал цього ж кільця.
2. Якщо J 1 , J 2 – ліві (праві) ідеали кільця K, їх
безліч усіх сум
J 2 > лівих (правих) ідеалів
J 1 , J 2 кільця K є лівий (правий) ідеал цього кільця.
4. Для кожного елемента a кільця K множина aK = < ak k K є лівий ідеал кільця K.
5. Якщо кільце K з одиницею елемент a K * , тоa = K ; якщо ж a K * , то a - власний ідеал кільця K.
6. Якщо K – комутативне кільце і a = bc для незворотних елементів a, b, c K, то ac, ab.
Доказ полягає у прямій перевірці всіх аксіом ідеалів.
Визначення 2.23. Лівим головним ідеалом кільця K, породженим
елементом a K ,називається ідеал з пункту теореми 2.17, тобто підкільце кільця K, що складається зі всіх елементів ak k K . Правий головний
ідеал складається з усіх елементів ka , k K .
Теорема 2.18. У кільці цілих чисел Z – будь-який ідеал J – головний.
На безлічі ідеалів кожного кільця існує відношення часткового порядку включення їх один до одного як множин. Особливу роль відіграють максимальні ідеали.
Визначення 2.24. Ідеал M (лівий, правий, двосторонній) кільця K називається максимальним, якщо K немає власного ідеалу J з умовою M J .
Теорема 2.19. У кільці цілих чисел ідеал J максимальний і тоді, коли існує просте число p, таке, що J = p.
2.10. Подільність у кільці багаточленів
Нехай P - поле, тобто довільне комутативне кільце з одиницею, у якого всі елементи, відмінні від нуля, оборотні, інакше кажучи,
P * = P \ < 0 >. Наприклад, P = Q, R, C, Z/pZ.
Нехай P [ x ] - кільце многочленів з коефіцієнтами P з звичайними
операціями складання та множення багаточленів. За своїми властивостями багаточлени близькі до цілих чисел. Наприклад, як і для цілих чисел має місце
Теорема 2.20 (про поділ із залишком). Для будь-яких двох багаточленів f(x) і g(x) ≠ 0 з кільця P[x] існують єдині багаточлени q(x)
і r(x), такі, що f(x) = g(x)q(x) + r(x), причому r(x) = 0 або ступінь r(x) менший за ступінь g(x).
Визначення 2.25. У разі теореми 2.20 многочлен q ( x ) називається приватним, а многочлен r ( x ) – залишком від розподілу f ( x ) на g ( x ) . Якщо r(x) = 0, то кажуть, що f(x) ділиться на g(x), а g(x) і q(x) називають дільниками або множниками многочлена f(x).
Якщо у рівності f(x) = g(x) q(x) ступеня співмножників не менше 1, то q(x) і g(x) називають нетривіальними дільниками многочлена f(x).
Очевидно, кожен ненульовий елемент поля P є дільником будь-якого багаточлена з кільця P [x]. Тому елементи полів називають тривіальними дільниками багаточленів.
Теорема 2.21. Оборотними багаточленами в кільці багаточленів P [ x ]
є багаточлени нульового ступеня, відмінні від нуля, і тільки вони, тобто P [x] * = P *.
Визначення 2.26. Найбільшим спільним дільником багаточленів f 1 ( x ) , f 2 ( x ) , K , f 5 ( x ) називається їх спільний дільник зі старшим коефіцієнтом
том 1, який ділиться будь-який інший спільний дільник. Його позначають
НОД (f 1 (x), f 2 (x), K, f s (x)).
Алгоритм Евкліда знаходження НОД, розглянутий раніше у розділі 1
для цілих чисел, справедливий і багаточленів.
Теорема 2.22. Найбільший спільний дільник багаточленів f(x) та g(x) з
кільця P [ x ] (з точністю до множників з поля P) збігається з останнім
відмінним від нуля залишком r n ( x ) наступного ланцюжка рівностей: