Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 11 лет назад пользователемВалерий Чеченев
1 Вычислительные аспекты RSA. Электронная подпись Лекция 6
2 Алгоритмы поиска простых чисел Алгоритмы перебора Простой перебор Решето Эратосфена Проверка делимости на первые N простых чисел Вероятностные алгоритмы Тест Рабина-Миллера Алгоритм Лемана
3 Тест Рабина-Миллера (Rabin-Miller) 1. Генеpиpyют слyчайное число длиной n-бит 2. Стаpшие и младшие биты yстанавливают в 1 3. Пpовеpяют чтобы p не делилось на маленькие пpостые числа (до 2000) 4. Делают пять тестов Rabin-Miller'a с pазными слyчайными а. Для yскоpения вычислений а pекомендyют бpать небольшое. p должно пpойти все тесты.
4 Тест Лемана (Lehmann) 1. Выбрать случайно число a, меньшее p. 2. Вычислить a (p-1)/2 mod p. 3. Если a (p-1) /2 1 (mod p) или a (p-1) /2 -1(mod p), то p не является простым. 4. Если a (p-1)/2 = 1 (mod p) или a (p-1)/2 = -1 (mod p), то вероятность того, что число p не является простым, не больше 50%.
5 Тест Лемана (Lehmann) 6. Повторить эту проверку t раз. 7. Если результат вычислений равен 1 или -1, но не всегда равен 1, то p является простым числом с вероятностью ошибки (1/2) t
6 Обратные значения по модулю Расширенный алгоритм Евклида a -1 = x (mod n) Работающий алгоритм на С
7 Арифметика вычетов Основные тождества (a + b) mod n = ((a mod n) + (b mod n)) mod n (a - b) mod n = ((a mod n) - (b mod n)) mod n (a * b) mod n = ((a mod n) * (b mod n)) mod n (a * (b+c)) mod n = (((a*b) mod n) + ((a*c) mod n)) mod n Возведение в степень обычным умножением a 8 mod n = (a * a * a * a * a * a * a * a) mod n Возведение в степень с промежуточными привидениями a 8 mod n = ((a 2 mod n) 2 mod n) 2 mod n Для нечетных степеней, например для = => 25 = a 25 mod n = (a*a 24 ) mod n = (a* a 8 *a 16 ) mod n = = (a*(( a 2 ) 2 ) 2 *((( a 2 ) 2 ) 2 ) 2 ) mod n = = (a*((( a*a 2 ) 2 ) 2 )2 ) mod n Прием «Цепочка сложений» (((((((a 2 mod n)* a) 2 mod n) 2 mod n) 2 mod n) 2 mod n) 2 *a) mod n
8 Алгоритм Диффи-Хеллмана 1. V и N – числа доступные для всех 2. X и Y - случайные простые числа 3. (V x )mod N – первый абонент передает второму 4. (V y )mod N – второй абонент передает первому 5.Первый абонент вычисляет значение (((V y ) mod N) x ) mod N 6.Второй абонент вычисляет значение (((V x ) mod N) y ) mod N Полученное значение - ((V x*y ) mod N
9 «Дыра» в механизме распределения ключей по алгоритму RSA
10 Общая схема использования хеш-функций
11 RSA наоборот
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.