e，phi不互素
题目

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


m=bytes_to_long(b'HDCTF{******}')
e=65537
p=getPrime(256)
q=getPrime(512)
r=getPrime(512)
n=p*q*r
P=pow(p,2,n)
Q=pow(q,2,n)
c=pow(m,e,n)
print(f"P = {P}")
print(f"Q = {Q}")
print(f"n = {n}")
print(f"c = {c}")
'''
P = 8760210374362848654680470219309962250697808334943036049450523139299289451311563307524647192830909610600414977679146980314602124963105772780782771611415961
Q = 112922164039059900199889201785103245191294292153751065719557417134111270255457254419542226991791126571932603494783040069250074265447784962930254787907978286600866688977261723388531394128477338117384319760669476853506179783674957791710109694089037373611516089267817074863685247440204926676748540110584172821401
n = 12260605124589736699896772236316146708681543140877060257859757789407603137409427771651536724218984023652680193208019939451539427781667333168267801603484921516526297136507792965087544395912271944257535087877112172195116066600141520444466165090654943192437314974202605817650874838887065260835145310202223862370942385079960284761150198033810408432423049423155161537072427702512211122538749
c = 7072137651389218220368861685871400051412849006784353415843217734634414633151439071501997728907026771187082554241548140511778339825678295970901188560688120351732774013575439738988314665372544333857252548895896968938603508567509519521067106462947341820462381584577074292318137318996958312889307024181925808817792124688476198837079551204388055776209441429996815747449815546163371300963785
'''

解题思路

e,phi可能不互素
把e里面的b的因子除掉后 bb和phi互素
进行部分解密得到a
c^a=m^{bbba}(mod n)
因为bb*a(mod phi)同余1
c^a同余m^b(mod n)
mm=m^b

exp

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
34
35
36
import gmpy2
from Crypto.Util.number import *
import math

P = 8760210374362848654680470219309962250697808334943036049450523139299289451311563307524647192830909610600414977679146980314602124963105772780782771611415961
Q = 112922164039059900199889201785103245191294292153751065719557417134111270255457254419542226991791126571932603494783040069250074265447784962930254787907978286600866688977261723388531394128477338117384319760669476853506179783674957791710109694089037373611516089267817074863685247440204926676748540110584172821401
n = 12260605124589736699896772236316146708681543140877060257859757789407603137409427771651536724218984023652680193208019939451539427781667333168267801603484921516526297136507792965087544395912271944257535087877112172195116066600141520444466165090654943192437314974202605817650874838887065260835145310202223862370942385079960284761150198033810408432423049423155161537072427702512211122538749
c = 7072137651389218220368861685871400051412849006784353415843217734634414633151439071501997728907026771187082554241548140511778339825678295970901188560688120351732774013575439738988314665372544333857252548895896968938603508567509519521067106462947341820462381584577074292318137318996958312889307024181925808817792124688476198837079551204388055776209441429996815747449815546163371300963785
e=65537

i=0
while True:
    #返回的是元组按下标索引（num，布尔）
    if gmpy2.iroot(P+i*n,2)[1]==True:
        p= gmpy2.iroot(P + i * n, 2)[0]
        print(f"p={p}")
        break

    i+=1
i=0
while True:
    if gmpy2.iroot(Q + i * n, 2)[1] == True:
        q= gmpy2.iroot(Q + i * n, 2)[0]
        print(f"q={q}")
        break
    i += 1

r=n//(p*q)
phi=(r-1)*(q-1)*(p-1)

b=math.gcd(e,phi)
bb=e//b
a=gmpy2.invert(bb,phi)
mm=pow(c,a,n)
m=gmpy2.iroot(mm,b)[0]
print(long_to_bytes(int(m)))

coppersmith attack
题目

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
from gmpy2 import *
from Crypto.Util.number import *



flag  = '******************'

p = getPrime(512)
q = getPrime(512)
m1 = bytes_to_long(bytes(flag.encode()))


n = p*q



flag1 = pow(m1,p,n)
flag2 = pow(m1,q,n)
print('flag1= '+str(flag1))
print('flag2= '+str(flag2))
print('n= '+str(n))


#flag1= 17893542812755845772427795161304049467610774531005620109503081344099161906017295486868699578946474114607624347167976713200068059018517606363517478396368430072890681401898145302336139240273132723451063402106360810413024642916851746118524166947301681245568333254648265529408446609050354235727237078987509705857
#flag2= 95580409405085606847879727622943874726633827220524165744517624606566789614499137069562997931972825651309707390763700301965277040876322904891716953565845966918293178547100704981251056401939781365264616997055296773593435626490578886752446381493929807909671245959154990639046333135728431707979143972145708806954
#n= 140457323583824160338989317689698102738341061967768153879646505422358544720607476140977064053629005764551339082120337223672330979298373653766782620973454095507484118565884885623328751648660379894592063436924903894986994746394508539721459355200184089470977772075720319482839923856979166319700474349042326898971

思路
c1=pow(m,p,n)=m^p mod (pq)
c2=pow(m,q,n)=m^q mod (pq)
由费马小定理：a^(p-1)≡1(mod p)进一步推导可得a^p≡a(mod p)
则m^p≡m(mod p)，m^q≡m(mod q)，那么有
m^p=m+k1p
m^q=m+k2q
进而有
c1=m^p mod (pq)=(m+k1p) mod (pq)=m+k1p+k3pq
c2=m^q mod (pq)=(m+k2q) mod (pq)=m+k2q+k4pq
可以构造
c1+c2=m+k1p+k3pq+m+k2q+k4pq=2m+(k1p+k3pq+k2q+k4pq)
c1c2=(m+k1p+k3pq)(m+k2q+k4pq)=m²+(k1p+k3pq+k2q+k4pq)m+(k1p+k3pq)(k2q+k4pq)
(c1+c2)m=2m²+(k1p+k3pq+k2q+k4pq)m
则有
c1c2-(c1+c2)m=-m²+(k1p+k3pq)(k2q+k4pq)
=>
m²-(c1+c2)m+c1c2=(k1p+k3pq)(k2q+k4pq)
至此，我们构成了模多项式m²-(c1+c2)m+c1c2

exp

1
2
3
4
5
6
7
8
9
10
11
<---sage--->
c1= 17893542812755845772427795161304049467610774531005620109503081344099161906017295486868699578946474114607624347167976713200068059018517606363517478396368430072890681401898145302336139240273132723451063402106360810413024642916851746118524166947301681245568333254648265529408446609050354235727237078987509705857
c2= 95580409405085606847879727622943874726633827220524165744517624606566789614499137069562997931972825651309707390763700301965277040876322904891716953565845966918293178547100704981251056401939781365264616997055296773593435626490578886752446381493929807909671245959154990639046333135728431707979143972145708806954
n= 140457323583824160338989317689698102738341061967768153879646505422358544720607476140977064053629005764551339082120337223672330979298373653766782620973454095507484118565884885623328751648660379894592063436924903894986994746394508539721459355200184089470977772075720319482839923856979166319700474349042326898971

PR.<m>=PolynomialRing(Zmod(n))
f=m^Integer(2)-(c1+c2)*m+c1*c2
x0=f.small_roots(X=2^400)
print(long_to_bytes(int(x0[0])))

#flag:NSSCTF{why_gongmo_again}

题目

#n: 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L #e:0x3 #c:0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365#so,how to get the message?

思路
比较简单就是小e攻击
exp

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
#小e攻击,直接爆破
from Crypto.Util.number import *
import gmpy2

# n=0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
# e=0x3
# c=0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
# print(n)
# print(e)
# print(c)
n=10456335904838169914349646852830082932152130624533179855437700729986430916359910968035371355128152016750075271161129744979254605922991030753616570849211931989112941277121682363790710646503345520505931418350219098036569932546893477983585713668853372819392130314661542626399462820378837771792293945490048339575869129479058678981790418112887403292721775644533540769467889512773382494878291574262142755186374570245813695390664702262226281601456889176191920270658811753696081082528539263191477192236336112147705564796435800152614366113854349615104191052807647128834113146535639155857819697492608839941056356828288393881491
e=3
c=2217344750798296091193230394221582894657909643174934416842588335871298152598368701484028832407289746218387783855373449002121088413603751014125921242419602155087438902181522441026460003722677539409576093794862185483713606547386172606576925933695952279401957552813065318376293

def exp(e,n,c):
    k=0
    while 1:
        m1=k*n+c
        m,t=gmpy2.iroot(m1,e)
        if t:
            print(m)
            print(long_to_bytes(m))
            break
        k+=1

exp(e,n,c)

coppersmith 知道p的高位求低位
题目

1
2
3
4
n:0xb119849bc4523e49c6c038a509a74cda628d4ca0e4d0f28e677d57f3c3c7d0d876ef07d7581fe05a060546fedd7d061d3bc70d679b6c5dd9bc66c5bdad8f2ef898b1e785496c4989daf716a1c89d5c174da494eee7061bcb6d52cafa337fc2a7bba42c918bbd3104dff62ecc9d3704a455a6ce282de0d8129e26c840734ffd302bec5f0a66e0e6d00b5c50fa57c546cff9d7e6a978db77997082b4cb927df9847dfffef55138cb946c62c9f09b968033745b5b6868338c64819a8e92a827265f9abd409359a9471d8c3a2631b80e5b462ba42336717700998ff38536c2436e24ac19228cd2d7a909ead1a8494ff6c3a7151e888e115b68cc6a7a8c6cf8a6c005L
e:65537
enc:1422566584480199878714663051468143513667934216213366733442059106529451931078271460363335887054199577950679102659270179475911101747625120544429262334214483688332111552004535828182425152965223599160129610990036911146029170033592055768983427904835395850414634659565092191460875900237711597421272312032796440948509724492027247376113218678183443222364531669985128032971256792532015051829041230203814090194611041172775368357197854451201260927117792277559690205342515437625417792867692280849139537687763919269337822899746924269847694138899165820004160319118749298031065800530869562704671435709578921901495688124042302500361
p>>128<<128:0xe4e4b390c1d201dae2c00a4669c0865cc5767bc444f5d310f3cfc75872d96feb89e556972c99ae20753e3314240a52df5dccd076a47c6b5d11b531b92d901b2b512aeb0b263bbfd624fe3d52e5e238beeb581ebe012b2f176a4ffd1e0d2aa8c4d3a2656573b727d4d3136513a931428b00000000000000000000000000000000L

思路
已知p的高128位结合n利用coppersmith求低位
exp

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 sage.all import*
n=0xb119849bc4523e49c6c038a509a74cda628d4ca0e4d0f28e677d57f3c3c7d0d876ef07d7581fe05a060546fedd7d061d3bc70d679b6c5dd9bc66c5bdad8f2ef898b1e785496c4989daf716a1c89d5c174da494eee7061bcb6d52cafa337fc2a7bba42c918bbd3104dff62ecc9d3704a455a6ce282de0d8129e26c840734ffd302bec5f0a66e0e6d00b5c50fa57c546cff9d7e6a978db77997082b4cb927df9847dfffef55138cb946c62c9f09b968033745b5b6868338c64819a8e92a827265f9abd409359a9471d8c3a2631b80e5b462ba42336717700998ff38536c2436e24ac19228cd2d7a909ead1a8494ff6c3a7151e888e115b68cc6a7a8c6cf8a6c005
e=65537
c=1422566584480199878714663051468143513667934216213366733442059106529451931078271460363335887054199577950679102659270179475911101747625120544429262334214483688332111552004535828182425152965223599160129610990036911146029170033592055768983427904835395850414634659565092191460875900237711597421272312032796440948509724492027247376113218678183443222364531669985128032971256792532015051829041230203814090194611041172775368357197854451201260927117792277559690205342515437625417792867692280849139537687763919269337822899746924269847694138899165820004160319118749298031065800530869562704671435709578921901495688124042302500361
p1=0xe4e4b390c1d201dae2c00a4669c0865cc5767bc444f5d310f3cfc75872d96feb89e556972c99ae20753e3314240a52df5dccd076a47c6b5d11b531b92d901b2b512aeb0b263bbfd624fe3d52e5e238beeb581ebe012b2f176a4ffd1e0d2aa8c4d3a2656573b727d4d3136513a931428b00000000000000000000000000000000

R=Zmod(n)
P.<x>=PolynomialRing(R)
#x是未知的128位
f=p1+x
#把最高次的首项系数变为1
f=f.monic()

roots=f.small_roots(x=2^128,beta=0.4)
for r in roots:
    p=p1+int(r)
    if n%p==0:
        q=n//p
        print(f"p={p}")
        print(f"q={q}")
phi=(p-1)*(q-1)
d=pow(e,-1,phi)
m=pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]).decode())

#flag{3d0914a1-1e97-4822-a745-c7e20c5179b9}