Дополнительный материал

Факторизация целых чисел

Что это?

Факторизация целых чисел — это процесс разложения числа на простые множители, то есть такие множители, которые не могут быть разделены на другие числа, кроме 1 и самого себя.

Зачем это нужно?

Факторизация лежит в основе криптографических алгоритмов, таких как RSA. Безопасность RSA основана на сложности факторизации больших чисел. Если бы мы могли быстро факторизовать большие числа, мы могли бы легко взломать шифры, использующие RSA.

RSA (Rivest-Shamir-Adleman)

Что это?

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

Как он работает ?

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

• Выбираются два больших простых числа p и q
• Вычисляется их произведение n=p×q
• Вычисляется функция Эйлера ϕ(n)=(p−1)×(q−1)
• Выбирается число e (открытый ключ), которое взаимно простое с ϕ(n)
• Вычисляется число d (закрытый ключ), которое является мультипликативным обратным к e по модулю ϕ(n)

2. Шифрование:

• Сообщение mmm шифруется как c=m^e mod n

3. Расшифровка:

• Зашифрованное сообщение ccc расшифровывается как m=c^d mod n

Зачем это нужно?

RSA используется для безопасной передачи данных и создания цифровых подписей, подтверждающих подлинность отправителя.

Задача дискретного логарифма

Что это?

Задача дискретного логарифма заключается в нахождении такого числа x, что для данного основания g и модуля p, выражение gx≡h (mod p) выполняется. Проще говоря, нужно найти x, зная g, h и p.

Зачем это нужно?

Эта задача является основой для многих криптографических протоколов, таких как Диффи-Хеллман и алгоритмы цифровой подписи (например, DSA). Их безопасность основывается на сложности решения задачи дискретного логарифма.

Диффи-Хеллман (Diffie-Hellman)

Что это?

Диффи-Хеллман — это криптографический протокол, позволяющий двум сторонам безопасно обмениваться секретным ключом по незащищённому каналу.

Как работает?

Обмен параметрами:

• Обе стороны договариваются о большом простом числе ppp и основании ggg (публичные параметры).

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

• Каждая сторона выбирает случайное секретное число a и b
• Сторона A вычисляет A = g^a mod p и отправляет A стороне B.
• Сторона B вычисляет B=g^b mod p и отправляет B стороне A.

Вычисление общего секрета:

• Сторона A вычисляет общий секрет s=B^a mod p
• Сторона B вычисляет общий секрет s=A^b mod p

DSA (Digital Signature Algorithm)

Что это?

DSA — это стандарт цифровой подписи, основанный на задаче дискретного логарифма.

Как работает?

1. Генерация ключей:
• Выбирается простое число p, q (меньшее простое число, делящее p−1), и основание g.
• Выбирается случайное число x (секретный ключ).
• Вычисляется y=g^x mod p (открытый ключ).
2. Подпись сообщения:
• Вычисляется хэш сообщения m.
• Генерируется случайное число k.
• Вычисляются параметры подписи r и s.
3. Проверка подписи:
• Используются r, s, y, g, p для проверки подлинности хэша сообщения.

Задачи на эллиптических кривых

Что это?

Эллиптические кривые — это множества точек, удовлетворяющих определенному уравнению, которое имеет вид y^2=x^3+ax+b. Задача дискретного логарифма на эллиптических кривых аналогична обычной задаче дискретного логарифма, но проводится на группе точек эллиптической кривой.

Зачем это нужно?

Эллиптические кривые используются в криптографии (например, алгоритм ECC - Elliptic Curve Cryptography) благодаря своей эффективности и безопасности. Криптосистемы на основе эллиптических кривых обеспечивают такую же безопасность, как и системы на основе RSA, но с гораздо меньшими размерами ключей, что делает их быстрее и экономичнее.

ECC (Elliptic Curve Cryptography)

Что это?

ECC — это метод криптографии, использующий свойства эллиптических кривых для создания более эффективных и безопасных криптографических алгоритмов.

Как работает?

1. Генерация ключей:
• Выбирается эллиптическая кривая и начальная точка G.
• Выбирается случайное число d (секретный ключ).
• Вычисляется точка Q=d×G (открытый ключ).
2. Шифрование и подпись:
• Могут использоваться различные алгоритмы, такие как ECDH (Elliptic Curve Diffie-Hellman) для обмена ключами и ECDSA (Elliptic Curve Digital Signature Algorithm) для цифровой подписи.