Генерация ключа алгоритма RSA

Question

Я в настоящее время борется с RSA encryption algorythm.

Моя проблема находится в генерации ключа в public/private, вот мои шаги:

1. -Generate 2 prime numbers p, q with p > q and nbBits(p) == nbBits(q) 
      using the miller-rabin algorythm this was done succesfully 
2. -compute n = p*q 
3. -compute fi(n) = (p-1)*(q-1) 

Вот приходит беда: мне нужно найти одно целое число е с q < e < fi(n). Это целое число должно иметь какую-то примитивность.

Мой вопрос: должен ли он быть первым (не может быть разделен на любое число, кроме самого себя или 1) ИЛИ первично С fi(n) (gcd(e, fi(n)) = 1) ИЛИ оба?

У меня действительно есть некоторые проблемы, полагая, что из (мой источник ясно заявляет Euclide алгоритм (НОД) необходим, но так как английский язык не мой родной язык у меня есть некоторые проблемы с математической английский язык)

Вероятно немой вопрос, но я не мог найти ясного объяснения этого (по крайней мере, достаточно ясного для меня).

Спасибо за чтение, еще больше за ответ.

Answer 1

Показатель шифрования e должен быть сопоставлен с phi(n), то есть gcd(e,phi(n)) = 1. Это условие необходимо, так как в противном случае вы не сможете построить (через расширенный алгоритм Евклида) показатель d (показатель дешифрования), такой как e*d = 1 mod phi(n).