Где именно в криптосистеме электронной подписи ECDSA “работает” эллиптическая кривая?

Посмотрим, для начала, на значение подписи, которое состоит из двух параметров – (R, S). Здесь R – это координата X точки на используемой эллиптической кривой, а именно, X-координата точки k∘G, где G – точка кривой, называемая генератором (зафиксированный параметр криптосистемы), а k – секретное уникальное значение (ECDSA nonce). Запись k∘G, – “умножение на скаляр”, – означает повторное сложение точек: G⊕G⊕G⊕…⊕G, где G встречается k раз, а “⊕” – обозначает операцию в группе точек кривой, то есть, сложение точек. (Умножение тут лучше было бы записать [k]G, например, но это детали.)

На значение k накладываются различные ограничения, но это всего лишь натуральное число (конечно, так можно сказать про всё, что встречается “в компьютерах”). Структура кривой такова, что есть пары точек с совпадающими X-координатами, но различными Y-координатами. Этот момент нередко используется в атаках на реализации ECDSA. В данном случае – R это именно X-координата.

Эллиптическая кривая непосредственно использована для вычисления одного параметра подписи – R, который, впрочем, сразу “превращается” из точки, как кортежа значений, задаваемых дополнительной структурой уравнения кривой, в единственное число.

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

Это основная математическая идея ECDSA: базовое уравнение так устроено, что части структуры преобразования, вынесенные наружу в составе публичных значений, сокращаются, если ключ проверки соответствует подписи (и параметрам), но не сокращаются в почих случаях.

Сокращающиеся структуры не видны, а вычислить их, – то есть, обратить, – по открытым значениям и параметрам, сложно. Концептуально это напоминает, например, RSA, где внутри открытого ключа всегда содержится структура, связанная с разложением на простые множители, благодаря которой криптосистема работает. Тут необходимо обратить внимание на то, что, во многих практических реализациях, значение k может вычисляться с использованием и подписываемого сообщения, и секретного ключа – например, так делается в схеме детерминированной ECDSA. Но “классическая” ECDSA такого, вообще говоря, не требует. Это, впрочем, один из самых проблемных моментов реализаций данной криптосистемы – так, если третья сторона знает параметры генератора псевдослучайных чисел, который использовался для получения k, то эта третья сторона без особых трудностей может вычислить секретный ключ по значению подписи и подписанного сообщения (см. ниже).

Итак, эллиптическая кривая, заданная для ECDSA, использовалась для вычисления R. Где ещё встречаются операции с точками? Прежде всего – вычисление открытого ключа. Открытый ключ в ECDSA это точка на кривой, а получается он из секретного значения d путём умножения генератора: Q == d∘G. То есть, d – целое число. Принцип эквивалентен вычислению r. Однако, в отличие от r, открытый ключ Q повсеместно записывают как пару координат (X,Y), но это только способ записи, потому что достаточно сохранять X и один “бит знака” для Y.

Вторая часть подписи ECDSA – параметр s. И значение этого параметра вычисляется уже без использования операций с точками кривой. Уравнение для s следующее:

S == k^(-1)*(H + Rd)

– здесь, кроме уже определённых k, R и d (d – секретный ключ), используется значение H – это и есть подписываемое сообщение (технически, это значение хеш-функции от сообщения).

Все значения в данной формуле – это натуральные числа (даже k^(-1)), а не точки. Поэтому тут использованы другие значки для обозначения операций: “+”, “*”, “^(-1)” – это “обычные” операции сложения, умножения и взятия обратного по умножению. “Обычные” в кавычках по той причине, что вычисления проводятся по модулю некоторого числа. То есть, это привычная арифметика остатков. Положительное число, по модулю которого проводятся операции, это так называемый порядок группы точек кривой. Можно считать, что порядок – это количество доступных для вычислений точек кривой. Порядок обозначают, например, P, а тот факт, что это арифметика остатков “по P” записывают как (mod P). Так что свойства кривой тут участвуют только косвенно. Взятие обратного по умножению – k^(-1) – это нахождение такого числа, которое даст 1 (mod P) при умножении на k. Так как вычисления выполняются (mod q), то k^(-1) тоже будет целым числом. Пример: 4*2 == 1 (mod 7) – так как 8/7 – даст остаток 1. Обратите внимание, что все вычисления дальше – тоже (mod P), но отдельно этот момент упоминаться не будет, так как, для практических целей ECDSA и для простого P, свойства вычислений совпадают с привычными операциями в рациональных числах (кроме сложения точек кривой).

Раз это обычная арифметика, то и по формуле для S нетрудно увидеть, что если известны k, H, R, S, то легко вычислить секретный ключ d – просто перепишем уравнение относительно неизвестной переменной d. Значения H, R, S – публично доступны: первое из них это подписанное сообщение, а два других – сама подпись. Никаких “хитростей” эллиптической кривой тут уже не задействовано, поэтому и никакие особенности арифметики эллиптических кривых конкретно на этом направлении криптосистему не защищают. (Более того, если известно не точное значение, но какие-то дополнительные свойства k, то уравнение S можно превратить в неравенство, составить набор “приближений”, который позволит найти приближённое значение для секретного ключа, чтобы потом быстро подобрать его точно по значению открытого. Но это тема для другой записки.) Итак, при вычислении S операции на эллиптической кривой не используются.

Проверка подписи в ECDSA использует следующее уравнение:

C == (H*S^(-1))∘G ⊕ (R*S^(-1))∘Q

– обратите внимание, что тут разные обозначения операций, чтобы можно было различить операции с точками и операции с числами; а значение Q, – открытый ключ, – это d∘G. Работает вся эта схема потому, что, из-за свойств сложения в группе точек кривой, можно операцию сложения точек ⊕ спустить в натуральные числа, вот как: 3∘G ⊕ 5∘G == (G⊕G⊕G)⊕(G⊕G⊕G⊕G⊕G) == 8∘G. При этом, если подставить вместо S формулу вычисления S (см. выше), то в правой части сократится всё, кроме k. Получим, что C == k∘G, а X-координата C должна совпасть с R, если, конечно, подпись верна и вычисления верны. И здесь эллиптическая кривая используется непосредственно для вычисления итогового значения, а именно – умножение на скаляры точек G (генератор) и Q (открытый ключ), сложение получившихся точек.



Комментировать »

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

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

Понятно, что в статье обнаружатся ошибки и она потребует, как минимум, уточнений. Так, сегодня опубликована записка (Omri Shmueli), указывающая на недостижимые значения параметров, которые использованы в доказательстве корректности алгоритма. Это, впрочем, только добавляет арифметической занимательности, поскольку доказательство недостижимости основано на оценке количества простых чисел, меньших заданного. Дело в том, что описанная версия алгоритма, для корректной работы, требует построения набора из некоторого количества попарно простых натуральных чисел, меньших заданного порогового значения – но для определённых значений параметров таких чисел может не найтись в нужном количестве, поскольку не хватит простых. Если алгоритм нельзя исправить (это ещё тоже не факт) и это удастся доказать, то может даже так оказаться, что постквантовая стойкость криптологических задач теории решёток зависит от количества простых чисел, меньших заданного порога. А это весьма сильное и интересное ограничение. (Но, конечно, вряд ли это так.)



Комментировать »

В марте довольно много писали про новую атаку на SHA-256, “с обнаружением коллизий”. Вообще, тут нужно отделять академические атаки от практики, условно говоря, всяких биткойнов: в исходной работе (“New Records in Collision Attacks on SHA-2”, Li, Liu, Wang) речь идёт про академические атаки на урезанную “функцию сжатия” (см. ниже) из состава SHA-2 (SHA-256 – это разновидность SHA-2), да ещё и со специально подобранным предыдущим состоянием. Это общепринятый подход к исследованию стойкости хеш-функций, результат существенно лучше предыдущих достижений, но нужно учитывать, что он не обязательно приводит к практической атаке на полную хеш-функцию. В статье сказано именно про “практическую атаку”, это верно, однако это разная “практика”.

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

После каждого раунда, блок, в результате применения преобразований, изменяется и потом снова подвергается тем же преобразованиям, которые опять изменяют блок. Эта комбинаторная часть позволяет добиться нужного разрежения для отображения входных блоков в выходные значения. Штатная схема SHA-256 использует 64 раунда в функции сжатия. Атака, о которой идёт речь, работает для 39 раундов (обратите внимание: с подобранным начальным состоянием – это очень важный момент).

Что это означает? Это означает, что исследователи нашли и предъявили кортеж из трёх конкретных значений (чисел или массивов байтов – как хотите), которые, будучи подставленными в урезанную до 39 раундов сжатия версию хеш-функции SHA-256, дают одинаковый результат. Одно из этих значений – это начальное состояние, устанавливаемое перед вызовом функции сжатия внутри урезанной SHA-256. То есть, при штатной реализации SHA-256 – этим состоянием либо был бы предыдущий обработанный блок, либо начальные константы из спецификации SHA-256. Два других упомянутых значения – это различающиеся в некоторых байтах входные блоки. Обработка этих блоков при указанных, весьма строгих, условиях – даёт коллизию. То есть, академическая “практическая” демонстрация, с конкретными числами. Это вполне себе строгий и разумный способ анализа стойкости преобразований. В данной науке это называется SFS-коллизия (от Semi-Free-Start). Но, опять же, очень далеко от демонстрации реальной, практической, “уничтожающей” коллизии SHA-256, то есть, демонстрации двух различных входных текстов, дающих одинаковый результат хеш-функции. (Что, конечно, не отменяет заметного продвижения.)

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

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

Конкретный пример, взятый из исходной работы: для 39 раундов SHA-256, при заданном начальном состоянии, получаются совпадающие значения для разных входных блоков (выдача программы, прилагаемой к работе):

431cadcd ce6893bb d6c9689a 334854e8 3baae1ab 038a195a ccf54a19 1c40606d
431cadcd ce6893bb d6c9689a 334854e8 3baae1ab 038a195a ccf54a19 1c40606d

Можно было бы предположить, что, раз точка совпадения найдена, то и дальнейшие раунды дадут одинаковые результаты. Но это далеко не так – состояние хеш-функции шире, чем конкретный результат преобразования блока. Так, если в той же программе указать 42 раунда (всего на три раунда больше), то значения уже заметно разойдутся:

d33c0cff 17c9de13 21f528f0 3362e217 563f1779 521a1b9c df062e86 19fb5973 
105d6c34 43ceb0ad 120ba1a0 3362e217 d6dd86e0 7da567b5 cf1ca736 19fb5973

Это, ещё раз, никак не уменьшает ценности результата для 39 раундов, но показывает, что для полной SHA-256 всё, – пока что, – хорошо.

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



Комментировать »

Картинка из прошлогодней записки про таблицу подстановок:

S-boxes

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

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



Комментировать »

Единичной окружностью, при некоторых допущениях, можно назвать достаточно мощное множество пар чисел (x, y), которые удовлетворяют формуле X^2 + Y^2 == 1. Это, например, привычный случай школьной координатной плоскости. Но можно сказать, что “окружность”, без всяких формул, это большой набор конкретных пар чисел, которые буквально переписаны в массиве исходных данных. Отсутствие формулы в методе определения делает второй вариант существенно отличающимся от первого. И этот второй вариант как раз соответствует популярному сейчас подходу с использованием ИИ (“искусственного интеллекта”) в качестве инструмента анализа: вместо построения вычислительно эффективного общего метода – предлагается таскать с собой наборы исходных данных, проводя там поиск. Чтобы описать больше разных окружностей – возьмём больше разных массивов.

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

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

Понятно, что не всякие наборы пар чисел укладываются в заданную выше формулу, если, конечно, не изменять базовую логику, определения операций и прочие свойства. У схемы X^2 + Y^2 == 1 – есть много оговорок, её запись и реализация требует некоторых дополнительных соглашений, в отличие от простого “итератора”, построенного в стиле попарного сопоставления некоторых элементов множества. Однако именно поэтому данная схема несравнимо богаче по познавательным возможностям. Например, использование формулы позволяет построить объяснение того, как так выходит, что некоторая пара чисел не лежит на заданной окружности, то есть, построить весьма мощные новые теории. А вот массив исходных данных, сам по себе, – такой возможности не предоставляет: тут только и можно сказать, что “соответствующей пары нет в списке”.



Комментировать »

Кстати, есть весьма полезный пример, показывающий различие между формулами, компьютерами и интерпретацией формул. Его удобно приводить в качестве иллюстрации к объяснениям про “компиляторы, регистры, транзисторы и ячейки с битами”. Отчасти относится к предыдущей заметке. Сравним запись (a == b) с записью ((a – b) == 0). Например, в контексте записи и компиляции исходного кода на том или ином языке программирования: if (a == b) {…} и if ((a – b) == 0) {…} – известно, что результаты вычисления условий в таких if-ах на практике могут различаться; причём то, как именно они различаются, зависит и от языка, и даже от используемого системного окружения.

Наивная арифметическая логика тут такая: “a равно b, когда a-b == 0”. Но тут многое спрятано внутри. Во-первых, никто же не сказал, какого типа объекты a, b; во-вторых, не определено, что это за операция “-“; в-третьих, с равенством, как понятием, вообще говоря, тоже есть масса тонкостей. Так, в записи использован двойной знак равенства “==” – он означает какую-нибудь “эквивалентность”?

Знак “=” – один из самых сложных, с точки зрения машинной интерпретации. Собственно, поэтому и возникли “==”, “===”, “:=” и прочие сочетания. Вот если написано “f = m+n”, то что тут имеется в виду? Что “f” – это “формула” (или даже “функция”), имеющая вид _ + _? Или запись обозначает, что имя “f” нужно использовать как синоним для строки “mn”? Или это условие, которое обозначает проверку того, что число под именем “f” равно сумме чисел под именами “m” и “n”? Или какой-то другой вариант?

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

Однако, если не заходить далеко в орнитологическую область, а остаться с компьютерами, то и тут не нужно даже вспоминать теоретическую математику, чтобы символ “==” начал расплываться: достаточно того, что компьютеры, через языки высокого уровня, работают и со строками символов (что бы это ни значило). Сравнение строк требует дополнительных соглашений, с которыми сталкивались даже многие пользователи персональных компьютеров. Причём процесс тут двунаправленный, приводящий к занимательным эффектам: вспомним, что во многих случаях заглавные и строчные буквы ASCII считаются одинаковыми. Тогда строка “AbC”, выходит, равна строке “ABc”, пусть тут и некоторое видимое свойство перешло на соседнюю букву; но это означает, что “ABC” является повторением “Abc”, и хоть битов для записи нужно больше, ничто не мешает на каком-то этапе обработки переписать “ABC” как “abc” – что сплошь и рядом делается в программировании, а побочный эффект используется для защиты DNS-запросов, сколь бы странным это ни показалось.

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

Вот и вернёмся к языкам программирования и представлению чисел в компьютерах. Известно, что уже в языке Python попытка признать (a-b) == 0 и a == b эквивалентными наталкивается на тот самый, занимательный, эффект:

import math
a = math.pow(5, 55)
b = 5 ** 55

print(a == b)
print((a - b) == 0)

Эта нехитрая программа печатает следующий результат (Python 3.9, Debian 11):

False
True

Так что здесь a хоть и не равно b, но зато (a – b) равно нулю. Что происходит? Происходит вычислительное сравнение, на которое влияет представление чисел внутри Python, переполнение и автоматическое (неявное) преобразование типов:

a == 2.7755575615628914e+38
b == 277555756156289135105907917022705078125

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

import math
a = math.pow(5, 55)
b = 5 ** 55

print(a == float(b))
print((a - b) == 0)

За простыми на вид компьютерными формулами часто скрываются хитрые трактовки и скрытые структуры, которые хоть и подразумеваются, но это подразумевание бывает с двойным (“==”), а то и с тройным дном (“===”).



Комментировать »

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

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

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



Комментировать »

Что лучше – заучить, что 7 * 9 == 63 или знать, что 7 * 9 == 9 * 7? Вопрос дискуссионный. Коммутативность – свойство из разряда “универсальных”, но и хорошее понимание про 63 приводит к не менее важному наблюдению: 63 = 7 * 3^2. С другой стороны, спросите у знающего человека, чему равно π * e – и ответ, с минимальной “занимательностью”, будет таким: π * e == e * π. Спросите то же самое у человека с калькулятором, и он ответит: 8.539734223(…) – возможно, даже без многоточия, поэтому оно в скобках.

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

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



Комментировать »

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

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

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

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

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



Комментировать »

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

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

Почему вычислительное моделирование вообще должно работать на скорости, сравнимой с моделируемым процессом? Это моделирование больше похоже на попытку перебора состояний, то есть на обращение некоторой сложной функции-свёртки. Можно было бы попробовать придумать небольшой алгоритм, который моделировать ничего не будет, но вывод даст похожий на какую-нибудь сворачиваемую молекулу. Другими словами, обязательно ли предполагать, что упавшая на каменный пол стеклянная ёлочная игрушка, прежде чем разбиться, вычисляет набор осколков, на которые она разлетится?

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

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

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

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



Комментировать »

Случайно тут попалось высказанное в качестве примера утверждение про восприятие текста: “если в предложении на английском языке поменять слово, то человек, знакомый с английским, сразу увидит – изменился смысл (meaning) предложения или нет” (перевод с английского). Конечно, всякий пример, подготовленный с подобной степенью обратной аллегоричности, содержит обязательные неточности, но данный вариант особенно интересен, потому что сводит взаимодействие “смысла” и “текста” к отдельным словам.

Вот если в предложении “дерево весело задело” поменять “дерево” на “платье”, то изменится ли смысл? Сможет ли оценить изменение смысла человек, знакомый с русским языком?

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



Комментировать »