cscg20-cry1

commit e5649fac45abbf0d0f516b70720e00a04126c553
Author: Louis Burda <quent.burda@gmail.com>
Date:   Fri, 24 May 2024 14:51:48 +0200

Add challenge files and solution

Diffstat:
A
chall/description
 | 
9
+++++++++
A
chall/intro-to-crypto-1.tar.gz
 | 
0

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

5 files changed, 47 insertions(+), 0 deletions(-)
diff --git a/chall/description b/chall/description
@@ -0,0 +1,9 @@
+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. For an introduction to the first challenge visit the authors
+`step by step guide`_.
+
+For my new RSA key I used my own SecurePrimeService which definitely generates a
+HUGE prime!
+
+.. _step by step guide: https://static.allesctf.net/Intro_Crypto.html
diff --git a/chall/intro-to-crypto-1.tar.gz b/chall/intro-to-crypto-1.tar.gz
Binary files differ.
diff --git a/solve/message.txt b/solve/message.txt
@@ -0,0 +1 @@
+4522827319495133992180681297469132393090864882907734433792485591515487678316653190385712678072377419115291918844825910187405830252000250630794128768175509500175722681252259065645121664124102118609133000959307902964132117526575091336372330412274759536808500083138400040526445476933659309071594237016007983559466411644234655789758508607982884717875864305554594254277210539612940978371460389860098821834289907662354612012313188685915852705277220725621370680631005616548237038578956187747135229995137050892471079696577563496115023198511735672164367020373784482829942657366126399823845155446354953052034645278225359074399
+\ No newline at end of file
diff --git a/solve/pubkey.pem b/solve/pubkey.pem
@@ -0,0 +1,9 @@
+-----BEGIN PUBLIC KEY-----
+MIIBITANBgkqhkiG9w0BAQEFAAOCAQ4AMIIBCQKCAQBRz/RtnuMgltbIBsvH3y0d
+O+p+ey/E6CbZ/F4YeZkS3KFQspxlwPnmZFM5bOfeYxoPmmdFE4thJbvNGFqhLrCa
+ShvYBhGMl6jeBe0L5rRfwcnpk3GS9YvEpcwnZ4A8CyE0KvXLjzSv+xpuwlIMdl2H
+UhxoSNvYMYEuzG2Ls9YXM7Drw1LPZNREXJlVcpIvST1xiZWdsjIeG6xZJfpW3Gn2
+hY7+66ClqddroZgYcVOSdCTl97aAmKuMEEQrc9FJAnz8N9AwBWM3w+D0IWz0MiOW
+dEG2CO7CpkjozoV4lMZlAwwBJFYpJ5s4f829w1thZ3FbVL1VVhgNmvJQS1J6kPrn
+AgMBAAE=
+-----END PUBLIC KEY-----
+\ No newline at end of file
diff --git a/solve/solve.py b/solve/solve.py
@@ -0,0 +1,26 @@
+#!/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())
+
+# Small primes can be found with naive approach.
+
+for i in tqdm(range(3, isqrt(pubkey.n), 2), total=inf):
+    if pubkey.n % i == 0:
+        p = i
+        break
+else:
+    raise
+
+q = pubkey.n // p
+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())