bi0sCTF 2024 crypto

Posted on

rr

  • task:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    flag = ...
    n = ...
    rr = ...
    ks = [randint(0, rr**(i+1)) for i in range(20)]
    c1 = pow(sum(k*flag**i for i, k in enumerate(ks)), (1<<7)-1, n)
    c2 = pow(flag, (1<<16)+1, n)
    ks = [pow(69, k, rr**(i+2)) for i, k in enumerate(ks)]
    print(f"{ks = }")
    print(f"{c1 = }")
    print(f"{c2 = }")

    明显就是要还原 ，也就是求一堆 DLP。

    这里面有个重要细节是 在 内随机，DLP 的模数是 。

    然后进行一番搜索，找到这个，他里面提到如果是形如 的 DLP，我们可以通过一个神秘映射直接求出 是多少。

    具体而言，令 ，则有 。

    那么本题就很好做了，用上面的方法把 还原，然后求一个多项式 gcd 就好。

lalala

  • task：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    flag = "bi0sctf{%s}" % f"{randint(2**39, 2**40):x}"

    p = random_prime(2**1024)
    unknowns = [randint(0, 2**32) for _ in range(10)]
    unknowns = [f + i - (i%1000)  for i, f in zip(unknowns, search("{(.*)}", flag).group(1).encode())]

    output = []
    for _ in range(100):
        aa = [randint(0, 2**1024) for _ in range(1000)]
        bb = [randint(0, 9) for _ in range(1000)]
        cc = [randint(0, 9) for _ in range(1000)]
        output.append(aa)
        output.append(bb)
        output.append(cc)
        output.append(sum([a + unknowns[b]^2 * unknowns[c]^3 for a, b, c in zip(aa, bb, cc)]) % p)

    print(f"{p = }")
    print(f"{output = }")

    这个题比较简单，我们只有 10 个 ，但有 100 个方程，我们直接把所有 都看成变量，就是 100 个变量 100 个线性方程组，可以直接解。

    然后 时我们就知道了 ，直接求出 ，就没了。

daisy_bell

  • task：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    p = getPrime(1024)
    q = getPrime(1024)
    n = p*q
    c = pow(bytes_to_long(flag), 65537, n)

    print(f"{n = }")
    print(f"{c = }")
    print(f"{p>>545 = }")
    print(f"{pow(q, -1, p) % 2**955 = }")

    考验大家 copper 板子的时候到了！ 最后一行明显是一个可以看成 的多项式，然后和 一起做 copper 就好了。

    但我为啥每次做 copper 都得 玄学调参 加 等好久 呢。

Katyusha's Campervan

  • task:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    p = getPrime(1024)
    q = getPrime(1024)
    e = getPrime(132)
    n = p*q
    hint = pow(e, -1, (p-1)*(q-1))
    hint %= p-1
    hint %= 2**892
    c = pow(3, int.from_bytes(flag), n**5) * pow(randint(0, n**5), n**4, n**5) % n**5

    print(f"{n = }")
    print(f"{e = }")
    print(f"{c = }")
    print(f"{hint = }")

    说实话，我认为这个题是 rr 和 daisy_bell 的缝合，不知道为啥放出来。 这个跟 daisy_bell 形式基本一致，直接拿来求出 。

    然后这个 有扰动，注意到 。

    直接 ，这样后面的扰动就没了，然后用 rr 的方法求出 就好了。

challengename

  • task:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    flag = open("flag", "rb").read()[:-1]

    magic = os.urandom(16)

    p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
    a = ###REDACTED###
    b = ###REDACTED###
    G = ###REDACTED###

    q = G.order()

    def bigsur(a,b):
        a,b = [[a,b],[b,a]][len(a) < len(b)]
        return bytes([i ^ j for i,j in zip(a,bytes([int(bin(int(b.hex(),16))[2:].zfill(len(f'{int(a.hex(), 16):b}'))[:len(a) - len(b)] + bin(int(b.hex(),16))[2:].zfill(len(bin(int(a.hex(), 16))[2:])) [:len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:])] [i:i+8], 2) for i in range(0,len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:]),8)]) + b)])

    def bytes_to_long(s):
        return int.from_bytes(s, 'big')

    def genkeys():
        d = random.randint(1,q-1)
        pubkey = Public_key(G, d*G)
        return pubkey, Private_key(pubkey, d)

    def sign(msg,nonce,privkey):
        hsh = md5(msg).digest()
        nunce = md5(bigsur(nonce,magic)).digest()
        sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nunce))
        return json.dumps({"msg": msg.hex(), "r": hex(sig.r), "s": hex(sig.s)})

    def enc(privkey):
        x = int(flag.hex(),16)
        y = pow((x**3 + a*x + b) % p, (p+3)//4, p)
        F = ellipticcurve.Point('--REDACTED--', x, y)
        Q = F * privkey.secret_multiplier
        return (int(Q.x()), int(Q.y()))

    pubkey, privkey = genkeys()
    print("Public key:",(int(pubkey.point.x()),int(pubkey.point.y())))
    print("Encrypted flag:",enc(privkey))

    nonces = set()

    for _ in '01':
        try:
            msg = bytes.fromhex(input("Message: "))
            nonce = bytes.fromhex(input("Nonce: "))
            if nonce in nonces:
                print("Nonce already used")
                continue
            nonces.add(nonce)
            print(sign(msg,nonce,privkey))
        except ValueError:
            print("No hex?")
            exit()

    首先给了两个点 Public_key 和 enc_flag，所以能把曲线直接求出来。

    然后 bigsur 不知道具体是啥东西，但是如果 nonce 传 00 和 0000 都是明显不影响 magic 的。

    然后这个 sign 第二个参数就是那个应该是随机数的 k，这样我们就能在 k 不变的情况下搞到两次签名，这样就有方程： 其中 是这个曲线的阶。有人直接拿 当模数卡了 2h，我不说是谁

    所以就能搞到 ，就没了。

Predictable

  • task: no

    a long description:

    1
    2
    3
    4
    Can you help me test out this PRNG I implemented? 
    I'm inserting a backdoor, but I'm sure you can't find it. 
    Oh btw, I did some optimizing, so version 2 is faster. 
    You can still try out version 1 though. They're the same anyway.

    不会的神秘题。

    连上去看到好像是用 Elliptic Curve 去生成这个随机数，交互允许的事情是生成一个随机数，或者你去预测下一个随机数，然后就啥都没有了。

    感觉不太能理解这东西的可做性，就是光盯这个交互是啥都不知道的，然后 description 提到的 backdoor 我也没啥思路，是不是得要 pwn 大手子来啊。

    然后这个 version 也很怪啊，optimize 难道会增加漏洞吗？