The whole idea of the RSA private key is the hardness of factorisation of two very large prime numbers.
That’s why recommended RSA keys are >2048bit long.
I won’t get into RSA details itself. If You need any info, it’s here: WIKI
For a sake of demonstration, 256bit public_key will be used. With the current hardware that we have these days, it’s very easy crackable.
-----BEGIN PUBLIC KEY----- MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhALDxlk/H4PXkJ2ERM3PZmXB5cH0ApFr+ IrDuluL/kQIzAgMBAAE= -----END PUBLIC KEY-----
Lets convert it to a more ‘mathematical’ expression:
$ openssl rsa -noout -text -inform PEM -in vr_RSA29.pem -pubin
Public-Key: (256 bit)
Modulus:
00:b0:f1:96:4f:c7:e0:f5:e4:27:61:11:33:73:d9:
99:70:79:70:7d:00:a4:5a:fe:22:b0:ee:96:e2:ff:
91:02:33
Exponent: 65537 (0x10001)
Ok, so the public key consists of Modulus (product of two prime numbers) and a public exponent:
00:b0:f1:96:4f:c7:e0:f5:e4:27:61:11:33:73:d9:99:70:79:70:7d:00:a4:5a:fe:22:b0:ee:96:e2:ff:91:02:33
Let’s get rid of colons and convert all the letters to a uppercase to be prepared for a conversion:
$ echo '00:b0:f1:96:4f:c7:e0:f5:e4:27:61:11:33:73:d9:99:70:79:70:7d:00:a4:5a:fe:22:b0:ee:96:e2:ff:91:02:33' | sed -e 's/://g' | tr 'a-z' 'A-Z' 00B0F1964FC7E0F5E42761113373D9997079707D00A45AFE22B0EE96E2FF910233
Conversion to a decimal:
$ echo "ibase=16; 00B0F1964FC7E0F5E42761113373D9997079707D00A45AFE22B0EE96E2FF910233" |bc 80033908906103969695821767102622510991943039576059641379772648172129130447411
For digit factorization, I’ve used yafu (Yet Another Factoring Utility)
Ok, let’s factor the digit:
~/yafu> ./yafu 11/23/15 15:36:05 v1.34.5 @ server.loginroot.com, System/Build Info: Using GMP-ECM 6.4.4, Powered by GMP 5.1.1 detected QEMU Virtual CPU version (cpu64-rhel6) detected L1 = 32768 bytes, L2 = 4194304 bytes, CL = 64 bytes measured cpu frequency ~= 3392.201950 using 20 random witnesses for Rabin-Miller PRP checks =============================================================== ======= Welcome to YAFU (Yet Another Factoring Utility) ======= ======= bbuhrow@gmail.com ======= ======= Type help at any time, or quit to quit ======= =============================================================== cached 78498 primes. pmax = 999983 >> factor(80033908906103969695821767102622510991943039576059641379772648172129130447411) fac: factoring 80033908906103969695821767102622510991943039576059641379772648172129130447411 fac: using pretesting plan: normal fac: no tune info: using qs/gnfs crossover of 95 digits starting SIQS on c77: 80033908906103969695821767102622510991943039576059641379772648172129130447411 ==== sieving in progress ( 4 threads): 36224 relations needed ==== ==== Press ctrl-c to abort and save state ==== SIQS elapsed time = 1.9259 seconds. Total factoring time = 1.9639 seconds ***factors found*** P39 = 299565145299812070871826362285166503457 P39 = 267166959046601000378504971553629664723 ans = 1
Factorisation may take a while depending on the number lenght. My case was very fast because it cached the results. The first time run this command for this digit it took around 1 minute with 4threads (You may set the thread count in yafu.ini file)
So our digit is a product of two prime numbers 299565145299812070871826362285166503457 and 267166959046601000378504971553629664723.
This is the part, that for longer keys takes forever. That’s why the >2048bit keys currently are counted as unbreakable.
Lets go on, shall we?
Private exponent is calculated with formula:
e^–1 mod φ(n)
in other words, it’s a reverse public exponent by a modulus of Euler function.
Euler function may be calculated using:
φ(n) = (p – 1)(q – 1)
p and q are the prime numbers that we’ve found.
So,
φ(n) = (p – 1)(q – 1) = (299565145299812070871826362285166503457 - 1)(267166959046601000378504971553629664723 -1) = 80033908906103969695821767102622510991376307471713228308522316838290334279232
Ok, so now only private exponent is left.
For that we need the public exponent that we saw in public key, so the whole calculation looks like this:
d=e^–1 mod φ(n) = 65537^-1 mod 80033908906103969695821767102622510991376307471713228308522316838290334279232=42081396264635804076297698591471521526036226546344296111866129299947306543297
It would be hard to calculate these things with the simple calculator, so I’ve used the WolframAlpha for that.
That’s it. The private exponent is 42081396264635804076297698591471521526036226546344296111866129299947306543297.
Next: Cracking the RSa keys (Part 2 – generating the private key)
Nice ..