Криптоанализ RSA Докладчик: Николай Гравин (311 Группа)

Презентация:



Advertisements
Похожие презентации
Разложение чисел на простые множители Демонстрационный материал 6 класс.
Advertisements

Шифрование с открытым ключом: Криптосистема RSA Докладчик: Евгений Сеппель (344 гр. 5/6 у.г.) Математико-механический факультет СПбГУ.
Асимметричная криптография. Проблемы и идеи. Проблемы, связанные с использованием симметричных шифров Симметричные алгоритмы обеспечивают эффективное.
Наибольший общий делитель. (НОД) Взаимно простые числа.
Базовые технологии безопасности. Шифрование - это средства создания защищенного канала или способ безопасного хранения данных. Пара процедур - шифрование.
Криптография: алгоритм RSA
АЛГОРИТМ RSA Шифрование с открытым ключом. Содержание Симметричный шифр Ассиметричный шифр Виды ассиметричных шифров Алгоритм RSA Алгоритм RSA Теоретические.
Разложение чисел на простые множители Демонстрационный материал 6 класс.
ПРОСТЫЕ И СОСТАВНЫЕ ЧИСЛА РАЗЛОЖЕНИЕ НА ПРОСТЫЕ МНОЖИТЕЛИ Урок математики в 6 классе.
Криптосистемы с открытым ключем
Введение в криптографию 2 Семейство алгоритмов над конечными полями (RSA)
Тема урока: «Разложение числа на простые множители»
Анализ слепых цифровых подписей на основе дискретного логарифмирования Фаль Алексей Михайлович, ведущий научный сотрудник Институт кибернетики им. В.М.
1) Найдите наибольший общий делитель чисел 84 и 90. 2) Каждое число и их НОД разложите на простые множители. Проанализируйте полученные результаты. Проверьте.
В верхнем левом уrлу этой диаrраммы мы берем исходное сообщение и создаем 160-битовый хеш (дайджест сообщения) при помощи алrоритма SНAl. Затем дайджест.
СИСТЕМЫ ШИФРОВАНИЯ С ОТКРЫТЫМ КЛЮЧОМ Ассиметричные криптосистемы.
СИСТЕМЫ ШИФРОВАНИЯ С ОТКРЫТЫМ КЛЮЧОМ Ассиметричные криптосистемы.
Модуль 2. Математичні основи криптографії 1. Лекция 6 Криптография с использованием эллиптических кривых 1. Основные понятия 2. Способы использования.
Введение в криптографию 2 Семейство алгоритмов над конечными полями (RSA)
Разложение составного числа на простые множители Автор: Еремеева М.В МОУ «Средняя общеобразовательная школа 25»
Транксрипт:

Криптоанализ RSA Докладчик: Николай Гравин (311 Группа)

RSA: Берем p,q- два больших простых числа(512 бит) n=p q, (n)=(p-1) (q-1) e< (n),такое что gcd(e, (n))=1 d-? : e d=1 (mod (n)) (e,n)-открытый ключ, d-закрытый ключ Задача: Как зная e и (n) найти за полиномиальное время такое d(такое что e d=1 (mod (n))).

Encryption and Digital Signature Шифрование: M О Z n( секретное сообщение ) C=M^e(mod n) то, что мы посылаем получателю. D=С^d(mod n) D=M, D является расшифровкой C Цифровая подпись: М-сообщение или Hash от него Мы посылаем (M,S), где S=M^d(mod n)–подпись. Каждый может проверить, что S^e=M, но не может сам придумать по M такое S.

Полезный теоретический факт Пусть (N,e)-публичный ключ, d- закрытый ключ. Тогда зная (N,e,d) можно разложить N на простые множители N=p q за полиномиальное время.

Полезный теоретический факт Пусть (N,e)-публичный ключ, d- закрытый ключ. Тогда зная (N,e,d) можно разложить N на простые множители N=p q за полиномиальное время. Задача: Докажите этот факт.

Теоретический факт Открытый вопрос: Пусть даны N,e:gcd(e, (n))=1 и F:Z n - >Z n, F(x)=x^(1/e)(mod n) – вычисляется за единичное время. Существует ли тогда полиномиальный алгоритм, раскладывающий N на простые множители.(F(x)-оракул) Результат: для малых e ответ нет. Boneh и Venkatesan доказали,что в определенной модели, ответ Да на вопрос для малых e даст нам эффективный алгоритм разложения N.

Методы разложения N на простые сомножители Trial Division Pollards p-1 Method Pollards rho Method Elliptic Curve Method Quadratic Sieve Method Number Field Sieve Method

Trial Division Пытаемся разделить n на все простые числа от 1 до n.

Trial Division Пытаемся разделить n на все простые числа от 1 до n. Плохой метод (работает log(n)*2n^1/2)

Trial Division Пытаемся разделить n на все простые числа от 1 до n. Плохой метод (работает log(n)*2n^1/2) Хороший метод так, как больше чем у 91% чисел есть простой делитель меньший 1000.

Pollards p-1 Method n=pq, у p-1 все простые делители

Pollards rho Method Если у нас есть n исходов и 1.2*(n^1.2) испытаний то вероятность того, что 2 элемента совпали >50%.(birthday paradox) Теперь придумаем какую-нибудь функцию f: Z n - >Z n, которая ведет себя в Z nрандомно(f(x)=x^2+1(mod n)-подойдет) Начнем выписывать последовательность x 1,x 2,x 3,…, где x i+1 =f(x i ), параллельно будем считать gcd(x i -x j,n) для всех i и j – если gcd не 1 то мы разложили n.

Pollards rho Method Замечание Если считать для всех пар i и j gcd( x j -x i, n), то мы сделаем слишком много операций.

Pollards rho Method Замечание Если считать для всех пар i и j gcd( x j -x i, n), то мы сделаем слишком много операций. Вопрос: Как этого избежать?

Pollards rho Method Замечание Если считать для всех пар i и j gcd( x j -x i, n), то мы сделаем слишком много операций. Вопрос: Как этого избежать? Ответ: Проверять только для j=2i.

Литература Twenty Years of Attacks on the RSA Cryptosystem (Dan Boneh) The Quadratic Sieve Factoring Algorithm (Eric Landquist) Cryptanalysis of RSA: A Survey (Calros Frederico Cid)