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

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

Рассмотрим два произвольных множества X и Y . Функция f: X -> Y называется однонаправленной, если f(x) может быть легко вычислена для каждого x из X, тогда как почти для всех y из Y вычисление такого x из X, что f(x) = y (при условии, что хотя бы один такой x существует), является сложным. Это понятие не нужно путать с функциями, которые являются математически необратимыми из-за того, что они не взаимнооднозначны.

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

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

Конечно, необходимо понимать, что "не в состоянии" означает "не в состоянии за приемлемое время (такое, как время человеческой жизни или возраст вселенной)".

Другим важным примером кандидата на однонаправленную функцию является модульное возведение в степень или модульное экспонирование (с фиксированными основанием и модулем). Пусть n и a – целые числа, такие что 1 < a < n, и пусть Zn = { 0,1,2,…,n-1 }. Тогда модульное возведение в степень ( относительно основания a и модуля n) это такая функция f[a,n]: Zn -> Zn, определяемая как f[a,n](m) = a^m mod( n), где i mod(j) обозначает положительный остаток при делении i на j. Сразу не очевидно, что такую функцию можно вычислить эффективно, когда длина каждого из трех параметров a, n и m составляет несколько сотен знаков. То, что это возможно и в самом деле так, лучше всего увидеть на примере:
a25=(((a2*a)2)2)2*a.

Он показывает, как можно вычислить a25 c помощью лишь четырех возведений в квадрат и еще двух умножений. При вычислении am mod(n) произведение по модулю n желательно делать после каждого возведения в квадрат и каждого умножения, чтобы избежать получения очень больших целых чисел. Если экспонента m является числом длиной в L битов, то следующему рекурсивному алгоритму, для того чтобы вычислить am mod(n), требуется от L до 2L модульных умножений (считая умножением и возведение в квадрат):

function expo(a,m,n)
if m=0 then return 1
if m четно then return ((expo(a,m/2,n)^2 mod(n))
else return((a*expo(a,m-1,n) mod(n))

По аналогии с действительным анализом обратная операция известна как задача дискретного логарифмирования: даны целые числа a, n и x, требуется найти такое целое m (если оно существует), что am mod(n) = x. Например, 54 mod(21) = 16. Следовательно, 4 это дискретный логарифм 16 с основанием 5 по модулю 21. При желании можно проверить, что, например, число 3 вообще не имеет логарифма с основанием 5 по модулю 21. Несмотря на то, что вычисление больших модульных экспонент может быть осуществлено эффективно, в настоящее время неизвестно ни одного алгоритма для вычисления дискретных логарифмов больших чисел за приемлемое время даже на самых быстродействующих компьютерах.

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

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

Более употребимым в криптографии является понятие однонаправленной функции с потайным ходом. Функция f: X -> Y называется однонаправленной функцией с потайным ходом, если она может эффективно вычисляться как в прямую так и в обратную сторону, более того, может быть даже известен эффективный алгоритм вычисления f такой, что полное знание того, как этот алгоритм работает, не дает никакой возможности разработать эффективный алгоритм вычисления обратной ей функции.

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

Наш первый кандидат на однонаправленную функцию с потайным ходом очень похож на нашего второго кандидата на просто однонаправленную функцию: модульное возведение в степень с фиксированной экспонентой и модулем. Пусть m и n – целые числа, а Zn определено так же, как и ранее. Тогда модульное возведение в степень (относительно экспоненты m и модуля n) есть функция g[m,n]: Zn -> Zn, определенная следующим образом: g[m,n](a) = am mod(n).

Необходимо убедиться в понимании различия между функциями f[a,n] и g[m,n].

Опять по аналогии с действительным анализом, операция обратная g[m,n] известна под названием взятия корня m-той степени из x по модулю n: даны целые числа m, n и x, найти такое целое a(если оно существует), что am mod(n) = x. Например, 5 это корень 4-ой степени из 16 по модулю 21, так как мы уже видели, что 54 mod(21) = 16. Очевидно, что 2 также является корнем 4-ой степени из 16 по модулю 21. Можете ли Вы найти другие корни 4-ой степени из 16 по модулю 21 ? Найдите целое число x, которое не имеет корней 4-ой степени по модулю 21.

В том случае, когда экспонента m и модуль n фиксированы, мы уже приводили эффективный алгоритм вычисления g[m,n](a) для любого основания a.

В противоположность задаче дискретного логарифмирования, тем не менее, известно, что существует также и эффективный алгоритм взятия корня m-ой степени их x по модулю n (или выяснения, что его не существует) для любого заданного x. Любопытный феномен заключается в том, что неизвестно, как эффективно построить этот эффективный алгоритм при заданных лишь m и n. Другими словами, функция g[m,n] в действительности не является однонаправленной, поскольку мы знаем, что она может быть эффективно обращена, но несмотря на этот факт мы не знаем, как это сделать!

Тем не менее, легко построить эффективный алгоритм вычисления m-ого корня по модулю n при условии, что известно разложение n на простые множители. Именно по этой причине g[m,n] и является кандидатом на однонаправленную функцию с потайным ходом, для которой m и n используются как открытая информация, тогда как разложение служит в качестве секретного потайного хода.

Важный специальный случай модульного возведения в степень имеет место, когда экспонента равна 2 и когда модуль является числом специального вида. Для понимания этого второго примера кандидата на однонаправленную функцию с потайным ходом необходимы дополнительные сведения из теории чисел. Если p и q два различных больших простых числа примерно равного размера, и если оба p и q сравнимы с 3 по модулю 4, то мы будем говорить, что их произведение n = p*q является целым числом Блюма. Определим Zn* как множество целых между 1 n-1, которые не делятся ни на p ни на q. Наконец, определим QRn как подмножество Zn*, состоящее из чисел, которые являются совершенными квадратами по модулю n. Элементы QRn известны как квадратичные вычеты по модулю n.

В качестве небольшого примера рассмотрим p = 19 и q = 23, таким образом n=437. В этом случае 135 является элементом Zn*, в то время как 133 нет(поскольку 133 = 19*7). Кроме того 135 не является квадратичным вычетом по модулю 437, так как не существует целого числа a такого, что a^2 = 135 (mod 437), тогда как 139 является квадратичным вычетом, так как 24^2 = = 576 = 139 (mod437).

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

Число элементов в Zn* равно (p-1)*(q-1), и ровно одну четвертую часть из них составляют квадратичные вычеты. Каждый квадратичный вычет допускает в точности четыре различных "квадратичных корня" в Zn*, из которых лишь один единственный сам является квадратичным вычетом. Этот особый корень мы назовем главным квадратичным корнем.

В нашем примере 24 это главный квадратичный корень из 139 по модулю 437, а другими тремя корнями являются 185,252 и 413. Имеющий криптографическое значение факт заключается в том, что способность определять квадратические корни по модулю n оказывается вычислительно эквивалентной умению раскладывать n на множители. Иначе говоря, тот кто знает разложение n на множители может эффективно вычислять главные квадратичные корни по модулю n, тогда как такие вычисления столь же трудны сколь и факторизация n для того, кто этого разложения еще не знает. Наш второй кандидат на однонаправленную функцию с потайным ходом теперь должен быть очевиден. Вы случайно выбираете p и q и вычисляете n = p*q, которые открыто объявляете. После этого любой может эффективно вычислить квадраты по модулю n, но только ваш друг может эффективно обратить эту операцию (в предположении, что факторизация трудна).

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

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100