Каждый участник информационного обмена генерирует пару ключей (открытый и секретный) в соответствии со следующими правилами:
1. Выбираются два больших простых целых числа р и q приблизительно одинакового размера. Выбор чисел р и q определяется следующими соображениями:
- увеличение порядка чисел ведет к замедлению операции зашифровывания / расшифровывания;
- увеличение порядка чисел р и q ведет к увеличению стойкости алгоритма. Поэтому, при выборе чисел следует руководствоваться практической необходимостью.
Так, например, при реализации RSA в интеллектуальных карточках с точки зрения скоростных параметров системы не следует выбирать слишком большие р и q в связи с ограниченными вычислительными возможностями, заложенными в данных устройствах. На практике обычно рекомендуется выбирать числа, содержащие порядка 150-200 десятичных знаков.
2. Вычисляется модуль системы n = pq и ф(п) = (р- l)(q - 1) - функция Эйлера.
3. Выбирается достаточно большое число е, удовлетворяющее условию 1 < е < ф(п), и взаимно простое с (р(п).
4. Используя расширенный алгоритм Евклида, вычисляется большое целое число d, отвечающее условию:
ed = 1 (mod
Таким образом, секретным ключом является пара чисел (n, d), а открытым - пара чисел (п, е). Открытый ключ помещается в общедоступный справочник (детально этот процесс будет описан ниже). В соответствии с PKCS # 1 формат представления ключей имеет следующий вид:
