i'm studying for my basic crypto class and I'm trying to formalize the algorithm for the parameter generation of RSA, unfortunately, I cannot find any algorithm, just plain text.

Can someone tell me if this algorithm could be accepted? Please focus more on the public exponent $e$

  1. KeyGen()

    1. Let $p,q$ be two random prime numbers
    2. $N\leftarrow pq$
    3. $\phi(N)=(p-1)(q-1)$
    4. $e\xleftarrow{R}\{x|\;0< x < \phi(N) \land x\in \mathbb{N} \land gcd(x,\phi(N))=1 \}$ // $\xleftarrow{R}$ means that the element is chosen randomly
    5. calculate $d$ such that $ed\equiv 1 \pmod{\phi(N)}$
    6. $PK\leftarrow (N,e)$
    7. $SK\leftarrow (N,d)$
    8. return $(pk,sk)$
  • 1
    $\begingroup$ Ideally the $e$ is selected on advance, when $\gcd(e,\phi(n))\neq 1$ we select new randoms. The key-gen should take a security parameter like $1^{2048}$ to determine the modulus size... $\endgroup$
    – kelalaka
    Dec 12 '21 at 17:27
  • $\begingroup$ yup i got it but i would like to avoid the while loop as hell, just to make the code clean. Said that the definition of the set Is correct? $\endgroup$
    – gerasia
    Dec 12 '21 at 17:30
  • $\begingroup$ What about the Wikipedia's RSA Key-gen?. Yours almost sound like it! And, could be accepted for what? $\endgroup$
    – kelalaka
    Dec 12 '21 at 17:31
  • $\begingroup$ omg thank you, i don't know how but I missed it. By accepted I mean that could be okay to write that code in a basic crypto class exam (of course followed by a more verbal explanation) $\endgroup$
    – gerasia
    Dec 12 '21 at 17:32
  • $\begingroup$ Interesting that a crypto class doesn't mention this properly. Edit your question so that we can review it. $\endgroup$
    – kelalaka
    Dec 12 '21 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.