REFERATUA.ORG.UA — База українських рефератів



Головна Інформатика, комп'ютери, програмування → RSA – алгоритмів кодування з відкритим ключем

251.

k

0

251

1

310

2

47

3

4

4

234

5

123

6

251

З таблиці маємо:c = RSA – алгоритмів кодування з відкритим ключем = 251. Оскільки me = , то m = RSA – алгоритмів кодування з відкритим ключем = 123.

Атака методом осліплення

Припустимо, А має секретний ключ RSA системи, а Z – злодій, який перехопив шифр c і хоче декодувати його. При цьому А відмовляє видати Z вихідний текст m. Тоді Z обирає деяке значення b  Zn*, обчислює c' = be * c і просить А дешифрувати його. А погоджується дешифрувати c' своїм секретним ключем d, оскільки зміст повідомлення c' йому ні про що не говорить і виглядає невинним. Отримавши m' = c'd mod n, злодій Zобчислює m = m' / b і отримує шукане m. Шифром m дійсно є c, оскільки me = m'e/ be = c'de / be = c' / be = c.

Така атака можлива, оскільки А не знає повної інформації про шифр c', який дає йому злодій Z.

Приклад. Нехай А має RSA систему: p =17, q = 19, n = 323, e = 7, d = 247.

Злодій Z перехопив шифр c = 234 і хоче знайти таке m, що m7 = 234 mod 323.

1. Z обирає b = 10  Z323*, обчислює c' = 107 * 234 mod 323 = 14 і просить А дешифрувати його.

  • A обчислює m' = 14247 mod 323 = 40 і передає його Z.

    3. Z знаходить шукане повідомлення обчислюючи

    m = 40 / 10 = 40 * 10-1 = 40 * 97 = 4 mod 323.

    Таким чином 47 = 234 mod 323.

    Прискорення дешифрування

    За допомогою китайської теореми про лишки можна прискорити процес дешифрування, знаючи секретні прості числа p та q.

    Алгоритм

    Дешифрування. А має декодуючу експоненту d, а також p та q (n = p * q). А отримує від В шифр с та повинен виконати операцію cd (mod n).

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

    2. Обчислити mp = RSA – алгоритмів кодування з відкритим ключем mod p, mq = RSA – алгоритмів кодування з відкритим ключем mod q.

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

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

    Розв'язком системи буде декодоване повідомлення: 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 = 247mod 16 = 7, dq = 247mod 18 = 13;

    2., mp = 2517 mod 17 = 4, mq = 25113 mod 19 = 9;

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

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

    Розв'язуючи її методом Гауса, отримаємо 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 складемо систему порівнянь

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

    Одним із її розв'язків буде 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)  2, НСД(e - 1,q - 1)  2, а отже кількість неприхованих повідомлень завжди не менша за 9.


  •  
    Загрузка...