Skip to content

Latest commit

 

History

History
121 lines (82 loc) · 4.88 KB

README.md

File metadata and controls

121 lines (82 loc) · 4.88 KB
Raw

Rasa

Whispers linger in an ancient, forgotten cemetery. Can you unearth the secrets buried within?

Iran

Write Up

This challenge has two parts. In the first part, you need to recover the missing public modulus n. Using c1 and c2, we know that:

c1 = m1**3 - k1*n
c2 = m2**3 - k2*n

k1*n = m1**3 - c1
k2*n = m2**3 - c2

n = gcd(m1**3 - c1, m2**3 - c2)

With m1, m2, c1, and c2, you can compute the value of n.

In the second part, you’ll compute the original message m (the flag). According to Bézout’s identity, if e1 and e2 are coprime, there exist integers u and v such that:

u*e1 + v*e2 = gcd(e1,e2) = 1
u*e1 + v*e2 = 1

Using this, you can compute the value of m.

Iran

Here’s the solution:

from Crypto.Util.number import long_to_bytes as l2b , bytes_to_long as b2l
from math import gcd

e1 = 0x10001
e2 = 0x8001

us = [1,0]
vs = [0,1]

u = 0
v = 0

def extended_euclidean_recursive(a, b):

    global step, us, vs
    global u, v

    if b == 0:

        u = us[0]
        v = vs[0]
        return

    quotient = a // b
    remainder = a % b

    new_dividend = b
    new_divisor  = remainder

    tmp = us[1]
    us[1] = -us[1] * quotient + us[0]
    us[0] = tmp

    tmp = vs[1]
    vs[1] = -vs[1] * quotient + vs[0]
    vs[0] = tmp

    extended_euclidean_recursive(new_dividend, new_divisor)


c1 = 7312232205725560918880635536477561563951105942080784583040587732025728955663761404141906466221803771241668226254445656842206509903880625470305551817791640567760095065379834317180527151002023243675848728144303517895034048801077630636276546659167180061810278337245790748041953964192950787190836087748761931018375268317415139223189221542933459175340282543201681373068022886003290692335622261911762123167145358330265077996739972057142751836312368259067345307680444138477903610756442684528699968540254286788504345842549018335185238498662875849503931195860267772402077415052691570766208027832117791457633247747050720778096
c2 = 4092768064829185003307135737122669216755416218607991698109265641935614529306605255898505138176859359220806966201405995657572565475171810905152589121847952677794344395292411470904470260597928163119680207928756763951530331068088666763877360420171426795234005220505273344167840995874147140127115534612357467873112350745191774587068676759926236129214375726182944178434555170366619928070843534666768549296978895027241870592939675634034541843374711671665979119238503693662733638195734015169586040944530436317231147472324251026131186160941399104235762327005429356354696574055948757201862537779063308851808098877194874199701
c3 = 10371129253188241257343365750470748858010759457463048273187957947779606966670261493945185032235126612008448703202456009452020623091338068435890304213722409378189641115510453335750597975188152347561884648348403561730905354112438207774249277862191492813430462437443155587533420599836513842126043573819406455130271848081074191175596787888891927050490304745183577684795820082562879515297325944648118396318530778619267518200739706199009043996904012199783271989318080960200267780009862547056688931727453799749036935904194053642920459935229135634206799206581491013644089149894937309217794060778156232936990908433989692160360
c4 = 7301979747720982742150854900767204173406764967694236306364706368553656835097628663111387544851382251523079381015125455707573819747974963039605091956771707345453912652512500041140199957446928228859572617858491935877122994348471955816146884104857086441646325771038792936805595471654179273071479984850102110340158207988155965525668901407876998622393053958083710054433705738038371694225321070751981748938494206529512266110484264516600095421669184158049996436595671645812130644861548029409362811899766013632628711857145691713787243935475362084185357475170126065397054842575276706340945103085240864576087839146421769190729

m1 = b2l(b'There were a mysterious underground cemetery found in Tabriz about 10 years ago near Blue Mosque while worker were digging in nearby locations')
m2 = b2l(b'It is a unknown cemetery which no historical records have registered it so far and it still remains a mystery for everyone. Can you help recover the secrets behind it?')

n = gcd(m1**3 - c1, m2**3 - c2)
print(f"Recovered Modulus n : {n}")

extended_euclidean_recursive(e1, e2)
print(f"[+] u,v of a({e1}) , b({e2}) is {u} , {v}")

m = pow(c3, u, n) * pow(c4, v, n) % n
flag = l2b(m)
print(flag)

Flag

uctf{TABRIZ_myst3r1ous_c3meterY_near_Blue_Mosque}

Categories

Check the categories which the challenge belongs to.

  • Web
  • Reverse
  • PWN
  • Misc
  • Forensics
  • Cryptography
  • Blockchain
  • Steganography
  • AI
  • Data Science

Points

Warm up This Challenge Evil
25 400 500