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)