Cracking the RSA keys (Part 2 – generating the private key)

by

in

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

PART 2
For a private key generation, we need to create an asn1parse.txt file with the contents of:

asn1=SEQUENCE:rsa_key

[rsa_key]
version=INTEGER:0
modulus=INTEGER:0
pubExp=INTEGER:0
privExp=INTEGER:0
p=INTEGER:0
q=INTEGER:0
e1=INTEGER:0
e2=INTEGER:0
coeff=INTEGER:0

Explanation:
Modulus – it’s the product of two prime keys. It’s visible in public key.
pubExp – public exponent, it’s also visible in public key.
privExp – private exponent (d) that was calculated in previous post.
p – first prime number
q – second prime number
So we have all these from a previous post.

We are missing 3 private key values. They are easy calculable, and they are only auxilary private key values to speedup encryption and other processes.
I’ve used for calculations wolframalpha.
e1 – first exponent

e1 = d mod (p - 1) = 42081396264635804076297698591471521526036226546344296111866129299947306543297 mod (299565145299812070871826362285166503457 - 1) = 32864998317067439607678586826225600193



e2 – second exponent

e2 = d mod (q - 1) = 42081396264635804076297698591471521526036226546344296111866129299947306543297 mod (267166959046601000378504971553629664723 - 1) = 245112650054091251503095479265225610735



coeff – coefficient

coeff = q^-1 mod p = 267166959046601000378504971553629664723^-1 mod 299565145299812070871826362285166503457 = 189941519478868394433951698467035418490



Lets fill up the file with our values (as I’ve mentioned before, some of the values are from the previous post here). All the values are decimal:

asn1=SEQUENCE:rsa_key

[rsa_key]
version=INTEGER:0
modulus=INTEGER:80033908906103969695821767102622510991943039576059641379772648172129130447411
pubExp=INTEGER:65537
privExp=INTEGER:42081396264635804076297698591471521526036226546344296111866129299947306543297
p=INTEGER:299565145299812070871826362285166503457
q=INTEGER:267166959046601000378504971553629664723
e1=INTEGER:32864998317067439607678586826225600193
e2=INTEGER:245112650054091251503095479265225610735
coeff=INTEGER:189941519478868394433951698467035418490

Now it’s the last part. Generating the private key itself:

$ openssl asn1parse -genconf asn1parse.txt -out private.key
    0:d=0  hl=3 l= 171 cons: SEQUENCE
    3:d=1  hl=2 l=   1 prim: INTEGER           :00
    6:d=1  hl=2 l=  33 prim: INTEGER           :B0F1964FC7E0F5E42761113373D9997079707D00A45AFE22B0EE96E2FF910233
   41:d=1  hl=2 l=   3 prim: INTEGER           :010001
   46:d=1  hl=2 l=  32 prim: INTEGER           :5D0939EA8B033AE712D993ECC4DE4631A04A25569E048D739FA550702456E8C1
   80:d=1  hl=2 l=  17 prim: INTEGER           :E15E25FB1A1B49BD68EE34C6081D2621
   99:d=1  hl=2 l=  17 prim: INTEGER           :C8FE7C1289D112FD420D1DBB6E6DF5D3
  118:d=1  hl=2 l=  16 prim: INTEGER           :18B9918528EA117EFC4215FC1BEBC6C1
  136:d=1  hl=2 l=  17 prim: INTEGER           :B866FAB00B6F1D0BEBF09AA99E8C15EF
  155:d=1  hl=2 l=  17 prim: INTEGER           :8EE567EFEC27324AD3CC45063B520F7A

And here You go:

$ openssl rsa -in private.key -inform der -text -check
Private-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
publicExponent: 65537 (0x10001)
privateExponent:
    5d:09:39:ea:8b:03:3a:e7:12:d9:93:ec:c4:de:46:
    31:a0:4a:25:56:9e:04:8d:73:9f:a5:50:70:24:56:
    e8:c1
prime1:
    00:e1:5e:25:fb:1a:1b:49:bd:68:ee:34:c6:08:1d:
    26:21
prime2:
    00:c8:fe:7c:12:89:d1:12:fd:42:0d:1d:bb:6e:6d:
    f5:d3
exponent1:
    18:b9:91:85:28:ea:11:7e:fc:42:15:fc:1b:eb:c6:
    c1
exponent2:
    00:b8:66:fa:b0:0b:6f:1d:0b:eb:f0:9a:a9:9e:8c:
    15:ef
coefficient:
    00:8e:e5:67:ef:ec:27:32:4a:d3:cc:45:06:3b:52:
    0f:7a
RSA key ok
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MIGrAgEAAiEAsPGWT8fg9eQnYREzc9mZcHlwfQCkWv4isO6W4v+RAjMCAwEAAQIg
XQk56osDOucS2ZPsxN5GMaBKJVaeBI1zn6VQcCRW6MECEQDhXiX7GhtJvWjuNMYI
HSYhAhEAyP58EonREv1CDR27bm310wIQGLmRhSjqEX78QhX8G+vGwQIRALhm+rAL
bx0L6/CaqZ6MFe8CEQCO5Wfv7CcyStPMRQY7Ug96
-----END RSA PRIVATE KEY-----

rsa-logo
Now let’s match:

-----BEGIN RSA PRIVATE KEY-----
MIGrAgEAAiEAsPGWT8fg9eQnYREzc9mZcHlwfQCkWv4isO6W4v+RAjMCAwEAAQIg
XQk56osDOucS2ZPsxN5GMaBKJVaeBI1zn6VQcCRW6MECEQDhXiX7GhtJvWjuNMYI
HSYhAhEAyP58EonREv1CDR27bm310wIQGLmRhSjqEX78QhX8G+vGwQIRALhm+rAL
bx0L6/CaqZ6MFe8CEQCO5Wfv7CcyStPMRQY7Ug96
-----END RSA PRIVATE KEY-----

with the public key that we had:

-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhALDxlk/H4PXkJ2ERM3PZmXB5cH0ApFr+
IrDuluL/kQIzAgMBAAE=
-----END PUBLIC KEY-----

Lets create files public_rsa.txt and private_rsa.txt with the keys accordingly.

$  openssl rsa -noout -modulus -in public_rsa.txt -pubin | openssl md5
(stdin)= 6b139f2f6606bbdafea11fb4158f90ad
$  openssl rsa -noout -modulus -in private_rsa.txt | openssl md5
(stdin)= 6b139f2f6606bbdafea11fb4158f90ad

To me, they look the same :)

The final word:
Do not forget to use strong keys when generating keys. >2048bits is advised.


Comments

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.