dxdt.blog: занимательный интернет-журнал

Как понять, что факторизация числа 15 не может ничего говорить о реализации квантового алгоритма Шора? Понять это несложно: один из делителей числа 15 должен быть меньше 4 (потому что 4^2 == 16), единица не рассматривается по условиям задачи, и это не 2 (потому что только нечётные подходят). Так что любой процесс поиска, каким бы аналоговым он ни был, если вообще сходится, то неизбежно попадёт в 3, что и будет верным ответом.

Заметьте, что ещё и 5 = 3 + 2, а простых чисел, меньших 15, только шесть: поэтому, учитывая, что умножение здесь коммутативно (это очень важно для квантовых алгоритмов), число 2 отбрасывается, а схема поиска расщепляется на пары, то, в самом худшем случае, вероятность, что аналоговый аппарат, состояния которого переключаются по возможным узлам дерева, промахнётся – меньше трети. (На практике, ещё раз, для промахов там просто нет места.)

Представьте нехитрую схему с простым 8-битным микроконтроллером, семисегментным индикатором, сегменты которого подключены в произвольном, неизвестном заранее, порядке к выходам микроконтроллера, и с парой кнопок.

Программа, прошитая в микроконтроллер, реализует следующую логику: на индикаторе включаются сегменты случайным образом, после чего пользователь должен определить, похожа ли конфигурация на заданную арабскую цифру (и ноль), а если похожа, то нажать одну кнопку (“Да”); соответственно, если непохожа, то на вторую кнопку нажать. Нажатие на вторую кнопку приводит к тому, что микроконтроллер генерирует новую комбинацию сегментов. Цикл с участием пользователя повторяется. Подтверждение же конфигурации – приводит к тому, что микроконтроллер запоминает её как обозначение выбранной цифры, после чего переходит к следующей цифре. Далее, опять же, цикл повторяется. Начинается всё, предположим, с нуля.

Комбинаций сегментов для семисегментного индикатора – не так много, даже по меркам микроконтроллера: 127. Опробованные состояния индикатора сохраняются в памяти, а “ошибочные” – второй раз не выводятся. “Успешные” состояния – записываются в отдельный массив, с индексом, соответствующим числовым значениям нужных цифр ({0,1,…,9}). Если достаточно долго нажимать кнопки, то в результате получится “знакосинтезирующий” массив. “Ещё пять тысяч вёдер и – золотой ключик у нас в кармане!”.

Почему-то сейчас забывают, что эта технология из прошлого века – есть типичное машинное обучение, результатом которого является массив индикации для цифр. Соответственно, цитата из пресс-релиза может выглядеть так: “система использует методы машинного обучения для синтеза цифровой индикации”.

Минутка специфического интернет-технологического юмора:

A (печатая в консоли, случайно склеивает два IP-адреса, вот так: 192.168.11.12192.168.12.11.).
B (наблюдая за процессом, пишет в чат): Это был адрес в формате IPv010.
A: Почему десять?
B: Потому что два IPv4 склеились – то есть, четыре плюс четыре.
A: Тогда должно быть IP-8.
B: Вот я и пишу: IPv010.

Иногда спрашивают: почему (некоторые) УЦ TLS не поддерживают подтверждение права управления доменом с использованием WHOIS-запросов? Вот появился очередной практический пример, иллюстрирующий, почему тут не нужно использовать WHOIS ни в каком виде: исследователи зарегистрировали домен, ранее служивший хостнеймом для whois-сервиса зоны .MOBI, и, как утверждается, получили потенциальную возможность подтверждать право управления доменом по запросам от УЦ, подставляя произвольный адрес e-mail в ответ (“потенциальную” – потому что сертификат исследователи заказывать не стали).

Подтверждение (валидация) права управления доменом (DCV – Domain Control Validation) – основа процесса выпуска TLS-сертификатов публичным УЦ. Понятно, что и ответы из WHOIS должны дополнительно валидироваться, и актуальность хостнейма сервера – контролироваться. Однако, каждый новый поддерживаемый метод DCV создаёт риски, а особенно велики эти риски, когда метод подразумевает использование дополнительных протоколов. Вообще, для автоматического выполнения DCV сейчас есть только один полностью подходящий способ: публикация TXT-записи с заданным значением в DNS. Но и тут имеется куча оговорок, конечно. При этом, уже и близкий метод – HTTP-запрос, – существенно хуже, пусть и использует DNS для передачи A-записей.

Продемонстрировано извлечение данных, раскрывающих секретный ключ ECDSA, из аппаратных токенов YubiKey при помощи ПЭМИН (то есть, побочных электромагнитных излучений и наводок). Используется утечка информации о внутреннем состоянии микроконтроллера при выполнении математических операций (алгоритм Евклида при вычислении обратного элемента, которое необходимо в ECDSA). По ссылке выше – очень большое описание, потому что атака сложная, требуется достаточно хитрая аппаратура и нужен не просто физический доступ, но необходимо разобрать токен. (via)

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

С другой стороны – работающая аппаратура так или иначе уязвима к утечкам по побочным каналам: если состояние изменяется, то это изменение можно отследить и использовать. Большой вопрос: можно ли вообще на практике вычислять что-то содержательное (типа подписи с постквантовой стойкостью, скажем) так, чтобы внешний наблюдатель, в электромагнитных деталях фиксирующий “переключения триггеров”, не мог вычислить секрет. Скорее всего – нет, нельзя, а данные через побочные каналы утекают даже при передаче уже обработанной информации, и даже при использовании абсолютно стойких (математически) шифров.

Кстати, не совсем по теме алгоритма Евклида в микроконтроллерах, но тоже интересно: квантовая криптография, которую, почему-то, повсеместно называют “абсолютно защищённой законами физики” (или что-то такое) – тут тоже не помогает никак: утечки состояния оборудования, создающего “квантовый канал”, вполне себе раскрывают “нераскрываемые” секреты. Понятно, что квантовая криптография – это про передачу данных. Однако декларируемая защита “физическими законами” – это лишь результат экспериментального применения некоторой модели, которая явно неполна, а дополнения и уточнения к ней – вполне себе могут принести каналы утечки уже на квантовом уровне.

Посмотрел, на какой домен можно было бы перенести dxdt.ru (поскольку RU-CENTER усиленно шлёт письма про привязку ЕСИА). Я ранее зарегистрировал несколько подходящих имён в других зонах верхнего уровня (например, .blog), однако и на этом направлении просматриваются проблемы, пусть и другого рода: вполне вероятно, что в скором времени интернет-санкции расширят очередной раз, а в результате – регистратуры (не регистраторы даже) заблокируют домены администраторов с неподходящим “подсанкционным” адресом (как уже было и с хостингами, и со многими иностранными регистраторами). Я недавно писал, что оператор реестра, – регистратура, – не только может отключить доступ регистраторов (уже происходит), но и заблокировать/удалить имена по своему выбору.

Недавняя записка про оптимизацию циклов и микроконтроллеры иллюстрирует весьма важный момент, связанный с пониманием алгоритмов, записи алгоритмов и реализаций этих алгоритмов. Не менее рельефный пример в этом же направлении касается базовых логических операций и понимания записи формул. Речь про вопрос из области логики, логических выражений: является ли P и ¬¬P – одним и тем же? Даже разработчики-программисты нередко говорят, что “да, является”.

Знак “¬” – это логическое отрицание, проще говоря – “не”, или “!”, как будет во многих привычных языках. То есть, казалось бы, тут, во второй части, написано, что “не-не-P”, а тогда, если P имеет значение TRUE, то “не-не-P” тоже TRUE; то же верно и для P == FALSE. Понятное двойное отрицание, поэтому, что P, что ¬¬P – разницы нет: одно и то же. Это, впрочем, не совсем так.

Использование дополнительной “закорючки” (“¬”) позволило реализовать два способа записи, которые точно отличаются. Как способ записи, как “формула”, “P” и “¬¬P” – сильно разные вещи. Посудите сами: во втором случае на два “знака-закорючки” больше; кроме того – для выполнения “сокращения” нужно ввести дополнительное правило, по которому двойное отрицание вообще схлопывается, а чтобы это правило сработало, потребуется его внести “в набор допустимых операций” и применить, то есть, продумать и оптимизировать, даже если не сравнивать именно две записи. Так что “¬¬P” приносит с собой много разного, отсутствующего в “P”.

Понятно, что тут очень многие соглашения вынесены за скобки, но, тем не менее, это хороший пример базовых свойств процесса оптимизации. Да, компилятор мог бы заменить ¬¬P на P. Почти что то же самое компилятор и проделывает, когда заменяет запись цикла, тело которого не вносит изменений в результаты работы фрагмента кода, на простое присваивание:

b = 14; 
for(a = 0; a < 8; a++){ 
 b = b + a;
} 

заменяется на эквивалентное

b = 42;

(или это не эквивалентная замена?)

Вообще, запись алгоритма, содержащая определение цикла, описывает повтор неких операторов/команд, но не определяет, как этот повтор должен реализовываться на оборудовании. В принципе, тело цикла можно прямо выписать в качестве повторений команд, это известный приём оптимизации, он так и называется - "развернуть циклы". Очень часто, будучи применённым к программе на языке высокого уровня (ЯВУ), приём даёт заметный прирост производительности. Почему? Потому что исчезли накладные вычислительные расходы. При обычной обработке представления цикла на ЯВУ - появляются необходимые машинные команды, соответствующие "записи" цикла, а процессор вынужден их исполнять. Команд может оказаться неожиданно много: например, потребуется сложная обвязка для реализации обработки переменной цикла.

Занятно, что автоматическая "обратная оптимизация", по размеру кода, когда повторяющиеся логические блоки сворачиваются в циклы, - представляет трудность. Тут, впрочем, уже недалеко и до алгоритмической неразрешимости.

В июне этого года я удивлялся, что на сайте ИИ-корпорации SSI даже тег div в коде страницы закрыть не могут, что уже там говорить про добавление DOCTYPE. Уже сегодня эта корпорация получила миллиард финансирования (насколько я понимаю, по меркам данного рынка – не очень много), об этом они написали пару строк на сайте и – чудесным образом – тег div в коде теперь закрыт! (Впрочем, возможно, что и раньше закрыли, не дожидаясь минимального финансирования.) А вот DOCTYPE всё ещё не реализовали.

Занятно, кстати, что моё описание TLS (как я считаю, неплохое, и уж точно очень подробное) отсутствует совсем на первых страницах выдачи Google, даже по специальным, техническим/тематическим запросам. Возможно, в выдаче Google ссылок на него вообще нет. Наверное, бот Google “не осилил много букв”. А вот в “Яндексе” (ya.ru) – ссылки на описание всё ещё присутствуют, и даже нередко на первой странице, что правильно, а поэтому “Яндекс” тут выигрывает (но посмотрим, что будет дальше).

Решил посмотреть, что пишут в поисковых машинах про TLS. Не обошлось без ИИ. По профильному запросу “Аутентификация в TLS” поиск Ya.ru (это “Яндекс”) отдельным блоком в самом верху страницы показывает текст со странным утверждением, что MITM-атака, это “когда третья сторона вмешивается в соединение двух участников и перехватывает закрытые ключи”. Тут же указано, что это текст от YandexGPT. Да, MITM подразумевает вмешательство третьей стороны, но суть атаки состоит в том, что эта третья сторона выдаёт себя за другого участника обмена, а не “в перехвате закрытых ключей”. MITM, хоть и может использоваться для “перехвата ключей”, но, вообще-то, не про перехват, а про подмену.

Впрочем, цитата сопровождается ссылкой на более объёмное “Введение в TLS”, которое, насколько можно понять, тоже сгенерировано YandexGPT, однако подписано Yandex.Cloud и опубликовано на другом сайте из “обломков” “Яндекса”, а именно, – ни много ни мало, – на сайте самого этого сервиса Yandex.Cloud, который, вроде бы, имеет прямое отношение к информационным технологиям (впрочем, сейчас уже сложно определить). Кроме прочих занимательностей, на этой странице с описанием TLS, например, в блоке с подзаголовком “Целостность данных в TLS” сказано, буквально, следующее:

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

Насколько это далеко от реальности? Так, TLS никак не гарантирует “защиту передаваемых данных от потери”: такая защита – задача из области, как минимум, транспортных протоколов, а как максимум – из области помехоустойчивого кодирования. В TLS и близко нет никакой защиты от потери данных. Напротив, протокол полностью полагается на то, что данные между сторонами уже передаются без потерь. Что касается защиты данных от изменения – да, целостность TLS пытается обеспечить, верно. А вот защита “от дублирования” – это, видимо, из области систем хранения данных (дело в том, что от “дублирования передаваемых данных” TLS тоже никак не защищает, передавайте сколько хотите копий исходных данных, однако не стоит тут путать слова из описаний атак, основанных на повторной передаче сообщений).

Конечно, “сравнение отправленной и полученной хеш-суммы данных” вовсе и не позволяет убедиться в том, что “информация пришла в исходном виде”, как почему-то утверждается: к изменённым данным нетрудно приделать соответствующее значение хеш-функции, поскольку хеш-функции для заданного значения вычисляются быстро, а вот коды аутентификации – они хоть и используют хеш-функции и подобные конструкции, но работают совсем не поэтому и не так: обнаружение изменения данных обеспечивается секретностью общего ключа аутентификации сессии, а не самой хеш-функцией.

К сожалению, некорректные и весьма странные утверждения встречаются по всему упомянутому тексту. Видимо, это всё результат, выданный синонимайзером YandexGPT. Например, в блоке “Преимущества использования TLS” утверждается, что “протокол TLS поддерживает NAT” и что “в TLS встроены функции журналирования и аудита”. Если что, то ни первое, ни второе – не верно: в TLS, естественно, нет “поддержки NAT”, но протокол, понятно, может работать через соединение, использующее трансляцию адресов (NAT); TLS не предусматривает никакого “журналирования и аудита” на уровне протокола, да ещё и в качестве “преимущества”, всё строго наоборот – TLS современной версии (1.3) старается снизить возможности по сбору метаинформации, которая могла бы обеспечить “журналирование” и “аудит”.

Представьте, что текст, позиционируемый как описание принципов построения современных языков программирования, содержит следующий фрагмент: “В языках программирования очень распространён оператор присваивания. Из-за своих преимуществ этот оператор обозначается двойной вертикальной чертой и помещает в переменную справа, которая называется “регистром”, значение суммы переменных слева. Оператор присваивания повсеместно записывается вот так: a,b || c”. Подходит ли такой текст в качестве ответа на вопрос об операторах в современных языках программирования? Вряд ли. При этом, поисковые системы всё ещё не полностью растеряли “авторитетность” в глазах пользователей Веба, так что пользователи теперь вынуждены пытаться осмыслить “ответ”, сгенерированный LLM, тем более, что ответ, – вроде как, – записан строгим текстом. Такой вот прогресс.

Отмечу отдельно некоторые записки, которые вышли на dxdt.ru в августе (2024):

ИИ и математические задачи, “автоматизированные” дважды – решает ли ИИ LLM от Google задачи Международной метематической олимпиады “на уровне серебряной медали”?
Подпись и использование ключей из TLS-сертификатов для веба – ключи “от TLS-сертификатов” можно использовать не только в TLS.
Распознавание TLS-клиентов в трафике – в открытой части TLS немало признаков, позволяющих различать конкретные типы TLS-клиентов.
Реплика: быстрая факторизация квантовым компьютером и штампы в СМИ – немного про “квантовый хайп”, с конкретным примером.
Централизованные мессенджеры и многообразие мест хранения сообщений – где ещё записываются сообщения пользователей централизованных сервисов-мессенджеров, кроме как на устройствах-клиентах.