Сегодня разберемся с двумя самыми популярными страшилками журналистских заголовков: квантовые компьютеры вот-вот взломают всю криптографию и ИИ якобы может взломать твой пароль. Посмотрим, как устроена хеш-функция, что такое квантовые вычисления, при чем здесь алгоритмы Шора и Гровера, может ли ИИ брутфорсить пароли и как все это поможет нам в хешкрекинге.
Дисклеймер: хеш?функции, как и ИИ, и квантовые компьютеры, и вычисления на них, — темы достаточно сложные и глубокие, но я старался объяснить суть, по возможности сохраняя научные термины. Конечно, не обошлось без упрощений — надеюсь, это не вызовет гнев физиков и криптографов.
В предыдущей статье я писал, что хеш-функция — это математическая функция, которая превращает произвольный массив данных (сообщение) в битовый массив фиксированного размера (хеш?сумма, или дайджест). Сейчас самое время заглянуть в ее внутреннее устройство.
Есть два варианта: либо специально разработанный алгоритм сжатия работает по схеме Меркла — Дамгарда, как в SHA-256 или BLAKE, либо используют симметричный блочный шифр, например AES, по схеме Миягути — Пренеля, как в Whirlpool.
Названия схем пусть не пугают: они чем?то напоминают блокчейн — сообщение режут на блоки, для каждого считают хеш, который участвует в обработке следующего блока, и так до тех пор, пока не будет обработано все сообщение.
Разница в том, что в схеме Меркла — Дамгарда хеш блока считают по любому одностороннему алгоритму, а в схеме Миягути — Пренеля сжатие выполняет шифр, где ключ — это блок сообщения, а входные данные — хеш от предыдущего блока.
За счет множества операций и связи между блоками возникает лавинный эффект: один бит разницы в сообщении приводит к совершенно разным дайджестам. Важно запомнить: хеш?функция строится либо на одностороннем алгоритме, либо на симметричном шифре, ключи от которого теряются в жерновах сжатия.
Квант славы
В 2003 году один из сооснователей Intel Гордон Мур сказал, что развитие любого устройства рано или поздно упирается в физический предел. Закон Мура работал благодаря росту плотности транзисторов и увеличению размеров кристаллов, но компоненты уже приближаются к масштабу нескольких атомов и теряют работоспособность из?за квантовых эффектов. Как бы ни было в далеком 2003?м, сегодня, с техпроцессом в пару нанометров, квантовая повестка уже явно маячит на горизонте.
Идея квантовых компьютеров возникла еще в 1980 году одновременно у Юрия Манина и Пола Бениоффа, а первая рабочая реализация появилась только в 1998-м.
Но фишка в том, что 40 лет назад никто не представлял, как эти квантовые компьютеры использовать: была только идея квантового превосходства — когда квантовый компьютер справляется с задачей быстрее классического. Для этого нужен квантовый алгоритм, без него квантовые вычисления вообще не имеют смысла.
Ждать такого алгоритма пришлось до выступления Питера Шора в 1994 году. Именно тогда мечты о квантовых компьютерах захватили умы физиков, хакеров и, конечно, журналистов.
Что такое квантовый компьютер?
Грубо говоря, по законам квантовой механики электрон не может одновременно иметь точно заданные скорость и положение, поэтому он существует в некоторой области — электронном облаке вокруг ядра атома. Состояние электрона в каждой точке этого облака описывают как суперпозицию, и, так как таких состояний может быть бесконечно много, поведение электрона в целом задается волновой функцией.
При взаимодействии нескольких электронов коэффициенты суперпозиций их волновых функций запутываются. Каждому состоянию запутанной волновой функции соответствует своя вероятность, но при попытке измерения электроны «умирают», и этот процесс называют коллапсом волновой функции.
Смысл квантового компьютера в том, чтобы использовать кубит (условную частицу) с двумя базовыми состояниями — 0 и 1. Чем больше кубитов, тем мощнее квантовый компьютер, а запутанная волновая функция перемножает числа состояний: при одном кубите их 21 = 2, при трех кубитах уже 23 = 8.
Квантовый алгоритм заставляет эту запутанную волновую функцию эволюционировать, выполняя нужные нам вычисления. Квантовое превосходство достигается за счет того, что кубит может находиться во всех своих состояниях одновременно и все возможные варианты как бы анализируются за одну операцию.
Но у суперпозиций есть свои вероятности, поэтому при коллапсе мы каждый раз можем получать разные значения для каждого кубита. Если же повторить алгоритм тысячи раз, самый частый результат и будет считаться верным — почему так происходит, остается одним из парадоксов квантовой физики.
Защитные свойства хешей и шифров, по сути, держатся на том, что их нельзя взломать за разумное время, а квантовое превосходство, как вещают из всех утюгов, позволяет обойти это ограничение. Для нас наиболее интересны два квантовых алгоритма: алгоритм Шора и алгоритм Гровера, остальные к криптографии прямого отношения не имеют.