Генерация простых чисел04.10.2019 22:05

В продолжение темы, начатой в этой серии статей, сегодня мы поговорим о генерации простых чисел. Генерация бывает вероятностной и бывает гарантированной. Так вот, наш случай — с гарантией, которая позволяет использовать получаемые числа в приложениях, связанных с криптографией, что обеспечивает, например, безопасность распоряжения вашими деньгами через банковские приложения. Далее вы увидите, как гарантированно получать простые числа достаточного для криптографии размера, а так же какими могут быть проблемы, если пренебречь гарантиями.

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

Сначала определимся с размером. В современной криптографии порядок составного числа определяется формулой $2^{2048}$ , то есть собственно порядок равен 2048 в двоичной систем счисления. А делители у этого составного числа бывают порядка 1024, то есть где-то около значений $2^{1024}$ . Почему 1024? Потому что уже лет десять назад было разложено на множители число порядка 768, а сегодня уже весьма вероятно разложение составных чисел порядка 1024. Вот и решено для надёжности увеличить порядок сразу в два раза, то есть до 2048. Ну, а отталкиваясь от этого порядка легко определить порядок необходимых сомножителей.

Но что будет, если порядок сомножителей окажется много меньше 1024? Тогда за приемлемое время можно разложить составное число, даже если оно имеет порядок 2048. Значит нужно гарантировать, что выбранные нами сомножители действительно имеют порядок близкий к 1024 и при этом являются простыми, то есть не разлагаются на множители. Но вот сам выбор осуществляется по вероятностной схеме, а это как раз и ведёт к потенциальным проблемам.

Проверка вероятности простоты числа осуществляется на основе предположения о том, что число «скорее всего» простое, если его период (о котором рассказывается здесь) является делителем самого числа, минус единица ( $N-1$ ). В виде формулы это выглядит так:

$a^p \pmod N = 1$

$N-1 \pmod p = 0$

Здесь $N$ — исследуемое число, $а$ — значение от $2$ до $N-2$ (оно определяет основание системы счисления, в которой вычисляется период), $p$ — период исследуемого числа. Операция $mod$ здесь означает взятие остатка от деления первого операнда на второй.

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

Как часто ошибается вероятностная проверка простоты? Достаточно редко. Бывает одна ошибка на несколько десятков тысяч простых, а бывает и две, но ни что не гарантирует нас и от трёх. Кроме того, многое зависит от используемого теста. Так, например в стандартной библиотеке языка Java в классе BigInteger реализована проверка, которая допускает промах 2–3 раза на тысячу простых. То есть не стоит думать, что если теоретически ошибок очень мало, то и на практике всё будет в шоколаде.

Чем это опасно? Вроде бы и не так страшно, как могут сказать некоторые, ведь ну что с того, если какой-нибудь сайт, закрывающий просмотр своих страниц протоколом https, получит легко вычисляемый ключ, то какие от этого будут проблемы? Ну узнают хакеры, какие новости вы читали на этом сайте, а что толку? Но на самом деле шифрование производится не только при просмотре веб-страниц. Более неприятная ситуация случится, если хакеры узнают ключ вашего любимого банковского сервиса по дистанционному управлению вашими деньгами. Хотя опять же, вроде бы для того, что бы наверняка вскрыть обмен с банком (и если банк использует слабую проверку простоты), хакеру придётся ждать примерно 500 лет, пока наконец реализуется вероятность выпуска легко вычисляемого ключа, ведь ключи обычно имеют срок действия 1 год и потому чтобы гарантировать взлом нужно ждать пока не будут проведены 500 выпусков нового ключа. Вроде всё логично, но есть очередное «но» — банков на свете гораздо больше, чем 500 штук. Поэтому прямо сейчас, возможно именно в вашем любимом банке, хакеры могут получить доступ к вашим же деньгам.

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

Как устранить эту проблему? Нужно научиться получать гарантированно простые числа. Но как гарантировать их простоту? Для этого существуют четыре метода.

Первый метод — перебор с минимумом ограничений. Обычно это вариант усовершенствованного решета Эратосфена. Метод надёжный и гарантированный, но ограничен очень скромными порядками (менее сотни). Поэтому такой метод неприменим в криптографии.

Второй метод — перебор с более сильными ограничениями. Так, если период числа равен самому числу, минус один, то число гарантированно простое. Формула здесь такая — $N-1=p$ . Но вот для определения равенства периода разности числа и единицы, используются очень тяжёлые методы, которые работают не для всех классов чисел. Поэтому применение их в криптографии упирается либо в ограниченность количества чисел специфических классов, либо во время выполнения проверки, если мы будем наращивать размер числа. И кроме того, даже числа определённого класса сами по себе ничего не гарантируют, что означает необходимость перебирать много чисел-кандидатов. Вот, например, числа Мерсенна, для которых есть безусловный тест простоты, уже все перебрали и выяснили, что в используемом в криптографии диапазоне их практически нет. Вот весь их список с близкими порядками — 1279, 2203, 2281, 3217. Как вы видите, от 1024 до 2048 есть лишь одно подходящее число. Но даже если взять остальные, то их количество нам очень наглядно намекает — не стоит! Значит опять нам не повезло с методом проверки.

Третий метод — вероятностный. Именно его сегодня используют, в том числе, в вашем любимом банке. Как он работает? Очень просто — проверяется остаток от деления произвольного числа в степени $N-1$ на $N$ , если остаток равен единице — вероятно, что число простое. И вот слово «вероятно» здесь наиболее неприятное. И хотя вероятностные методы проверки простоты содержат ещё и дополнительные улучшения, но тем не менее, как было показано выше, стандартная библиотека Java довольно часто ошибается.

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

Теоретические основы.

Что бы понять, как генерировать гарантированно простые числа, нужно немного погрузиться в математику. Но не пугайтесь, математика здесь на уровне пятого класса.

Для полноты понимания рекомендуется посмотреть здесь подробности о том, что такое период и ряды остатков. Ну, а кратко скажем, что ряд остатков образуется при делении «уголком» (известный любому школьнику метод) единицы на выбранное для исследования число. При этом на каждом шаге появляется разность между выше расположенным числом, с дописанным к нему ноликом, и произведением исследуемого числа на значение от 0 до 9 (для десятичной системы счисления) — это и есть остаток. Но шагов при делении «уголком» много, поэтому и остатков тоже много, а вместе они образуют ряд остатков, в котором один и тот же набор чисел периодически повторяется бесконечное число раз. Признаком начала нового цикла является остаток, равный единице. Количество остатков между единицами — это длина периода (или цикла). Вот, собственно, и всё, но так же стоит понимать, что такой метод построения ряда остатков можно применить, используя любую систему счисления, и в частности далее чаще всего будет использована система с основанием 2 (а не 10, как принято в школе). При использовании других систем счисления все правила сохраняются, но количество вариантов произведений на каждом шаге будет другим, равным b (от base), то есть основанию системы счисления.

Итак, из ранее показанного мы знаем, что составные числа всегда дают относительно короткие периоды, не включающие ряд «запрещённых» значений. Зная разложение составного числа на множители легко вычислить, сколько значений обязаны отсутствовать в ряде остатков, формирующих период данного числа. Ряд остатков не будет содержать множители и все числа, кратные этим множителям, если сам ряд построен по основанию системы счисления, не кратному ни одному из делителей (то есть основание не делится на делители числа). Например, если множителей всего два, то количество кратных им остатков определяется по формуле $m=a+b-2$ , где $m$ — количество кратных остатков, $a$ и $b$ — множители, формирующие наше составное число. Зная количество «запрещённых» остатков, легко вычислить, что ряд остатков длинною более половины значения $N-1$ , будет иметь длину, равную $L=N-1-(a+b-2)=N-a-b+1$ . То есть такой ряд будет на $a+b-2$ короче, чем ряд, который получился бы, если данное число было бы простым. Это объясняет, почему все числа с периодом, равным полному периоду (то есть $N-1$ ), оказываются простыми — если бы из последовательности остатков был исключён хотя бы один элемент (который «запрещён»), то период стал бы меньше $N-1$ . В результате наличия такой закономерности мы наблюдаем работоспособность всех тех вероятностных тестов, которыми сегодня проверяют простоту числа. Эти тесты вычисляют значения в ряде остатков на позиции $N-1$ или $(N-1)/2$ , и если значения равны $1$ или $N-1$ , то можно с большой вероятностью утверждать, что число простое. Почему лишь с большой вероятностью, а не гарантировано? Потому что период вероятностные тесты не вычисляют, а между позициями $N-1$ и $(N-1)/2$ могут встретиться ещё единицы, что будет означать неравенство периода значению $N-1$ , но если период не равен $N-1$ , то число может быть составным. При этом само по себе отсутствие равенства не критично, важно другое — такое расположение единиц могут дать псевдопростые числа. Среди проверенных таким тестом чисел можно найти псевдопростые, которые являются составными и тем помогают хакерам, ворующим ваши деньги. Ведь каковы делители таких составных чисел? Они вполне могут оказаться достаточно малыми для того, что бы злоумышленник легко вскрыл зашифрованный обмен данными.

Теперь вспомним, почему вообще могут появляться псевдопростые числа. Такие числа имеют короткие периоды, которые повторяются много раз в пределах полного периода $N-1$ , а потому иногда могут «вмастить» и уложиться целое количество раз в полный период. Так, например, число 25 имеет период длинною 4 для системы счисления с основанием 7. $N-1$ для 25 равно 24, попробуем поделить: 24/4=6. То есть данный период уложился целое число раз в полный период. Этот факт можно проверить по приведённой выше формуле для сокращения периода, но с учётом того факта, что a и b в данном случае одинаковы. Максимально возможный период будет равен 24–4=20, здесь 24 — полное количество остатков, 4 — количество остатков, кратных 5. Но период не всегда бывает максимальным, а все остальные варианты можно получить поделив нацело максимальный период. 20 делится на 2,4,5,10, и как раз при делении 20 на число из приведённого списка мы получаем период длинною 4, который и даёт нам в конце полного периода $N-1$ единицу. А при проверке простоты проверяют как раз значения на позиции $N-1$ , то есть последнее значение в полном периоде. И для 25 оно равно 1, что является признаком простоты числа. Хотя на самом деле однозначный признак простоты, это когда для всех оснований систем счисления, менее $N$ , последнее значение в полном периоде равно единице. Но проверять все системы счисления для больших чисел нет никакой возможности, вот и появляются псевдопростые числа, которые иногда используются даже в криптографии, чем повышают уязвимость наших финансов.

Как устранить влияние псевдопростых чисел? В принципе просто — можно проверить периоды для всех систем счисления, но тогда на эту операцию для больших чисел не хватит никакого времени. Поэтому мы пойдём другим путём. И путь тоже простой (в буквальном смысле — в нём используются другие простые числа). Мы видели, что короткие периоды могут уложиться в полный период целое число раз, и это даёт нам псевдопростые числа. Но что нам мешает эти понедельники «взять и отменить»? Да в общем-то, ничего не мешает.

Для существования коротких периодов полный период ( $N-1$ ) должен делиться на много делителей. Так для числа 25 полный период 24 делится на 2, 3, 4, 6, 8, 12. Вот столько есть возможностей для проникновения на охраняемую территорию псевдопростых чисел. Значит нам нужно просто взять в качестве полного периода простое число, ведь оно вообще ни на что не делится и потому автоматически спасает нас от вражеского элемента. Правда есть одно «но» — нам нужны простые числа, а они, как известно, нечётные (кроме одного исключения — 2), значит если $N-1$ простое, то само $N$ простым уже быть не может. Поэтому нам придётся допустить возможность для появления неполных периодов. Чем это плохо? Как мы видели выше — полный период гарантирует простоту числа, а вот про неполный — мы пока не доказали. Значит нам нужно доказать данный момент.

Доказательство довольно простое — для составного $N$ период, длинною, укладывающейся в $N-1$ два раза, полученный в системе счисления, не кратной делителям N, имеет всего два ряда остатков, и ни один из них не должен содержать чисел, кратных делителям числа $N$ («запрещённых» чисел). Если исключается хоть один элемент из одного ряда остатков, то и второй автоматически уменьшается на столько же (ведь один ряд равен другому, домноженному на любое число, отсутствующее в первом). Значит при наличии делителей у числа $N$ , мы получим меньшую суммарную длину двух периодов со всеми «разрешёнными» остатками, нежели значение полного периода и тем самым сдвинем единицу с места в конце полного периода, чем обеспечим отсутствие псевдопростоты. Но может ли количество кратных делителям остатков оказаться таким, что бы дать ровно половину или одну треть полного периода? Ведь тогда мы получили бы, например, две трети «разрешённых» остатков (два ряда) и одну треть «запрещённых», а в сумме — полный период. Но для получения одной трети нам нужно обеспечить делимость полного периода ( $N-1$ ) на 3, что мы можем довольно легко исключить — берём простое число, умножаем его на два и прибавляем к результату единицу — вуаля, перед нами гарантированно исключающее псевдопростоту число. У него количество кратных делителям остатков не может быть равным одной третьей полного периода, потому что на три полный период не делится. Остаётся вариант с половиной остатков, кратных делителям $N$ . Этот вариант устраняется чуть сложнее, поэтому ниже будет небольшое отступление.

Вычисление периода, или все числа — дети Мерсенна.

Период любого числа можно вычислить. В простейшем случае вычисление производится простым делением уголком $1/N$ до тех пор, пока нам не встретится остаток, равный единице (в системе счисления, не кратной делителям $N$ ). Но для больших чисел это нереально долго. Поэтому есть необходимость в выводе формулы для вычисления периода. И такая формула существует, правда не в идеальном виде, когда на входе имеем число, а на выходе — период. Формула такая:

$N=\frac{b^{m+n+1}-1} {b^n+k}$

Здесь $N$ — исследуемое число, $b$ — основание используемой системы счисления (base), $m$ — максимальная степень $b$ , при которой результат возведения в степень меньше $N$ (по другому — индекс старшего разряда в $N$ в системе счисления $b$ ), $n$ — расстояние слева направо в ряду остатков от индекса $m+1$ (равного количеству разрядов в $N$ ) до единицы, $k$ — некоторый целый коэффициент.

Вывод формулы.

По определению формулы понятно, что (1) $b^{m+1}-N=x$ , то есть первая степень $b$ , которая больше $N$ , позволяет вычесть $N$ и получить некую разницу в виде $x$ . Так же из определения следует, что (2) $x*b^n-k*N=1$ , здесь $k$ — целочисленный коэффициент. Если домножить (1) на $b^n$ и заменить $x*b^n$ на его значение из (2), которое равно $kN+1$ , то получим $$b^{m+n+1}=N*b^n+kN+1=N*(b^n+k)+1 => N=\frac{b^{m+n+1}-1}{b^n+k}$» />.</p> <h3>Полезные свойства.</h3> <p>Как мы видим, используя эту формулу можно получать числа с заранее известным периодом. Правда есть одна сложность — нужно подбирать коэффициент <img src=$ , что для больших чисел опять превращается в нечто недостижимое. Но формула даёт нам другое — мы наглядно видим, как формируются все числа. Да, абсолютно все положительные целые числа можно получить по этой формуле, ведь у всех чисел есть какой-то период. И что интересно — все числа получаются от деления числа Мерсенна на один из его делителей. Вспомним, что числом Мерсенна называется такое число, которое равно $2^n-1$ . В формуле же в числителе мы видим обобщение для чисел Мерсенна с любым основанием (включая 2, разумеется). И если нас интересуют простые числа, то другие основания, кроме 2, нам вообще не понадобятся.

Зная, что мы делим число Мерсенна, нам было бы полезно уметь вычислять период чисел именно для случая деления чисел Мерсенна (вспомним расширенное понятие периода здесь). Но что очень замечательно — формула для вычисления мерсенновского периода совпадает с формулой для вычисления периода типа $1/N$ . Ну, а для вывода формулы деления чисел Мерсенна используется тот же принцип, что и при выводе формулы для деления $1/N$ , за исключением формулы для вычисления значения в ряде остатков с индексом $n$ , которая выглядит так — $\frac{b^{n+1}-1}{b-1}$ , а для двоичных чисел получаем $2^{n+1}1$ .

Теперь у нас все карты на руках и мы можем начинать игру по вскрытию псевдопростых засланцев в рядах простых чисел.

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

Снова про половину периода.

Теперь вспомним, что мы остановились на поиске способа доказать, что мы можем исключить случай, когда половина длины ряда остатков числа кратна его делителям. Доказать мы это хотели для устранения псевдопростых чисел при выборе одного простого числа в качестве основы для конструирования периода следующего простого числа. Так вот теперь мы знаем, что если конструируемое число имеет делители, то их периоды всегда делят период конструируемого числа нацело. Тогда нам остаётся проверить — какие делители могут уложиться в ранее заданные ограничения на конструируемое число. А ограничения такие — его период делится лишь на $2$ и на $(N-1)/2$ . Значит и делителями могут быть лишь числа с периодами $2$ и . Период $2$ имеет число $2$ , более ни одно число такого периода не имеет. Период $2$ не укладывается целое количество раз в $(N-1)/2$ , ведь — простое, поэтому делимость на три исключается при таком периоде. Значит остаётся лишь одна возможность — делители имеют период . Но число не может быть меньше или равно своему периоду, поэтому минимальное значение для делителей такое — $(N-1)/2+1$ . Если перемножить два минимальных делителя, то получим — $(N-1)^2/4+(N-1)+1=(N^2-2N+1+4N)/4=(N^2+2N+1)/4$ , такое значение должно быть не больше $N$ , ведь мы говорим о делителях $N$ . Тогда получаем неравенство $$(N^2+2N+1)/4\leq N => N^2–2N+1\leq 0$» />. Это неравенство может быть отрицательным или равным нулю только при <img src=$ , поэтому для всех сконструированных таким способом чисел псевдопростота исключена, если полученное число больше $1$ . Ну, а для меньших чисел мы можем проверить простоту даже в уме.

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

Но конечно, жизнь была бы мёдом, если бы все проблемы решались так просто. Исключив псевдо-простоту, мы так и не исключили числа, которые ни от кого не прячутся и ни подо что не маскируются. А с ними есть ещё одна проблема — мы пока что умеем проверять произвольный член последовательности остатков лишь при помощи возведения в степень с последующим взятием остатка. Но такой метод очень медленный. Точнее, он достаточно быстр для чисел, используемых в криптографии, но вот для поиска больших простых он не пригоден в домашних условиях, ибо требует много лет вычислений обычного домашнего компьютера, что не даёт нам возможность получить 400k$ (как показано здесь).

Но тем не менее, для вычисления криптографических простых у нас уже почти всё готово. Хотя остаётся ещё наш старый друг — максимализм. Он спрашивает — раз можно использовать период $(N-1)/2$ , то что мешает использовать периоды $(N-1)/4, (N-1)/6, (N-1)/8$ и т.д.? И оказывается, что при должной осторожности — ничего не мешает!

Точно так же, как и в случае с периодом $(N-1)/2$ , для периода $(N-1)/4$ имеем возможность задать ограничение снизу, умножив простое число на 4 и прибавив 1. Тогда мы гарантируем себя от псевдопростых с периодами менее . Значит остаётся рассмотреть возможность появления псевдопростых с периодом, кратным 4, 3, 2 (1 для составных исключается, как показано выше). Из формулы для вычисления числа по периоду видно, что период делимого числа должен быть равен наименьшему общему кратному его делителей, из чего следует, что возможный период числа $N$ должен не только укладываться целое количество раз в $N-1$ (иначе не будет псевдопростоты), но и содержать в себе целое количество периодов делителей. Таким образом резко ограничивается количество возможных делителей псевдопростого числа. Поскольку период любого числа не может быть длиннее $N-1$ , то для возможного делителя $N$ , дающего в результате деления 3, период не может быть длиннее $N/3-1$ , кроме того учтём, что период числа 3 равен 2. $N/3$ должно быть нечётным, поскольку нечётным является $N$ . Из перечисленного следует, что чётный период N/3–1 является наименьшим общим кратным с периодом 2 числа 3, значит возможный период потнециально псевдопростого N должен быть равен периоду числа $N/3$ . Всего есть одно значение величины периода $N$ , для которого возможна псевдопростота, это $(N-1)/4$ . Для остальных значений либо $N/3$ слишком мало, либо его период (а вместе с ним и период $N$ ) уйдёт в запрещённую область ниже . Такая же история и с нечётными числами, меньше $N/3$ , но у них периоды не могут быть больше $(N-1)/4$ , а потому все они просто исключаются из рассмотрения. Теперь покажем, что $N/3$ не может иметь период , а значит не может делить полный период нацело. Сначала вспомним формулу $m=a+b-2$ , которая даёт нам количество кратных делителям остатков для числа, делящегося только на $a$ и $b$ . В нашем случае $N$ , как предполагается, может делиться на $N/3$ и на 3, все остальные делители исключены, поэтому получаем — $m=N/3+3-2=N/3+1$ . Теперь из полного периода нужно вычесть «запрещённые» значения, которых будет $N/3+1$ , а потом разделить на 4. Получаем возможный период произведения $3*N/3$ : $p=(N-1-N/3-1)/4=N/6-1/2$ , что меньше $(N-1)/4$ , то есть период длинной невозможен из-за необходимости учитывать «запрещённые» остатки, которая уводит все возможные псевдопростые периоды в запрещённую область (меньше $(N-1)/4$ ). Значит такая ситуация гарантирует нам, что сконструированное число не псевдопростое, а потому мы снова можем быть уверены в результатах последующего вероятностного теста простоты.

Аналогично, и с учётом делимости полного периода, можно получить такие же результаты и для других значений.