2

While doing an internal pentest (a red team exercise basically) I figured out the following components of a private key (to be exact OpenSSLRSAPrivateCrtKey):

  • Modulus
  • Public exponent
  • Private exponent
  • First prime
  • Second prime
  • First exponent
  • Second exponent
  • Coefficient

Now is there a way to reconstruct the whole of the private key with this? And will that key (if re-constructed) be sufficient to decrypt the traffic ?

To give better context here are the values I have been able to extract so far :

modulus = e62a3583cb27093288d04f0a329ccec23f4fce25832f9a91633ed845f31c72cc276f538a313a4dd29d71770bafa0a828e931767c8fa7839e966f9222854a800980771f4998a25acfdea4c0fbcef9171827fe813b59a24f44ec0b09e8983ac7150636cff3d527be5554d2e8266d9f4ad3704406c01c4faabb2e3692c2f449da3fff865d99586e9a54bfe602a54566f74eb0841e545e5f76408ee68bd65c086b46bd47ebfffd84d537b47c3b938b1777549294cfa2b08c7b690728af55c194aae743166a237f92ff69c85e931e4c424fe9940d55ac15cfa2830f8cec4de04dc4afa8f2b74454a35f9175970c22830d5de2038e0768abb7ca2c8f746cde79d757e3

publicExponent = 10001

privateExponent = b205bfb29a752cf5fb4033824db75f6c7b0fbd00e2c0f52ab2baaf091b8acb7800a068db204c5a592711d5e422097f4775669ea0a57409a7a5efd1f60566a435b5396de7bcb906c8750ab5818e8ab74425db0215e7b454df983ac985300976665a9216b22012477334d29460f4b51a69041279ae29b7acf46e4023afcac73c9880012ef8ea0c46f80af6e00c6ca3dd051bf8e48a70419bf2097609ef41547f0852a469dcbb360e90e16a8a7cf5b23ebdfde0ca20c69f8346fb2cac8b227168733ea30f7ca07d51b61a9f50b9b911de31676a2e5826c78094f2fd8b73611d02b3b1a9cee7bfe43cf73f8f12c47d1d31e04f7a9acc9fea829053c24f7546342021

primeP = f5da5ef5099cc70460afb65874f0981e4220d79005c3ee07ea7557be612e9890ac28c47bee93d6a556bc8205826daf1bd23c768fe47dc50f65d33b0f7c5328047b51d85dec29b7f4fcb01984966b272f37e3cd5c45cd0e2216f916c9408d0b5d468b60f9231a73c83d70dc455f1360f8a254338305930220b403053f33d24ee9

primeQ = efaa14abb77223209b416f147acec8c1805393d688864cb33c896d84eb2fa2d4859925a1a0a619799c152d2dd5ade93ab2981f784dc735e882dcac298254e1365127a2b64b31307d87edf882662dd378ee236c3d90ae5568c7eb9b2c19740027625da33b791143ce2a7dd40d2dfce0735a338b325ea028713c43a4924400a8eb

primeExponentP = 3637eb5b14bc9b734eb3517e5e83b4b86f92f8970d7e711f13c8bf0a003a9b70c456d546138e4cf6f792e905b806e2683b4c14491cc5d3d09a7f23f63d4fc5727f93c428aa6d64e1455cbcb3edcc41befb0f64f9a5771c57ce432e90418919697fa63b4396473e2379d14af28d8e238390a10a1f29fa8aac95a658e0e057d009

primeExponentQ = 750ef3adb39a32021912eab86c0b580efb28d74aafc038f24a9d2d3b00cc7191aff74f64145d4c9013665c7cc8a37b094a75f6d901d44d4655b486fa774812003fbf46401795dd0353432e60329c2b70239075abd460f2228d934c654bc156d9e5b7aaa4bfcb68fce7d031a48653bf2558675893af983668a870b98f1f5bdb25

crtCoefficient = 354ba87acadf85a7f1178011a03ca25a8c359400d2ca7cffc0391d911342bc2f424268d0e445470b306f0179c780cad52c8a011ebffae5f1269f80ab0b6d68697aa977a0a8992b887477711ecb3caf1176b9ea2c940eff41e2de6c314ca73590275d654025cd56637a0b856152ff31cf7d814d5d6b47676c78b9dc783711214c

3

Yes, assuming that you indeed got all the correct values. All you need to do so is the private exponent (d) and the modulus (n).

Let c be a ciphertext and m be a message. This is computed like this:decrypt RSA

Here's how the RSA cryptosystem's private key is generated (simplified for your purposes).

  1. Two prime numbers are chosen: p and q
  2. n =pq
  3. We compute Carmichael's totient function of n, lcm(p-1, q-1), let's call the value that we obtain C
  4. We choose an integer e such that 1< e < C and such that e and C are coprime.
  5. We find d = e^-1 (mod C). d is the modular multiplicative inverse of e modulo C

Now, the public key is composed of the pair (e, n). The private key is composed of the pair (d, n). e is the "public exponent" and d is the "private exponent."

  • 1
    Ok. Although I truly admire the skills and the depth of your technical knowledge on the subject matter, I would, shamelessly, like to request for a more plain english answer if you could please. :) – qre0ct Jun 21 '17 at 16:00
  • 1
    Using the explanation above, you could check this link for practice. They also have directions on each step. If I'm correct, you need to convert each hexadecimal to decimal to make the conversions. The tool might fail (because of big numbers) but will give you an idea on how to code a simple script to do this. Try it with small numbers to understand. Also, you have to read on how messages are transformed so that they can be encrypted so that you are successful decrypting them. – aedcv Jun 21 '17 at 16:40
  • I found this as well: [mobilefish.com/services/rsa_key_generation/… to be very helpful. However, am still trying to figure out my private key from the above info. – qre0ct Jun 21 '17 at 18:59
  • 1
    So, in the effort to not give the answer right away: you do have your private key: the private exponent and the modulus. A ciphertext is decrypted by the above formula. You convert the ciphertext into a decimal value. Then you do the modulo exponentiation (you can use an online tool) where the private key is the exponent and the modulus is the modulus you found. This decrypts the message. However, if a padding scheme was used, you will have to do one more step (in which you revert the padding scheme). Padding schemes are used because of weaknesses in "vanilla" RSA – aedcv Jun 21 '17 at 19:14
  • @qre0ct if this/these answers solved both of your proposed questions: a) is there a way to reconstruct the private key? b) be sufficient to decrypt traffic, please accept it as the appropriate answer. Cheers! – aedcv Jun 22 '17 at 8:13
1

You could decrypt the traffic only if you did capture the initial SSL handshake. SSL uses a symmetric cipher to encrypt the traffic. The key to encrypt/decrypt using this cipher (negotiated during the handshake) is exchanged using RSA keys. You can find the chosen cipher in the handshake packets.

If the server uses Diffie-Hellman key exchange, you are pretty much screwed.

  • Are you talking about traffic captured in the past? Isn't it true that you can still capture live traffic (including the handshake) if you have only the private key? – Sjoerd Jun 22 '17 at 7:14
  • With Wireshark, you can specify your private key, then it can live decrypt an https session with the handshake. But this is because Wireshark decrypts the shared symmetric key then uses it by itself to decrypt all the traffic. Wireshark is that powerfull. – NdFeB Jun 22 '17 at 7:27
0

Ok .. outright huge thanks to @aedcv for his amazing answer/comments. I finally figured out my python code to reconstruct the private key in PEM format from the various private key components. Below is the code (for my future reference and for that of others like me :) )

from Crypto.PublicKey import RSA
from base64 import b64decode

# modulus as is from the components obtained
modulus = 'b733eb38bf886b43962bdde4688a8f5638f59a01416e59d543a29d5686d31be1623bcb5aebffa897ce3c702e6275b5ee22b77825d67f321fd90feda390780dc63beb04b4fcdf8b21d7e424d9ef4a319bc910790b36e844dee62582c2bf3ca6b9fbb219083a9d36044f7bf777c90101b8165cdfe6477ac83af9f320b2bfe39f35d6476c1f8c2e8c0dcd790c6d364d21559c75d496a0383952649ec136a48fd1ba41cedd63c5bf8d0138fb1d68c8935754a38e6dff4389dc7f42ea4bc754fab5fa49f2da9efb007a8a81219375e798e43b4fa970e8694557e7bd781e7bde90b38428df92d90c3ed5594d71d95ebb9fd9ce830484319698c736a6dd43242209a8af'

# public exponent as is from the components obtained
publicExponent = '10001'

# private exponent as is from the components obtained
privateExponent = '293675c8eb556e03e34974fe48023ba282e7c540590ed108a7d172219fece7cdb9028889a8a377b2c6c353dd2b6b1d8537ac1c4c2ec7a867ffb59499020befd5536f583cbad233036704bcc1861223bcceeb74bf7017aa3e927983c3f9af54366c87b117e7cfabf2264b55ed4d7b7b7e85115990fd2d82d3b99cd7133f159df320f7c6b4b1510c1dfe043a46d0616355fd3464ba55e923fef0262532f6f6239de21a1eb404597a620995083dc3e8cfbe3b0fcafedf52b69c8954def6abd1391acc34fc10f4f0e3e8e6f4d0a324414ae317135f58133025fb6e802a35b85b417ab25e53b5701475bcc82123756861e7252c3596d06397d4c58f0d83334b4d3ae9'

# primeP as is from the components obtained
primeP = 'e330e4226321ce47f8e81577a9914ad512d9006c0e197f99261c18c474acc218104ee8ca7808943adf9f4cdf9e541c6f2799cb27b77b9751b93ae001ee6e731cb48d293568b88764629d1a0014179ea51b5b49fa2a0a3dcc4852cea8c23bd244773b391a71e63820e809968a188dbd3f3609d62c4ca24df3373873d8bb9096bb' 

# primeQ as is from the components obtained
primeQ = 'ce6f13a87e04662296619ff6c56c9c2fc8e5fc3678b53d609d6be7a654319262a9a788226900ab833cb4e0e578691570f0739134aed7e77587dadc6ba1b12dc489fe254d48f8e03e3032f95d91fff0e5200883b31cdd00b89eb4895aa9b60907ec3ee3eec65946f36d8d6d733e7df7f8de641473c995ec2c39275dd72370209d'

# crtCoefficient as is from the components obtained
crtCoefficient = '542a5d9afcf012d6488bab79d38e7c74a1f5ccae51779d4191964c29137b8093bb355208d8358d8e40e8fca254e3e863c2557cae180e976d44f34d692984da2af4c213d42b9dc519376b2bc76790d93fc7c04018806f4cafe2390b30e01fbbab65c143ceb62a0ee1985025a748749117b85fac7b78d51a3830a9d216dea4046'


# converting each of the above from hex to long integers. Why, becasue pyCrypto contruct expects them to be that way
modulus_int = long(modulus,16)
publicExponent_int = long(publicExponent, 16)
privateExponent_int = long(privateExponent, 16)
primeP_int = long(primeP, 16)
primeQ_int = long(primeQ, 16)
crtCoefficient_int = long(crtCoefficient, 16)

private_key = RSA.construct((modulus_int, publicExponent_int, privateExponent_int, primeP_int, primeQ_int))

# encrypted stuff as is from the request response
cipher_text = 'QLOWI4eOKYnjGxwjMccbbepL5Nq8exGiwZQWSK2YiefFIS2+a7uaZn9cZzI0ywq9bfaTjUM/T2dvx7hsf9AgbEPGVbwruZFWpB8vlTxHVO0ynKJHpGE1L3jyuXg81oxzdr1wCetuBBN1tgc1T7JwDSWrq3/x4L4KKJ8VC+Ui0S9hYssH7zWWCYqYzb5bV0sMOYyJMLxP/VT2R/DYfAMIXegsDP/1blK16V4fVdu11zmuSNK8gMKYpnXZ2zD3hUWYu+9nj3g+mI/bTBP77aDdK/sPUjN2qYc7lV3VlAf1bBIhaToddWQwiLbrh2O80ZMdcF+EBkkoHBlT6J7yMyQtvw=='

raw_cipher_data = b64decode(cipher_text)

# decrypt the message directly with the private key
decrypted_data = private_key.decrypt(raw_cipher_data)
print decrypted_data

# export the private key to PEM format 
pem_key = private_key.exportKey('PEM')
print pem_key

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.