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

N = pq; φ(N) = N – p – q + 1 = (p-1)(q-1)

Обобщенная теорема Эйлера

x Z*N : xφ(N) ≡ 1{N}

Пример: 5φ(24) = 58 = 390625 = 1{24}

Обобщенная теорема Эйлера является базисным понятием криптографии, носит более широкий характер, чем теорема Ферма и является основой криптосистем стандарта RSA.

Нелинейные сравнения

Задача извлечения корня произвольной степени из некоторого целого числа по модулю n.

Число x Z*p| xt ≡ C{P} называется корнем C степени t из числа x.

Лемма: Z*px → x2 не является биекцией

53

Определение: число x Zp называется квадратичным вычетом (QR), если оно имеет квадратный корень Zp.

Если Р – простое число, то

QR{p}(p) = P−21 + 1 – число вычетов

Модальная теорема Эйлера

x Z*p, где p – нечетное простое число, тогда 2 ≡ 1{P}. Значение 2 называют символом Лежандра.

−1

Лемма: C Z*p sqrt(C) = C{P} 2

Если p ≡ 1{4}, то корень может быть вычислен за кратчайшее время, во всех остальных случаях время пропорционально O(log23P).

Квадратные уравнения по модулю p

ax2 + bx + c = O{p}

Особенности вычисления: x1,2 = (2a1 )*(-b± D1/2) D – дискриминант. Корень из D на конечном поле может и не существовать.

Функция Dlogq(gx) = x, x [0; q -2] называется функцией дискретного логарифмирования.

Z11

Dlog2(1) = 0{11}

Dlog2(2) = 1{11}

Dlog2(3) = 8{11}

Dlog2(4) = 2{11}

Dlog2(5) = 4{11}

54

Dlog2(6) = 9{11}

Dlog2(7) = 7{11}

Dlog2(8) = 3{11}

Dlog2(9) = 6{11}

Dlog2(10) = 5{11}

Функция дискретного логарифма может быть обобщена. Пусть G =<g>q-1={1; g; g2;

… ;gq-1}. Говорят, что задача дискретного логарифмирования является вычислительно сложной в циклической группе G, если любому алгоритму , вычисляемому за полиномиальное время, вероятность Pg←G; x Zp [(G, q; qx) = x] составляет пренебрежимо малую величину.

Примером группы, в которой задача дискретного логарифмирования является вычислительно сложной, является Z*p, где p – большое простое число или группа точек конечной эллиптической кривой над конечным полем.

Лучшим из известных алгоритмом дискретного логарифмирования таких типов задач является алгоритм – решетка числового поля. Его трудоемкость – 0( 1/3), где n –

числа в битах.

Следующая вычислительно сложная процедура – факторизация. Факторизация – разложение составного числа на простые составляющие.

Z+2(n) = {N/N = pq}, где p и q – n-битные простые числа, их нахождение является вычислительно сложной задачей.

На данный момент рекордом является факторизация 768 битного числа.

Необходимые сведения из теории вероятностей

U – финитное множество. Cap|U| - мощность этого множества. Можно сопоставить частоту появления элементов этого множества во входном потоке шифрования/дешифрования, то есть собрать статистику их встречаемости. Эта частота будет стремиться к вероятности появления элемента множества входного/выходного

потока.

55

P: U → B1

∑ p(x)=1

Если все символы множества во входном/выходном потоке равновероятны, то распределение носит равномерный характер.

P(x) = 1

capU

P(x0) = 1; x0 U

P(x0) = 0; x U

Рассмотрим случай совпадения множества U с булевым кубом Bn и исследуем вопросы распределения вероятностей для таких случаев:

Полная группа элементарных событий имеет вид [p(0; 0; … ; 0); p(0; 0; … ; 1); … ; p(1; 1;

… ; 1)]. Θ U.

Pr(Θ) = [(0, 0, … , 0); …; (1, 1, … , 1)]

Мощность множества Θ определяется по формуле | Θ |= 2

cap|B|

Pr[Θ] = ∑ p(x) – по всем событиям из покрытия Bn.

τ B8;

τB8

lsb2(x) = 11 (младший бит)

B8

msb2(x) = 11 (старший бит)

Теорема сложения вероятностей

p[A1 A2] ≤ p[A1] + p[A2]

p[A] = 0.5

56

p[(lsb2(x) = 11) (msb2(x) = 11)] ≤ 0.25 + 0.25 = 0.5

X: U → Vx

Bn → B1

p[x = 0] = 0.5 p[x = 1] = 0.5 p[x = v]: p[x-1(v)]

Пусть U – финитное множество. Равновероятность выбора а Up[r = a] = capU1 .

Вероятностный алгоритм

: y ← (m). По выходному значению случайной переменной m однозначно вычисляется значение выходной переменной y.

C ← (m)

p[A B] = p[A]p[B]

Случайные величины x и y независимы, если для а;b V:

p[(Y = b)] p[(x = a)] = P[(x = a)]p[(Y = b)]

U = B2

00

01

10

11 r← U

x = lsb(r) y = msb(r)

p[(x = 0) (y =0)] = p[(r = 00)] = 0.5 = p[x = 0]*p[y = 0]

xBn

57

y – независимая от x равномерно распределенная величина на Bn.

Z:=x + y – новая случайная величина, представляет собой равномерно распределенную случайную величину.

Теорема (парадокс дней рождения):

r1, … ,rn U. n = 1, 2, …, sqrt(capU) . Тогдаp[ i ≠ j; ri = rj] ≥ 0.5

58

Литература

1. Зегжда П.Д. Теория и практика обеспечения информационной безопасности. - М.:

Москва, 1996 - 292 с.

2. Казарин О.В. Методология защиты программного обеспечения. - М.: МЦНМО Москва,

2009 - 464 с.

3.Запечников С.В., Казарин О.В., Тарасов А.А. Криптографические методы защиты информации. - М.: ЮРАЙТ, 2015 - 309 с.

4.Грушо А.А., Применко Э.А., Тимошина Е.Е. Теоретические основы компьютерной безопасности. - М.:Academia, 2009 - 340 с.

5.Романьков В.А. Введение в криптографию. - М.: Форум, 2012 - 240 с.

6.Бабаш А.В., Баранова Е.К. Криптографические методы защиты информации. - М.:

КноРус, 2017 - 200 с.

59