RSA – алгоритмів кодування з відкритим ключем, Детальна інформація

1. Обчислити dp = d mod (p - 1), dq = d mod (q - 1)

mod q.

3. Розв’язати систему лінійних порівнянь



Розв’язком системи буде декодоване повідомлення: m = cd (mod n).

Приклад

Нехай 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))