книги / Практическая криптография

11.2 Генерация малых простых чисел

213

списка неверно. Таким образом, существует бесконечное количество простых чисел. □

Примерно такое доказательство и было дано Евклидом более 2000 лет назад.

На протяжении многих веков было получено множество результатов, ка­ сающихся распределения простых чисел. Что интересно, ученые так и не вы­ вели универсальной формулы того, как найти все простые числа из конкрет­ ного интервала, поскольку они располагаются в случайном порядке. Многие простые гипотезы так и не были доказаны. Например, гипотеза Гольдбаха утверждает, что каждое четное число, большее 2, является суммой двух про­ стых чисел. Это утверждение легко проверить с помощью компьютера для относительно малых четных чисел, но математики все еще не знают, является ли это утверждение верным для всех четных чисел.

Для общего развития нелишне ознакомиться и с фундаментальной тео­ ремой арифметики: любое целое число, большее единицы, может быть пред­ ставлено в виде произведения простых чисел, и такое представление является однозначным (если не учитывать порядок, в котором записываются эти про­ стые числа). Например: 15 = 3 •5, 255 = 3 ■5 •17, а 60 = 2 ■2 •3 -5. Мы не будем приводить доказательство этой теоремы в данной книге. Интересующиеся могут найти его в любом учебнике по теории чисел.

11.2Генерация малых простых чисел

Иногда под рукой полезно иметь список малых простых чисел. Для по­ лучения последних воспользуемся так называемым “решетом Эратосфена”; этот алгоритм генерации малых простых чисел все еще считается лучшим.

ф у н к ц и я SM A LLP R IM E LIST

вход: п Максимально возможное значение простого числа. Должно удовлетворять условию 2 < п < 220.

выход: Р Список всех простых чисел < п.

Ограничим значение п. Если оно слишком большое, нам не хватит памяти.

assert 2 < п < 220

Инициализируем список флажков. Каждому из них будет присвоено значение 1.

(Ь2,Ьз,... A ) < - ( U , •••,!)

г <— 2

while г2 < n do

214 Глава 11. Простые числа

Мы нашли простое число г. Пометим все следующие числа, крат­ ные i, как составные.

for j е 2г, Зг, 4г,..., [п/г\ г do bj <— О

od

Поищем следующее простое число в нашем списке. Можно пока­ зать, что этот цикл никогда не приведет к условию г > п, по достиоюении которого функция выполняла бы доступ к несуще­ ствующему bi.

repeat

г <— г + 1 until bi = 1

od

Теперь все простые числа помечены флажками 1. Соберем их в список.

Р < -1 ]

for к € 2,3 ,4 ,..., п do if bk = 1 then

P + - P \ \ k

fi

od return P

В основе этого алгоритма лежит очень простая идея. Каждое составное число с делится на простое число, меньшее с. Каждому из чисел от 2 до п ставится в соответствие флажок, который указывает, может ли данное чис­ ло быть простым. Сначала все числа помечаются как потенциально простые. Для этого их флажки устанавливаются равными 1. Переменной г присваива­ ется значение первого простого числа, т.е. 2. Разумеется, ни одно из чисел, кратных 2, не может быть простым, поэтому мы помечаем числа 2г, Зг, 4г и т.д. как составные, изменяя их флажки на 0. Затем увеличиваем г, пока не доберемся до следующего кандидата на звание простого числа. Отметим, что этот “кандидат” не делится ни на одно из простых чисел, меньших его самого, — в противном случае он был бы уже помечен как составное число. Следовательно, новое значение г является простым числом. Аналогичным об­ разом будем помечать составные числа и искать новое простое число, пока г2 не станет бблыпим, чем п.

Очевидно, в результате применения данного алгоритма ни одно простое число не будет ошибочно помечено как составное, поскольку это делается лишь тогда, когда найден его делитель. (Цикл, который помечает числа как составные, последовательно перебирает значения 2г, Зг,... Каждое из этих чисел имеет множитель г, а потому не может считаться простым.)

11.3 Арифметика по модулю простого числа		215
Почему можно остановиться, когда г2 >	гг? Предположим, число к яв­
ляется составным. Пусть р — его наименьший делитель,		больший едини­
цы. Мы уже знаем, что р — это простое число (согласно		лемме 2). Пусть

q := к/p. Можно утверждать, что р < q\ в противном случае q было бы делителем к, меньшим р, что противоречит определению р. Теперь пока­

жем, что р < у/к. Если бы р было больше чем у/к, мы бы получили, что к = р •q > у/к ■q > у/к•р > у/к •у/к = кИз. этого неравенства следует, что

к > к, а это явное противоречие. Таким образом, р < у/к.

Мы показали, что любое составное число к делится на простое число, которое меньше или равно у/к. Из этого следует, что любое составное число < п обязательно делится на простое число < у/п. Если г2 > п, то г > у/п. Но мы уже пометили все числа, кратные каким-либо простым числам, меньшим г, как составные, поэтому больше составных чисел в списке быть не должно. Оставшиеся числа списка, помеченные как простые, действительно являются таковыми.

Последняя часть алгоритма организует все найденные простые числа в список и возвращает их как результат выполнения функции.

Описанный алгоритм можно было бы несколько оптимизировать, но мы решили отказаться от оптимизации в пользу простоты понимания. При пра­ вильной реализации этот алгоритм работает очень быстро.

Возможно, вас интересует, зачем нам нужны малые простые числа. Ока­ зывается, что их можно использовать для генерации больших простых чисел, которые нам вскоре понадобятся.

11.3Арифметика по модулю простого числа

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

Пусть р — простое число. Когда мы вычисляем результат арифметической операции по модулю р, то используем только числа 0,1,... ,р - 1. Основное правило выполнения операций по модулю простого числа состоит в следую­ щем: мы используем целые числа так, как обычно, но каждый раз, получая результат г, берем его значение по модулю р. Операция взятия по модулю очень проста: мы делим г на р и отбрасываем целую часть полученного ре­ зультата. Остаток от деления г на р и будет искомым ответом. Например, чтобы вычислить значение 25 по модулю 7, мы делим 25 на 7, в результа­ те чего получаем частное 3 и остаток 4, который и будет ответом, а значит, (25 mod 7) = 4. Запись (a mod Ь) применяется для обозначения непосред­ ственной операции взятия числа а по модулю Ь, но, поскольку вычисления

216 Глава 11. Простые числа

по модулю используются слишком часто, а математики довольно ленивы, су­ ществует еще несколько общепринятых способов обозначения. Зачастую все выражение записывается без каких-либо символов модуля, и только в са­ мом конце выражения добавляется оператор (mod р), чтобы напомнить, что все действия в этом выражении выполняются по модулю р. Более того, ес­ ли смысл выражения понятен из контекста, оператор (modp) могут вообще опустить, и тогда вам придется постоянно помнить о том, что все вычисления следует выполнять по модулю р.

Вообще-то заключать операцию взятия по модулю в скобки необязатель­ но. Вполне допустимо записать ее как a mod b. Однако те, кто не привык к использованию оператора mod, могут поначалу путать его с обычным тек­ стом. Чтобы избежать путаницы, мы будем заключать выражение (a mod b) в скобки.

Обратите внимание: число, взятое по модулю р, всегда должно находиться в диапазоне 0,... ,р —1, даже если исходное целое число было отрицатель­ ным. Некоторые языки программирования допускают применение операций по модулю к отрицательным числам (что очень раздражает математиков). Например, если мы возьмем -1 по модулю р, то получим р —1. Общее прави­ ло формулируется таким образом: чтобы подсчитать (a mod р), необходимо найти числа q иг, такие, что a = qp + r u O < r < p . Результатом выражения (a mod р) будет г. Если а = —1, то q = — 1 и г = р — 1.

11.3.1Сложение и вычитание

Складывать по модулю р очень легко. Просто сложите два числа и вы­ чтите из полученного результата р, если он окажется бблыыим или равным р. Поскольку оба слагаемых находятся в диапазоне 0,... ,р — 1, их сумма не может превышать 2р - 2, поэтому, чтобы получить результат в нужном диапазоне, достаточно вычесть р не более одного раза.

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

Эти правила применимы только к числам, уже взятым по модулю р. Если же они находятся за пределами диапазона 0,... ,р — 1, вам придется выпол­ нять полноценное взятие их суммы по модулю р.

Чтобы привыкнуть к вычислениям по модулю, нужно некоторое время. Вначале вас будут смущать выражения наподобие 5 + 3 = l(mod 7). Вы хо­ рошо знаете, что 5 плюс 3 равняется никак не 1, а 8. В то же время, работая по модулю 7, мы имеем, что 8 mod 7 = 1, а значит, 5 + 3 = l(m od 7).

Довольно часто, сами того не понимая, мы используем арифметические операции по модулю и в реальной жизни. Подсчитывая время суток, мы скла­

11.3 Арифметика по модулю простого числа

217

дываем часы по модулю 12 (или 24). В расписании автобусов может быть написано, что автобус отправляется в 55 минут такого-то часа, а его время в пути составляет 15 минут. Чтобы узнать, когда автобус приезжает в место назначения, мы складываем 55 + 15 = 10(mod 60) и определяем, что автобус приезжает в 10 минут следующего часа. Мы пока ограничимся вычислени­ ями по модулю простого числа, однако вы можете выполнять операции по модулю любого числа, которое вам понравится.

11.3.2Умножение

Выполнять умножение, как правило, немного труднее, чем сложение. Что­ бы вычислить (ab mod р), мы вначале подсчитываем произведение аЪ как обычное целое число и затем берем полученный результат по модулю р. Если оба числа находятся в диапазоне 0,..., р— 1, их произведение может достигать числа (р — I)2 = р2 — 2р -I-1. В этом случае вам придется выполнить полно­ ценное деление с остатком, чтобы найти пару (g,r), такую, что ab = qp + г и 0 < г < р. Отбросьте д; искомым результатом является г.

Для большей наглядности рассмотрим пример. Пусть р = 5. Результатом выражения 3 •4(modp) будет 2. Действительно, 3 •4 = 12 и (12 mod 5) = 2. Таким образом, 3 •4 = 2(mod 5).

11.3.3Группы и конечные поля

Математики называют множество чисел по модулю простого числа р(0, 1,

... ,р — 1) конечным полем (finite field) и часто именуют его “полем modp” или же просто “modp”. Ниже приведено несколько полезных замечаний ка­ сательно вычислений в поле mod р.

•Если к элементу поля mod р прибавить любое кратное числа р или вы­ честь из него любое кратное числа р, исходный элемент не изменится.

•Все результаты арифметических операций над полем modp будут на­ ходиться в диапазоне 0, 1,... ,р — 1.

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

ские законы относительно сложения и умножения целых чисел (такие, как a(b -1- с) = аЬ+ ас).

В литературе применяются разные символы для обозначения конечного поля целых чисел по модулю р. Мы будем обозначать его как Zp. В других источниках можно встретить обозначения GF(p) или даже Z/pZ.

218	Глава 11. Простые числа

Теперь необходимо познакомиться с понятием группы (group) — еще одним математическим термином, но на сей раз совсем простым. Группа — это мно­ жество чисел, для которых определена одна операция, например сложение или умножение2. Сумма двух элементов группы должна равняться третьему элементу этой же группы. В группе, для которой определена операция умно­ жения, не может находиться число 0. (Во-первых, умножать на 0 не очень-то интересно, а во-вторых, делить на 0 нельзя.) Тем не менее числа 1 ,... ,р — 1 вместе с операцией умножения по модулю р образуют группу. Эта группа называется мультипликативной группой по модулю р (multiplicative group modulo р) и обозначается по-разному; мы будем использовать обозначение Z*. Конечное поле состоит из двух групп: аддитивной (группы сложения)

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

имультипликативной группы Z*.

Группа может включать в себя подгруппу (subgroup). Подгруппа содер­ жит несколько элементов группы. Если применить операцию группы к двум элементам подгруппы, мы должны снова получить элемент подгруппы. На первый взгляд это звучит довольно сложно, поэтому рассмотрим небольшой пример. Числа по модулю 8 вместе с операцией сложения (по модулю 8) обра­ зуют группу. Числа {0,2,4 ,6} образуют подгруппу. Сложив два любых числа этой подгруппы по модулю 8, мы снова получим элемент этой же подгруп­ пы. Аналогичное утверждение справедливо и для мультипликативных групп. Мультипликативная группа по модулю 7 состоит из чисел 1 ,..., 6 и операции умножения по модулю 7. Множество { 1, 6} образует подгруппу, как, впрочем,

имножество {1,2,4}. Попробуйте перемножить два любых элемента одной

итой же подгруппы по модулю 7, и вы сами убедитесь в том, что получите элемент этой же подгруппы.

Подгруппы применяются для ускорения некоторых криптографических операций. Они также часто используются злоумышленниками для нападения на системы. Вот почему понятие подгруппы так важно для нас.

До сих пор речь шла только о сложении, вычитании и умножении по модулю р. Чтобы полностью определить мультипликативную группу, нужно ввести операцию, обратную умножению, т.е. деление. Оказывается, что мы можем определить и операцию деления по модулю р. Самое простое опреде­ ление этой операции выглядит следующим образом: a /6(modp) — это такое число с, что с •6 = a(mod р). Делить на 0 нельзя, но оказывается, что выра­ жение a /6(modp) определено для всех чисел при b ф 0.

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

11.3 Арифметика по модулю простого числа

219

Как же вычислить частное двух чисел по модулю р на практике? Объяс­ нение того, как это делается, займет несколько страниц. А для начала вновь вернемся на 2000 лет назад — к Евклиду и его алгоритму поиска наибольшего общего делителя.

11.3.4Алгоритм поиска НОД

Еще раз вернемся к курсу математики старших классов: наибольшим об­ щим делителем (greatest common divisor — GCD), или НОД, двух чисел а и b называют наибольшее число к, такое, что к\а и к\Ь. Другими словами, НОД(а, Ъ) — это самое большое число, которое делит и а и 6.

Алгоритм вычисления НОД двух чисел, который мы используем сегодня, был разработан еще Евклидом. Более подробное описание этого алгоритма содержится в книге Дональда Кнута [54].

функция GCD

вход: а Положительное число.

ЬПоложительное число.

выход: к Наибольший общий делитель а и 6.

assert а > О Л Ь> 0 while а ф 0 do

(а, Ь) <— (Ь mod а, а)

od return b

Почему этот алгоритм приводит к нужному результату? Вначале пока­ жем, что операция присвоения, используемая в цикле, не изменяет множе­ ство общих делителей чисел а и Ь. Действительно, (b mod а) — это всего лишь b—sa для некоторого целого числа s. Любое число /г, которое делит а и 6, бу­ дет также делить а и (b mod а). (Между прочим, обратное утверждение тоже верно.) А когда а = 0, b будет общим делителем чисел а и 6, причем наиболь­ шим делителем. Можете сами убедиться в том, что цикл рано или поздно придет к завершению, потому что значения а и 6 все время уменьшаются, пока одно из них не достигнет нуля.

В качестве примера подсчитаем НОД чисел 21 и 30. Начнем с пары (а, Ь) = (21,30). На первой итерации мы вычисляем (30 mod 21) = 9, а значит, получа­ ем (а,Ь) = (9,21). На второй итерации вычисляем (21 mod 9) = 3 и получаем (а,Ь) = (3,9). И наконец, на последней итерации вычисляем (9mod3) = 0 и получаем (а, Ь) = (0,3). Алгоритм возвращает число 3, которое действи­ тельно является наибольшим общим делителем чисел 21 и 30.

У НОД есть еще один “родственник”: наименьшее общее кратное (least common multiple — LCM)> или HOK. Наименьшее общее кратное чисел а и Ь—

220	Глава 11. Простые числа

это наименьшее число, которое делится и на а и на Ъ. Например, НОК(6, 8) = 24. НОД и НОК тесно связаны между собой следующим соотношением:

аЬ

НОК(а, Ь) =

НОД(а, Ь)

Данное утверждение приводится просто как констатация факта, доказывать его мы не будем.

11.3.5 Расш иренны й алгоритм Е вклида

Несмотря на всю свою прелесть, приведенный выше алгоритм не помог нам вычислить частное по модулю р. Для выполнения этой операции восполь­ зуемся другим алгоритмом, известным как расширенный алгоритм Евклида. Его идея такова: вычисляя НОД(а,Ь), мы можем найти два числа и и у, та­ кие, что НОД(а, b) = иа + vb. Это позволит подсчитать значение выражения a/b(modp).

ф ункция EXTEN D E D GCD

вход: а	Положительное число.
b	Положительное число,
выход: к	Наибольший общий делитель а и Ь.
(и, у)	Целые числа такие, что иа + vb= к.

assert а > 0 Л b > 0 (c,d) <- (а, Ь) (uc>vc,ud,vd) <- (1, 0, 0, 1) while сф 0 do

Инвариант: иса + vcb = с Лuda + уф = d

q [d/c\ (с, d) <— (d— qc, c) (uc, vc, ud,vd) <- (ud- quc, vd - qvc, uC}vc)

od

return d, (ud,vd)

Данный алгоритм во многом аналогичен алгоритму поиска НОД. Мы за­ менили переменные а и Ь новыми переменными c u d , чтобы сохранить исход­ ные значения а и 6, так как они нужны для инварианта. Мысленно заменив с и d переменными а и Ь, мы получим в точности алгоритм поиска НОД. (Мы записали формулу d mod с в несколько ином виде, однако результат остается тем же.) Помимо этого, мы добавили четыре переменные, в которых хранятся значения коэффициентов инварианта; для каждого сгенерированного значе­ ния с или d мы отслеживаем, как представить это значение в виде линейной комбинации а и Ь. Инициализировать значения этих переменных легко, пото­ му что в начале алгоритма значению с присваивается значение а, а значению

11.3 Арифметика по модулю простого числа

221

d — значение 6. Когда мы изменяем значения с и d в ходе цикла, обновить значения переменных и и v также несложно.

Зачем нам нужен расширенный алгоритм Евклида? Пусть необходимо вычислить 1/6 mod р, где 1 < 6 < р. Мы используем расширенный алго­ ритм Евклида, чтобы определить EXT E N D E D GCD(6, р). Мы знаем, что НОД 6 и р равен единице, поскольку р — простое число и других делителей кро­ ме единицы и самого себя у него нет. Но в результате применения функции EX T E N D E D G CD мы получаем числа u u v, такие, что ub+vp = НОД(6,р) = 1. Другими словами, ub = 1 — vp или, что то же самое, ub = l(modp). Это зна­ чит, что и = l / 6(modp), т.е. и является числом, обратным 6 по модулю р. Теперь частное а/Ъможет быть подсчитано путем умножения а на и. Мы по­ лучили формулу а/Ь = aw(modp), а подсчитать значение такого выражения не составляет труда.

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

Обратите внимание: значение и может быть отрицательным, поэтому, прежде чем использовать его в качестве обратного числа 6, рекомендуется подсчитать и mod р.

Внимательно посмотрев на алгоритм EXTEN DE DGCD, вы заметите сле­ дующее: если в качестве выходных данных нас интересует только значение и, можно не вычислять значения переменных vc и vj, поскольку они никак не влияют на вычисление и. Это позволяет немного сократить объем работы, необходимый для подсчета частного по модулю р.

11.3.6 Вычисления по модулю 2

Особым случаем арифметики по модулю простого числа является ариф­ метика по модулю 2. Действительно, поскольку 2 — это простое число, мы можем выполнять любые операции по модулю 2. Вычисления по модулю 2 знакомы всем, кто когда-нибудь занимался программированием. На рис. 11.1 представлены таблицы сложения и умножения по модулю 2. Сложение по мо­ дулю 2 — это не что иное, как операция “исключающее ИЛИ” (XOR), которая встречается во всех языках программирования. Умножение по модулю 2 — это всего лишь операция AND. В поле по модулю 2 существует только одна пара взаимно обратных чисел (1/1 = 1), поэтому деление совпадает с умно­ жением. Думаем, вас нисколько не удивит, что поле Z2 является важным средством анализа многих алгоритмов, используемых компьютерами.

222	Глава 11. Простые числа
о	о
о	1

Рис. 11.1. Сложение иумно­ жение по модулю 2

11.4 Большие простые числа

Некоторые криптографические алгоритмы используют очень большие простые числа. Говоря об “очень больших числах”, мы имеем в виду числа с многими сотнями разрядов. Но не стоит беспокоиться — вам не придется работать с такими числами вручную. Для этого существуют компьютеры.

Чтобы компьютер смог оперировать такими большими числами, требует­ ся библиотека арифметических операций многократной точности (multipreci­ sion library). Мы не можем использовать числа с плавающей запятой, потому что у них нет нескольких сотен разрядов точности. Мы не можем исполь­ зовать и обычные целые числа, поскольку в большинстве языков програм­ мирования значения целочисленных типов ограничены примерно десятком разрядов. Лишь некоторые языки программирования обладают встроенной поддержкой целых чисел с произвольной точностью. Написание функций для выполнения вычислений над большими целыми числами — весьма интересное занятие. Более подробно об этом можно прочитать в книге Кнута [54, раз­ дел 4.3]. Тем не менее реализация библиотеки арифметических операций мно­ гократной точности требует намного больше работы, чем кажется на первый взгляд. Нам нужно не только получить правильный ответ, но и вычислить его настолько быстро, насколько это возможно. Существует довольно много особых случаев, рассмотрение которых требует крайне тщательного подхода. Поэтому рекомендуем оставить время для более важных вещей и загрузить из Internet одну из многочисленных бесплатных библиотек или же воспользо­ ваться языком наподобие Python, который обладает встроенной поддержкой больших целых чисел.

Для реализации криптографических систем с открытым ключом нам по­ надобятся простые числа в 2000-4000 бит длиной. Базовый метод генерации таких больших простых чисел удивительно прост: взять случайное число и проверить, не является ли оно простым. Существует много хороших ал­ горитмов, позволяющих определить, является число простым или нет. Су­ ществует также масса простых чисел. В окружении числа п приблизительно одно из каждых Inn чисел является простым. (Натуральный логарифм п, или Inп — одна из стандартных функций, встречающихся на любом инже­