Теоретические основы современной криптографии

1.

Теоретические
основы современной
криптографии

2.

I. Элементы теории чисел
…
…
1) Множества N и Z .
2) Делители и кратные d|a, a d
3) a d=>|d|< |a|
4) Простые и составные числа.
5) Деление с остатком. Сравнения по
модулю.

3.

Теорема 1.
(о делении с остатком).
Для любого целого числа а и положительного целого
числа n существует единственная пара целых числа q и r,
для которых 0 < r < n и a = qn + r

4.

Число q=[a/n] называется частным или
неполным частным;
число r, обозначаемое a mod n, называется
остатком.
Если r = 0, то пишут a mod n = 0
Если r = 1, то пишут a mod n = 1
в общем случае a mod n = r, т.е.
a =[a/n]n +(a mod n) => a mod n = a -[a/n]n

5.

Класс эквивалентности (класс вычетов):
Ca = cl(a)={nk+a|k
Z}
Множество классов вычетов по модулю n:
Zn = {C0 ,C1 ,… ,Cn-1 }
Выбирая в каждом классе по представителю,
можно считать, что:
Zn = {0 ,1 ,… ,n-1}

6.

6) Общие делители. Наибольший общий
делитель.
Среди всех общих делителей данных чисел
а и b можно выбрать наибольший общий
делитель, который обозначают НОД(а, b).
Он определён, если хотя бы одно из чисел
а и b отлично от 0. Положим для удобства
НОД(0,0) = 0.

7.

Важные свойства общих делителей и наибольшего
общего делителя:
если d | а и d | b, то d (а + b) и d | (а - b)
(1)
если d| а и d | b, то d(ах + bу) при любых целых
х и у.
(2)
Если а | b, то |а| ≤ |b| или b = 0, поэтому
если а | b и b | a, то а = ± b.
Кроме того,
НОД (а,b) = НОД (b,а),
НОД (а,b) = НОД(-а, b),
НОД (а,b) = НОД (|а|, |b|),
НОД (a,0) = |а|,
НОД (а, ka) = |а| при всяком k Z.

8.

Теорема 2.
Наибольший общий делитель целых чисел а и b, не
равных 0 одновременно, является наименьшим
положительным
элементом
множества
{ах + bу : x,у Z} целочисленных линейных
комбинаций чисел а и b

9.

Доказательство.
Пусть наименьший положительный элемент этого
множества равен s. Тогда s = ах + bу для некоторых
x,у Z. Положим q =[a/s].
Согласно (a mod n = a – [a/n]n)
a mod s = a – qs = a – q(ax + by) = a(1 – qx) + b(-qy)
и потому остаток от деления а на s тоже является
линейной комбинацией а и b. Но s был наименьшей
положительной комбинацией такого вида, =>
|s|< a mod s. Итак, a mod s - линейная комбинация, а
s – наименьшая линейная комбинация => a mod s>s
(если a mod s положительно) или a mod s=0.

10.

Но! Остаток строго меньше делителя =>
a mod s < s => a mod s
не может быть
положительным. Так что a mod s = 0 и s|a.
По аналогичным причинам верно s|b. Таким
образом, s =НОД (а,b) делит как а, так и b, а
потому делит и s = ах + bу.
Поскольку s > 0, отсюда следует, что
НОД (а,b) ≤ s. Таким образом, НОД (а,b) ≥ s и
НОД (а,b) ≤ s, так что НОД (а,b) = s , ч.т.д.

11.

Следствие 2.1
Наибольший общий делитель двух целых чисел
кратен любому их общему делителю.

12.

Доказательство.
По теореме 2 НОД (а,b) является линейной
комбинацией а и b. Из свойства 2 вытекает, что
d|(ax + by), но НОД = min(ax + by),
следовательно, делитель а и b является делителем
любой комбинации (ax + by), в том числе и
наименьшей, ч.т.д.

13.

Следствие 2.2
Для любых целых чисел а и b и неотрицательного
целого числа n выполняется соотношение
НОД (аn,bn) = n НОД (а,b).

14.

Доказательство.
Элементы вида (апх + bпу) получаются из
элементов вида (ах + bу) умножением на n, так
что это относится и к наименьшему элементу
такого вида, ч.т.д.

15.

Следствие 2.3
Для любых положительных целых чисел п, а и b из
того, что п|аb и НОД(а, п) = 1 следует п|b.

16.

a
n
b
n
n
|b
Доказательство.
НОД(а, п) = 1 => a не кратно n =>
b кратно n => n|b
ч.т.д.

17.

7) Взаимно простые числа.
Целые числа а и b взаимно просты, если
НОД (а,b) = 1.

18.

Теорема 3.
Если НОД (а,p) = 1 и НОД (b,p) = 1, то
НОД (аb,p) = 1 (для любых целых чисел а, b, p).

19.

Доказательство.
По теореме 2 найдутся целые числа х, у, x´ и y´ для которых,
ах + ру = 1,
bx´ + py´= 1.
Перемножая эти равенства, мы видим, что
ab(xx´) + p(ybx´ + y´ax + pyy´ )= 1,
так что 1 является целочисленной линейной
комбинацией ab и p; осталось сослаться на теорему 2,
ч.т.д.

20.

8) Разложение на простые множители.

21.

Теорема 4.
Если простое число p делит произведение двух
целых чисел а и b, то p | а или p | b.

22.

Доказательство.
Если это не так и p не делит ни а, ни b, то p
взаимно просто с этими числами (других
делителей у p нет) и потому взаимно просто с
их произведением (теорема 3) => ab не кратно p
=> противоречие, ч.т.д.

23.

Теорема 5.
(существование и единственность разложения),
(основная теорема арифметики).
Всякое составное число а единственным образом
представляется в виде
a = p1e p2e · …· prer,
1
2
где p1<p2<…<pr - простые числа,
еi - положительные целые числа.
Без доказательства.

24.

9) Наибольший общий делитель.
Если
a = p1e p2e · …· prer
1
2
и
b = p1 f p2 f · …· pr fr
1
2
то
НОД(a,b) = p1 min(e
1,
f1 )
· p2 min(e
2,
f2 )
…· pr min(e
r,
fr )

25.

Теорема 6.
(рекуррентная формула для НОД).
Пусть а – целое неотрицательное, а b – целое
положительное число.
Тогда НОД (а,b) = НОД (b , а mod b).

26.

Доказательство.
Пара (а,b) имеет те же делители, что и пара
(b, а mod b):
а mod b = а – [а/ b] b = 1 а + (-q) b
(a mod b является целочисленной линейной
комбинацией а и b и наоборот). Поэтому и
наибольший общий делитель у этих пар
одинаковый, ч.т.д.

27.

10) Алгоритм Евклида.
Euclid (а,b)
if b = 0
then return а
else return Euclid (b, а mod b)
Число рекурсивных вызовов составляет
O(logb).

28.

11) Расширенный алгоритм Евклида.
d = НОД (а,b) = ax + by
НОД (а,b) = min (ax + by) при аb ≠ 0
Extended-Euclid(a,b)
if b=0
then return (a,1,0)
(d ,x ,y ):=Extended-Euclid(b, a mod b)
(d,x,y):=(d ,x ,y -[a/b] y )
return (d,x,y)

29.

II. Элементы общей алгебры.
1) Группа.
Алгебраической операцией (на множестве S)
называется отображение * : S S S,
т.е. отображение, обладающее свойством
замкнутости.

30.

Множество S с определённой на нём
алгебраической операцией * называется
группой, если выполнены следующие свойства:
Ассоциативность: a * (b * c) = (a * b) * c
для любых a, b, c из S.
2. Существование нейтрального элемента:
существует элемент е из S, для которого
е*a = а*е = а для любого a из S (такой элемент может
быть только один, так как е = e*е’= e’ для любых двух
элементов e и e’ с таким свойством).
3. Существование обратного элемента: для
всякого a из S найдется единственный элемент b из S,
для которого a * b = b * a = e
1.

31.

Условия 1-3 называются аксиомами группы.
Группа с коммутативной операцией называется
коммутативной или абелевой.
а * b = b * а для любых а, b из S

32.

Обычно групповую операцию * обозначают
специальными символами, чаще всего
символами • или +, называя a·b произведением,
а (a + b ) – суммой элементов а, b из S. В первом
случае нейтральный элемент называют
единицей (обозначение: 1), симметричный
элемент – обратным (обозначение: а-1), а саму
группу S –мультипликативной.
Во втором случае нейтральный элемент
называют нулем (обозначение: 0),
симметричный – противоположным
(обозначение: -а), а саму группу S – аддитивной.

33.

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

34.

для любых а, b, с из К
1) (a + b) + c = a + (b + c);
2) Существует 0 из К : a + 0 = 0 + a;
3) Для любого a из К существует -a из К :
a + (-a) = (-a) + a = 0;
4) a + b = b + a;
5) (ab)c = a(bc);
6) (a + b)c = ab + bc, a(b + c) = ab +ac.

35.

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

36.

Простейшие свойства кольца:
1. Кольцо обладает всеми свойствами аддитивной
абелевой группы:
а) существует, и притом единственный,
нулевой элемент 0;
б) для каждого элемента a существует, и
притом единственный, противоположный
элемент - а;
в) для любых элементов а, b К существует,
и притом единственное, решение уравнения
x + а = b; это решение называется разностью
элементов b и а и обозначается символом b - a.
Итак, b – a = b + (-a).

37.

2. В кольце умножение дистрибутивно относительно
вычитания:
a(b – c) = ab – ac,
(a – b)c = ac – bc, для любых a,b,c K.
Это следует из того, что b = (b - с) + с
и
аb = а(b - с) + ас.

38.

3. В кольце для любого элемента а:
a 0 = 0 a = 0.
Это следует из дистрибутивности умножения
относительно вычитания:
а 0 = а(b - b) = аb - аb = 0.

39.

4. В кольце для любых элементов а,b:
(-а)b = а(-b) = -аb.
Это следует из того, что
аb + (-а)b = (а + (-а))b = 0b = 0.
Следствие: (-а)(-b) = аb, а,b К.

40.

5. В кольце с единицей для любого элемента а:
(-1)а = а(-1)=-а.
Это следует из того, что
а + (-1)а = 1а + (-1)а = (1 + (-1))а = 0а = 0.

41.

6. В кольце с единицей, содержащем не менее двух
элементов:
1≠0.
Действительно, если 0 = 1, то существует
а К : а ≠ 0, а ≠ 1. Тогда из равенства 0=1
следует, что 0а = 1а, т.е. 0 = а, но а ≠ 0.

42.

7. В кольце с единицей множество обратимых
(по умножению), элементов образует
мультипликативную группу.
Это следует из того, что произведение
обратимых элементов обратимо, т.е. умножение
в кольце является алгебраической операцией на
этом множестве.

43.

Делители нуля.
Ненулевые элементы a и b кольца называются
делителями нуля, если ab = 0.
При этом элемент a называется левым
делителем нуля, а элемент b – правым.
( )( ) ( )
1 0
0 0
0 0
1 1
= 0 0
0 0

44.

3) Кольцо вычетов.
1. Замкнутость: Ca+b Zn
2. Ассоциативность: Ca+(Cb+Cd)=(Ca+Cb)+Cd
3. Существует нейтральный элемент C0:
Ca+C0=C0+Ca=Ca
4. Существует противоположный элемент:
-C a =
{
C 0 ,если а=0
C n-a ,если а>0

45.

Определим на Zn операцию умножения. Положим
CaCb=Cr , где r ab(mod n). Эта операция обладает
следующими свойствами:
1. CaCb=CbCa , так как CaCb-класс, в который
входит ab, а ab=ba.
2. (CaCb)Cd=Ca(CbCd), так как оба произведения
представляют собой один и тот же класс, в
который входит число (ab)d=a(bd).
3. Существует единица C1, так как CaC1=C1Ca=Ca

46.

4. (Ca +Cb)Cd=CaCd +CbCd, так как оба произведения
представляют собой класс, в который входит
число (a+b)d=ad+bd.
5. Если n – составное число, то в кольце Zn есть
делители нуля, так как если n=ab, где 1<a<n ,
1<b<n, то Ca ,Cb Zn и CaCb=C0.

47.

Таким образом, Zn- конечное коммутативное
кольцо с единицей, которое имеет делители
нуля, если n – составное число. Оно
называется кольцом вычетов по модулю n.
По умножению кольцо вычетов не является
группой, так как не для каждого элемента
есть обратный.