IEEE — EGCERT — CTF Crypto Writeups

5 min readSep 27, 2022

Hi, I’m Gonna Discuss The Crypto Challenges, Given To Participants in the IEEEv1 CTF at Mansoura University, Organized By the IEEE Mansoura Student Branch, With the Help Of EG-CERT.

Challenges Written By Y4mm1, You Can Find More Details In His Blog Here

Rotten ( 100 points )

A Chinese veteran encoded this so no one could read it.

given Chinese characters In an output.txt file

籛 籭粃籶籶粃 籼籿粃籲 籷籵籲籿 粃粂籵籯籰 籰籼类籱 粃籭籿籱籵籷籿 粁类籴籼籿籲 类籶 籵籲粀籿籲 籰籵 籿籶粁籲籫籴籰 粃籸籸 籵籾 籷籫 籯籴粁籵籷类籶籽 籷籿籱籱粃籽籿籱 籱籿粁籯籲籿籸籫簷 籐籼籿 籾籸粃籽 类籱籃 粁籼簺籶簼籱簼籨籲簹籀籨粁簺籴籼簼籲籨籁簹簹簹

So, With The Challenge Name We Recognize That it is a Rot Cipher, So let's Decrypt It With CyberChef, By Trying All Possible ROTs, We Finally Got The English Words, With ROT8000.

But It’s Wierd, Something Like It also ROT again, But Let’s Paste That Text In One Of The Cipher Identifiers.

We Got That This Cipher Is Atbash Cipher, CyberChef Also Help Us To Get The Flag

EGCERT{ch1n3s3_r07_c1ph3r_8000}

Powers ( 250 Point )

Powers are everywhere.
Hint: Modualr roots are everywhere !

After Some Delegations With The Author Of Challenges Y4mm1, We Solved The Challenge, a Challenge With Few lines of Code But it’s Ninja.

#!/usr/bin/env python3

from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime
from secret import FLAG, BITS

m = bytes_to_long(FLAG)
p, q, r = getPrime(BITS), getPrime(BITS), getPrime(BITS)
n = p * q * r
e = 0x10001

with open('output.bin', 'wb') as h:
    c = pow(m,e*18,n)
    h.write(long_to_bytes(c))

print(n) # n=1954619295407385391500055750434960972919277486798624600020577469183964093523742461044801

as figured, we have a Multiprime RSA, The Problem Here, Is The Message Has a Power Of e*18, So We Need To Decrypt The Message Twice, One For the e and One For The 18th Power,

So we Need To Reverse The e at First, given N we Can Factorize It, and Got The Primes p, q, and r, Factordb Cannot Help us, So We Moved Forward To Alpertron, pasting The N, Pressing The Factor Button, and wait….

Finally, we got The 3 Primes.

p = 95594214675659352345212230367
q = 133016078534567930684443633433
r = 153718603998366488291151543991

Currently, we Can Get The Phi(n)

phi = (p-1)*(q-1)*(r-1)

So, Now It’s Easy For Us To Get The Inverse Of e with That Equation

d = pow(e, -1, phi)

So By Powering The d to The c Value We Have, d Will Cancel The Exponent e, and it will result in The Second Equation.

So We Ended Up With The exponent e, let’s face The Second Problem.

I Was Going Through a Wrong Way Until Y4mm1 Helped Me,

and Tell Me “It’s Too Small Value“, I Was Like.

So After a While of Recognizing These Words, We Find Out That We Need To Get the 18th Modular Root, On N, Trying, But It Takes a Long Time Without any Result, So It Will Be Hard and Wasting Time.

So, Using Sagemath, And The 3 Primes We Have We Got The Modular Root For Our Flag, This Is The Sage script

p = FiniteField(95594214675659352345212230367)
q = FiniteField(133016078534567930684443633433)
r = FiniteField(153718603998366488291151543991)
c_after_e_inverse = 292051111143287906497930558112646692583131330503402508266176662739719049962760084557092
roots_on_p = p(c_after_e_inverse).nth_root(18, all=True)
roots_on_q = q(c_after_e_inverse).nth_root(18, all=True)
roots_on_r = r(c_after_e_inverse).nth_root(18, all=True)

This Script Result in These Numbers.

roots_on_p = [76109110095654167827432297148, 19485104580005184517779933219]
roots_on_q = [4432785956670063381886642097, 128583292577897867302556991336]
roots_on_r = [
     130020534460189462571622451548,
     97250983998614535502552038640,
     139903724044919156191850731766,
     57087094620958932008702004374,
     63418577223741089396486343554,
     36211743418272659542716088103,
     80785164159135957728231096817,
     119886197223493042185085848905,
     50026623371719991642016900328,
     23698069538177025719529092443,
     56467619999751952788599505351,
     13814879953447332099300812225,
     96631509377407556282449539617,
     90300026774625398894665200437,
     117506860580093828748435455888,
     72933439839230530562920447174,
     33832406774873446106065695086,
     103691980626646496649134643663]

Reconstructing nth_root Equations, We Got This Form

for every x, y, z which is a Single Root for every prime, Seems Like it’s a Chinese Reminder Theorm Scheme

But We Have Multiple Values For Every Prime, We Need To Test All Of Them, and The Flag Will Result in One Of These Combinations

for i in roots_on_p:
    for j in roots_on_q:
        for k in roots_on_r:
            m = crt([p, q, r], [i, j, k])[0]
            flag = long_to_bytes(m)
            print(f"{flag=}")

Finally, We Got The Flag

EGCERT{R00t5_0f_R5A_Mult1pl3_pr1m3$}

Real ( 250 Point )

Imagine that you’re not a real person.

We Got Only a Challenge File

#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long, getPrime, getRandomInteger
from secret import FLAG

a, b = getRandomInteger(29), getRandomInteger(29)
p = getPrime(64)
A = a + b*1J

parts = []
for i, j in zip(range(0,len(FLAG),2), range(0,len(FLAG)//2)):
    x = bytes_to_long(FLAG[i:i+2])
    if j % 2 == 0:
        enc = x*int(A.imag) % p
    else:
        enc = x*int(A.real) % p
    parts.append(enc)

print(A**2) # (2070967379364096, 1965986935604360)
print(parts) # [252436673555, 983312194379, 299991842788, 1801149750856, 416837213705, 766219518981, 180114669702, 838621810513, 201892403592, 750916826449, 293045742044, 766105319783, 402176386315, 982113102800, 398774505008, 1581601792701, 438515310904, 1761237131155]
print(p) # 13621462712021260087

Challenge, Generate Two Primes and Use Them as Parameters For Complex number A, then Loop around The flag, Taking Two Bytes and Do Some Operations On Them.

if index is even it will multiply bytes by the imaginary part of A
if odd it will multiply by real part

Then Append The Encrypted Part To The List of Parts

Solution

For Given Parts We Need To Get The Real Value and Imaginary Value,

So We Need To Figure Out The Even Indexes, and Observer Which Number Is The Common Factor Among Them, Then We get The Imaginary part.

Also, We Repeat This Step For The Odd Indexes, To Get The Real Part.

After That, We Can Divide Every value into Parts by the Corresponding Value — Real or Imaginary —, So We Wrote This Script For It.


from Crypto.Util.number import long_to_bytes, GCD

parts=[252436673555, 983312194379, 299991842788, 1801149750856, 416837213705, 766219518981, 180114669702, 838621810513, 201892403592, 750916826449, 293045742044, 766105319783, 402176386315, 982113102800, 398774505008, 1581601792701, 438515310904, 1761237131155]
p = 13621462712021260087

imag = GCD(parts[0], parts[2])
real = GCD(parts[1], parts[3])
flag = []

for index, part in enumerate(parts):
    if index % 2 == 0:
        enc = part // imag
    else:
        enc = part // real
    flag.append(long_to_bytes(enc))

print("Flag: {}".format("".join([c.decode() for c in flag])))

Finally, We Got The Flag

EGCERT{8re4k1n9_7h3_Pl4in_C0mpl3xXx}

IEEE — EGCERT — CTF Crypto Writeups

Written by Mohamed Gamal