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

Реферат на тему:

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

Перший алгоритм кодування з відкритим ключем (Public Key Encryption, далі PKE) було запропоновано Вітфілдом Діффі та Мартіном Хелманом у Стендфордському університеті. Вони, а також незалежно від них Ральф Меркл, розробили основні його поняття у 1976 році. Перевага PKE полягає у відсутності потреби секретної передачи ключа.

PKE базується на нерозв’язності проблеми розкладу натурального числа на прості множники.

RSA схему шифрування було запропоновано у 1978 році та названо іменами трьох його винахідників: Роном Рівестом (Ron Rivest), Аді Шаміром (Adi Shamir) та Леонардом Адлеманом (Leonard Adleman). RSAналежить до класу алгоритмів кодування з відкритим ключем.

У 80-х роках криптосистема переважно використовувалася для забезпечення секретності та достовірності цифрових даних. Усучасному світі RSAвикористовується в web – серверах та браузерах для зберігання таємності даних що передаються по мережі, .

Схема RSA базується на обчисленні виразів зі степенями. Відкритий текст шифрується блоками, довжина кожного із яких менша за деяке число n .

Алгоритм генерації ключа

A повинен згенерувати відкритий та секретний ключі:

1. Згенерувати два великих простих числа p та q приблизно однакової довжини;

2. Обчислити n = p * q , fi = (p – 1) * (q – 1);

3. Вибрати натуральнеe , 1 < e < fi , взаємно просте з fi ;

4. Використовуючи розширений алгоритм Евкліда, розв’язати рівняння

d * e º 1 (mod fi ).

Відкритий ключ: (n , e ). Секретний ключ: d .

Схема шифрування RSA

B шифрує повідомлення m та надсилає A .

1. Шифрування. В робить наступні дії:

а) отримати відкритий ключ (n , e )від А ;

б) представити повідомлення у вигляді натурального числа m з проміжку [1..n ];

в) обчислити c = m^e modn ;

г) надіслати шифротекст c до А .

2. Дешифрування. Для отримання повідомлення m із шифротксту c А робить наступні дії:

а) використовуючи секретний ключ d , обчислити m = c^d modn .

Теорема. Шифр c декодується правильно.

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

c^d modn = (m ^e )^d modn = m ^{( e * d )} modn = m ^ ^{( j ( n ) * k + 1)} modn = (m ^{j ( n )} modn ) ^{k * m} = 1 ^{k * m} = m , оскільки за теоремою Ейлера m ^{j (n )} mod n = 1.

Означення. RSA системою називають функцію RSA_{n , e} (x ) = x^e modn та обернену їй RSA^-1 _{n , e} (y ) = y^d modn , де e – кодуюча, а d – декодуюча експонента, x , y Î Z_n ^* .

Приклад

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. Кодування: 4⁷ mod 323 = 234.Декодування: 234²⁴⁷ mod 323 = 4.

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

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

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

c , c^e , , , …

Оскільки обчислення відбуваються в групі Z_n *, то елемпнти послідовності знаходяться в межах від 0 до n - 1. Отже існує таке нату

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать