Теоретико-численные методы в криптографии

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ 

СИБИРСКИЙ  ФЕДЕРАЛЬНЫЙ  УНИВЕРСИТЕТ 
 
 
 
 
 
 
 
 
 
 
 
 
 
Л. В. Кнауб, Е. А. Новиков, Ю. А. Шитов 
 
 
ТЕОРЕТИКО-ЧИСЛЕННЫЕ  МЕТОДЫ  
В  КРИПТОГРАФИИ 
 
 
Рекомендовано Сибирским региональным учебно-методическим 
центром высшего профессионального образования для межвузовского использования в качестве учебного пособия для студентов, обучающихся по 
специальности 090102 «Компьютерная безопасность» и направлениям подготовки 090900 «Информационная безопасность» и 010200 «Математика и 
компьютерные науки» от 5 июля 2010 г. 
 
 
 
 
 
 
 
 
 
 
 
Красноярск 
СФУ 
2011 

УДК 519.72(075) 
ББК 32.811я73 
К53 
 
Рецензенты: 
И. О. Богульский, ведущий научный сотрудник ИВМ СОРАН, 
д-р физ.-мат. наук, проф.; 
Ю. В. Шорников, д-р техн. наук, проф. кафедры АСУ новосибирского государственного технического университета 
 

 
Кнауб, Л. В. 
К53 
 
Теоретико-численные методы в криптографии : учеб. пособие /  
Л. В. Кнауб, Е. А. Новиков, Ю. А. Шитов. – Красноярск : Сибирский федеральный университет, 2011. – 160 с. 
ISBN 978-5-7638-2113-7 
 
Излагаются некоторые элементы теории чисел, отношения сравнимости, модулярная арифметика, степенные вычеты, первообразные корни, индексы, алгоритмы дискретного логарифмирования, китайская теорема об остатках, простые 
числа и проверка на простоту, разложение чисел на множители и арифметические 
операции над большими числами. В прил. 1 описаны основы теории групп, колец 
и полей, а в прил. 2 приведены реализации некоторых алгоритмов, даны тексты 
программ на языке Borland C++, снабженные подробными комментариями. 

Для студентов, обучающихся по специальности 090102 «Компьютерная 

безопасность» и направлениям подготовки 090900 «Информационная безопасность» и 010200 «Математика и компьютерные науки». 
 
УДК 519.72(075) 
ББК 32.811я73 
 
Учебное издание 
 
Кнауб Людмила Владимировна, Новиков Евгений Александрович 
Шитов Юрий Александрович 
 
ТЕОРЕТИКО-ЧИСЛЕННЫЕ  МЕТОДЫ  
В  КРИПТОГРАФИИ 
 
Редактор Т. М. Пыжик 
Компьютерная вёрстка Д. Р. Мифтахутдинова 
 
Подписано в печать 06.06.2011. Печать плоская. Формат 60×84/16 
Бумага офсетная. Усл. печ. л. 9,3. Тираж 100 экз. Заказ № 2481 
 
Редакционно-издательский отдел Библиотечно-издательского комплекса 
Сибирского федерального университета. 660041, г. Красноярск, пр. Свободный, 79 
 
Отпечатано полиграфическим центром Библиотечно-издательского комплекса 
Сибирского федерального университета. 660041, г. Красноярск, пр. Свободный, 82а 
 
ISBN 978-5-7638-2113-7  
 
 
© Сибирский федеральный университет, 2011 

ВВЕДЕНИЕ 
 
 
Основой данного пособия является курс лекций по теоретикочисленным методам в криптографии (ТЧМК). Этот курс предназначен для 
студентов ИКИТ кафедры прикладной математики и компьютерной безопасности, которые специализируются по информационной безопасности. Лекции по данному предмету формировались с 1996 года. Надо сказать, что в то 
время литературы на русском языке по таким направлениям, как защита информации, криптографии и математическим методам в криптографии практически не было (в отличии от зарубежных изданий). Поэтому на первом 
этапе «скелет» курса формировался на элементах теории чисел, алгоритмах 
арифметических операций с длинными числами и криптографических алгоритмах с открытыми ключами (RSA, схема Диффи – Хеллмана, схема ЭльГамаля, схема аутентификации Шнора). Постепенно в тексты лекций, начиная с 2000 года, включались численные алгоритмы для решения трудных  
задач теории чисел. Для этого использовались переводы из зарубежных изданий по соответствующей тематике. В 2003 году Ю. А. Шитов издал методические указания по изучению численных алгоритмов для некоторых задач  
из теории чисел, которые использовались в курсе лекций по ТЧМК [15]. 
С 2001 года по направлениям «Криптография и математические методы в криптографии» начинают появляться учебные пособия и монографии на 
русском языке. В библиографическом списке приведен, по мнению авторов, 
достаточно полный обзор существующей литературы по этому направлению. 
В список не включены те учебники, в которых содержатся главы и разделы 
по арифметическим алгоритмам в теории чисел, так как любое учебное пособие по классическим курсам представляет собой аранжировку давно сформулированных и доказанных результатов, поэтому мы широко используем  
материалы из учебников, перечисленных в библиографическом списке. 
Данное пособие отличается порядком и простотой изложения.  
Немного больше, чем в других пособиях, уделяется внимание решениям 
сравнений. Кроме того, при изложении результатов исключаются из рассмотрения доказательства некоторых трудных теорем, поскольку при желании слушатели курса могут ознакомиться с доказательствами в перечисленных источниках. При выборе материала авторы исходили из минимальных требований к начальной подготовке слушателей данного курса. 
Авторы предлагаемого пособия делают упор на возможность практической 
реализации изложенных алгоритмов на компьютере. Для некоторых алгоритмов, сформулированных в пособии, в приложении даны тексты программ, реализованных на языке BORLAND C++. Программы реализовал  
и тестировал М. В. Рыбков – студент группы ВТ 05–04, ИКИТ, СФУ. 
Нумерация определений, теорем и соотношений приведены в разделах пособия. 

НЕКОТОРЫЕ  ЭЛЕМЕНТЫ  ТЕОРИИ  ЧИСЕЛ 
 
 
В пособии не излагается теория чисел, а дан минимальный инструментарий из этой теории, который в дальнейшем потребуется для изучения 
криптографических систем, используемых в задачах по защите информации. Более подробное изложение математической теории чисел можно 
найти, например, в [1–2]. В теории чисел (по крайней мере, в той части, которая используется в криптографии) рассматривают целые числа  
и арифметические операции над ними. Перейдем к описанию основных 
понятий и определений из теории чисел [3]. 
Определение. Множество N натуральных чисел определяется с использованием аксиом Пеано: 
1. 1  N (единица  натуральное число). 
2. Для любого а  N существует единственное последующее а+  N. 
3. Для любого а  N выполняется неравенство а+ ≠ 1 (единица – наименьшее натуральное число). 
4. Если а+ = b+, то а = b (каждое последующее число обладает единственным предыдущим). 
5. Если некоторое подмножество N  N содержит единицу и для  
каждого натурального числа аN выполняется а+N, то N = N (принцип 
индукции). 
Таким образом, N = {1, 2, 3, 4, ...}. 
На основании этих аксиом строится арифметика натуральных чисел, 
в которую включены операции сложения и умножения. Каждой паре натуральных чисел a, b можно единственным образом сопоставить их сумму  
натуральное число а + b так, чтобы выполнялись условия для любых натуральных чисел а, b, с: 
1) а + 1= а+; 
2) ассоциативность сложения: (а + b) + с = а + (b + с); 
3) коммутативность сложения: а + b = b + а; 
4) если а + b = а + с, то b = с. 
Каждой паре натуральных чисел а, b можно единственным образом 
сопоставить их произведение  натуральное число a·b так, чтобы выполнялись условия для любых натуральных чисел а, b, с: 
1) а · 1 = а; 
2) a · b+ = а · b + а; 
3) ассоциативность умножения: (а · b) · с = а · (b · с); 
4) коммутативность умножения: a · b = b · а; 
5) дистрибутивность умножения относительно сложения: 
а · (b + с) = а · b + а · с, (а + b) · с = а · с + b · с; 
6) если а · b = а · с, то b = с. 

Заметим, что множество натуральных чисел линейно упорядочено, т. е. 
для любых а, b  N выполняется ровно одно из условий: а > b, а < b, а = b. 
Отношение < и > транзитивно, т. е. из неравенств а < b и b < с следует, что а < с. Если для а, b  N выполняется одно из соотношений а > b 
или а = b, то записывают а ≤ b или b ≥ а. 
Определение. Множество Z целых чисел определим как объединение множеств натуральных чисел, отрицательных натуральных чисел и нуля. Таким образом 
 
Z = {..., –3, –2, –1, 0, 1, 2, 3, ...}. 
 
На множестве Z целых чисел операции сложения и умножения задаются теми же правилами, что и для натуральных чисел. 
Определение. Говорят, что целое число а делится (нацело) на целое 
число b > 0 (или что целое число b > 0 делит целое число а), если существует такое целое число с, что а = bс. Число а называют кратным числа b, 
число b  делителем числа а, число с  частным от деления а на b. 
Пример. 8 = 4 · 2 (8 делится на 4 или 4 делит 8). 
Отношение делимости обладает следующими свойствами. 
1. Нуль делится на любое целое число. 
2. Если a1 делится на b, а2 делится на b, то a1 + а2 делится на b.  
3. Если a1 ± а2 делится на b и a1 делится на b, то а2 делится на b. 
4. Если а делится на b и х  произвольное целое число, то ха делится на b. 
5. Любое целое число делится на 1. 
6. Если а делится на b и b делится на с, то а делится на с. 
7. Если 1 делится на а, то а = ±1. 
Теорема 1. Для любого целого a и целого b > 0 существуют, и притом единственные, целые q и r, такие, что a = bq + r, 0 ≤ r < b. 
Число r называют остатком от деления a на b. Если r = 0, то число q 
называют полным частным, в противном случае (r ≠ 0) число q называют 
неполным частным. 
Доказательство. Возьмем числа b · 1, b · 2, …, … При a ≥ 0 среди 
этих чисел рассмотрим множество M тех, которые больше, чем a. Согласно 
аксиом Пеано, множество M не пусто. Следовательно, в этом множестве 
существует некоторое наименьшее число b · k. Тогда справедливо неравенство b · k ≤ a < b · (k + 1).  
При a < 0, a > 0 можно рассмотреть множество M чисел b · i (i = 1, 
2, …), для которых выполняется неравенство b · i ≥ a и, соответственно, 
найти такое наименьшее  число b · t', что при t = t' – 1 будет справедливо  
 
bt < –a ≤ b(t + 1),  

так что 
 
b(– t – 1) ≤ a < b(– t).  
 
Итак, для a и b (b > 0) существует целое q, такое, что 
 
bq ≤ a < b(q + 1). 
 
В этом случае, обозначив через r разность a–bq, получаем 
 
r = a – bq < b(q + 1) – bq = b, r ≥ 0, 
 
так что a = bq + r, 0 ≤ r < b. 
Определение. Целое число d ≠ 0 называется общим делителем целых 
чисел a1, a2,… ak, если каждое из чисел a1, a2,… ak делится на d. 
Пример. Числа 2, 3, 6 являются общими делителями чисел 12, 18, 36, 72. 
Определение. Общий делитель d ≠ 0 чисел a1, a2,… ak называется 
наибольшим общим делителем (НОД) этих чисел, если d делится на любой 
другой общий делитель этих чисел.  
Наибольший общий делитель чисел a1, a2,… ak обозначается так:  
d = НОД(a1, a2,… ak) или просто d = (a1, a2,… ak). 
Пример. Число 6 является наибольшим делителями чисел 12, 18, 36, 
72, т. е. 6 = НОД (12, 18, 36, 72) или 6 = (12, 18, 36, 72). 
Теорема. Для любых целых чисел, из которых хотя бы одно отлично 
от нуля, существует единственный НОД (см., например, [3]). 
Теорема 2. Для любых целых чисел a1, а2, ..., ak наибольший общий 
делитель d можно представить в виде линейной комбинации этих чисел, т. е.  
 
d = c1a1 + c2a2 + ... + ckak, 
 
где ci – целые числа. 
Доказательство [3]. Пусть А = {c1a1 + c2a2 + ... + ckak}  множество 
всевозможных целочисленных линейных комбинаций чисел а1, а2, ..., ak. 
Будем считать, что не все числа a1, а2, ..., ak нулевые, тогда в множестве А 
существует наименьший положительный элемент. Обозначим его через d. 
Покажем, что множество А совпадает с множеством всех целых чисел, 
кратных d. Поскольку число d может быть представлено в виде линейной 
комбинации чисел a1, а2, ..., аk, то и любое число вида xid, где xi – целые 
числа, может быть представлено в виде линейной комбинации этих чисел. 
Обратно, любая линейная комбинация чисел a1, а2, ..., аk делится на 
d. Действительно, применим к числу d и произвольному элементу у  А 
теорему о делении с остатком: существуют такие целые числа q и r, что  
y = qd + r, причем 0 < r < d. Число r = y – qd является элементом множества А, 

поскольку у  А и d  А. Но d  наименьший неотрицательный элемент 
множества А, значит, r = 0 и y = qd. Таким образом, A = {xid}. 
Осталось доказать, что d = НОД(a1, a2,… ak). Каждое из этих чисел 
имеет вид xid, (xi – целое число), что следует из комбинации вида  
 
0 · a1 + 0 · а2+ ... + 0 · ai–1 + 1 · ai + 0 · ai+1, + ... + 0 · аk). 
 
Таким образом, d  общий делитель чисел a1, а2, ..., аk. Пусть с  любой другой делитель этих чисел. Тогда по свойству 2 делимости с делит 
каждую линейную комбинацию вида c1a1 + c2a2 + ... + ckak, в том числе  
и ту, которая равна d. 
Из доказанной теоремы следует, что для любых не равных одновременно 0 чисел a, b существует два числа c, d такие, что НОД(a, b) =  
= a · c + b · d. 
Определение. Целое число n называют простым, если |n| ≠ 1 и единственными делителями числа n являются числа 1, 1, n, n. 
Если натуральное число p не делится ни на одно простое число d  
√p, то число p – простое. 
Определение. Натуральное число p  1 называется составным, если 
число p имеет, по крайней мере, один положительный делитель, отличный 
от 1 и p. 
Если число p составное, то справедлива следующая теорема. 
Теорема. Для любого составного числа наименьший, отличный от 1, 
положительный делитель является простым числом. 
Определение. Целые числа a1, а2, ..., аk называются взаимно простыми в совокупности, если НОД(a1, а2, ..., аk) = 1. Целые числа а и b называются взаимно простыми, если НОД(a, b) = 1. 
Определение. Целые числа a1, а2, ..., аk называются попарно взаимно 
простыми, если НОД(a1, aj) = 1 для всех 1 ≤ i ≠ j ≤ k. 
Пример. Числа 3, 15, 6, 4 взаимно просты в совокупности, так как 
НОД(3, 15, 6, 4) = 1. Числа 3, 8, 17, 25, 121 попарно взаимно просты. 
Теорема. Для того чтобы целые числа были взаимно просты, необходимо и достаточно, чтобы существовали такие целые числа,что a · c + b · d = 1. 
Теорема 3 (основная теорема арифметики [3]). Всякое целое число n 
(n ≠ 1, 0, 1) можно представить в виде n = ε p1 p2...pr , где ε = ± 1 и р1 ,р2 ,…, 
рr  простые числа (не обязательно различные), r ≥ 1. Это представление 
единственно с точностью до порядка сомножителей. 
Доказательство [3]. Сначала докажем, что разложение существует. 
Пусть n – целое число (n ≠ –1, 0, 1). Доказывать будем индукцией по |n|. 
Если |n| = 2, то n = ε · 2,  ε =  ± 1. Пусть для всех целых чисел a (a ≠ –1, 0,1), 
|а| < |n|, доказано существование нужного представления. Покажем, что для 
n такое представление тоже возможно. Если |n|  простое число, то, обозначив его |n| = р1, получим n = ±|n| = ± εр1, где ε = ±1. 

Пусть теперь число n составное, |n| > 1, т. е. существует нетривиальный делитель а (а ≠ ±1, а ≠ ± n) числа n. Тогда существует такое целое 
число b, что n = ab, где b ≠ ±1, b ≠ ± n. Поскольку |n| > 1, справедливо равенство для абсолютных величин: |n| = |ab| = |а| · |b| > |а|. 
Аналогично |n| > |b|, поэтому к числам а и b применимо предположение индукции: a = ε1 p1 p2 ... pk, b = ε2 q1 q2 ... ql, где числа pi , qj простые, ε1, 
ε2 =± 1. Произведение a · b дает требуемое представление. Существование 
представления доказано. 
Теперь покажем единственность. Пусть n = ε1 p1 p2 ... pk = ε2 q1 q2 ... ql, 
где числа pi, qj  простые, ε1 = ± 1, ε2 = ± 1. Тогда ε1 = ε2 = – 1 при n < 0. Далее, p1 p2 ... pk, = q1 q2... ql, тогда по свойству 5 простых чисел k = 1 и числа 
q1 q2 ... ql можно перенумеровать так, что p1 = q1,  р2 = q2,…, pk = ql. 
Представление числа n в виде  
 
n = p1
α1 p2 α2 ... ps αs, 
 
гдe ε = ±1, p1, p2,..., ps  различные простые числа, αi, ≥ 1 для i = 1, 2, ..., s, s ≥ 1, 
называется каноническим разложением числа n. 

ВЫЧИСЛЕНИЕ НАИБОЛЬШЕГО ОБЩЕГО ДЕЛИТЕЛЯ 
 
 
Алгоритм Евклида 
 
При работе с большими составными числами их разложение на простые множители, как правило, неизвестно. Но для многих прикладных  задач теории чисел поиск разложения числа на множители является важной, 
часто встречающейся практической  задачей. В теории чисел существует 
сравнительно быстрый способ вычисления НОД двух чисел, который называется алгоритмом Евклида. 
Алгоритм 1. Алгоритм Евклида [3]. 
Вход. Целые числа а, b; 0 < b < а. 
Выход. d = НОД (a,b). 
1. Положить r0 ← a, r1 ← b, i ← 1. 
2. Найти остаток ri+1 от деления ri–1 на ri. 
3. Если ri+1 = 0, то положить d ← ri. В противном случае положить  
i ← i + 1 и вернуться на шаг 2. 
4. Результат: d. 
Теорема. Для любых а, b > 0 алгоритм Евклида останавливается и 
выдаваемое им число d является наибольшим общим делителем чисел а и b. 
Доказательство [3]. По теореме о делении с остатком для любого  
i ≥ 1 имеем ri–1 = qiri + ri+1, где 0 ≤ ri+1 < ri. Получаем монотонно убывающую последовательность неотрицательных целых чисел r1 > r2 > r3> ... ≥ 0, 
ограниченную снизу. Такая последовательность не может быть бесконечной, значит, алгоритм Евклида останавливается. 
 
 
Бинарный алгоритм Евклида 
 
Бинарный алгоритм Евклида вычисления НОД оказывается более 
быстрым [3] при реализации этого алгоритма на компьютере, поскольку 
использует двоичное представление чисел а и b. Бинарный алгоритм Евклида основан на следующих свойствах наибольшего общего делителя 
(считаем, что 0 < b ≤ а): 
1) если оба числа а и b четные, то НОД(a,b) = 2 · НОД(a/2 , b/2)  
2) если число а нечетное, число b четное, то НОД(a, b) = НОД(а, b/2); 
3) если оба числа а и b нечетные, а > b, то НОД(а, b) = НОД(а – b, b); 
4) если а = b, то НОД(а, b) = а. 
 
Алгоритм 2. Бинарный алгоритм Евклида [3]. 
Вход. Целые числа a, b; 0 < b ≤ а. 
Выход. d = HOД(a,b). 
1. Положить g ← 1. 

2. Пока оба числа а и b четные, выполнять а← a/2 , b ← b/2, g ← 2g 
до получения хотя бы одного нечетного значения а или b. 
3. Положить u ← a, v ← b. 
4. Пока u ≠ 0, выполнять следующие действия. 
4.1. Пока u четное, полагать u ← u/2. 
4.2. Пока v четное, полагать v ← v/2. 
4.3. При u ≥ v положить u ← u – v.  
В противном случае положить v ← v – u. 
5. Положить d ← gv. 
6. Результат: d. 
 
 
Расширенный алгоритм Евклида 
 
Расширенный алгоритм Евклида [3] находит наибольший общий делитель d чисел а и b и его линейное представление, т. е. целые числа x и у, 
для которых ах + by = d, и не требует «возврата», как в рассмотренном 
примере. 
Пусть d – НОД для a и b, т. е. d = (a, b), где a  b. Тогда существуют 
такие целые числа x и y, что d = ax + by. Иными словам, НОД двух чисел 
можно представить в виде линейной комбинации этих чисел с целыми коэффициентами. 
Алгоритм 3. Схема расширенного алгоритма Евклида. 
1. Определить a0 = 1, a1 = 0, b0 = 0, b1 = 1,  = a,  = b. 
2. Пусть число q – частное от деления числа a на число b, а число r – 
остаток от деления этих чисел (т. е. a = qb + r). 
3. Если остаток от деления r равен нулю, то выполняем шаг 6. 
4. Определяем:  
a = b; 
b = r; 
t = a0; 
 
// t = xi-1 
a0 = a1; 
a1 = t – a1q; 
// a1 = xi – для правой части = xi+1 для правой 
t = b0; 
 
// t = yi-1 
b0 = b1; 
b1 = t – b1q; 
5. Возвращаемся на шаг 2. 
6. Определяем x = x0, y = y0, d = x + y. 
 
Вариант расширенного алгоритма Евклида 
 
Вход. Целые числа а, b; 0 < b ≤ а. 
Выход: d = НОД(а, b); такие целые числа х, у, что ах + by = d. 
1. Положить r0 ← а, r1 ← b, х0 ← 1, x1 ← 0, у0 ← 0, y1 ← 1, i ← 1