Студопедия — О стойкости криптосистемы RSA
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

О стойкости криптосистемы RSA






Безопасность алгоритма RSA основана на трудоемкости разложения на большие простые множители больших целых чисел. Современное состояние технических средств разложения на множители таково, что число, содержащее в записи 193 десятичных знака, факторизовано в 2005 г. Следовательно, выбираемое значение N должно быть больше. Большинство общепринятых алгоритмов вычисления простых чисел p и q носят вероятностный характер.

О выборе чисел p и q

Для работы алгоритма RSA нужны простые числа. Наиболее приемлемым является генерация случайных чисел и последующая проверка их на отношение к простым числам. Существуют вероятностные тесты, определяющие с заданной степенью достоверности факт простоты числа. Возникает вопрос, что произойдет, если числа окажутся составными? Можно свести вероятность такого события до приемлемого минимума, используя тесты на простоту. Кроме того, если такое событие произойдет, это будет быстро обнаружено — шифрование и расшифрование не будет осуществлено.

Кроме разрядности p и q, к ним предъявляются следующие дополнительные требования:

– числа не должны содержаться в списках известных больших простых чисел;

– они не должны быть близкими, так как иначе можно воспользоваться для факторизации N методом Ферма и решить уравнение .

– в алгоритме RSA всегда есть эквивалентные по расшифрованию показатели степеней, например d и . При этом эквивалентных решений тем больше, чем больше (p – 1, q – 1).

В лучшем случае (p – 1, q – 1) = 2, p = 2 t + 1, q = 2 s + 1, где s, t – нечетные числа с условием, - НОД (s, t) = 1.

Чтобы исключить возможность применения методов факторизации накладывают следующее ограничение: числа p – 1, p + 1, q – 1, q + 1 не должны разлагаться на сомножители в виде произведения малых простых множителей, должны содержать в качестве сомножителя хотя бы одно большое простое число.

В 1978 г. Райвест сформулировал наиболее сильные требования.

Числа должны быть простыми, причем числа p 1 – 1 и q 1 – 1 не должны разлагаться в произведение малых простых чисел.

О выборе параметров e и d

Рассмотрим вопрос о выборе экспонент шифрования и расшифрования.

Так как значения е и d определяют время зашифрования и расшифрования, то можно назвать ряд ситуаций, в которых желательно иметь малое значение е и d. Например, при использовании системы RSA при защите электронных платежей с применением кредитных карточек естественным является требование использования небольших значений экспоненты d у владельца карточки и большого значения экспоненты e у центрального компьютера.

Однако выбор малых параметров е или d представляется небезопасным по ряду соображений.

Если малым является секретный параметр d, то можно применить метод перебора малых значений до получения искомого числа d. А если малым является параметр е, то достаточно большое число открытых сообщений, удовлетворяющих неравенству будут зашифровываться простым возведением в степень y = xe (mod N) и поэтому их можно найти путем извлечения корня степени е.

Другая аналогичная ситуация может сложиться, когда у нескольких абонентов используется одинаковая экспонента е. Тогда становится возможна атака на основе китайской теоремы об остатках.

 







Дата добавления: 2014-11-10; просмотров: 799. Нарушение авторских прав; Мы поможем в написании вашей работы!



Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

Картограммы и картодиаграммы Картограммы и картодиаграммы применяются для изображения географической характеристики изучаемых явлений...

Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

ИГРЫ НА ТАКТИЛЬНОЕ ВЗАИМОДЕЙСТВИЕ Методические рекомендации по проведению игр на тактильное взаимодействие...

Реформы П.А.Столыпина Сегодня уже никто не сомневается в том, что экономическая политика П...

Виды нарушений опорно-двигательного аппарата у детей В общеупотребительном значении нарушение опорно-двигательного аппарата (ОДА) идентифицируется с нарушениями двигательных функций и определенными органическими поражениями (дефектами)...

Ганглиоблокаторы. Классификация. Механизм действия. Фармакодинамика. Применение.Побочные эфффекты Никотинчувствительные холинорецепторы (н-холинорецепторы) в основном локализованы на постсинаптических мембранах в синапсах скелетной мускулатуры...

Шов первичный, первично отсроченный, вторичный (показания) В зависимости от времени и условий наложения выделяют швы: 1) первичные...

Предпосылки, условия и движущие силы психического развития Предпосылки –это факторы. Факторы психического развития –это ведущие детерминанты развития чел. К ним относят: среду...

Studopedia.info - Студопедия - 2014-2024 год . (0.008 сек.) русская версия | украинская версия