diff options
Diffstat (limited to 'solve')
| -rw-r--r-- | solve/message.txt | 1 | ||||
| -rw-r--r-- | solve/pubkey.pem | 9 | ||||
| -rw-r--r-- | solve/solve.py | 29 |
3 files changed, 39 insertions, 0 deletions
diff --git a/solve/message.txt b/solve/message.txt new file mode 100644 index 0000000..a806c9f --- /dev/null +++ b/solve/message.txt @@ -0,0 +1 @@ +6213639477312598145146606285597413094756028916460209994926376562685721597532354994527411261035070313371565996179096901618661905020103824302567694878011247857685359643790779936360396061892681963343509949795893998949164356297380564973147847768251471545846793414196863838506235390508670540548621210855302903513284961283614161501466772253041178512706947379642827461605012461899803919210999488026352375214758873859352222530502137358426056819293786590877544792321648180554981415658300194184367096348141488594780860400420776664995973439686986538967952922269183014996803258574382869102287844486447643771783747439478831567060
\ No newline at end of file diff --git a/solve/pubkey.pem b/solve/pubkey.pem new file mode 100644 index 0000000..150dd45 --- /dev/null +++ b/solve/pubkey.pem @@ -0,0 +1,9 @@ +-----BEGIN PUBLIC KEY----- +MIIBITANBgkqhkiG9w0BAQEFAAOCAQ4AMIIBCQKCAQBXyI8cm57UfYRPh7KfRHlu +F85Hwv4kzBq340QyszUhJGPSOZ0HRxGABXLqaBLikBICvF8ZDMtJZtVwkEpBaXpj +ZEiK4UCxtjV/xqa0rM1RenQDu8mW39ByiV9qmh6o8qbatp2hVXUXf0zvGtuQglu9 +T+xQAarAGnDooQ4QEzRxOTK+R9GgnXDTEVf+JuVTd0+NnlAgmEcryocHkx4rycuS +qslEUb5vHlWLk6hoXOmE9IQK+vjSqK0NRlRUYqkYFRpQ3qGij03x5eaZsAUtpSMF +nrIdVrZ8keVqt181vJ9km+p2oTaxcNOmdvUUuciVXq94qQut1Uhbun8SF4sfj+/v +AgMBAAE= +-----END PUBLIC KEY-----
\ No newline at end of file diff --git a/solve/solve.py b/solve/solve.py new file mode 100644 index 0000000..aa7e1bb --- /dev/null +++ b/solve/solve.py @@ -0,0 +1,29 @@ +#!/usr/bin/env python3 + +from Crypto.PublicKey import RSA +from Crypto.Util.number import long_to_bytes +from math import isqrt, inf +from tqdm import tqdm + +pubkey = RSA.importKey(open("pubkey.pem").read()) + +# Primes close to sqrt(N) can be found quickly with Fermat factorization. + +a = isqrt(pubkey.n)+1 +prog = tqdm(total=inf) +has_sqrt = lambda n: isqrt(n)**2 == n +while not has_sqrt(a * a - pubkey.n): + prog.update() + a += 1 +prog.close() +b = isqrt(a * a - pubkey.n) + +p = a + b +q = a - b +phi = (p-1)*(q-1) +d = pow(pubkey.e, -1, phi) + +ciphertext = int(open("message.txt").read()) +plaintext = pow(ciphertext, d, pubkey.n) + +print(long_to_bytes(plaintext).decode()) |