We are given this code that implements RSA with e = 1.
#!/usr/bin/env python3from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytese =1d =-1while d ==-1: p =getPrime(512) q =getPrime(512) phi =(p -1)*(q -1) d =inverse(e, phi)n = p * qflag =b"XXXXXXXXXXXXXXXXXXXXXXX"pt =bytes_to_long(flag)ct =pow(pt, e, n)print(f"n = {n}")print(f"e = {e}")print(f"ct = {ct}")pt =pow(ct, d, n)decrypted =long_to_bytes(pt)assert decrypted == flag
Since in RSA, ct = m^e mod n. So, e = 1 would make it ct = m mod n. The value of m would most likely be less than n, which results in ct = m.
Here's the solver code.
Flag: crypto{saltstack_fell_for_this!}
Modulus Inutilis
The challenge name literally translates to "useless modulus", which hints about the vulnerability. We are given this source code.
Here, e = 3 is used. The value for n is very big and the value for m is low (since the message is very short). It is very likely that m^3 is less than n, resulting in ct = m^3, rendering the modulus useless.
The main thing to note here is that e is as big as n, while d is notably small. In the condition where d is small enough, Wiener's attack might be possible.
Wiener's attack works by approximating e/n to k/d using continued fractions. Basically, a continued fractions takes a fraction and find the "simplest" form. Adding more terms mean converging into the most correct value. We are hoping that at least one of the convergents of e/n equals to k/d. In fact, when d is small enough, a convergent which equals to k/d is guaranteed.
I tried implementing the solution using Sage's continued_fraction() function, but it didn't work for large numbers. So, I used a code from mananpal1997 which turned out to be working well.
Here's the mathematical derivation.
Now, if d is small enough, 1/(d*phi) wouldn't be too small, and we can hope for k/d to coincide with one of the convergents.
For this challenge's solution, I attached two files: continued_fractions.py and solve.py.
continued_fractions.py
solve.py
Output of solve.py
Flag: crypto{s0m3th1ng5_c4n_b3_t00_b1g}
Crossed Wires
We are given this source code.
Here, we are given both n and d, but the d will be useless in directly decrypting the ciphertext, since the plaintext was encrypted using a different e. However, there is a way that we can efficiently factor n given d. This article explains such algorithm.
This is a continuation of the Wiener's attack (Everything is Big) challenge. This time, the size of d is raised just so that it's slightly above Wiener's boundary.
Boneh-Durfee showed that Wiener's boundary might've been too tight and that an extended attack can efficiently factor N as long as d < N^(0.292).
In this challenge, even with the modification, N can still be factored using Wiener's attack. However, in the spirit of the challenge, I tried searching for the most convenient implementation of Boneh-Durfee attack to use, and came across this repo.
According to the description, some of the messages are exactly the same. Meaning, there is one value of m that's encrypted using different public moduli. For this scenario, we can implement Hastad's broadcast attack using Chinese Remainder Theorem (CRT).
The tricky part is that among the ciphertexts, only some of them have the same m. Therefore, we need to try every single combination and hope that at least a group of them have the same m.
from Crypto.Util.number import *
n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
print(long_to_bytes(ct))
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes
e = 3
d = -1
while d == -1:
p = getPrime(1024)
q = getPrime(1024)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
n = p * q
flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")
pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag
from Crypto.Util.number import *
from gmpy2 import *
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
m = iroot(ct,e)[0]
print(long_to_bytes(m))
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, bytes_to_long
FLAG = b"crypto{?????????????????????????}"
m = bytes_to_long(FLAG)
def get_huge_RSA():
p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
while True:
d = getPrime(256)
e = pow(d,-1,phi)
if e.bit_length() == N.bit_length():
break
return N,e
N, e = get_huge_RSA()
c = pow(m, e, N)
print(f'N = {hex(N)}')
print(f'e = {hex(e)}')
print(f'c = {hex(c)}')
e*d ≡ 1 mod phi
e*d = k*phi + 1 --> div. by d*phi
e/phi = k/d + 1/(d*phi)
# Taken from https://gist.github.com/mananpal1997/73d07cdc91d58b4eb5c818aaab2d38bd
def rational_to_contfrac(x,y):
# Converts a rational x/y fraction into a list of partial quotients [a0, ..., an]
a = x // y
pquotients = [a]
while a * y != x:
x, y = y, x - a * y
a = x // y
pquotients.append(a)
return pquotients
def convergents_from_contfrac(frac):
# computes the list of convergents using the list of partial quotients
convs = [];
for i in range(len(frac)): convs.append(contfrac_to_rational(frac[0 : i]))
return convs
def contfrac_to_rational(frac):
# Converts a finite continued fraction [a0, ..., an] to an x/y rational.
if len(frac) == 0: return (0,1)
num = frac[-1]
denom = 1
for _ in range(-2, -len(frac) - 1, -1): num, denom = frac[_] * num + denom, num
return (num, denom)
from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
from sage.all import *
from continued_fractions import *
N = int("b8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d", 16)
e = int("9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3", 16)
c = int("3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474", 16)
# Taken from https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/wieners-attack
def wiener(e, n):
# Take the convergents of e/n
cf = rational_to_contfrac(e,n)
convergents = convergents_from_contfrac(cf)
# Check each convergents
for kd in convergents:
k = kd[0]
d = kd[1]
# Check if k and d meet the requirements
# These are characteristics that we know from k and d to speed up the process
if k == 0 or d%2 == 0 or e*d % k != 1:
continue
phi = (e*d - 1)//k
# Create the polynomial
x = PolynomialRing(RationalField(), 'x').gen()
f = x**2 - (n-phi+1)*x + n
roots = f.roots()
# Check if there are two roots
if len(roots) != 2:
continue
# Check if the roots (p and q) computes for n
p, q = int(roots[0][0]), int(roots[1][0])
if p*q == n:
return d
return None
# Wiener's attack is feasible when d < [1/3 * (N)^(1/4)
d_limit = iroot(N,4)[0]//3
print(f"Testing Wiener's atttack feasibility...")
print(f"The value \"d\" must have less than approx. {d_limit.bit_length()} bits")
print(f"Here, \"d\" is 256 bits")
print(f"==========================================")
# Performing Wiener's attack
print(f"Performing Wiener's attack...")
d = wiener(e, N)
print(f"d = {d}")
assert not d is None, "Wiener's attack failed (\"d\" not found) :("
m = pow(c, d, N)
print(f"Flag: {long_to_bytes(m)}")
Testing Wiener's atttack feasibility...
The value "d" must have less than approx. 511 bits
Here, "d" is 256 bits
==========================================
Performing Wiener's attack...
d = 79434351637397000170240219617391501050474168352481334243649813782018808904459
Flag: b'crypto{s0m3th1ng5_c4n_b3_t00_b1g}'
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse
import math
from gmpy2 import next_prime
FLAG = b"crypto{????????????????????????????????????????????????}"
p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
e = 0x10001
d = inverse(e, phi)
my_key = (N, d)
friends = 5
friend_keys = [(N, getPrime(17)) for _ in range(friends)]
cipher = bytes_to_long(FLAG)
for key in friend_keys:
cipher = pow(cipher, key[1], key[0])
print(f"My private key: {my_key}")
print(f"My Friend's public keys: {friend_keys}")
print(f"Encrypted flag: {cipher}")
from Crypto.Util.number import *
import random
n = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
e = 65537
d = 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
ct = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
friend_pubkey = [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)]
fn = [k[0] for k in friend_pubkey]
fe = [k[1] for k in friend_pubkey]
# Implementation from https://www.di-mgt.com.au/rsa_factorize_n.html
def factorize_from_d(n, e, d):
k = (d*e) - 1
for g in range(2,n-1):
t = k
while t % 2 == 0:
t = t//2
x = pow(g,t,n)
if x > 1:
y = GCD(x-1,n)
if y > 1:
p = y
q = n//p
return p, q
else:
continue
# Factorize n
p, q = factorize_from_d(n,e,d)
phi = (p-1)*(q-1)
# Decrypt ciphertext
for e in fe:
d = pow(e,-1,phi)
ct = pow(ct,d,n)
print(long_to_bytes(ct))
from __future__ import print_function
from sage.all import *
from continued_fractions import *
from Crypto.Util.number import *
from gmpy2 import *
N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5
# Taken from https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/wieners-attack
def wiener(e, n):
# Take the convergents of e/n
cf = rational_to_contfrac(e,n)
convergents = convergents_from_contfrac(cf)
# Check each convergents
for kd in convergents:
k = kd[0]
d = kd[1]
# Check if k and d meet the requirements
# These are characteristics that we know from k and d to speed up the process
if k == 0 or d%2 == 0 or e*d % k != 1:
continue
phi = (e*d - 1)//k
# Create the polynomial
x = PolynomialRing(RationalField(), 'x').gen()
f = x**2 - (n-phi+1)*x + n
roots = f.roots()
# Check if there are two roots
if len(roots) != 2:
continue
# Check if the roots (p and q) computes for n
p, q = int(roots[0][0]), int(roots[1][0])
if p*q == n:
return d
return None
# Wiener's attack is feasible when d < [1/3 * (N)^(1/4)
d_limit1 = iroot(N,4)[0]//3
print(f"Testing Wiener's atttack feasibility...")
print(f"The value \"d\" must have less than approx. {d_limit1.bit_length()} bits")
print(f"Here, \"d\" is 512 bits")
print(f"==========================================")
# According to Boneh-Durfee, Wiener's bound was not tight. They showed that the same attack is feasible as long as d < N^(0.292)
d_limit2 = int(floor(mpz(N)**mpfr(0.292)))
print(f"Testing Boneh-Durfee's atttack feasibility...")
print(f"The value \"d\" must have less than approx. {d_limit2.bit_length()} bits")
print(f"Here, \"d\" is 512 bits")
print(f"==========================================")
# Performing Wiener's attack
print(f"Performing Wiener's attack...")
d_w = wiener(e, N)
print(f"d = {d_w}")
assert not d_w is None, "Wiener's attack failed (\"d\" not found) :("
m_w = pow(c, d_w, N)
print(f"Flag: {long_to_bytes(m_w)}")
print(f"==========================================")
# Performing Boneh-Durfee's attack
print(f"Performing Boneh-Durfee's attack...")
print(f"Factorized from crypto-attacks:")
p_bd = 126941806460244095377115101056215170200213929484090514615615360791047815508282999312547430020357429932308768712158161906404559758053111268332560036207583087350177765905028171368043071041697143783557751018420251412743117633405829486334952312669390185416378995607092112979722242788438125727258195819223984881293
q_bd = 176171647623796415963359037459080158279832338949959164916683927127298628490481547783271812783698644240568426097637418877451963005025506022174220789400439434207167210194263661330803801184790705595672502832081604208722809411817374316086936064983248582792693864440342630864686435882656704880417413599728301262999
print(f"p = {p_bd}")
print(f"q = {q_bd}")
phi_bd = (p_bd-1)*(q_bd-1)
d_bd = pow(e,-1,phi_bd)
print(f"d = {d_bd}")
assert not d_bd == (None, None), "Boneh-Durfee's attack failed (\"d\" not found) :("
m_bd = pow(c, d_bd, N)
print(f"Flag: {long_to_bytes(m_bd)}")
Testing Wiener's atttack feasibility...
The value "d" must have less than approx. 511 bits
Here, "d" is 512 bits
==========================================
Testing Boneh-Durfee's atttack feasibility...
The value "d" must have less than approx. 598 bits
Here, "d" is 512 bits
==========================================
Performing Wiener's attack...
d = 4405001203086303853525638270840706181413309101774712363141310824943602913458674670435988275467396881342752245170076677567586495166847569659096584522419007
Flag: b'crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5}'
==========================================
Performing Boneh-Durfee's attack...
Factorized from crypto-attacks:
p = 126941806460244095377115101056215170200213929484090514615615360791047815508282999312547430020357429932308768712158161906404559758053111268332560036207583087350177765905028171368043071041697143783557751018420251412743117633405829486334952312669390185416378995607092112979722242788438125727258195819223984881293
q = 176171647623796415963359037459080158279832338949959164916683927127298628490481547783271812783698644240568426097637418877451963005025506022174220789400439434207167210194263661330803801184790705595672502832081604208722809411817374316086936064983248582792693864440342630864686435882656704880417413599728301262999
d = 4405001203086303853525638270840706181413309101774712363141310824943602913458674670435988275467396881342752245170076677567586495166847569659096584522419007
Flag: b'crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5}'
#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long, getPrime
from secret import messages
def RSA_encrypt(message):
m = bytes_to_long(message)
p = getPrime(1024)
q = getPrime(1024)
N = p * q
e = 3
c = pow(m, e, N)
return N, e, c
for m in messages:
N, e, c = RSA_encrypt(m)
print(f"n = {N}")
print(f"e = {e}")
print(f"c = {c}")
from Crypto.Util.number import *
from libnum import solve_crt
from gmpy2 import iroot
import itertools
e = 3
n1 = 14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021
c1 = 6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225
n2 = 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123
c2 = 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172
n3 = 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147
c3 = 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153
n4 = 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961
c4 = 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577
n5 = 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823
c5 = 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805
n6 = 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263
c6 = 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749
n7 = 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897
c7 = 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144
all_cn = [(c1,n1), (c2,n2), (c3,n3), (c4,n4), (c5,n5), (c6,n6), (c7,n7)]
# we hope that at least there's one group of length k where all the ct share the same original message
k = 3
possible_cn_group = list(itertools.combinations(all_cn, k))
for cns in possible_cn_group:
cs = [cn[0] for cn in cns]
ns = [cn[1] for cn in cns]
m3 = solve_crt(cs, ns)
m = iroot(m3, e)
if m[1]:
plain = long_to_bytes(m[0])
print(f"Message obtained: {plain}")
Message obtained: b'yes\n\n---\n\nJohan Hastad\nProfessor in Computer Science in the Theoretical Computer Science\nGroup at the School of Computer Science and Communication at KTH Royal Institute of Technology in Stockholm, Sweden.\n\ncrypto{1f_y0u_d0nt_p4d_y0u_4r3_Vuln3rabl3}'