Generowanie kluczy algorytmów RSA

Question

Aktualnie walczę z RSA encryption algorythm.

Mój problem znajduje się na generowaniu kluczy public/private, oto moje kroki:

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) 

Nadchodzi problemy: Muszę znaleźć się jedna liczba całkowita e z q < e < fi(n). Ta liczba całkowita musi mieć jakąś pierwotność.

Moje pytanie: czy e musi być pierwotne (nie może być podzielone przez żadną liczbę inną niż ona sama lub 1) LUB pierwotne Z fi(n) (gcd(e, fi(n)) = 1) LUB jedno i drugie?

naprawdę mam pewne problemy ze zorientowaniem się, że (moja źródło wyraźnie stwierdza Euclide algorytm (NWD) jest potrzebna, ale ponieważ angielski nie jest mój język ojczysty mam pewne problemy z matematycznego angielskim)

Prawdopodobnie niemych pytanie, ale nie mogłem znaleźć jasnego wytłumaczenia tego (przynajmniej dla mnie wystarczająco jasne).

Dzięki za przeczytanie, tym bardziej, że odpowiadasz.

Answer 1

Wykładnik szyfrowania e musi być koprime z phi(n), czyli gcd(e,phi(n)) = 1. Ten warunek jest konieczny, ponieważ w przeciwnym razie nie będzie można zbudować (za pomocą rozszerzonego algorytmu Euclid) wykładnika d (wykładnik deszyfrowania) w taki sposób, że e*d = 1 mod phi(n).