Нехай RSA система має вигляд: p = 17, q = 19, n = 323, e = 7, d = 247.
Для розв’язку рівняння m7 mod 323 = 251 (c = 251) обчислимо 251247 mod 323:
1. dp = 247 mod 16 = 7, dq = 247 mod 18 = 13;
2., mp = 2517 mod 17 = 4, mq = 25113 mod 19 = 9;
3. Розв’яжемо систему лінійних порівнянь
Розв’язуючи її методом Гауса, отримаємо m = 123.
Отже 1237 mod 323 = 251.
Мала декодуюча експонента
Приклад. Виберемо аовідомлення m = 13 та зашифруємо його трьома різними RSA системами.
1. p = 5, q = 17, n = 85, e = 3, d = 57,
m3 mod 85 = 72;
2. p = 11, q = 23, n = 253, e = 3, d = 169,
m3 mod 253 = 173;
3. p = 17, q = 23, n = 391, e = 3, d = 261,
m3 mod 391 = 242;
Для знаходження повідомлення m за відкритими ключами (ni, ei ) та перехопленими шифрами ci складемо систему порівнянь
Одним із її розв’язків буде x = 2197 = 133. Тобто шуканим повідомленням буде m = 13.
Неприховані повідомлення
Означення. Повідомлення m називається неприхованим, якщо його шифр дорівнює самому повідомленню, тобто me = m (mod n).
Наприклад, повідомлення m = 0 та m = 1 завжди є неприхованими для довільних значень e та m.
Твердження. Кількість неприхованих повідомлень в RSA системі дорівнює
(1 + НСД(e - 1, p - 1)) * (1 + НСД(e - 1, q - 1))
Оскільки значення e - 1, p - 1 та q - 1 – парні, то НСД(e - 1, p - 1) \xF0B3 2, НСД(e - 1, q - 1) \xF0B3 2, а отже кількість неприхованих повідомлень завжди не менша за 9.
|
Скачати "Реферат на тему Public Key Encryption"
