Dado um número inteiro positivo $N >= 4$ , produza um par de chaves RSA (tanto a chave privada quanto a pública) cujo tamanho da chave é $N$ bits.

O algoritmo de geração de chaves RSA é o seguinte:

1. Escolher um $N$ -bit semiprimo $n$ . Deixe os fatores primos de $n$ serem $p$ e $q$ .
2. Calcular $\lambda(n) = LCM(p-1, q-1)$ .
3. Escolha um número inteiro $e$ tal que $1 < e < \lambda(n)$ e $GCD(e, \lambda(n)) = 1$ .
4. Calcule .$d \equiv e^{−1} \pmod {\lambda(n)}$

A chave pública é composta por e . A chave privada é .$n$$e$$d$

Regras

• Pode-se presumir que existe pelo menos um semiprimo com comprimento de bits .$n$$N$
• A saída pode estar em qualquer formato consistente e inequívoco.
• $e$ e devem ser escolhidos entre distribuições uniformes discretas.$n$
• Você pode assumir que é menor ou igual ao número máximo de bits para números inteiros representáveis ​​no seu idioma, se o seu idioma tiver essa restrição.$N$

JavaScript (ES7), 190 bytes

Retorna [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)

Experimente online!

Devido ao tamanho limitado da pilha de chamadas, isso pode falhar para $N>13$ .

Comentado

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)

Geléia , 30 29 27 26 bytes

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

Experimente online!

Explicação

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)

Axioma, 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 em b (x) encontraria o bit len ​​de x; randnum (x) com x um número inteiro positivo seria uma função que retornaria um número pseudo-aleatório no intervalo 0 .. (x-1); P em P (n) encontraria um primo pseudoaleatório no intervalo 2 ^ (n-1) .. (2 ^ n-1) [comprimento desse intervalo 2 ^ n-1-2 ^ (n-1) = 2 ^ (n-1) -1]; R em R (n) encontraria [n, e, d] como o exercício diz.

(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