commit a7f46b9f7c31c7ae936588b969bae92d561aebaa
Author: Louis Burda <quent.burda@gmail.com>
Date: Sat, 25 May 2024 00:52:54 +0200
Add challenge files and solution
Diffstat:
7 files changed, 83 insertions(+), 0 deletions(-)
diff --git a/chall/description b/chall/description
@@ -0,0 +1,13 @@
+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.
+
+After a new potentially deadly disease first occurring in Wuhan, China, the
+Chinese Corona Response Team sends messages to the remainder of the world.
+However, to avoid disturbing the population, they send out this message
+encrypted.
+
+We have intercepted all messages sent by the Chinese government and provide you
+with the public keys found on the governments' website.
+
+Please, find out if we are all going to die!
diff --git a/chall/intro-to-crypto-3.tar.gz b/chall/intro-to-crypto-3.tar.gz
Binary files differ.
diff --git a/solve/german_government.pem b/solve/german_government.pem
@@ -0,0 +1,9 @@
+-----BEGIN PUBLIC KEY-----
+MIIBHzANBgkqhkiG9w0BAQEFAAOCAQwAMIIBBwKCAQBp5eXbaoCjLFnsHsY3EPSI
+ZAfuAAehBQsiF41a6Ihl2GG2Y3GpMSDVgbpwG8EiHPK0oOPz/xX3nf5m0Penlemw
+g2UPOC+l9+W02P16hUI964Jj9ZVwG56GPjtpjT7RYpuTlFgKtQxRHJqcBZ+bfD8C
+vewfvk+psTo3bwQkVJNyehnTLoILpKoxU1zuQsxOwmA//OXXclU3alu9aT8nVhjY
+wJAOtPTyY77apSS9D7ZQ1Zx966PeS/pPs8pQMS/FhYYOicAb2QZ18yHMftyDkS6e
+OpWQ/wixRYUbHPhHvSuvGkptQJ6Lu47NN0dDxl/OrwUsM6QwZwdwq/JNruovJ29n
+AgED
+-----END PUBLIC KEY-----
+\ No newline at end of file
diff --git a/solve/intercepted-messages.txt b/solve/intercepted-messages.txt
@@ -0,0 +1,3 @@
+An unsere Freunde in Deutschland: 3999545484320691620582760666106855727053549021662410570083429799334896462058097237449452993493720397790227435476345796746350169898032571754431738796344192821893497314910675156060408828511224220581582267651003911249219982138536071681121746144489861384682069580518366312319281158322907487188395349879852550922320727712516788080905540183885824808830769333571423141968760237964225240345978930859865816046424226809982967625093916471686949351836460279672029156397296634161792608413714942060302950192875262254161154196090187563688426890555569975685998994856798884592116345112968858442266655851601596662913782292282171174885
+To our friends in the US: 7156090217741040585758955899433965707162947606350521948050112381514262664247963697650055668324095568121356193295269338497644168513453950802075729741157428606617001908718212348868412342224351012838448314953813036299391241983248160741119053639242636496528707303681650997650419095909359735261506378554601448197330047261478549324349224272907044375254024488417128064991560328424530705840832289740420282298553780466036967138660308477595702475699772675652723918837801775022118361119700350026576279867546392616677468749480023097012345473460622347587495191385237437474584054083447681853670339780383259673339144195425181149815
+нашим друзьям в россии: 9343715678106945233699669787842699250821452729365496523062308278114178149719235923445953522128410659220617418971359137459068077630717894445019972202645078435758918557351185577871693207368250243507266991929090173200996910881754217374691865096976051997491208921880703490275111904577396998775470664002942232492755888378994040358902392803421017545356248082413409915177589953816030273082416979477368273328755386893089597798104163894528521114946660635364704437632205696975201216810929650384600357902888251066301913255240181601332549134854827134537709002733583099558377965114809251454424800517166814936432579406541946707525
diff --git a/solve/russian_government.pem b/solve/russian_government.pem
@@ -0,0 +1,9 @@
+-----BEGIN PUBLIC KEY-----
+MIIBIDANBgkqhkiG9w0BAQEFAAOCAQ0AMIIBCAKCAQEAkU9rlTNWhbo39Plb+Yk+
+18ArsTHW16SjfO1ywx9Sg6ZXdOpn04xwKdHnUaglZLLBib9sdsdeB/hzjpc2NoVv
+NGHVkhH+lvgYpBk6CtRTLMHllf8YfcjOFJCtGa6eSy6mOgcO5+ktQ2xkUvoHAH46
+lmLu60Mq6QNUoHScP8qPpeJepz1kDDUuFlqFfO+hYor6F+Aktz54JG4SQC5xq2Wr
+vtztgwZinTEZStiL8HsIWr5yNQD9AuROcEIHnPuBWMbtiLff0lJm5BmfaO0cWC/Z
+Wfh6Vy96uMe1TvMnIF9xDH8nCyKd16NzFVguWSGGWtx7dKxzgWviG0LgvdkRfi+x
+MwIBAw==
+-----END PUBLIC KEY-----
+\ No newline at end of file
diff --git a/solve/solve.py b/solve/solve.py
@@ -0,0 +1,37 @@
+#!/usr/bin/env python3
+
+from Crypto.PublicKey import RSA
+from Crypto.Util.number import long_to_bytes
+from gmpy2 import iroot
+from sympy import primefactors
+
+# Hastad Boardcast: Multiple unpadded ciphertexts with small e.
+# Use Chinese Remainder Theorem to extract plaintext.
+# Possible since N1*N2*N3 larger than M^e for e = 3.
+
+recipients = [
+ RSA.importKey(open("german_government.pem").read()),
+ RSA.importKey(open("us_government.pem").read()),
+ RSA.importKey(open("russian_government.pem").read()),
+]
+ciphertexts = [int(l.split(": ")[1]) for l in open("intercepted-messages.txt").readlines()]
+
+# C1 = K mod N1, C2 = K mod N2, C3 = K mod N3
+# K = C1 * N2 * N3 * pow(N2 * N3, -1, N1) + ... (mod N1 * N2 * N3)
+# K % N1 = C1 * N2 * N3 * pow(N2 * N3, -1, N1) = C1
+
+N = 1
+for r in recipients:
+ assert(r.e == 3)
+ N *= r.n
+
+K = 0
+for i in range(3):
+ K += ciphertexts[i] * (N // recipients[i].n) \
+ * pow(N // recipients[i].n, -1, recipients[i].n)
+K %= N
+
+plaintext, real = iroot(K, 3)
+assert(real)
+
+print(long_to_bytes(plaintext).decode().lstrip("A"))
diff --git a/solve/us_government.pem b/solve/us_government.pem
@@ -0,0 +1,9 @@
+-----BEGIN PUBLIC KEY-----
+MIIBHzANBgkqhkiG9w0BAQEFAAOCAQwAMIIBBwKCAQBykvErl/K7aBCrbejBKxFA
+FSSKOP1Ra/UaWOajRDpLcFgGJT1wnnDeC1Z647HcASI57lGK+5s2IxQAVai9OjAl
+TqSZh0O7sO3xEpxA4JjOKBB/NtMXdrLxUxQsr3njJeR4CPb1z93fViR6KsKJpb/C
+C6cjuota0m33qWWPgk6FCcMlNi/IzTBPcj8z6/CwZcbWCyubnTPvCznOQbHH469U
+f20PZcp/tBIoJxu33K+LcH+UF1HrhafSxYV44RIV0wHNcsDRkX8S4VFZXuP+QIp1
+SdnphuWCVJUUEOTt0diPN3bfMpPINVs82/N7JtuDjSBGqhhiiFHfxog+FzbA76uj
+AgED
+-----END PUBLIC KEY-----
+\ No newline at end of file
