首发于安全客
这次比赛密码学一共有四题，除了EZRSA真的比较easy，其他题还是有一些做头 ，尤其最后一道ECDSA个人感觉出的挺不错的。
先来两道RSA
EZRSA
1234567891011121314151617181920212223 |
from Crypto.Util.number import *from gmpy2 import *from secret import *assert(flag.startwith('flag{')) and (flag.endwith('}'))assert(is_prime(beta) and len(bin(beta)[2:]) == 512) assert(len(bin(x)[2:]) == len(bin(y)[2:]))# This is tip!!!assert(tip == 2*x*y*beta + x + y)p = 2*x*beta + 1q = 2*y*beta + 1assert(is_prime(p) and is_prime(q))n = p*qe = 65537m = bytes_to_long(flag)enc = powmod(m,e,n) #n = #beta = #e = |
题目提供了n，beta，e
这道题意思很明确了，n = p * q = 4xybeta ^ 2 + 2(x+y )beta + 1
很自然的能得到 tip = (n-1) //（2 * beta）
然后我们给tip模上beta，我们就能得到 (x+y)%beta ，如果我们能够获得x + y，那么显然我们也能获得x * y，然后解个方程即可获得x和y，然后就能获得p和q，继而解密rsa得到flag
那么对于获得 x + y这个问题，由于beta是512位，我们去看一下n的位数为 2068，那么平均一下p的位数就是1034了，那么x的位数大概就是1034 - 1 - 512 = 521，x + y 估计也就是522位左右，和beta位数差了10位左右，完全是可以暴力的范围
参考脚本
1234567891011121314151617181920212223 |
n =e = 65537enc = beta =tip = (n-1)//(2*beta)for i in range(10000): #获取x + y的值 x_add_y = tip % beta + beta*i #根据x + y 获取 x * y x_mul_y = (tip - x_add_y)//(2*beta) try: if iroot(x_add_y**2 - 4*x_mul_y,2)[1]: #解方程获取x 和 y y = (x_add_y - iroot(x_add_y**2 - 4*x_mul_y,2)[0] )//2 x = x_add_y - y p = 2*y*beta + 1 q = 2*x*beta + 1 phi = (p-1)*(q-1) d = inverse(e,int(phi)) print long_to_bytes(pow(enc,d,n)) except: pass |
reverse
1234567891011121314151617181920212223242526 |
from Crypto.Util.number import *from gmpy2 import *from secret import *assert(flag.decode().startswith('flag{')) and (flag.decode().endswith('}'))def reverse(x):y = 0while x != 0:y = y*2 + x%2x = x // 2return ywhile True:p = getStrongPrime(512)q = reverse(p)if is_prime(q):breakn = p*qe = 65537m = bytes_to_long(flag)enc = powmod(m,e,n)#n = #enc = |
这一道题就是一个正常的RSA，但是生成的p和q再二进制上是相反的，即若p是11（0b1011），那么q就是13（0b1101）
其实有点像一个算法题，我们可以通过测试得知，如果p * q = n ，那么p的最低位 乘以 q的最低为 等于 n 的最低为，基于这个事实，我们可以从最低位一位一位爆破p和q，但是实际操作后会发现，可能性太多，无法剪枝，那么复杂度过高的情况下这种做法是不可取的。
所以我们在以上的基础再加一个判断：
由于我们知道 p的高位是q的低位，那么我们将p反过来然后末尾补0，补齐512位，这个肯定会比真真的q小，同理将q反过来末尾补0，这样子我们可以得到p_min 和 q_min，那么p_min * q_min 肯定是小于 n的，如果p_min * q_min > n，那么就可以舍弃这个可能性。
同理末尾补1就能得到p_max 和 q_max ，如果p_max * q_max < n 那么这种可能行也可以舍弃
参考代码
12345678910111213141516171819202122232425262728293031323334353637383940 |
from Crypto.Util.number import *from gmpy2 import *from itertools import productn = 158985980192501034004997692253209315116841431063210516613522548452327355222295231366801286879768949611058043390843949610463241574886852164907094966008463721486557469253652940169060186477803255769516068561042756903927308078335838348784208212701919950712557406983012026654876481867000537670622886437968839524889ct = 103728452309804750381455306214814700768557462686461157761076359181984554990431665209165298725569861567865645228742739676539208228770740802323555281253638825837621845841771677911598039696705908004858472132222470347720085501572979109563593281375095145984000628623881592799662103680478967594601571867412886606745max_idx = 1pq_list = [(1,1)]for idx in range(1, 512): mod = 2 ** (idx + 1) new_pq_list = [] for p, q in pq_list: for i, j in product(range(2), repeat=2): np = i * 2 ** idx + p nq = j * 2 ** idx + q #judge1 if (np * nq) % mod != n % mod: continue#judge2 rp_min = int('{:b}'.format(np)[::-1].ljust(512, '0'), 2) rq_min = int('{:b}'.format(nq)[::-1].ljust(512, '0'), 2) rp_max = int('{:b}'.format(np)[::-1].ljust(512, '1'), 2) rq_max = int('{:b}'.format(nq)[::-1].ljust(512, '1'), 2) if n < rp_min * rq_min or rp_max * rq_max < n: continue#可能性集合 new_pq_list.append((np, nq)) print(len(new_pq_list)) print(idx) pq_list = new_pq_list |
运行代码大概要个十多分钟。然后可能性集合能达到快二十万，我们遍历这个集合，找到其中的两个512位素数即为p和q，进而RSA解密即可。
然后是两个需要交互的题目，给的是Crypto_System，一个给了源码， 一个没给，但两道题核心都是构造一个等式然后解方程。先来看看这个给了源码的。
Crypto_System
1234567891011121314151617181920212223242526272829303132333435363738394041424344 |
# These three are constantsp = 12039102490128509125925019010000012423515617235219127649182470182570195018265927223g = 10729072579307052184848302322451332192456229619044181105063011741516558110216720725# random generationm1 = "test1"m2 = "test2"# Initializationr1, s1 = sign(m1)# r1 will be provided to playerdef int2str(data, mode="big"): if mode == "little": return sum([ord(data[_]) * 2 ** (8 * _) for _ in range(len(data))]) elif mode == "big": return sum([ord(data[::-1][_]) * 2 ** (8 * _) for _ in range(len(data))])def get_parameter(m): x = int2str(m, 'little') y = powmod(g, x, p) a = bytes_to_long(hashlib.sha256(long_to_bytes(y).rjust(128, "\0")).digest()) b = powmod(a, a, p - 1) h = powmod(g, b, p) return y, h, bdef sign(m): y, h, b = get_parameter(m) r = getStrongPrime(512) s = (y * powmod(h, r, p)) % p return str(r),str(s)def verify(m, r, s): y, h, b = get_parameter(m) if s == ((y * powmod(h, r, p)) % p): return True else: return False# Give me the (r2,s2)if r2 != r1 and s2 == s1 and verify(m2, r2, s2): print("Congratulation!Here is your flag: %s" % flag) |
这道题的他会提供两个msg，然后你需要给他们签名，要求是，签名中两者的s相等，但是r不相等
我们提取一下信息，
签名的验证是 s == ((y * powmod(h, r, p)) % p)
其中 x 就是要被签名的信息， y = powmod(g, x, p)， h = powmod(g, b, p) ， b = powmod(a, a, p - 1) ，
a = bytes_to_long(hashlib.sha256(long_to_bytes(y).rjust(128, “\0”)).digest()) ,显得挺麻烦，但是由于我们是知道参数x, g, p的，因此y是一个已知的常数，从而a也可以看成一个已知常数即可，继而b、h也会是一个已知常数。（全都已知，完全不用管了）
那么s = powmod(g, x, p) * powmod(powmod(g, b, p), r, p)) == powmod(g, x + br, p)
我们要给不同的x，有着相同的s和不同的r，那么可以构造我们的目标等式： powmod(g, x1 + b1r1, p) == powmod(g, x2 + b2r2, p)
很自然的我们可以把这个方程转化为 x1 + b1r1 == x2 + b2r2，由于模数p，那么g应该是一个原根叭。那么阶就是p - 1了，所以完整的应该是 x1 + b1r1 ≡ x2 + b2r2 （mod p - 1 ） 固定r1，那么有r2 = (x1 + b1r1 - x2) * inverse(b2 , p-1)，
这里会有一个问题，就是b2 和 p - 1不互素怎么办？撞就完事了，由于决定b2的是msg2，每次连接msg2都是随机的，所以撞就完事，经过测试，互素的概率还是蛮高的。
或者也可以提前将方程两边整除b2 和 p - 1的公因数，但如果没法整除，那就GG了，还是撞叭23333
参考脚本
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192 |
from pwn import *from Crypto.Util.number import *sh=remote("139.129.98.9","30001")from pwnlib.util.iters import mbruteforcefrom hashlib import sha256import hashlibfrom math import gcdcontext.log_level = 'debug'def proof_of_work(sh): sh.recvuntil("XXXX+") suffix = sh.recvuntil(')').decode("utf8")[:-1] log.success(suffix) sh.recvuntil("== ") cipher = sh.recvline().strip().decode("utf8") proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() == cipher, string.ascii_letters + string.digits, length=4, method='fixed') sh.sendlineafter("Give me XXXX:", proof)proof_of_work(sh)sh.interactive()# These three are constantsp = 12039102490128509125925019010000012423515617235219127649182470182570195018265927223g = 10729072579307052184848302322451332192456229619044181105063011741516558110216720725def int2str(data, mode="big"): if mode == "little": return sum([ord(data[_]) * 2 ** (8 * _) for _ in range(len(data))]) elif mode == "big": return sum([ord(data[::-1][_]) * 2 ** (8 * _) for _ in range(len(data))])def get_parameter(m): x = int2str(m, 'little') y = pow(g, x, p) a = bytes_to_long(hashlib.sha256(long_to_bytes(y).rjust(128, b"\0")).digest()) b = pow(a, a, p - 1) h = pow(g, b, p) return y, h, bdef sign(m): y, h, b = get_parameter(m) r = getStrongPrime(512) s = (y * powmod(h, r, p)) % p return str(r),str(s)def verify(m, r, s): y, h, b = get_parameter(m) if s == ((y * powmod(h, r, p)) % p): return True else: return Falsesh.recvuntil("Here is the frist message(64 bytes):")message1 = bytes.fromhex(sh.recvuntil("\n")[:-1].decode()).decode()sh.recvuntil("Here is the second message(64 bytes):")message2 = sh.recvuntil("\n")[:-1].decode()print("message2",message2)message2 = bytes.fromhex(message2).decode()sh.recvuntil("The frist message's 'r':")message1_r = int(sh.recvuntil("\n")[:-1])sh.recvuntil("Please choice your options:")#根据题目获取各个参数message1_y, message1_h, message1_b = get_parameter(message1)message1_s = (message1_y * pow(message1_h, message1_r, p)) % pmessage2_s = message1_smessage2_y, message2_h, message2_b = get_parameter(message2)#######################################################解题核心#x1+b1r1=x2+b2r2x1 = int2str(message1, 'little')b1 = message1_br1 = message1_rx2 = int2str(message2, 'little')b2 = message2_btmp = gcd(b2,p-1)print(tmp)r2 = (((x1+b1*r1-x2)//tmp)*inverse(b2//tmp,p-1))%(p-1)######################################################sh.sendline("3")sh.recvuntil("Please give me the (r,s) of the second message:")print("("+str(r2)+","+str(message2_s)+")")sh.sendline("("+str(r2)+","+str(message2_s)+")")sh.interactive() |
ECDSA
这道题贼狠，源码都不给，来看一看MENU叭
123456789101112131415161718192021222324 |
[] Received 0xd bytes: b'Give me XXXX:'[] Sent 0x5 bytes: b'bwUI\n'[] Received 0x4f bytes: b'Hello,guys!Welcome to my ECC Signature System!I promise no one can exploit it!\n'[] Received 0x269 bytes: b'Howevers if you can exploit it in 10 times,I will give what you want!\n' b'Here is the frist message(64 bytes):fipoN9jy/*@~J:] PcZY8{&X!7v+\\duTln_#k(WK^Q2L)<SbM$-V=Ex3Uw|h,%}F\n' b'Here is the second message(64 bytes):%wh-(xJ4kR+7<^Zv9,Ol\\Kp/&"FHbc_ D@Y*mSos}V?.#L{!3B8QiP=nqCI[y:X2\n' b'Try to calculate the same signature for this two messages~\n' b'(((Notice: curve = SECP256k1, hashfunc = sha1)))\n' b'\n' b'ECC Signature System:\n' b' 1. Show your pubkey\n' b' 2. Generate new prikey\n' b' 3. Update your pubkey\n' b' 4. Sign a message\n' b' 5. Verify a message\n' b' 6. Exploit\n' b' 7. Exit\n' b'\n' b'You have only 10 times to operate!\n' b'Please choice your options:' |
根据题目名这是一个ECDSA的签名系统，完了呢要求是给这他提供的两个msg签名，不仅验证要通过，而且签名还得一样。
先来看看这几个功能，
功能1是显示公钥，（可能要利用）
功能2是重新生成一个私钥，（应该是没用的，没啥意义，生成后就是告诉你更新后的公钥）
功能3是更新你的公钥，你来输入（这个肯定有点用）
功能4是帮你签个名 （也许用得上）
功能5是验证签名 （可以，但没必要）
功能6就是整完了用来获取flag的了。
六个功能一眼看来也就这个功能3可以用了。这里需要一点前置知识（现查就可以了，一样的），就是ECDSA签名的验证规则
这种资料CSDN一抓一大把。
最后是判断 v = r，即 X.x = dG.x ,我们可以把验证公式提取出来，也即 $es^{-1}G + rs^{-1}Q = dG$
注意到由于验证用的是公钥Q，然后题目是提供篡改公钥这个功能的，我们知道ECDSA中$Q = kG$, 其中k是私钥，那么其实等价于我们是可以篡改私钥的，即我们用自己的私钥去给一个信息签名，完了后把用于验证的公钥给改成我们自己的公钥，验证同样也是可以通过的。那么整个过程系统的私钥都不参与了。
解决了签名验证的问题，剩下来就是解决如何让他们的签名保持一致了。
回到验证公式 $es^{-1}G + rs^{-1}Q = dG$
其中e是我们的消息，可以看作已知常数，r和s是我们能控制的，G是固定的，Q是公钥，也是我们自己决定，d是签名时用的随机数，整个签名的过程我们都能掌握，自然d也有我们决定，然后d会决定r，因为r = dG.x， 那么r也就固定下来了，只剩Q和s了。
我们把公式约一约，去掉G后就是 $es^{-1} + rs^{-1}k = d => e + rk = ds => s = (e + rk)*d^{-1}$
由于两个msg的s要保持一直，那么我们构造的等式就是$ (e_1 + rk) * d^{-1} = (e_2 + rk) * d^{-1}$
很显然啊，因为d不能等于0，这等式不可能成立啊，于是陷入僵局。
但这里我们忘了一个很重要的性质，就是，我们最后验证的是v = r，而r是什么，r = dG.x，我们要知道的是，椭圆曲线是一个关于x轴对称的图形，所以其实 r = -dG.x。华点都发现了，这题就解决了，
等式变为$ (e_1 + rk) * d^{-1} = (e_2 + rk) * (-d)^{-1}$
化成同余式就是$ (e_1 + rk) * d^{-1} \equiv (e_2 + rk) * (-d)^{-1} \pmod{n}$
有 $e_1 + rk \equiv -e_2 -rk\pmod{n}$
有 $k \equiv \frac{-e1-e2}{2r}\pmod{n}$
然后怕【我们去查一下这条曲线的参数即可
参考脚本
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172 |
from pwn import *from Crypto.Util.number import *sh=remote("139.129.98.9","30002")from pwnlib.util.iters import mbruteforcefrom hashlib import sha256import hashlibfrom math import gcdcontext.log_level = 'debug'a=0b=7q=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2Fgx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8order=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141ecc = EllipticCurve(GF(q), [a,b])G = ecc(gx,gy)import hashlibdef sha1(content): return hashlib.sha1(content).digest()def proof_of_work(sh): sh.recvuntil("XXXX+") suffix = sh.recvuntil(')').decode("utf8")[:-1] log.success(suffix) sh.recvuntil("== ") cipher = sh.recvline().strip().decode("utf8") proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() == cipher, string.ascii_letters + string.digits, length=4, method='fixed') sh.sendlineafter("Give me XXXX:", proof)proof_of_work(sh)sh.recvuntil("Here is the frist message(64 bytes):")msg1 = sh.recvuntil("\n")[:-1]sh.recvuntil("Here is the second message(64 bytes):")msg2 = sh.recvuntil("\n")[:-1]message = hex(bytes_to_long(msg1))[2:]e1=bytes_to_long(sha1(msg1))e2=bytes_to_long(sha1(msg2))#######################################################解题核心#pubkey = sh.recvuntil("\n")[:-2].decode()#r=[d * G].xd=12321r=int((d*G)[0])new_k = ((-e1-e2)*inverse(2*r,order))%ordernew_Q = new_k * Gnew_S = ((e1 + new_k*r)*inverse(d,order))%ordernewpubkey = hex(new_Q[0]).replace("0x","").rjust(64,"0")+hex(new_Q[1]).replace("0x","").rjust(64,"0")newsignature = hex(r).replace("0x","").rjust(64,"0")+hex(new_S).replace("0x","").rjust(64,"0")######################################################sh.recvuntil("Please choice your options:")sh.sendline("3")sh.recvuntil("Please give me your public_key(hex):")sh.sendline(newpubkey)sh.recvuntil("Please choice your options:")sh.sendline("6")sh.recvuntil("Please give me the signature(hex) of the frist message:\n")sh.sendline(newsignature)sh.recvuntil("Please give me the signature(hex) of the second message:\n")sh.sendline(newsignature)sh.interactive() |
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 [email protected] - source:Van1sh的小屋
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论