leak泄露

(Updated: )

之前写的leak泄露，整理了一下搬到这

特征：
一般来说 leak泄露类型的题目和p，q之间有直接的关系，那么剩下就是靠数学推导

前置需要：同余的性质和运算，费马小定理，欧拉定理

1.leak = （p^q + q^p)%n

定义一个变量leak leak = (pq + qp) (mod  n)

从上面的定义可以推出： leak ≡ pq + qp (mod  n)

另外，题目中也给出了： leak ≡ p (mod  q) 同理： leak ≡ q (mod  p)

因此，我们可以写出： leak = p + k1q = q + k2p 其中k1和k2是某个整数。

重新整理上述等式： (k1 − 1)q = (k2 − 1)p

考虑两种情况： 第一种情况 k1 = k3p + 1 k2 = k4q + 1 这种情况下，由于leak < n，所以不成立。 第二种情况 k1 = 1 k2 = 1 将k1=1代回leak = p + k1*q的等式中： leak = p + (1)q 因此得出结论： leak = p + q

1
2
3
4
5
6
p, q = var('p q')
seq = [
    leak == p + q,
    n == p * q
]
print(solve(seq, p, q))
1
2
3
phi = n - leak + 1
d=inverse(e,phi)
c=pow(m,e,n)

2.leak = d+p+q

leak = d + p + q ϕn = n − (p + q) + 1 h = d + (p + q)e d = 1 + kϕn ed − 1 = k(n + 1 − h) + kd (e − k)d = k(n + 1 − h) + 1 [k(n + 1 − h) + 1] (mod  e − k) = 0遍历k即可

1
2
3
4
5
for k in range(1, e):
    if (k * (n + 1 - leak) + 1) % (e - k) == 0:
        d = (k * (n + 1 - leak) + 1) // (e - k)
        m = pow(c, d, n)
        print(long_to_bytes(m)) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import libnum
import gmpy2
from Crypto.Util.number import *

flag=b'ISCTF{********}'
m=bytes_to_long(flag)

p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
n=p*q
e=0x10001
c=pow(m,e,n)
d=inverse(e,(p-1)*(q-1))
leak = (d+(pow(p,q,n)+pow(q,p,n)))%n

print("c=", c)
print("n=", n)
print("leak=", leak)

"""
c= 8989289659072309605793417141528767265266446236550650613514493589798432446586991233583435051268377555448062724563967695425657559568596372723980081067589103919296476501677424322525079257328042851349095575718347302884996529329066703597604694781627113384086536158793653551546025090807063130353950841148535682974762381044510423210397947080397718080033363000599995100765708244828566873128882878164321817156170983773105693537799111546309755235573342169431295776881832991533489235535981382958295960435126843833532716436804949502318851112378495533302256759494573250596802016112398817816155228378089079806308296705261876583997
n= 13424018200035368603483071894166480724482952594135293395398366121467209427078817227870501294732149372214083432516059795712917132804111155585926502759533393295089100965059106772393520277313184519450478832376508528256865861027444446718552169503579478134286009893965458507369983396982525906466073384013443851551139147777507283791250268462136554061959016630318688169168797939873600493494258467352326974238472394214986505312411729432927489878418792288365594455065912126527908319239444514857325441614280498882524432151918146061570116187524918358453036228204087993064505391742062288050068745930452767100091519798860487150247
leak= 9192002086528025412361053058922669469031188193149143635074798633855112230489479254740324032262690315813650428270911079121913869290893574897752990491429582640499542165616254566396564016734157323265631446079744216458719690853526969359930225042993006404843355356540487296896949431969541367144841985153231095140361069256753593550199420993461786814074270171257117410848796614931926182811404655619662690700351986753661502438299236428991412206196135090756862851230228396476709412020941670878645924203989895008014836619321109848938770269989596541278600166088022166386213646074764712810133558692545401032391239330088256431881
"""


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import libnum
import gmpy2
from Crypto.Util.number import *

c= 8989289659072309605793417141528767265266446236550650613514493589798432446586991233583435051268377555448062724563967695425657559568596372723980081067589103919296476501677424322525079257328042851349095575718347302884996529329066703597604694781627113384086536158793653551546025090807063130353950841148535682974762381044510423210397947080397718080033363000599995100765708244828566873128882878164321817156170983773105693537799111546309755235573342169431295776881832991533489235535981382958295960435126843833532716436804949502318851112378495533302256759494573250596802016112398817816155228378089079806308296705261876583997
n= 13424018200035368603483071894166480724482952594135293395398366121467209427078817227870501294732149372214083432516059795712917132804111155585926502759533393295089100965059106772393520277313184519450478832376508528256865861027444446718552169503579478134286009893965458507369983396982525906466073384013443851551139147777507283791250268462136554061959016630318688169168797939873600493494258467352326974238472394214986505312411729432927489878418792288365594455065912126527908319239444514857325441614280498882524432151918146061570116187524918358453036228204087993064505391742062288050068745930452767100091519798860487150247
leak= 9192002086528025412361053058922669469031188193149143635074798633855112230489479254740324032262690315813650428270911079121913869290893574897752990491429582640499542165616254566396564016734157323265631446079744216458719690853526969359930225042993006404843355356540487296896949431969541367144841985153231095140361069256753593550199420993461786814074270171257117410848796614931926182811404655619662690700351986753661502438299236428991412206196135090756862851230228396476709412020941670878645924203989895008014836619321109848938770269989596541278600166088022166386213646074764712810133558692545401032391239330088256431881
e=65537

for k in range(1, e):
    if (k * (n + 1 - leak) + 1) % (e - k) == 0:
        d = (k * (n + 1 - leak) + 1) // (e - k)
        m = pow(c, d, n)
        print(long_to_bytes(m)) 

#b'ISCTF{u_got_it}'

当e比较小的时候，k ≈e*leak /n

3.leak1=(p+q)e % n, leak2=(p+e)q % n

leak2 = (p + e)q  = (p + e) (mod  q) p = leak2 − e (mod  q)

leak1 = (p + q)e  = pe  = (leak2 − e)e (mod  q)

所以有 leak1 − (leak2 − e)e = k ⋅ q q = gcd (k ⋅ q, n)

kq = leak1 − (leak2 − e)e q = gcd (kq, n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from secret import e1,e2,flag
from Crypto.Util.number import *

msg = bytes_to_long("=========Hint:e1="+str(3)+"=============")

p = getPrime(512)
q = getPrime(512)
N = p*q
print (N)
print (pow(msg,3,N))

msg = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
N = p*q
c = pow(msg, e2, N)

print (N,e2) #65537
print (c)
print(pow(p+q,e1,N))
print(pow(p+e1, q, N))



'''
N = 92492770373119584460081987762423642921257844727187836762004909281192459271971634726161143981458071695340994591107972425352531669271078740978901135762304359798469976380706711716397909327202889036066332030534806956149533263677365472375053769919044969923810993041551455618809123044195807478835222921551845223673
pow(msg,3,N) = 28249132350044579687091110964285446575404805400757326954185222098803605008954490760462246663674360047951197296557689347856716297531621331430289344669498939239588624311221464757652619402073234993515450143594805022438694559765344247838048186137683783869848355994953125
N,e2  = 27015781782143176377305444708803319343811009307670517970464768333771120997045181708841835585570829548449323842457013912871572311489720085833836018287540353234899258733164425361573491416926759037218022548655403489670177828691645649124879974295681372533797388585691439378293643867458900873524289213226600650695273378214798580343627514294295063280759129845430749116891862775979009255567653541999885963152760100703226634896555671676063304361506854160585739743294659176171738147833879545955904927967598053108666430271719503999512230196683852929862867406713611436850146222646354297511499309143157446775247989917315728885081 65537
c = 6960471390887676836770576717723665527999812876556281118485164081998911577875381908446602930344333654944091349042662834710841686602096786488652321359862587616056255592745697363730350424006430304398118412822538778460783959334956287873626339403915923932633438142296099193868446694776583016981952887671846310453413799566390944727222387714300425256165444782922011140095044159890292073622972447390685582541707094791774266611010707510165706469905665511940032155195482276746347896610980037890500866671279623501021060117466463857453415816945239635341057570437059560066260202940898394476654111403345827675113200431405898577228
pow(p+q,e1,N) = 1043358162140860962273728863918690254907683549241317489027248804399285815575770538413854959643097587139967903983728298468193229257795104589966904860928102961617976618240299512928763147662509317818932641083203337246219100049009339117603571633877302978817219689048124475419370026280279605865626353406562716520200330156419718727010377305953369496577186008235640834052476174479818668164269356133941979167253165318046864430749941469717776898395077805761110978284600985034996774850879017975655590682283621730288960471273895327469257980443060594976109602435213897419646191853646130932643009667656100697739228571988907108326
pow(p+e1,q,N) = 2367294939363830936563488061919820815242930281093184747199533909423831655805653462926444204702027721204809679004109764873839689145594088483842010258154637719914884625388278232087919706082381019835448905310742695003695950771324141473767622775925225996118945331612570816055138158026344226500272784973866690432399708551301786027237710788172551956598563031161785118254195771411706070504960683710473948125061842911067623875812101363911946970263021272358739604106737786749756437515890114561301491995915709307108967981619075610635000644793538253463486203886648971971414160634218354735619624263269704236191332074536463815524
'''

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
from gmpy2 import *
C1 = 28249132350044579687091110964285446575404805400757326954185222098803605008954490760462246663674360047951197296557689347856716297531621331430289344669498939239588624311221464757652619402073234993515450143594805022438694559765344247838048186137683783869848355994953125
m=iroot(C1, 3)[0]
print(long_to_bytes(m))
#低加密指数攻击，密文太小了直接开三次方就有了

#b'=========Hint:e1=2020321============='

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
from gmpy2 import *
from libnum import *

leak1 = 1043358162140860962273728863918690254907683549241317489027248804399285815575770538413854959643097587139967903983728298468193229257795104589966904860928102961617976618240299512928763147662509317818932641083203337246219100049009339117603571633877302978817219689048124475419370026280279605865626353406562716520200330156419718727010377305953369496577186008235640834052476174479818668164269356133941979167253165318046864430749941469717776898395077805761110978284600985034996774850879017975655590682283621730288960471273895327469257980443060594976109602435213897419646191853646130932643009667656100697739228571988907108326
leak2 = 2367294939363830936563488061919820815242930281093184747199533909423831655805653462926444204702027721204809679004109764873839689145594088483842010258154637719914884625388278232087919706082381019835448905310742695003695950771324141473767622775925225996118945331612570816055138158026344226500272784973866690432399708551301786027237710788172551956598563031161785118254195771411706070504960683710473948125061842911067623875812101363911946970263021272358739604106737786749756437515890114561301491995915709307108967981619075610635000644793538253463486203886648971971414160634218354735619624263269704236191332074536463815524
e1 = 2020321
N = 27015781782143176377305444708803319343811009307670517970464768333771120997045181708841835585570829548449323842457013912871572311489720085833836018287540353234899258733164425361573491416926759037218022548655403489670177828691645649124879974295681372533797388585691439378293643867458900873524289213226600650695273378214798580343627514294295063280759129845430749116891862775979009255567653541999885963152760100703226634896555671676063304361506854160585739743294659176171738147833879545955904927967598053108666430271719503999512230196683852929862867406713611436850146222646354297511499309143157446775247989917315728885081
e2 = 65537
c = 6960471390887676836770576717723665527999812876556281118485164081998911577875381908446602930344333654944091349042662834710841686602096786488652321359862587616056255592745697363730350424006430304398118412822538778460783959334956287873626339403915923932633438142296099193868446694776583016981952887671846310453413799566390944727222387714300425256165444782922011140095044159890292073622972447390685582541707094791774266611010707510165706469905665511940032155195482276746347896610980037890500866671279623501021060117466463857453415816945239635341057570437059560066260202940898394476654111403345827675113200431405898577228

kq =leak1-pow(leak2-e1,e1,N)#这里模N是因为数据过大无法爆破，在测试中在不模N的情况下很难跑出来（反正我没跑出来），并且模N不会影响结果
q = gcd(kq,N)
print(q)

p = N//q

phi = (p-1)*(q-1)
d = invert(e2,phi)
m = pow(c,d,N)

print(long_to_bytes(m))

#flag{5b55c69f-398d-47bc-ad37-4f268e8ae4b2}