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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пишут в The Guardian, что обнаружена “самая старая” чёрная дыра из когда-либо наблюдавшихся. При этом в самой статье, конечно же, речь про следы “окрестностей” дыры, которые “датируют” в 440 млн лет после Большого взрыва. То есть, самая старая дыра относится к раннему периоду избранной модели наблюдений Вселенной – на чём и строится новизна результата наблюдения.

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

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

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

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

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

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

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

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

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