Crypto/Corrupted_key [Pragyan 2024]
Corrupted Key
We are given a corrupted private key. Our task was to full recover it with the partial information and use the recovered private key to ssh.
privatekey.txt
1
2
3
4
5
6
7
8
9
10
0:d=0 hl=4 l=1187 cons: SEQUENCE
4:d=1 hl=2 l= 1 prim: INTEGER :00
7:d=1 hl=4 l= 257 prim: INTEGER :F805C3BB46006897829ADD84A3421242DE9C0C1AC260806AFFE7C16E955CEC804A9683CCA4B607CE96AFBB4D6E55363201FAFE54A4C7FF91D4BA59D77F1B0BE35F02AB8140B8C618747ECD4C5E241F1E6C2548081EA0B52BCE84D6D24F2E981B0E7A0D46FFB41EE0B233B4C0BB5FD39061D7EC033495FF6DBDD96803674F95ADE6E34D111BE528EF055EAE9AD077DBDB0402B7A0A716EB78D524CA94C1628624EB9622CE92E0B5B9C30ED1870C6799B808C391B3CB2E3936E6B09C31C49668F7F7CD43623333F1A532E513364E511C4639CF0FE77EA3BCCA4E105E9C53485D4509BED7F661A6FBE27AE556EC63F122BB8C359D7C1E740B159947DCB9F18B88CB
268:d=1 hl=2 l= 3 prim: INTEGER :010001
273:d=1 hl=4 l= 256 prim: INTEGER :XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
533:d=1 hl=3 l= 129 prim: INTEGER :XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
665:d=1 hl=3 l= 129 prim: INTEGER :FC12B6905BF1D20EBE695A6FA4D46C1EABB82CB739441A5141FBBDBEF10EE757D719C8CC9882AB8D70B2C7EB79EF67D39D639D2685B44FA21FCED95A7E656429CECE26558FECE349B736D6488D7C5793CC4EECEA08F0XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
797:d=1 hl=3 l= 128 prim: INTEGER :XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
928:d=1 hl=3 l= 129 prim: INTEGER :XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
1060:d=1 hl=3 l= 128 prim: INTEGER :XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
To understand about the private lets create a dummy private key using and compare with the given corrupted key.
From the comparison we can see we have complete N,e value and a partial information about the factor of N.
We can use this information to factorize N and recover all the private keys.
Solve Script
1
2
3
4
5
6
7
8
9
10
11
12
13
N=0xF805C3BB46006897829ADD84A3421242DE9C0C1AC260806AFFE7C16E955CEC804A9683CCA4B607CE96AFBB4D6E55363201FAFE54A4C7FF91D4BA59D77F1B0BE35F02AB8140B8C618747ECD4C5E241F1E6C2548081EA0B52BCE84D6D24F2E981B0E7A0D46FFB41EE0B233B4C0BB5FD39061D7EC033495FF6DBDD96803674F95ADE6E34D111BE528EF055EAE9AD077DBDB0402B7A0A716EB78D524CA94C1628624EB9622CE92E0B5B9C30ED1870C6799B808C391B3CB2E3936E6B09C31C49668F7F7CD43623333F1A532E513364E511C4639CF0FE77EA3BCCA4E105E9C53485D4509BED7F661A6FBE27AE556EC63F122BB8C359D7C1E740B159947DCB9F18B88CB
e=0x10001
q_high=0xFC12B6905BF1D20EBE695A6FA4D46C1EABB82CB739441A5141FBBDBEF10EE757D719C8CC9882AB8D70B2C7EB79EF67D39D639D2685B44FA21FCED95A7E656429CECE26558FECE349B736D6488D7C5793CC4EECEA08F0
P.<x>= PolynomialRing(Zmod(N))
f = q_high*(1<<336) + x
lsb = f.small_roots(X=2^400, beta=160/1024)[0]
q=q_high*(1<<336)+lsb
q=int(q)
p=N//q
d=pow(e,-1,(p-1)*(q-1))
from Crypto.PublicKey import RSA
key=RSA.construct((n,e,d,p,q))
pem = key.export_key('PEM')
This post is licensed under CC BY 4.0 by the author.