Краткий алгоритм создания открытого и закрытого ключа для алгоритма RSA
1. Для двух случайных простых чисел P и Q вычисляем N=PQ, и Fi=(P-1)(Q-1)
2. Выбираем e такое что: НОД(e, Fi) = 1 и 1 < e < F i
3. Выбираем d и e такие, что: de=1 | Fi
4. (e,n) - есть открытый ключ. (d,n) - есть закрытый кюч.
(В данный момент желательная длина ключей есть 1024 бит.)
Алгоритм шифрования/дешифрования
5. Encrypt(M)=(M^e) mod N
6. Decrypt(M)=(M^d) mod N
Где M -целое число от 0 до N-1
Доказательство корректности 5-6
Требуется доказать, что
((M^e)^d) mod N=((M^d)^e) mod N=M
Из (3) следует, что de = 1+s*(p-1)*(q-1)
По Малой Теореме Ферма, которая является следствием теоремы Лагранжа для конечных групп
"Если M не делится на простое число P, то M^(p-1)=1 | P"
А) Допустим P не делит M =>
Т.к. M ^ (P-1) = 1 |P => M^(p-1)*(q-1)*s=1^((q-1)*s)|P=1|P =>
M*M^(s(p-1)^(q-1))=M|P=>
M(1+s(p-1)^(q-1))=M | P =>
M^de=M|mod p (*)
Б) Если P делит M cоотношение (*) становится практически очевидным (справа и слева от уравнения будут стоят нулевые значения)
Аналогично доказывается
M^de=M|mod q (**)
Таким образом (M^de - M) делится простыми числами q и p (без остатка)
Таким образом (M^de - M) = 0 | PQ => M^de = M | N
Замечание:
Если ослабить требвоание к P, Q, потребовав от них того, что они будут являться лишь псведвопростыми числами - то доказательство верности алгоритма будет затруднительным.
Оценку времени для генерации случайных простых чисел возможно сделать с учетом Теоремы о распределении случайных чисел