Целочисленная проблема факторизации (IFP): RSA и Рабин-Уильям

Описание задачи

Целочисленная проблема факторизации (IFP): находит p и q, учитывая составное число n, который является произведением двух больших простых чисел p и q.

    Обнаружение больших простых чисел - относительно простая задача, а проблема разложения на множители, произведение двух таких чисел рассматривается в вычислительном отношении труднообрабатываемым. Базирующиеся на трудности этой проблемы Ривест, Чамир и Адлеман разработали RSA общее - ключевую систему шифрования.

В то время как целочисленная проблема факторизации занимала внимание известных математиков подобно Фермату и Гауссу более чем столетия ,только в прошлых 20 годах был сделан прогресс в разрешении этой проблемы. Имеются две главных причины для этого явления. Сначала, изобретение RSA-системы шифрования в 1978 стимулировало много математиков к изучению этой проблему. И быстродействующие ЭВМ стали доступными для выполнения и испытания сложных алгоритмов. Фермат и Гаусс имели небольшой стимул для изобретения алгоритма разложения на множители решета поля цифр, так как этот алгоритм более громоздкий ,чем испытательное деление с целью разложения на множители целых чисел вручную.

Разложения на множетели

Имеются в основном два типа специализированных и универсальных алгоритмов разложения на множители. Специализированные алгоритмы разложения на множители пытаются эксплуатировать специальные особенности номера n разлагаемого на множители. Текущие времена универсальных алгоритмов разложения на множители зависят только от размера n.

Один из наиболее мощных специализированных алгоритмов разложения на множители - эллиптический метод разложения на множители кривой (режим исправления ошибок), который был изобретен в 1985 Х.Ленстром младшим. Текущее время этого метода зависит от размера главных множителей n, и следовательно алгоритм имеет тенденцию находить сначала маленькие множители. 21 июня 1995 Andreas Mueller (студент в Universitaet des Saarlandes, Германия) объявил, что он нашел 44-десятичную цифру с 147-разрядным множителем 99-десятичной цифрой с 329-разрядным составным целым числом, используя режим исправления ошибок. Вычисление было выполнено на сети АРМ, и долговечность была приблизительно 60 MIPS годы. Самый большой главный множитель, найденный к настоящему времени режимом исправления ошибок - 47-десятичная цифра с 157-разрядным главным множетелем 135-десятичной цифры 449-разрядный номер. До развития RSA системы шифрования, лучший универсальный алгоритм разложения на множители был алгоритм цепной дроби , который имел числа множителя до 40 десятичных цифр (133 бита). Этот алгоритм был основан на идее относительного использования основы множителя штрихов и производства связанного с набором линейных уравнений, чее решение в конечном счете вело к факторизации. Та же самая идея лежит в основе лучших универсальных алгоритмов, используемых сегодня: квадратичное решето (QS) и решето поля цифр (NFS). Оба эти алгоритмы могут быть легко параллелизованы, чтобы разрешить разложение на множители на распределительных сетях АРМ. Квадратичное решето было разработано Карлом Померансом 1984. Первоначально, это применялось к числам множителя в 70-десятичной цифре 233-разрядный диапазон. В 1994 это использовалось группой исследователей во главе с А.Ленстром к множителю 129-десятичной цифры 429-разрядного номера проблемы RSA, который был изложен Мартином Гарднером 14 1977. Факторизация была выполнена через 8 месяцев примерно на 1600 компьютерах во всем мире. Долговечность для факторизации была оценена как 5000 MIPS годы.

Сначала было разработано в 1989 ,что Решето поля цифр работает лучше всего на числах специальной формы. Алгоритм привык к множителю 155-десятичной цифры 513-разрядного номера. Это было впоследствии расширено к универсальному алгоритму факторизациию. Эксперименты доказали, что NFS является действительно превосходящим алгоритмом для целых чисел разложения на множители, имеющих по крайней мере 120 десятичных цифр (400 битов). В 1996, группа во главе с А.Ленстром использовала NFS к множителю 130-десятичной цифры 432-разрядного номера. Это - самый большой номер, разложенный на множители до настоящего времени. Факторизация, как оценивали, брала меньше чем 15 % из 5000 MIPS годы, которые требовались для факторизации 129-десятичной цифры проблемы RSA. Разложение на множители 155 десятичной цифры 512-разрядного номера могло брать меньше усилия в 5 раз. 512-разрядный модуль n обеспечивает только крайнюю защиту , когда используется в RSA системе шифрования.

3.2.Дискретная проблема логарифма (процессор передачи данных):

Описание задачи

Алгоритм цифрового представления Американского правительства (системный агент каталога), Diffie-Hellman ключевая схема соглашения, ElGamal кодирование и схемы сигнатуры, Schnorr схема сигнатуры, и Nyberg-Rueppel схема сигнатуры.

Если p - простое число, то Zp обозначает набор целых чисел 0, 1, 2,..., p - 1, где сложение и амплитудное искажение - выполняются с модулем. Известно, что существует ненулевой элемент О Zp такой, что каждый ненулевой элемент в Zp может быть написан как мощность a, такой элемент называется генератором Zp.

Дискретная проблема логарифма (процессор передачи данных) заключается в следующем: учитывая штрих p, генератор Zp, и ненулевой элемент О Zp, находит уникальное целое число 0,1,2,..., p - 2, такое что b принадлежит

 al (mod p). Целое число l называется дискретным логарифмом b к основе a.

Базируясь на трудности этой проблемы, Диффи и Хеллман предложили известную Diffie-Hellman ключевую схему соглашения в 1976. С тех пор были предложены многочисленные другие криптогафические протоколы, чья защита зависит от процессора передачи данных, включая: Американский правительственный алгоритм цифрового представления (системный агент каталога), ElGamal кодирование и схемы сигнатуры, Schnorr схема сигнатуры, и Nyberg-Rueppel схема сигнатуры.С должным интересом процессор передачи данных экстенсивно изучился математиками в течение прошлых 20 лет.