Криптографічний захист інформації. Лекція 3. Елементи теорії чисел

1.

Subscribe to DeepL Pro to edit this document.
Visit www.DeepL.com/profor more information.

2.

КРИПТОГРАФІЧНИЙ
ЗАХИСТ ІНФОРМАЦІЇ
Лекція 3
Елементи теорії чисел

3.

ТЕОРІЯ ЧИСЕЛ І КРИПТОГРАФІЯ
Багато результатів теорії чисел, як і інших
фундаментальних наук, довгий час не були
дуже широко застосовні на практиці.
Однак із розвитком інформаційних технологій і
криптографії теорія чисел дала змогу
реалізувати низку проривних рішень, серед
яких вирізняються криптосистеми з відкритим
ключем.
Виділимо такі: протоколи узгодження ключів,
шифри з відкритим ключем, ігрові протоколи,
протоколи електронного голосування,
електронні гроші тощо.

4.

ДЕЯКІ ПОНЯТТЯ ТА ТЕМИ
ТЕОРІЇ ЧИСЕЛ
Прості числа;
Подільність, залишок від ділення;
Найбільший спільний дільник;
Найменше спільне кратне;
Розкладання чисел на прості множники;
Перевірка чисел на простоту;
Генерація великих простих чисел;
Взаємно прості числа;
Функція Ейлера;
Теореми Ейлера та Ферма;
...

5.

ЗАЛИШОК ВІД ДІЛЕННЯ ОДНОГО
ЧИСЛА НА ІНШЕ
Нехай дано натуральні числа a і b, тоді число r з
діапазону 0 ≤ r < b називається залишком від
ділення числа a на число b, якщо існує ціле число
k, за якого виконується рівність a = k*b + r. Кажуть
також, що k - це результат ділення націло (ціла
частина) числа a на число b.
Приклади.
27 = 3*9 + 0 => 27 mod 9 = 0 і 27 div 9 = 3;
45 = 4*11 + 1 => 45 mod 11 = 1 і 45 div 11 = 4;
17 = 3*5 + 2 => 17 mod 5 = 2 і 17 div 5 = 3.
Якщо залишок від ділення одного числа на інше дорівнює 0, то
кажуть, що перше число ділиться на друге.

6.

ПРОСТЕ ЧИСЛО
Ціле додатне число називається простим, якщо
воно ділиться тільки на 1 і на саме себе.
Ціле додатне число називається складеним,
якщо в нього існує хоча б один дільник,
відмінний від 1 і його самого.
Приклади.
2, 3, 5, 7, 11, 13, 17 - це прості числа.
15, 30, 45, 100 - це складові числа.

7.

КІЛЬКІСТЬ ПРОСТИХ ЧИСЕЛ
Твердження. Кількість простих чисел, що не
перевершують n, приблизно дорівнює n/ln(n).
Точніше.
Кількість простих чисел, що не перевершують n,
лежить у проміжку від
0,921*n/ln(n) до 1,106*n/ln(n).
N
Нижня межа
Верхня межа
100
19
24
1 тис.
133
160
10 тис.
999
1200
100 тис.
7999
9606
1 млн.
66664
80054

8.

ЯК ПЕРЕВІРИТИ, ЧИ Є ЧИСЛО
ПРОСТИМ?
Найочевидніший алгоритм.
Алгоритм. Вхід число n.
Цикл i Від 2 До n-1
Початок циклу
Якщо n ділиться на i, тоді
Відповідь - false (не просте)
Кінець циклу
Відповідь - true (просте)

9.

"РЕШЕТО ЕРАТОСФЕНА"
(АЛГОРИТМ ПОШУКУ ПРОСТИХ
ЧИСЕЛ)
Дано: число N.
Знайти: усі прості числа < N.
Алгоритм:
Виписуємо числа 1, 2, ... N-1;
Викреслюємо кратні 2 від 22 до N-1;
Викреслюємо кратні 3 від 32 до N-1;
Викреслюємо кратні 5 від 52 до N-1;
Викреслюємо кратні 7 від 72 до N-1;
....... і так далі до N1/2 .

10.

"РЕШЕТО ЕРАТОСФЕНА"
(ПРИКЛАД)
Знайдемо прості числа, менші за 61.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
51, 52, 53, 54, 55, 56, 57, 58, 59, 60.

11.

КРИТЕРІЙ ПРОСТОТИ ВІЛЬСОНА
Теорема. Число n є простим тоді й тільки тоді,
коли (n-1)! = -1 mod n.
Приклади.
(2-1)! = 1! = 1 = -1 mod 2;
(3-1)! = 2! = 2 = -1 mod 3;
(5-1)! = 4! = 24 = -1 mod 5;
(7-1)! = 6! = 720 = -1 mod 7.
Зауваження. Критерій Вільсона буває зручний під час
доказів, але застосовувати його для перевірки простоти
неможливо через величезну трудомісткість.

12.

МАЛА ТЕОРЕМА ФЕРМА
Теорема (Ферма). Нехай p - просте, і 0<a<p. Тоді ap-1
mod p = 1.
Приклади.
212 mod 13 = 1, 316 mod 17 = 1.
Наслідок із теореми Ферма. Якщо ap-1 mod p ≠ 1
хоча б для одного числа a з інтервалу 0<a<p, то
число n - складене.
Визначення. Число n називається псевдопростим
за основою a, якщо an-1 mod n = 1.

13.

ТЕСТ НА ПРОСТОТУ НА ОСНОВІ
МАЛОЇ ТЕОРЕМИ ФЕРМА
Потрібно перевірити, чи є число n простим.
Алгоритм.
Вибираємо випадково число a з інтервалу 0<a<n
і перевіряємо умову an-1 mod n = 1. Якщо ця
умова не виконується, то n - складена.
Якщо умова виконується, то n - "імовірно" просте.
Повторивши тест ще кілька разів, ми збільшуємо
нашу впевненість у простоті числа.

14.

ПРОБЛЕМА ТЕСТУ ФЕРМА
Існують числа, які є псевдопростими за одними
підставами, але не псевдопростими за іншими.
Існують також числа, які є псевдопростими за
всіма підставами.
Такі числа називаються псевдопростими (без
зазначення основи) або числами
Кармайкла.
Кількість чисел Кармайкла, що не перевищують
25 млрд. всього 2163.
Чисел Кармайкла, що не перевершують 100000,
всього 16: 561, 1105, 1729, 2465, 2821, 6601,
8911 і т.д.

15.

ОСНОВНА ТЕОРЕМА АРИФМЕТИКИ
Теорема. Будь-яке ціле додатне число може бути
подано у вигляді добутку простих чисел,
причому єдиним чином (з точністю до порядку
співмножників).
Приклади.
64 = 26 .
100 = 22 * 52 .
17 = 17.
55 = 5 * 11.
30 = 2 * 3 * 5.

16.

ВЗАЄМНО ПРОСТІ ЧИСЛА
Два числа називаються взаємно простими, якщо
в них немає спільних дільників, крім 1.
Приклади.
Пари взаємно простих чисел: (15,8), (2,3), (100,
99), (1000,3), (45,17).
Пари не взаємно простих чисел: (3,15), (100,20),
(30,40), (28,35).
Властивість. Просте число є взаємно простим із
будь-яким меншим за нього числом.
Приклад. Число 11 взаємно просте з числами від
2 до 10.

17.

ФУНКЦІЯ ЕЙЛЕРА
Нехай дано ціле додатне число N. Значення
функції Ейлера φ(N) дорівнює кількості чисел
серед 1,2,3,...,N-1, які взаємно прості з N.
Приклад.
Обчислимо φ(15).
15 = 3*5.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14.
φ(15) = 8.

18.

ВЛАСТИВІСТЬ ФУНКЦІЇ ЕЙЛЕРА - 1
Твердження. Якщо p - просте, то φ(p) = p-1.
Доказ. Оскільки число p - просте, то в нього
немає дільників, крім 1 і p.
Отже, p може бути не взаємно простим тільки з
тими числами, серед дільників яких є p.
Очевидно, що будь-яке таке число має бути
більшим або дорівнювати p.
Таким чином, у ряді від 1 до p-1 таких чисел
немає, отже, φ(p) дорівнює кількості чисел у
цьому ряді - з усього p-1. ■

19.

ВЛАСТИВІСТЬ ФУНКЦІЇ ЕЙЛЕРА - 2
Твердження. Нехай p і q - це прості і p≠q, тоді
φ(pq) = (p-1)(q-1).
Доказ. Позначимо N=pq. Числа, які не взаємно
прості з N - це ті, серед дільників яких є p або
q. Випишемо їх:
Діляться на p: p, 2p, 3p, 4p, ... , (q-1)p.
Діляться на q: q, 2q, 3q, 4q, ... , (p-1)q.
У першому ряду q-1 чисел, а в другому - p-1.
Отже, φ(N) = (N-1) - ((q-1)+(p-1)) = (p-1)(q-1). ■

20.

ДВІ ТЕОРЕМИ
Теорема (Ейлер). Якщо a і b взаємно прості, то
aφ(b) = 1 mod b.
Теорема. Якщо p і q - прості й не дорівнюють
одне одному, то для довільного цілого k
виконується akφ(pq)+1 = a mod pq.

21.

НАЙБІЛЬШИЙ СПІЛЬНИЙ
ДІЛЬНИК
Найбільший спільний дільник чисел a і b - це
найбільше з усіх чисел, які ділять і a, і b.
Позначення.
НОД(a,b) або GCD(a,b).
Англ. - Найбільший спільний дільник.
Приклади.
НОД(100,10) = 10; НОД(45,27) = 9;
НОД(100,99) = 1; НОД(17,30) = 1.
Числа є взаємно простими тоді й тільки тоді, коли
їхній найбільший спільний дільник дорівнює 1.

22.

НАЙМЕНШЕ СПІЛЬНЕ КРАТНЕ
Найменшим спільним кратним двох чисел
називається найменше число з усіх, які
діляться на обидва ці числа.
Обчислення НОК
НОК(a,b) = a*b/НОД(a,b).
Приклади
НОК(6,9) = 6*9/3 = 18;
НОК(10,100) = 10*100/10 = 100;
НОК(24,18) = 24*18/6 = 72.

23.

ОБЧИСЛЕННЯ НСД (НАЇВНИЙ
ПОВІЛЬНИЙ АЛГОРИТМ)
Алгоритм. Вхід a і b.
m := min(a,b);
НОД := 1;
Цикл i від 2 до m
Якщо i ділить a і b Тоді
НОД := i;
Відповідь - НОД;

24.

АЛГОРИТМ ЕВКЛІДА
Властивість.
НОД(a,b) = НОД(a mod b, b).
НОД(0,a) = a.
Алгоритм. Вхід: a і b, де a≥b.
Поки b≠0
t := a mod b;
a := b;
b := t;
Відповідь - a

25.

АЛГОРИТМ ЕВКЛІДА
(РЕКУРСИВНИЙ ВАРІАНТ)
Функція НОД(a,b)
m := min(a,b);
M := max(a,b);
Якщо m=0 Тоді
Відповідь - M;
Інакше
Відповідь НОД(M mod m, m);
Приклад.

26.

ДІОФАНТОВЕ РІВНЯННЯ
(ОКРЕМИЙ ВИПАДОК)
Теорема. Нехай дано цілі додатні числа a і b.
Тоді існують цілі (не обов'язково додатні) числа
x і y, такі, що
ax+by = НОД(a,b).
Приклади.
a=93, b=53.
НОД(93,53)=1
93*4 + 53*(-7) = 1
a=100, b=68.
НОД(100,68)=4
100*(-2) + 68*3 = 4

27.

РОЗШИРЕНИЙ (УЗАГАЛЬНЕНИЙ
АЛГОРИТМ ЕВКЛІДА)
Вхід: Цілі додатні числа a і b, де a≥b.
Вихід: x, y і НОД(a,b), де x і y задовольняють
розглянутому діофантовому рівнянню.
Алгоритм.
Позначимо U = (u1 ,u2 ,u3 ), V = (v1 ,v2 ,v3 ) і T
(t1 ,t2 ,t3 ).
U := (a,1,0), V := (b,0,1).
Поки v1≠0
q := u1 div v1;
T := (u1 mod v1, u2-qv2, u3-qv3);
U := V; V := T;
Відповідь - u1 = НОД(a,b); u2 = x; u3 =

28.

РОЗШИРЕНИЙ АЛГОРИТМ
ЕВКЛІДА (ПРИКЛАД)
a=93, b=53.
93 1 0
53 0 1
40 1 -1 q=1
13 -1 2 q=1
1 4 -7 q=3
0 -53 93 q=13
НОД(93,53)=1
x=4, y=-7
Перевірка:
93*4 + 53*(-7) = 1

29.

ПОНЯТТЯ ІНВЕРСІЇ
Інверсією числа c за модулем m називається таке
число 0<d<m, яке задовольняє співвідношенню
cd mod m = 1.
Позначення.
Часто використовується позначення d = c-1 mod
m.
У цьому разі можна записати cc-1 mod m = 1.
Приклади.
1 = 1 mod m, 28*31 mod 51 = 1, 3*4 mod 11 = 1.

30.

ОБЧИСЛЕННЯ ІНВЕРСІЇ
Дано: Взаємно прості числа c і m.
Знайти: c-1 mod m.
За визначенням інверсії cc-1 mod m = 1. Згідно з
визначенням залишку від ділення ця рівність
означає, що існує k, за якого cc-1 = km + 1 або
cc-1 - km = 1.
Позначимо a:=m, b:=c, x:=-k, y:=c-1 і отримаємо
діофантове рівняння: ax + by = НОД(a,b).
Таким чином, для обчислення інверсії потрібно
розв'язати діофантове рівняння за a:=m, b:=c,
а потім з-1 :=y або c-1 :=y+m, якщо y<0.

31.

ОБЧИСЛЕННЯ ІНВЕРСІЇ
(ПРИКЛАД)
c=19, m=68.
68 0
19 1
11 -3 q=3
8 4 q=1
3 -7 q=1
2 18 q=2
1 -25 q=1
0 68 q=2
НОД(68,19)=1, y=-25, c-1 = 68-25 = 43
Перевірка: 19*43 mod 68 = 1

32.

ЛІТЕРАТУРА
Рябко Б.Я., Фіонов О.М.
Розділ 2, параграф 2.3.
Черемушкін А.В.
Лекції з арифметичних алгоритмів у
криптографії. Розділ I і III.
(електронний варіант книги лежить в
обміннику).

33.

ЗАВДАННЯ (СТОР. 1)
1.
Написати функцію, яка приймає як аргумент ціле
число і повертає true, якщо число - просте, і false інакше.
2.
Написати функцію, яка приймає як аргументи два
цілих числа і повертає true, якщо вони - взаємно
прості, і false - інакше.
Написати програму, яка приймає як аргумент ціле
число і виводить на екран його розкладання на прості
множники в такому вигляді: 360 = 2^3 * 3^2 * 5.
Написати функцію, яка приймає як аргумент ціле
число і повертає значення функції Ейлера від цього
числа.
3.
4.

34.

ЗАВДАННЯ (СТОР. 2)
1.
Написати функцію, яка приймає як аргументи два
цілих числа і повертає їхній найбільший спільний
дільник.
2.
Написати функцію, яка приймає як аргументи два
цілих числа і повертає їхнє найменше спільне кратне.
Написати програму, яка приймає як аргументи числа
a і b і повертає структуру з трьох полів: x, y і
НОД(a,b), що є розв'язком діофантового рівняння з
параметрами a і b.
Написати функцію, яка приймає як аргументи
взаємно прості числа c і m і повертає інверсію числа c
за модулем m.
3.
4.