Материалы лекций Математические основы криптологии

 

В.М. Захаров

Материалы лекций

Математические основы криптологии

 

 

Лекция№1

  Криптология состоит из двух направлений: криптографии и криптоанализа.  

Симметричное шифрование

 

 

Кс

 

 

А, М В

 

х

С

Ек(М) Dк(С)

 

Кр

 

А – источник информации

В – получатель

М – сообщение, открытый текст

С – шифрованный текст

Ек(М) – некая функция шифрования

Dк(С) – функция расшифрования

Кр – криптоаналитик

Кс – секретный ключ

Зная С, Dк(С), Ек(М) на основе некоторой функции ψ(С) = (Х, Кс)

получаем сообщение.

Для шифрования различных сообщений необходимо использовать различные ключи, поэтому у стороны А должна быть целая система ключей

А{Кс,Ек}.

 

Асимметричное шифрование.

  Алгоритм RSA (Revest, Shamir, Adelman) 1978г. e, n

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

криптографии – появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами. Здесь отправной точкой принято… Мартином Хеллманом в 1976г. под названием «Новые направления в современной… У. Диффи и М. Хеллман предложили для создания криптографических систем с открытым ключом функцию дискретного…

Делимость целых чисел.

Лекция№2

 

Элементы теории чисел

 

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

Основная теорема арифметики:

 

Пусть заданно два натуральных числа a и b и b<a, тогда справедливо утверждение о aможно представить как a= b*q+r, где r- остаток, может быть равен 0, а может быть и не равен.

Если r 0, то q – не полное частное, а если r=0, то q –полное частное.

 

b – Делитель a.Краткая запись:(b|a)– b делит a без остатка.

 

 

Алгоритм Евклида

Алгоритм Евклида дает правило вычисления наибольшего общего делителя   (НОД) 2-х натуральных чисел. (a,b)= d , где d – НОД НОК – наименьшее общее кратное

Ax+by=d

 

Дополнительно вычисляются коэффициенты x,y

 

Пример: a=1234, b= 54

 

2=8-6*1=8-(46-8*5)=6*8-46=-6(54-46*1)-46 = 6*54-6*46-46=6*54-7*46=6*54-

 

7*(1234-54*22)=6*54-7*1234 x=7; y= 160

Алгоритм РАЕ Кнута

   

Лекция№3

 

Свойства делимости целых чисел

Два числа a и b называются взаимно простыми если их НОД = 1   (a1,a2,….,an)= НОД

Свойства делимости целых чисел

Свойства приведены без доказательства.   1)Свойство дистрибутивности

Простые числа

1)- каноническое разложение   2)минимальный делитель числа m (m- целое) является простым числом. Это свойство является прямым следствием из главной…

Плотность появления простых чисел на заданном интервале падает с увеличением N.

Н-р: при N=10 у нас 4 простых числа (от 1 до 10) (40%)

 

при N=100 имеем 25 чисел (1 до 100) ( 25%)

 

при N=1000 около 13%

 

И так далее плотность убывает. Тем не менее интервалы расположение таких чисел совершенно не предсказуемы . Есть числа расположенные близко к друг другу (5,7; 11,13; 13,19 – простые числа близнецы). Причем до сих пор не доказано бесконечно ли число близнецов или нет.

Допустим задан интервал и мы хотим оценить плотность в заданном интервале (от 1 до N). Плотность определяется по формуле : - асимптотическая плотность. Это отношение начинает хорошо проявляться

при больших N. С ростом N эта величина растет.

 

Зафиксируем некоторый интервал на оси от 1 до N. потом прибавим некоторое . И вот в зависимости от величины существуют оценки, сколько простых чисел в интервале N+ . Проблема заключалось в том чтобы узнать величину этого интервала чтобы в нем находилось хотя бы одно простое число. Еще в 18 веке была получена (потом она конечно уточнялась). На сегодняшний день эта имеет величину

N N - на этом интервале гарантированно есть хотя бы одно

 

 

простое число.

 

Это свойство тоже является не последним по важности для криптоаналитиков.

В попытках открыть закономерность расположения простых чисел ученные выяснили седующие:

Допустим мы имеем простое число 11 оно состоит из двух единиц. рассмотрим простые числа построенные из единиц. Выясним какое ближайшее простое число состоит тоже только из единиц. 111 – не простое

 

число. 1111- тоже не простое. Числа составленные из трех до восемнадцати единиц не являются простыми. А вот число 1111111111111111111 – простое (состоит из 19 единиц). Это так называемое второе простое число.

Третье это - 11111111111111111111111 (23 единицы).

 

А вот четвертое простое число до сих пор ищется. Уже перебрали числа состоящие из 70 единиц но пока не нашли простого числа.

Т.е имеются определенные «сгустки» простых чисел на оси которые дают интересные формулы,

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

Одна из проблемных задач которой занимались начиная с Ферма, позднее

 

Эйлер, Гаусс ….

 

как раскладывать составное число. Допустим школьный метод проб. Проверяем сначала делится ли на 2,3….. Он не используется в шифрование из за своей очевидности.

Пример:

 

исходя из этого числа нам нужно перебрать все делители, чтобы

 

последний был

 

– если мы не нашли делителей до этого числа то простое. Но чтобы найти делители в этом интервале ( на среднем компьютере) нам понадобится 1040секунд. 108 – то примерное количество секунд в одном годе. т.е. понадобится 1032 лет чтобы найти все делители.

Для справки: Большой Взрыв, приведший к зарождению вселенной, произошел примерно 1011 лет тому назад. Даже если мы возьмем 1000

000 000 компьютеров то нам понадобится 1025 лет.

 

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

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

 

пытаемся их найти. Еще Ферма предложил определенный алгоритм. Мы рассмотрим его модификацию чуть позже. Он предназначен для случаев когда число m имеет хотя бы один небольшой делитель. Не больше чем корень из N.

Составные числа могут иметь запись не только в виде канонического разложения, но и в виде определенной формулы. Например: простейший полином (один из интереснейших в современной криптографии). Дано некоторое число, причем не известно какое оно простое или составное.

и оно имеет в запись вид:

 

– полином степени n, где в качестве х выступает 2-ка.

 

Если n нечетное, но составное тогда число m тоже составное. Но если n нечетное, но простое , то при некоторых простых n число m составное, а при некоторых простое. Т.е, или/или. Начиная с 17 века эта формула изучается.

В криптографии это один из простых способов получения простых чисел. Берем большое n – простое, и потом тестируем , полученное m может оказаться или простым или составным. Простые числа получаемые при n простых расположены на оси редкими группами. Впервые эту закономерность начал изучать Мерсен (18 век). Он начал подставлять в n

2,3,5,7…. и получил ряд чисел (до тех пор пока ему было легко это делать на бумаге). Так он дошел до n=257, но он ошибся , 257 – не простое число. Подставляя, он получил ряд(причем в нем он допустил ряд ошибок), который выглядит следующим образом:

n= 2,3,5,7,13,17,19,31,67,127,157 т.е. те простые числа, при подстановке которых в формулу получаем простое число.

Ошибки;

 

- составное

 

-составное

 

он пропустил числа 41,47,61,89 и надо убрать 67 и 257. Самое большое простое число найдено при n = 3021377

 

само это простое число, содержит 1819050 десятичных знаков. Способы возведение в большую степень рассмотрим позже.

 

 

Ферма выдвинул предположение, что число - является простым. Но при k =5 – число получается составное. А при k=0,1,2,3,4 . И до сих пор не найдено простого числа после k=5.

Предыдущие формулы являлись экспоненциальными , но существует еще одна интересная формула:

Праимориальная формула. Из школы нам известно понятие факториал . Он определяется как 1*2*3*4*…..*N. А прамориал - берется простое число p и на основе его составляется прамориальная формула такого типа: произведение простых сомножителей до p(включая p). 2*3*5*7*…*p. прамориал обозначается - p#.

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

 

Лекция№4

 

Получение простых чисел.

По мере того как мы будем изучать курс «Математические основы криптологии» мы будем возвращаться к этой теме. Задача получение простых чисел во многом зависит от того как ставить эту… Методы:

Решето Эратосфена

 

Решето Эратосфена - это древнейший способ поиска простых чисел. В отличие от других методов, он не использует специальных функций.

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

В названии алгоритма звучит слово "решето" потому, что он позволяет из ряда нечетных натуральных чисел "просеивать" составные числа, а простые - "задерживать". Четные числа не используются, так как все они, кроме 2, составные.

Цель алгоритма - определить все положительные простые числа, меньшие некоторой верхней границы п, где nÎN. Вначале выписываются все нечетные целые между 3 и n.

Далее ряд просеивается. Первое число в нем 3. Вычеркиваются из списка все числа, кратные трем и большие трех. Теперь выбирается наименьшее число из списка, превосходящее 3, которое еще не было вычеркнуто - число 5. Вычеркивается каждое число из списка, кратное пяти и большее пяти. Эта процедура продолжается до тех пор, пока не будут рассмотрены все числа до п.

 

При вычеркивании чисел, кратных р, отсчет начинается с числа р+2, и том случае, если р+2 было вычеркнуто на предыдущих шагах алгоритма.

Пример 1.3. Для п = 41 список нечетных чисел следующий:

 

3 5 7 9 11 13 15 17 19 21

 

23 25 27 29 31 33 35 37 39 41

 

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

 

3 5 7 9 11 13 15 17 19 21

 

23 25 27 29 31 33 35 37 39 41

 

Теперь вычеркиваем числа, кратные пяти и начиная с семи, что

 

Дает

 

3 5 7 9 11 13 15 17 19 21

 

23 25 27 29 31 33 35 37 39 41

 

Далее, ни одно из чисел, оставшихся в списке, не будет вычеркнуто

 

На следующих этапах просеивания. Таким образом, положительные нечетные простые числа, не превосходящие 41, это

3 5 7 11 13 17 19 23 29 31 37 41.

 

Можно отметить следующие замечания к алгоритму "решето

 

Эратосфена".

 

1. Некоторые числа вычеркиваются больше, чем один раз.

 

2. Хотя процесс вычеркивания повторяется вплоть до граничного числа

 

п, но все составные числа вычеркиваются раньше достижения этой границы.

 

В модифицированном алгоритме сделаны следующие изменения.

 

1. Простейшее усовершенствование - это начинать процесс вычеркивания не с числа р + 2, а с наименьшего кратного р числа, которое не делится на простое число, меньшее р. Найдем его.

Положительные числа, кратные р, записываются в виде kр, где k - натуральное. Если k < р, то kр делится на число, меньшее р, а именно на k. Но все числа, меньшие p, уже были в алгоритме рассмотрены ранее. Значит, k = p и первое кратное р число, которое не делится на простое, меньшее р число, есть р2.

 

Таким образом, достаточно вычеркивать все числа, кратные р, начиная с р2. Однако все равно будут оставаться числа, которые будут вычеркиваться более одного раза.

2. Можно закончить просеивание раньше n-го шага. Пусть вычеркивается каждое р−ое число. Из пункта 1 следует, что первое число, подлежащее вычеркиванию, равно р2. Но если р2 > п, то такого числа нет в

списке. Тогда приемлемым является диапазон р2 ≤ п Þ p Î[− n ; n ] и pÎN

 

Þ p Î[1; n ].

 

В итоге, необходимо вычеркивать каждое р-ое до тех пор, пока р≤] n [ (если число заключается в квадратные скобки, то данное число округляется к наименьшему целому). В примере, разобранном выше, ] 41 [ = 6. Поэтому

отбрасывание чисел, кратных 3 и 5, было достаточно для вычеркивания всех

 

составных чисел из списка.

 

Так как вычеркиваются все нечетные числа в диапазоне

3, n , то можно

 

использовать вектор V признаков "зачеркнутости" чисел. Для хранения признака "зачеркивания" одного числа требуется 1 бит информации: два возможных значения - 1 или 0, не вычеркнуто или вычеркнуто. Вектор V состоит из (n-1)/2 ячеек, по одной для каждого нечетного целого числа 2j + 1.

Инициализация вектора V заключается в проставлении единицы во всех ячейках. При вычеркивании некоторого числа p (число помечается как составное) в ячейку с индексом (p−3)/2 вектора V записывается 0 (первая ячейка вектора имеет индекс 0).

Модифицированное "решето Эратосфена" имеет следующие

 

особенности:

 

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

2. Не хранятся четные числа.

 

3. Зачеркиваются все кратные числа для чисел из диапазона

"p = 3, n .

 

4. Для текущего выбранного числа p, для которого будут вычеркиваться все кратные ему числа, процесс вычеркивания будет начинаться не с p+2, а с p2, с шагом 2p (так как не учитываются четные числа).

Модифицированное "решето Эратосфена" имеет следующие

 

недостатки:

 

1. Оно неэффективно при поиске очень больших простых чисел. Такой поиск невыполним, если граница слишком велика.

2. Для работы алгоритма требуется большой объем компьютерной памяти для больших чисел.

Алгоритм работы.

 

Представим алгоритм работы модифицированного "решета

 

Эратосфена".

 

Пусть число p задается в векторе V под индексом (p-3)/2, а отсчет в массиве начинается с нуля (нулевой элемент V задает флаг простоты числа

3).

 

1. Ввод числа n, до которого включительно надо найти простые числа.

 

2. Если n<2, то выход.

 

3. Если n=2, то вывод простого числа 2, выход.

 

4. Вычисление размера памяти под вектор V: size=(n-1)/2 бит (можно задавать массив статичного размера; тогда необходимо проверять, что размер size, требуемый под вектор V, не больше размера данного массива).

5. Выделение памяти под вектор размера size, установка в каждой ячейке значения 1 (флага, что соответствующее число не вычеркнуто).

6. Если память не была выделена, то был запрошен слишком большой

 

блок данных, выход.

 

7. Для

"p =3,

n (данную конструкцию лучше реализовать с помощью

 

оператора цикла с предусловием, наподобие while):

 

7.а. Если для данного числа p значение в векторе не нулевое (элемент под индексом (p−3)/2): V[(p−3)/2] ≠ 0, то

 

 

7.а.1.Для

"t =

p 2 , n

(данную конструкцию лучше реализовать с

 

помощью оператора цикла с предусловием, наподобие while),

 

7.а.1.1. Если для текущего числа t соответствующее значение в векторе не равно нулю: V[(t-3)/2] ≠ 0, то значение в ячейке заменяем на 0 (вычеркиваем число t).

7.а.1.2. Увеличиваем число t на 2? p.

 

7.б. Увеличить счетчик p на 2. Перейти к пункту 7.

 

8. Вывод простых чисел, задаваемых ячейками вектора, в которых значения не нулевые.

8.а. Вывод числа 2.

 

8.б. Для "t = 0, size - 1: если V[t] ≠ 0, то выводим число 2? t+3.

 

9. Выход.

 

 

Пример работы вышеописанного алгоритма.

 

Найдем множество простых чисел до числа n = 41 включительно с помощью модифицированного "решета Эратосфена".

Размер ячеек вектора V равен size = (n-1)/2 = 20.

 

Шаги работы алгоритма представлены в трассировочной табл. 1.3.

 

Таблица 1.3. Трассировочная таблица

Шаг,p	p≤n ?	V[(p-3)/2]≠0	Шаг,t	t≤n?	V[(t-3)/2]≠0	t=t+2?p	p=p+2
	да: 3≤6	Да: V[0]≠0		да: 9≤41	да: V[3]≠0	15← 9+2×3
				да: 15≤41	да: V[6]≠0	21← 15+2×3
				да: 21≤41	да: V[9]≠0	27← 21+2×3
				да: 27≤41	да: V[12]≠0	33← 27+2×3
				да: 33≤41	да: V[15]≠0	39← 33+2×3
				да: 39≤41	да: V[18]≠0	45← 39+2×3
				нет:45>41			5←3+2
	да: 5≤6	Да: V[1]≠0		да: 25≤41	да: V[11]≠0	35← 25+2×5
				да: 35≤41	да: V[16]≠0	45← 35+2×5
				нет:45>41			7←5+2
	нет: 7>6

 

При выписывании результатов получаем следующий ряд простых

 

чисел:

 

3 5 7 11 13 17 19 23 29 31 37 41.

 

 

Вопросы для самопроверки.

 

1. Для чего предназначено решето Эратосфена?

 

2. Поясните работу алгоритма "решето Эратосфена".

 

3. Какие изменения происходят в модификации решета Эратосфена?

 

4. До какой границы производится проверка числа n на простоту в модифицированном решете Эратосфена?

5. Поясните работу модифицированного решета Эратосфена.

 

6. Какими особенностями обладает модифицированное решето Эратосфена?

 

7. Какими ограничениями по использованию обладает модифицированное решето

 

Эратосфена?

 

8. Какие ограничения накладываются на входные значения алгоритма?

 

9. Для чего нужен вектор V?

 

Проверка простоты чисел Мерсенна

Числами Мерсенна называются числа вида М(p) = 2p - 1, pÎN.   Задача для чисел Мерсенна - поиск в ряду этих чисел простых.

Тест Люка - Лемера

 

Тест создает последовательность натуральных чисел: S0, S1, S2, ..., Sp-2

 

k

,определяемую рекуррентной формулой Sk+1 = S2

 

- 2, где So

 

= 4. Пусть р -

простое число. Число Мерсенна М(р) является простым тогда и только тогда, когда

 

Sp-2 mod M(p) ≡ 0, т.е. остаток равен 0.

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

ЛЕКЦИЯ 5

 

Алгоритмы факторизации

 

Разложение чисел на 2 простых сомножителя

 

Пусть N - множество натуральных чисел и все операции производятся

 

над целыми числами. Формула

i =r , k

будет определять ряд целых чисел,

 

лежащих в диапазоне от r до k включительно, значения из которого может принимать переменная i. ]k[ - взятие от дробного числа k только целой части,

без округления.

 

Алгоритм Бухштаба

Данный алгоритм приведен из книги Бухштаба А.А. "Теория чисел" [4]. Пусть задано натуральное нечетное число n, n ≥ 9, которое… возрастания: для вычисления Ns к Ns−1 прибавляется число (2s-1).  

Алгоритм Ферма

Алгоритм Ферма похож на алгоритм Бухштаба и является эффективным, если у раскладываемого числа n есть делитель (который может и не быть простым числом), незначительно превосходящий n .  

Лекция № 6

 

Числовые функции

 

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

 

Функция Эйлера

Имеется целое, положительное число m. Оно может быть как составным, так и простым. Функцию Эйлера принято обозначать, практически во всех учебниках как:  

Берем число a, возводим в , берем модуль от т.е. остаток будет равен всегда единице.

Частный случай: m- простое(p), то:

 

 

 

Это теорема малая теорема Ферма.

 

Допустим если авне диапазона (a>m),

 

если а и m – взаимно просты то будет справедливо и для этого случая.

 

А если m – простое(р), то ане должно делится на р. Т.е. если а делится на р, то это уже не соответствует определению взаимно простых чисел.

 

 

Мультипликативная функция

Имеем два натуральных числа a и b, если они взаимно просты, то мультипликативная функция устанавливает число взаимно простых чисел, для произведение…  

Функция Мебиуса

 

Функция Мебиуса служит характеристикой канонического разложения.

 

? (d) – обозначение

 

Характеристики канонического разложения :

 

1) кратность

 

2)четность

 

3)нечетность

 

(число сомножителей может быть четным или нечетным)

 

Функция Мебиуса и отражает эти характеристики, она принимает три значения: 0, 1, -1.

 

 

1, при d=1,

 

? (d)= (-1)к, если d произведение к простых чисел,

 

Если d делится на квадрат некоторого ростого числа.

 

Если хотя бы один сомножитель является кратным, то Функция

 

Мебиуса принимает значение 0.

 

Если число членов четное, то Функция Мебиуса принимает значение 1

 

Если число членов нечетное, то Функция Мебиуса принимает значение

 

-1.

 

Причем характеристика кратность имеет больший приоритет. Т.е. если кратное и нечетное, то ? (d) =0.

Пример.

 

? (1)=1

 

? (2)=1

 

? (3)=-1

 

? (4)=0

 

? (5)=-1

 

? (6)=1

 

…….

 

На основе Функции Мебиуса можно найти Функцию Эйлера (третья формула).

Эта так называемая связь Функции Мебиуса и Функции Эйлера.

 

III) , суммирование выполняется по всем делителям di|m.

 

Задано число m

 

1) находим все делители di|m

 

2) находим числа

 

 

делителя.

3) - находим функцию Мебиуса для каждого значения

 

В конце мы и получаем значение функции Эйлера. Пример: m=18

1) di=1,2,3,6,9,18

 

2) числа = 18, 9, 6, 2, 1

 

3) = 1, (-1), (-1), (-1), (1), 0, 0

 

Витогеполучаем:

 

Числовая функция

Это функция устанавливающая целую часть от некоторого рационального числа [a] – обозначение  

Лекция №7

 

 

Возведение натуральных чисел по модулю в большие степени

 

 

Приложение функций Эйлера

Для возведение натуральных чисел по модулю в большие степени

  Функция Эйлера может быть использована для возведение больших чисел в большую…  

Здесь сомножитель (2435272*12)mod13 по теореме Эйлера равен 1.

 

Рассмотрим общий случай

Сначала нужно вычислить значение функции Эйлера для числа m

(aj( m ) ) mod m

а=317

x=259

m=15, ф(15)=8

(317259 )mod15 ºy

x=259=8*32 +3

 

Вычисляем:(а8*32+3)mod15=(а8*32)mod15(а3)mod15=

(3173 mod15) º 23 mod15 = 8

Ответ: 8

Учитываем, что сомножитель (а8*32)mod15 и 317mod15=2.

 

 

Возведение натуральных чисел по модулю в большие степени по схеме Горнера

  y = a x mod m , (1.1)  

Лекция 8

 

 

Сравнимость по модулю. Модулярная арифметика

  Понятие «модулярная арифметика» ввел немецкий ученый Гаусс.  

Свойства операций сравнения

  В криптографии существуют шифры и по простому модулю и по составному модулю. …  

Теорема Эйлера

Приложение свойств

 

aj ( m )

 

≡ 1 mod m

 

a и m должны быть взаимнопростыми. (a,m)=1

 

Доказательство теоремы Эйлера

Пусть даны m и φ(m)=k   Имеем число a, причем (a,m)=1

Классы вычетов

 

Сравнимость по mod п является отношением эквивалентности на множестве

 

Z целых чисел.

 

Классами эквивалентности, называемыми классами вычетов по mod п,

 

являются следующие множества - разбиения Z :

 

[О] = {..., -2п, -п, О, п, 2п, ...},

 

[1]= {..., -2п+l, -п+l, 1, п+l, 2п+l, ...},

 

…

 

[п-l]={..., -п-l, -1, п-l, 2п-l, 3п-l, ...}.

 

Замечание. Класс чисел, сравнимых с а по модулю п, совпадает с линейной функцией а + nt при t = 0, ±1, ±2,…

.

Пример 1.3.Определим классы вычетов по mod 7:

 

 

[0]= {..., -14, -7, 0, 7, 14, 21, ...}, [1]= {..., -13, -6, 1, 8, 15, 22, ...}, [2]= {..., -12, -5, 2, 9, 16, 23, ...}, [3]= {..., -11, -4, 3,10,17, 24, ...}, [4] ={..., -10, -3, 4, 11, 18, 25, ...}, [5] ={..., -9, -2, 5, 12, 19, 26, ...}, [6] ={..., -8, -1, 6, 13, 20, 27, ...}.

 

 

Число классов вычетов совпадает со значением модуля

Число чисел в классе бесконечно.

В каждом классе свои числа – они больше нигде не встречаются –

пересечений нет.

 

Полная система вычетов – когда из любого класса берется по одному представителю.

Приведенная система вычетов – система, состоящая из взаимнопростых вычетов.

 

 

Лекция 9

Модулярная арифметика (продолжение) Квадратичные вычеты Степенные вычеты

Продолжим исследовать вычеты. Широкое применение в криптографии нашла формула: xn ≡ a mod m, n=2

Лекция 10

Общая алгебра

 

 

ЭЛЕМЕНТЫ ТЕОРИИ КОНЕЧНОГО ПОЛЯ Простейшие алгебраические структуры

Под алгебраической структурой будем понимать некоторое множество   S с одной или несколькими операциями на нем.

Кольца и поля

Алгебраические структуры с двумя бинарными операциями - сложение и умножение.    

Поле

 

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

 

 

Onределение 1.8. Множество S называется полем, если сложение и умножение определены для любой пары ( α, β) элементов из S и выполняются следующие аксиомы.

1) Замкнутость по двум операциям (сложения и умножения).

 

2) Множество S является абелевой группой относительно операции сложения.

3) Множество S является абелевой группой относительно операции умножения. Это свойство создает основу для деления элементов и

определяет математическое правило сокращения, т.е. если αβ = уα, α, β, у ÎS

 

, то β = у (в предположении, что α не равно нулю).

 

4) Выполняется дистрибутивность: для любых α,β, у ÎS

 

α(β+y)=αβ+αy (β+ у)α=βα+yα .

 

Итак, поле представляет собой алгебраическую структуру, элементы в которой можно складывать, вычитать, умножать и делить в соответствии с обычными правилами арифметики (для случая, когда аддитивная и мультипликативная группы бесконечны).

Примером поля являются множество Q рациональных чисел,

 

множество R - действительных чисел. Заметим, что множество Z целых чисел не удовлетворяет аксиомам поля, поскольку любое целое число больше 1 не имеет обратного по операции умножения элемента, который являлся бы целым числом.

 

 

поле.

Отметим важное свойство поля - разрешимость линейных уравнений в

 

Введем обозначение F для поля, этим же символом далее будем

 

обозначать и множество элементов поля.

 

Линейным уравнением относительно х над полем F называется выражение вида αх + β = 0 , где 0, α,β ÎF.

Если α не равно нулю, то линейное уравнение αх + β = 0

 

имеет единственное решение в F (т.е. существует только один элемент поля, при подстановке которого в уравнение получается верное равенство).

Приведем доказательство [5] этого утверждения, которое ил- люстрирует, каким образом разрешимость линейного уравнения следует из аксиом поля.

αх+β=0,

 

αх +β+ ( -β) = 0 + ( -β) ассоциативность и свойство аддитивной единицы (О);

αх+0 =(-β) по определению 0;

 

х = ( -β) свойство 0;

 

a-1

(αx) =

a-1

( -β) α не равно 0;

 

(αa-1 )x = (-β)

a-1

ассоциативность и коммутативность;

 

lх = (-β)

 

х = (- β)

a-1

 

a-1

по определению мультипликативной единицы;

 

свойство 1.

 

Элемент (-β)

a-1 содержится в F (так как F замкнуто относительно операций

 

сложения и умножения). Этот элемент и дает решение уравнения. Более того,

 

так как обратные элементы в F единственны, то -β и

a-1 определяются из

 

данного уравнения единственным образом, и, следовательно, решение единственно.

 

ЛЕКЦИЯ 11

 

Конечные поля

 

Определение 1.9. Поле Fq называется конечным, если множество его элементов конечно.

Обозначение. F - символ для обозначения конечного поля из q элементов. Число q называется порядком конечного поля.

Так как поле Fq, по определению, является мультипликативной группой, то каждый ненулевой элемент α поля Fq имеет мультипликативный порядок (напомним, что если существует m ÎN такое,

что α m = 1, α ÎFq, и не существует меньшего i ÎN ,

 

такого, что α = 1 , то m называется мультипликативным порядком элемента α ).

 

 

Определение 1.10. Примитивным элементом поля Fq называется элемент, у которого мультипликативный порядок точно равен q-1.

 

 

Любое поле

*

F

q содержит примитивный элемент.

 

Мультипликативная группа Fq ненулевых элементов произвольного конечного поля Fq циклическая.

 

 

Примитивный элемент поля Fq является образующим элементом

 

 

циклической группы

F* .

 

q

Определение 1.11. Если существует целое k ÎN , такое, что ka = 0, α ÏFq (и не существует меньшего целого i Е N, ,такого, что ia = 0 ), то k называется аддитивным порядком элемента α.

Ненулевые элементы поля Fq имеют один и тот же аддитивный порядок [2].

 

Характеристика поля

Определение 1.12. Если в поле Fq все ненулевые элементы имеют аддитивный порядок k, то говорят, что поле Fq имеет характеристику k. Обозначение. р -… Характеристика любого конечного поля Fq (с числом элементов р) является… Число q элементов конечного поля Fq определяется характеристикой поля:. для любого целого n ≥1 и простого числа…

Отметим, что в поле GF(p n ) при n > 1 правила сложения и

 

Умножения не являются сложением и умножением по модулю

 

Операции в таком поле будем рассматривать далее.

p n .

 

Вычисление обратных элементов

В арифметике действительных чисел просто вычислить обратную величину a−1 для ненулевого a: a-1 = 1/a или a? a-1 = 1.  

ЛЕКЦИЯ 12

 

Многочлены над конечным полем

Onределенuе 1.13. Многочленом (относительно х) над полем GF(p)   m называется выражение

Для любого простого р и nÎN существует хотя бы один неприводимый над полем GF(p) многочлен степени n [9].

    многочлен

Алrебраические структуры над множеством многочленов

Кольцо многочленов над полем GF(p)   Определение 1.17. Кольцо, образованное многочленами над полем GF(p), называется кольцом многочленов над конечным по …

Корни многочлена

 

Элемент а из поля F называется корнем многочлена f(x) над а, если

 

f(a)=0.

 

Элемент а ÎF является корнем нулевого многочлена f(x) над F тогда и только тогда, когда многочлен (х - а) является делителем f(x). Если f(x) имеет степень п, то число элементов поля F, являющихся корнями f(x), не превосходит n [2].

Если f(x) - неприводимый многочлен степени n≥2 над F, то он не имеет корней в F [2].

 

ЛЕКЦИЯ 13

 

Расширение полей

Рассмотрим, какова связь полей GF(p) и GF( p n ).   Пусть F - поле. Подмножество К поля Р, которое само является полем относительно операций поля Р, называется подполем.…

Лекция 14

Дополнительный материал из раздела Теория чисел

Уравнения сравнений

a * a-1 ≡ 1 mod P, где a-1 = x a * x ≡ 1 mod P

 

Общий вид:

 

 

Ax ≡ b mod P

 

x ≡ (ba-1) mod P

 

H/p

 

 

a=5, b=9, mod = 23

5x = 9 mod23

5→ 5-1 = y

5 * y ≡ 1 mod 23

5 * 14 => y = 14 x ≡ 9*14 mod P x = 11

 

Системы уравнений сравнений

Общий вид:   x ≡ c1 mod m1

Китайская теорема об остатках

 

 

Пусть m1, m2, … mt – модули mi > 1 (mi, mj) > 1; i ¹ j

 

 

Пусть a1, a2, … , at – целые 0 £ai £mi

Пусть M = m1, m2, …, mt, mi = M/mi, Ni = Mi-1

 

 

Ni * Mi ≡ 1 mod Mi

 

Тогда x ≡ ai (mod mi)

x ≡ a1 (mod m1)

x ≡ a1(mod m2)

………………

x ≡ at (mod mt)

 

 

X =å (ai Ni Mi) mod M, 0£ x£ M

 

Тестирование чисел на простоту

 

 

Псевдопростые числа

 

Псевдопростые числа – это составные натуральные числа, удовлетворяющие малой теореме Ферма.

 

 

Малая теорема Ферма утверждает, что если n простое, то выполняется условие: при всех a из {1, 2, …, n−1} имеет место сравнение

an-1≡ 1 (mod n) (1)

 

 

Из этой теоремы следует, что если сравнение (1) не выполнено хотя бы для одного числа a в интервале {1, 2, …, n−1}, то n — составное.

 

 

И для которых справедливы следующие утверждения:

 

Ap-1(mod p) ≡ 1

 

bn-1(mod n) ≡ 1,где 1 < b £ n-1

 

Тест Люка

 

Предположим, что мы хотим определить, является ли данное число n простым. Один из возможных путей – попытаться показать, что порядок группы U(n) равен n-1, т.е. имеет место равенство φ(n) = n-1. Если это так, то любое натуральное число а, меньше n, должно быть взаимно простым с ним, что возможно только для простого n.

 

Пусть n – нечетное натуральное и b – целое число, подчиняющееся

 

неравенству

 

Pound; b£ n-1

Если для каждого простого делителя p числа n-1 справедливы следующие утверждения:    

Bi n-1 ≡1 (mod n)и bi (n-1)/p

¹ 1 (mod n),

 

Отметим, что числа bi не обязательно должны быть различными.

 

Числа Кармайкла

Может ли составное нечетное число n быть псевдопростым по всем взаимно-простым с ним основаниям b? Забегая вперед, скачем, что «да».    

Получение простых чисел для алгоритма RSA

 

Процедура получения устойчивых простых чисел

1. Генерируются простые числа s,t   2. Получаем простое число r такое что, (r-1) делит t без остатка: r-1|t

ЛЕКЦИЯ 15

 

 

Генераторы псевдослучайных последовательностей

 

Над полем

GF (2)

 

М-последовательности. ГПСЧ типа ЛРС1

Опр ед ел ени е. Последовательностью над полем   GF ( p)

ГПСП на основе произведения многочленов

 

M - последовательности на основе произведения многочленов

  многочленов, при  

M - 1) - последовательности на основе

 

Произведения многочленов

Рассмотрим следующие свойства ЛРП, порождаемой схемой ГПСП,   изображенной на рис. 2.1, при

ЛЕКЦИЧ 16

Способы представления элементов поля GF(2n)   Для представления элементов в полях Галуа вида GF(2n) существуют различные способы, образующие изоморфные поля:

Алгоритм получения элементов поля GF(2n) в стандартном базисе

Для построения элементов поля GF(2n) в стандартном базисе существует следующий алгоритм, использующий сдвиговые регистры. На входе: поле GF(2n), заданное полиномом-модулем ψ(x).  

Заданными в стандартном базисе

  Сложение двух многочленовa0 b0 a0Åb0 a1 b1 a1Åb1 a2 b2… . . . . . . . . .

Классическая схема умножения

 

Данный алгоритм состоит из двух основных шагов:

 

1) вначале 2 полинома f1(x) и f2(x) перемножаются, с сокращением подобных членов (коэффициенты складываются по модулю два);

2) от результата берется остаток от деления на неприводимый полином-

 

модуль P(x), задающий данное поле.

 

Пример . Пусть заданы поле GF(24), примитивный полином-модуль

 

P(x) = x4 + x + 1 и перемножаемые элементы поля f1(x) = x3 + x2 + 1 и

 

f2(x) = x2 + x + 1. Найти f3(x) = f1(x)? f2(x) mod P(x).

 

f1(x)? f2(x) = (x3 + x2 + 1)(x2 + x + 1) = x5 + x4+ x3+ x4+ x3+ x2+ x2+ x + 1

 

=

 

= x5 + x + 1.

 

Найдем остаток от деления f1(x)?f2(x) на P(x):

 

x5 +

Å

 

x + 1

 

x4 + x + 1

x5 +x2 +x x .

 

x2 + 1

 

В итоге, результат равен f3(x) = f1(x)? f2(x) mod P(x) = x2 + 1.

 

Проверим результат. f1(x) соответствует степени примитивного элемента ξ13, а f2(x) - ξ10. Используя формулу (раздел 3.1) умножения двух примитивных элементов, заданных в нормальном базисе, получим в качестве результата элемент ξ13? ξ10= ξ 23 mod 15 = ξ8. Ему соответствует полином x2 + 1 (пример 3.3, табл. 3.1).

Ответ: f3(x) = x2 + 1.

 

Операция деления на модуль Р(х)

 

 

Пример. Модуль – примитивный полином Р(x) = x4 + x + 1 , в векторной форме 10011

Исходный полином f(x) = x10 + x8 + x6 + x5 + x , в векторной форме

 

 

Операция деления полинома на модуль Р(х):

x10 + x8 + x6 + x5 + x x4 + x + 1 x10 + x7 + x6 x6 + x4 + x3

x8 + x7 + x5 + x

x8 + x7 + x4

x7 + x4 + x x7 + x4 + x3

x3 + x - R(x)

 

Операция деления на модуль Р(х) в векторной форме (в двоичном представлении)

 

 

10101100010 10011

10011 1011

11010

10010

1010 - R(x)

 

 

Лекция 17

 

 

ПРИЛОЖЕНИЯ ТЕОРИИ ЧИСЕЛ

 

И КОНЕЧНЫХ ПОЛЕЙ К АЛГОРИТМАМ ШИФРОВАНИЯ

 

Алгоритм асимметричного шифрования RSA

Алгоритм RSA предложили в 1978 г. 3 автора: Райвест (Rivest), Шамир (Shamir) и Адлеман (Adleman). RSA является алгоритмом с открытым ключом,… Надежность алгоритма основывается на большой вычислительной сложности: - факторизации (разложения на простые сомножители) больших чисел

Приложение теории поля GF(2n) к алгоритму шифрования AES

 

В 1997 г. Национальный институт стандартов и технологий США (NIST) объявил конкурс на новый стандарт криптографической защиты для информации правительственного уровня на замену алгоритму DES.

Стандарт AES - FIPS-197 [5, 14, 15] (вариант алгоритма RIJNDAEL,

 

авторы Joan Daemen и Vincent Rijmen, Бельгия) вступил в силу в 2002 г.

 

Симметричный алгоритм RIJNDAEL обладает:

 

- доступностью для открытого использования (без патентных прав);

 

- низкими требованиями к памяти - возможность реализации в смарт-

 

картах;

 

- простой конструкцией схемы в аппаратной и программной

 

реализациях;

 

- возможностью распараллеливания операций;

 

- поддержкой любых аппаратных платформ - из-за использования простых арифметических операций;

- быстрой процедурой формирования ключа;

 

- поддержкой разных длин ключа с шагом 32 бита, в том числе 128, 192 и 256 бит;

- одинаковой алгоритмической структурой и временной сложностью при прямом и обратном преобразовании;

- базируется на теории конечных полей.

 

Стойкость - способность шифра противостоять методам криптоанализа. Недостатком является уязвимость к анализу мощности.

Авторами решались следующие задачи:

 

- найти оптимальное соотношение между скоростью работы алгоритма и запасом его стойкости;

- поддержка простых и дешевых смарт-карт;

 

- аппаратная поддержка чипов FPGA и ASIC;

 

- выбрать дополнительные режимы функционирования алгоритма.

 

В табл. 4.2 представлены сравнительные характеристики двух симметричных алгоритмов ГОСТ 28147-89 и RIJNDAEL.

Таблица 4.2. Характеристики алгоритмов ГОСТ 28147-89 и

RIJNDAEL

Показатель	ГОСТ 28147-89	RIJNDAEL
Размер блока, бит
Размер ключа, бит		128,192,256
Архитектура	Однородная сеть Фейстеля	"Квадрат" (Square)
Число раундов		10, 12, 14
Часть блока, шифруемая за один раунд, бит
Размер ключа на 1 раунд, бит
Используемые на раунде операции	Сложение, подстановки и сдвиги	Использование арифметики конечных полей
Размер узлов замены, вход/выход, бит	4/4	8/8
Способ конструирования узлов замены	Закрытая методика	Алгебраический подход

 

 

Математическая модель алгоритма RIJNDAEL

Байты можно рассматривать как элементы конечного поля GF(28) -   многочлены степени не более 7

Раунд преобразования алгоритма RIJNDAEL

RIJNDAEL выполняет серию однотипных раундов преобразования шифруемого блока. Шифруемый блок и его промежуточные состояния в ходе преобразования…   1) замена байтов S[ ] (SubBytes) - каждый байт блока данных заменяется новым значением по фиксированной матрице…

ПЕРЕЧЕНЬ

Тем по практическим занятиям

1. Алгоритм Ферма

2. Тестирование чисел Мерсенна

3. Схема Горнера

4. Вычисление обратных мультипликативных элементов

5. Вычисление обратных мультипликативных элементов в поле

GF(2n)

6. Вычисление первообразных элементов

7. М- последовательности

8. М-1 последовательности

 

Список литературы

 

1. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. - М.: Гелиос АРВ, 2005. - 480 с.

2. Бахарев А.Н., Захаров В.М., Нурутдинов Ш.Р., Песошин В.А., Шалагин С.В. Вычислительные и автоматные схемы над полем GF(2n): Учебное пособие /Под ред. Захарова В.М. - Казань: Изд-во КГТУ им. А.Н.Туполева, 2006. - 136 с.

4. Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А.

 

Алгоритмические основы эллиптической криптографии. - М.: МЭИ,

 

2000. -100 c.

 

5. Бухштаб А.А. Теория чисел. - М.: Просвещение, 1966. - 384 с.

 

6. Зензин О.С., Иванов М.А. Стандарт криптографической защиты AES.

 

Конечные поля. - М.: Кудиц-Образ, 2002. - 176 с.

 

7. Захаров В.М., Нурутдинов Ш.Р., Шалагин С.В. Аппаратная реализация умножения элементов поля Галуа на программируемых микросхемах

 

архитектуры FPGA // Вестник Казан. гос. техн. ун-та им. А.Н.Туполева,

 

2001. - №1. С. 36-41.

 

8. Коутинхо С. Введение в теорию чисел. Алгоритм RSA. - М.: Постмаркет,

 

2001. - 328 с.

 

9. Лидл Р., Нидеррайтер Г. Конечные поля: в 2-х томах, Т.2. Пер. с англ. -

 

М.: Мир, 1986. - 822 с.

 

10. Нечаев В.И. Элементы криптографии. Основы теории защиты информации. - М.: Высшая школа, 1999. - 109 с.

11. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. - М: Радио и связь, 1999. - 328 с.

12. Самсонов Б.Б., Плохов Е.М., Филоненков А.И. Компьютерная математика (основание информатики). - Ростов-на-Дону: Феникс, 2002. -

512 с.

 

13. Чеботарёв Н.Г. Теория Галуа. Кн. 1. - М.: ОНТИ НКТ СССР, 1936. -

 

156с.

 

14. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. - М.: Триумф, 2002. - 816 с.

15. Daemen J., Rijmen V. AES Proposal: Rijndael. http://csrc.nist.gov/encryption/aes

16. Federal Information Processing Standards Publication. Announcing the

 

Advanced Encryption Standard (AES). http://csrc.nist.gov/encryption/aes

 

17. Paar C., Fleishmann P., Roelse P. Efficient multiplier architectures for Galois fields GF((24)n) // IEEE Trans. Computers, 1998, №2, Vol.47, P.162-170.

18. Захаров В.М., Эминов Б.Ф. Вычисления в конечных полях. Учеб. пособие. – Казань: КГТУ им. А.Н. Туполева, 2010. – 132с.