Шифрование с открытым ключом: Криптосистема RSA Докладчик: Евгений Сеппель (344 гр. 5/6 у.г.) Математико-механический факультет СПбГУ

О системе Создана в 1977 г. Ronald Rivest, Adi Shamir и Leonard Adleman. Использует принцип открытого ключа 2

Недостатки классических систем Необходимо предварительно обменяться ключом. В противном случае перехват всего разговора приведёт к расшифровке. 3

Недостатки классических систем Ключ должен являться секретом общающихся сторон. 4

Как будет работать RSA? Создание открытого ключа Опубликование открытого ключа Посылка шифрограммы владельцу открытого ключа 5

Поподробнее.... Пусть P Г P Л – открытые ключи, S Г S Л – секретные ключи D – множество всех возможных сообщений. И S Л (M), P Л (M), где M D суть перестановки. (Каждая из них может быть быстро вычислена если известен P или S) Необходима взаимная обратность перестановок одного владельца: S Л (P Л (M)) = M P Л (S Л (M)) = M M D Никто кроме владельца не должен уметь находить S() за разумное время!!! 6

Поподробнее.... Схема шифрования 7 Схема подписи

RSA Берём 2 больших простых числа p,q (~100 знаков) n:=p*q произведение простых чисел Пусть (n) – функция Эйлера (Число элементов в Z n ) (n) = (p-1)(q-1) Возьмём небольшое e взаимно простое с (n) Найдём d=e -1 mod (n) (оно и однозначно по mod) Теперь P = (e,n) S = (d,n) D=Z n P(M) = M e mod n S(C) = C d mod n 8

Время Заметим, что если числа d,n имеют порядка бит, число e имеет O(1) бит, то преобразование P потребует O(1) умножений по модулю n (O( 2 ) битовых операций), а преобразование S – O( ) умножений (O( 3 ) битовых операций). Мы пользуемся методом повторного возведения в квадрат. Теорема P() S() задают взаимно обратныее перестановки D. P(S(M)) = S(P(M)) = M ed mod n. e и d взаимно обратные по mod (n) => ed = 1+k(p-1)(q-1) для некоторого k По малой теореме Ферма M ed M(M p-1 ) k(q-1) M*1 k(q-1) M 9

Надёжность Трудно разложить n на p и q! Если легко разложить=> легко взломать Если трудно разложить =?> трудно взломать Задача восстановления секретного ключа эквивалентна задаче разложения на множители модуля: можно использовать d для поиска сомножителей n, и наоборот, можно использовать n для поиска d. 10

Взлом Можно(?) найти метод вычисления корня степени e из mod n. С = M e mod n, => корень степени e из mod n = M. Но мы так ещё не умеем.... Если на основе одного и того же e относительно небольшой величины шифруется много связанных сообщений, есть возможность вскрыть сообщения. Упомянутые атаки единственные способы расшифровать все сообщения, зашифрованные данным ключом RSA. восстановление исходной информации по ее криптограмме; вычисление закрытого ключа по известному открытому; формирование электронной цифровой подписи сообщения без знания закрытого ключа; создание фальшивого электронного документа, соответствующего известной подписи. 11

Взлом Успехи: В конце 95 года удалось практически реализовать раскрытие шифра RSA для 500-значного ключа. Для этого с помощью Интеpнета было задействовано 1600 компьютеров. (три-пять лет -- практическое время взлома) рекомендации по длине ключа n: бит для частных лиц; бит для коммерческой информации; бит для особо секретной информации 12

Список Литературы Т.Кормен. «Алгоритмы: Построение и анализ» -- М. МЦНМО, 2002 Б.Шнайер. «Прикладная Криптография» 2-е издание S. Goldwasser. «Lecture notes on Cryptography» 2001 Э.А. Гирш. Конспект лекций 3-го семестра 2 курса потока матобеспечения. Мат-мех