cscg20-cry2

CSCG 2020 Challenge 'Intro To Crypto 2'
git clone https://git.sinitax.com/sinitax/cscg20-cry2
Log | Files | Refs | sfeed.txt

solve.py (665B)

      1#!/usr/bin/env python3
      2
      3from Crypto.PublicKey import RSA
      4from Crypto.Util.number import long_to_bytes
      5from math import isqrt, inf
      6from tqdm import tqdm
      7
      8pubkey = RSA.importKey(open("pubkey.pem").read())
      9
     10# Primes close to sqrt(N) can be found quickly with Fermat factorization.
     11
     12a = isqrt(pubkey.n)+1
     13prog = tqdm(total=inf)
     14has_sqrt = lambda n: isqrt(n)**2 == n
     15while not has_sqrt(a * a - pubkey.n):
     16    prog.update()
     17    a += 1
     18prog.close()
     19b = isqrt(a * a - pubkey.n)
     20
     21p = a + b
     22q = a - b
     23phi = (p-1)*(q-1)
     24d = pow(pubkey.e, -1, phi)
     25
     26ciphertext = int(open("message.txt").read())
     27plaintext = pow(ciphertext, d, pubkey.n)
     28
     29print(long_to_bytes(plaintext).decode())