...и вопрос открыт до сих пор. :)

Вот статья Иврия 1980 года — http://mi.mathnet.ru/faa1796 — а теорему о том, что таких четырёхугольных траекторий не бывает, доказали Глуцюк и Кудряшов в 2012 году:
http://www.aimsciences.org/article/doi/10.3934/jmd.2012.6.287

(Про треугольные знали раньше, пятиугольные и выше — вопрос всё ещё открыт...)

Ну и на этой истории я хочу на сегодня прекратить дозволенные речи.

Сегодняшняя байка будет о применении эллиптических кривых в криптографии, как для защиты (что более известно), так и для «нападения»-факторизации (что,
почему-то, известно заметно меньше, хотя алгоритм именной, называется алгоритмом Ленстры).
(На всякий случай: рассказ по открытым источникам :) )

Но сначала — старая красивая задача: в одной далёкой стране почта доставляет любую посылку по адресу, но всё, что из неё можно изъять без применения ломика
с автогеном, исчезает. В этой стране живут два человека, А и Б, и А хочет переслать Б бриллиант. У каждого из них есть свой навесной замок (с ключом),а у А ещё и железный ящик с петлями, на который такой замок можно навесить — если ящик закрыть на замок, внутрь залезть никто не сможет. Но без ключа тогда открыть его нельзя.
Вопрос: как А переслать Б бриллиант?

Скажем, А может отправить Б ящик с бриллиантом, закрытый на замок. И Б его получит. Но без ключа А получатель не сможет этот замок открыть — а задача пересылки ключа ничем не отличается от пересылки бриллианта.

Если вдруг вы эту задачу не решали — она очень классная, и над ней стоит подумать. (Но в следующих сообщениях будет решение и его обсуждение, так что тогда пока не читайте дальше, или подождите немного и промотайте сильно вниз!)

Так вот — первым делом А приходится прислать Б ящик с бриллиантом, закрытый на замок А. Но после этого Б — от обиды, что не может открыть — навешивает на него ещё и свой замок!
И посылает обратно А ящик, закрытый уже на два замка, и А, и Б. Получив его, А со словами « это моё, это я заберу » снимает свой замок — остаётся ящик с бриллиантом, закрытый на замок Б. Он его пересылает Б, тот снимает свой замок и забирает бриллиант.

Давайте уберём метафору и посмотрим, что же нужно, чтобы эта схема функционировала.

Замок и ключ, это, конечно, шифры, а бриллиант — пересылаемое сообщение. И тут нужны две важные вещи:
*) шифры должны коммутировать: мы взяли сообщение, сначала зашифровали его шифром А, а потом результат шифром Б; после этого « снимаем замок А » — применяем расшифровывающее отображение — и хотим получить сообщение, зашифрованное чисто шифром Б.
*) знание для одного из шифров какой-то пары из исходного и зашифрованного сообщения не должно помогать атакующему: по открытому каналу передаются как «сообщение» А(бриллианта), так и его «результат Б-шифровки» Б(А(бриллианта)).

Так, есть простой шифр « прибавление секретного ключа K » [например, с приведением по публично объявленному модулю].
Он удовлетворяет первому условию — прибавления ключей K_A и K_B коммутируют — но не удовлетворяет второму: по сообщению и его зашифрованному образу атакующий мгновенно восстанавливает секретный ключ, и дальше расшифровывает все остальные сообщения.

Зато можно такую схему реализовать с возведением в степень вместо сложения (и получается не алгоритм RSA, хоть и визуально похожий). А именно:
*) Публично объявлено большое [как положено, сотня-тысяча знаков) простое число P.
*) У каждого из А и Б есть свои секретные ключи — [большие] числа a и b, взаимно простые с P-1.

Раз a и P-1 взаимно-простые, то из алгоритма Евклида А знает такое R, что aR сравнимо с 1 по модулю P-1.
И тогда по модулю P операции возведения в степень a и в степень R взаимно-обратны: для любого
сообщения M выполнено (M^a)^R=M^(aR) = M, поскольку M^(P-1)=1, а aR=1 mod (P-1).
Поэтому возведение в степень a можно счесть « А-шифровкой », а в степень R — « А-расшифровкой »

Точно так же, Б знает такое S, что bS=1 mod (P-1), и возведения в степень b и в степень S обратны
друг другу, и мы возьмём их как Б-шифрование и Б-расшифровку.

Ну и, чтобы передать сообщение M от A к Б, им достаточно переслать друг другу сообщения (каждый раз приводя результат по модулю P, я этого каждый раз писать не буду):
1) (А вычисляет и отправляет) M^a
2) (Б добавляет свой шифр и пересылает обратно) (M^a)^b=M^(ab)
3) (А снимает свой шифр и пересылает опять Б) (M^(ab))^R = M^(abR)= M^b
4) (Б снимает свой шифр) (M^b)^S=M^(bS)=M.
Ура!

И видно, что формально-математически знание (M^a) и (M^a)^b позволяет восстановить b — но это задача « дискретного логарифмирования ». Соответственно, нужно, чтобы она была сложной (ну и, как совсем не специалист, я не полезу в вопросы того, когда она считается сложной, а когда нет).

См.: https://en.wikipedia.org/wiki/Three-pass_protocol
+ https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%9C%D1%8D%D1%81%D1%81%D0%B8_%E2%80%94_%D0%9E%D0%BC%D1%83%D1%80%D1%8B

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

А именно — много что можно сделать, если у двух сторон есть общий секретный ключ. Только вот как сделать так, чтобы он оказался у обоих сторон сразу?

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

Это называется «шифр Вернама» ( https://ru.wikipedia.org/wiki/шифр_Вернама ), и при условии секретности (и случайности, и однократного использования) ключей он абсолютно надёжен —
любое кодированное сообщение может быть шифром любого исходного, если монетка выпадала нужной последовательностью. И с точки зрения перехватывающего, все возможные исходные сообщения равновероятны.

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

В качестве отступления в сторону: когда в 1940-ых в советской шифрованной переписке произошло повторное использование кодовых страниц (делающее атаку на шифр возможной) — американцы смогли некоторые сообщения расшифровать ( https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82_%C2%AB%D0%92%D0%B5%D0%BD%D0%BE%D0%BD%D0%B0%C2%BB ).
И я тут процитирую из той же Википедии прекрасную формулировку:
«При этом складывалась парадоксальная ситуация: величайший секрет разведки США — чтение советских депеш, из которых узнали, что советская разведка знала величайший секрет британской разведки, состоявший в том, что они читали немецкие депеши.»

Но, конечно, шифром Вернама всё не исчерпывается — шифры, где один и тот же ключ используется для шифровки и для дешифровки, называются симметричными (см. https://en.wikipedia.org/wiki/Symmetric-key_algorithm ) — и их много. Главный вопрос — как получить общий секретный ключ.

И позволяющий сделать это алгоритм — протокол Диффи-Хеллмана: https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D1%82%D0%BE%D0%BA%D0%BE%D0%BB_%D0%94%D0%B8%D1%84%D1%84%D0%B8_%E2%80%94_%D0%A5%D0%B5%D0%BB%D0%BB%D0%BC%D0%B0%D0%BD%D0%B0 ; в англовики на эту тему есть прекрасная картинка из той же Википедии: