Простое число. Количество простых чисел. Основная теорема арифметики

 

Простое число – это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя.

Количество простых чисел бесконечно велико – доказательство Эвклида:

«Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор. Противоречие.»

 

Основная теорема арифметики: любое число не равное нулю или может быть разложено на произведение простых чисел в некоторых степенях и такое разложение единственно.

Основная теорема арифметики может быть распространена и на другие кольца(множества с заданной операцией умножения), но в некоторых из них разложение не будет единственно.

 

32. Функция Эйлера. Вычисление функции Эйлера, в частности, функция Эйлера простого числа и произведения двух простых чисел: примеры.

Ф-ция Эйлера – возвращает кол-во натуральных чисел меньше ее аргумента, которые имеют с ним НОД =1(взаимно просты).

Для простого числа – возвращает значение на 1 меньше его самого(Поскольку любое число меньше простого взаимно просто с ним).

Для произведения двух простых чисел a и b: phi(a*b)=(a-1)*(b-1)

Доказательство. Очевидно, что всего натуральных чисел меньше произведения а*b ровно a*b-1. Из них все числа: 1*b,2*b,….,(a-1)*b – имеют c ab НОД=b и не являются взаимно простыми. Этих чисел b-1. Аналогично 1*a,2*a,….,(b-1)*a – имеют c ab НОД=a. Этих чисел всего a-1. Если предположить, что эти набора чисел не имеют общих элементов, то взаимно простых чисел остается ровно: ab-1-(a-1)-(b-1)=ab-a-b+1=(a-1)(b-1). Т. к. и a и b простые, то наборы чисел будут иметь общие элементы, только в случае, когда a=b и значит они совпадают тождественно и значит вычитать следует только один из них. Тогда, если a=b: phi(a*a)=a*a-a=a*(a-1)

Примеры:

phi(13)=12

phi(21)= phi(3*7)=2*6=12

phi(9)=3*(3-1)=6

 

33. Теорема Эйлера и ее доказательство, малая теорема Ферма: примеры.

 

Если a и m взаимно просты, то , где φ(m) — функция Эйлера.

Читается, как: a, возведенное в степень функции Эйлера от m, и взятое по модулю m тождественно единице.

Доказательство:

Пусть — все различные натуральные числа, меньшие m и взаимно простые с ним.

Рассмотрим всевозможные произведения x_i*a для всех i от 1 до φ(m).

Поскольку a взаимно просто с m и x_i взаимно просто с m, то и x_i*a также взаимно просто с m, то есть для некоторого j.

Отметим, что все остатки x_i*a при делении на m различны. Действительно, пусть это не так, то есть существуют такие , что

Или

Так как a взаимно просто с m, то последнее равенство равносильно тому, что

или .

Это противоречит тому, что числа попарно различны по модулю m.

Перемножим все равенства . Получим:

или

Так как число взаимно просто с m, то последнее равенство равносильно тому, что

или

 

Пример:a=3 m=8

φ(8)=4

(3⁴) mod 8=(81) mod 8 = 1

 

Малая теорема Ферма – частный случай теоремы Эйлера, основывающийся на значении функции Эйлера от простого числа: если m – простое, то

 

 

34. Способы деления чисел в конечном простом поле: примеры. Алгоритм быстрого вычисления степеней числа.

 

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

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

Пусть нужно найти: на поле ограниченном простым числом p

Возьмем соотношение Безу для p и b: . Так как p – простое, то . Если взять это соотношение по модулю p, то получится:

, т. к. , то

 

Либо, исходя из малой теоремы Ферма, т. к. то и , а значит

Примеры:

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

a	b	c	d	x1	x2	y1	y2
							-2
					-1	-2
				-1	-2		-5

 

Малая теорема Ферма:

 

Алгоритм быстрого возведения в степень — алгоритм, предназначенный для возведения числа x в натуральную степень n за меньшее число умножений, чем это требуется в определении степени.

Рассмотрим двоичное представление степени, в которую требуется возвести число x

где .

Тогда алгоритм примет вид:

Задача факторизации больших чисел и криптографическая система RSA. Общая схема и пример шифрования и дешифрования. Достоинства и недостатки. Рекомендации о длине ключа RSA Labs и NIST. Стойкость к атаке полным перебором.

 

Задача факторизации больших чисел – это задача разложения числа N на произведение простых чисел. Это NP задача.

 

RSA использует эту задачу для построения однонаправленной функции с секретом.

 

RSA-ключи генерируются следующим образом:

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

1. Вычисляется их произведение , которое называется модулем.
2. Вычисляется значение функции Эйлера от числа :

1. Выбирается целое число (), взаимно простое со значением функции . Обычно в качестве берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма 17, 257 или 65537.
2. Число называется открытой экспонентой
3. Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в .
4. Слишком малые значения , например 3, потенциально могут ослабить безопасность схемы RSA.
5. Вычисляется число , мультипликативно обратное к числу по модулю , то есть число, удовлетворяющее условию:
6. 
7. Число называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.
8. Пара публикуется в качестве открытого ключа RSA.
9. Пара играет роль закрытого ключа RSA и держится в секрете.

 

Общая схема работы:

Шифрование:

 

Расшифрование:

 

Пример: p=7, q=13, m=10

n=7*13=91;

e=17;

 

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

a	b	c	d	x1	x2	y1	y2
							-4
					-4	-4

 

Задача нахождения дискретного логарифма в конечном поле и криптографическая система ElGamal. Общая схема и пример шифрования и дешифрования. Достоинства и недостатки. Стойкость к атаке полным перебором.

 

Задача нахождения дискретного логарифма в конечном поле: любой элемент поля есть некая степень примитивного элемента этого поля. Нахождения показателя степени по элементу (дискретного логарифма) – NP задача.

Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи.

Генерация ключа:

1. Генерируется случайное простое число длины битов.
2. Выбирается случайный примитивный элемент поля .
3. Выбирается случайное целое число такое, что .
4. Вычисляется .
5. Открытым ключом является тройка , закрытым ключом — число .

Общая схема:

Шифрование:

Сообщение шифруется следующим образом:

Выбирается сессионный ключ — случайное целое число такое, что

Вычисляются числа и .

Пара чисел является шифротекстом.

Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения вдвое.

 

Расшифрование

Зная закрытый ключ , исходное сообщение можно вычислить из шифротекста по формуле:

При этом нетрудно проверить, что

и поэтому

.

Для практических вычислений больше подходит следующая формула:

 

 

Пример: p=11, g=2. M=9, x=4,k=8

Шифрование:

Шифротекст: (3,3)

Расшифрование

 

37. Целостность. Избыточность как способ обеспечения целостности данных. Классификация методов. Код аутентификации сообщения (имитовставка). Функция хеширования и ее свойства. Сжимающая функция (структура Merkle–Damgard).

 

Задача обеспечения целостности – заключается в необходимости удостовериться, не были ли внесены изменения в исходные данные, не зная их заранее. Если избыточность данных равна 0, то обеспечить их целостность невозможно. Поэтому для решения задача целостности избыточность вносится в данные специально.

Процесс контроля целостности обеспечивается введением в передаваемую информацию избыточности. Это достигается добавлением к сообщению некоторой проверочной комбинации. Такая комбинация вычисляется согласно определенным алгоритмам и играет роль индикатора, с помощью которого проверяется целостность сообщения. Именно этот момент дает возможность проверить, были ли изменены данные третьей стороной. Дополнительную избыточную информацию, вносимую в сообщение, называют имитовставкой.

 

m – исходное сообщение

h = f(m) – контрольная последовательность исходного сообщения

m’ – принятое сообщение

h’ = g(m’) – контрольная последовательность принятого сообщения

Если h=h’, то с большой вероятностью и m=m’

Методы:

1. – симметричные
2. – ассиметричные

h – также называется хэш значением, имитовставкой или кодом аутентификации сообщения(MAC)

Свойства хэш функции y=f(x):

1. Незначительное изменение x должно вести к значительному изменению y.

2. Множество значений у < множества значений x, поэтому для x может существовать x’, для которого f(x)= f(x’). Поиск x’ по x должен быть NP задачей Для исключения атаки полным перебором длина х>64 бит

3. f(x) – однонаправленная функция. Обратное преобразование должно быть NP задачей

4. Сама f(x) – P задача и должна вычисляться быстро.

Для выполнения пункта 3 можно использовать сжимающую функцию с потерей, в этом случае речь идет о хэш функции, построенной по структуре Merkle–Damgard:

Структура Меркла-Дамгарда — метод построения криптографических хеш-функций. Криптографическая хеш-функция должна преобразовывать входное сообщение произвольной длины в выходное сообщение фиксированной длины. Этого можно достичь путём разбиения входного сообщение на блоки одинакового размера и их последовательной обработки односторонней функцией сжатия, которая преобразовывает входное сообщение фиксированной длины в более короткое выходное сообщение фиксированной длины. Функция сжатия либо может быть специально построена для хеширования либо может представлять собой функцию блочного шифрования. Хеш-функция Меркла-Дамгарда разбивает входное сообщение на блоки и работает с ними по очереди с помощью функции сжатия, каждый раз принимая входной блок с выходным от предыдущего раунда.