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)