3.4.Безопасность rsa

Безопасность RSA полностью зависит от проблемы разложения на множители больших чисел. Технически, это утверждение о безопасности лживо. Предполагается, что безопасность RSA зависит от проблемы разложе­ния на множители больших чисел. Никогда не было доказано математически, что нужно разложить n на множи­тели, чтобы восстановить m по с и е. Понятно, что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот новый способ позволит криптоаналитику получить d, он также может быть использован для разложения на множители больших чисел. Я не слишком волнуюсь об этом.

Также можно вскрыть RSA, угадав значение (p-l)(q-l). Это вскрытие не проще разложения n на множители.

Для сверхскептиков: доказано, что некоторые варианты RSA также сложны, как и разложение на множители. Раскрытие даже нескольких битов информации по зашифрованному RSA шифротексту не легче, чем дешифрирование всего сообщения .

Самым очевидным средством вскрытия является разложение n на множители. Любой противник сможет получить открытый ключ е и модуль n. Чтобы найти ключ дешифрирования d, противник должен разложить n на множители. В настоящее время передним краем этой технологии является число, содержащее 129 десятичных цифр. Значит, n должно быть больше этого значения.

Конечно, криптоаналитик может перебирать все возможные d, пока он не подберет правильное значение. Но такое вскрытие грубой силой даже менее эффективно, чем попытка разложить n на множители.

Время от времени появляются заявления о том, что найден простой способ вскрытия RSA, но пока ни одно из подобных заявлений не подтвердилось. Например, в 1993 году в черновике статьи Вильяма Пейна был предложен метод, основанный на малой теореме Ферма. К сожалению, этот метод оказался медленнее разложения на множители

Существует еще один повод для беспокойства. Большинство общепринятых алгоритмов вычисления простых чисел и q вероятностны, что произойдет, если р или q окажется составным? Ну, во-первых, можно свести ве­роятность такого события до нужного минимума. И даже если это произойдет, скорее всего такое событие будет сразу же обнаружено - шифрование и дешифрирование не будут работать. Существует ряд чисел, называемых числами Кармайкла, которые не могут обнаружить определенные вероятностные алгоритмы поиска простых чисел. Они небезопасны, но чрезвычайно редки.

3.5. Эллиптическая криптография кривой.

После изобретения шифрования с открытым ключом, были предложены многочисленные общее - ключевые системы засекречивания на ее основе. Криптография с открытым ключом может применяться как для шифрования сообщений , так и для аутентификации (так называемая цифровая подпись).

Каждая из этих систем полагается на трудную математическую проблему для ее защиты. Они являются труднообрабатываемыми, потому что годы интенсивного изучения ведущими математиками и компьютерными учеными не сумели создать эффективные алгоритмы для их решения, так, чтобы практически, они остались труднообрабатываемыми с текущей вычислительной технологией. Требуется время , чтобы получить безопасный ключ с лучшим известным алгоритмом для этой проблемы. Обще - ключевая система шифрования, основана на этой проблеме. Эллиптические кривые - математические конструкции, которые изучались математиками начиная с семнадцатого столетия. В 1985 Нейл Коблиц и Виктор Миллер независимо предложили криптосистемы с ключом общего пользования, использующие группу точек на эллиптической кривой, и эллиптическая криптография кривой (код с исправлением ошибок) была рождена. Начиная с того времени, многочисленные исследователи и разработчики потратили несколько лет, исследуя силу кода с исправлением ошибок и улучшая методы для его выполнения. Сегодня более быстрая криптосистема с ключом общего пользования предлагает практическую и безопасную технологию для наиболее сдерживаемой среды.

Код с исправлением ошибок дает самую высокую силу в любой известной криптосистемы с ключом общего пользования из-за трудности жесткой проблемы, на которой это основано. Эта большая трудность жесткой проблемы эллиптической кривой, дискретной проблемы логарифма (ECDLP) означает что меньший размер ключа выдает эквивалентные уровни защиты. Учитывая лучшие известные алгоритмы к целым числам множителя и вычисляют эллиптические логарифмы кривой, размеры ключа являются эквивалентной силой, основанной на MIPS годах, необходимых, чтобы восстановить один ключ.