Use a RSA public key to generate the corresponding 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.):

*"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. — Robby Cornelissen, Apr 27 '18 at 01:18
It's possible to brute-force it, though it would take *some* time. — zerkms, Apr 27 '18 at 01:18
Can you please help me understand how to brute force for a given private key? @zerkms — Aakanksha Choudhary, Apr 27 '18 at 01:20
@AakankshaChoudhary it was a joke, sorry - it would take thousands years, unless RSA is broken earlier. — zerkms, Apr 27 '18 at 01:20
Brute force hack of 1024 bit RSA seems very, very unlikely. See this answer on Stack Overflow's sister site Information Security Stack Exchange: https://security.stackexchange.com/a/19057/123722 — STLDev, Apr 27 '18 at 01:25
I think you cannot sign using a public key. The whole idea of signature that only a private key holder owns it. — zerkms, Apr 27 '18 at 01:26
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. — President James K. Polk, Apr 27 '18 at 01:38

Robby Cornelissen · Accepted Answer · 2022-07-21T08:44:44.247

This is a very long answer that came together over a long time. It basically comprises 3 different answers, from bottom to top:

Original answer
Details how to create a private key from a public key when the two prime factors of the modulus of the public key are known. This is useful in cases where one of the two primes is relatively small, and can be easily factored. The created key is considered valid by OpenSSL if both factors are effectively prime.
Updated answer
Describes how to create a valid private key if the modulus of the public key is the product of more than 2 primes that can be easily factored. The created key is technically valid, but OpenSSL will refuse to use it if it considers the number of factors too large for the length of the key.
Final answer
Explains how to create a private key from two factors that are not necessarily prime. The created key has issues, but can be successfully used with OpenSSL to sign messages that can be correctly verified with the public key.

^{Disclaimer: The answers below are the result of a lot of trial and error. I lack the mathematical background to fully understand all the cryptographic operations that are involved, and found a lot of inspiration on crypto.stackexchange.com/.}

Final answer

Step 1: Derive the primes
From the public key in the question, we get that these are the values of the key's modulus (n) and public exponent (e):

n=112420265940019545385580931264662691888876377549063413938338239508058300548918731393322848876821656910452908064089039911552450302375557565600923056341141750687524704844725632296552824986371719004485250857447936962589230504662333990648942759862805127715014382377701044586628936249950092121536791020138692688871
e=3

As noted in the Updated answer section below, the modulus (n) is the product of the following 6 prime numbers (p1, p2, p3, p4, p5 and p6):

p1=55685342628135644993
p2=55929779616155790098563170377
p3=64741922158863007611093686267
p4=1004116810002299452628120005391
p5=899999049528188671493567437865381261
p6=616948235298561636059669351367929995833009266650461846821351961247854078133359796107391322920088709996730585706342033417954132775239823879192156129555584368164353183

Again, as explained in the Updated answer section, it is possible to create a valid multi-prime RSA key from these six values, but OpenSSL will balk at it because it considers a 1024-bit 6-prime key to be insecure. What we will do instead is create a factor p = p1 * p2 * p3 * p4 * p5, and a factor q = p6:

p=182219932739763270648005503629318079241230129119477190482462876894226401750770169792056565873199604072837331844075265147007599647331896874871737
q=616948235298561636059669351367929995833009266650461846821351961247854078133359796107391322920088709996730585706342033417954132775239823879192156129555584368164353183

Note that p is not prime, but that p and q are coprime.

Step 2: Calculate the private exponent and coefficient
As described in this answer, we should be able to calculate a private exponent d if we calculate Euler's totient with knowledge of all the prime factors, so in our case, the totient of n becomes ϕ(n) = (p1 - 1) * (p2 - 1) * (p3 - 1) * (p4 - 1) * (p5 - 1) * (p6 - 1), or:

ϕ(n)=112420265940019545383562082841557623794401803174962816591163564637337152649071389308753109740365619997953228173075041437232667728900367883549436497816570558785205895886262651863610175301779522497901539098790868823740777076877485036802521497522424439611149854943994123031116549292726779873714088471603368345600

Using the same methods outlined in the Original answer section, we calculate the private exponent (d) and the coefficient (c) to be:

d=74946843960013030255708055227705082529601202116641877727442376424891435099380926205835406493577079998635485448716694291488445152600245255699624331877713705856803930590841767909073450201186348331934359399193912549160518051251656691201680998348282959740766569962662748687411032861817853249142725647735578897067
c=11400012284752460027886253528293202304825202012135117091563382077917535900107285161280123288750670147288021587359790762214264926835198334744338

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

Again, following the same steps described in the Original answer, we create a file called asn with the following contents:

asn1=SEQUENCE:rsa_key

[rsa_key]
version=INTEGER:0
modulus=INTEGER:112420265940019545385580931264662691888876377549063413938338239508058300548918731393322848876821656910452908064089039911552450302375557565600923056341141750687524704844725632296552824986371719004485250857447936962589230504662333990648942759862805127715014382377701044586628936249950092121536791020138692688871
pubExp=INTEGER:3
privExp=INTEGER:74946843960013030255708055227705082529601202116641877727442376424891435099380926205835406493577079998635485448716694291488445152600245255699624331877713705856803930590841767909073450201186348331934359399193912549160518051251656691201680998348282959740766569962662748687411032861817853249142725647735578897067
p=INTEGER:182219932739763270648005503629318079241230129119477190482462876894226401750770169792056565873199604072837331844075265147007599647331896874871737
q=INTEGER:616948235298561636059669351367929995833009266650461846821351961247854078133359796107391322920088709996730585706342033417954132775239823879192156129555584368164353183
e1=INTEGER:137214246688368010854170162309899042235002625091403895801341918066238559668552121536780346376812813096497808976793391993049835618280391164843955
e2=INTEGER:411298823532374424039779567578619997222006177766974564547567974165236052088906530738260881946725806664487057137561355611969421850159882586128104086370389578776235455
coeff=INTEGER:11400012284752460027886253528293202304825202012135117091563382077917535900107285161280123288750670147288021587359790762214264926835198334744338

Step 4: Create the private key
Using the same commands as in the Original answer, we end up with the following private key:

Running openssl rsa -in private.pem -inform pem -check -noout reveals a couple of problems with this private key, which we will quietly ignore:

RSA key error: p not prime
RSA key error: d e not congruent to 1

Step 5: Testing the private key against the original public key The original question asks to use the created private key (stored in private.pem) to sign a message, and then verify that message using the public key from the question (stored in public.pem).

To create a signature in file signature of the message passed in via standard input:

echo "My name is Robby. My voice is my passport." | openssl dgst -sign private.pem -keyform pem -sha1 -out signature

To verify the signature against the same message:

echo "My name is Robby. My voice is my passport." | openssl dgst -verify public.pem -keyform pem -sha1 -signature signature

Which yields:

Verified OK

Mission accomplished.

Updated answer

The original answer below started from the assumption that the modulus (n) is the factor of two primes p and q. When I tried to factor n, after finding one factor p, I readily assumed that the remaining q was also prime.

This is not the case, which renders the answer below, as well as the created private key, invalid. While it will generate a matching public key, signature verification (or decryption) will fail when using the key pair for signing (or encryption).

I have decided to leave the Original answer up because it does correctly show how to create a private key for cases where the modulus actually is the factor of two primes, and can be easily factored.

As far as a correct and complete answer to the original question goes, I am only partway there: I have now factorized n to the following 6 factors, which (as far as I can tell) are all prime:

p1=55685342628135644993
p2=55929779616155790098563170377
p3=64741922158863007611093686267
p4=1004116810002299452628120005391
p5=899999049528188671493567437865381261
p6=616948235298561636059669351367929995833009266650461846821351961247854078133359796107391322920088709996730585706342033417954132775239823879192156129555584368164353183

Using some of the mechanisms outlined in the original answer, it is possible to create a multi-prime RSA key consisting of these 6 prime numbers. The ASN.1 structure to pass to openssl asn1parse would look like this:

asn1=SEQUENCE:rsa_key

[rsa_key]
version=INTEGER:1
modulus=INTEGER:112420265940019545385580931264662691888876377549063413938338239508058300548918731393322848876821656910452908064089039911552450302375557565600923056341141750687524704844725632296552824986371719004485250857447936962589230504662333990648942759862805127715014382377701044586628936249950092121536791020138692688871
publicExponent=INTEGER:3
privateExponent=INTEGER:74946843960013030255708055227705082529601202116641877727442376424891435099380926205835406493577079998635485448716694291488445152600245255699624331877713705856803930590841767909073450201186348331934359399193912549160518051251656691201680998348282959740766569962662748687411032861817853249142725647735578897067
prime1=INTEGER:55685342628135644993
prime2=INTEGER:55929779616155790098563170377
exponent1=INTEGER:37123561752090429995
exponent2=INTEGER:37286519744103860065708780251
coefficient=INTEGER:10583113183442869648
otherPrimeInfos=SEQUENCE:other_prime_infos

[other_prime_infos]
prime3=SEQUENCE:prime3
prime4=SEQUENCE:prime4
prime5=SEQUENCE:prime5
prime6=SEQUENCE:prime6

[prime3]
prime=INTEGER:64741922158863007611093686267
exponent=INTEGER:43161281439242005074062457511
coefficient=INTEGER:27817376944661773518043380720

[prime4]
prime=INTEGER:1004116810002299452628120005391
exponent=INTEGER:669411206668199635085413336927
coefficient=INTEGER:285320348305749284006046153442

[prime5]
prime=INTEGER:899999049528188671493567437865381261
exponent=INTEGER:599999366352125780995711625243587507
coefficient=INTEGER:658460078383005934070309924158661879

[prime6]
prime=INTEGER:616948235298561636059669351367929995833009266650461846821351961247854078133359796107391322920088709996730585706342033417954132775239823879192156129555584368164353183
exponent=INTEGER:411298823532374424039779567578619997222006177766974564547567974165236052088906530738260881946725806664487057137561355611969421850159882586128104086370389578776235455
coefficient=INTEGER:578350825258330649391070121677654395357069928435806599539320692960806529213345731736785707130093900487154780989433570566819293550718740139056912058574616030960959114

However, while OpenSSL will generate this private key, it refuses to use it for signing as it considers 6 primes too much for a 1024 bit key. Theoretically, it should be possible to use another library/tool with support for weak multi-prime RSA keys to sign/encrypt a message using this key, but I have yet to find one.

Original answer

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

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

Step 2: Calculate the private exponent and the coefficient

I calculated the totient of n as ϕ(n) = (p - 1) * (q - 1) using the python REPL:
ϕ(n)=112420265940019545383562082845416045411981431454487849423161376946428320592635503999973422759627461737095663419267762837841655167835571546831529127621801245931718255313312614982156040651459582892231514853950574881671713352908778385051165894248654079110333265820418532073390681314653181675602213322541221954432
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
Here, d is calculated as d ≡ e^−1 mod ϕ(n) and c as c ≡ q^-1 mod p.

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:1345898946164430984596630729717043010117908374419986637522151595566284078129463448904829763214184715807196756359990679179595952479560336503870966354275344876264522889941424074835824002331574720611678101169037070398517910409434032403120744371521675008825503290197940297252594903312890059631
coeff=INTEGER:1040291110785843997

The values of the two exponents e1 and e2 are calculated as d mod (p - 1) and d mod (q - 1) respectively.

Step 4: Create the private key

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

Create the private key in DER format:
openssl asn1parse -genconf asn -out private.der
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:

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.

@crushman not really, as said in the answer the prime number was small — thecow milk, Jul 18 '22 at 13:54
@thecowmilk I am revisiting this answer now and I think it's incorrect. The value of `e2` doesn't seem right, but what's worse is that I also think that `q` is not prime. I will be updating the answer soon. — Robby Cornelissen, Jul 19 '22 at 02:18
@RobbyCornelissen dont think you have made any mistake. I tried and it was correct. the point is that I'm finding a hard time calculating `e1` and `e2` and `coeff` — thecow milk, Jul 19 '22 at 07:22
@RobbyCornelissen hi, how could you find 6 factors of that number? — thecow milk, Jul 20 '22 at 14:29
@thecowmilk Used a combination of factordb.com and the site linked in the answer. Took less than a day on my very modest laptop. — Robby Cornelissen, Jul 21 '22 at 01:12
@thecowmilk Looks like I finally cracked it. That was decidedly non-trivial :) Thanks for bringing this question back to my attention. It always kind of felt like I had unfinished business here. — Robby Cornelissen, Jul 21 '22 at 08:41
@RobbyCornelissen you are more than welcomed :) although if you wanna linkup to talk somewhere it would be awesome, ping me and tell me where should we chat(if you want too) — thecow milk, Jul 21 '22 at 13:11

Use a RSA public key to generate the corresponding private key in OpenSSL?

1 Answers1

Final answer

Updated answer

Original answer

Linked