Однонаправленные функции. Факторизация и дискретное логарифмирование

Однонаправленные функции используются для создания криптосистем с отрытым ключем.

Однонаправленные функции

Понятия однонаправленной функции и однонаправленной функции с "потайным ходом" являются центральными понятиями всей криптографии с открытым ключом.

Функция F(x) = yназывается однонаправленной при выполнении 2-х условий:

• при любом x вычислить F(x) = y было легко;
• зная y, вычислить такой x, чтобы F(x) = yбылонедостижимо трудно.

Очевидно, что однонаправленные функции не могут непосредственно использоваться в качестве криптосистем, поскольку тогда даже законный получатель не сможет раскрыть зашифрованный текст!

Поэтому используется понятие однонаправленной функции с потайным ходом. Функция F(x) = yназывается однонаправленной функцией с потайным ходом, если она может эффективно вычисляться в обе стороны при условии знания определенного секрета.

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

Однонаправленными (на современном уровне наших знаний) являются функции:

–      Умножение целых чисел f(x, y) = xy

–      Возведение заданного числа в степень по данному модулю F_n,a(m) = a^m mod n

–      Возведение числа в заданную степень по данному модулю F_n,a(a) = a^m mod n

Нахождение функций, обратных к данным, приводит к задачам:

–      Факторизация целого числа: f = xy, найти x и y, зная f.

–       Дискретное логарифмирование: пусть f_n,a(m) = a^m modn, найти m, зная n, f, a.

–      Извлечение корня по модулю: пусть F_n,a(a) = a^m modn, найти a, зная n, f, m.

Примечание: mod – остаток от деления

З а м е ч а н и е (об извлечении корня по модулю). Для последней задачи точно известно, что существует эффективный алгоритм, находящий корень по модулю или устанавливающий, что такого корня нет. Выяснено, что для построения эффективного алгоритма достаточно знать разложение n на простые множители. Таким образом, используемых односторонних функций, собственно, две, и современные криптосистемы почти все основаны на проблеме факторизации целых чисел или на проблеме дискретного логарифма в конечной абелевой группе. Задачи эти в настоящее время одинаково трудны.

Факторизация(разложение на множители) — представление целого числа в виде произведения простых делителей

N = p * q , например

• 10 = 2 * 5,
• 1993423291715412685783 = 1868569 * 1066818132868207

Определение множителей является очень трудоемкой вычислительной операцией.

Дискретное логарифмирование – задача обращения функции A^X = B.

Обратная данной функции будет x = log_AB.

Эффективные алгоритмы для решения этой задачи пока не известны.

Факторизация

Существует несколько методов факторизации числа N = p * qс простыми p и q:

Средневековые методы

• Пробное деление,
• (p – 1)—метод,
• (p + 1)-метод,
• p-метод Полларда.

Современные методы:

• Метод непрерывных дробей,
• Квадратичное решето,
• Квадратичное решето в числовом поле.

Время работы современных алгоритмов лежит где-то между полиномиальным и экспоненциальным, т.е. в суб-экспоненциальной области. Средневековые методы имеют экспоненциальную сложность.

Рассмотрим более подробно метод пробного деления, для рассмотрения других методов обратимся к дополнительной литературе.

Пробное деление. Это элементарный алгоритм факторизации.

N= р* q (р и q— простые числа) B этом алгоритме для всех простых чисел p, не превосходящих N проверяется условие — является ли N/р целым числом. Также существуют дополнительные условия, по которым мы может отсеять заведомо непростые числа, чтобы не тратить время на их проверку, например никакое четное число больше 2 не может быть простым, а любое число с суммой цифр, кратной 3 делится на 3 и т.д.

Алгоритм имеет экспоненциальную сложность.

В известном конкурсном списке RSA приводятся большие числа, за факторизацию которых объявлены премии. Выпишем здесь для наглядности два из этих чисел:

число RSA-640 (640 двоичных, 193 десятичных цифры, уже факторизовано):

31074182404900437213507500358885679300373460228427275457201619488232064405180815045563468296а23286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609;

число RSA-704 (704 двоичных, 212 десятичных цифр, не факторизовано, премия $30000):

74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359.

RSA (Rivest, Shamir, Adleman)

На односторонней функции f(x, y) = xy основана предложенная в 1978 г. и выдержавшая испытание временем криптосистема RSA (Rivest, Shamir, Adleman).

Представим себе сеть абонентов, где каждые два должны иметь возможность обмениваться секретной информацией.

Каждый из абонентов сети:

–      выбирает 2 различных простых числа p и q;

–      находит n = pq и функцию Эйлера m = (p–1)(q–1);

–      Выбирает целое число e, взаимно простое с m.

–      Вычисляет число d, удовлетворяющее условию: ed = 1 (mod m).

–      Секретным ключом абонента является тройка чисел (p, q, d), открытым ключом — пара чисел (n, e).

–      Открытые ключи всех абонентов помещаются в общедоступный справочник.

Закодированный с  помощью RSA текст защищён от несанкционированного прочтения настолько, насколько затруднено разложение на множители числа n.

Дискретный логарифм

Идея, лежащая в основе подобных систем, опирается на высокую вычислительную сложность обращения функции F_n,a(x) = a^x modn

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

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

Классическими криптографическими схемами, базирующимися на сложности задачи дискретного логарифмирования, являются схема выработки общего ключа Диффи-Хеллмана, система электронной подписи Эль-Гамаля, криптосистема Мэсси-Омуры для передачи сообщений.

Алгоритмы решения:

Существует алгоритм решения для любых групп чисел, но он медленный и не пригоден для практического использования. Для конкретных групп существуют свои, более эффективные, алгоритмы:

–      В кольце вычетов по простому модулю(не все эти алгоритмы обладают суб-экспоненциальной сложностью)

–      В произвольном конечном поле

–      В группе точек на эллиптической кривой