Generar un par de claves RSA

8

Dado un entero positivo N>=4 , genera un par de claves RSA (tanto la clave privada como la pública) cuya longitud de clave es N bits.

El algoritmo de generación de claves RSA es el siguiente:

  1. Elija un N bit semiprime n . Deje que los factores primos de n sean p y q .
  2. Calcule λ(n)=LCM(p1,q1) .
  3. Elija un número entero e tal que 1<e<λ(n) y GCD(e,λ(n))=1 .
  4. Calcule .de1(modλ(n))

La clave pública se compone de y e . La clave privada es d .ned

Reglas

  • Es posible suponer que existe al menos un semiprimo n con la longitud de bits N .
  • La salida puede estar en cualquier formato coherente y sin ambigüedades.
  • e yn deben elegirse entre distribuciones uniformes discretas.
  • Puede suponer que N es menor o igual que el número máximo de bits para enteros representables en su idioma, si su idioma tiene tal restricción.
Mego
fuente
Sandbox
Mego
¿Puedo usar utilidades RSA existentes en un envío bash?
Pavel
1
Entonces, ¿desea específicamente la distribución uniforme en todos los semiprimes de N bits?
Misha Lavrov
1
¿Existe realmente una solución para ? Creo que tenemos en ese caso, lo que hace que sea imposible elegir . λ ( n ) 2 eN=3λ(n)2e
Arnauld
2
Además, recomiendo encarecidamente vincular a la pila de cifrado para obtener una explicación sobre los primos de N bits en el contexto de RSA, o explicar mejor el concepto en la pregunta, ya que no es obvio.

Respuestas:

2

JavaScript (ES7), 190 bytes

Las devoluciones [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)

Pruébalo en línea!

Debido al tamaño limitado de la pila de llamadas, esto puede fallar 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)
Arnauld
fuente
1

Jalea , 30 29 27 26 bytes

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

Pruébalo en línea!

Explicación

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)
PurkkaKoodari
fuente
0

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 en b (x) encontraría el bit len ​​de x; randnum (x) con x un entero positivo sería una función que devuelve un número pseudoaleatorio en el rango 0 .. (x-1); P en P (n) encontraría un primo pseudoaleatorio en el rango 2 ^ (n-1) .. (2 ^ n-1) [longitud de ese rango 2 ^ n-1-2 ^ (n-1) = 2 ^ (n-1) -1]; R en R (n) encontraría [n, e, d] como dice el ejercicio.

(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
RosLuP
fuente