跳转至
2024 | ångstromCTF | crypto

random rabin

#rabin cryptosystem

题目

I heard that the Rabin cryptosystem has four decryptions per ciphertext. So why not choose one randomly?

random_rabin.py 
 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
from random import SystemRandom
from Crypto.Util.number import getPrime
from libnum import xgcd

random = SystemRandom()

def primegen():
    while True:
        p = getPrime(512)
        if p % 4 == 3:
            return p

def keygen():
    p = primegen()
    q = primegen()
    n = p * q
    return n, (n, p, q)

def encrypt(pk, m):
    n = pk
    return pow(m, 2, n)

def decrypt(sk, c):
    n, p, q = sk
    yp, yq, _ = xgcd(p, q)
    mp = pow(c, (p + 1)//4, p)
    mq = pow(c, (q + 1)//4, q)
    s = yp * p * mq % n
    t = yq * q * mp % n
    rs = [(s + t) % n, (-s - t) % n, (s - t) % n, (-s + t) % n]
    r = random.choice(rs)
    return r

def game():
    pk, sk = keygen()
    print(f'pubkey: {pk}')
    secret = random.randbytes(16)
    m = int.from_bytes(secret, 'big')
    print(f'plaintext: {decrypt(sk, encrypt(pk, m))}')
    guess = bytes.fromhex(input('gimme the secret: '))
    return guess == secret

if __name__ == '__main__':
    for _ in range(64):
        success = game()
        if not success:
            exit()

    with open('flag.txt') as f:
        flag = f.read().strip()
        print(flag)

解题思路

  • 已知公钥和密文的任一解密结果，需要连续猜对 64 次明文
  • 由 secret 加密得到密文的任一解密结果再加密的结果相同

  • 而 secret 相对于公钥较小，其平方仍然小于公钥，因此获得密文后直接开方的结果即为 secret

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
    import pwn
from Crypto.Util.number import long_to_bytes
from gmpy2 import isqrt
from tqdm import tqdm

io = pwn.remote("challs.actf.co", 31300)

for _ in tqdm(range(64)):
    pk = int(io.recvline().split(b':')[-1])
    pt = int(io.recvline().split(b':')[-1])
    guess = isqrt(pow(pt, 2, pk))
    io.sendlineafter(b"secret: ", long_to_bytes(guess).hex().encode())

io.interactive()

Flag

actf{f4ncy_squ4re_r00ts_53a370c33f192973}

最后更新: 2024年5月28日 20:58:01
Contributors: YanhuiJessica

评论