Use RSA public key to generate private key in Openssl?

Question

I know that it is possible using this link to generate a public and a private key for self-signed certificate in OpenSSL. But for a given Public Key, is it possible for me to figure out the corresponding Private Key? I have been using a 1024-bit RSA public key.

Because I had this question in my homework saying:

Generate a digital signature for the sentence “My name is . My voice is my passport.” that verifies correctly using OpenSSL with the following 1024-bit RSA public key. (Hint: The modulus might not have been generated like a normal RSA modulus.):

-----BEGIN PUBLIC KEY-----
MIGdMA0GCSqGSIb3DQEBAQUAA4GLADCBhwKBgQCgF35rHhOWi9+r4n9xM/ejvMEs
Q8h6lams962k4U0WSdfySUevhyI1bd3FRIb5fFqSBt6qPTiiiIw0KXte5dANB6lP
e6HdUPTA/U4xHWi2FB/BfAyPsOlUBfFp6dtkEEcEKt+Z8KTJYJEerRie24y+nsfZ
MnLBst6tsEBfx/U75wIBAw== 
-----END PUBLIC KEY-----

Solution

The key (pun intended) to the solution is in the hint:

The modulus might not have been generated like a normal RSA modulus.

This is the approach I took.

Step 1: Derive the primes

1. I first took your file and saved it as public.pem.
2. To get the value of the modulus (n) and the public exponent (e), I ran:
   openssl rsa -pubin -in public.pem -text -noout
3. I converted the hexadecimal modulus and exponent to decimal numbers, which yielded
   n=112420265940019545385580931264662691888876377549063413938338239508058300548918731393322848876821656910452908064089039911552450302375557565600923056341141750687524704844725632296552824986371719004485250857447936962589230504662333990648942759862805127715014382377701044586628936249950092121536791020138692688871
e=3
4. I plugged that number into an online factorialization calculator to discover that one of the two primes used to calculate the modulus was relatively small:
   p=55685342628135644993
q=2018848419246646476894946094575564515176862561629979956283227393349426117194195173357244644821277073710795134539986018769393928719340504755806449531413017314396784334912136112253736003497362080917517151753555605597776865614151048604681116557282512513238254935296910445878892354969335089447

Step 2: Calculate other required values

1. I calculated the totient of n as ϕ(n) = (p - 1) * (q - 1) using the python REPL:
   ϕ(n)=112420265940019545383562082845416045411981431454487849423161376946428320592635503999973422759627461737095663419267762837841655167835571546831529127621801245931718255313312614982156040651459582892231514853950574881671713352908778385051165894248654079110333265820418532073390681314653181675602213322541221954432
2. I then used the python script from this answer to calculate the private exponent (d) and the coefficient (c), which yielded:
   d=74946843960013030255708055230277363607987620969658566282107584630952213728423669333315615173084974491397108946178508558561103445223714364554352751747867497287812170208875076654770693767639721928154343235967049921114475568605852256700777262832436052740222177213612354715593787543102121117068142215027481302955
c=1040291110785843997

Step 3: Create the private key's ASN.1 structure

I then used the calculated values to create an ASN.1 structure in a file named asn as described in this answer:

asn1=SEQUENCE:rsa_key

[rsa_key]
version=INTEGER:0
modulus=INTEGER:112420265940019545385580931264662691888876377549063413938338239508058300548918731393322848876821656910452908064089039911552450302375557565600923056341141750687524704844725632296552824986371719004485250857447936962589230504662333990648942759862805127715014382377701044586628936249950092121536791020138692688871
pubExp=INTEGER:3
privExp=INTEGER:74946843960013030255708055230277363607987620969658566282107584630952213728423669333315615173084974491397108946178508558561103445223714364554352751747867497287812170208875076654770693767639721928154343235967049921114475568605852256700777262832436052740222177213612354715593787543102121117068142215027481302955
p=INTEGER:55685342628135644993
q=INTEGER:2018848419246646476894946094575564515176862561629979956283227393349426117194195173357244644821277073710795134539986018769393928719340504755806449531413017314396784334912136112253736003497362080917517151753555605597776865614151048604681116557282512513238254935296910445878892354969335089447
e1=INTEGER:37123561752090429995
e2=INTEGER:903312890059631
coeff=INTEGER:1040291110785843997

Step 4: Create the private key

Based on the ASN.1 structure, I generated the private key as follows:

1. Create the private key in DER format:
   openssl asn1parse -genconf asn -out private.der
2. Convert the private key to PEM format:
   openssl rsa -in private.der -inform der -out private.pem -outform pem

This results in a private.pem file being created with the following contents:

-----BEGIN RSA PRIVATE KEY-----
MIIBsAIBAAKBgQCgF35rHhOWi9+r4n9xM/ejvMEsQ8h6lams962k4U0WSdfySUev
hyI1bd3FRIb5fFqSBt6qPTiiiIw0KXte5dANB6lPe6HdUPTA/U4xHWi2FB/BfAyP
sOlUBfFp6dtkEEcEKt+Z8KTJYJEerRie24y+nsfZMnLBst6tsEBfx/U75wIBAwKB
gGq6VEdpYmRdHGzsbmP7vDiYe2zYHLwQ0AKnPKNErq6KQyQC5eEngbgT4WpWl+J2
Xn+R9m0vwNbaiDam0uD3p5192BaN2tdaW5P5JjfGa95ytRBCQ/cr+z03FjG9C6zQ
QZG5eyOoMloHAfnYiJMV5SZarfTiF9BGFvtcfrjhbterAgkDBMoUFjHxL0ECeDUI
f9nbOl1O2AgI/51gfHGo/NKv+kcQenM8RO7dy9+hUAulwqMlyszSq+0GdZdgQL/i
Lz8NclSgyuUtptmaSWtjB5Tdc8boaBApGKac7vB4M1AfTkng1+SplKbkdFlCVg4n
6EvCOrUFFsLp308JSbkv2240Q93JJwIJAgMxYrl2oMorAgcDNY7r7ttvAggOb9tA
6WMDHQ==
-----END RSA PRIVATE KEY-----

Step 5: Verifying the result

To check whether the created private key (in private.pem) matches the provided public key, I just generated a new public key from the private key:

openssl rsa -in private.pem -pubout

This yields the following output:

writing RSA key
-----BEGIN PUBLIC KEY-----
MIGdMA0GCSqGSIb3DQEBAQUAA4GLADCBhwKBgQCgF35rHhOWi9+r4n9xM/ejvMEs
Q8h6lams962k4U0WSdfySUevhyI1bd3FRIb5fFqSBt6qPTiiiIw0KXte5dANB6lP
e6HdUPTA/U4xHWi2FB/BfAyPsOlUBfFp6dtkEEcEKt+Z8KTJYJEerRie24y+nsfZ
MnLBst6tsEBfx/U75wIBAw==
-----END PUBLIC KEY-----

This output exactly matches the public key that you provided.

Comments

[Robby Cornelissen]

"But for a given Public Key, is it possible for me to figure out the corresponding Private Key?" No, that would defeat the entire purpose of PKI.

[zerkms]

It's possible to brute-force it, though it would take some time.

[Aakanksha Choudhary]

Can you please help me understand how to brute force for a given private key? @zerkms

[zerkms]

@AakankshaChoudhary it was a joke, sorry - it would take thousands years, unless RSA is broken earlier.

[STLDev]

Brute force hack of 1024 bit RSA seems very, very unlikely. See this answer on Stack Overflow's sister site Information Security Stack Exchange: security.stackexchange.com/a/19057/123722

[zerkms]

I think you cannot sign using a public key. The whole idea of signature that only a private key holder owns it.

[President James K. Polk]

This is a challenge problem for you to use your brains, as well as the hints that were provided for you (and which you've not fully shared with us), to solve the problem. It is your homework.

[crushman]

Holy Moly! does that mean RSA encryption is UNSECURE ??