Файл: Вопросы Криптография основные термины.pdf

Что для нас важно?
Главным образом в криптографии используются НАТУРАЛЬНЫЕ числа.
Мы не работаем с дробными, иррациональными и комплексными числами.
В криптографии используются целые числа!!!
Целые числа делятся на:
• простые;
• составные.
Целое число d является делителем n, тогда и только тогда, когда можно записать произведение n = k · d и записывается d | n.
Целое число р (р≥1) является простым, если его делителями являются только 1 и р. Например: 2, 3, 5, 7, 11, 13, 17<и т.д. Числа, имеющие более 2–х делителей являются составными.
Целые числа

Любое целое число n>1 может быть представлено единственным образом как произведение простых чисел в соответствующих степенях.
Такое представление называется каноническим разложением Евклида.
Процедура получения такого разложения называется разложением на простые
сомножители или факторизацией числа.
На настоящий момент не известны быстрые алгоритмы разложения чисел.
На этом основаны большинство современных криптосистем.
Получение простых чисел является одной из основных задач криптографии.
Евклид показал, что существует бесконечное множество простых чисел, однако их удельный вес среди других чисел невелик.

Алгоритмы получения простых чисел
Один из первых алгоритмов был предложен во времена Евклида.
Базируется на следующих теоремах:

Алгоритм Эратосфена построения последовательности простых чисел в ряду целых
чисел, не превосходящих данного целого N.
Выписываем ряд чисел 1,2,<, N (1.6)
Первое простое число в ряду (1.6) – 2. Вычеркиваем из ряда (1.6) все числа кратные 2, кроме самого числа 2. Первое, оставшееся после 2, простое число – 3. Вычеркиваем из ряда (1.6) все числа кратные 3, кроме самого числа 3. Первое, следующее за 3, невычеркнутое простое число 5. Вычеркиваем из ряда (5) все числа кратные 5, кроме числа 5. И т.д.
Когда указанным способом вычеркнуты все числа, кратные простых, меньше простого p, то все невычеркнутые меньшие ????
2
будут простые.

Пример.
2, 3, 4, 5, 6, 7, 8, 9, 10.
√10 ≈ 3 2, 3 < 10 => вычеркиваем те числа, которые делятся на 2 и 3. Все оставшиеся после вычеркивания числа – простые. Попытка формальным образом определить простые числа привела к отрицательному результату.

Составные числа

Определение
Если a делится на b нацело, мы будем говорить, что b
делит a.
При этом а называется кратным числа b, b – делителем числа а. Число а можно представить как
a = q *b , где q – полное частное.

Таким образом, k представляется произведением b на целое число ( и тем самым делится на b по определению l. Что и требовалось доказать.

Бинарный алгоритм
Определение. Два числа называются попарно простыми, если их НОД равен 1
Пример

Алгоритм Евклида
Исторически одним из первых инструментов определения взаимно простых чисел стал алгоритм Евклида.

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

Расширенный алгоритм Евклида

Расширенный алгоритм Евклида

Одним из существенных недостатков алгоритма
Евклида является применение операций деления. Это увеличивает его вычислительную сложность.

Пример
Доказать, являются ли числа попарно простыми:

Алгебраические свойства

Что еще для нас важно?
В криптографии как правило используется не бесконечное множество натуральных чисел, а вполне себе конечное.
О чем речь? Об алгебраических структурах.
Алгебраическая структура
– некоторое множество элементов (не обязательно чисел) с определенных на ней операциях алгебры.
То есть их бывает много? Как правило 9.
Чтобы понять в чем их отличие нужно разобрать некоторые алгебраические свойства

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

Какие алгебраические свойства у операции бывают?
Коммутативность
– свойство операции ∘ при которой a ∘ b
= b ∘ a
Сможете сказать какие известные вам операции являются коммутативными?
1) Конечно же + (известно со школы – от перестановки слагаемых сумма не меняется). 3+2 = 2+3. Еще?
2) Произведение. Ее, вы знали. 3*2 = 2*3. Может что-то из дискретной математики?
3) Молодец! Конъюнкция и дизъюнкция. А из теории множеств?
4) Объединение, пересечение и симметрическая разность. Супер!
∧
∨
+
∙
∪
∩

Ок, это было просто, а какие тогда не коммутативны?
1) Хм. Это ты сам догадался или мне послышалось?
Возведение в степень
, да. 2 3
≠ 3 2
2) Матрицы, матрицы... Ага.
Перемножение матриц
!

Какие они бывают?
Ассоциативность
– свойство операции ∘ при которой
(a ∘ b) ∘ c = a ∘ (b ∘ c). Тут и без примеров поймете (:
Дистрибутивность
– определяется как проявление двух бинарных операций (бинарные – операции над двумя элементами)
(возьмем ∘ и ∴) для которых (a ∘ b) ∴ c = a ∴ c ∘ b ∴ c.
Сложно? Да бросьте!
Например, для операций (+, *): (a+b)*c = a*c + b*c
Идемпотентность
– когда повторная операция уже не меняет значения. Например, −5 = 5; −5 = 5 и тд. Сколько бы не брали модуль от модуля ничего уже не изменится  Даже обидно.

Вроде разобрались. У нас есть некоторые операции и свойства этих операций. А еще мы будем работать с натуральными числами.
Все супер, переходим к алгебраическим структурам.

Так так так стоп! Ничего не понятно, что за нейтральный элемент
, что за обратный элемент и нужны же примеры
!
Ок, справедливо. Давайте разберѐмся.

Кольцо
- Множество с двумя операциями (сложение и умножение), обладающими свойством ассоциативности
(a ∙ b) ∙ c = a ∙ (b ∙ c), (a+b)+c=a+(b+c)
- При этом сложение коммутативно
???? + ???? = ???? + ????
- Имеется нейтральный элемент по сложению
???? + 0 = 0 + ???? = ????
- Имеется обратный элемент по сложению
???? + −???? = −???? + ???? = 0
- Выполняется дистрибутивность этих двух операций
???? + ???? ∙ ???? = ???? ∙ ???? + (???? ∙ ????)
???? ∙ ???? + ???? = ???? ∙ ???? + (???? ∙ ????)

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