Что такое Общий метод решета числового поля (GNFS) — сильнейшая математика человечества, взламывающая криптографию интернета?

Интернет, которым мы пользуемся каждый день. Все наши коммуникации, будь то сообщения в LINE, видео на YouTube или покупки на Amazon, защищены «криптографией». В настоящее время самым распространенным алгоритмом шифрования в мире является «шифр RSA».

Суть защиты RSA очень проста. Она использует математическое свойство, заключающееся в том, что «даже компьютеры не могут решить задачу факторизации гигантских чисел на простые множители» . Например, для числа «15» сразу понятно, что это «3 × 5». Но как только число становится «270-значным», даже если объединить все суперкомпьютеры мира, на его решение уйдут сотни миллионов лет.

Однако математики тоже не сидят сложа руки. Чтобы взломать этот неприступный шифр, человечество создало магический алгоритм (вычислительную процедуру) под названием «Общий метод решета числового поля (GNFS — General Number Field Sieve)» .

В этой статье мы не будем использовать сложные технические термины, а опираясь только на знания математики средней школы (разложение на простые множители, алгебраические выражения, наибольший общий делитель) , полностью шаг за шагом объясним, как этот «сильнейший алгоритм человечества» взламывает шифры!

Глава 1: Цель взлома — «формула из средней школы»

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

$X^2 - Y^2 = (X + Y)(X - Y)$

Вы можете подумать: «Э-э, неужели такая базовая формула может взломать шифр?». Однако это и есть тот самый главный ключ, который все открывает.

Главная цель при взломе шифра — найти для огромного числа $N$ «такие числа ($X$ и $Y$), что остатки от деления $X^2$ и $Y^2$ на $N$ будут одинаковыми» .

Почему «одинаковые остатки» могут взломать шифр?

Предположим, у двух чисел $X^2$ и $Y^2$ «остатки от деления на $N$ одинаковые». Одинаковые остатки означают, что при вычитании «$X^2 - Y^2$» результат обязательно будет без остатка делиться на $N$ (станет кратным $N$) .

Здесь давайте представим, что огромное число $N$, используемое в шифре, образовано умножением двух секретных простых чисел ($p$ и $q$) ($N = p \times q$).

Если разложить на множители $X^2 - Y^2$, то получится $(X - Y)(X + Y)$ . То, что это число кратно $N$, означает, что где-то в этом умножении спрятаны секретные простые числа $p$ и $q$.

И тут происходит чудо. Математическая вероятность того, что два простых числа $p$ и $q$ разойдутся по разным «комнатам» — «$p$ в комнату $(X - Y)$», а «$q$ в комнату $(X + Y)$» — составляет ровно 50% (одна вторая) .

Предположим, что только простое число $p$ попало в комнату $(X - Y)$. Давайте вычислим «наибольший общий делитель (самый большой общий компонент)» между $(X - Y)$ и $N$.

• Содержимое $(X - Y)$ = $p \times$ какое-то число
• Содержимое $N$ = $p \times q$ Единственный общий компонент здесь — это «$p$» !

Другими словами, в момент вычисления наибольшего общего делителя скрытое простое число $p$ внезапно выпадает, и шифр оказывается полностью взломанным. (Наибольший общий делитель можно моментально вычислить даже на смартфоне с помощью «Алгоритма Евклида»)

[Мини-колонка: Почему именно квадрат? Разве куб или удвоение не подойдут?]

Если взять «$2X - 2Y$», это превратится в $2(X - Y)$, и останется только одна комната, так что простые числа разделить не получится. Если взять «$X^3 - Y^3$», размеры комнат станут несбалансированными, и вычисления станут неоправданно тяжелыми. Для идеального разделения двух простых чисел «квадрат», образующий две красивые комнаты, является самым оптимальным вариантом.

Глава 2: Как найти X и Y? «Головоломка по сбору карточек с простыми числами»

Цель ясна. Однако, если пытаться искать «$X^2$ и $Y^2$ с одинаковыми остатками» наугад, мы не найдем их до самого конца существования Вселенной. Поэтому математики придумали гениальный метод под названием «Головоломка по сбору карточек с простыми числами» .

Шаг 1: Просеивание только золотого песка (гладких чисел)

Сначала мы берем произвольное число $Z$, возводим его в квадрат и вычисляем остаток $W$ от деления на $N$. (Мир остатков: $Z^2 = W$)

Полученный остаток $W$ мы раскладываем на простые множители. Здесь, только когда получается «$W$, состоящее исключительно из маленьких простых чисел, таких как 2, 3, 5, 7» , мы оставляем эту формулу как «выигрышную карточку». Если примешивается большое простое число — мы ее выбрасываем. Это похоже на работу с ситом (решетом) в реке: мы отбрасываем большие камни и собираем только золотой песок.

Шаг 2: Головоломка с приведением к «четному числу»

Предположим, мы собрали 3 таких карточки с золотым песком:

• Карточка A: $Z_1^2 = 2^3 \times 3^1$
• Карточка B: $Z_2^2 = 2^1 \times 5^1$
• Карточка C: $Z_3^2 = 3^1 \times 5^1$

Давайте перемножим их все. Правая сторона станет $(2^3 \times 3^1) \times (2^1 \times 5^1) \times (3^1 \times 5^1)$, а после упрощения получится «$2^4 \times 3^2 \times 5^2$» .

Поразительно, но количество простых чисел стало «4, 2, 2» — все они стали четными ! То, что все они стали четными, означает, что если поделить их количество пополам, мы получим «квадрат чего-либо». А именно: $(2^2 \times 3^1 \times 5^1)^2 = (60)^2$.

Поскольку левая сторона равна $(Z_1 \times Z_2 \times Z_3)^2$, мы, наконец, получаем: $X = (Z_1 \times Z_2 \times Z_3)$ $Y = 60$ Долгожданная пара «$X^2 = Y^2$» завершена!

Для компьютеров головоломки с подсчетом того, «четное число или нечетное (0 или 1)», даются очень легко, поэтому с помощью этого метода можно очень быстро найти $X$ и $Y$.

Глава 3: Стена отчаяния на пути

Казалось бы, теперь любой шифр можно взломать! …Но тут возникает огромная проблема. Если число шифра $N$ имеет длину до «100 цифр», этот метод (называемый методом квадратичного решета) справляется. Но когда $N$ становится «200-значным или 300-значным», промежуточное значение $W$ становится слишком гигантским.

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

И вот здесь наконец появляется совершенное оружие человечества — «Общий метод решета числового поля (GNFS)» .

Глава 4: Гениальная идея человечества — создание «двух миров»

Гениальность идеи GNFS заключается в следующем: «Раз числа становятся огромными потому, что мы считаем только в реальном мире, давайте создадим “параллельный мир” с помощью полиномов (алгебраических выражений) и разделим вычислительную нагрузку на две части» .

Магия алгебраических выражений

GNFS преобразует огромное число $N$ в алгебраическое выражение, используя базовое число $m$. Например, если $N=100$, мы выбираем $m=4$, тогда $100 = 4^3 + 2(4^2) + 4$. Используя переменную $x$, мы превращаем это в выражение (параллельный мир): $f(x) = x^3 + 2x^2 + x$ .

Самое интересное в этом выражении — его свойство: «Если подставить вместо $x$ число $m$ (в данном примере 4), то можно в любой момент “телепортироваться” обратно к реальному числу $N$» .

Поиск золотого песка одновременно в двух мирах

GNFS генерирует множество произвольных пар целых чисел $(a, b)$ и одновременно выполняет два вычисления:

1. Реальный мир: $a - b \times m$
2. Алгебраический мир: значение $a - b \times x$, вычисленное по правилам алгебраических выражений

Благодаря разделению задачи на два мира, размер используемых чисел радикально уменьшается (становится «легче»). Представьте себе, что гигантский валун разбили на два удобных камня.

Затем с помощью сита (решета) отсеиваются и собираются только те чудесные пары $(a, b)$, в которых «и в реальном мире, и в алгебраическом мире результаты состоят только из маленьких простых чисел (являются золотым песком)» . Отсюда и происходит название «метод решета числового поля».

Момент взлома шифра

Когда из обоих миров собираются десятки миллионов «карточек с золотым песком», с помощью матричных вычислений на суперкомпьютерах находится «комбинация, при которой количество простых чисел становится полностью четным», точно так же, как во 2-й главе.

Когда комбинация найдена:

• Число в квадрате, полученное в реальном мире, обозначается как $X^2$
• Выражение в квадрате, полученное в алгебраическом мире, обозначается как $Y(x)^2$

И наконец, мы подставляем $m$ вместо $x$ в $Y(x)$ алгебраического мира, телепортируя его и объединяя с реальным миром. И тут, как по математическому волшебству, строго выполняется условие «остатки $X^2$ и $Y^2$ одинаковы» !

Дальше, как было описано в 1-й главе, достаточно вычислить наибольший общий делитель $X - Y$ и $N$, и неприступный шифр RSA с грохотом рассыпается, открывая секретные простые числа.

Заключение: Математика не заканчивается

Возможно, вы подумали: «Отлично, с помощью GNFS можно взломать любой шифр!». Однако шифр RSA не сдается. В современном интернете используется чудовищно огромное число под названием «RSA-2048 (около 617 цифр)».

Каким бы сильным алгоритмом ни был GNFS, считается, что даже для взлома 270-значного числа (RSA-270) потребовались бы тысячи, а то и десятки тысяч лет, даже если бы объединили все компьютеры мира. На данный момент наши данные в LINE и банках в безопасности.

Но что, если появится «магия, способная мгновенно находить $X$ и $Y$ для любого сколь угодно гигантского числа» ? На самом деле, самое близкое к этому — разрабатываемые сейчас «квантовые компьютеры (Алгоритм Шора)» . Математически доказано, что, используя волновую природу квантовой механики, можно проигнорировать утомительную головоломку со сбором карточек и вытянуть правильный ответ за один раз.

Бесконечная битва умов между создателями шифров (защитой) и создателями алгоритмов взлома (атакой). Когда узнаешь, что «разложение на простые множители» и «алгебраические выражения», которые изучают в средней школе, на самом деле являются оружием, ожесточенно сражающимся на переднем крае глобальной безопасности, разве уроки математики не начинают казаться чуточку интереснее?

Возможно, именно вы, читающий эту статью, в будущем откроете новый сильнейший алгоритм!

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