8
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Sandbox \$\endgroup\$ – Mego Nov 6 '18 at 1:24
  • \$\begingroup\$ Am I allowed to use existing RSA utils in a bash submission? \$\endgroup\$ – Pavel Nov 6 '18 at 1:30
  • 1
    \$\begingroup\$ So you specifically want the uniform distribution over all N-bit semiprimes? \$\endgroup\$ – Misha Lavrov Nov 6 '18 at 1:42
  • 1
    \$\begingroup\$ 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\$. \$\endgroup\$ – Arnauld Nov 6 '18 at 7:26
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – user77406 Nov 6 '18 at 19:57
2
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

Jelly, 30 29 27 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)
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.