Безопастность метода rsa

Зависит от проблеммы разложения больших чисел на множетели. Матиматичеки некогда не одоказывалось что нужно разложить N на множетели чтобы востановить сообщение Х по велечине У и ключу Е.

Для криптоанализа может быть приведен совсем иной способ и если этот другой способ позволит получить ключ D его также можно будет применить для разложения больших чисел на множетели. Другой вариант как можно скрыть все секреты: угадав значаение произведения (p-1)(q-1).

Есть один способ для беспокойства. Большинство обще принятых алгоритмов вычесления простых чисел p и q носят вероятностный характер. Вероятность этого события можно свести к минимуму но не к 0 и если это произойдет то такое осбытие сразуже будет обнаружено. Ни процес шифрования ни разшифрования работать при этом не будут.

Существенным недостатком асиметричных методов шифрования является их сложностьа следовательно низкое быстро действие по-этому такие методы основаные на RSA используется в сочетании с семитричными.

Асиметричные методы на 3 или 4 порядка медленее чем семитричные.

Как при шифровании так и при разшифрованииалгоритм состоит из операций возведения в степень, которые образуются последовательным рядом умножений. В практических приложениях для открытого ключа обычно выбираются относительно небольшой показатель. И часто целые группы пользователей имеют один и тотже показатель но каждый с различным модулем, если открытый показатель неизменен то вводится ограничения на главные делители модуля. Эти главные делители назыв факторами. При этом шифрование данных выполняется быстрее чем разшифрование. Если в модуле k бит то в алгоритмах RSA обычно количество шагов необзодимых для операций с открытым ключом пропорционально второй степени к. Количество шагов для операции секретного ключа пропорционально как квадрат. Количество шагов секретного –кубе. И еще какогото- 4степени.

Методы бысрого умножения основаны на быстром преобразовании фурье выполняются на быстром количестве шагов, но сложность этой программы не позволило использовать. Алгоритм RSA намного медленее чем алгоритм DES и другие алгоритмы блочного шифрования. Программная реализация DES работатет в 100 раз быстрее, а в зависимости от аппаратной реализации от 1000 до 10 000 раз быстрее чем RSA.

………………………………………………….

Для её взлома необходимо по известным входным велечинам N, e и зашифрованому сообщению необходимо найти такое значение х є (Z/(N))

Наиболее распространен вид атаки назыв. Метод повторного шифрования.

Он состоит в следующем:

Основные действия:

Вычисления ключей

Выбор p*q -//- должны быть простыми

Вычисление n=p*q

Вычисление ф(n)=(p-1)(q-1)

Выбор иного е gcd(ф(n),e)=1 1<e< ф(n)

Вычисление A=e^-1mod ф(n)

Открытый ключ KU={e,n}

Личный ключ KR = {d,n}

1)Выберем два простых числа p=7, q=17.

2)N=p*q=119

3)ф(n)=6*16=96

4)е=5

5)d: de=1mod96

77*5=385=4*96+1

d=77

пусть в качестве открытого текста поступает открытое число

откр шифров

19⁵=2476099/119

19---> = 20807

Сост.66

Если без искажений передается то нужно провести востановление.

19⁵=66mod119

66⁷⁷(mod119)=119

Сравнительная характеристика методов традиционного шифрования и методов с открытым ключем.

Традиционное шифрование	Метод с открытым ключем
Необходимо для работы
1)Один алгоритм с одним и тем же ключем служит и для шифрования и для расшифрования 2) отправитель и получатель сообщения должны использовать одинаковые алгоритм и ключ	1)Используется одинаковый алгоритм но 2 ключа. 2) отправитель и получатель должны иметь по одному из пары соответствующих ключей.
Необходимо для защиты
1)Ключ должен сохраняться в секрете. 2)Должно быть невозможно или практически невозможно расшифровать сообщение при отсутствии доп. Инф. 3) знания алгоритма и наличее образцов шифрованого текста должно быть недостаточно для востановления ключа.	1)У систем с открытым ключем один должен сохраняться в секрете. 2) практически невозможно расшифровать сообщение при отсутствии доп инф. 3) знание алгоритма и одного из ключей и образцов шифрованого текста должно быть недостаточно чтобы востановить второй ключ.

При рассмотрении сложностей вычислений RS алгоритма выделяют 2 вопроса:

1. Сложность шифрования, дешифрования

2. Сложность вычисления ключей используемых при этом.

Применяется операция возведения целого числа в целую степень и взятие модуля. Если возведение в степень выполнять с целыми числами, а затем проводить сравнения по модулю n, то промежуточные значения могут оказаться огромными величинами.

Для уменьшения величин полезно использовать такие соотношения:

[(a mod n)*(b mod n)] mod n = (a*b) mod n

Позволяет промежуточные результаты брать по модулю n.

Эффективная реализация операций возведения в степень.

Пусть нужно найти a^m, где a и m положительные целые чила.

Прежде чем использовать систему с открытым ключем у каждого из сторон должна быть возможность сгенерировать пару ключей. 1) сгенерировать пару ключей p и q

2)выбор одного из чисел e и d и вычисление другого.

Т.к. n=0 будет известно противнику то с помощью перебора эти числа должны быть выбраны из достаточно большого множесва.

Метод нахождения больших простых чисел доджен быть эффективным на практике. В настоящее время нет хороших методов вычесления произвольно больших чисел. И для их определения прибегают к большим хитростям. Чаще всего процедура определения большого простого числа заключается в выборе случайного нечетного числа приблизительно желаемой величины и выяснением является ли оно простым. Для проверки того что числа простыесуществует целый ряд тестов. Почти все они носят вероятносный характер. Такой тест определит то что конкретное число верояно простое. Одним из наиболее популярных алгоритмов является «алгоритм Миллера-Рабина».

Проверка простоты конкретного целого числа n заключается в выполнении целого числа в котором используется число n некоторое случайное число А. если оно не выдерживает тестирование то оно не является простым. Если n выдерживает 1 тестирование то оно может оказаться простым, а может быть и непростым. Если успешно проходит ряд испытаний с различными случайно выбраными значениями А, то это дает больше увереность что n является простымю.

Процедура выбора простого чилса:

1) выбрать нечетное целое число некоторым случайным образом.

2) выбирается целое число А<n случайным образом.

3) выполняется вероятносный тест на простоту числа. Если n выдерживает достатотчное число испытаний то оно принимается подходящим на роль целого и простого.