Published on

BlueHensCTF 2023 - RSA School 3rd Grade

Authors

RSA School 3rd Grade

Table of Contents

  1. Source
  2. Solution

Source

Third_Grade.py file content :

from Crypto.Util.number import *
p=getPrime(512)
q=getPrime(512)
n=p*q
e1=71
e2=101
msg=bytes_to_long(b'UDCTF{REDACTED}')
c1 = pow(msg, e1, n)
c2 = pow(msg, e2, n)
print(n)
print(e1)
print(e2)
print(c1)
print(c2)

output.txt file content :

87587426608653108851564813489752475287019321764561555461700901651463446024854423042554629096780987943450742890279417241231211446818009232077230407281610183609540264821974669679932743621434901779832901512681108061652309435608446510337833028029876549629818957952682516026313018526405972829923620377438164377109
71
101
1421275848974615267320815554113040672023972283807752574007971561416386636110464890632994733734995114229161525885389065244354678964389211537085513310823751266472044865745324866096898051759507738772227296453397678055024824805366251635154522059070310922367078281343183508274450904681187384450253350434931649011
26097095086985946477598349002260598942399303275420948828501512467473619292573670218058274201990116295246084096584962695127706609264424951086000719935218496250047555039460733768633688410770610612614744411304261153778159881980276162174277085197608466835857196307432992312260307797540746411319330318058866868362

Solution 

import gmpy2
from Crypto.Util.number import long_to_bytes

# Given values
n = 87587426608653108851564813489752475287019321764561555461700901651463446024854423042554629096780987943450742890279417241231211446818009232077230407281610183609540264821974669679932743621434901779832901512681108061652309435608446510337833028029876549629818957952682516026313018526405972829923620377438164377109
e1 = 71
e2 = 101
c1 = 1421275848974615267320815554113040672023972283807752574007971561416386636110464890632994733734995114229161525885389065244354678964389211537085513310823751266472044865745324866096898051759507738772227296453397678055024824805366251635154522059070310922367078281343183508274450904681187384450253350434931649011
c2 = 26097095086985946477598349002260598942399303275420948828501512467473619292573670218058274201990116295246084096584962695127706609264424951086000719935218496250047555039460733768633688410770610612614744411304261153778159881980276162174277085197608466835857196307432992312260307797540746411319330318058866868362


def extended_euclidean(a, b):
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_euclidean(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

# Find Bézout coefficients using gmpy2
gcd, u, v = gmpy2.gcdext(e1, e2)


# If v is negative, adjust it and c2
if v < 0:
    v = -v
    c2 = gmpy2.invert(c2, n)

# Compute the message
M = gmpy2.powmod(c1, u, n) * gmpy2.powmod(c2, v, n) % n
print(long_to_bytes(M))

Flag : UDCTF{3uc1id_th4_60at}