EzECC:

题面：

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
 from Crypto.Util.number import *
from secret import msg
import random

flag = b'0xGame{' + msg + b'}'

q = getPrime(80)
a,b= [random.randrange(1,q-1) for i in range(2)]

def add(P,Q):
	if P[0] != Q[0] and P[1] != Q[1]:
		t = ((Q[1]-P[1]) * inverse(Q[0]-P[0],q)) %q
	else:
		t = ((3*P[0]*P[0]+a) * inverse(2*P[1],q))%q

	x3 = t*t - P[0] - Q[0]
	y3 = t*(P[0] - x3) - P[1]
	return (x3%q, y3%q)

def mul(t, A, B=0):
    if not t: return B
    return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A)

assert len(msg)%2==0
m1=bytes_to_long(msg[:len(msg)//2])
m2=bytes_to_long(msg[len(msg)//2:])

k = random.getrandbits(64)
G = (641322496020493855620384 , 437819621961768591577606)
K = mul(k,G)

M = (m1,m2)
r = random.getrandbits(16)

C_1 = add(M,mul(r,K))
C_2 = mul(r,G)

print(f'q={q}\na={a}\nb={b}\n')
print(f'G = {G}\nK = {K}\nC_1={C_1}\nC_2={C_2}')

'''
q=1139075593950729137191297
a=930515656721155210883162
b=631258792856205568553568

G = (641322496020493855620384, 437819621961768591577606)
K = (781988559490437792081406, 76709224526706154630278)
C_1=(55568609433135042994738, 626496338010773913984218)
C_2=(508425841918584868754821, 816040882076938893064041)
'''

分析：

add()和mul()是用python写的椭圆曲线的加法和乘法
$$
\begin{align}C_1 &= M+rK\

&C_2 = rG
\end{align}
$$
可以通过先求出r，然后再用减法来求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
27
28
29
30
31
32
33
34
35
36
from Crypto.Util.number import *
from gmpy2 import *
from tqdm import *

q = 1139075593950729137191297
a = 930515656721155210883162
b = 631258792856205568553568
E = EllipticCurve(GF(q),[a,b])

G = E(641322496020493855620384, 437819621961768591577606)
K = E(781988559490437792081406, 76709224526706154630278)
C_2 = E(508425841918584868754821, 816040882076938893064041)
C_1 = (55568609433135042994738, 626496338010773913984218)

def add(P,Q):
    if P[0] != Q[0] and P[1] != Q[1]:
        t = ((Q[1]-P[1]) * inverse(Q[0]-P[0],q)) %q
    else:
        t = ((3*P[0]*P[0]+a) * inverse(2*P[1],q))%q

    x3 = t*t - P[0] - Q[0]
    y3 = t*(P[0] - x3) - P[1]
    return (x3%q, y3%q)


for i in trange(2^16):
    if C_2 == i*G:
        r = i
        print(r)
        break

_rk = -r*K
M = add(C_1,_rk)
mx = M[0]
my = M[1]
print(long_to_bytes(int(mx))+long_to_bytes(int(my)))

LLL-FirstBlood：

题面：

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
 from random import randrange
from Crypto.Util.number import getPrime,bytes_to_long
from secret import flag
assert len(flag) % 4 == 0

length = len(flag)//4
m = [bytes_to_long(flag[i*length:(i+1)*length]) for i in range(4)]
p = getPrime(int(128))

def MakeMask(n,p):
    upper = identity_matrix(n)
    low = identity_matrix(n)
    for i in range(n-1):
        for j in range(i+1, n):    
            upper[i, j] = randrange(1, p)
            low[j, i] = randrange(1, p)
    result = upper * low
    assert det(result) == 1
    return result

def Matrix2List(x):return [list(i) for i in x]

noise = [[randrange(1, p) for i in range(4)] for _ in range(4)]
noise[0] = m
M = matrix(noise)
A = MakeMask(4,p)
C = A*M

print(f'p={p}')
print(f'C={Matrix2List(C)}')
'''
p=198880159035681668071031460916089145469
C=[[1528140902799730745476264672501768332416990282355490479242339131918301176698899635154781328839496210200676497333428, 2081687444435007467807250373278513114045272585243815458840083487459795021302180077490134099644993120009567147202772, 3080873409460299046339495750746632185307246572817534784703936044874106809413620470006445984962733721029566440253675, 3491734341995174183626991907292607070252197520631412767989879432598743851171175369180080355977574296558734415823458], [2359409535809048127331244699867147546817134802610067329431135227991488324148374065940238308147500809599395748756798, 3191196199160821446351036460385791985682645040446022512790815348810555748825420237291839170774872264097466183208742, 4665346530155386457242345394284286198347336281451530670818113876767736288089400119492317775648206643242839430899283, 5369350746042850276067380638571565496087948799720968959426256192923852197959381101839484196445995828389461004495917], [1641407111066265429602929560264443103285908072677065498760570514577412905392260182334706635555256537745902283191251, 2190536173399177167068153351271988931232272884028569669242062395087922275021628334797729266560930040116807133977244, 3127556759140845426132305699421707182108351516931881411928719802847628408656887897596425133523782526561471050447359, 3707239956529200159380870618471703921011276020439315706352183576289925263316580408968092016782483770373121972835410], [9883814543195849013523934427451407019514807606993414569626142656857168165339, 13190422499129347541373922929251088892868361241120937213742340947017395215646, 18832738552342488056498211782604832513006649329982003661701684946590064734701, 22323329751908690611034666068697427811613727429398087082295754189068333861152]]
'''

分析：

$$
M = \begin{pmatrix}m_1 &m_2 &m_3 &m_4\
noise_{1,1} &noise_{1,2} &noise_{1,3} &noise_{1,4}\
noise_{2,1} &noise_{2,2} &noise_{2,3} &noise_{2,4}\
noise_{3,1} &noise_{3,2} &noise_{3,3} &noise_{3,4}
\end{pmatrix}\ \ \ A=\begin{pmatrix}
A_{1,1} &A_{1,2} &A_{1,3} &A_{1,4}\
A_{2,1} &A_{2,2} &A_{2,3} &A_{2,4}\
A_{3,1} &A_{3,2} &A_{3,3} &A_{3,4}\
A_{4,1} &A_{3,2} &A_{3,3} &A_{3,4}
\end{pmatrix}
$$

又 C = A*M

对C用LLL算法，可以得到m~1~,m~2~,m~3~,m~4~

题解：

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 gmpy2 import *
from tqdm import *

p=198880159035681668071031460916089145469
C=[[1528140902799730745476264672501768332416990282355490479242339131918301176698899635154781328839496210200676497333428, 2081687444435007467807250373278513114045272585243815458840083487459795021302180077490134099644993120009567147202772, 3080873409460299046339495750746632185307246572817534784703936044874106809413620470006445984962733721029566440253675, 3491734341995174183626991907292607070252197520631412767989879432598743851171175369180080355977574296558734415823458], [2359409535809048127331244699867147546817134802610067329431135227991488324148374065940238308147500809599395748756798, 3191196199160821446351036460385791985682645040446022512790815348810555748825420237291839170774872264097466183208742, 4665346530155386457242345394284286198347336281451530670818113876767736288089400119492317775648206643242839430899283, 5369350746042850276067380638571565496087948799720968959426256192923852197959381101839484196445995828389461004495917], [1641407111066265429602929560264443103285908072677065498760570514577412905392260182334706635555256537745902283191251, 2190536173399177167068153351271988931232272884028569669242062395087922275021628334797729266560930040116807133977244, 3127556759140845426132305699421707182108351516931881411928719802847628408656887897596425133523782526561471050447359, 3707239956529200159380870618471703921011276020439315706352183576289925263316580408968092016782483770373121972835410], [9883814543195849013523934427451407019514807606993414569626142656857168165339, 13190422499129347541373922929251088892868361241120937213742340947017395215646, 18832738552342488056498211782604832513006649329982003661701684946590064734701, 22323329751908690611034666068697427811613727429398087082295754189068333861152]]

C = Matrix(ZZ,C)

M = C.LLL()[0]
print(M)
M = (-228892343979120176686388, -473218447137085890782052, -260770537947126049367394, -270233647859726974858109)

flag = b''

for i in M:
    m = long_to_bytes(int(abs(i)))
    flag += m
print(flag)

LLL-SecondBlood：

题面：

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 secret import flag

m = bytes_to_long(flag)
q = getPrime(512)
assert m.bit_length() == 318

def encrypt(m):
	mask,noise = getPrime(511),getPrime(50)
	mask_.append(mask)
	noise_.append(noise)
	c = (mask*m + noise)%q
	return c

noise_,mask_  =[[] for _ in range(2)]
c_ = [encrypt(m) for i in range(4)]

print(f'q = {q}\nmask = {mask_}\nc_ = {c_}')

'''
q = 9342426601783650861020119568565656404715236059903009041977149778244153930435908024696666887269890479558473622355346816236972767736577737332173213722012253
mask = [6237128445236992920577225644858662677575951126467888858782461334057970069468925833844231116647406833999142659751374620280213290736114576089069396331226747, 6368031389213953889417545256750169233725975229197446803885029159767701479445576860704561593200907482372690851152126782391126462547524526631934408981070841, 5106473460982791188578285397420642137630347289252852045044021197988607082777231839839730169682158507822078412449827976663385282021916120837408192506341443, 6318090842950331228033349517542810123596316850353637421587264886413877142612686177796023049304908696413386218992511112752788640732410845589679820003047667]
c_ = [3823539664720029027586933152478492780438595004453489251844133830947165342839393878831914879334660250621422877333022321117120398528430519794109624186204492, 1721659645750224819953244995460589691120672649732560768435214608167861246790136217219349234604724148039910656573436663379375048145045443527267790379816425, 668633520079344839648950502380059311916108468801009386138810324259146523323704014491547148973835774917331333581475920804677395949854411894556705238578896, 497860586379981076499130281851986010889356253371192266267220334713415782402939318483926418213877341511996918189750595755372560345085899109305344338944066]
'''

分析：

$$
C_i ≡ a_i*m +b_i\ \ (mod\ p)\
b_i = C_i-a_im+kp
$$

构造格：
$$
\begin{pmatrix}k_1&k_2&k_3&k_4&m&1\end{pmatrix}
\begin{pmatrix}p &0&0&0&0&0\
0 &p &0&0&0&0\
0 &0 &p&0&0&0\
0 &0&0&p&0&0\
-a_1 &-a_2 &-a_3 &-a_4 &1 &0\
C_1 &C_2 &C_3 &C_4 &0 &2^{318}
\end{pmatrix}=\begin{pmatrix}b_1&b_2&b_3&b_4&m&2^{318}\end{pmatrix}
$$

题解：

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 gmpy2 import *
from tqdm import *

q = 9342426601783650861020119568565656404715236059903009041977149778244153930435908024696666887269890479558473622355346816236972767736577737332173213722012253
mask = [6237128445236992920577225644858662677575951126467888858782461334057970069468925833844231116647406833999142659751374620280213290736114576089069396331226747, 6368031389213953889417545256750169233725975229197446803885029159767701479445576860704561593200907482372690851152126782391126462547524526631934408981070841, 5106473460982791188578285397420642137630347289252852045044021197988607082777231839839730169682158507822078412449827976663385282021916120837408192506341443, 6318090842950331228033349517542810123596316850353637421587264886413877142612686177796023049304908696413386218992511112752788640732410845589679820003047667]
c_ = [3823539664720029027586933152478492780438595004453489251844133830947165342839393878831914879334660250621422877333022321117120398528430519794109624186204492, 1721659645750224819953244995460589691120672649732560768435214608167861246790136217219349234604724148039910656573436663379375048145045443527267790379816425, 668633520079344839648950502380059311916108468801009386138810324259146523323704014491547148973835774917331333581475920804677395949854411894556705238578896, 497860586379981076499130281851986010889356253371192266267220334713415782402939318483926418213877341511996918189750595755372560345085899109305344338944066]

GE = Matrix(ZZ,[
    [q,0,0,0,0,0],
    [0,q,0,0,0,0],
    [0,0,q,0,0,0],
    [0,0,0,q,0,0],
    [mask[0],mask[1],mask[2],mask[3],1,0],
    [c_[0],c_[1],c_[2],c_[3],0,2^318]
])

for i in GE.LLL():
    if abs(i[-1]) == 2^318:
        m = abs(i[-2])
        print(long_to_bytes(m))

EzMatrix：

题面：

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
 from Crypto.Util.number import getPrime
from random import randint
from secert import secert,flag
from hashlib import md5
def n2b(n):return md5(str(n).encode()).hexdigest()

assert secert < pow(2,64)
assert flag == '0xGame{'+n2b(secert)+'}'

def Martix2list(Martix):
    result = []
    Martix = list(Martix)
    for i in Martix:
        result.append(list(i))
    return result

A =
# 12 * 12的矩阵
p = 
A = Matrix(GF(p),A)
enc = A**secert

def Martix2list(Martix):
    result = []
    Martix = list(Martix)
    for i in Martix:
        result.append(list(i))
    return result

with open('enc.txt','w') as f:
    f.write(str(Martix2list(enc)))

分析：

$$
可知A^m=C,由线性代数知识可知，存在可逆矩阵P\
使得P^{-1}AP=B\ \ (B为对角矩阵)\
故B^m=P^{-1}A^mP=P^{-1}CP\
$$

$$
根据对角矩阵次方的性质(即对角线上的元素自乘)，这样就把矩阵的乘法转化为了\
b^m ≡c\ mod\ p这样的离散对数问题，只要用B和C中任意对应的元素即可
$$

可以利用sage自带的diagonalization()求解

题解：

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 *
import hashlib
A=[[12143520799533590286, 1517884368, 12143520745929978443, 796545089340, 12143514553710344843, 28963398496032, 12143436449354407235, 158437186324560, 12143329129091084963, 144214939188320, 12143459416553205779, 11289521392968],[12143520799533124067, 1552775781, 12143520745442171123, 796372987410, 12143514596803995443, 28617862048776, 12143437786643111987, 155426784993480, 12143333265382547123, 140792203111560, 12143460985399172467, 10983300063372],[12143520799533026603, 1545759072, 12143520746151921286, 781222462020, 12143514741528175043, 27856210942560, 12143440210529480891, 150563969013744, 12143339455702534403, 135941365971840, 12143463119774571623, 10579745342712],[4857408319806885466, 2428704161425648657, 12143520747462241175, 758851601758, 12143514933292307603, 7286139389566980165, 9714738936567334300, 144947557513044, 12143346444338047691, 130561054163540, 4857352974113333366, 2428714303424782417],[12143520799533339320, 1476842796, 12143520749060275613, 733281428880, 12143515144091549812, 25896324662208, 12143446129977471347, 139126289668080, 12143353609086952433, 125093278125816, 12143467808884068695, 9705993135696],[3469577371288079926, 5204366058378782250, 12143520750775862343, 706665985740, 12143515359139397843, 24876891455539, 12143449149385190675, 5204499435641729607, 1734628523990131469, 119757210113970, 12143470097256549947, 9282407958928],[10986995009101166671, 1734788687033207505, 12143520752514668698, 680173911560, 12143515570582515443, 23883386182656, 12143452072344092516, 10408859957710764174, 8673790006740000925, 4047954924507284041, 12143472277719610437, 8879790035168],[12143520799534210329, 8095680534365818753, 12143520754224346525, 6071761054204856029, 12143515774342357443, 22931775530664, 12143454859049102627, 122586336122081, 12143373761302849103, 109840689548590, 8095634066844843878, 8500892291801],[2428704159899526175, 7286112481016467893, 12143520755876491019, 629765964828, 12143515968446948123, 9714838668887734012, 4857345013259425502, 117630592711632, 12143379764863568374, 105318302849760, 2428659620509049335, 7286120625945355053],[7286112479717322389, 7286112480971640825, 12143520757456628435, 606320684970, 12143516152115449139, 4857429497934652454, 4857347490735050126, 112978994964264, 12143385390297217523, 101086824360217, 7286069740980100293, 7286120294834973633],[7727695054246476847, 1202487728, 12143520758958480293, 584144077140, 12143516325240923843, 20377952745696, 12143462294760579275, 108622249048560, 12143390651947217363, 97133513961120, 12143479741445599772, 8831658996900830432],[12143520799535388887, 1161628182, 12143520760380594623, 563225247585, 12143516488091679443, 19626876325056, 12143464472820678035, 104545135017180, 12143395570399006523, 93441517429260, 12143481309754543787, 7218375794633]]# 12*12
p = 12143520799543738643
C = [[11285847990515095003, 7585413350741918021, 11658254512436412666, 477577914899276103, 2941386515764607825, 11283325421744133699, 4096971712575507616, 8118672870538606033, 2377937081025778041, 6576171711896495163, 6152554374963853172, 5022013484610428974], [8354008012616001452, 7787447107046065118, 9504997911333967278, 1082773427768571094, 6015520658629219637, 11244285744740006951, 4493944053220750368, 3504246247470690014, 1738582001618280397, 2330057776906622572, 3043456814665571080, 2981613454022714952], [2508674373714509177, 3544963739532775937, 7952732753025175616, 11161786730565526285, 3397123486689639675, 6454135592624912854, 6613201018024296927, 9748485344986779929, 1819761609989340766, 1259944825407465767, 1596049024644778041, 7769939905324967788], [4200851163596876950, 11960539098651202761, 3303721151143544462, 2532304102428121556, 11083895221097319129, 1171933471304558017, 1549099593543874478, 6088238862927163233, 6459553630361959801, 947358195425767572, 2090533922210134578, 9023030120605201052], [2271102089902208138, 1614812525306266829, 1546249462332047661, 3168333397191737100, 7678980468150522028, 3128939172985153696, 1146041044751755224, 11870173227065140617, 8351303466095252790, 694704483676649448, 7944218023016968278, 583421745603756386], [10309472503110333289, 1100598261990718822, 10235859400888405310, 910925705831020921, 10771855884237562064, 9970830255165655653, 11678899608458971536, 4368822164222204233, 3104861419162339779, 4540709628196554222, 7851809145727500968, 12086896840826708824], [10973051751637593366, 5039073157846327641, 4855314857834773443, 4416954195828423951, 8243966437000815560, 8250554263390748131, 8093181066366682440, 1145520354143718292, 294729013023637045, 10115389386419597159, 2767140395261835843, 6724257139233017485], [6878768250003631244, 10834164422364241529, 6946589221005878489, 539734218479521833, 2691724062063066048, 3989403041446358401, 815244541494093987, 11168528286389981272, 2021358468726921955, 1123433019094267521, 524639025046508882, 5720273332497702547], [6688451244183880831, 10892730373179989558, 6987453292894341174, 5572212176769878684, 11332149024403380575, 3944612864568504791, 6768594304071589280, 10526434024562201079, 10241323610053039912, 1120473558410865753, 306153635148226248, 3606666063074222104], [7556871914690327290, 11353594909211427742, 747771112781361153, 1245068803956910299, 2831489557155431404, 1800035620948876551, 1050411779595241927, 5665981688041778089, 2028968510484240787, 4386552235402890530, 10334391443650474796, 3883841302951550608], [4485787817401669404, 184501191500952934, 3690661645276970957, 6263309802498749034, 6484490370652685031, 9743108369653588026, 3045941510087387269, 5870433915209047275, 4679598273992216016, 11839352681285251516, 4957980185504231911, 7925596893607015470], [1000449712878466719, 7022601702937838844, 1095849907482791166, 11989051568709522226, 6768031250066783733, 185945517026191241, 4280928696740160411, 5633542561098902406, 10176177574499086410, 5782837249861240943, 7406530879613861823, 1971858224839520916]]


A = matrix(GF(p),A)
C = matrix(GF(p),C)

A,P = A.diagonalization()
print(A)

P_ = P.inverse()
C = P_*C*P 

a = A[0][0]
c = C[0][0]

m = discrete_log(mod(c,p),mod(a,p))
print(m)
flag = hashlib.md5(str(m).encode()).hexdigest()
print(flag)