Евгений Ерошев
Недавно я сделал генератор паролей из случайных слов. Пока писал к нему пояснения, застрял на простом вопросе: почему пароль нельзя просто вычислить по тому, что хранит сайт? Ответ оказался гораздо интереснее, чем я думал. Он ведёт к одной из главных нерешённых задач математики, за решение которой обещан миллион долларов, и к новостям этой осени, когда нейросети начали решать задачи, над которыми люди бились десятилетиями.
Сайт хранит не пароль, а его отпечаток
Почта, магазин или соцсеть не должны записывать ваш пароль в базу как есть. При регистрации они пропускают его через особую формулу и получают набор знаков, отпечаток пароля. В базу записывается только он. Когда вы входите, сайт снова считает отпечаток введённого пароля и сравнивает его с записанным: совпало, значит, пароль верный.
Из пароля Reka7TableGorod! такая формула (SHA-256) делает отпечаток, который начинается на c153 и заканчивается на ca3c. Стоит заменить один знак, Reka7TableGorod?, и отпечаток станет совсем другим: e650…f2b0. По отпечатку нельзя даже понять, близко ли вы к правильному паролю.
Главное свойство формулы: она работает в одну сторону. Из пароля отпечаток получается мгновенно, а способа вычислить пароль по отпечатку никто не знает. Поэтому тот, кто украл базу сайта, получает отпечатки, а не пароли, и ему остаётся только угадывать.
Попробуйте сами: проверить легко, найти трудно
Ниже я загадал пароль из двух слов. Проверка любой вашей догадки занимает долю миллисекунды. А чтобы найти пароль, придётся делать то же, что делает взломщик: перебирать все варианты подряд. Ваш браузер сделает это сам, засечёт свою скорость и прикинет, сколько ушло бы на настоящие пароли.
Разница между строчками таблицы и есть защита. Проверить пароль всегда просто, а время поиска с каждым словом из словаря генератора растёт примерно в 3 685 раз.
Задача на миллион долларов
«Проверить легко, найти трудно» встречается не только в паролях. Возьмите судоку: решить его трудно, а проверить готовое решение может кто угодно за минуту. Так же устроены составление расписаний, прокладка маршрутов и тысячи других задач.
Главный открытый вопрос информатики звучит так: правда ли, что существуют задачи, где ответ легко проверить, но по-настоящему трудно найти? Математики записывают его как P ≠ NP. В 2000 году Математический институт Клэя включил его в семь задач тысячелетия и пообещал за решение миллион долларов. Почти все специалисты уверены, что ответ «да», но доказать этого не может никто.
Если бы вдруг оказалось, что P = NP, то есть всё, что легко проверить, легко и найти, то пароль по отпечатку можно было бы вычислять без угадывания. Вместе с паролями рухнула бы почти вся криптография: замок в адресной строке, шифрование переписки, электронные подписи.
Почему очевидное так трудно доказать
Доказать, что задачу можно решить быстро, легко: достаточно показать один способ. Доказать, что быстрого способа нет, гораздо труднее, ведь нужно исключить все мыслимые алгоритмы, включая те, которые ещё никто не придумал. Найти в лесу гриб — один раз нагнуться. Доказать, что такого гриба в лесу нет, — значит обойти бесконечный лес.
К тому же интуиция «быстрее тут не бывает» не раз подводила даже великих. В 1960 году Андрей Колмогоров предположил на семинаре, что умножать большие числа быстрее, чем столбиком, нельзя. Через неделю 23-летний студент Анатолий Карацуба нашёл способ быстрее. Быстрый и при этом безошибочный способ проверить, простое ли число, нашли только в 2002 году. А вот две похожие задачи: проехать по каждой дороге ровно один раз — лёгкая, а побывать в каждом городе ровно один раз — трудная, и быстрого способа для неё не знает никто.
Есть и совсем удивительная деталь. Математики доказали, что привычные способы доказательства для этой задачи заведомо не годятся. Одно из таких препятствий в 1994 году нашли Александр Разборов и Стивен Рудич. Если надёжные шифры существуют, то самые естественные методы доказать «эта задача трудна» обречены на провал. Вера в стойкость шифров сама мешает её доказать.
Почему нельзя доказать хотя бы для одной формулы
Кажется, что проще доказать стойкость одной конкретной формулы, например MD5. Но и это не выходит. Теория сложности говорит о том, как растёт время решения, когда растёт задача. А у MD5 размер фиксирован: отпечаток всегда 128 бит. Для такой формулы математически существует «мгновенный» способ: таблица всех отпечатков с подходящими паролями. Построить её физически невозможно, но с точки зрения теории она есть. Так же обстоит дело с обычными шахматами 8×8: их можно решить таблицей всех позиций, поэтому теория сложности говорит только о шахматах на доске любого размера.
Да и «только перебором» про MD5 неправда. В 2009 году нашли способ обращать его быстрее полного перебора: примерно за 2^123 действий вместо 2^128. Это всё равно непредставимо много, но перебор оказался не единственным путём.
Как формулам доверяют без доказательства
Так же, как мосту или сейфу. Мост не доказывают математически, его испытывают нагрузкой. Сейфу присваивают класс взломостойкости после того, как специалисты с инструментами пытаются его вскрыть.
С формулами работают похожие механизмы.
- Формулы открыты. Секретом должен быть только ключ или пароль, а сама формула публикуется, и разбирать её может кто угодно.
- Их выбирают на конкурсах. Стандарт шифрования AES выбрали в 2000 году после трёх лет открытого конкурса, в котором команды со всего мира ломали формулы друг друга. За взлом стандартной формулы дают мировую славу, поэтому атакуют её лучшие специалисты.
- За взлом можно очень хорошо заработать. На SHA-256 держится биткоин. Тот, кто научился бы её обращать, сказочно разбогател бы, но за все годы этого никто не сделал.
И главное: формулы не ломаются в один день, трещины видно заранее.
| Формула | Опубликована | Первая слабость | Настоящая подделка отпечатка |
|---|---|---|---|
| MD5 | 1992 | 1996 | 2004, поддельный сертификат сайта в 2008 |
| SHA-1 | 1995 | 2005 | 2017, Google |
От первой трещины до настоящей атаки у MD5 и SHA-1 прошло от 8 до 12 лет, и всё это время специалисты вслух советовали переходить на новую формулу.
Что изменилось в 2026 году
Этой осенью стало ясно, что нейросети умеют делать настоящую математику. В мае модель OpenAI опровергла гипотезу Эрдёша о единичных расстояниях, вопрос 1946 года; независимые учёные повторили результат и опубликовали его в PNAS. В сентябре Claude компании Anthropic впервые полностью перевёл доказательство Великой теоремы Ферма на язык, где компьютер проверяет каждый шаг. В октябре система Google DeepMind решила 9 открытых задач Эрдёша, работа вышла в журнале Science.
Самое громкое заявление пока самое спорное. В сентябре OpenAI объявила, что её система решила ещё одну задачу тысячелетия, об уравнениях движения жидкости. Институт Клэя решение не признал: в нём используется специально подобранная внешняя сила, которую большинство математиков из задачи исключает. А из 166 страниц машинного доказательства люди пока почти ничего не поняли.
Для шифров это значит вот что. Испытание, на которое у людей уходили годы, нейросеть проводит за дни. В июле модель Anthropic за 60 часов нашла слабость в подписи HAWK, которую два года проверяли специалисты на конкурсе NIST, и на следующий день авторы сняли её с конкурса. Та же модель нашла атаку на AES, урезанный до 7 раундов из 10. Полный AES не пострадал, но так всегда и начинается проверка запаса прочности. А на китайском конкурсе шифров в сентябре за первую неделю у 89 участников нашли 191 слабость, 78 из них критические, и больше половины критических нашёл один исследователь с помощью ИИ.
Теперь о квантовых компьютерах. Оценки того, сколько нужно кубитов для взлома RSA, на котором держится замок в адресной строке, за несколько лет упали в сотни раз.
Сколько кубитов нужно, чтобы взломать RSA-2048
Источники: трекер оценок, обзор Quantum Sentinel. Таких машин пока нет.
Поэтому мир уже переходит на новые стандарты, которые квантовый компьютер не берёт. Google назначил себе срок до 2029 года, а американский институт стандартов NIST в октябре утвердил: старые алгоритмы устаревают после 2030 года и запрещены после 2035-го.
Что это значит для вашего пароля
Меньше, чем кажется по новостям. Квантовые компьютеры угрожают прежде всего замку соединения и подписям, а не отпечаткам паролей. Нейросети пока ломают новые и урезанные формулы, а не те, что хранят ваши пароли. Главная опасность осталась прежней: короткий или повторяющийся пароль угадывают перебором, и никакая математика тут не нужна.
Поэтому правила простые:
- длинный случайный пароль, например из пяти случайных слов: его не переберут даже там, где сайт хранит отпечатки устаревшей формулой;
- на каждом сайте свой пароль: если один сайт подведёт, взломщик попадёт только туда;
- второй шаг входа на почте и в банке: код из приложения или ключ выручат, даже если пароль узнали.
Каждая защита может дать трещину, но чтобы все они сломались разом, должно очень не повезти. Пароль из случайных слов можно сделать в моём генераторе: он работает прямо в браузере и никуда ничего не отправляет.
Обложка: чертёж кодового замка из патента США № 1 071 633, Джордж Бакай, 1913 год. Общественное достояние, Wikimedia Commons.
Можно ли вычислить пароль, если украли базу сайта?
Нет, если сайт хранит отпечатки паролей, а не сами пароли. Способа вычислить пароль по отпечатку никто не знает, взломщику остаётся угадывать. Короткие и популярные пароли он угадает быстро, длинные случайные — нет.
Что такое P ≠ NP простыми словами?
Это вопрос о том, бывают ли задачи, где готовый ответ проверить легко, а найти его трудно, как в судоку. Почти все специалисты считают, что бывают, но доказать это не может никто, хотя за доказательство обещан миллион долларов.
Опасны ли квантовые компьютеры для моих паролей?
Почти нет. Они угрожают прежде всего шифрованию соединения и электронным подписям, и мир уже переходит на новые стандарты. От перебора пароля защищает его длина и случайность.
.jpg){kind=link}