Cracking the RSA keys (Part 1 – getting the private exponent)

by

in

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
rsa-logo
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)


Comments

2 responses to “Cracking the RSA keys (Part 1 – getting the private exponent)”

  1. […] разобраться со всем этим, в гугле нашёл хорошую статью, которая мне очень помогла. Хочу сразу уточнить то, что […]

  2.  Avatar
    Anonymous

    Nice ..

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.