Держинский Р.И. Математические основы информационной безопасности

Мультипликативная абелева группа

Множество В с элементами a, b, c для которых справедливы ассоциативность и коммутативность, существование единицы и обратного элемента называется мультипликативной абелевой группой.

Примеры:

Q* = Q \ {0}

R* = R \ {0}

Порядок группы – мощность множества А (для конечного числа элементов).

Замыкание множества – множество с его предельными точками.

Подмножество B А – множество, уложенное в А со следующими свойствами:

̅ замкнута относительно операции сложения. (a, b) B / a + b B.

(a) B ̅ / a + ̅ = 0

Пример: Z Q R

По умножению:

̅

(a) B / a*b B

(a) B ̅ / a*̅ = ll B

Пример:

{± 1} O* R*

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

<a> = {ka; k Z}

<a> = { ak; k Z }

43

Группы. Циклические группы и их виды

Множество Gcалгебраической операцией * называется группой, если выполняются

следующие условия:

операция * в Gассоциативна: a * (b * c) = (a * b) * c a,b G

в Gсуществует нейтральный элемент θ: a * θ = θ * a = a a G

для каждого элемента a G существует обратный ему элемент а-1 G: a * a-1

= a-1 * a = 0

Если операция * коммутативна, то группа называется коммутативной или абелевой. В

противном случае группа называется некоммутативной.

Определение: группа Gназывается циклической, если в ней существует порождающий элемент (то есть такой элемент d G, что G = <d>).

Основные понятия теории множеств

Операции над множествами:

объединение множеств (A B)

пересечение множеств (А В)

разность множеств (А \ В)

44

симметрическая разность (А В)

дополнение множества

декартово произведение

x A; y B

AxB = ((x, y)| x A, y B)

Пример: X = {1,2,3} Y = {2, 4}

Инъекция, сюръекция, биекция

Инъекция – отображение f множестваXна множество Y (f:X → Y), при котором разные элементы множества Xпереводятся в разные элементы множества Y.

45

Сюръекция – отображение множества X на множество Y, при котором каждый элемент множества Yявляется образом хотя бы одного элемента множества X.

Биекция – отображение, которое является одновременно и субъективным и инъективным. При биективном отображении каждому элементу одного множества соответствует ровно один элемент другого множества, при этом определено обратное отображение, которое обладает теме же свойствами.

Мощность множества. Счетные множества

Мощность множества – число элементов этого множества.

Счетное множество – это бесконечное множество, элементы которого можно пронумеровать натуральными числами.

Отношения на множествах

Область определения: dom(R) := {x | y := xRy}

Область значений: rang(R) := {y | x := xRy}

Основные теоремы теории множеств

любая часть счетного множества либо конечна, либо счетна

сумма конечного или счетного числа конечных или счетных множеств есть счетное множество

любое бесконечное множество содержит счетное подмножество

если множество Mне счетно, а В М есть конечное или счетное множество, то множество М и множество М / В имеют одинаковый ординал

присоединение к некоторому счетному/несчетному бесконечному множеству М счетного или конечного множества А дает множество с таким же ординалом

множество рациональных чисел счетно

множество всех пар натуральных чисел счетно

если некоторое бесконечное множество содержит в себе произвольное множество,

то они относятся к одному классу эквивалентности

46

множество всех конечных последовательностей состоящих из элементов данного счетного множества есть счетное множество

множество всех алгебраических чисел счетно

Множества образуют континуум С. Континуум – мощность множества всех вещественных чисел.

Кольца

Кольцо – абелева группа относительно операции сложения. Оно обладает свойствами:

Дистрибутивности относительно сложения

Коммутативности

Ассоциативности

Существования единицы

Примеры колец:

Целые числа

Рациональные числа

Действительные числа

Характеристика кольцаK – некоторое число, равное минимальному натуральному числу,

для которого: !a K / a + a + … + a = 0, если K – несчетное число.

CharK = 0 λλ ~ K

Поля

Полем называется коммутативное, ассоциативное кольцо с единицей, в котором любой ненулевой элемент обратим (Q, R).

В Z обратимы только 1 и -1.

47

Группа точек эллиптических кривых

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

Алгебраическая кривая порядка N называется множеством точек аффинной плоскости, для которых: f(x, y) = 0. При этом сама функция представляет собой полином с коэффициентами на поле k: degfk(x, y) = degPk(x, y) = n.

Особые точки алгебраической кривой – это набор точек вида:

Двойные особые точки алгебраических кривых и парные особые точки алгебраических кривых – обобщение на дифференциалах более высоких порядков рассмотренной выше системы.

Точки бифуркации – особые точки кривой, в которых все производные равны нулю.

Родом алгебраической кривой P называется главная характеристика алгебраической кривой порядка N, вычисляемой как P = 12 ( − 1)( − 2) − , где r – число точек возврата

Эллиптические кривые и групповые задачи на эллиптической кривой

Эллиптическая кривая над полем K, есть кривая первого рода в P2 (проективное пространство) c набором точек (x, y, z) K, удовлетворяющие условию Вейерштрасса:

E: y2z + a1xyz + a2yz = x3 + a2x2z + a4xz2 + a5z3ai K

Если charK> 3, то уравнение Вейерштрасса может быть записано в аффинных координатах с учетом специальной точки 0(∞;∞).

E:y2 = x3 + ax + b

48

Известно, что на эллиптической кривой существует групповой закон, определяющий аддитивную абелеву группу, при этом нейтральный элемент группы 0, есть несобственная точка. Групповая операция двух полиномов приводит к получению результирующего полинома P3(x3, y3) через сложение, задаваемое системой:

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

Китайская теорема об остатках применяется для решения систем уравнений вида:

x = b1{n1}

x = b2{n2}

……..

x = bk{nk}x Z

К ni выдвигается требование взаимной простоты, то есть НОД(ni, nj) = 1 i≠j

Данная система всегда имеет решение, более того, любое целое y Z, сравнимое с x,

также является решением.

Пример:

Решим систему из уравнений с помощью китайской теоремы об остатках

x = 2{5}

x = 15{17}

x = 5{12}

ВычислимN = n1*n2*n3 = 5 * 17 * 12 = 1020

49

N1 = N/n1 = 1020/5 =204

N2 = N/n2 = 1020/17 = 60

N3 = N/n3 = 1020/12 = 85

Решим вспомогательные уравнения вида Ni*yi = ai{ni}

Рассмотрим подробно первое из них:

204 * y1 = 2{5}

200 * y1 + 4 * y1 = 2{5}

0 + 4 * y1 = 2{5}

Перебирая y1 = 1, 2, 3, 4, 5, … находим его значение. Оно равно 3.

Проверка: 4 * 3 = 12{5} = 2{5}

Остальные два уравнения решаются аналогично:

60y2 = 15{17}y2 = 13

85y3 = 5{12}y3 = 5

Итоговое решение имеет вид: x = N1*y1 + N2*y2 + N3*y3 = 1817{1020} = 797{1020}

Математический аппарат теории чисел

n N, p – простое число, Z = {0, 1, 2, … , N-1}

Z12: 9 + 8 = 5{12}

5 * 7 = 11{12}

5 – 7 = 10{12}

x,y Z a,b Z НОД(x ,y) = ax + by

Определение: обратным к y-1: x Z : y будет называться такое число y, что xy ≡ 1{N}, N =

2n+1, n N.

50

Пример:

y-1{2} ≡ N ≡ N+12

Лемма: число x имеет обратное по модулю n число тогда и только тогда, если НОД(x,N) = 1

Z*{p} := {x Z | НОД(x, N) = 1}

Пример: пусть p – простое число, тогда

Z*p = Zp \ {0} = {1, 2, … ,p -1}

Для любого x Z*p может быть найден обратный элемент путем нахождения множителей Безу через расширенный алгоритм Евклида ax + b = O{N}.

X = -b*a-1{N}

Теорема Ферма

Для любого натурального числа n> 2 уравнение an + bn = cn не имеет решений в целых ненулевых числах a, b, c.

x Z*p :xp-1 ≡ 1{p}

Пример: p = 5

Zp = {0, 1, 2, 3} x Z*p | НОД(x, p) = 1

34 = 81 ≡ 1{5}

x Z*p :x*xp-2 ≡ 1{p} представляет собой альтернативный способ вычисления обратных элементов, однако значительно менее эффективный, чем метод Евклида.

51

Тест на простоту Ферма

Пусть необходимо сгенерировать большое простое число P длиной 1 килобайт. Для

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

случайно выбирается числоp [21024; 21025 - 1]

2p-1 ≈ 1{p}, если это так, то p – искомое число, если нет, то начинаем снова с 1-го пункта

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

g Z*p | {1, g, g2, … , gp-2} = Z*p, при этом p называется образующим элементом циклический группы <g>.

Пример:

p = 24

Z*24 = {1, 5, 7, 11, 13, 17, 19, 23}

Не каждый элемент группы является образующим.

Порядком элемента g в группе Z*p называется число элементов в ней. Порядок равен наименьшему a> 0, такому, что ga ≡ 1{p}

Пример:

ord7(3) = 6; ord7(1) = 1; ord7(2) = 3

Теорема Лагранжа

g Z*pordp(g) (p-1)

Для любого образующего порядок образующего делит порядок (p-1). Для такого случая вводят φ(N) = |Z*N|.

φ (12) = |{1, 5, 7, 11}| = 4

φ(p) = p – 1

52