cscg20-rsa

CSCG 2020 Challenge 'RSA Service'
git clone https://git.sinitax.com/sinitax/cscg20-rsa
Log | Files | Refs | sfeed.txt

gen_rsa_values.py (1266B)

      1from sage.all import *
      2import random
      3c = 6453808645099481754496697330465
      4m = 1067267517149537754067764973523953846272152062302519819783794287703407438588906504446261381994947724460868747474504670998110717117637385810239484973100105019299532993569
      5ref = sqrt(m)
      6succeed = False
      7while not succeed:
      8    ps = [3]
      9    for i in range(100):
     10        ps.append(next_prime(ps[-1]))
     11#   print ps;exit()
     12    out = []
     13    for i in range(2):
     14        p = 0
     15        while not is_prime(p+1):
     16            used = set()
     17            p = 1
     18            while p <= ref:
     19                tp = random.choice(ps)
     20                used.add(tp)
     21                p *= tp ** random.randint(1, 20)
     22            p *= 2
     23            # print p
     24        for u in used:
     25            # print u
     26            ps.pop(ps.index(u))
     27        out.append(p)
     28    print(out)
     29    pp, qp = out
     30    p = pp + 1
     31    q = qp + 1
     32    try:
     33        resp = discrete_log(Mod(c, p), Mod(m, p))
     34        resq = discrete_log(Mod(c, q), Mod(m, q))
     35    except:
     36        continue
     37    print('tried')
     38    if resp < (p-1)/2 and resq < (q-1)/2:
     39        print('good1')
     40        e = crt([resp, resq], [(p-1)/2, (q-1)/2])
     41        if e < p*q:
     42            print('e: ', e)
     43            print('p: ',p)
     44            print('q: ',q)
     45            succeed = True