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.
1
2
3
4
|
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhALDxlk/H4PXkJ2ERM3PZmXB5cH0ApFr+
IrDuluL/kQIzAgMBAAE=
-----END PUBLIC KEY----
|
Lets convert it to a more ‘mathematical’ expression:
1
2
3
4
5
6
7
|
$ 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:
1
|
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:
1
2
|
$ 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:
1
2
|
$ echo "ibase=16; 00B0F1964FC7E0F5E42761113373D9997079707D00A45AFE22B0EE96E2FF910233" |bc
80033908906103969695821767102622510991943039576059641379772648172129130447411
|
For digit factorization, I’ve used yafu (Yet Another Factoring Utility)
Ok, let’s factor the digit:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
~/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:
in other words, it’s a reverse public exponent by a modulus of Euler function.
Euler function may be calculated using:
p and q are the prime numbers that we’ve found.
So,
1
|
φ(n) = (p – 1)(q – 1) = (299565145299812070871826362285166503457 - 1)(267166959046601000378504971553629664723 -1) = 8003390890610396969582176710262251099137630747171322830852231683829033427923
|
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:
1
|
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)