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


Воспользуйтесь поиском к примеру Реферат        Грубый поиск Точный поиск






Загрузка...

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

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 & lt; e & lt; fi, взаимно простое с fi;

4. Используя расширенный алгоритм Евклида, разв связать уравнения

d e является 1 (mod fi).

Открытый ключ: (n, e). Секретный ключ: d.

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

B шифрует сообщение m и направляет A.

1. Шифрования. В делает следующие действия:

а) получить открытый ключ (n, e) от А;

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

в) вычислить c = me mod n;

г) отправить шифротекст c-А.

2. Дешифрувки. Для получения сообщения m с шифротксту c А делает следующие действия:

а) используя секретный ключ d, вычислить m = cd mod n.

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

Поскольку p и q простые числа, то j (p q) = j (n) = (p - 1) (q - 1), где j функция Эйлера. Из условия выбора ключа d имеем: d e mod j (n) = 1, или d e = j (n) k + 1 для некоторого натурального k.

cd mod n = (me) d mod n = m (e d) mod n = m ^ (j (n) k + 1) mod n = (mj (n) mod n) k m = 1 k m = m, поскольку по теореме Эйлера mj (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

0 | 251

1 | 310

2 | 47

3 | 4

4 | 234

5 | 123

6 | 251

Из таблицы имеем: c = 251. Поскольку me =, то m = 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 = mod p, mq = 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))

Поскольку значение e - 1, p - 1 и q - 1 парные, то НОД (e - 1, p - 1) и 2 НОД (e - 1, q - 1) и 2, а следовательно количество нескрываемым сообщений всегда не менее чем 9.

Загрузка...