cscg20-cry2

commit 84a4ee4091c8547bc576c3eb9ddcec96a887d1dc
Author: Louis Burda <quent.burda@gmail.com>
Date:   Fri, 24 May 2024 15:09:56 +0200

Add challenge files and solution

Diffstat:
A
chall/description
 | 
6
++++++
A
chall/intro-to-crypto-2.tar.xz
 | 
0

A
solve/message.txt
 | 
2
++
A
solve/pubkey.pem
 | 
10
++++++++++
A
solve/solve.py
 | 
29
+++++++++++++++++++++++++++++

5 files changed, 47 insertions(+), 0 deletions(-)
diff --git a/chall/description b/chall/description
@@ -0,0 +1,6 @@
+This is an introductory challenge for beginners which want to dive into the
+world of Cryptography. The three stages of this challenge will increase in
+difficulty.
+
+I learned my lesson from the mistakes made in the last challenge! Now p and q
+are huge, I promise!
diff --git a/chall/intro-to-crypto-2.tar.xz b/chall/intro-to-crypto-2.tar.xz
Binary files differ.
diff --git a/solve/message.txt b/solve/message.txt
@@ -0,0 +1 @@
+6213639477312598145146606285597413094756028916460209994926376562685721597532354994527411261035070313371565996179096901618661905020103824302567694878011247857685359643790779936360396061892681963343509949795893998949164356297380564973147847768251471545846793414196863838506235390508670540548621210855302903513284961283614161501466772253041178512706947379642827461605012461899803919210999488026352375214758873859352222530502137358426056819293786590877544792321648180554981415658300194184367096348141488594780860400420776664995973439686986538967952922269183014996803258574382869102287844486447643771783747439478831567060
+\ No newline at end of file
diff --git a/solve/pubkey.pem 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
@@ -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())