2020 RoarCTF 密码学 Write Up

 

这次比赛密码学一共有四题，除了EZRSA真的比较easy，其他题还是有一些做头 ，尤其最后一道ECDSA个人感觉出的挺不错的，想了还挺久的，做题的时候思维有点跳不出来，还是太菜了。

先来两道RSA

EZRSA

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 + 1
q = 2*y*beta + 1

assert(is_prime(p) and is_prime(q))

n = p*q
e = 65537
m = 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)//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位左右，完全是可以暴力的范围

参考脚本

n =
e = 65537
enc = 
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

from Crypto.Util.number import *
from gmpy2 import *
from secret import *

assert(flag.decode().startswith('flag{')) and (flag.decode().endswith('}'))
def reverse(x):
    y = 0
    while x != 0:
        y = y*2 + x%2
        x = x // 2
    return y


while True:
    p = getStrongPrime(512)
    q = reverse(p)
    if is_prime(q):
        break

n = p*q
e = 65537
m = 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 那么这种可能行也可以舍弃

参考代码

from Crypto.Util.number import *
from gmpy2 import *
from itertools import product

n = 158985980192501034004997692253209315116841431063210516613522548452327355222295231366801286879768949611058043390843949610463241574886852164907094966008463721486557469253652940169060186477803255769516068561042756903927308078335838348784208212701919950712557406983012026654876481867000537670622886437968839524889
ct = 103728452309804750381455306214814700768557462686461157761076359181984554990431665209165298725569861567865645228742739676539208228770740802323555281253638825837621845841771677911598039696705908004858472132222470347720085501572979109563593281375095145984000628623881592799662103680478967594601571867412886606745

max_idx = 1

pq_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

# These three are constants
p = 12039102490128509125925019010000012423515617235219127649182470182570195018265927223
g = 10729072579307052184848302322451332192456229619044181105063011741516558110216720725

# random generation
m1 = "test1"
m2 = "test2"

# Initialization
r1, s1 = sign(m1)
# r1 will be provided to player

def 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, b

def 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

参考脚本

from pwn import *
from Crypto.Util.number import *
sh=remote("139.129.98.9","30001")
from pwnlib.util.iters import mbruteforce
from hashlib import sha256
import hashlib
from math import gcd
context.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 constants
p = 12039102490128509125925019010000012423515617235219127649182470182570195018265927223
g = 10729072579307052184848302322451332192456229619044181105063011741516558110216720725


def 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, b

def 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

sh.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)) % p
message2_s = message1_s
message2_y, message2_h, message2_b = get_parameter(message2)


######################################################
#解题核心
#x1+b1r1=x2+b2r2

x1 = int2str(message1, 'little')
b1 = message1_b
r1 = message1_r
x2 = int2str(message2, 'little')
b2 = message2_b
tmp = 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叭

[DEBUG] Received 0xd bytes:
    b'Give me XXXX:'
[DEBUG] Sent 0x5 bytes:
    b'bwUI\n'
[DEBUG] Received 0x4f bytes:
    b'Hello,guys!Welcome to my ECC Signature System!I promise no one can exploit it!\n'
[DEBUG] 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} ≡ (e_2 + rk) * (-d)^{-1} mod{n}

有 e_1 + rk ≡ -e_2 -rk mod{n}

有 k ≡ (-e1-e2) // 2r mod{n}

然后怕【我们去查一下这条曲线的参数即可

参考脚本

from pwn import *
from Crypto.Util.number import *
sh=remote("139.129.98.9","30002")
from pwnlib.util.iters import mbruteforce
from hashlib import sha256
import hashlib
from math import gcd
context.log_level = 'debug'

a=0
b=7
q=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
order=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

ecc = EllipticCurve(GF(q), [a,b])
G = ecc(gx,gy)

import hashlib

def 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].x
d=12321
r=int((d*G)[0])
new_k = ((-e1-e2)*inverse(2*r,order))%order
new_Q = new_k * G
new_S = ((e1 + new_k*r)*inverse(d,order))%order
newpubkey = 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()