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