week1:

EzAES

题面:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Cipher import AES
import os

iv = os.urandom(16)
key = os.urandom(16)
my_aes = AES.new(key, AES.MODE_CBC, iv)
flag = open('flag.txt', 'rb').read()
flag += (16 - len(flag) % 16) * b''
c = my_aes.encrypt(flag)
print(c)
print(iv)
print(key)
'''
b'\x81\x96wkkH0MBf5\xd6\x11\xfb\x8b\xf1\xc9}.&\x12\xa8\x97"\xf7\xa8\xe8\xb53\xe1\xdb\xcas\xa2$,M\xd6\x97a]\x8dL\x92\xdb\x8d\xc6\x8f'
b"\xbfD\xd8\xcdS\x8c\x98'\xf3\xcfU\xe4\xbe0\xb6\xa2"
b'QA\x8e\xaefR\xae\xba,\x8b\xb1\xf6=\xb9\x0f{'

题解:

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
from Crypto.Cipher import AES
import os

c = b'\x81\x96wkkH0MBf5\xd6\x11\xfb\x8b\xf1\xc9}.&\x12\xa8\x97"\xf7\xa8\xe8\xb53\xe1\xdb\xcas\xa2$,M\xd6\x97a]\x8dL\x92\xdb\x8d\xc6\x8f'
iv = b"\xbfD\xd8\xcdS\x8c\x98'\xf3\xcfU\xe4\xbe0\xb6\xa2"
key = b'QA\x8e\xaefR\xae\xba,\x8b\xb1\xf6=\xb9\x0f{'

my_aes = AES.new(key, AES.MODE_CBC, iv)
dec_data=my_aes.decrypt(c)

print(dec_data)

Hello_Crypto

题面:

1
2
3
4
5
6
7
8
from Crypto.Util.number import bytes_to_long
m = 215055650564999509147066999848883334420789832798256881072222896463316693748286072893535034339093689456003436134143558435197
print("m =",m)

# In cryptography, m stands for message, also plaintext
# so, why this m is number?
# decrypt this Message to get flag!
# m = 215055650564999509147066999848883334420789832798256881072222896463316693748286072893535034339093689456003436134143558435197

题解:

1
2
3
4
5
from Crypto.Util.number import *

m = 215055650564999509147066999848883334420789832798256881072222896463316693748286072893535034339093689456003436134143558435197
print("m =",long_to_bytes(m))

baby_mod

题面:

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

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
r = getPrime(777)
t = getPrime(777)
tmp = getPrime(15)
e = 65537
n = p*q
print(f"c = {pow(m,e,n)}")
print(f"leak = {p*r-q*t-tmp}")
print(f"r = {r}")
print(f"t = {t}")
'''
c = 97610462492002879448145034238630107721496882713736657636077240561048586238485053606622888377586592441662921010683325670263966861933266973547401954383304597879946174271956467147054800852978898062896406588557923225397199747210285180813093412825564779495263095092065192414107443273483268797966978170564927066475
leak = -3418385568007294219531133906774400703585305793184534598641151860740038439772706468209021224256302847905425081079687599920271455711877993136355184890751507142389651493357156292737184035912099646120698831608019296227865676299669297211177610119970698004971271424729749652357464730142019838118272727724231500538626481228406149361425819900739512849357287283665739393488258414489313140237062723
r = 571618702052548575636396565346239181114459149562484583680556272266797562732606186373115731945092495317681002724205599716261107952783841204088616716899173484197217617589167453663751087497809760551420360830162477023053984382829271392271
t = 771269036130382250458376689295688302279593133231832011484181928436070129662173414543113035228080569616354360938084829648180512995512766240199773311332182330264739472429240334001750283204056949905055988969462169388237279706386515630567
'''

分析:

tmp的位数比较小,可以爆破
$$
模去r:-(leak+tmp) ≡ q*t\ \ mod \ r\
q =-(leak+tmp)inv(t,r)\ \ mod\ r\
模去t:(leak+tmp) ≡ p
r\ \ mod \ t\
q =(leak+tmp)*inv(r,t)\ \ mod\ t
$$

题解:

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

c = 97610462492002879448145034238630107721496882713736657636077240561048586238485053606622888377586592441662921010683325670263966861933266973547401954383304597879946174271956467147054800852978898062896406588557923225397199747210285180813093412825564779495263095092065192414107443273483268797966978170564927066475
leak = -3418385568007294219531133906774400703585305793184534598641151860740038439772706468209021224256302847905425081079687599920271455711877993136355184890751507142389651493357156292737184035912099646120698831608019296227865676299669297211177610119970698004971271424729749652357464730142019838118272727724231500538626481228406149361425819900739512849357287283665739393488258414489313140237062723
r = 571618702052548575636396565346239181114459149562484583680556272266797562732606186373115731945092495317681002724205599716261107952783841204088616716899173484197217617589167453663751087497809760551420360830162477023053984382829271392271
t = 771269036130382250458376689295688302279593133231832011484181928436070129662173414543113035228080569616354360938084829648180512995512766240199773311332182330264739472429240334001750283204056949905055988969462169388237279706386515630567
e = 65537
#leak = p*r-q*t-tmp

tmp = 1<<12
while tmp < (1<<15):
tmp = next_prime(tmp)
p = (leak+tmp)%t*invert(r,t)%t
q = (-leak-tmp)%r*invert(t,r)%r
if isPrime(p) and isPrime(q):
print(p,q,long_to_bytes(pow(c,invert(e,(p-1)*(q-1)),p*q)))

factor

题面:

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

m = bytes_to_long(flag)
e = 65537
def prod(iterable):
result = 1
for num in iterable:
result *= num
return result
prime_list = [getPrime(64) for _ in range(10) ]
N = prod(prime_list)
p_list = random.sample(prime_list,7)
n = prod(p_list)
c = pow(m,e,n)
print(f"c = {c}")
print(f"N = {N}")
'''
c = 63332007657802769359979857416714238678559997235302130140293127409769287138161017004901739826451121688045455306271902581303928092331550
N = 131273501101084056326916918562906503813640957593643105869600337230649910138528834871493208182528963064102738684864591356457574578083376463066450772350380527917801659383766858602195179105417301
'''

题解:

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 itertools import combinations
from functools import reduce

c = 63332007657802769359979857416714238678559997235302130140293127409769287138161017004901739826451121688045455306271902581303928092331550
N = 131273501101084056326916918562906503813640957593643105869600337230649910138528834871493208182528963064102738684864591356457574578083376463066450772350380527917801659383766858602195179105417301
e = 65537

factors = list(factor(N))
fac = []
for i in range(len(factors)):
fac.append(factors[i][0])

fac = [10678131510432173393, 11077021854104172331, 11433235673636713159, 11839649384198468323, 13104606310100454503, 13625969576010644557, 13773403749460101269, 14092362469754752801, 15324465244017628739, 15436505349197729911]

p_list = []
for li in combinations(fac,7):
n = reduce(lambda x,y:x*y,(i for i in li))
phi = reduce(lambda x,y:x*y,(i-1 for i in li))
d = invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

d_known

题面:

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

m = bytes_to_long(flag)
p = getPrime(1024)
q = next_prime(p)
n = p * q
e = 0x10001
d = inverse(e, (p-1) * (q-1))
c = pow(m, e, n)
print(c)
print(d)

'''
c = 2883620629660612450315567253517591313374095359234860938721359222980159255698366604530034703365914018441838075480998740934929899729055375243468223689955298061049450559072292341655200798151888326595070321347418171935156319701587233131093986864515698960032108533543674915919584327585372115903492516892959756238260915349309584970959518810930514654787675974347245665255782161855829336017529953070886255609781057027701786668679442524578946026880838639468938098318176761757105692599154234782380566367080010108495138822994852038207257140564502206591870270736665464612235769485098763392965227389530799385436600352949450788621
d = 3267713328131131393927090426583292798051585768522548921962391781018685541611864486409221872466643053709031552602777290149936594733589714529379164301025521901022279490806218195782207268482992306851812484557313943594712283155921401278760659159081050651895345082927360592651748569268831382530565966734930624702359508936996315334757217620545859025580475722260965811194219516139227989776442596084534486404364594354143948448090158729900223853501155385481700131584772998281740459846724662522194723493790611298548620395643021847458570302023337953093170201322318002775103409648414248646166403320704046395360052144031180381789
'''

分析:

已知d求n,由于e*d = 1+kphi,当e很小时k也会很小,可以爆破。

如果e很大的时候可以用更快的方法(wiener

题解:

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

c = 2883620629660612450315567253517591313374095359234860938721359222980159255698366604530034703365914018441838075480998740934929899729055375243468223689955298061049450559072292341655200798151888326595070321347418171935156319701587233131093986864515698960032108533543674915919584327585372115903492516892959756238260915349309584970959518810930514654787675974347245665255782161855829336017529953070886255609781057027701786668679442524578946026880838639468938098318176761757105692599154234782380566367080010108495138822994852038207257140564502206591870270736665464612235769485098763392965227389530799385436600352949450788621
d = 3267713328131131393927090426583292798051585768522548921962391781018685541611864486409221872466643053709031552602777290149936594733589714529379164301025521901022279490806218195782207268482992306851812484557313943594712283155921401278760659159081050651895345082927360592651748569268831382530565966734930624702359508936996315334757217620545859025580475722260965811194219516139227989776442596084534486404364594354143948448090158729900223853501155385481700131584772998281740459846724662522194723493790611298548620395643021847458570302023337953093170201322318002775103409648414248646166403320704046395360052144031180381789
e = 65537
kphi = e*d-1
for k in range(1,e):
if (kphi % k) == 0:
phi = kphi // k
tmpp = iroot(phi, 2)[0]
tmpp = next_prime(tmpp)
tmpq = phi//(tmpp-1)+1
if phi%(tmpq-1) == 0 and isPrime(tmpp):
n = tmpp*tmpq
print(long_to_bytes(pow(c,d,n)))

week2:

E&R

题面:

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
#sage
from Crypto.Util.number import *
from secret import flag

flag = flag[6:-1]
l = len(flag)
m1 = bytes_to_long(flag[:l//2])
m2 = bytes_to_long(flag[l//2:])
#RSA
p = getPrime(256)
q = getPrime(256)
n = p * q
e = 65537
r_q = int(bin(q)[2:][::-1] , 2)
leak = p ^^ r_q
c = pow(m2,e,n)

#ECC
E = EllipticCurve(Zmod(n),[114514,1919810])
G = E.lift_x(Integer(m1))
P = G * e
print(f'leak = {leak}')
print(f'n = {n}')
print(f'c = {c}')
print(f'P = {P}')
# leak = 5599968251197363876087002284371721787318931284225671549507477934076746561842
# n = 7120275986401660066259983193598830554385933355254283093021239164350142898387660104515624591378875067038235085428170557400012848874756868985306042421950909
# c = 6803450117490196163076010186755045681029929816618361161925865477601994608941714788803007124967390157378525581080320415602012078322064392991884070073083436
# P = (4143131125485719352848137000299706175276016714942734255688381872061184989156686585992844083387698688432978380177564346382756951426943827434190895490233627 : 3879946878859691332371384275396678851932267609535096278038417524609690721322205780110680003522999409696718745532857001461869452116434787256032366267905519 : 1)

分析:

flag被分为了两段,第一段用RSA加密,第二段用ECC加密

先分析第一段:

p⊕(q的反序列) ,所以采用首尾剪枝

搜索方式:
  • 从两端向中间搜索

  • 每一次搜索,需要利用当前p_xor_q 两端的bit位。这是因为,p_xor_q的当前最高位对应p的最高位以及q的最低位,p_xor_q的当前最低位对应p的最低位及q的最高位(最高与最低都是相对于当前搜索而言)

  • 如果当前需要搜索的最高位为"1",则对应两种可能:p该位为1,q对应低位为0;p该位为0,q对应低位为1。剩下依此类推

剪枝条件:
  • 将p,q未搜索到的位全填“0”,乘积应小于n
  • 将p,q未搜索到的位全填“1”,乘积应大于n
  • p,q低k位乘积再取低k位,应与n的低k位相同

如此进行剪枝即可:

先分析第一段:

已知 P = G * e,m1为G的横坐标x,现在我们要求的就是G
$$
\because y^2≡x^3+ax+b\ mod\ n,n=p×q\
\therefore y同时满足下列方程组\
y^2≡x^3+ax+b\ mod\ p\
y^2≡x^3+ax+b\ mod\ q\
将x代入计算:\
y^2 ≡y_p^2\ mod\ p\
y^2 ≡y_q^2\ mod\ q\
对于y^2 ≡y_p^2\ mop\ p\
有(y+y_p)(y-y_p) ≡ 0\ mod\ p\
\therefore y≡y_p\ mod\ p\
同理y≡y_p\ mod\ q\
令前式中的y_p,y_q对应的k为k_p,k_q \
y = k_pp+y_p = k_qq+y_q\
k_pp=k_qq+y_2-y_1\
设p对q取逆为p^{-1},有p^{-1}p≡1\ mod\ q\
(y_q-y_p)p^{-1} p≡y_2-y_1\ mod\ q\
k_p = (y_q-y_p)p^{-1}\
此时y^{'}=(y_q-y_p)p^{-1}p+y_1\
对n取模后,即可得到y
$$
接下来看下面的推导:
$$
P≡G ·e\
已知e和P,需要得到G\
记G生成元的阶为n,即nG= 0\
e与n互素时,记e^{-1} 为e对n的逆元,即e·e^{-1}≡1\ mod\ n \
有e·e^{-1} = kn+1\
\therefore e·e^{-1}P = e^{-1}Q = knP+P = P\
\therefore P = e^{-1}Q\
注意本题中的n不是素数,所以求不出阶Zmod(n)的椭圆曲线的阶\
$$
所以,先求模p,q下的阶,再相乘

题解:

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
from Crypto.Util.number import *
from gmpy2 import *

pxorq = 5599968251197363876087002284371721787318931284225671549507477934076746561842
n = 7120275986401660066259983193598830554385933355254283093021239164350142898387660104515624591378875067038235085428170557400012848874756868985306042421950909
c = 6803450117490196163076010186755045681029929816618361161925865477601994608941714788803007124967390157378525581080320415602012078322064392991884070073083436
pxorq = str(bin(pxorq)[2:]).zfill(256)
e = 65537

def find(ph,qh,pl,ql):
l = len(ph)
tmp0 = ph + (256-2*l)*"0"+pl
tmp1 = ph + (256-2*l)*"1"+pl
tmq0 = qh + (256-2*l)*"0"+ql
tmq1 = qh + (256-2*l)*"1"+ql

if int(tmp0,2)*int(tmq0,2) > n:
return
if int(tmp1,2)*int(tmq1,2) < n:
return
if int(pl,2)*int(ql,2) % (2**(l-1)) != n % (2**(l-1)):
return

if l==128:
pp0 = int(tmp0,2)
if n%pp0 == 0:
pf = pp0
qf = n//pp0
phi = (pf-1)*(qf-1)
d = invert(e,phi)
m1 = pow(c,d,n)
print("p=",pf)
print("q=",qf)
print(m1)
print(long_to_bytes(m1))
exit()
else:
if(pxorq[l] == "1" and pxorq[255-l] == "1"):
find(ph+"1",qh+"0","1"+pl,"0"+ql)
find(ph+"0",qh+"0","1"+pl,"1"+ql)
find(ph+"1",qh+"1","0"+pl,"0"+ql)
find(ph+"0",qh+"1","0"+pl,"1"+ql)
elif(pxorq[l] == "1" and pxorq[255-l] == "0"):
find(ph+"1",qh+"0","0"+pl,"0"+ql)
find(ph+"0",qh+"0","0"+pl,"1"+ql)
find(ph+"1",qh+"1","1"+pl,"0"+ql)
find(ph+"0",qh+"1","1"+pl,"1"+ql)
elif(pxorq[l] == "0" and pxorq[255-l] == "1"):
find(ph+"0",qh+"0","1"+pl,"0"+ql)
find(ph+"0",qh+"1","0"+pl,"0"+ql)
find(ph+"1",qh+"0","1"+pl,"1"+ql)
find(ph+"1",qh+"1","0"+pl,"1"+ql)
elif(pxorq[l] == "0" and pxorq[255-l] == "0"):
find(ph+"0",qh+"0","0"+pl,"0"+ql)
find(ph+"1",qh+"0","0"+pl,"1"+ql)
find(ph+"0",qh+"1","1"+pl,"0"+ql)
find(ph+"1",qh+"1","1"+pl,"1"+ql)

find("1","1","1","1")

m2 = 3939513057628514533900105670644286436358199

e = 65537
n = 7120275986401660066259983193598830554385933355254283093021239164350142898387660104515624591378875067038235085428170557400012848874756868985306042421950909
p= 64760524083545528318139240449356269097871629401328435356643510319660757701117
q= 109947782034870726628911928816041880655659770652764045401662566933641952899777

E = EllipticCurve(Zmod(n),[114514,1919810])
E1 = EllipticCurve(Zmod(p),[114514,1919810])
E2 = EllipticCurve(Zmod(q),[114514,1919810])

order1 = E1.order()
order2 = E2.order()


Px = 4143131125485719352848137000299706175276016714942734255688381872061184989156686585992844083387698688432978380177564346382756951426943827434190895490233627
Py = 3879946878859691332371384275396678851932267609535096278038417524609690721322205780110680003522999409696718745532857001461869452116434787256032366267905519
P = E(Px,Py)

inv = invert(e,order1*order2)
G = P*inv

m1 = G.xy()[0]
print(long_to_bytes(Integer(m1))+long_to_bytes(Integer(m2)))

ezECC

题面:

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

assert flag.startswith(b'SHCTF{')

m = next_prime(bytes_to_long(flag))
p = getPrime(512)
a,b = getPrime(128),getPrime(128)
E = EllipticCurve(Zmod(p),[a,b])
k = getPrime(256)
A1 = E.random_point()
A2 = A1*k
M = E.lift_x(m)
C = M+A2

print('p = ',p)
print('k = ',k)
print('A1 = ',A1)
print('C = ',C)

分析:

$$
M = C-A2\
又A2 = k*A1,则我们要先得到椭圆曲线的方程,即得到a,b\
目前我们已经知道了曲线上的两个点,A1和C的坐标\
$$

推导一下求a和b的公式:
$$
y_1^2 ≡ x_1^3+ax_1+b\ mod\ p\
y_2^2 ≡ x_2^3+ax_2+b\ mod\ p\
y_1^2-y_2^2 = x_1^3-x_2^3+ax_1-ax_2 \ mod\ p\
故a = (y_1^2-y_2^2-(x_1^3-x_2^3))*inv(x_1-x_2)\
b=y_1^2 - x_1^3-ax_1\ mod\ p
$$
至此我们就已经得到了椭圆曲线的方程了,接下来我们把A1,C代入曲线,然后计算出M即可

但此处的Mnext_prime(bytes_to_long(flag)),所以需要爆破一下

题解:

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

p = 9799485259524549113003780400336995829253375211044694607315372450399356814285244762186468904824132005209991983177601498069896166228214442123763065076327679
k = 73771953838487511457389800773038323262861649769228176071578897500004883270121

A1_x = 5945412329827707694132352090606154232045921322662767755331097180167148601629747751274580872108985870208681845078153424348847330421799769770041805208089791
A1_y = 4113102573821904570542216004200810877456931033522276527318388416329888348077285857968081007666714313806776668203284797556825595791189566621228705928598709
C_x = 2336301464307188733995312208152021176388718095735565422234047912672553316288080052957448196669174030921526180747767251838308335308474037066343018337141276
C_y = 6868888273736103386336636953449998615833854869329393895956720058438723636197866928342387693671211918574357564701700555086194574821628053750572619551290025

a = (A1_y^2-C_y^2-(A1_x^3-C_x^3)) * invert(A1_x-C_x,p)
b = (A1_y^2-(A1_x^3+a*A1_x)) % p

E = EllipticCurve(Zmod(p), [a, b])
A1 = E(A1_x, A1_y)
C = E(C_x, C_y)

M = C - A1 * k
M_x , M_y = M.xy()

k = 0
while True:
flag = long_to_bytes(int(M_x-k))
if flag[-1] == b'}'[0]:
print(flag)
break
k += 1

worde很大

题面:

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

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e = getPrime(200)
d = gmpy2.invert(e,(p-1)*(q-1))
dp = d % (p-1)
c = pow(m,e,n)

print(f"n = {n}")
print(f"c = {c}")
print(f"e = {e}")
print(f"dp = {dp}")
'''
n = 92797370233873980442906837712414991273557887109421137254005693821179220783842664608517867406356194811250903692662294194772517175771472442998264053800209507802340858817129901572887641971506178402260272016618602673324838089319265076895469765618292133725686282926562911790435991025985096881352385317181522422893
c = 89968108788841244292184399182197183068411969931344872899046588844967805710352461009240634450773273264271106561993097902448878266207577111610556813133265990381430146279262050112291305134672648733263203282384984046555241503191008384825224216367805957120815912017959439261470534390849958016313836627026692556367
e = 820518797206132363024281168340023453296291743961172484304213
dp = 1184146217371194358261310753860992839433651078991071329301207180061717009917010070253406446707109553858885449086048694852826908606256268831948709163842437
'''

分析:

dp泄露,
$$
dp ≡d\ mod\ (p-1)\
\because dp·e≡d·e≡1\ mod\ (p-1)\
\therefore dp·e-1 = k(p-1)\
\therefore d·e = -k^{‘}(p-1)+dp·e ≡ 1 \ mod\ (p-1)\
\Longleftrightarrow -k^{’}(p-1)+dp·e≡1\ mod\ \phi(n)\
\therefore k_1(p-1)+dp·e-1=k_2(p-1)(q-1)\
\Longleftrightarrow (p-1)(k_2(q-1)-k_1)+1=dp·e\
\because dp<p-1\
\therefore (k_2(p-1)-k_1)\in (0,e)\
\therefore 遍历(1,e),当满足(dp·e-1)\ mod\ i ==0及n\ mod\ ((dp·e-1)//i+1) == 0
$$

题解:

可以用轩禹RSA工具一把梭:

image-20241017181216680

魔鬼的步伐

题面:

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
37
from Crypto.Util.number import *
from random import choice
from enc import flag

m = bytes_to_long(flag)
def get_primes(limit):
primes = []
is_prime = [True] * (limit + 1)
for num in range(2, limit + 1):
if is_prime[num]:
primes.append(num)
for multiple in range(num * num, limit + 1, num):
is_prime[multiple] = False
return primes

def get_Prime(bits):
while True:
n = 2
while n.bit_length() < bits:
n *= choice(primes)
if isPrime(n + 1):
return n + 1

e = 65537
primes = get_primes(e)
p = get_Prime(512)
q = get_Prime(512)
n = p*q
c = pow(m,e,n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
'''
n = 35601554404754443205956197767423638244480819513213682424263415784189360201503977713989478448065863842922293141167061009349836600661138400420745957170702611455032458385307995759985750190194883961438802429818317334557370322376981182910506715820470270665609532303127903640729053325462244100052156990287648878390213
e = 65537
c = 25669467541734062787273903983642917970822884237203202191927737495611911448627776616708151411981081016485118746837589353902895497467184409226693662152513677651390970185817242816391352159486936008209774125122744829085520318588336506824592067648516864895142417926675028614243289604906803071508018106144850063152126
'''

分析:

n-1为光滑数,直接用工具或者在线工具不能分解出来,所以考虑使用Pollard’s p-1分解算法
$$
如果一个整数的所有素因子都不大于B,我们称之为B-smooth数\
设p-1是B-smooth,可设p-1=p_1p_2…p_n(\forall1\leq i\leq n,p_i\leq B)\
若p_1,p_2,…,p_n两两不同,则p_1p_2…p_n|B! \ \implies B!=k(p-1)\
因此a^{B!}≡a^{k(p-1)}≡ 1\ (mod\ p),假设N=pq,计算gcd(a^{B!}-1,N)\
只要结果大于0小于N,那么结果就为p
$$

所以先用题面里的primes生成素因子表,然后用Pollard算法

题解:

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

n = 35601554404754443205956197767423638244480819513213682424263415784189360201503977713989478448065863842922293141167061009349836600661138400420745957170702611455032458385307995759985750190194883961438802429818317334557370322376981182910506715820470270665609532303127903640729053325462244100052156990287648878390213
e = 65537
c = 25669467541734062787273903983642917970822884237203202191927737495611911448627776616708151411981081016485118746837589353902895497467184409226693662152513677651390970185817242816391352159486936008209774125122744829085520318588336506824592067648516864895142417926675028614243289604906803071508018106144850063152126

def get_primes(limit):
primes = []
is_prime = [True] * (limit + 1)
for num in range(2, limit + 1):
if is_prime[num]:
primes.append(num)
for multiple in range(num * num, limit + 1, num):
is_prime[multiple] = False
return primes

primes = get_primes(e)

def Pollard(n):
a = 2
k = 2
while True:
a = pow(a, k, n)
res = gcd(a-1, n)
if res != 1 and res != n:
q = n // res
print("p =",res)
print("q =",q)
break
k += 1


Pollard(n)
p = 157290711012743540609220771570093181374753427996160208189626221897700257418758760571436529178587175468744711595491787767788459889466620543153198794942168987
q = 226342383320207891059296656711298153324668771315113043811023133972329330954560085280382748680518013393430808934023233255316390534439679894352705874716141599
phi = ( p - 1 ) * ( q - 1 )
d = invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

week3:

Lattice

题面:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)
n = getPrime(1024)
x = getPrime(200)
hint = (x*gmpy2.invert(m,n)) % n
print(f'n = {n}')
print(f'hint = {hint}')
'''
n = 91751682724535383426801979233579382146249394054927593853461441975873025861338566696842296300709396390853300050191456099001086369483700789545835126937129619414311385366187515386412489097637473211898440133723475548144630889528908646059677415293944340234999557462910013479791949310558143120476675974944688824571
hint = 42125624518172839303389534879456152068028936608676262828777097595105006642559548429514103308460116227664397888279179743591953506571256577685892992138017030717494209460025519334015055225882499334529921737699859956746163407510686233560899639248016131752745320752913080094007261094137047705913674790672335925527
'''

分析:

一眼NTRU格密码,这里解释一下NTRU的攻击手段

考虑等式
$$
h\ =\ gf^{-1}\ (mod\ p)
$$
对其变形得到
$$
f·h\ =\ g\ (mod\ p)\ = g+kp
$$
改写为矩阵乘法,得到
$$
(f,-k)*\begin{bmatrix}
1 & h\
0 & p
\end{bmatrix}\ =\ (f,g)
$$

注意:这里我们建立的矩阵就是一个格

下面我们令:
$$
L\ =\ \begin{bmatrix}
1 & h\
0 & p
\end{bmatrix}
$$
而上面那个矩阵乘法说明**(f,g)在格L上,所以我们能用svp问题的解法来解,也就是LLL格基规约算法**来解。

题解:

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

n = 91751682724535383426801979233579382146249394054927593853461441975873025861338566696842296300709396390853300050191456099001086369483700789545835126937129619414311385366187515386412489097637473211898440133723475548144630889528908646059677415293944340234999557462910013479791949310558143120476675974944688824571
hint = 42125624518172839303389534879456152068028936608676262828777097595105006642559548429514103308460116227664397888279179743591953506571256577685892992138017030717494209460025519334015055225882499334529921737699859956746163407510686233560899639248016131752745320752913080094007261094137047705913674790672335925527

M = matrix([[1,hint],[0,n]])
L = M.LLL()
ans = L[0]
if ans<0:
ans = -ans
f,g = ans

print(long_to_bytes(f))