Можно долго писать о том, что информация — это лоскуты, из которых соткан мир, и нам стоит ее беречь, но все мы тут серьезное люди и жаждем науки на пальцах. Так что резко, сейчас, моделируем ситуацию: ты, в отчаянных попытках завоевать интересующую тебя особь, хочешь отправить ей изображение Аполлона (себя), но господин майор не дремлет! Так что, если хорошенько не зашифровать сообщение, он умрет со смеху. [Если холодный пот не проступил, то попробуй все по стандарту: ты связист в окопе зимой 43-го]

В обоих случаях, как ты понимаешь, ситуация безотлагательная. Надо действовать!

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

Не одни мы сталкиваемся с такими проблемами, так что в 1976 году американскими информатиками был придуман алгоритм RSA, который дал начало асимметричным шифрам. Рассмотрим его на примере двух собеседников — Гали и Какия.

Какий берет два простых числа и перемножает их, чтобы получить максимум (П1 * П2 = M), затем выбирает простое число для открытого ключа (О). Дальнейший шаг Какия — получить секретный ключ (С), и для этого он использует расширенный алгоритм Евклида (это найти НОД + найти коэффициенты x и y: a*x + b*y = gcd(a,b).) Теперь он отправляет пару (M, О) Гале, а секретный ключик оставляет в потайном месте.

Галя эту пару получает и зашифровывает свое сообщение следующим образом. Например, она хочет передать выражение FUCK OFF, string у нас, так сказать не зарезервирован, так что переводим в числа: F — это 70 (кодировка UTF-8 естессна). Попробуем зашифровать, 70^О и смотрим, чтобы на каждой итерации полученное число было меньше максимума. Если нет, то мы «докручиваем» его до нужного нам диапазона [0,M] и берем остаток, затем repeat. Когда мы все уже зашифровали — отправляем Какию, и он проводит ту же операцию, что и Галина, только уже с (С), а не с (P).

Ашушчэнне какого-то наебалова, да? Как это, используя два разных ключа, собеседники понимают друг друга ? Вся обнаженка процесса в использовании идеи односторонних функций. Односторонняя функция с потайным входом (TDF) предполагает, что по известному x довольно легко найти f(x), но вот из f(x) найти x — нихуевая такая задача. Чтобы это все дело закрепить, представь, что функция — это мееелкий-мелкий шредер, а x — лист бумаги. В нашем алгоритме в роли односторонней функции выступает факторизация, это одна из самых известных штуковин, заимствованных из теории чисел. [В принципе, под лозунгом «Попробую. Хули нет» майор может использовать отмычки в виде Quadratic Sieve и General number field sieve]. Вторая пиздатая функция — это F(a, n) = a (mod M), где a, n и M — целые числа. При известных a, n и M значение b = a (mod M) может быть вычислено за полиномиальное количество шагов. Однако для обратной задачи — задачи дискретного логарифмирования — определить n по известным a, b и M {пока, в общем случае} нельзя. Собственно, на этой фиче и основана эллиптическая криптография.

Давай теперь разберемся, каким образом линии в виде колокольчиков (дзинь-дзинь) помогут тебе в романтических отношениях. Вообще говоря, эллиптические кривые представляют собой абелеву группу над полем Галуа. {Поздравляю: если ты понял о чем речь, то наверняка не проебывал пары у того деда по матану. Если не понял — поймешь через пару абзацев.} Если попроще, то давай взглянем на нашу кривую: она обладает рядом особенностей. Одна из них — горизонтальная симметрия. Каждую точку кривой можно зеркально отобразить, и ты окажешься на все той же кривой. Еще забавно то, что любая не строго вертикальная прямая пересекает эллиптическую кривую не более чем в трех местах. То есть если представить, что ты стоишь в точке P и бросаешь мяч в точку на стене B, то он обязательно отскочит в симметричную точку C.

Что-то кажется тебе знакомым? Не то ли мы обсуждали в RSA? Мы точно так же сколько-то раз умножали исходное число само на себя (или на «докрученный» результат). Все эти точки мяча — такие же промежуточные результаты, только полученные не арифметически, а геометрически. Интуитивно понятно, что если мы имеем две точки — начальную, помноженную на себя n раз, и конечную — нам довольно-таки сложно найти n. Но подожди, в RSA мы работали как бы в модульной арифметике, давай и тут попробуем!

Возьмем из всех точек кривой только целые и те, что до нашего максимума — тогда мы получим множество хаотично разбросанных точек. Это будет совсем не похоже на школьную кривую — но это она! И горизонтальная симметрия сохранилась, поэтому мы с тобой все еще можем играть в мяч. С помощью такой «кривой» уже реально зашифровать наше сообщение. Можно представить исходное число сообщения как x и получить из уравнения эллиптической кривой y — и, соответственно, точку на кривой. На практике конечно же все сложнее, но идея-то какая!

Получается, эллиптическую криптосистему определяют: взятое за максимум простое число, уравнение кривой и открытая (стартовая) точка на кривой. Секретным ключом будет число p, а открытым ключом — стартовая точка, соединенная сама с собой p раз. Вычисление секретного ключа по открытому в такой криптосистеме называется функцией дискретного логарифма эллиптической кривой (или, в рамках нашей истории — «майор иди на хуй»). Кажется, это и есть то, что мы искали! До скорых встреч.

P.S.
Если остался вопрос, нахуя нам эллиптические кривые, если есть RSA: мы можем использовать ключи меньшей длины и получать тот же уровень безопасности.

P.P.S.
Группа — это множество, для которого мы выдумали двоичную операцию сложения, а также потребовали, чтобы оно обладало четырьмя свойствами: замыкание, ассоциативность (скобки можно переставлять), единичный элемент и обратная величина {добавив сюда коммутативность, можно назвать группу абелевой}.

Теперь о полях: поле Галуа или конечное поле — это, в первую очередь, множество конечного числа элементов. Отличный пример такого поля — множество целых чисел по модулю p (простое число), в нем сложение и умножение работают как в модулярной арифметике (это именно то, что мы «докручивали» в алгоритме RSA). По сути, через одно предложение мы потребовали, чтобы для всех точек эллиптической кривой (которая уже на картинке даже не кривая, а просто точечки) каким-то образом были определены разные «обычные» для нас операции — и мы к тому же, запихнули их в конечное поле, в котором эти операции тоже работают! Успех!




Спасибо за то, что вы с нами.
С любовью, Рителлинг favorite