В2: Что такое функция Эйлера, используемая в RSA, и как она вычисляется

RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом. В криптографической системе с открытым ключом каждый участник располагает как открытым ключом, так и закрытым ключом. В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их.

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

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

2)Вычисляется их произведение n=p*q.

3)Вычисляется значение функции Эйлера от числа: φ(n)= (p-1)(q-1).

Функция Эйлера φ(n), где n — натуральное число, равна количеству натуральных чисел, меньших и взаимно простых с ним.

4)Выбирается целое число e (1<e<φ(n)), взаимно простое со значением функции. Обычно в качестве e берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма 17, 257 или 65537.

Число e называется открытой экспонентой. Слишком малые значения, например 3, потенциально могут ослабить безопасность схемы RSA. 5) Вычисляется число d, мультипликативно обратное к числу e по модулю φ(n), то есть число, удовлетворяющее условию: de = 1 modφ(n). Число d называется секретной экспонентой. Пара e,n публикуется в качестве открытого ключа RSA.Пара d,n играет роль закрытого ключа RSA и держится в секрете.