Вычислительные аспекты RSA. Электронная подпись Лекция 6

Алгоритмы поиска простых чисел Алгоритмы перебора Простой перебор Решето Эратосфена Проверка делимости на первые N простых чисел Вероятностные алгоритмы Тест Рабина-Миллера Алгоритм Лемана

Тест Рабина-Миллера (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ойти все тесты.

Тест Лемана (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%.

Тест Лемана (Lehmann) 6. Повторить эту проверку t раз. 7. Если результат вычислений равен 1 или -1, но не всегда равен 1, то p является простым числом с вероятностью ошибки (1/2) t

Обратные значения по модулю Расширенный алгоритм Евклида a -1 = x (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) 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

Алгоритм Диффи-Хеллмана 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

«Дыра» в механизме распределения ключей по алгоритму RSA

Общая схема использования хеш-функций

RSA наоборот