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
Sandbox – Mego – 2018-11-06T01:24:05.157
Am I allowed to use existing RSA utils in a bash submission? – Pavel – 2018-11-06T01:30:11.260
@Pavel Yes, though, as always, including a solution that doesn't use builtins is encouraged. – Mego – 2018-11-06T01:33:55.047
1So you specifically want the uniform distribution over all N-bit semiprimes? – Misha Lavrov – 2018-11-06T01:42:49.887
@MishaLavrov Yes. – Mego – 2018-11-06T01:43:35.817
Are we required to make sure that $p\neq q$? – Arnauld – 2018-11-06T06:54:26.500
1Is 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 – 2018-11-06T07:26:37.463
But "4.Compute d≡e −1 (modλ(n)) d≡e−1(modλ(n))" would require invmod function, and not many programming languages have one invmod function... or I remember wrong? – RosLuP – 2018-11-06T09:23:49.153
@Arnauld A semiprime can be the product of two equal primes. – Erik the Outgolfer – 2018-11-06T16:35:11.867
@EriktheOutgolfer Sure, but my concern was that if $n$ is a perfect square, it can be trivially factorized -- making it a very inefficient RSA key. That said, I realize that such issues are probably off-topic for this challenge. :) – Arnauld – 2018-11-06T16:40:20.923
@Arnauld You're right - there is not a solution for $N = 3$. Also, distinctness is not necessary - RSA technically only requires that $p$ and $q$ are both prime, but if they are equal, it is very weak, so it is usually stated that they are distinct. – Mego – 2018-11-06T19:39:28.807
Are you sure that you have private and public keys the right way around? Given $n$ and $e$, it is relatively trivial to compute $d$... – None – 2018-11-06T19:39:50.443
@Rogem It is not trivial, because it requires factoring $n$. – Mego – 2018-11-06T19:40:58.007
Also, you might want to require that programs must finish in a reasonable time. Else picking random $n$, factoring the primes, etc. becomes a very attractive option in certain languages. – None – 2018-11-06T19:49:01.810
2
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.
– None – 2018-11-06T19:57:14.517The 'uniform distribution' for me it is better not on n but on the 2 primes because one time one has n 'uniform distribution' one has to factor n and more can be n=3*(n/3) if n is divisible for 3 and n/3 is prime (possible I not know what semi-prime means) – RosLuP – 2018-11-07T07:17:52.200
If a number has length in bit one number not divisible for 2, is it possible break it in 2 number both have exact bit length? – RosLuP – 2018-11-08T11:46:48.940