CatCTF出题小记 | 随缘的博客

CatCTF的题目总结以及出题的动机、想法。

DDH_Game

图片来自 A Graduate Course in Applied Cryptography(Version 0.5)

这道题就是在让大家求解椭圆曲线上的DDH问题(ECDDHP)。

解法一

由于题目中的BLS曲线是配对友好曲线，所以可以计算双线性对。

双线性对满足 $e(aG, bG) = e(G, abG)$

这就给了我们一个解DDHP的后门。因此如果随便选一个椭圆曲线点群，ECDDH假设通常是不成立的，并且攻击方法很简单：看等式$e(aG, bG) = e(G, cG)$ 是否成立。个人认为这是一个很优美的做法。

# sagemath 9.5
from Crypto.Util.number import long_to_bytes

# Before running, modify your filename and add "DDH_instances = " at the beginning of the file.
load('DDH_instances.sage')

# curve
p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
a = K(0x00)
b = K(0x04)
E = EllipticCurve(K, (a, b))
# G = E(0x17F1D3A73197D7942695638C4FA9AC0FC3688C4F9774B905A14E3A3F171BAC586C55E83FF97A1AEFFB3AF00ADB22C6BB, 0x08B3F481E3AAA0F1A09E30ED741D8AE4FCF5E095D5D00AF600DB18CB2C04B3EDD03CC744A2888AE40CAA232946C5E7E1)
E.set_order(0x73EDA753299D7D483339D80809A1D80553BDA402FFFE5BFEFFFFFFFF00000001 * 0x396C8C005555E1568C00AAAB0000AAAB)

G = E(3745324820672390389968901155878445437664963280229755729082200523555105705468830220374025474630687037635107257976475, 2578846078515277795052385204310204126349387494123866919108681393764788346607753607675088305233984015170544920715533)
n = G.order()

# Embedding degree of the curve
k = 12


def solve_ECDDHP(DDH_instances, G, Ep, m, n):
    """
    Parameters:
        DDH_instances - list consists of (aG, bG, cG), where aG, bG, cG are EC_point.xy()
        m - embedding degree of <G>
        n - G's order. 
    """
    sols = []
    
    Fpm.<x> = GF(p^m)
    Epm = Ep.base_extend(Fpm) 
    
    G = Epm(G)
    
    for ins in DDH_instances:
        aG, bG, cG = ins
        aG = Epm(aG); bG = Epm(bG); cG = Epm(cG)
        
        # e_aG_bG = aG.weil_pairing(bG, n)
        e_aG_bG = aG.tate_pairing(bG, n, m)
        
        e_G_cG = G.tate_pairing(cG, n, m)
        if e_aG_bG == e_G_cG:
            sols.append(True)
        else:
            sols.append(False)
    
    return sols

sols = solve_ECDDHP(DDH_instances, G, E, k, n)
# print(sols)

pt = 0
for i in range(len(sols)):
    pt += sols[i] * (2^i)

flag = long_to_bytes(pt)
print(flag)
print(b'CatCTF{' + flag + '}')

解法二

其实是非预期解，不过测题的时候队里有其他师傅想到了，这个思路也是直击DDH问题中的’Decisional’ 。

题目中点G的阶为

做法类似Pohlig-Hellman算法中使用的原理，不过我们不用算出a, b和c，而是在模3，模11，模10177等的意义下计算出a,b和c。再对应考察同余式是否成立： $ab \equiv c \pmod{3}$ $ab \equiv c \pmod{11}, … $ 。如果成立那么大概率有$ab = c$。打印出来看看flag对不对就行了。

# sagemath 9.5
from Crypto.Util.number import long_to_bytes
# Before running, modify your filename and add "DDH_instances = " at the beginning of the file.
load('DDH_instances.sage')


p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
a = K(0x00)
b = K(0x04)
E = EllipticCurve(K, (a, b))
E.set_order(0x73EDA753299D7D483339D80809A1D80553BDA402FFFE5BFEFFFFFFFF00000001 * 
0x396C8C005555E1568C00AAAB0000AAAB)
G = E(3745324820672390389968901155878445437664963280229755729082200523555105705468830220374025474630687037635107257976475, 
      2578846078515277795052385204310204126349387494123866919108681393764788346607753607675088305233984015170544920715533)


def Pohlig_Hellman(G, Y, ord_G, facts):
    """
    Using the idea of Pohlig-Hellman.
    G: EC group generator G
    facts: list, some small factors of the group order
    return x: discrete log of Y modulo prod(facts) 
    """
    new_bases = [(ord_G // facts[i])*G for i in range(len(facts))]
    assert len(new_bases) == len(facts)
    xi = [new_bases[i].discrete_log((ord_G // facts[i])*Y, facts[i]) for i in range(len(facts))]
    # print(f"xi = {xi}")
    
    x = CRT(xi, facts)
    return x

order = G.order()
# factors of order, pairwise coprime
facts = [3, 11, 10177]
s = prod(facts)
m = ''

import tqdm
for i in tqdm.tqdm(range(len(DDH_instances))):
    aG, bG, cG = DDH_instances[i]
    aG = E(aG); bG = E(bG); cG = E(cG)
    a, b, c = [Pohlig_Hellman(G, E(Pt), order, facts) for Pt in (aG, bG, cG)]
    if (a*b) % s == c:
        m += '1'
    else:
        m += '0'
print(m)

print(long_to_bytes(int(m[::-1], 2)))

动机和细节

早就想把密码理论与密码攻击相结合出一个题目，之前想到DDH，上面写嵌入度较低的椭圆曲线上DDH假设不成立。于是我找了一条BLS曲线来出这道题，题面非常简单就是进行DDH Game。DDH假设是一个很重要的话题，Game则是密码理论中的security game，双线性对也是很重要的密码学工具。不过题目难度比较低，希望能够抛砖引玉。

cat_theory

题解

根据交换图，两个明文先做加法再加密，其结果与先加密再做密文乘法相同。因此CatCrypto是一个同态加密，具有加法同态性。

其实这道题是Paillier-DJN算法，Paillier的一个变种。见Paillier半同态加密：原理、高效实现方法和应用

交换图原图

from Crypto.Util.number import long_to_bytes

m1_plus_m2 = 127944711034541246075233071021313730868540484520031868999992890340295169126051051162110
m2_plus_m3 = 63052655568318504263890690011897854119750959265293397753485911143830537816733719293484
m3_plus_m1 = 70799336441419314836992058855562202282043225138455808154518156432965089076630602398416

m = (m1_plus_m2 + m2_plus_m3 + m3_plus_m1) // 2
print(long_to_bytes(m))

"""
b'CatCTF{HE_sch3m3_c4n_b3_a_c4t_eg0ry}'
"""

动机

因为是Cat CTF，并且说出题可以不限于传统的CTF思路，所以想涉及一些猫论(category theory, 范畴论)。找了一些资料来看：Categorical & Diagrammatic methods In Cryptography and Communication
确实有一些人提出范畴论与密码学结合，想法很有意思（比如p35~36的内容）。但这些想法似乎还没有太多应用。并且我自己对范畴论了解也很有限，也没试过自己编造一个密码方案。一时间想不到怎么用这个出一道题。

正好想到Craig Gentry（第一个全同态方案的提出者）给出的用交换图概括同态加密，交换图可以算是范畴论的东西，并且在密码学中也还是经常能看到的。于是干脆来个Paillier-DJN同态加密方案（Paillier的改进方案），给一张交换图来提示同态性。

cat’s gift

题解

跨年气氛题，想起Amann的Analysis上有一只猫猫，翻了一会儿找到一个与pi相关的公式。注意到flag示例中 CatCTF{apple} CatCTF{banana}是小写开头英文单词，都是食物，以及题目中提到这是一份礼物，因此提交的flag不是pi而是pie。

有四种解法

法一：直接猜结果是pie
法二：手算，写出arctanx的幂级数展开，然后把x=1带进去

法三：编程算近似值，然后猜

def solve_gift(n=100):
    ans = 0
    for i in range(n):
        ans += (-1)**i * 1/(2*i + 1)
        
    return ans * 4
    
solve_gift(n=10000000)

法四：问猫猫（根据题目描述的提示）

找到Amann的 Analysis I p389

Leibniz公式

后记

其实pi=pie也是一种数学文化，3.14那天有一些人会吃派庆祝，因此就把这个题放在了跟数学最相近的crypto里面。出题时感觉应该很自然能想到pie吧，没想到很多朋友因为没有get到所以没做出来…

忘记了这是一种小众文化，出题人随缘在此向各位深表歉意。