2023-0xGame-week3-wp-crypto

比赛记录

[Week 3] EzECC

题目描述：

还在偷听小爱和小爆的通讯！

Hint 1: 也许SageMath能给你想要的东西

Hint 2: 预期解法时间估计可能一两分钟左右，可能更短

Hint 3: 阿贝尔群上的加加减减能随便写吗？

题目：

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)
'''

题目基于椭圆曲线加密方案。用给定的q、a、b三个参数，建立如下常见形式的椭圆曲线：

$y^2 = x^3+ax+b \quad(mod\;q)$

同时给出椭圆曲线上加法与倍点的计算实现。

题目加密过程如下：

将flag串拆成两半，分别转成整数后，作为M点的横纵坐标(需要注意的是M点并不是椭圆曲线上的点)
给出椭圆曲线上的点G，计算其k倍点K，给出G、K坐标
给出C1、C2点的坐标。两个点生成方式分别如下：

$C1 = M + rK$ $C2 = rG$

而注意到，r是一个16比特的数字，数量级很小。因此我们可以根据2式直接爆破出正确的r，然后计算C1-rK即可得到M点。

这里有一个细节需要注意，由于M不在椭圆曲线上，因此C1也不在椭圆曲线上，故无法直接用sagemath内置的椭圆曲线相关操作直接进行加减。因此可以通过计算出椭圆曲线的阶，从而计算出rK点逆元，然后用题目给定的加法函数计算出M。

exp：

from Crypto.Util.number import *

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)

q=1139075593950729137191297
a=930515656721155210883162
b=631258792856205568553568

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

E = EllipticCurve(GF(q), [a, b])
for r in range(2**16):
    if(mul(r,G) == C_2):
        break

M = add(C_1,mul(E.order()-r,K))

print("0xGame{",end = "")
print(str(long_to_bytes(int(M[0])))[2:-1],end = "")
print(str(long_to_bytes(int(M[1])))[2:-1],end = "")
print("}")

#0xGame{Al1ce_L0ve_B0b}

[Week 3] LLL-FirstBlood

题目描述：

1	Hint 1: SageMath中的LLL算法该怎么用……？为啥这算法能解出想要的东西

题目：

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]]
'''

完成本题需要对格密码有最基础的了解。首先还是梳理一下加密过程：

将flag拆成四组并分别转为整数，作为一个4x4矩阵M的第一行
生成12个(1,p)之间的随机数，作为M的后三行
生成一个行列式为1的矩阵A，并计算C=AM
给出C矩阵以及生成有限域的素数p

其实只需要明白一点：格是对一些向量进行整系数线性组合得到的产物。而在本题中，明文flag与剩下三行noise分别是四组行向量，左乘A矩阵，实质上就是对四个行向量进行线性组合，而C就是这四个行向量组合后张成的格，对应的，四个行向量均为C的格基。

而很显然，flag组成的第一行行向量均较短，因此可以对格C用LLL算法解决SVP问题，得到的第一行向量就是flag的四部分。

exp：

from Crypto.Util.number import *

p=198880159035681668071031460916089145469
C=[[1528140902799730745476264672501768332416990282355490479242339131918301176698899635154781328839496210200676497333428, 2081687444435007467807250373278513114045272585243815458840083487459795021302180077490134099644993120009567147202772, 3080873409460299046339495750746632185307246572817534784703936044874106809413620470006445984962733721029566440253675, 3491734341995174183626991907292607070252197520631412767989879432598743851171175369180080355977574296558734415823458], [2359409535809048127331244699867147546817134802610067329431135227991488324148374065940238308147500809599395748756798, 3191196199160821446351036460385791985682645040446022512790815348810555748825420237291839170774872264097466183208742, 4665346530155386457242345394284286198347336281451530670818113876767736288089400119492317775648206643242839430899283, 5369350746042850276067380638571565496087948799720968959426256192923852197959381101839484196445995828389461004495917], [1641407111066265429602929560264443103285908072677065498760570514577412905392260182334706635555256537745902283191251, 2190536173399177167068153351271988931232272884028569669242062395087922275021628334797729266560930040116807133977244, 3127556759140845426132305699421707182108351516931881411928719802847628408656887897596425133523782526561471050447359, 3707239956529200159380870618471703921011276020439315706352183576289925263316580408968092016782483770373121972835410], [9883814543195849013523934427451407019514807606993414569626142656857168165339, 13190422499129347541373922929251088892868361241120937213742340947017395215646, 18832738552342488056498211782604832513006649329982003661701684946590064734701, 22323329751908690611034666068697427811613727429398087082295754189068333861152]]
L = Matrix(ZZ, C)
res = L.LLL()
for i in res[0]:
    print(str(long_to_bytes(abs(i)))[2:-1],end = "")

#0xGame{8e4d5924dc4cd78f11c1eeb99e991ab3}

[Week 3] LLL-SecondBlood

题目描述：

前面的学习已经很累了！所以这道题的flag就直接送了！奇怪……怎么发送的时候受到了一些信号干扰，，

Hint 1: 当然也可以直接应用SageMath中的Coppersmith定理去直接梭哈，前提是得学会多元Coppersmith该如何使用、构造。

Hint 2: HNP问题是什么？CVP问题是什么？SVP问题又是什么？这些问题的求解矩阵又该如何构造？

题目：

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]
'''

一个LWE问题，其一般会提供多组如下形式的等式：

$c_i = a_ix + b_i \quad (mod\;q)$

其中，ai、ci均为已知，而bi是未知的量且较小，要求我们通过这些等式还原x。

这个问题一般写成矩阵形式：

$C_{m*1} = A_{m*n}x_{n*1} + e_{m*1} \quad (mod\;q)$

那么如何用格进行求解呢？这里介绍两种方法：

方法一：CVP

把问题转化成一个CVP问题：

首先由模等式：

$c_i = a_ix + b_i \quad (mod\;q)$

转化为等式如下：

$c_i-b_i = a_ix + k_iq$

所以可以构造如下格：

$\left( \begin{matrix} a_{1} &p & & & \\ a_{2} & &p & & \\ ... & & &... & \\ a_{m} & & & &p \\ \end{matrix} \right)$

该格满足：

$\left( \begin{matrix} a_{1} &p & & & \\ a_{2} & &p & & \\ ... & & &... & \\ a_{m} & & & &p \\ \end{matrix} \right)* \left( \begin{matrix} x \\ k_{1} \\ ... \\ k_{n} \\ \end{matrix} \right) = \left( \begin{matrix} c_1-b_1 \\ c_2-b_2 \\ ... \\ c_m-b_m \\ \end{matrix} \right)$

观察到由于b_i较小，所以右侧向量近似为：

$\left( \begin{matrix} c_1 \\ c_2 \\ ... \\ c_m \\ \end{matrix} \right)$

因此可以求解CVP问题可以得到c_i-b_i组成的向量，进而还原flag。

exp：

from Crypto.Util.number import *

q = 9342426601783650861020119568565656404715236059903009041977149778244153930435908024696666887269890479558473622355346816236972767736577737332173213722012253
mask_ = [6237128445236992920577225644858662677575951126467888858782461334057970069468925833844231116647406833999142659751374620280213290736114576089069396331226747, 6368031389213953889417545256750169233725975229197446803885029159767701479445576860704561593200907482372690851152126782391126462547524526631934408981070841, 5106473460982791188578285397420642137630347289252852045044021197988607082777231839839730169682158507822078412449827976663385282021916120837408192506341443, 6318090842950331228033349517542810123596316850353637421587264886413877142612686177796023049304908696413386218992511112752788640732410845589679820003047667]
c_ = [3823539664720029027586933152478492780438595004453489251844133830947165342839393878831914879334660250621422877333022321117120398528430519794109624186204492, 1721659645750224819953244995460589691120672649732560768435214608167861246790136217219349234604724148039910656573436663379375048145045443527267790379816425, 668633520079344839648950502380059311916108468801009386138810324259146523323704014491547148973835774917331333581475920804677395949854411894556705238578896, 497860586379981076499130281851986010889356253371192266267220334713415782402939318483926418213877341511996918189750595755372560345085899109305344338944066]
p = q
rs = mask_
cs = c_

G=GF(p)
def Babai_closest_vector(M, G, target):
  small = target
  for _ in range(1):
    for i in reversed(range(M.nrows())):
      c = ((small * G[i]) / (G[i] * G[i])).round()
      small -= M[i] * c
  return target - small

m = 4
n = 1
A = matrix(ZZ, m+n, m)
for i in range(m):
    A[i, i] = p
for x in range(m):
    A[m , x] = rs[x]
lattice = IntegerLattice(A, lll_reduce=True)
 
gram = lattice.reduced_basis.gram_schmidt()[0]
target = vector(ZZ, cs)
res = Babai_closest_vector(lattice.reduced_basis, gram, target)
#print("Closest Vector: {}".format(res))
 
R = IntegerModRing(p)
M = Matrix(R, rs)
res=vector(R, res)
for i,j in zip(cs,res):
    assert len(bin(i-j))-2==50
x=((res[0])*inverse(rs[0],p)) %p

print(long_to_bytes(int(x)))
#0xGame{19255b5c7b19c790e28d87c8a8bb1d33}

方法二：SVP

我们构造如下格：

$\left( \begin{matrix} q & & & & & \\ &q & & & & \\ & &q & & & \\ & & &q & & \\ mask1 &mask2 &mask3 &mask4 &1 & \\ c1 &c2 &c3 &c4 & &1 \\ \end{matrix} \right)$

那么由等式：

$c_i = mask_ix + k_iq +noise_i$ $noise_i = c_i-mask_ix - k_iq$

所以有如下线性关系：

$(k1,k2,k3,k4,m,-1)* \left( \begin{matrix} q & & & & & \\ &q & & & & \\ & &q & & & \\ & & &q & & \\ mask1 &mask2 &mask3 &mask4 &1 & \\ c1 &c2 &c3 &c4 & &1 \\ \end{matrix} \right) = (-noise1,-noise2,-noise3,-noise4,x,-1)$

然后配一下系数使得格最后规约出的数量级相当，即可还原m

exp：

from Crypto.Util.number import *

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

L = matrix(ZZ, 6, 6)
K = 2**(318-50)
for i in range(4):
    L[i,i] = q * K
    L[4,i] = mask_[i] * K
    L[-1,i] = c_[i] * K
L[4,4] = 1
L[-1,-1] = 2**318

res = L.LLL()
print(long_to_bytes(abs(res[0][-2])))

#0xGame{19255b5c7b19c790e28d87c8a8bb1d33}

[Week 3] EzMatrix

题目描述：

1	Hint 1: 相似矩阵相似吗？相似矩阵相似吗？

题目：

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=[[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
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)))

enc.txt：

[[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和M，满足：

$A^{secret} = M$

要求求出secret。

矩阵乘法是很复杂的，因此直接做难以求解离散对数，要想办法转化成数域上的离散对数问题才行。因此需要用相似矩阵将矩阵对角化。

首先，可以用sage内置函数is_diagonalizable()判断一个矩阵是否可以对角化：

1
2
3

print(A.is_diagonalizable())

True

而A可以对角化，就代表A可以写成下面的形式：

$A = P^{-1}BP$

其中，B是一个对角矩阵。而由于可逆矩阵可以两两相消，由此可以简化A的幂次的计算：

$A^{secret} = (P^{-1}BP)^{secret} = P^{-1}B^{secret}P = C$

所以：

$B^{secret} = PCP^{-1}$

而由于B是一个对角矩阵的缘故，所以B的幂次其实就是对角线上各个元素的幂次，因此可以将矩阵的离散对数问题转化为对角线上某个元素的离散对数问题，问题得解。

exp：

from Crypto.Util.number import *
from hashlib import md5
def n2b(n):return md5(str(n).encode()).hexdigest()

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]]

n = 12
A = Matrix(GF(p), n, n, A)
C = Matrix(GF(p), n, n, c)

#print(A.is_diagonalizable())
A, P = A.diagonalization()
C = P.inverse()*C*P

a = int(A[0][0])
b = int(C[0][0])

x=discrete_log(mod(b,p),mod(a,p))
#print(x)
print("0xGame{" + n2b(x) + "}")

#0xGame{06450201eb6171d40151563d967e59ea}

当然，如果你取的元素的阶小于secret，就得不到正确结果，不过多试几组就行了，并且本题中第一个元素就能满足要求。

[Week 3] EzOverflow

题目描述：

1
2
3

真正意义上的签“到”题 

Hint 1: 密码当然也要做代码审计！

题目：

Elgamal.py：

from Crypto.Util.number import getPrime,GCD,inverse,bytes_to_long
import random

def getKey(bits):
    p = getPrime(bits)
    g = getPrime(bits//2)
    d = random.randint(1,p-2)
    y = pow(g,d,p)
    public,private = (p,g,y),d
    return public,private

def sign(m,public,private):
    m = bytes_to_long(m)
    p,g,y = public
    d = private
    while True:
        k = random.randint(1,p-1)
        if GCD(k,p-1)==1:break
    r = pow(g,k,p)
    s = ((m-d*r)*inverse(k,p-1)) % (p-1)
    return (r,s)

def verity(m,sign,public):
    m = bytes_to_long(m)
    p,g,y = public
    r,s = sign
    if pow(g,m,p) == (pow(y,r,p)*pow(r,s,p)) % p:
        return True
    else:
        return False

task.py：

from ElGamal import *
import socketserver
import signal
from secert import flag
pub,pri = getKey(512)

class Task(socketserver.BaseRequestHandler):
    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
        _hexdigest = sha256(proof.encode()).hexdigest()
        self.send(f"[+] sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
        x = self.recv(prompt=b'[+] Plz tell me XXXX: ')
        if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            return False
        return True

    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'> '):
        self.send(prompt, newline=False)
        return self._recvall()

    def timeout_handler(self, signum, frame):
        raise TimeoutError

    def handle(self):
        signal.signal(signal.SIGALRM, self.timeout_handler)
        signal.alarm(300)
        if not self.proof_of_work():
            self.send(b'[!] Wrong!')
            return

        self.send(b'Here are your public key:')
        self.send(str(pub).encode())
        while True:
            #sign
            self.send(b'Pz tell me what you want to sign?')
            message = self.recv()
            if message == b'0xGame':
                self.send(b"Permission denied!")
                quit()
            self.send(b'Here are your sign:')
            r,s = sign(message,pub,pri)
            self.send(f'r={r}\ns={s}'.encode())
            #ver
            self.send(b'Tell me your signature,if you want to get the flag.')
            r = int(self.recv())
            s = int(self.recv())

            if verity(b'0xGame',(r,s),pub):
                self.send(b'Here you are:'+flag)
                self.send(b'bye~')
                quit()
                
            else:
                self.send(b"sorry~you can't get it.")

class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10007
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    print(HOST, PORT)
    server.serve_forever()

其实是一个考察细心程度的题目。题目要求：

传入一个msg，并且msg不能是”0xGame”，靶机会返回对msg的Elgamal签名。
传入一个签名对，要求验签结果与”0xGame”相等。

而观察他的Elgamal，可以发现他省略了对msg取哈希的步骤，而直接用了m本身，也就是本身应该取：

1	s = ((H(m)-dr)inverse(k,p-1)) % (p-1)

而他却直接取了：

1	s = (m-dr)inverse(k,p-1)) % (p-1)

而m最终会模p-1，因此我们直接求p倍的”0xGame”转成的整数值，再转回字节串发送给靶机，然后直接将靶机返回的签名再传回去就能得到flag了。

exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
import string
from hashlib import sha256
from gmpy2 import powmod

#context.log_level = 'debug'

def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = r.recvuntil(b"sha256(XXXX+")
	temp = r.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						r.sendline(temp1.encode())
						return

r = remote("43.139.107.237", 10007)
proof_of_work()
r.recvuntil(b"public key:")
r.recvline()
p,g,y = eval(r.recvline().strip().decode())
m = long_to_bytes(bytes_to_long(b"0xGame")*p)
r.recvuntil(b"to sign?")
r.sendline(m)
r.recvuntil(b"your sign:")
r.recvline()
R = eval(r.recvline().strip().decode()[2:])
s = eval(r.recvline().strip().decode()[2:])
r.recvuntil(b"the flag.")
r.sendline(str(R).encode())
r.sendline(str(s).encode())
r.recvline()
print(r.recvline())

#0xGame{24b6edfdc07d71311774ed15248f434e}