09
10
11
12
13
14
15
16
17
Т
У
Ф
Х
Ц
Ч
Ш
Щ
Комерсант
И
Ь
Е
Ю
Я
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Одним з відоміх алгорітмів дешіфрування системи RSA є метод ітерацій. Згідно з ним Вихідне ПОВІДОМЛЕННЯ можна отріматі з шифруванням Повторну шифрування Доті пока не отрімаємо Відкритий текст. <В
Приклад 1 . Нехай р = 383, q = 563, n = 215 629, E = 49. У цьом випадка Відкритий текст Повністю отримується вже через 10 ітерацій повторного шифрування. Щоби в цьом впевнітіся, Достатньо довести, что 49 10 = 1 mod ( p -1) ( q -1). Виконання цієї рівності можна перевіріті даже на калькуляторі: (49 4 = 5764801 -> 49 4 = 183 017 mod 214 684 ... 49 9 = 56957 mod 214684 -> 49 10 = 1 mod 214684). p> Інший метод атаки на шифр RSA - метод Розкриття чисел p и q . Праворуч у тому, что n = pq (Як и Самі ці числа p и q ) повінні буті й достатньо великими, Щоби розкласті его на множнікі Було Дуже доладно (у цьом и Полягає складність цього алгоритму шифрування). Бажано, Щоби p и q вибираете Випадкове чином и НЕ булі "Дуже близько" Одне до одного. Покажемо, Яким чином можна вікорістаті блізькість значень p и q. Будемо вважаті, что p > q (что НЕ накладає Зайве обмежень). Тоді для величин x = ( p + q )/2, y = ( p - q )/2 справедливе співвідношення: x 2 - y 2 = n . Перебіраючі у порядку ЗРОСТАННЯ Варіанти x>, ​​легко найти розв'язок рівняння x 2 - y 2 = n , так як x = ( p + q )/2 буде близьким до у випадка блізькості p и q . p> Приклад 2 . Нехай n = pq = 851. Вікорістаємо описів способ для знаходження p и q . Так як = 29.17, Беремо x = 30 и обчіслюємо 30 2 -851 = 49 І з Першої СПРОБА знаходимо розв'язок x = 30 и y = 7. Таким чином, p = 30 +7 = 37, q = 30-7 = 23. p> Крім Вказаною обмежень на p , q , E , D накладаються ї Другие обмеження. p> Система шифрування RSA может буті застосована для цифрового підпісу. У випадка підпісу ПОВІДОМЛЕННЯ М Відправник обчіслює P = M E mod n . Отримувач, Який має М та Р , перевіряє справедливість співвідношення Р D = М mod n и впевнюється у справжності ПОВІДОМЛЕННЯ М . p> Приклад 3 . Нехай p = 3, q = 11, n = 3x11 = 33, E = 7, D = 3. Тоді Відправник ПОВІДОМЛЕННЯ М = "02" обчіслює цифровий підпис Р = 2 7 mod 33 = 29 и відправляє ПОВІДОМЛЕННЯ "02, 29" отримувачу. Тієї, у свою черго, перевіряє справжність ПОВІДОМЛЕННЯ "02", Обчислено М = (29 3 ) mod 33 = 2.
Насправді підпісують НЕ самє ПОВІДОМЛЕННЯ, а его т.зв. хеш-функцію. Спочатку оригінальне ПОВІДОМЛЕННЯ обробляється Деяк функцією, яка має таку властівість, что пріймає на вході рядки різної довжина, а на віході відає Деяк "дайджест", як правило, однакової и меншої, чем вхідна, довжина. Хеш-функція Виконує математичні обчислення, у результаті якіх обчіслюється Значення хеш-Функції. Хеш-функція может буті Дуже простою. Наприклад, вона может віконаті п...
