Математические методы в теории защиты информации

В.А. Горбунов 

МАТЕМАТИЧЕСКИЕ 
МЕТОДЫ В ТЕОРИИ 
ЗАЩИТЫ 
ИНФОРМАЦИИ 

-ИИ 

МОСКВА 

ИЗДАТЕЛЬСТВО МОСКОВСКОГО 
ГОСУДАРСТВЕННОГО ГОРНОГО УНИВЕРСИТЕТА 

2004 

УДК 519.48 
ББК 22.1 
Г 67 

Горбунов В.А. 

Математические методы в теории защиты информации. 
— М.: Издательство Московского государственного горного 
университета, 2004. — 82 с: ил. 

ISBN 5-7418-0339-3 

УДК 519.48 
ББК 22.1 

ISBN 5-7418-0339-3 
© В.А. Горбунов, 2004 
© Издательство МГГУ, 2004 
© Дизайн книги. Издательство 
МГГУ, 2004 

ПРЕДИСЛОВИЕ 

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

Широко известная система кодирования RSA использует 
простые числа с количеством знаков более 100. Суть системы 
проста: если два таких числа перемножить, то полученное 
число разложить на множители практически невозможно за 
обозримое количество лет. Если п = p q, где pwq 
простые числа с большим количеством знаков, то сообщение «и» передается открытым ключом, а числа р и q секретные (их знает 
только получатель). 

Для того, чтобы выяснить является ли число с большим 
количеством знаков простым или составным, существуют различные тесты, которые, в основном, используют арифметику 
остатков. 

Практическая польза гипотезы Гольдбаха (которой посвящена глава 2) состоит в том, что по малым простым числам 
можно находить сколь угодно большие простые числа. 

В главе 3 рассматриваются праймориальные последовательности 
чисел, 
то 
есть 
чисел 
вида 
2п = т • р * , 
где 

pi = 2-3-5-рк 
— произведение первых к простых чисел, а 

т-1, 
2,..., 
рк+1-1. 
Эти последовательности являются периодическими (с периодом pi) и с ними связаны некоторые особенности распределения простых чисел. В частности, эти четные числа имеют наибольшее число разбиений в сумму двух 

простых чисел по сравнению с ближайшими четными числами. Каждая последовательность вида р\, 
2 • р\, 
3 • р\, 
. . . , 

[рк+] -1)- pi 
имеет в среднем около 20 простых чисел вида 

т-р\-\ 
или т- pi + 1 , где т = l,2,3,...,p t + 1 - 1 . 

3 

Простые числа в окрестности праймориальных членов последовательностей могут быть записаны в виде п- р*к— pt, где 

pi 
— 
простое число, принадлежащее 
интервалу 
(0; р\), 

Рк
 < Pi < Рк • Используя такое представление простых чисел, 
доказывается теорема о близнецах, следствием которой является вывод: если множество пар простых чисел — близнецов 

(р (;р, +2) ограничено, то гипотеза Гольдбаха неверна и, наоборот, если гипотеза Гольдбаха справедлива, то множество 
пар простых чисел — близнецов неограниченно. 

В главе 4 приводится доказательство великой теоремы 
Ферма, принадлежащее автору. На протяжении более трех 
столетий математики всего мира 
тщетно пытались доказать 
(или опровергнуть) 
эту теорему. Пьер Ферма, 
на 
полях 
«Арифметики» Диофанта — древнегреческого 
математика, 
сделал запись: «Я нашел поистине удивительное доказательство этой теоремы» и тем самым сделал вызов всему математическому сообществу многих поколений (своего доказательства он не оставил). 

Были доказаны частные случаи этой теоремы: «Эйлером 
для и = 3; Дирихле для п = 5; Ламе для п = 7 . Позднее немецкий математик Э. Куммер доказал эту теорему для всех показателей меньших 100. 

С появлением компьютеров справедливость теоремы была 
проверена для п до 4000000, но общего доказательства не было до 1995 года. На основе работ небольшой группы математиков (Фрей, К. Рибет, Тейлор) Э. Уайлс доказал знаменитую 
гипотезу Таниямы-Шимуры о модулярности эллиптических 
кривых. Эта гипотеза часто использовалась при доказательстве теорем в теории чисел, и ее доказательство было крайне необходимо. 

В 1983 году на симпозиуме по теории чисел Фрей сделал 
доклад, в котором привел пример эллиптической кривой, связанной с уравнением Ферма. Он сообщил, что такие кривые 
ведут себя странным образом, если предположить, что теоре
4 

ма Ферма неверна. На основе этого он сделал сенсационный 
вывод: если теорема Ферма неверна, то неверна и гипотеза 
Таниямы-Шимуры и наоборот. В 1995 году Э. Уайлсу удалось 
доказать гипотезу Таниямы-Шимуры и, тем самым, было признано, что теорема Ферма доказана окончательно. 

Надо отметить, что в эллиптических кривых Фрея рассматривались только показатели — простые числа больше 3. 
Считалось, что для четных показателей сам П. Ферма доказал 
теорему (методом бесконечного спуска) и, следовательно, если доказать теорему для всех простых чисел больших 3, то 
теорема будет доказана полностью. 

Такое доказательство теоремы Ферма (косвенное) естественно не устраивало многих математиков и поэтому продолжались попытки доказать эту теорему прямым подходом. 

Как-то, просматривая книгу Ф. Клейна «Элементарная математика с точки зрения высшей». Я наткнулся на историческую справку по поводу теоремы Ферма. Ф. Клейн меня убедил в том, что П. Ферма действительно знал доказательство 
своей теоремы и, следовательно, должен существовать подход, 
позволяющий доказать эту теорему достаточно просто. С этого MOMCfrra, на протяжении нескольких месяцев, я ежедневно 
уделял этой теореме по несколько часов. 

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

Примерно через два месяца я увидел одну «ниточку», с 
которой удалось распутать весь «клубок». Доказательство теоремы Ферма оказалось достаточно простым и проведено было 
в рамках элементарного подхода. 

Центральная идея доказательства состояла в том, что я 
ввел в рассмотрение равномерную сетку с рациональным шагом в единичном квадрате, и надо было доказать, что ни одна 
кривая Ферма не проходит через узловые (рациональные) точки этой сетки для любого натурального числа г, (г > 1). 

Глава 1 написана по материалам книги [1]. 

5 

Глава 1 

КРИПТОСИСТЕМА RSA 

ВВЕДЕНИЕ 

В настоящей главе кратко изложены необходимые сведения из теории чисел, используемые в криптосистеме RSA. В 
конце главы на конкретном примере показано как работает 
система RSA. Эту систему изобрели в 1978 году Ривест, Шамир и Адлеман из Массачусетского технологического института. 

Основными составляющими системы служат два нечетных простых числа, р и q. Обозначим через п произведение 
этих чисел, п = pq. 
Открытый, 
или кодирующий 
ключ этой 
системы — число п (и еще одно число, которое мы введем 
позже). Секретный 
или декодирующий 
ключ состоит, по существу, из чисел р и q. Таким образом, у каждого пользователя 
есть персональная пара простых чисел, которую нужно держать в тайне. Однако произведение этих простых чисел общедоступно. 

Если каждое из простых чисел содержит больше 
100 
цифр, то время и ресурсы, необходимые для разложения числа 
п на множители таковы, что взламывание кода становится 
очень трудным. 

Таким образом, ловушка в системе RSA заключается в 
том, что умножение чисел р и q для получения числа п — простая операция, тогда как обратная задача — разложения числа 
п на множители для получения р и q — практически неразрешима. 

В заключении укажем, что: 
• для реализации системы RSA необходимо иметь два 
больших простых числа р и q\ 

• для кодирования сообщений с помощью RSA мы пользуемся числом п = p q; 

6 

• для декодирования шифровки RSA мы должны знать 
числа р и q; 

• безопасность системы RSA определяется тем, что разложить число п на множители р и q трудно, поскольку 
они очень велики. 

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

ТЕОРЕМА ДЕЛЕНИЯ 

Теорема. Пусть а и b — натуральные числа. Тогда существует единственная пара неотрицательных целых чисел q и г 
таких, что 

a = bq + r, и 
0<r<b. 

Теорема содержит два утверждения про числа q и г. Вопервых, они существуют, во-вторых, они единственны. 

АЛГОРИТМ ЕВКЛИДА 

Алгоритм Евклида предназначен для вычисления наибольшего общего делителя двух натуральных чисел. 

Мы говорим, что целое число Ъ делит целое число а, если 
существует еще одно целое число с такое, что а = Ь • с . В этом 
случае мы говорим, что Ъ является делителем 
или 
множителем числа а , а а, в свою очередь, — кратным числа Ъ. Определить, является ли Ьделителем 
числа а, можно, подсчитать 
остаток от деления а на Ъ и, проверив, равен ли он нулю. 

Пусть а и Ъ — натуральные числа. Наибольший общий 
делитель чисел а и Ъ — это наибольшее целое число d, на 
которое и а и b делятся; тогда мы пишем d = НОД(а,6). Если 
d =1, то мы называем числа а и Ъ взаимно 
простыми. 

7 

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

Наибольший общий делитель можно подсчитать и другим, 
весьма эффективным способом. Евклид приводит его в своих 
«Элементах». 

Алгоритм 
Евклида 
действует 
следующим 
образом. 
Разделим а на Ь с остатком; назовем этот остаток г\. Если 
tj^O, то разделим Ъш. г\ с остатком; пусть 
— остаток 
второго деления. Аналогично, если г2 Ф 0, то разделив 
на 
г2 получим 
новый 
остаток 
г 3. 
Таким 
образом, 
/-й 
цикл 
алгоритма состоит из одного деления с остатком; причем 
делимое равно остатку, полученному в (i-2) — ом цикле, а 
делитель - остатку, полученному в 
— ом цикле. Цикл 
повторяется до тех пор, пока мы не получим нулевого остатка; 
наименьший 
ненулевой 
остаток является наибольшим общим 
делителем чисел а и Ь. 

Пример. а = \2ЪА\ Ь = 54. Деление с остатком выглядит 

так: 

1234 = 54-22 + 46 
54 = 46-1 + 8 
46 = 8-5 + 6 
8 = 6-1 + 2 
6 = 2-3 + 0. 

Последний ненулевой остаток равен 2, поэтому НОД 
(1234; 54) = 2. 

Опишем теперь алгоритм Евклида: 
Ввод: натуральные числа а и Ъ, 
а>Ь. 

8 

Шаг 1. Положить А = а и R = B = b. 
Шаг 2. Заменить значение R остатком от деления А на 
В и перейти к шагу 3. 

Шаг 3. Если R = 0, то сообщить: «наибольший общий 
делитель чисел а и Ъ равен В», и остановиться; в противном 
случае перейти к шагу 4. 

Шаг 4. Заменить значение А на значение В, значение В 
на значение R и возвратиться к шагу 2. 

Таким образом, для вычисления НОД нам необходимо лишь 
выполнить несколько делений с остатком. Но почему наибольший общий делитель совпадает с последним ненулевым остатком 
в последовательности делений? И вообще, почему в последовательности остатков всегда появится нуль? Если бы нуль не 
появлялся, то процедура никогда бы не остановилась. 

Начнем со второго вопроса. Тем самым мы докажем, что 
алгоритм всегда завершает работу. Предположим, что для 
того, чтобы найти НОД чисел а и Ь, мы проделаем следующие 
деления с остатком: 

a = b-q1 + r1 
и 
0< г, <Ъ; 

Ь 
= 
г1-Ъ
 
+ 
Г2
 
и 
0 < г 2 < / ; ; 

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

b>rx >г2 >г3 > . . . > 0 . 

Поскольку между bw нулем есть лишь конечное число целых чисел, последовательность остатков не может продолжаться 
бесконечно. Однако в конце ее может стоять только нуль, а значит, алгоритм наверняка остановится. При применении алгоритма 
Евклида к паре чисел а > Ъ число делений не превосходит b. 

rx = r2-q3 + r3 
r2 = r3-q4 + r4 
и 

и 
0 < г 3 < г 2 
0 < г 4 < г 3 ; 

9 

РАСШИРЕННЫЙ АЛГОРИТМ ЕВКЛИДА 

У алгоритма Евклида есть еще один вариант, 
более 
мощный. Достоинство нового варианта в том, что наибольший 
общий делитель - лишь часть выходных данных. Пусть а и Ъ 
— натуральные числа, ad 
— их НОД, НОД (а, b) = d. 

Расширенный алгоритм Евклида подсчитывает не только d, но 
и два целых числа а и 3 таких, что 

Отметим, что (за исключением тривиальных случаев) если 
а оказывается положительным, то (3 — отрицательным, и 
наоборот. Приводимый здесь вариант расширенного алгоритма Евклида принадлежит Кнуту, автору знаменитой книги 
«Искусство программирования». 

Наибольший общий делитель представляет собой последний ненулевой остаток в последовательности делений. Значит, 
нам надо найти способ записывать последний 
ненулевой 
остаток в виде (4.1). 

Суть алгоритма Кнута в том, что нам не следует ждать, 
пока мы дойдем до последнего ненулевого остатка; вместо 
этого 
нам 
стоит 
записывать 
в таком 
виде 
каждый 
из 
получающихся остатков. 

Предположим, что для вычисления НОД (а, Ь) мы выполнили последовательность делений 

a = bq1+rl 
и 
0 < г, < 6; 

b = rx-q2 + г2 
и 
0 < г2 < гх; 

1 =
 Г2-Яъ

+Гз
 
и 
0 < г 3 < г 2 ; 

a a + fi-b = d. 
(4.1) 

r2 = r3-q, + r4 
и 
0 < r 4 < r 3 ; 

Гп-4 =

Гп-3-Яп-1

+Гп 

г„_3 = г п_ 2-^_ ]+г л. 

' л - 2 

л-1 

л - 2 

и 

и 

и 
0^гя,<гя 

п—1 
л 

о </•„_,</-„. 
гя=0. 

' л - 2 ' 

г л - 3 ' 

10