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

CAA-запись в DNS позволяет управлять тем, какие УЦ могут выпускать сертификаты для имён в соответствующей доменной зоне. Проще говоря, в DNS публикуется имя УЦ, которому разрешено выпускать сертификаты. Чьё имя не указано – тем выпускать нельзя. (Есть тонкости с Wildcard-именами и уведомлениями о попытках заказа сертификата.) Интересно, что отсутствие CAA-записи в зоне разрешает выпуск всем. А если в CAA для имён УЦ указать пустой список (“;”), то выпускать нельзя никому.

То есть, тут мы неожиданно, на практике, сталкиваемся с весьма важной особенностью из области теоретической математики вообще и математической логики в частности. Речь про логики и формальные системы разного уровня. Пустой ящик – имеет совсем другой смысл, чем отсутствие ящика. Отсутствие ящика – это отсутствие CAA-записи, которое отсутствие вовсе и не эквивалентно пустому значению CAA-записи. Ящик есть, но он пуст – это наличие CAA-записи, значение которой – пустое множество. В первом случае, пустое множество – это “количество” CAA-записей в зоне. Во втором случае – количество УЦ, имена которых указаны в CAA-записи. Пустое множество при этом одно и то же, но оно укладывается в разные, рекурсивные ящики. Так можно построить натуральные числа.

Конечно, в спецификации этот подход использован не с целью построения натуральных чисел, а всего лишь с целью сделать использование CAA мягким. Иначе без доступа к DNS вообще не получилось бы сертификаты заказывать у УЦ, которые следуют CAA-записям.

В продолжение недавней записки про числа в ML-KEM. Один из ключевых параметров ML-KEM, одинаковый для всех наборов, это число (модуль) 3329. Почему выбрано именно 3329? Был ли выбор “случайным” (а иногда используют проверяемые методы для выбора параметров) или это число подобрано специально?

Число 3329, обозначаемое q, в ML-KEM выбрано строго специально. И вот из каких соображений. Весь практический вычислительный смысл ML-KEM (Kyber) в преобразовании (NTT), позволяющем быстро производить арифметические операции с полиномами. Чтобы быстрые операции NTT стали возможны в ML-KEM, число q должно быть простым, а (q-1) должно делиться на 256. (Более “общо” – делиться должно на степень двойки.) 256 – это другой параметр ML-KEM, его значение продиктовано разрядностью операций (256 бит).

То есть, 3329 – простое, (3329 – 1)/256 == 13. Если эти требования не выполняются, быстрый NTT работать должным образом не будет, поскольку это не настолько универсальный алгоритм, умножать полиномы “в лоб” – очень медленно, и другие быстрые алгоритмы – тоже оказываются медленными по сравнению с NTT. Неподалёку от 3329 не так много чисел, обладающих описанными свойствами: 257, 769, 3329, 7681, 7937. При этом, нужно выбрать число поменьше (важна экономия каждого бита), но чтобы не слишком выросла вероятность получения неверного результата при работе криптосистемы. Для 257 и 769 вероятность ошибки заметно больше. Поэтому авторы алгоритма выбрали 3329.

Оценка корректности употребления слов английского языка less и fewer нередко вызывает споры даже среди грамотных носителей языка. Эти слова различаются тем, что одно, в сравнении, модифицирует объекты как “неисчисляемые” (“неперечислимые”, если хотите), а второе – как “исчисляемые” (“перечислимые”). Если задуматься о том, что происходит, то можно обнаружить особенность, достаточно тонкую, которая модифицирует воспринимаемый смысл, переставляя фокус его построения между словами, следующими за less/fewer. Эффект напоминает “морфологический переворот”, который я как-то упоминал. Уловить изменение непросто, нужны хорошие иллюстрации. Такая иллюстрация попалась мне в стилистическом руководстве издания The Guardian, где эффект less/fewer рельефно проиллюстрирован четырьмя предложениями – все эти предложения говорят о разном, попутно закрывая все четыре возможных относительных варианта:

For less bad things to happen, fewer bad people need to be involved.
For fewer bad things to happen, less bad people need to be involved.
For fewer bad things to happen, fewer bad people need to be involved.
For less bad things to happen, less bad people need to be involved.

Перевод, понятно, эффект уничтожает. Но можно дать объяснение, используя несколько испорченные обороты на русском. Посмотрим на первое предложение: “Чтобы случались менее плохие вещи, меньше плохих людей должно быть вовлечено”. Less – “уменьшает” (сравнительно) то, что “нельзя посчитать”, отсюда привязка к bad. Bad, – здесь, – нельзя сравнивать “в натуральных числах”, то есть, нельзя сказать, что что-то хуже на “две единицы измерения ухудшения”. Поэтому “менее плохие” (дословный перевод здесь использован как иллюстрация). Fewer – обозначает тоже “меньше в количестве”, но именно в том количестве, которое можно считать. Поэтому “меньше плохих людей”, а не “менее плохие” “люди”. Всем известны примеры “неисчисляемых” существительных – “вода”, “песок” и т.д., – а равно и примеры “исчисляемых”: “кирпичи”, “мячи” и т.д.

Второе предложение: “Чтобы меньше плохих вещей случалось, менее плохие люди должны быть вовлечены”. Тут сравнительная характеристика “less bad” применяется уже к “людям”. Думаю, два оставшихся предложения несложно самостоятельно “раскодировать” аналогичным способом, наблюдая, как переключается фокус интерпретации.

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

Схожие знаки встречаются и в средневековых манускриптах (и не только там). Пусть метод очевидный, но всё равно занятный. Вот, например, встретился такой фрагмент манускрипта Urb.gr.15 (“Слова” Григория Богослова, десятый век, Ватиканская Апостольская библиотека):

И здесь знаками, напоминающими “>”, отмечена цитата из книги пророка Михея (Мих.2:10), использованная в тексте Григория Богослова (Слово 9), который ссылается на соответствующий стих так (самое начало текста на скриншоте): […]”Μιχαίας λέγειν, χαμόθεν ἡμᾶς ἀνέλκων ἐπι τὰ ἡμέτερα ὕψη” (“[…]Михей говорит, от земли нас поднимая на нашу (собственную) высоту”).

А более близкий к “>” по начертанию знак называется “дипле” (διπλῆ), и в дополнение к нему нередко, – но не всегда, – шли точки, расположенные сверху и снизу. Знак, конечно, не обязательно обозначал библейскую цитату, как и цитату вообще. Пример из Venetus A:

Этот фрагмент “про птицеведов”, кстати, недавно встречался в заметке про квантовые вычисления у Гомера.

Пример из серии про неявные преобразования и компьютерную алгебру. Табличный процессор Google Spreadsheets в браузере, скриншот:

То есть, написана формула “-3^2”, но в ячейке получаем значение 9, что не обязательно-то верно, как ни странно. Почему? Вообще говоря, в этой формуле неявно подразумевается следующее выражение: -1*3^2. Так как операция возведения в степень имеет более высокий приоритет, чем умножение, должно получиться -9. Если в том же приложении Google так и написать, с минусом и единицей, то получим верный ответ: -9. С другой стороны, может оказаться, что подразумевается использование операции взятия обратного по сложению, обозначаемой знаком “минус”, и она имеет приоритет выше возведения в степень. Ну или это просто “минус три” написано, то есть, (-3)^2. Поэтому, скажем, Gnumeric – тоже выводит 9, но при этом автоматом дописывает в формулу скобки вокруг -3.

(Пример попался в Telegram-канале Бориса Трушина.)

Даниэль Бернштейн (Daniel J. Bernstein) опубликовал большую статью (англ.) с критикой некоторых возражений, относящихся к возможности создания универсальных квантовых компьютеров. Вообще, основной посыл статьи такой: нужно немедленно повсеместно внедрять постквантовую криптографию, потому что, исходя из анализа ситуации, не удаётся найти веских причин для уверенности в том, что АНБ уже не строит активно (или построило) квантовый компьютер, пригодный для практического криптоанализа.

В статье есть странный частный момент: в качестве примера, поясняющего, почему проблема огромного количества состояний, с которым должен работать квантовый компьютер, – это совсем не проблема, приводится работа обычного, классического компьютера с тысячей битов. То есть, обычный компьютер без труда может сгенерировать тысячу случайных битов, а потом провести с ними преобразование, которое изменит распределение вероятностей. Поэтому и тысяча кубитов, якобы, не создаёт теоретических проблем теоретическим квантовым компьютерам.

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

I’m not saying that computation on qubits is the same as computation on random bits. When you look at the details, you see that quantum computation allows a useful extra trick, setting up interference patterns between positive and negative variables. But an argument saying “quantum computing is impossible because there are so many variables” can’t be right: it also says that your laptop is impossible.
(“Я не утверждаю, что вычисление на кубитах это то же самое, что и вычисление на случайных битах. Если посмотреть детально, то можно увидеть, что квантовое вычисление позволяет провести дополнительный полезный трюк, задав схемы интерференции между положительными и отрицательными переменными. Однако аргумент, говорящий, что “квантовые вычисления невозможны, так как там настолько много переменных”, не может быть верным, поскольку этот же аргумент говорит, что ваш ноутбук невозможен.”)

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

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

Воскресное чтение манускриптов. Ватиканский кодекс (Vat.gr.1209) – один из важнейших источников библейских текстов на древнегреческом. Основную часть манускрипта датируют четвёртым веком (н.э.), но в нём есть добавления, сделанные в 15 веке – новые листы с переписанным текстом подшиты взамен утраченных. На полях и между колонками текста данного манускрипта встречаются необычные “умляуты” или “двойные точки” (distigmai) – см. скриншот ниже.

Считается, что такими точками обозначены места в тексте, которые отличаются в других источниках. Так, на фрагменте листа со скриншота точками обозначено начало 17 стиха второй главы Евангелия от Марка. То есть, это редакторские знаки. И вот, эти точки на данном манускрипте академические палеографы обнаружили и признали значимыми только в начале 90-х годов двадцатого века. Тридцать лет назад. Что несколько неожиданно. Ну, понятно, конечно, что если знаки эти всё же полагать редакторскими, то они просто должны были быть известны в такой роли и сильно раньше, но тогда в какой-то момент инструкция была утрачена, а “данные – удалены”.

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

Естественно, момент датировки отметок о разночтениях в Ватиканском кодексе – это весьма важный, в исторической перспективе, момент. Недавно его прояснили при помощи сравнительного рентгенофлуоресцентного анализа чернил, которые встречаются на листах данного манускрипта. В свежей работе (“Did the Original Scribes Write the Distigmai in Codex Vaticanus B of the Bible?”, Gordon et al., The Vatican Library Review 3, 2, 125-156) чернила, которыми сделаны упомянутые отметки в виде двух точек, датируют началом 16 века. То есть, даже позже момента написания листов на замену утраченным. Датировка основана на наблюдении над примесями металлов в составе чернил.

(Source: “Did the Original Scribes Write the Distigmai in Codex Vaticanus B of the Bible?”, Gordon et al., The Vatican Library Review 3, 2, 125-156.)

Основа чернил содержит примеси, которые можно обнаружить при помощи спектрометрии. Конкретно – в качестве маркера используется медь. Основной текст манускрипта записан чернилами, которые содержат существенную долю медной примеси. Но есть и другие чернила, в которых медный след практически не заметен. Считается, что такие чернила без меди появились в Европе не раньше 16 века.

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

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

Кстати, занятный момент, который исследователи выявили в результате “фингерпринтинга” чернил по спектру, связан с процессом обновления текста манускрипта. Как уже упоминалось выше, буквы основного текста манускрипта обводились позже (возможно, не раз). И вот, на некоторых страницах, чернила, которыми записан оригинальный (исходный) текст, отличались по полученному спектру от чернил, использованных для обновления на этой же странице, но совпадали с чернилами, использованными для обновления на другой странице.

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

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

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

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

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

Возможен и вариант, когда дополнения или изменения прежде появятся в математическом аппарате квантовой механики, а потом предложат алгоритмы атак на постквантовые криптосистемы, использующие эти нововведения. Этот вариант менее вероятен, чем предыдущий, но сбрасывать его со счетов вовсе и не нужно.

Ну а интереснее всего вариант, когда изменения в аппарат квантовой механики вносятся специально для того, чтобы предложить алгоритмы взлома постквантовых криптосистем, а уже в качестве “побочного эффекта”, несколько позже, этот новый вариант оказывается полезен и для теоретической физики. Такое тоже возможно.

Постоянно тиражируются странные утверждения про “суперпозицию” и “мощность квантовых компьютеров”. Вот свежий пример: в небольшой справке по квантовым “оборонным технологиям” для штатовских конгрессменов написано, что термином “суперпозиция” обозначается “способность квантовых систем существовать в двух или более состояниях одновременно” (оригинал: “Superposition refers to the ability of quantum systems to exist in two or more states simultaneously”). Дальше из этого ошибочного определения выводится, что если классический компьютер кодирует информацию в битах, “которые представляют двоичные состояния нуль и единицу”, а квантовый компьютер – использует кубиты, которые могут быть и нулём, и единицей, и комбинацией нуля и единицы одновременно, то мощность квантового компьютера “увеличивается экспоненциально с добавлением каждого кубита” (буквально: “Thus, the power of a quantum computer increases exponentially with the addition of each qubit”).

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

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

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

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