Книги: "Создание сайтов" - "Доменные войны". Защита информации: техническое описание TLS, тестовый сервер TLS 1.3. Ресурсы: LaTeX
Переход сети ARPANET на TCP/IP состоялся 01/01/1983 – то есть, в 2023 году Интернету исполнилось 40 лет. Почему отсчёт связан именно с этой датой? Потому что Интернет, как глобальная сеть, это именно ARPANET c TCP/IP и связанные технологии, к которым, прежде всего, отсносятся механизмы IP-маршрутизации между компьютерными сетями. Интернет составляют автономные системы. Логические инструменты, позволяющие определить автономную систему (в терминах Интернета и маршрутизации), это следущие понятия:
- межсетевая граница контроля над связностью узлов;
- пограничный маршрутизатор;
- алгоритм маршрутизации и схема межсетевой адресации узлов.
Межсетевая граница – позволяет разделить сетевые узлы внутри и сетевые узлы снаружи, с точки зрения структуры связности; ключевой аспект: локальная администрация сети контролирует и самостоятельно определяет связность локальных узлов (то есть, “какой компьютер куда и как подключен”), а на “коммутацию” внешних узлов повлиять не может и об их реальной связности ничего априори не знает.
Пограничный маршрутизатор – узел, который позволяет логически взаимодействовать с внешними сетями и, по сути, формирует основу для преобразования внутренних политик доставки пакетов во внешние; то есть, пограничный маршрутизатор как раз позволяет получить информацию (с ограничениями) о том, как связаться с внешними узлами, находящимися в других автономных системах.
Алгоритм маршрутизации и межсетевой адресации узлов – это универсальный и эффективный способ адресовать сети и узлы так, чтобы можно было строить практические маршруты доставки пакетов через межсетевые границы при помощи пограничных узлов-маршрутизаторов, абстрагируясь от свойств физических каналов и конкретных протоколов электросвязи. Это и есть IP (префиксы и адреса узлов) и необходимый, в современной сети, BGP (Border Gateway Protocol).
Второй важнейший составляющий элемент Интернета – DNS. Но здесь он оставлен за скобками.
Идея о том, что можно обмениваться обобщёнными “пакетами данных”, самоочевидная. Тем более, если уровень технического развития такой, что уже есть вычислительные машины. Первые строгие механизмы систематической доставки “пакетов данных” очень древние: почтовая связь по дорогам силами гонцов и оптические телеграфы (прообраз электросвязи). Телеграфная связь между “вычислителями” существовала ещё в те дни, когда полупроводниковых электронных вычислительных машин не было, а сложные расчёты проводили с использованием механических калькуляторов организованные коллективы “лаборантов”, работавших параллельно по общей схеме в одном помещении. Но, конечно, это ещё не являлось “Интернетом”.
Комментировать »
Сейчас популярна история с чат-ботом ChatGPT, который даёт пространные ответы на вопросы из самых разных областей. Мне доступ к данному сервису получить не удалось (там хотят слишком много реквизитов), но это не важно: понять, о чём речь, не так уж трудно по многочисленным цитатам. Всё это увлечение соответствует попыткам найти смысл непосредственно в тексте. Проблема в том, что текст, как набор символов с определённой структурой, тем не менее, самостоятельного смысла не несёт. Смысл образуется (или не образуется) после того, как результат прочтения текста вкладывается в некоторую большую структуру; и чтобы говорить об “интеллекте”, давать оценки, данная структура должна быть заметно мощнее конкретного текста. Это, впрочем, хорошо известное явление, про которое написано очень много и подробно. Несомненно, письменность очень важна не только для древних языков, но и для современных. Однако переход автоматического генератора текстов от фильтрации совсем примитивных конструкций к “наследованию” чуть более развитой “семантической” структуры, свойственной многим текстам по заданной теме, скорее свидетельствует об успешной оптимизации использования вычислительной аппаратуры с целью удивить пользователей Интернета, чем о чём-то ещё.
В советском мультфильме “Трое из Простоквашино” (1978 года) есть эпизод с Галчонком и потальоном. Почтальон Печкин стучится в дверь, но дома только специально обученная птичка – Галчонок, который на стук реагирует одной и той же фразой.
– Кто там? – спрашивает Галчонок. (Это единственная фраза, которую он знает на тот момент.)
– Это я, почтальон Печкин, принёс заметку про вашего мальчика, – отвечает Печкин. Ничего не происходит, поэтому почтальон стучит снова.
– Кто там? – спрашивает Галчонок.
– Это я, почтальон Печкин, принёс заметку про вашего мальчика, – отвечает Печкин.
Цикл “запрос-ответ-пояснение” повторяется многократно. В какой-то момент Галчонок замечает муху на оконной раме и клюёт её, производя тем самым стук.
– Кто там? – спрашивает, вместо Галчонка, заскучавший Печкин.
– Это я. Почтальон Печкин. Принёс заметку. Про вашего мальчика, – будто телетайпом отбивает ответ Галчонок.
И тут столкновение могучих интеллектов оканчивается поражением Печкина: эмоционально потрясённый, почтальон теряет сознание.
Комментарии (3) »
– Почему криптосистема называется X25519, откуда это 25519?
– Потому что там присутствует 2^255 и 19. Вот только “плюс” или “минус”? А, понятно, конечно, “минус”, поскольку 2^255+19 делится на 3, что очевидно.
Число, являющееся “модулем” в данной криптосистеме, должно быть простым. Соответственно, 2^255 – 19. Но выбор в большей степени обусловлен тем, что такое число имеет удобное двоичное представление: там много единичных битов подряд. Тем не менее, из наблюдения про 2^255 + 19 можно сделать задачу к Новому году: докажите, что 2^2023 + 2023 делится на три.
(Решение: записка и комментарии ниже.)
Комментарии (5) »
Иногда открытый ключ нужно буквально вводить руками, например, через “воздушный зазор”. Открытый ключ в ECDSA (и, кстати, в ГОСТ-подписи, но не только там) – это точка на кривой, заданной в параметрах. Речь тут про кривые, используемые в криптосистемах на практике, например, P-256. Координаты точки – это два числа X, Y (сторого говоря, два элемента соответствующего конечного поля, но это технические детали). Если разрядность 256 бит, то может показаться, что для передачи ключа придётся руками вводить 2*32 == 64 байта, что в hextext составит аж 128 знаков. Однако обычно можно ограничиться одной координатой X, а Y – вычислить из уравнения кривой. Такой способ кодирования называется сжатым представлением ключа. Единственная хитрость в том, что, так как в уравнение кривой Y входит в квадрате, координат, соответствующих данному X, пара. Это обратные по сложению элементы (всем привычные +/-). Поэтому нужно передать знак элемента, но для передачи знака достаточно одного дополнительного бита. Поэтому сжатое представление в два раза короче, но “разрядность ключа” при этом никак не страдает (страдают вычислительные затраты на принимающей ключ стороне, но этим часто можно пренебречь; иногда, впрочем, приключаются проблемы с обработкой заведомо неверных значений). Кстати, по этим же причинам ключи криптосистем с ed25519 короче в записи – они изначально “в сжатой форме”.
Комментировать »
Некоторое время назад я написал утилиту, кодирующую произвольные байтовые значения в строки англосаксонских рун. Используется кодирование, эквивалентное Base32, но с алфавитом из рун. Алфавит, понятно, может быть любым, но в случае рун для отображения в привычных компьютерных системах потребуется поддержка Unicode.
Таблицы Unicode – весьма богатое нововведение. Unicode позволяет записывать в тексте числа древними шумерскими цифрами, вот так: 𒁹 𒌍𒐋 𒌋𒌋𒐈. (Если на вашем устройстве эти цифры не отображаются, то, вероятно, устройство не содержит подходящих шрифтов; такое всё ещё возможно; более того, мне пришлось столкнуться с существенными трудностями при размещении этой записки в WordPress – стандартный редактор данной CMS отказывался принимать соответствующие символы, пришлось применять некоторые хитрости).
В принципе, шумерская (вавилонская) система записи – позиционная, по основанию 60, но имеет свои особенности, создающие неоднозначности при интерпретации: там используется плавающая “шестидесятеричная точка”, которая не обозначается; кроме того, в классическом варианте, нет цифры для нуля. 𒁹 𒌍𒐋 𒌋𒌋𒐈, в зависимости от контекста, можно интерпретировать не только очевидным способом, как 5783 (1*60^2 + 36*60 + 23), но и, например, как 96.38333(3) (1*60 + 36 + 23/60). Клинописные цифры, соответствующие числам от 1 до 59, записывались засечками; так, 𒐈 – это 3, а 𒌋𒌋 – это 2*10, то есть, 20 (𒌋 обозначает 10). Unicode, – по крайней мере, в теории, – позволяет все эти засечки напечатать и вывести на экран компьютера в виде текста, благодаря наличию разнообразных кодовых таблиц, среди которых есть и таблица с шумерскими древними цифрами.
Именно засечки, штрихи и прочие дополнительные “чёрточки” (умляуты и тому подобные знаки) Unicode создают исключительные проблемы при преобразовании символов. Рассмотрим в качестве примера кириллическую букву “И” с “краткой”, то есть, “Й” (“кратка” – это чёрточка над “И”). Правила Unicode позволяют обозначить данную букву как одним кодом (Й), так и комбинацией из двух – из сочетания кода буквы “И” (без “кратки”) и отдельного кода, обозначающего “кратку”, который предусмотрен в Unicode. То есть, одна буква расщепляется на два представления! Фольклорное фонетическое восприятие букв сталкивается с универсальным “чисто топологическим” и с треском прогрывает последнему. Результат, вообще говоря, может доставить неожиданных проблем разработчику программного кода, выполняющего преобразования кодировок. Поэтому в тех случаях, когда нужно запись Unicode приводить к другим кодировкам, которые не сохраняют разделение по принципам начертания, используются те или иные соглашения о нормализации, предназначение которых состоит в том, чтобы согласованным способом привести наборы кодов к единому символу. Это один из самых нетривиальных моментов в практике Unicode.
Комментировать »
Визирь поместил в тёмную комнату слона и позвал нескольких мудрецов, которые слона никогда не видели. Предупредив мудрецов о том, что в комнате слон, визирь предложил им пройти в комнату и “исследовать слона на ощупь”, а потом словами описать, какой он, этот загадочный слон. Посетившие комнату мудрецы сильно разошлись в своих описаниях слона: “он как толстое дерево”, “он как большая змея”, “он плоский, как лист пальмы”. Но слон-то был один, слон-то был един, а проблемы с предложенными его описаниями локализовались (во всех смыслах), как только визирь вывел животное из комнаты и представил взору мудрецов, но уже в статусе единого объекта.
Обычно считается, будто эта старинная и хорошо известная притча рассказывает о том, что есть различный частный опыт, а с другой стороны – большой единый слон, ощупыванием которого частный опыт создаётся. Это, однако, не так: фундаментальный смысл притчи в другом. Притча рассказывает, что настоящее осознание находится на уровне визиря, который затеял всё мероприятие, чтобы подшутить над мудрецами. Визирь-то хорошо понимает процесс, приводящий к рассечению образа единого слона на различные представления через ограниченные темнотой познавательные способности мудрецов. Уши, хобот, ноги – не так важно, на каком шаге комбинирования из них получается слон. Важно, что сам процесс онтологического спектакля, осознанный визирем, находится на таком высоком уровне абстракции, что в него не то что слон целиком вкладывается, но ещё и преобразования в локальные области точек зрения разных мудрецов, вместе с самими мудрецами и комнатой.
Комментировать »
Если выбрать систему координат таким образом, что Солнце движется в ней прямолинейно со скоростью несколько сотен км/сек., то траектория Земли окажется кривой, напоминающей синусоиду. В этой системе координат Земля вовсе не “вращается вокруг Солнца”, в том “наивном” смысле, что не описывает окружность, в центре которой Солнце.
Для навигации на поверхности Земли – удобны другие системы координат, в которых Солнце вращается вокруг Земли, поскольку она зафиксирована. Расхожее утверждение, что “Земля вращается вокруг Солнца” – не более чем фигура речи, пусть и очень популярная. Например, для того, чтобы получить существенные вычислительные преимущества при предсказании астрономических событий Солнечной системы, наблюдаемых с Земли, самой по себе гелиоцентрической системы не достаточно, нужно ещё учитывать геометрию орбит планет, иначе потребуется, как и в развитом геоцентрическом случае, вводить множество дополнительных “параметров”, чтобы наблюдения как-то сходились с моделью.
Существенные искажения смысла, которые сейчас встречаются повсеместно (см. надавнюю записку про соцопрос), возможно, вызваны таким явлением, как упрощённый, массовый “научпоп”: почему-то стало принято считать, будто уровень знаний достиг таких высот, что всё вокруг, от движения планет и устройства космических телескопов до систем связи пятого поколения и превращений элементарных частиц в ускорителях, очень просто, легко и, главное, детально, объясняется “физикой за пятый класс”. Сама “физика за пятый класс” при этом никак не определяется, поскольку важным признаётся именно подход, подразумевающий эквивалентность простых “утверждений”, которые легко запомнить (без осознания), и “научной грамотности”.
Вернёмся к движению планет. То, что Солнце существенно больше Земли, а наблюдаемое движение светила по небу можно объяснить при помощи модели, в которой именно Земля движется вокруг, выяснили ещё древние греки. Но, скажем, измерение годичного параллакса звёзд, как подтверждение движения Земли по орбите, удалось произвести только в 19 веке. Следует ли считать, что до этого момента утверждение “Земля вращается вокруг Солнца” было всего лишь популярным обобщением? Нет, конечно. Это утверждение, в изолированной форме, и сейчас не несёт особого смысла. То есть, процесс выбора моделей мира был длительным, непростым, и не сводился к тому, как сейчас нередко принято объяснять: “Коперник открыл, что Земля вращается вокруг Солнца”. Никаких особенных причин утверждать, что именно Земля движется, нет, а практическое удобство гелиоцентрических систем совсем в другом.
Но главное полезное наблюдение состоит не в этом. Так, в разных системах отсчёта, в разных системах координат, движение светил будет описываться различными формулами, которым соответствуют различные траектории. Результаты нередко выглядят неожиданными: например, траектория Луны, движушейся вокруг Солнца, очень близка к окружности. Действительно, от одной формулы можно перейти к другой. Именно на этом уровне и образуется новое знание, отличающееся от простого заучивания кратких “утверждений”. Это знание позволяет понять, почему разные системы отсчёта, представленные в наивном виде (“Земля вращается вокруг Солнца”), как бы “противоречат” друг другу. То есть, знание, – по крайней мере, математическое, – здесь соответствует механизму разрешения противоречий. Этот механизм находится на пару уровней выше утверждения “Земля вращается вокруг Солнца”. Естественно, астрономические успехи связаны с определением и строгим формулированием элементов этого механизма. На первом этапе – понимание того, что наблюдаемая картина движения светил может быть интерпретирована различными способами. На втором – создание логических конструкций, позволяющих вычленить существенные характеристики того, как различные модели переходят одна в другую, с сохранением наблюдаемого результата. И уже на третьем этапе – выяснение причин такого перехода и их строгое описание. Простое утверждение “Солнце вращается вокруг Земли” не играет сколь-нибудь значительной роли, гораздо важнее понимание того, что подразумевается под “вращением”, насколько это понятие универсально.
Комментировать »
“Коммерсант” пишет про результаты соцопроса, которые связывает, ни много ни мало, с “уровнем научной грамотности” (“невысоким”).
“Как показал опрос ВЦИОМа, 35% россиян считают, что Солнце вращается вокруг Земли. О том, что Земля вращается вокруг Солнца, знает 61% респондентов.”
Понятно, что влияет массовый “научпоп”, а опрос – манипулятивный, но всё равно довольно забавно читать выводы о “научной грамотности”, сделанные по результатам ответа на довольно бессмысленный вопрос, который был сформулирован следующим образом: “Согласны ли вы с утверждением: «Солнце вращается вокруг Земли»?”. Проблема в том, что интерпретация предложенного утверждения зависит от используемой модели и системы координат. Так, можно выбрать систему с зафиксированной Землёй в начале координат и, в таком случае, Солнце вращается вокруг Земли. Подобная система оказывается удобной при решении определённых задач. Можно выбрать систему, где началом координат является Солнце, а Земля движется вокруг – такая система хорошо подходит для других задач. А можно привязать начало координат к какому-нибудь далёкому пульсару. Но все эти хитрости не делают конкретную систему “истинной” настолько, чтобы с ней соглашаться или нет. Поэтому, если уж и судить о “научной грамотности”, то, скорее, как раз по высокой доле “неочевидных” ответов.
Комментарии (3) »
Запись чисел при помощи цифр различных систем счисления нередко приводит к недопониманию у тех, кто не очень хорошо представляет себе разницу между числами и их записью. Например, могут предположить, что 11 и 0x11 (в шестнадцатеричной записи, далее такая запись обозначается привычным префиксом) это одно и то же число, ну, как 7 и 0x7. Нетрудно наткнуться и на смешение свойств числа и его записи: то есть, на неверное представление о том, что какие-то свойства чисел соответствуют именно записи (запутывающее сочетание 0x100 == 2^8). Впрочем, всё это не мешает занимательным свойствам позиционных систем счисления интересным образом преобразовываться при переходе от одной системы к другой, сохраняя именно запись (то есть, цифры).
Так, если 1001001 умножить на 321, то получим 321321321. Почему? Очевидно: мы умножаем (10^6 + 10^3 + 10^0) на (10^2*3 + 10^1*2 + 10^0*1), то есть (10^6 + 10^3 + 10^0)*321. Известный, пусть и не очень широко, факт: всякое число, содержащие ровно три одинаковых тройки цифр в своей записи, делится на 333667. Примеры:
321321321/333667 == 963 == 3^2 * 107
111111111/333667 == 333 == 3 * 111
701701701/333667 == 2103 == 3 * 701
(Конструкция, конечно, переносится и на кратные записи, то есть, когда количество триплетов кратно трём.)
Выглядит занимательно. Причина в том, что на 333667 делится 1001001 == 3*333667. А 333667 – простое число. В записи 333667 нетрудно увидеть поразрядные “переносы единицы” при умножении на три. Можно ли найти число с такими же свойствами в шестнадцатеричной записи? Можно. Если в десятичной записи 3*3 == 9 == 10 – 1, где 10 – основание системы, то в шестнадцатеричной аналогом будет 3*5 == 15 == 0x10 – 1. Обратите внимание, что здесь 0x10 шестнадцатеричная запись числа 16, основания системы. Число другое, но нам здесь важны как раз некие свойства записи (а именно – позиция единицы). Искомое число – 0x555aab. Заметьте, что шестнадцатеричное 0xa равно 10 в десятичной системе, то есть, 5*2 (так же как и 3*2 == 6). Проверяем: 0x555aab * 0x3 == 0x1001001 (но это 16781313 в десятичной записи). Поэтому 0x321321321 делится на 0x555aab, а результат равен 0x963 (см. примеры в десятичной системе выше). Однако найденное нами “опорное” число хоть и полностью подходит по “свойствам” записи, но является составным: 0x13*0x25*0x49*0x6d == 0x555aab.
А вот в восмеричной системе ситуация иная. Число 0o1001001 (префикс 0o – обозначает восмеричную запись) – простое, а именно – 262657 == 8^6 + 8^3 + 8^0. Поэтому не получится найти делитель, который подходил бы для построения конструкции, аналогичной десятичной и шестнадцатеричной системам. Интересно, что число 46656216001 == 60^6 + 60^3 + 60^0 тоже простое. Это означает, что и в древней шестидесятеричной системе конструкция не сработает. Что ж, зато в десятичной системе 296296296296296296296296296/333667 == 888000000888000000888. Проверьте на калькуляторе.
Комментировать »
Некоторые странные заблуждения из области “научпопа” очень долговечны. Например, если заглянуть в статью про Галилея в русскоязычной “Википедии”, то нетрудно обнаружить типовые суждения в стиле “Галилей опроверг (мета)физику Аристотеля”. “Википедия”, конечно, здесь выступает лишь фольклорным зеркалом истории физики, но тем рельефнее выглядит цитата: “В частности, Аристотель утверждал: скорость падения пропорциональна весу тела; движение происходит, пока действует «побудительная причина» (сила), и в отсутствие силы прекращается”.
Да, Аристотель подобное утверждал, но с очень важной оговоркой, которая полностью меняет ситуацию. Аристотель изучал падение тел в среде и рассуждал о максимальной скорости падающего тела. Утверждения Аристотеля, процитированные выше, хорошо соответствуют эксперименту. Действительно, в воздухе свинцовый шарик и клочок ваты, сравнимого размера, будут падать с разной максимальной скоростью, потому что у них различный вес. Конечно, другое дело – вакуум. Однако Аристотель изучал падение не в вакууме. Понятно, что то же самое относится и к “побудительной силе”, если учитывать реальные условия. Поэтому хорошо бы и формулировать иначе: Аристотель утверждал, что при падении в среде, – например, в воздухе, – максимальная скорость, которой может достичь тело, пропорциональна его весу. Но при такой формулировке исчезает вся сенсационность. Получается, что Галилей не “опровергал физику”, а всего лишь обобщил ограничивающие свойства, обусловленные наличием среды, и предложил другую модель, в чём-то более универсальную. Кроме того, всё это знали другие естествоиспытатели, раньше Галилея. Надо заметить, такая интерпретация сильно богаче с точки зрения философии науки, но менее литературна. Поэтому в “Википедии” читаем: “Галилей сформулировал правильные законы падения: скорость нарастает пропорционально времени”. Занятно выглядит слово “правильные”. Как можно понять, что какие-то законы физики – правильные? А если вы сравниваете разные модели при различных “граничных условиях”? Физика, вообще говоря, не претендует на “правильность законов”.
(Продолжение с подробностями.)
Ссылка по теме: Aristotle’s Physics: a Physicist’s Look, Carlo Rovelli.
Комментарии (2) »
Обычно, протокол Диффи-Хеллмана (DH) описывают на примере вычетов, то есть, арифметики остатков. Это так называемый классический вариант реализации протокола, который тоже используется на практике. При этом, протокол успешно обобщается на другие математические структуры, лишь бы они обладали некоторыми специальными свойствами. Эти свойства весьма важны для применимости протокола на практике.
Посмотрим на классический вариант DH: s = Gab == Gba (mod P), а именно – мы выбрали некоторое большое простое число P, выбрали натуральное G < P (это значение называют генератором), а в рамках операций протокола возводим G в секретную степень a или b по модулю P. Другими словами – вычисляем остаток от деления на P. Из привычного свойства степеней выводится нужное равенство, означающее, что стороны придут к одинаковому значению секрета s. Уже при разборе классического варианта можно обнаружить первое важнейшее общее свойство, о котором нередко забывают.
Действительно, стороны обмениваются значениями Ga и Gb по открытому каналу, соответственно, атакующему нужно вычислить a или b, по известному значению Ga или Gb. Почему же атакующий не может просто последовательно возводить G в натуральные степени, чтобы на каком-то шаге получить Ga (или Gb, но для примера возьмём только a), определив, таким образом, секретное значение? Ответ на этот вопрос такой: будем выбирать значение a достаточно большим, чтобы полный прямой перебор оказался вычислительно недоступным. Например, последовательно перебрать уже 2128 значений, для нашей задачи, весьма и весьма затруднительно. (Техническая оговорка: классический протокол DH на практике использует значения гораздо большей разрядности – 4096 бит и больше; это связано с особенностями криптоанализа именно классического DH, и не должно нас смущать: 4096 бит, после применения некоторых оптимизаций, как раз превращаются, примерно, в 196 “честных” битов.) Итак, атакующий не может перебрать все показатели степени последовательно, потому что это очень долго. Но как же тогда быть сторонам, использующим DH, они же тоже возводят G в степень большой разрядности? Это и есть первое арифметическое свойство, необходимое для успешного обобщения DH.
Так как каждая сторона протокола знает своё секретное значение, она может воспользоваться тем, что, например, 16 == (22)2. То есть, вместо трёх умножений – ограничиться всего двумя: (2*2)*(2*2). Очевидно, что один раз вычислив 4 == 2*2, можно использовать 4 дальше. Зная нужное значение показателя, процесс вычисления нетрудно разбить на повторное “удвоение” (здесь – в смысле степени, но это весьма важный и более общий термин) и умножение на основание: 35 == 32*32*3 == 243. Существенная экономия вычислительных ресурсов, которая выводится из того, что умножение в целых числах не зависит от расстановки скобок: a×a×a×a×a == (a×a)×(a×a×a) == a×(a×a×a×a). Вместо того, чтобы 128 раз умножать 3 на 3, вычисляя 3129, можно поступить проще: 3129 == 3128*3 == (364)2*3 и т.д., рекурсивно. Всё это может показаться очевидным для целых чисел, особенно, если учесть тот факт, что описанный метод естественным образом отображается на двоичное представление, привычное для компьютерных вычислений. Однако при обобщении протокола DH данное свойство трансформируется: необходимо, чтобы арифметические операции в новой структуре позволяли выполнять “быстрое удвоение”. “Быстрое” – в смысле количества вычислительных операций.
Наличие “операций” подразумевает, что структура, на которую мы пытаемся перенести протокол DH, предполагает некоторую арифметику. Обычно, говорят о коммутативной группе: множестве с бинарной операцией, которая введена таким образом, что является ассоциативной, коммутативной, ей соответствует нейтральный элемент и взятие обратного элемента. Если новая структура – коммутативная (абелева) конечная группа, то протокол DH может на ней заработать без изменений. Именно поэтому DH работает на эллиптических кривых: точки кривой образуют абелеву группу, арифметика которой, очевидно, позволяет быстро вычислять удвоения (см. пример ECDH с числами). В некоммутативном случае – всё сложнее, прежде всего потому, что структурное разнообразие некоммутативных групп гораздо больше абелевых. Мы некоммутативный случай здесь не рассматриваем.
Итак, следующая особенность DH – это протокол достаточно высокого уровня, чтобы его можно было переносить на другие структуры, с подходящей арифметикой. Обычно – на группы. Естественным препятствием здесь является наличие сложности решения обратной задачи. Если у нас есть функция DH с параметром, отображающая элемент новой структуры в другой элемент, задаваемый параметром, то эту функцию должно быть сложно обратить. В случае классического варианта протокола, скажем, что параметр – это показатель степени, а функция может быть представлена как S = Gx. Тогда обратная задача – это задача дискретного логарифмирования: нужно отыскать x, по известным G и S. Для эллиптической кривой обратная задача, обеспечивающая возможность переноса обобщённого DH, это задача вычисления показателя кратности (скаляра) x по двум известным точкам: S = xG. Например, в случае суперсингулярных (не будем вдаваться в технические подробности) эллиптических кривых протокол ECDH может оказаться уязвимым, поскольку существуют практические методы быстрого решения задачи дискретного логарифмирования для некоторых из этих кривых (методы эти позволяют свести задачу к вычетам, то есть, к области классического DH, но это детали). Как ни странно, это совсем не означает, что суперсингулярные эллиптические кривые не годятся для реализации DH.
Примером использования DH в совсем другом математическом окружении является постквантовый протокол CSIDH. С одной стороны, этот протокол работает на весьма экзотических объектах из области теоретической математики, а именно, на кольцах эндоморфизмов (и изогениях) эллиптических кривых (опять же, не обязательно понимать, что это такое), с другой стороны, применяемый алгоритм на уровне логики полностью аналогичен классическому DH, хоть и использует весьма нетривиальные превращения в качестве основной операции.
Комментировать »