ch
Feedback

不要被骗子欺骗!Telemetrio 会找到并标记这些频道 👉 如果想查看标记,请订阅

Математические байки

Математические байки

前往频道在 Telegram

Рассказы про разную математику. Архив: http://dev.mccme.ru/~merzon/mirror/mathtabletalks/

显示更多
4 361
订阅者
+124 小时
+67 天
+3830 天
帖子存档
Буквально с этой задачей мы закончили — но та же идея коммутирующих шифров используется ещё одним способом, и именно тут применяют эллиптические кривые. А именно — много что можно сделать, если у двух сторон есть общий секретный ключ. Только вот как сделать так, чтобы он оказался у обоих сторон сразу?
25 2月 2020, 06:39

И видно, что формально-математически знание (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
25 2月 2020, 06:39

Ну и, чтобы передать сообщение 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. Ура!
25 2月 2020, 06:38

Зато можно такую схему реализовать с возведением в степень вместо сложения (и получается не алгоритм 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 обратны друг другу, и мы возьмём их как Б-шифрование и Б-расшифровку.
25 2月 2020, 06:37

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

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

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

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

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

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

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

Ну и на этой истории я хочу на сегодня прекратить дозволенные речи.
20 2月 2020, 07:02

(Про треугольные знали раньше, пятиугольные и выше — вопрос всё ещё открыт...)
20 2月 2020, 07:00

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

photo content
20 2月 2020, 06:56

...и вопрос открыт до сих пор. :)
20 2月 2020, 06:55

Он пришёл. Задача оказалась чуть более сложной — но ещё через неделю точно приходите, всё будет. Потом эта неделя стала месяцем...
20 2月 2020, 06:55

Так что он, недолго думая, пришёл на семинар Синая и спросил. И ему сказали, что ну конечно же, это правда, приходите через неделю на следующее заседание, всё докажем.
20 2月 2020, 06:54

У него эта гипотеза возникла в связи с собственными значениями оператора Лапласа — в предположении, что таких открытых областей траекторий нет, он получил следующий член их асимптотики.
20 2月 2020, 06:54

Гипотеза (В. Иврий, 1980). Нет, таких бильярдов нет.
20 2月 2020, 06:48