# Generate an RSA key pair

Given a positive integer $$\N >= 4\$$, output an RSA key pair (both the private and the public key) whose key length is $$\N\$$ bits.

The RSA key generation algorithm is as follows:

1. Choose an $$\N\$$-bit semiprime $$\n\$$. Let the prime factors of $$\n\$$ be $$\p\$$ and $$\q\$$.
2. Compute $$\\lambda(n) = LCM(p-1, q-1)\$$.
3. Choose an integer $$\e\$$ such that $$\1 < e < \lambda(n)\$$ and $$\GCD(e, \lambda(n)) = 1\$$.
4. Compute $$\d \equiv e^{−1} \pmod {\lambda(n)}\$$.

The public key is composed of $$\n\$$ and $$\e\$$. The private key is $$\d\$$.

## Rules

• You may assume that there exists at least one semiprime $$\n\$$ with bit length $$\N\$$.
• Output may be in any consistent and unambiguous format.
• $$\e\$$ and $$\n\$$ must be chosen from discrete uniform distributions.
• You may assume that $$\N\$$ is less than or equal to the maximum number of bits for integers representable in your language, if your language has such a restriction.
• Sandbox – Mego Nov 6 '18 at 1:24
• Am I allowed to use existing RSA utils in a bash submission? – Pavel Nov 6 '18 at 1:30
• So you specifically want the uniform distribution over all N-bit semiprimes? – Misha Lavrov Nov 6 '18 at 1:42
• Is there really a solution for $N=3$? I think we have $\lambda(n)\le2$ in that case, which makes it impossible to choose $e$. – Arnauld Nov 6 '18 at 7:26
• Furthermore, I highly recommend linking to the crypto stack for an explanation on N-bit primes in the context of RSA, or better explaining the concept in the question, as it is not an obvious one. – user77406 Nov 6 '18 at 19:57

# JavaScript (ES7), 190 bytes

Returns [n,e,d].

f=N=>(R=Math.random,g=d=>d&&p%--d?g(d):d)(p=g(p=n=R()*2**N|0))<2&n>1&(L=(q=n/p-1)*--p/(G=(a,b)=>b?G(b,a%b):a)(p,q))>2?(g=_=>G(L,e=R()*(L-2)+2|0)<2?(h=d=>d*e%L<2?[n,e,d]:h(-~d))():g())():f(N)


Try it online!

Because of the limited size of the call stack, this may fail for $$\N>13\$$.

### Commented

f = N =>
(
R = Math.random,
// helper function returning the highest divisor of p
g = d => d && p % --d ? g(d) : d
)(
// choose n and compute its highest divisor p
p = g(p = n = R() * 2 ** N | 0)
)
// make sure that p is prime
< 2 &
// and that n is greater than 1
n > 1 &
// compute L = λ(n) = LCM(p - 1, q - 1) = (p - 1) * (q - 1) / GCD(p - 1, q - 1),
// using the helper function G that returns GCD(a, b)
(L = (q = n / p - 1) * --p / (G = (a, b) => b ? G(b, a % b) : a)(p, q))
// make sure that L > 2
> 2 ?
// helper function to choose e such that GCD(e, L) = 1
(g = _ => G(L, e = R() * (L - 2) + 2 | 0) < 2 ?
// helper function to compute d such that d * e mod L = 1
(h = d => d * e % L < 2 ? [n, e, d] : h(-~d))()
:
g()
)()
:
f(N)


# Jelly, 302927 26 bytes

2*µrHÆfL2=ƲƇXṄÆcµgÐṂḊXṄæi


Try it online!

### Explanation

2*µrHÆfL2=ƲƇXṄÆcµgÐṂḊXṄæi    Main link. Arg: N
2*                            Compute 2^N
µ                           Begin a new chain. Arg: 2^N
H                         Compute 2^N/2
r                          Get all N-bit numbers (plus 2^N)
Ʋ                     Group the following. Arg: num
Æf                         Prime factors of num
L                        Number of prime factors of num
2=                      See if it is 2
Ƈ                  Filter by the above block
This gets N-bit semiprimes
X                 Choose n at random
Ṅ                Print n
Æc              Compute λ(n)
µ             Begin a new chain. Arg: λ(n)
gÐṂ         Find all 1≤x≤λ(n) with minimal GCD(x,λ(n))
Ḋ        Remove the 1 from the candidates
This gets candidates for e
X       Choose e at random
Ṅ      Print e
æi    Compute d = e⁻¹ mod λ(n)


# Axiom, 230 bytes

b(x)==(1+floor log_2 x)::INT
P(n)==nextPrime(2^(n-1)::NNI+randnum(2^(n-1)::NNI))
R(n)==(n<4=>-1;k:=n quo 2;repeat(p:=P(k+1);q:=P(k);b(p*q)=n=>break);l:=lcm(p-1,q-1);repeat(e:=2+randnum(l-2);gcd(e,l)=1=>break);[p*q,e,invmod(e,l)])


b in b(x) would find the bit len of x; randnum(x) with x one positive integer would be one function that return one pseudorandom number in the range 0..(x-1); P in P(n) would find one pseudorandom prime in range 2^(n-1)..(2^n-1) [lenght of that range 2^n-1-2^(n-1)=2^(n-1)-1]; R in R(n) would find [n,e,d] as the exercise says.

(15) -> a:=R 23
Compiling function P with type Integer -> Integer
Compiling function b with type Integer -> Integer
Compiling function R with type PositiveInteger -> Any
Compiling function G1452 with type Integer -> Boolean
(15)  [4272647,824717,1001213]
Type: List Integer
(16) -> b %.1
Compiling function b with type PositiveInteger -> Integer
(16)  23
Type: PositiveInteger
(17) -> factor a.1
(17)  1061 4027
Type: Factored Integer
(18) -> (a.2*a.3) rem lcm(1061-1,4027-1)
(18)  1
Type: PositiveInteger
(19) -> a:=R 23
(19)  [5215391,932257,1728433]
Type: List Integer
(20) -> R 2048
(20)
[23213251353270373502637714718370965847258432024211176383232570158843901982_
8374419721867989228927344460592814980635585372922578037879152449312504744_
2861913195543965318695967745717301811727824635815211233105475881576100225_
3632803572317998112861757923774382346449223053928741441134006614228292016_
5273067128098814936149948557863692935433292700177694639931896886174791595_
2591510100576556786861493463332533151814120157258896598771272703168867259_
1059421044639753552393378020089166512073314575563837723165164503239565057_
8157637522454347226109931834702697646569048737623886830735628816778282907_
16962402277453801137600520400279
,
26277208914513047097872541919539499189114183243456446871374032261842172481_
1782225662860226419702820497403134660912654534465780004169047137965180193_
9424240720814436784731953475388628791624586090011147747029161125853374433_
7624317473301390727052150821160711361987569549572011227572161234939947570_
1006480714726838475136080877420539301562592505847293621815149245444744497_
0146019787431225138564647562282720244978299356752301570039442420559831909_
1396109771341727891989553783027544302642531934746013600522012136408967482_
8591443211475273074214579546316395151724707332850441864609728119186620471_
5116079141878558542286273118499
,
37945816199160687259342706646596754136573392197139994836682676167798393778_
9533248999943052484273349085225287510658624414105052824140785833431676303_
9819497567439525931938766580464486131713424225091467044692614132161523472_
3141843691744552674894778838275993887411876266402821208140118598964705638_
4930606996298811686240430389336754369834390870340241699155004906972042503_
8705910893788941005489353671521480377818624793497995264157466810522707258_
4139749164641845206614670777070059395273813452365545085917304619784119668_
4846093245280478965642073804885084960796597065443090998925258186802193768_
8791746419960588307023018400019]
Type: List Integer
`