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)