Buat pasangan kunci RSA

8

Dengan bilangan bulat positif , mengeluarkan pasangan kunci RSA (baik kunci privat dan publik) yang panjang kuncinya adalah bit.N>=4N

Algoritma pembuatan kunci RSA adalah sebagai berikut:

  1. Pilih semiprime bit . Biarkan faktor utama menjadi dan .Nnnpq
  2. Hitung .λ(n)=LCM(p1,q1)
  3. Pilih bilangan bulat sehingga dan .e1<e<λ(n)GCD(e,λ(n))=1
  4. Hitung de1(modλ(n)) .

Kunci publik terdiri dari n dan e . Kunci pribadi adalah d .

Aturan

  • Anda mungkin berasumsi bahwa ada setidaknya satu semiprime n dengan panjang bit N .
  • Output mungkin dalam format yang konsisten dan tidak ambigu.
  • e dann harus dipilih dari distribusi seragam diskrit.
  • Anda dapat mengasumsikan bahwa N kurang dari atau sama dengan jumlah bit maksimum untuk bilangan bulat yang dapat diwakili dalam bahasa Anda, jika bahasa Anda memiliki batasan seperti itu.
Mego
sumber
Sandbox
Mego
Apakah saya diizinkan menggunakan utilitas RSA yang ada dalam pengiriman bash?
Pavel
1
Jadi Anda secara spesifik menginginkan distribusi seragam pada semua semiprim N-bit?
Misha Lavrov
1
Apakah benar ada solusi untuk ? Saya pikir kita memiliki dalam kasus itu, yang membuatnya tidak mungkin untuk memilih . N=3λ(n)2e
Arnauld
2
Selain itu, saya sangat menyarankan untuk menghubungkan ke tumpukan crypto untuk penjelasan tentang N-bit primes dalam konteks RSA, atau lebih baik menjelaskan konsep dalam pertanyaan, karena itu bukan yang jelas.

Jawaban:

2

JavaScript (ES7), 190 byte

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

Cobalah online!

Karena ukuran tumpukan panggilan yang terbatas, ini mungkin gagal untuk .N>13

Berkomentar

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
sumber
1

Jelly , 30 29 27 26 byte

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

Cobalah online!

Penjelasan

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
sumber
0

Aksioma, 230 byte

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 dalam b (x) akan menemukan bit len ​​dari x; randnum (x) dengan x satu bilangan bulat positif akan menjadi satu fungsi yang mengembalikan satu nomor pseudorandom dalam kisaran 0 .. (x-1); P dalam P (n) akan menemukan satu prime pseudorandom di kisaran 2 ^ (n-1) .. (2 ^ n-1) [panjang rentang itu 2 ^ n-1-2 ^ (n-1) = 2 ^ (n-1) -1]; R dalam R (n) akan menemukan [n, e, d] seperti yang dikatakan latihan.

(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
sumber