]> git.somenet.org - pub/jan/ctf-seminar.git/blob - writeups/icecrax/asis2019/understanding_duality_of_(c-t).py
Update ctfzone19.md
[pub/jan/ctf-seminar.git] / writeups / icecrax / asis2019 / understanding_duality_of_(c-t).py
1 import random
2 from Crypto.Util.number import *
3
4 def gen_rand(nbit, l):
5     R = []
6     while True:
7         r = random.randint(0, nbit-1)
8         if r not in R:
9             R.append(r)
10             if len(R) == l:
11                 break
12     R.sort()
13     rbit = '1'
14     for i in range(l-1):
15         rbit += (R[i+1] - R[i] - 1) * '0' + '1'
16     rbit += (nbit - R[-1] - 1) * '0' 
17     return int(rbit, 2)
18
19 def genkey(p, l):
20     n = len(bin(p)[2:]) # n = 229
21     f, skey = gen_rand(n, l), gen_rand(n, l)
22     pkey = f * inverse(skey, p) % p # Return the inverse of u mod v.
23     return (p, pkey), skey
24
25 def encrypt(msg, pkey):
26     p, g = pkey
27     msg, enc, n = bytes_to_long(msg), [], len(bin(p)[2:])
28     for b in bin(msg)[2:]:
29         s, t = gen_rand(n, l), gen_rand(n, l)
30         c = (s * g + t) % p
31         if b == '0':
32             enc.append((c, t))
33         else:
34             enc.append((p-c, t))
35     return enc
36
37 def sanity(p, l):
38     pkey, skey = genkey(p, l)
39     enc = encrypt(long_to_bytes(0b1010100001111), pkey)
40     p, g = pkey
41     for check, t in enc:
42         s = ((check - t) * inverse(g, p)) % p
43         print(bin(s))
44
45 p = 862718293348820473429344482784628181556388621521298319395315527974911
46 l = 5
47
48 sanity(p, l)