NewStar CTF week5 Crypto wp

easy_ecc

ecc的模板题，稍加推理就会发现c1=m+c2*k因此做一个减法就行，需要注意的点是c1,c2必须放到ecc里面过一道才能出正确结果

k = 86388708736702446338970388622357740462258632504448854088010402300997950626097
p = 64408890408990977312449920805352688472706861581336743385477748208693864804529
a = 111430905433526442875199303277188510507615671079377406541731212384727808735043
b = 89198454229925288228295769729512965517404638795380570071386449796440992672131
E = EllipticCurve(GF(p),[a,b])
c1 = E([10968743933204598092696133780775439201414778610710138014434989682840359444219,50103014985350991132553587845849427708725164924911977563743169106436852927878] )
c2 = E([16867464324078683910705186791465451317548022113044260821414766837123655851895,35017929439600128416871870160299373917483006878637442291141472473285240957511])
c_left = 15994601655318787407246474983001154806876869424718464381078733967623659362582
c_right = 3289163848384516328785319206783144958342012136997423465408554351179699716569
m=c1-k*c2
print(long_to_bytes(c_left//m[0])+long_to_bytes(c_right//m[1]))

没e也能玩

一开始看到dp以为是一个dp泄露题，结果一细看，不是哥们

搞定

RSA？cmd5!

这道题感觉教学意义更重，也是直观的看到了数字签名的过程，flag采用公钥e加密，而m生成的MD5使用私钥d加密，这也就意味着，我们使用公钥e可以解密数字签名，从而验证消息的来源

c = 119084320846787611587774426118526847905825678869032529318497425064970463356147909835330423466179802531093233559613714033492951177656433798856482195873924140269461792479008703758436687940228268475598134411304167494814557384094637387369282900460926092035234233538644197114822992825439656673482850515654334379332
s = 5461514893126669960233658468203682813465911805334274462134892270260355037191167357098405392972668890146716863374229152116784218921275571185229135409696720018765930919309887205786492284716906060670649040459662723215737124829497658722113929054827469554157634284671989682162929417551313954916635460603628116503
[n,e] = [139458221347981983099030378716991183653410063401398496859351212711302933950230621243347114295539950275542983665063430931475751013491128583801570410029527087462464558398730501041018349125941967135719526654701663270142483830687281477000567117071676521061576952568958398421029292366101543468414270793284704549051, 65537]
m0=long_to_bytes(pow(s,e,n))
print(m0)
m0='adm0n12'
flag = 'flag{th1s_1s_my_k3y:' + m0 + '0x' + hashlib.sha256(m0.encode()).hexdigest() + '}'
print(flag)

解出md5的值后，随便找个在线网站解密即可

md5在线解密破解,md5解密加密

格格你好棒

进去看脚本很简单，给的信息几乎等于没有，一看就是触及到知识盲区的东西，果断看wp

格密码这部分看了很久，对原理的部分依然不是很清楚，不过至少摸清楚了这类题怎么解决。

附上几个介绍这部分的网址：

【CTF-Crypto】格密码基础（例题较多，非常适合入门！）_ctf crypto-CSDN博客

crypto-从NTRU算法入门格密码 - 先知社区

简单的说，这是一个格密码的NTRU问题，那么这一部分问题怎么解决呢？首先了解它的加密过程

格密码笔记（一）

从公钥生成过程，可以得到hf=g+kp,借此，我们可以构造格，而对于其他题目，可以依据一开始的基础公式构造形如格的式子，关键是理清楚谁是f,谁是g，谁是h。

构造到这里，需要通过Hermite定理检查一下位数，

左边向量v的值是根号下（f**2+g**2），右边n代表维数，一般是二维，det是基的行列式的值

左右两边的bit_length()相差越小，结果越精确，如果相差过大，则构造b=2**x,x根据需要调整。

b1 = gmpy2.iroot(2 * b * p, 2)[0]  
print(b1.bit_length()) # 381b2 = gmpy2.iroot(f**2+(b*g)**2, 2)[0]  
print(b2.bit_length())  #376

变换的过程其实就是等式两边同时*b，只不过左边乘到了[h,p]这个列向量上形成[h*b,b*p],而右边乘到g上形成b*g，所以最后解密出来的结果也是b*g。

调整完毕之后，就可以根据LLL算法计算最小基，即等式右边的（f,g）

那么看一下这道题的脚本，感受一下 

from Crypto.Util.number import *
import random
flag = b'******'
m = bytes_to_long(flag)a = getPrime(1024)
b = getPrime(1536)p = getPrime(512)
q = getPrime(512)
r = random.randint(2**8, 2**9)
assert ((p+2*r) * 3*a + q) % b < 70c = pow(m, 0x10001, p*q)print(f'c =', c)
print(f'a =', a)
print(f'b =', b)

这里有一个断言assert ((p+2*r) * 3*a + q) % b < 70，其实就相当于h=((p+2*r)*3*a+q)%b,再化简，得(p+2*r)*3*a=q-h+kb，我们对比公钥得生成公式：

   hf=g+kp

那么其实f就相当于（p+2r），同样,h=3*a,g=q-h,p=b,所以构造矩阵

解出得f=p+2*r,g=q-h，奇怪的是，在这道题里不用Hermite定理调整也能得出正确答案

from Crypto.Util.number import *
import gmpy2
c = 75671328500214475056134178451562126288749723392201857886683373274067151096013132141603734799638338446362190819013087028001291030248155587072037662295281180020447012070607162188511029753418358484745755426924178896079516327814868477319474776976247356213687362358286132623490797882893844885783660230132191533753
a = 99829685822966835958276444400403912618712610766908190376329921929407293564120124118477505585269077089315008380226830398574538050051718929826764449053677947419802792746249036134153510802052121734874555372027104653797402194532536147269634489642315951326590902954822775489385580372064589623985262480894316345817
b = 2384473327543107262477269141248562917518395867365960655318142892515553817531439357316940290934095375085624218120779709239118821966188906173260307431682367028597612973683887401344727494920856592020970209197406324257478251502340099862501536622889923455273016634520507179507645734423860654584092233709560055803703801064153206431244982586989154685048854436858839309457140702847482240801158808592615931654823643778920270174913454238149949865979522520566288822366419746x=2**512
L = Matrix(ZZ,[[1,3*a*x],[0,b*x]])
p,q = L.LLL()[0] # 这里的 [0] 是取其中的最小向量
p,q = abs(p),abs(q)# 爆破 r 和 h
for r in range(2**8,2**9):for h in range(70):pp = p - 2*rqq = q//x + hphi = (pp-1)*(qq-1)if gcd(phi,65537) != 1:continuem = power_mod(c,inverse_mod(65537,phi),pp*qq)if b'flag' in long_to_bytes(m):print(long_to_bytes(m))

学以致用

刚进历上一道题的折磨，实在不想看论文了，后面心态调整好了再回来更新