I

stnieje możliwość odzyskania prywatnego klucza RSA tylko na podstawie klucza publicznego. Ze względu na ograniczoną moc obliczeniową poniższy przykład zostanie zaprezentowany na 256 bitowym kluczu. Tak skromna długość kluczy raczej nie występuje już w Internecie, ale czasami można natknąć się jeszcze na 512 bitowe instalacje (aktualnie OpenSSH za pomocą programu ssh-keygen nie pozwala na wygenerowanie krótszego klucza niż 768 bitów).

Na początek użyjemy OpenSSL do wygenerowania pary kluczy:

root@darkstar:~# openssl genrsa -out test.pem 256
Generating RSA private key, 256 bit long modulus
..+++++++++++++++++++++++++++
.+++++++++++++++++++++++++++
e is 65537 (0x10001)

root@darkstar:~# cat test.pem
-----BEGIN RSA PRIVATE KEY-----
MIGrAgEAAiEA6Pd155jmTU0aVcRcG48OLclDvhLwpAY8v0G8Q6HF/ccCAwEAAQIh
AKDJqmad8NWJUZPAYpHiujUuPIYtAf8uzQsSZgT1yGaBAhEA/rzyWYGAbsH9WbHD
RJaPvQIRAOoe52FeOguAlnFoRm6tadMCEQCXg0KSQhhlyDQsWTLPZM3xAhABSw5o
IUcczScHlVXeQqL1AhA3GvyzUj0cvc6hchqHRVBM
-----END RSA PRIVATE KEY-----

Z tak wygenerowanej pary wydzielimy tylko klucz publiczny, który posłuży nam do dalszego łamania prywatnego:

root@darkstar:~# openssl rsa -in test.pem -pubout > test.pub
writing RSA key

root@darkstar:~# cat test.pub
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAOj3deeY5k1NGlXEXBuPDi3JQ74S8KQG
PL9BvEOhxf3HAgMBAAE=
-----END PUBLIC KEY-----

Za pomocą PyCrypto (The Python Cryptography Toolkit) możemy z powyższego klucza wyciągnąć liczby n (moduł) oraz e (publiczny wykładnik):

apt-get install python-pip
pip install pycrypto

>>>> from Crypto.PublicKey import RSA
>>>> pub = RSA.importKey("""-----BEGIN PUBLIC KEY-----
... MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAOj3deeY5k1NGlXEXBuPDi3JQ74S8KQG
... PL9BvEOhxf3HAgMBAAE=
... -----END PUBLIC KEY-----""")
>>>> n = long(pub.n)
>>>> e = long(pub.e)
>>>> print n
105373805844490526703657838368339073503292646751969764907846382341563452095943
>>>> print e
65537

Za pomocą programu msieve na podstawie n możemy obliczyć liczby pierwsze p i q. Jest to najbardziej czasochłonny proces w przypadku dłuższych kluczy. Dla 256 bitów obliczenia na procesorze Intel Atom N2800 o taktowaniu 1.86GHz zajęły 11 minut:

apt-get install subversion zlib1g-dev libgmp-dev
cd msieve-1.52
make all

Msieve v. 1.52 (SVN Unversioned directory)
Mon Nov 17 22:59:53 2014
random seeds: 52dbfd5a 835fac20
factoring 105373805844490526703657838368339073503292646751969764907846382341563452095943
no P-1/P+1/ECM available, skipping
commencing quadratic sieve (78-digit input)
using multiplier of 7
using generic 32kb sieve core
sieve interval: 12 blocks of size 32768
processing polynomials in batches of 17
using a sieve bound of 924097 (36406 primes)
using large prime bound of 92409700 (26 bits)
using trial factoring cutoff of 26 bits
polynomial 'A' values have 10 factors

sieving in progress (press Ctrl-C to pause)
36750 relations (19085 full + 17665 combined from 193690 partial), need 36502
36750 relations (19085 full + 17665 combined from 193690 partial), need 36502
sieving complete, commencing postprocessing
begin with 212775 relations
reduce to 52240 relations in 2 passes
attempting to read 52240 relations
recovered 52240 relations
recovered 41830 polynomials
attempting to build 36750 cycles
found 36750 cycles in 1 passes
distribution of cycle lengths:
   length 1 : 19085
   length 2 : 17665
largest cycle: 2 relations
matrix is 36406 x 36750 (5.3 MB) with weight 1095985 (29.82/col)
sparse part has weight 1095985 (29.82/col)
filtering completed in 4 passes
matrix is 25669 x 25733 (4.0 MB) with weight 849519 (33.01/col)
sparse part has weight 849519 (33.01/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 25621 x 25733 (2.5 MB) with weight 591542 (22.99/col)
sparse part has weight 401314 (15.60/col)
commencing Lanczos iteration
memory use: 2.5 MB
lanczos halted after 407 iterations (dim = 25621)
recovered 18 nontrivial dependencies
prp39 factor: 311199812870338329446654643767241173459
prp39 factor: 338604978173282558596154093984850284477
elapsed time 00:11:04

Posiadając liczby pierwsze p oraz q jesteśmy w stanie obliczyć prywatny wykładnik d:

apt-get install python-gmpy

>>>> import gmpy
>>>> p = 311199812870338329446654643767241173459
>>>> q = 338604978173282558596154093984850284477
>>>> d = long(gmpy.invert(e,(p-1)*(q-1)))
>>>> print d
72726368096769695040356612983150174293476067375324035984310469524811869087361

Ostatnim krokiem jest odtworzenie prywatnego klucza RSA:

>>>> key = RSA.construct((n,e,d))
>>>> print key.exportKey()
-----BEGIN RSA PRIVATE KEY-----
MIGrAgEAAiEA6Pd155jmTU0aVcRcG48OLclDvhLwpAY8v0G8Q6HF/ccCAwEAAQIh
AKDJqmad8NWJUZPAYpHiujUuPIYtAf8uzQsSZgT1yGaBAhEA/rzyWYGAbsH9WbHD
RJaPvQIRAOoe52FeOguAlnFoRm6tadMCEQCXg0KSQhhlyDQsWTLPZM3xAhABSw5o
IUcczScHlVXeQqL1AhA3GvyzUj0cvc6hchqHRVBM
-----END RSA PRIVATE KEY-----
>>>> print key.publickey().exportKey()
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAOj3deeY5k1NGlXEXBuPDi3JQ74S8KQG
PL9BvEOhxf3HAgMBAAE=
-----END PUBLIC KEY-----

RSA organizowała otwarte zawody (RSA Factoring Challenge) w łamaniu kluczy o coraz to dłuższej ilości bitów. Za rozłożenie niektórych z nich wyznaczono pieniężną nagrodę. Najmniejsza z nich, 100-cyfrowa liczba RSA-100 została rozłożona w ciągu kilku dni, ale większość do dziś pozostaje niezłamana.

Więcej informacji: Regenerating an RSA private key with Python