RSA parameter generator algorithm

gerasia

4/12/23, 5:21 PM

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$

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)$

0 + 0

rsa

kelalaka

4/12/23, 5:27 PM

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...

gerasia

4/12/23, 5:30 PM

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?

kelalaka

4/12/23, 5:31 PM

What about the [Wikipedia's RSA Key-gen?](https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation). Yours almost sound like it! And, **could be accepted for what?**

gerasia

4/12/23, 5:32 PM

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)

kelalaka

4/12/23, 5:47 PM

Interesting that a crypto class doesn't mention this properly. Edit your question so that we can review it.

Maarten Bodewes

4/12/23, 7:08 PM

A note on terminology. With "parameter generation" we generally talk about (domain) parameters that are identical for all the key pairs generated using the key pair generation algorithm (usually just identified as $\text{Gen}$). In this case you just generate the keys themselves not so much the parameters as RSA doesn't require any - maybe the key size and often the public exponent, as mentioned. For elliptic curves the parameters are the parameters that define the curve (usually represented using a name or OID - a named curve).

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: RSA parameter generator algorithm

TH: อัลกอริทึมตัวสร้างพารามิเตอร์ RSA

RO: Algoritmul generator de parametri RSA

RU: Алгоритм генератора параметров RSA

VI: Thuật toán tạo tham số RSA

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.