![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
N 1 = 323, N 2 = 299, N 3 = 341
и перехваченные сообщения
C 1 = 50, C 2 = 299, C 3 = 1,
Чтобы восстановить исходное сообщение m, находим решение системы
X = 300763 (mod N 1 N 2 N 3),
после чего извлекаем обычный кубический корень
m = X 1/3 = 67.
Вывод. При использовании малой шифрующей экспоненты E противник может восстановить циркулярное сообщение m для E пользователей.
Обе вышеуказанные атаки позволяют раскрыть текст, не прибегая к разложению на множители. Наиболее важный вывод из них – необходимость дополнять оригинальные сообщения случайными цифрами перед их зашифрованием.
При практической реализации RSA необходимо решить следующие задачи:
1. Генерация больших простых чисел p и q с проверкой выполнения соответствующих требований к ним.
2. Выбор экспонент e и d с соблюдением соответствующих требований.
3. Реализация операции вычисления xy (mod n).
Генерация большого простого числа:
1) Сгенерировать случайное n -битовое число p.
2) Установить старший и младший бит равными 1. (Старший бит гарантирует требуемую длину простого числа, а младший – обеспечивает его нечетность).
3) Убедиться, что p не делится на малые простые числа: 3, 5, 7, 11 и т.д. Во многих практических реализациях проверяется делимость p на все простые числа, меньшие 256. Наиболее надежна проверка делимости на все простые числа, меньшие 2000. Эти проверки можно выполнить на основе массива этих простых чисел.
4) Выполнить тест простоты Рабина-Миллера для некоторого случайного числа a. Если p проходит тест, сгенерировать другое случайное число a и повторить тест. Для ускорения проверки можно выбирать относительно небольшие значения a. Выполнить тест минимум пять раз. Если p не проходит один из тестов, то перейти к шагу 1).
Другой путь – не генерировать случайное число p в каждом тесте, а последовательно перебирать все нечетные числа, начиная со случайно выбранного числа, пока не найдется простое число.
Тест Рабина-Миллера:
Выбрать для тестирования число p. Вычислить b – число делений p – 1 на 2 (то есть 2 b – это наибольшая степень числа 2, на которую делится p – 1). Затем вычислить m, такое, что p = 1 + 2 b · m.
1) Выбрать случайное число a, меньшее p.
2) Установить j = 0 и z = am mod p.
3) Если z = 1 или если z = p – 1, то p проходит тест и может быть простым числом.
4) Если j > 0 и z = 1, то p не относится к простым числам.
5) Установить j = j + 1. Если j < b и z ¹ (p – 1), установить z = z 2 mod p и вернуться к шагу 4). Если z = p – 1, то p проходит тестирование и может быть простым числом.
6) Если j = b и z ¹ (p – 1), то p не относится к простым числам.
Выбор экспонент e и d:
1) Так как единственное требование к e – отсутствие общих множителей с числом φ (n) = (p - 1) · (q - 1), то логично выбирать небольшое e легко разложимое на простые множители и осуществлять проверку делением φ (n) на множители e. Либо выбирать простое e. Неплохо также выбирать e с минимальным количеством единиц в двоичном представлении, что ускорит операцию возведения в степень, реализованную следующим алгоритмом.
2) Так как очевидно, что d = e -1(mod p), то d находим при помощи расширенного алгоритма Евклида.
Алгоритм вычисления xy (mod n).
1) Представим y в двоичной системе счисления y = y 02 r + … + yr -12 + yr, где yi, цифры в двоичном представлении равные 0 или 1, y 0 = 1.
2) Положим x 0 = x и затем для i = 1,…, r вычислим
.
3) xr есть искомый вычет xy (mod n).
Дата публикования: 2014-11-02; Прочитано: 547 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!