2024 n1junior crypto

Posted on Edited on

Junior RSA

  • 先看 RSA。

    容易求出 ，又 ，求个逆就能算 。

    然后现在就已知 和 ， 展开为 ，其中 。

    所以可以求出 ，就能算 ，这样就 都算出来了。

Masquerade

  • 看下 task

    1
    2
    3
    4
    5
    assert Auth_Code in long_to_bytes(Ticket[2]) \
            and Ticket[2]%int(Ticket_Office._key['p'])

    if Ticket_Office._verify(Ticket[2], Ticket[:2]):
        print(f"Welcome to the masquerade, Enjoy it! {FLAG}")

    主要是过这两关。

    要绕过这个 函数，进 pycryptodome 里面看源码，长这样：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def _verify(self, m, sig):
        r, s = sig
        y, q, p, g = [self._key[comp] for comp in ['y', 'q', 'p', 'g']]
        if not (0 < r < q) or not (0 < s < q):
            return False
        w = Integer(s).inverse(q)
        u1 = (w * m) % q
        u2 = (w * r) % q
        v = (pow(g, u1, p) * pow(y, u2, p) % p) % q
        return v == r

    注意到它没有检测 的范围。

    所以这就很简单了，令 取大一点， 可以直接算。

    我是手动交互的。

CC@

  • 我认为这是很好的题，但有人试图 attack aes-gcm。

    首先经过很长时间的努力学会了放弃，我们终于发现这个 oracle 返回的唯一信息是长度。

    然后一个容易发现的是，我们知道了一组 后，构造 ，可以使得返回的长度变化。

    那么我们第一步可以不断传 ，直到长度 ，这样我们就能知道 的最高位。

    然后我们从高往低确定每个位 ，我们取一个 ，这样我们每次只需要选择一个比较好的 就能让这个位是 区分开。

    自然是取 上取整，根据整除理论，只需要 就可以使得 和周围都不一样，这样就能求出 。

    100 次交互机会比较少，所以得连两次。

IEV@L

  • 没出，写点想法。

    一个让人不明所以的 task，有了上一次的经验，我们先放弃去弄清楚 到底是啥。

    注意到 比较小，hint 又给了是 meet in the middle，所以我们考虑暴力。

    想成功 hack，我们相当于找到一个起点和终点不变的新路径，所以只要从起点和终点一起搜大概率能在中间碰撞。

    此时，我遇到了一个问题是从终点搜完全不好搜，导致这个搜索的效率极低，我这个脚本至少得 30min 以上。

    希望出题人能教教怎么快速出解。

    现在是赛后，我知道我出了啥问题了：

    1. 因为交互是必须构造可见字符串，所以我当时搜索是每次添加一个可见字符，这个让搜索代价直接 *8。
    2. 正因为是添加可见字符，导致逆向的路径搜的很困难，大大减少了碰撞概率。

    正确的搜索方式应该是：

    先正反按 task 给的方式搜索，然后 meet in the middle 找到可能路径 。

    注意到这个情况下的 的路径需要重新计算。

    然后 check 最终的路径是否合法就可以了。