RSA - Recovering A Full Pem Private Key
Reconstruction d'une clé privée RSA à partir d'un fragment PEM corrompu.
RSA - Recovering A Full Pem Private Key
Énoncé
Alice a perdu une partie de sa clé privée … déchiffrez le flag à partir de la partie restante.
Exploitation
Comme dit dans l’énoncé du challenge, nous possédons une clé privée incomplète/corrompue au format PEM et un fichier flag.enc. Nous allons travailler sur celle-ci au format hexadécimal puis l’analyser.
Partie de la clé restante au format PEM :
1
2
3
4
5
6
7
8
9
10
11
---------------+LUJtSCo5IUbFMGufwzt7cYgy9emLl9blJifPQKCAQA4oKG6h
+RSa0N+p3I5njsPDcUVi8mfb7fJNis6T/jlWSGQMGeaNE/qhI/tlOc7oGCuU9q2t
ujA+i2dwcgyyNnzb5CQ2wAE9awZhBAg92E2APu1mDJgU5cl72QzpYVQymp8mWk/L
S9poVUcxNUC7Hx121sSDq0AFMKjVF8BeZ7LxCbTo7SAR007qRQOMK3QW7bEJPmoz
XocvshmW6lt1Enkd3LxK86LJ4gchW/w81XithEtBORVBOjhSr+x+5tF+7if0OQvA
fQlFoot9eY5HAueh/zKNnyGCl2mt4RlIBre71UCQPj4oJEO1G4lZHxXOGYkPlJQv
09klhUtcqHGlOlhAoIBADBoO5aR+b1LwN5y/VErkFvcYb7WjWn9cwD9ybNNoM7/H
+JY8KPimBE9TtPUQqUvaa2qDfV5szwSseZdl5ku6ue5ZzccXPIvo5M4k8YKKNheX
lhTfDQFxZM6Le7urY8tXDabHf9fxGmKrRP4g3CXQbNmBrerNHm00QwAd3DANYePu
5E5Py/HC6oILe7urY8tXDabHf9fxGmKrRP4g3CXQbNmBrerNHm00QwAd3DANYePu
5E5Py/HC6oI1jKurpsXDxFh3j2dLcALAqTVDXUxUi0---------------
Mettons la au format hex :
1
f8b509b520a8e4851b14c1ae7f0cededc620cbd7a62e5f5b94989f3d0282010038a0a1ba87e4526b437ea772399e3b0f0dc5158bc99f6fb7c9362b3a4ff8e559219030679a344fea848fed94e73ba060ae53dab6b6e8c0fa2d9dc1c832c8d9f36f9090db0004f5ac19841020f7613600fbb5983260539725ef6433a58550ca6a7c99693f2d2f69a1551cc4d502ec7c75db5b120ead0014c2a3545f01799ecbc426d3a3b480474d3ba9140e30add05bb6c424f9a8cd7a1cbec8665ba96dd449e47772f12bce8b27881c856ff0f355e2b6112d04e45504e8e14abfb1fb9b45fbb89fd0e42f01f425168a2df5e6391c0b9e87fcca367c860a5da6b78465201adeef550240f8f8a0910ed46e25647c573866243e5250bf4f6496152d72a1c694e9610282010030683b9691f9bd4bc0de72fd512b905bdc61bed68d69fd7300fdc9b34da0ceff1fe258f0a3e298113d4ed3d442a52f69adaa0df579b33c12b1e65d97992eeae7b967371c5cf22fa3933893c60a28d85e5e58537c3405c5933ae3dc85acd45802c541b135418cabb555790afc209aa68b5935198e972cd8af6bec84a06d1f4b1d0dd19134a98bbcdc34e2887c58af3bbc8d64e6bfc71ce614f64e5fd5812661d3b53f0af3894fe41bc512bc12eca8b9bf8e07dfdef064553ccb2deeeead8f2d5c369b1dff5fc4698aad13f883709741b36606b7ab3479b4d10c007770c035878fbb91393f2fc70baa08d632aeae9b170f1161de3d9d2dc00b02a4d50d7531522d
Elle nous révèle un délimiteur de 02820100, 3 parties séparent cette partie de clé.
Il se compose de cette façon :
1
2
3
02 indique que la structure suivante est un entier
82 indique que la longueur de l'entier est codée sur deux octets
01 00 sont les valeurs hexadécimales de la longueur, soit 256 en décimal
Cela signifie que l’entier qui suit a une longueur de 256 octets, soit 2048 bits.
On a donc :
1
2
3
1ère partie : f8b509b520a8e4851b14c1ae7f0cededc620cbd7a62e5f5b94989f3d
2ème partie : 38a0a1ba87e4526b437ea772399e3b0f0dc5158bc99f6fb7c9362b3a4ff8e559219030679a344fea848fed94e73ba060ae53dab6b6e8c0fa2d9dc1c832c8d9f36f9090db0004f5ac19841020f7613600fbb5983260539725ef6433a58550ca6a7c99693f2d2f69a1551cc4d502ec7c75db5b120ead0014c2a3545f01799ecbc426d3a3b480474d3ba9140e30add05bb6c424f9a8cd7a1cbec8665ba96dd449e47772f12bce8b27881c856ff0f355e2b6112d04e45504e8e14abfb1fb9b45fbb89fd0e42f01f425168a2df5e6391c0b9e87fcca367c860a5da6b78465201adeef550240f8f8a0910ed46e25647c573866243e5250bf4f6496152d72a1c694e961
3ème partie : 30683b9691f9bd4bc0de72fd512b905bdc61bed68d69fd7300fdc9b34da0ceff1fe258f0a3e298113d4ed3d442a52f69adaa0df579b33c12b1e65d97992eeae7b967371c5cf22fa3933893c60a28d85e5e58537c3405c5933ae3dc85acd45802c541b135418cabb555790afc209aa68b5935198e972cd8af6bec84a06d1f4b1d0dd19134a98bbcdc34e2887c58af3bbc8d64e6bfc71ce614f64e5fd5812661d3b53f0af3894fe41bc512bc12eca8b9bf8e07dfdef064553ccb2deeeead8f2d5c369b1dff5fc4698aad13f883709741b36606b7ab3479b4d10c007770c035878fbb91393f2fc70baa08d632aeae9b170f1161de3d9d2dc00b02a4d50d7531522d
Après avoir converti les 2 parties les plus grandes au format décimal et après multiples tests, j’en viens à la conclusion que ces deux-là ne sont pas n, p, q, d, qinv.
Il en reste donc 2 : exponent1 (dp) et exponent2 (dq).
Plaçons ces valeurs dans l’ordre chronologique au format ASN.1 pour les clés privées RSA PKCS1 :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
PrivateKeyInfo ::= SEQUENCE {
version Version,
privateKeyAlgorithm AlgorithmIdentifier,
privateKey PrivateKey,
attributes [0] Attributes OPTIONAL
}
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}
Donc d’après notre hypothèse :
1
2
exponent1 (dp) = 38a0a1ba87e4526b437ea772399e3b0f0dc5158bc99f6fb7c9362b3a4ff8e559219030679a344fea848fed94e73ba060ae53dab6b6e8c0fa2d9dc1c832c8d9f36f9090db0004f5ac19841020f7613600fbb5983260539725ef6433a58550ca6a7c99693f2d2f69a1551cc4d502ec7c75db5b120ead0014c2a3545f01799ecbc426d3a3b480474d3ba9140e30add05bb6c424f9a8cd7a1cbec8665ba96dd449e47772f12bce8b27881c856ff0f355e2b6112d04e45504e8e14abfb1fb9b45fbb89fd0e42f01f425168a2df5e6391c0b9e87fcca367c860a5da6b78465201adeef550240f8f8a0910ed46e25647c573866243e5250bf4f6496152d72a1c694e961
exponent2 (dq) = 30683b9691f9bd4bc0de72fd512b905bdc61bed68d69fd7300fdc9b34da0ceff1fe258f0a3e298113d4ed3d442a52f69adaa0df579b33c12b1e65d97992eeae7b967371c5cf22fa3933893c60a28d85e5e58537c3405c5933ae3dc85acd45802c541b135418cabb555790afc209aa68b5935198e972cd8af6bec84a06d1f4b1d0dd19134a98bbcdc34e2887c58af3bbc8d64e6bfc71ce614f64e5fd5812661d3b53f0af3894fe41bc512bc12eca8b9bf8e07dfdef064553ccb2deeeead8f2d5c369b1dff5fc4698aad13f883709741b36606b7ab3479b4d10c007770c035878fbb91393f2fc70baa08d632aeae9b170f1161de3d9d2dc00b02a4d50d7531522d
Calculons p et q à partir de dp et dq (au format décimal) et e (on va essayer de le deviner : 65537, on pourrait adapter notre script s’il était difficilement devinable, on verra par la suite) :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import isPrime
dp = 7148555547464038505019582073181987847221282336229090755303433935464041438728722315445920590295862691900510977361386320677860473810989959904375284918005822503490498629714441818111657597294112866124190516711142166703240642782046751441834698787320566407347275186885721002340336251213826539517538982749838281218351930912920837611810741859340764534985550700470528582527730023154106555023479350984164969387857980139298576959682474322435130483001430397565604367129022850910575247774674629721853252514890521369856402586485230434878874087329724012249237962607414595854323661609842458169031388035814172599136848735309198059873
dq = 6110837731088566352253221781036175367919253018523376282899460134677874564878401216507384943427927220524806674862457179446340613942066692858269570183978189888728064330003045868099468323724106389788209934294968725572772587551827772519479983428967827092576518158254621994207349871488516151148004300555859452598706382465317306648031526788407240594692980208094387779952221138768694912169842889075377451574509754595847039209814441119671744974531452517173371824184418025900649810707048375881108255850200714154032159719231171643502768691987934868963793270567688037612673362690122524924847642758845907369915127738132352553517
e = 65537
for kp in range(3, e):
p_mul = dp * e - 1
if p_mul % kp == 0:
p = (p_mul // kp) + 1
if isPrime(p):
print(f"p = {p}")
for kp in range(3, e):
q_mul = dq * e - 1
if q_mul % kp == 0:
q = (q_mul // kp) + 1
if isPrime(q):
print(f"q = {q}")
On obtient :
1
2
p = 27928160054494825126883359185104497021957745482530308246218846487541393965422609501483117599178536705757602856830591672027716356014953740819853534883537859279359571308232213021376077731974025329787247326002868803530866289478807627376662930219053827757872928400770759900469664196470971679306167052904688610206088256109692574340699886094522544579990941058523817091691197766166955665965649253379983284576575168070891853246301658400562214394304902769910999309003563074821244114063120787366980423849083761491283401270371537824778347008126862747587380527892824463100137693646750830463416398074703632168681469780385032086433
q = 26732926532431171018464681654346694151747152064279187734622649946357644039679312497579900342930115896905030041416518000759283413385036035635298900016512824960788408784153902747322265238095371501738863524723941350234483483771719960457189751951422767783605051100562923812453580437069813964207112865998889322806316012791502591668916772654151613834483268399831913219059389678358184263992723678081103534065726305783861385000574663083901418489811614953473818119055750895364187079921756185175902260440197864195501345138458934383568583657086528770261005244856456239304570734304956939857135035277116629817911202628261130051389
De vue, e est bien égal à 65537.
Ils font chacun 2048 bits, ce qui laisse penser que n fait logiquement 4096 bits, calculons n :
1
n = p * q
1
n = 746601450922789089705701592071438100012263055988877213418542096901953103990320756871218201853835552889188327878399402549085490835039405019252591371906221036608124660612934948482593109847370646445122484997259888120863223415509736830636722575982820947119186129993257666674107586854841834847405756800485744464756174972356173954375611223433403963056998599141462090264650068401164725710631985359015876368653083165946745975922577724441303533722820840105697268510100826492948453032033161252399099179547544007246001080416584100105247473305363551344150690341567675660359970065428347192396901139813867064701138951739369783468289764290429826235888619989991327112562893609863943986376182347162459797130440111268370692535397529183325882908847599129868019938058711957792910028347145036079894930337455505984145174522361274235240245860811261821228799970356319104830344703979957745939143449012204669522692263195710218649478591681518640247852325850341593372326983429776019189421551827593070008743583585358027882209610181872542698658120300156469150178676195719095318693026632009364447379486598325355292544152836281513323741301206284963525466743121619611486119473317531933236803796095843291412146793008748102253304239266662978781907066718860663179705437
n fait bien 4096 bits.
Après reconstruction de la clé privée, la voilà avec la partie dont nous disposons. On pourrait déchiffrer le flag à l’aide d’openssl mais nous allons le faire à l’aide d’un simple script.
Maintenant nous pouvons mettre en place un script pour déchiffrer le fichier flag.enc :
1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
n = 746601450922789089705701592071438100012263055988877213418542096901953103990320756871218201853835552889188327878399402549085490835039405019252591371906221036608124660612934948482593109847370646445122484997259888120863223415509736830636722575982820947119186129993257666674107586854841834847405756800485744464756174972356173954375611223433403963056998599141462090264650068401164725710631985359015876368653083165946745975922577724441303533722820840105697268510100826492948453032033161252399099179547544007246001080416584100105247473305363551344150690341567675660359970065428347192396901139813867064701138951739369783468289764290429826235888619989991327112562893609863943986376182347162459797130440111268370692535397529183325882908847599129868019938058711957792910028347145036079894930337455505984145174522361274235240245860811261821228799970356319104830344703979957745939143449112204669522692263195710218649478591681518640247852325850341593372326983429776019189421551827593070008743583585358027882209610181872542698658120300156469150178676195719095318693026632009364447379486598325355292544152836281513323741301206284963525466743121619611486119473317531933236803796095843291412146793008748102253304239266662978781907066718860663179705437
e = 65537
p = 27928160054494825126883359185104497021957745482530308246218846487541393965422609501483117599178536705757602856830591672027716356014953740819853534883537859279359571308232213021376077731974025329787247326002868803530866289478807627376662930219053827757872928400770759900469664196470971679306167052904688610206088256109692574340699886094522544579990941058523817091691197766166955665965649253379983284576575168070891853246301658400562214394304902769910999309003563074821244114063120787366980423849083761491283401270371537824778347008126862747587380527892824463100137693646750830463416398074703632168681469780385032086433
q = 26732926532431171018464681654346694151747152064279187734622649946357644039679312497579900342930115896905030041416518000759283413385036035635298900016512824960788408784153902747322265238095371501738863524723941350234483483771719960457189751951422767783605051100562923812453580437069813964207112865998889322806316012791502591668916772654151613834483268399831913219059389678358184263992723678081103534065726305783861385000574663083901418489811614953473818119055750895364187079921756185175902260440197864195501345138458934383568583657086528770261005244856456239304570734304956939857135035277116629817911202628261130051389
d = pow(e, -1, (p - 1) * (q - 1))
c = open('flag.enc', 'rb').read()
c = bytes_to_long(c)
m = pow(c, d, n)
print(long_to_bytes(m))
Ce qui donne :
1
cryptostonk{c0rRupTeD_PrIv&t_KeY}
This post is licensed under CC BY 4.0 by the author.