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

Оскільки p та q – прості числа, то  (p * q) =  (n) = (p - 1) * (q - 1), де  – функція Ейлера. З умови вибору ключа d маємо: d * e mod (n) = 1, або d * e =  (n) * k + 1 для деякого натурального k.

cd mod n = (me)d mod n = m (e * d) mod n = m ^ ( (n) * k + 1) mod n = (m  (n) mod n) k * m = 1 k * m = m, оскільки за теоремою Ейлера m (n) mod n = 1.

Означення. RSA системою називають функцію RSAn,e(x) = xe mod n та обернену їй RSA-1n,e(y) = yd mod n, де e – кодуюча, а d – декодуюча експонента, x, y Zn*.

Приклад

1. Оберемо два простих числа: p = 17, q = 19;

2. Обчислимо n = 17 * 19 = 323, fi = (p - 1) * (q - 1) = 16 * 18 = 288;

3. Оберемо e = 7 (НСД(e, fi) = 1) та розв’яжемо рівняння 7 * d  1 (mod 288), звідки d = 247.

Побудовано RSA систему: p = 17, q = 19, n = 323, e = 7, d = 247.

Відкритий ключ: n = 323, e = 7, секретний ключ: d = 247.

1. m = 4. Кодування: 47 mod 323 = 234.Декодування: 234247 mod 323 = 4.

2. m = 123. Кодування: 1237 mod 323 = 251.Декодування: 251247 mod 323 = 123.

Циклічна атака

За відомим шифром c (c = me mod n) злодій, маючи відкритий ключ e та n, бажає знайти повідомлення m. Він починає будувати послідовність чисел

c, ce, , , …

Оскільки обчислення відбуваються в групі Zn*, то елемпнти послідовності знаходяться в межах від 0 до n - 1. Отже існує таке натуральне k, що с = . Враховуючи що c = me mod n, маємо: me = або m = .

Таким чином для знаходження повідомлення m за його шифром c необхідно побудувати послідовність c, ce, , , …, , = c, і взяти її передостаннє число.

Приклад

Розв’язати рівняння: m7 mod 323 = 251.

e = 7, n = 323, c = 251.

k

0251

1310

247