Public Exponent

Salty

We are given this code that implements RSA with e = 1.

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes

e = 1
d = -1

while d == -1:
    p = getPrime(512)
    q = getPrime(512)
    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

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.

from Crypto.Util.number import *

n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485

print(long_to_bytes(ct))

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.

#!/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

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.

Below is the PoC for this challenge.

from Crypto.Util.number import *
from gmpy2 import *

n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957

m = iroot(ct,e)[0]
print(long_to_bytes(m))

Flag: crypto{N33d_m04R_p4dd1ng}

Everything is Big

References

In this challenge, we are given this source code.

#!/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)}')

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.

Here's the mathematical derivation.

e*d ≡ 1 mod phi
e*d = k*phi + 1     --> div. by d*phi
e/phi = k/d + 1/(d*phi)

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

# 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)

solve.py

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)}")

Output of solve.py

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}'

Flag: crypto{s0m3th1ng5_c4n_b3_t00_b1g}

Crossed Wires

We are given this source code.

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}")

Here is the solver code for the challenge.

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))

Flag: crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}

Everything is Still Big

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).

Here is the solution for the challenge.

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}'

Flag: crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5}

Endless Emails

We are given this source code.

#!/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}")

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.

Here's the solution code.

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}'

Flag: crypto{1f_y0u_d0nt_p4d_y0u_4r3_Vuln3rabl3}

PreviousPrimes Part 1 NextPortSwigger

Last updated 28 days ago

#!/usr/bin/env python3 from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes e = 1 d = -1 while d == -1: p = getPrime(512) q = getPrime(512) 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 * 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)}')

# 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}'