Необходимый математический аппарат

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

Поэтому было бы неправильно, более того, невозможно обойтись без определенных сведений и приложений из математики. Для начала введем некоторые определения Группой называется множество G с заданной на нем бинарной операцией, которая удовлетворяет следующим условиям 1. Выполняется замкнутость для любой пары a, b G 2. a b c a b c для всех a, b, c G ассоциативность 3. Существует элемент e, называемый нейтральным элементом либо единицей, такой, что a e e a a для любого a G 4. Для любого элемента a G существует элемент b, такой, что a b b a e существование обратного элемента . 4 Кольцом или коммутативным кольцом называется множество R с двумя заданными на нем замкнутыми бинарными операциями и, которые удовлетворяют следующим условиям 1. Существует элемент 0 и 1, называемые нулем и единицей соответственно, такие, что a 0 a 1 a для любого a R 2. Для любого элемента a R существует элемент b, такой, что a b 0 существование аддитивного обратного 3. a b c a b c и a b c a b c для всех a, b, c R ассоциативность 4. a b b a и a b b a для всех a, b R коммутативность 5. a b c a b a c для всех a, b, c R дистрибутивность 4 Полем называется множество K с двумя заданными на нем замкнутыми бинарными операциями и, которые удовлетворяют следующим условиям 1. a b c a b c и a b c a b c для всех a, b, c K ассоциативность 2. a b b a и a b b a для всех a, b K коммутативность 3. a b c a b a c для всех a, b, c K дистрибутивность 4. Существуют элементы 0 и 1, называемые нулем и единицей соответственно, такие, что a 0 a 1 a для любого a K 5. Для любого элемента a K существует элемент b, такой, что a b 0 существование аддитивного обратного 6. Для любого элемента a K, не равного нулю, существует элемент c, такой, что a c 1 существование мультипликативного обратного. 4 Модулярная арифметика.

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

Каждому целому числу отвечает определенный остаток от деления его на m если двум целым a и b отвечает один и тот же остаток r, то они называются равноостаточными по модулю m или сравнимыми по модулю m и записывается это так a bmod m. Сравнимость чисел а и b по модулю m равносильна 1.Возможности представить а в виде аbmt, где t- целое. 2. Делимости а-b на m. 3. Если a bmod m, то a, т b, m. Числа, равноостаточные образуют класс чисел по модулю т. Обозначим через Zт класс, состоящий из т элементов. Zт 0, 1 m1 Из такого определения следует, что всем числам класса отвечает один и тот же остаток r, и мы получим все числа класса, если в форме mqr заставим q пробегать все целые числа.

Соответственно, m различным значениям r имеем m классов чисел по модулю m. Любое число класса называется вычетом по модулю т по отношению ко всем числам того же класса.

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

Если a, т1 и х пробегает полную систему вычетов по модулю т, то ахb, где b-любое целое, тоже пробегает полную систему вычетов по модулю т. Взяв от каждого класса по одному вычету, получим приведенную систему вычетов по модулю т. Любые цm чисел попарно несравнимые по модулю т и взаимно простые с модулем, образуют приведенную систему вычетов по этому модулю.

Если привести обозначения, то это будет выглядить так Zт множество состоящее из элементов Zт, взаимно простых с m. Число элементов в Zт - определяет цт. Эта функция называется функцией Эйлера. Она определяется для всех натуральных т и представляет собою количество чисел от 1 до n взаимно простых с m. П р и м е р ы ц1 1, ц4 2,ц2 1, ц5 4,ц3 2, ц6 2. Несложно показать, что функция Эйлера мультипликативна, то есть, для любых n и m таких, что n, m 1 выполняется цnm цnцm Очевидно, что для простого p выполняются равенства цp p 1,цpn pn1p 1 Если npq, где p и q простые числа, то цп цpqp-1q-1. Эти числа появляются в некоторых алгоритмах с открытым ключом.

Эти свойства позволяют быстро вычислять функцию Эйлера, если известно разложение числа n на простые множители.

Доказывается формула2 цnn1-1 p11-1 ps Теорема Эйлера и малая теорема Ферма. В последние годы основные положения теории чисел стали широко применятся в криптографии. Приведем без доказательств некоторые важные теормы, неоюходимые для понимания дальнейшего материала.

Теорема Эйлер. 2 При n 1 и НОД a, n 1 верно следующее aцn 1 mod n, для любого a Zn При простом n эта теорема превращается в малую теорему Ферма Теорема Ферма. 2 Для любого простого p и любого натурального a верно следующее ap a mod p, для любого a Zp Первообразные корни. Пусть p простое число. Тогда, как известно, Zp является полем. Порядком вычета a 0 называется наименьшее натуральное число m такое, что am 1 mod p Согласно малой теореме Ферма, хотя бы одно такое m существует и равно p1. Теорема.

Для любого простого p существует вычет образующая группы Zp g порядка p1. Такой вычет g называется первообразным корнем по модулю p. Несложно также показать, что таких вычетов существует ровно цp1. Первообразные корни по модулям рб и 2рб. Я приведу, лишь, вспомогательный факт без доказательствa. Но доказательствo есть в 2. Теорема. 2 Пусть с цp и q1, q2, ,qk - различные простые делители числа с. Для того чтобы число g, взаимно простое с т, было первообразным корнем по модулю т, необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений gсq11mod m, gсq21mod m, gсqk1mod m. Введем обозначение Zn, n аддитивная группа вычетов по модулю n, здесь n операция сложения по модулю n. Zn, n мультипликативная группа вычетов по модулю n, здесь n операция умножения по модулю n. Сравнения первой степени.

Рассмотрим следующее соотношение ax b mod m, называемое, сравнением первой степени. Это сравнение имеет столько решений, сколько вычетов полной системы ему удовлетворяет. Но когда х пробегает полную систему вычетов по модулю т, то ах пробегает полную систему вычетов.

Следовательно, при одном и только одном значении х, взятом из полной системы ах будет сравнимо с b. Итак, при а, т1 наше сравнение имеет одно решение. Пусть а, тd, при d 1. Сравнение ax b mod m невозможно, если b не делится на d. При b, кратном d, сравнение имеет d решений. Модулярная арифметика основывается на так называемой Китайской теореме об остатках КТО. Около 100 г. до н. э. китайский математик Сун Цу Sun-Tsu решил такую задачу найти число, дающее при делении на 3, 5, 7, остатки 2, 3, 2 соответственно.

Китайская теорема об остатках. Пусть n n1n2nk. Причем числа n1, n2 nk попарно взаимно просты. Рассмотрим соответствие a - a1, a2 ak, где ai остаток от деления a на ni. Тогда оно задает взаимно однозначное соответствие между классом Zn и декартовым произведением Zn1Ч Ч Znk. При этом операция сложения, вычитания и умножения в Zn соответствуют покомпонентные операции над к-элементными кортежами если a - a1, a2 ak и b - b1,b2 bk, то ab mod n - a1 b1 mod n1 ak bk mod nk a-b mod n - a1- b1 mod n1 ak- bk mod nk ab mod n - a1 b1 mod n1 ak bk mod nk. Рассмотрим систему сравнений x b1mod m1, x b2mod m2 x bkmod mk. Решить эту систему, т.е. найти все значения х, ей удовлетворяющие, можно, применяя следующее утверждение 2 Пусть числа Ms и Ms определены из условий m1m2 mk Msmk, Ms Ms 1 mod ms, и пусть х0 M1 M1 b1 M2 M2 b2 Mк Mк bк. Тогда совокупность значений х, удовлетворяющих системе определяются сравнением x х0 mod m1m2 mk. П р и м е р Решим систему x 2mod 3, x 3mod 5, x 5mod 11. Здесь 35115533351511165, причем 551 1mod 3, 332 1mod 5, 153 1mod 11. Поэтому х0 5512332315311, и, следовательно, совокупность значений х, удовлетвряющих системе x 2mod 3, x 3mod 5, x 5mod 11, будет x 110 198225533 38mod 165. О дискретном логарифме.

Пусть g является образующей группы Zn, тогда для всякого a Zp найдется z, для которого gz amod n. Такое z называется дискретным логарифмом.

Теоремао дискретном логарифме. Пусть g является вычетом.

Тогда сравнение gx gymod p равносильно сравнению x y mod цp. Целые числа a и b являются взаимно простыми, если НОДa, b1 Теорема. Если НОДa, p1 и НОД b, p1,то НОДаb, p1 для любых простых чисел а, b,p. Алгоритм вычисления ad mod m. Как мы знаем, вычисление ad mod m при достаточно большом а, довольно таки, трудоемкое занятие. Я даже не говорю о буковке d, точнее о том, какие значения она принимает. Таким образом, чтобы облегчить это вычисления мы приведем алгоритм. 1. Представим d в двоичной системе счисления d d0 2r dr-12 dr, где di-цифры в двоичном представлении равны 0 или 1, d01. 2. Положим а0а и затем для i1 r вычислим аi a2i-1adi mod m 3. аr есть искомый вычет admod m. сложность алгоритма 0ln m П р и м е р Найдем 57207mod 3313 a057, d207272623222120. Таким образом, d01 d11 d20 d30 d41 d51 d61 d71 а157257 mod 3313 2978 а229782 mod 3313 2896 а328962 mod 3313 1613 а41613257 mod 3313 1014 а51014257 mod 3313 202 а6202257 mod 3313 102 а7102257 mod 3313 1 Т.о. 57207mod 3313 1. Разложение на простые множители.

Теорема.

Если простое число p делит произведение двух целых чисел а и b, то pa или pb. Теорема существование и единственность разложения. Всякое составное число а p1 E1p2 E2 prEr, где p1 p2 pr -простые числа, а Ei- положительные целые числа. Теорема рекуррентная формула для НОД. Пусть а целое неотрицательное число, а b- целое положительное число.

Тогда НОДa, bНОДb, а mod b. Расширенный алгоритм Евклида. Немного дополнив известный алгоритм нахождения НОД двух натуральных чисел, можно получить с его помощью коэффициенты х и у, для которых НОДa, bахby1, при a, b1.Итак, этот алгоритм используется для решения уравнения ax 1mod b или bу 1mod a, при a, b1. Определим матрицу 1. Вычислим остаток r от деления числа a на b, abqr,0r b. 2. Если r0, то второй столбец матрицы Е дает вектор решений уравнения 3. Если r0, то заменим матрицу Е матрицей 4. Заменим пару чисел a, b парой b, r и перейдем к шагу 1. Сравнения второй степени.

Рассмотрим сравнение х2 а mod р, при a, р 1. 1 Если 1 имеет решение, то а называется квадратичным вычетом по модулю т. В противном случае а называется квадратичным невычетом по модулю р. Несложно показать, что если а-квадратичный вычет, то данное сравнение имеет два решения. Действительно, если а- квадратичный вычет по модулю р, то сравнение 1 имеет, по крайней мере, одно решение х х1 mod р. Но тогда, ввиду-х12 х12, то же сравнение имеет и второе решение х -х1 mod р. Это второе решение отлично от первого, т.к. из х1 х1 mod р мы имели бы х1 0 mod р, что невозможно, ввиду 2,рх1,р1. Приведенная система вычетов по модулю р состоит из р-12 квадратичных вычетов, сравнимых с числами 12,22 р-122 и р-12 квадратичных невычетов.

О символе Лежандра Рассмотрим La, p, называемый символом Лежандра, с помощью, которого можно определить, является ли а квадратичным вычетом по модулю р для простого р. Вычислить символ Лежандра La, p и определить является ли а квадратичным вычетом, либо не является позволяет следующее утверждение Теоремакритерий Эйлера.

При а, не делящемся на р, имеем ap-12 La, pmod p. Итак, символ Лежандра определяется следущим образом La, p0, если а делится на р. La, p1,если а-квадратичный вычет по модулю р. La, p-1,если а-квадратичный невычет по модулю р. La, p можно рассчитать следующим образом La, p ap-12 mod p. Или можно воспользоваться следующим алгоритмом 1. Если а1, то La, p1. 2. Если а четно, то La, p La2,p-1 p-18 3. Если а нечетно и1, то La, p Lр mod a, p-1q-1p-14 О символе Якоби Ja, р Символ Якоби Ja, р представляет собой обобщение символа Лежандра на составные модули, он определяется для любого целого а и любого нечетного р. Ja, р определен только, если р нечетно.

J0,р 0 Если p простое число, то 1 Ja, p 0, если a делится на p 2 Ja, p1, если a - квадратичный вычет по модулю p 3 Ja, p-1, если a - квадратичный невычет по модулю p Если p составное число, то Ja, р Ja, p1 Ja, p2 Ja, pm, где p1 pm простые множители все p. Правило 1 J1,р1 Правило 2 Jab, р Ja, р Jb, р Правило 3 J2,p1, если p2 -18 четно и J2,p-1, если p2 -18 нечетно Правило 4 Ja, p Ja mod p, p Правило 5 Ja, b1 b2 Ja, b1 Ja, b2 Правило 6 Если НОДa, b1 и a и b нечетны, то Ja, bJb, a, если a-1b-14 четно, Ja, b-Jb, a, если a-1b-14 нечетно.

П р и м е р Вычислим J21,109 По правилу 2 имеем J21,109J37,109 J3,109 J7,109 По правилу 6 имеем НОД3,1091, НОД7,109 и 3 и 7 и 109 нечетны, тогда 2108454, то J3,109 J109,3 61084162, то J7,109 J109,7 По правилу 4 имеем J109 mod 3,3 J1,31 J109 mod 7,3 J4,7 По правилу 2 J4,7 J2,7 J2,7 По правилу 3 72 -186 - четно, то J2,71 Получаем, что J21,109 J1,3J2,7 J2,71. Итак, 21 является квадратичным вычетом.

Проверка чисел на простоту. Тест Соловея-Штрассена. Для проверки простоты числа p в этом алгоритме используется символ Якоби. p нечетное, большое число 1. Выберите случайное число a, меньше р. 2. Если НОДa, p 1, то р - составное число и не проходит тест. 3. Вычислите j ap-12 mod p. 4. Вычислите символ Якоби Ja, p. 5. Если j Ja, p,то число р определенно не простое. a-свидетель 6. Если j Ja, p,то вероятность того, что число р не является простым и не превышает. Повторить эту процедуру t раз. 5 П р и м е р Пусть требуется проверить на простоту число 109. 1. Выберем случайно а21. 2. НОДа, рНОД21,1091 вычисляем по алгоритму Евклида. 3. Вычисляем j ap-12 mod p 2154 mod 1091 вычисляем по быстрому алгоритму ad mod m. 4. Вычисляем символ Якоби Ja, р J21,1091это мы уже вычислили, можно посмотреть выше. 5. jJ21,1091, число а21 прошло тест. 1. Теперь выберем случайно а49. 2. НОДа, рНОД49,1091вычисляем по алгоритму Евклида. 3. Вычисляем j4954mod 1091 вычисляем по быстрому алгоритму. 4. Вычисляем символ Якоби Ja, р J49,1091. 5. jJ49,1091, число а49 прошло тест. 1. Выберем случайно а9. 2. НОДа, рНОД9,1091 вычисляем по алгоритму Евклида. 3. Вычисляем j ap-12 mod p 954 mod 1091 4. Вычисляем символ Якоби Ja, р J9,1091 5. jJ9,1091, число а21 прошло тест. Числа Кармайкла.

Неподходящими для теста Соловея-Штрассена являются так называемые числа Кармайкла.

Они обладают следующим свойством для любого a такого, что НОДa, p 1 верно an1 1 mod n Первые три числа Кармайкла таковы 561, 1105, 1729. Среди первых 10 чисел их всего 255. Лишь недавно 1994 г. было доказано, что таких чисел бесконечно много. 5 Тест Миллера-Рабина.

Вычислить b-число делений p-1 на 2 т.е. 2b это наибольшая степень числа 2, на которую делится p-1. Вычислить m, такое, что p12b m, m-нечетно. 1. Выберите случайное число а, меньшее р. 2. Установите j0 и z am mod p. 3. Если z1 или если zp-1, то p проходит тест и может быть простым числом. 4. Если j 0 и z1,то р не относится к простым числам. 5. Установите jj1. Если j b и zp-1,установите z z 2 mod p и вернитесь на этап 4. Если zp-1, то p проходит тест и может быть простым числом. 6. Если jb и zp-1, то р не относится к простым числам.

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

Гарантируется, что возможных значений а окажутся свидетелями. Это означает, что составное число ошибочно пройдет t тестов с вероятностью не более t, где t число итераций. Для большинства случайных чисел свидетелями служат около 99,9 возможных значений а. 5 Если р-простое число, p-12b m, m-нечетно, то согласно малой теореме Ферма для каждого а, такого, что а, р1 хотя бы одна из скобок в произведении am-1am1 a2m1 a2bm1 ap-1-1 делится на p.5 П р и м е р ы 1 Проверим, является ли число 2031 простым.

Итак, 203021015 т.о. b1 m1015 1. Выберем случайное a, a p а43 2. Установим j0 и z 431015 mod 20311406. 3. z1, z2030. 4. j 0 нет. 5. j1 j b нет, т.к. j1 6. j1 и z2030 Не является простым числом действительно, 20316773. 2 Проверим, является ли 109-1108 1082227 b2 m27. 1. Выберем случайное a15 2. Установим j0 и z1727 mod 1091 3. z1, то р109 проходит тест и может быть простым. 4.