好题分享系列 – 2023 江苏省数据安全竞赛 – hardrsa

密码学 8个月前 admin
76 0 0

首先声明,这个系列所分享的“好题” 仅代表我个人在解这道题时可能觉得这道题某一个知识点很有趣;或是很新颖;或是出题人对这道题各个知识点的衔接处理的很好,而不是单纯套娃;或是看了出题人的题解觉得特别优雅,或是觉得自己的解法很妙…… 但并不保证这道题目的实时性、原创性,可能我看到这道题的时候它已经是被抄袭过的,但我并没有遇到过原题。(题好,但不对比赛给予评价)另外为了避免纯粹的拿来主义,以给读者一定的思考、操作空间,这个系列也不会直接给出完整的解题 exp,大家自己也多试试叭!

今天这道题目来自 2023 江苏省数据安全竞赛 – hardrsa

from Crypto.Util.number import *
from random import randint
from secret import message

p, q = [getPrime(1024for _ in range(2)]
n = p * q


def pad(msg: bytes) -> bytes:
    return msg + long_to_bytes(len(msg) & 0xff) * (2048 // 8 - len(msg) - 1)


def f(x: int, poly: list[int]) -> int:
    return sum([
        poly[i] * pow(x, i, n) for i in range(len(poly))
    ]) % n


def commit(m: int, d: int, key: int, poly: list[int]) -> (int, int):
    sig = pow(m, d, n)
    c1 = (sig + pow(key, 8, n) + pow(key, 4, n) + pow(key, 2, n)) % n
    c2 = f(key, poly)
    return c1, c2


def reveal(comm: (int, int), e: int, key: int, poly: list[int]) -> int:
    c1, c2 = comm
    assert f(key, poly) == c2
    sig = (c1 - pow(key, 8, n) - pow(key, 4, n) - pow(key, 2, n)) % n
    return pow(sig, e, n)


def part1(msg):
    e = 233
    assert GCD(e, (p - 1) * (q - 1)) == 1

    m = bytes_to_long(pad(msg))
    c = pow(m, e, n)
    print(f"# Part1: RSA-Encrypted Ciphertextn"
          f"{e = }n"
          f"{n = }n"
          f"{c = }n")


def part2(msg):
    e = getPrime(256)
    assert GCD(e, (p - 1) * (q - 1)) == 1

    d = inverse(e, (p - 1) * (q - 1))
    key = getPrime(1024)
    poly = [randint(n // 2, n) for _ in range(8)]

    m = bytes_to_long(msg)
    comm = commit(m, d, key, poly)
    print(f"# Part2: RSA-Committed Promisen"
          f"{e = }n"
          f"{n = }n"
          f"{poly = }n"
          f"{comm = }n")


part1(message)
part2(message)

题目有两部分,第一部分使用 RSA 加密了 message,并给出了参数

第二部分是一个魔改了的 RSA 的承诺方案,

使用未知的 key ,给出

使用已知的 poly,给出

直观上感觉就是利用 和 poly 恢复出 key 然后再结合 搞出 来,然后计算一下 就可以了。但是实际上好像没那么容易,key 并不是那么容易恢复的。

我们还注意到加密 message 用的 ,如果能直接给 的每项升个 次,也能有 出来,但后面的 也没办法处理

思路就此卡住了。

赛后问了群友,@春哥 又拿去问了@maple,maple 立刻给出了一种很新我没见过的奇妙解法。

问了学弟 @冰,也想出了一种解法。

最后机缘巧合之下问到了出题人,预期解和学弟的这种解法比较接近。

下面我对这两种解法做一个简要的介绍。

解法一(预期)

注意到我们有以下三个式子

三条式子摆在这,显然是有把 3 式带到 2 式的冲动的,如果把 m 代进 ,这样 就只有一个公共的未知量 ,使用结式应该就能把这个 给求出来了。

但是如果直接代进去的话, 的 degree 会太高,所以这里我们还需要优化一下,考虑到  ,即 ,我们知道在模 下满足的式子一定在模 下成立,因此我们把 带进 后再模一个多项式 的度就低于 ,然后再让其和 做结式应该就能求出 了。(由于 式中有一个 pad,所以实际上还需要小小的爆破一下)(PS:自己实现一个模多项式快速幂比在 sagemath 中用 quotient 要快很多)

from copy import deepcopy

# Part1: RSA-Encrypted Ciphertext
e1 = 233
n = 
c = 

# Part2: RSA-Committed Promise
e2 = 
n = 
poly = []
comm = ()

R.<x,s>=PolynomialRing(Zmod(n)) # 这里的一个 s 变量看着没用,其实是为了让 f(x) 的类为一个多变量多项式,这样才能用后面的 Ideal 
f1 = 0
for i in range(len(poly)):
    f1 += poly[i]*x^i
f1 -= comm[1]

# 求 m 模 f1 下的 e 次
f = comm[0]-x^8-x^4-x^2
F = 1
for i in bin(e2)[2:][::-1]:
    if i == '1':
        F = (F*f)%f1
    f = (f*f)%f1

    
from Crypto.Util.number import *
for i in range(1,255):
    print(i)
    f = deepcopy(F)
    
    # 爆破一下填充,带入 f2,求 233 次
    f = f*256^(255-i)+bytes_to_long(long_to_bytes(i)*(255-i))
    FF = 1
    for i in bin(e1)[2:][::-1]:
        if i == '1':
            FF = (FF*f)%f1
        f = (f*f)%f1
    f2 = FF-c
    
    # 求 f1 和 f2 的结式,得到 (x-k)
    ans=Ideal([f1,f2]).groebner_basis()
    if ans != [1]:
        print(ans)
        break
 85%|██████████████████████████████████████████████████████████████████████████████████████████████████████▌                 | 217/254 [01:09<00:10,  3.47it/s][x + 11804593083540766953191768473584891632857464298610295673456410319093405751966708262984066641796004658380825990723088997287209884308749055923966759203552497405777188930982989535372734594928432767182748217929177897158889489317608554405915470112027996617864702664597137007278287666634774284031478676422259138168270660452037808633419847474475483128590811499676324666087197259465241042751682326546155170750087186789218676468094424397026064636516349145483400088735735646407761831516062003605276354601133145937560346030560793451506650510224288465793253472007049684097685317632151847843384406953550197684350062904939907961706]

测一下,

sage: isPrime(n-11804593083540766953191768473584891632857464298610295673456410319093405751966708262984066641796004658380825990723088997287209884308749055923966759203552497405777188930982989535372734594928432767182748217929177897158889489317608554405915470112027996617864702664597137007278287666634774284031478676422259138168270660452037808633419847474475483128590811499676324666087197259465241042751682326546155170750087186789218676468094424397026064636516349145483400088735735646407761831516062003605276354601133145937560346030560793451506650510224288465793253472007049684097685317632151847843384406953550197684350062904939907961706)
True

bingo!

解法二

根据题目,我们有式子

由于 的次数太高,这里我们直接把 也设为一个变量,于是

我们直接对这两个式子关于变量 求结式能够得到一个关于 的多项式

测试代码

from Crypto.Util.number import *
from random import randint
#from secret import message
msg = b"flag{12345678}"
p, q = [getPrime(1024for _ in range(2)]
n = p * q


def pad(msg: bytes) -> bytes:
    return msg + long_to_bytes(len(msg) & 0xff) * (2048 // 8 - len(msg) - 1)


def f(x: int, poly: list[int]) -> int:
    return sum([
        poly[i] * pow(x, i, n) for i in range(len(poly))
    ]) % n


def commit(m: int, d: int, key: int, poly: list[int]) -> (int, int):
    sig = pow(m, d, n)
    c1 = (sig + pow(key, 8, n) + pow(key, 4, n) + pow(key, 2, n)) % n
    c2 = f(key, poly)
    return c1, c2


e = 233
assert GCD(e, (p - 1) * (q - 1)) == 1

m = bytes_to_long(pad(msg))
c = pow(m, e, n)

e = getPrime(256)
assert GCD(e, (p - 1) * (q - 1)) == 1
d = inverse(e, (p - 1) * (q - 1))
key = getPrime(1024)
poly = [randint(n // 2, n) for _ in range(8)]
m = bytes_to_long(msg)
c1,c2 = commit(m, d, key, poly)

P = Zmod(n)["md,k"]
md, k = P.gens()
f = md + k**8 + k**4 + k**2 - c1
g = sum([poly[i] * k**i for i in range(len(poly))]) - c2
h = f.sylvester_matrix(g, k).det().univariate_polynomial().monic()
assert h(pow(m,d,n)) == 0

注意到 ,我们又知道 ,所以如果能直接把每一项都升 次就好了。(这样我们就能有一个关于 的多项式,和式子 求一个 GCD 就可以了)

如何做呢?这里涉及一下多项式的伴随矩阵 companion_matrix

多项式可以用一个伴随矩阵和一个基函数向量表示,其实我们在 密码学基础之线性代数 Ⅱ (qq.com) 有提到过的类似的

好题分享系列 - 2023 江苏省数据安全竞赛 - hardrsa

在 wiki 上对伴随矩阵的解释为

好题分享系列 - 2023 江苏省数据安全竞赛 - hardrsa

我们求出当前多项式  的伴随矩阵  C(h) 的特征多项式就是 ,C(h) 的特征值就是 的解,那么 就会是 对角矩阵上的一个元素。

因此我们求一个 ,那么其对角矩阵上的一个元素就会是 ,也就意味着新特征多项式的一个解是

总而言之:我们只需要对 的伴随矩阵求一个 的幂次,再取其特征多项式即可,he = (companion_matrix(h) ** e).charpoly()

验证一下

sage: he = (companion_matrix(h) ** e).charpoly()
sage: he(m)
0

bingo!

后面再爆破一下   的 padding,和 做一个  GCD 就完活了~


原文始发于微信公众号(Van1sh):好题分享系列 – 2023 江苏省数据安全竞赛 – hardrsa

版权声明:admin 发表于 2023年11月6日 上午9:50。
转载请注明:好题分享系列 – 2023 江苏省数据安全竞赛 – hardrsa | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...