RSA RSA RSA

I had something so important to say that I just had to tell three of my friends!

Here’s the provided txt file:

1
e: 3
2
n1: 96137714481560340073780038250015316564930752333880363375193088083653975552334517899735106334409092229494004991796910602440032630762575914714152238916128674595912438177270978040111855327624812652948702562503276973409716595778936978757384935820012322432156169815110042972411989274515686945691887468406312791931
3
ct1: 45640508926729498938915879450220374487095109122207451961200230820161694723491945276893630019713859109920025191680053056485030809079137883906737197875968862878423820820515399840094772412319820062860149582361429346029277273870654355752499436360499181221418835401103925420623212341317366954144592892392013649421
4
n2: 90990790933807553440094447797505116528289571569256574363585309090304380702927241663491819956599368816997683603352289726407304960362149545383683196526764288524742203975596414405902155486632888712453606841629050125783639571606440840246928825545860143096340538904060826483178577619093666337611264852255012241011
5
ct2: 58149644956871439128498229750735120049939213159976216414725780828349070974351356297226894029560865402164610877553706310307735037479690463594397903663323983980128060190648604447657636452565715178438939334318494616246072096228912870579093620604596752844583453865894005036516299903524382604570097012992290786402
6
n3: 86223965871064436340735834556059627182534224217231808576284808010466364412704836149817574186647031512768701943310184993378236691990480428328117673064942878770269493388776005967773324771885109757090215809598845563135795831857972778498394289917587876390109949975194987996902591291672194435711308385660176310561
7
ct3: 16168828246411344105159374934034075195568461748685081608380235707338908077276221477034184557590734407998991183114724523494790646697027318500705309235429037934125253625837179003478944984233647083364969403257234704649027075136139224424896295334075272153594459752240304700899700185954651799042218888117178057955

So we’re given a publix exponent, 3 n’s, and 3 ct’s. This is a classic example of Hastad’s broadcast attack. This site does a great job of explaining it.

We can very easily search up a script for this to decrypt the flag:

1
e = 3
2
n1 = 96137714481560340073780038250015316564930752333880363375193088083653975552334517899735106334409092229494004991796910602440032630762575914714152238916128674595912438177270978040111855327624812652948702562503276973409716595778936978757384935820012322432156169815110042972411989274515686945691887468406312791931
3
ct1 = 45640508926729498938915879450220374487095109122207451961200230820161694723491945276893630019713859109920025191680053056485030809079137883906737197875968862878423820820515399840094772412319820062860149582361429346029277273870654355752499436360499181221418835401103925420623212341317366954144592892392013649421
4
n2 = 90990790933807553440094447797505116528289571569256574363585309090304380702927241663491819956599368816997683603352289726407304960362149545383683196526764288524742203975596414405902155486632888712453606841629050125783639571606440840246928825545860143096340538904060826483178577619093666337611264852255012241011
5
ct2 = 58149644956871439128498229750735120049939213159976216414725780828349070974351356297226894029560865402164610877553706310307735037479690463594397903663323983980128060190648604447657636452565715178438939334318494616246072096228912870579093620604596752844583453865894005036516299903524382604570097012992290786402
6
n3 = 86223965871064436340735834556059627182534224217231808576284808010466364412704836149817574186647031512768701943310184993378236691990480428328117673064942878770269493388776005967773324771885109757090215809598845563135795831857972778498394289917587876390109949975194987996902591291672194435711308385660176310561
7
ct3 = 16168828246411344105159374934034075195568461748685081608380235707338908077276221477034184557590734407998991183114724523494790646697027318500705309235429037934125253625837179003478944984233647083364969403257234704649027075136139224424896295334075272153594459752240304700899700185954651799042218888117178057955
8

9
import gmpy2
10
gmpy2.get_context().precision = 4096
11

12
from binascii import unhexlify
13
from functools import reduce
14
from gmpy2 import root
15

16
# Håstad's Broadcast Attack
17
# https://id0-rsa.pub/problem/11/
18

19
# Resources
20
# https://en.wikipedia.org/wiki/Coppersmith%27s_Attack
21
# https://github.com/sigh/Python-Math/blob/master/ntheory.py
22

23
EXPONENT = 3
24

25
CIPHERTEXT_1 = "ciphertext.1"
26
CIPHERTEXT_2 = "ciphertext.2"
27
CIPHERTEXT_3 = "ciphertext.3"
28

29
MODULUS_1 = "modulus.1"
30
MODULUS_2 = "modulus.2"
31
MODULUS_3 = "modulus.3"
32

33

34
def chinese_remainder_theorem(items):
35
    # Determine N, the product of all n_i
36
    N = 1
37
    for a, n in items:
38
        N *= n
39

40
    # Find the solution (mod N)
41
    result = 0
42
    for a, n in items:
43
        m = N // n
44
        r, s, d = extended_gcd(n, m)
45
        if d != 1:
46
            raise "Input not pairwise co-prime"
47
        result += a * s * m
48

49
    # Make sure we return the canonical solution.
50
    return result % N
51

52

53
def extended_gcd(a, b):
54
    x, y = 0, 1
55
    lastx, lasty = 1, 0
56

57
    while b:
58
        a, (q, b) = b, divmod(a, b)
59
        x, lastx = lastx - q * x, x
60
        y, lasty = lasty - q * y, y
61

62
    return (lastx, lasty, a)
63

64

65
def mul_inv(a, b):
66
    b0 = b
67
    x0, x1 = 0, 1
68
    if b == 1:
69
        return 1
70
    while a > 1:
71
        q = a // b
72
        a, b = b, a % b
73
        x0, x1 = x1 - q * x0, x0
74
    if x1 < 0:
75
        x1 += b0
76
    return x1
77

78
if __name__ == '__main__':
79
    ciphertexts = [ct1, ct2, ct3]
80
    modulus = [n1, n2, n3]
81

82
    C = chinese_remainder_theorem([(ct1, n1), (ct2, n2), (ct3, n3)])
83
    M = int(root(C, 3))
84

85
    M = hex(M)[2:]
86
    print(unhexlify(M).decode('utf-8'))

1
squ1rrel{math_is_too_powerful_1q3y41t1s98u23rf8}