Cryptography

Name	Solves
Cube Cute 🥉	51
Cube Cute 2 🥇	34
Terix 🥉	34
Primer Puasa 🥈	32
Es Coco Prime 🥇	30
Motor CB-XR	22

Cube Cute

Description

Author: WanZKey

Easy chall to count?, yap, just focus on counting!. maybe yes, number three will help you!, don't forget the bit!!!.

Initial Analysis

We are given 2 files:

chall.py

import os
from Crypto.Util.number import getPrime, bytes_to_long

m = bytes_to_long(os.getenv("FLAG").encode())
p = getPrime(512)
n = p * p * p
e = 65537
c = pow(m, e, n)

print(f"{n,c=}")

output.txt

n = 630898657746765099122267528399725208189145247063682480924052168875604652609906980974582055383403839197154487585764970168295427913822134040973976165185049867109163706600223414592995357912884480125931297182733092986951525729943417082503377207750215095866659544261732457343170292593849656732143202362036798588858712097255250807514111870212119582395370012616879339177777597009269762479875901203517374464318585932616520746594131938550191763226024716780709090409632501
c = 566743658504610440666264570638634074273227110512101941192700827572262701380197987965724054202703078978793507864216820035950605301514782676829822525720770360686370257756515710853079962416300618585428543316192254417606542328610233935356522610247094462983431467069120612826495791771825504581081875258763019103278418007670583009168669348938222110660323577629493389539178804812907782381802089745317531681334924267970208266019479367907744408789540835482489133197924000

We can see the obvious vulnerability that $n = p^3$ then we can compute the p as \ p=\sqrt[3]{n} \. Then do basic RSA decryption.

Exploitation

I don't really think i can provide much explanation, because this is just textbook RSA, you probably can understand more reading this:

RSA cryptosystemWikipedia

We compute p, then compute Euler's Totient function, for $n = p^3$ the totient function becomes:

$$\phi(n) = p^2 \cdot (p-1)$$

Then we compute the private exponent (d) using this formula:

$$d \equiv e^{-1} \pmod{\phi(n)}$$

Then compute m:

$$m \equiv c^d \pmod{n}$$

solve.py

import gmpy2
from Crypto.Util.number import long_to_bytes, inverse

n = 630898657746765099122267528399725208189145247063682480924052168875604652609906980974582055383403839197154487585764970168295427913822134040973976165185049867109163706600223414592995357912884480125931297182733092986951525729943417082503377207750215095866659544261732457343170292593849656732143202362036798588858712097255250807514111870212119582395370012616879339177777597009269762479875901203517374464318585932616520746594131938550191763226024716780709090409632501
c = 566743658504610440666264570638634074273227110512101941192700827572262701380197987965724054202703078978793507864216820035950605301514782676829822525720770360686370257756515710853079962416300618585428543316192254417606542328610233935356522610247094462983431467069120612826495791771825504581081875258763019103278418007670583009168669348938222110660323577629493389539178804812907782381802089745317531681334924267970208266019479367907744408789540835482489133197924000
e = 65537ss

p, exact = gmpy2.iroot(n, 3)
phi = p**2 * (p - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

Running this script, we will get the flag:

Flag: RAMADAN{Lag1-Pu4s4_b3laj4r_Cub3-r0ot-C4lcul4t0r}

Cube Cute 2

Description

Author: WanZKey

same as the first, let's find out cube?

Initial Analysis

We are given two files:

chall.py

from Crypto.Util.number import *

flag = bytes_to_long(b"RAMADAN{testing}")
p, q = getPrime(1024), getPrime(1024)
pq = p * q
e = 3

c = pow(flag, e , pq)
print(f"{pq = }")
print(f"{c = }")

output.txt

pq = 26000605037389889835529373527414149345778186575709110927201735471687673869264136219843439315614934332155728720101968433812820341103842252122627723289850866241885368400162593166173815491133592822855620884190139469927294489286843206759263087095479306646820759925848164679542974970091466326535605556293250490322520487894638131357413236812564861295140993989897638275132361014368147995608298540572383974600377978150244239563856488134351329107448373354362303860067111549843588605595550249782950536009575914300918450372162775336484569179582841162916465019934049014320884279072097268226511747143249633860983113936103507505329
c = 759211273067433922963992034647885450662599416410705236429702408831148036835632595433847526546086813688570833808701975275299315436273155331214589388492267065915098739346525711455459119067892378083728620671330218258058824348856056826606451364057343700567134214801268864646738807454787259131276200506407505591472923510179106734251099762314168615280906595352809311538803600914921661888591173138706021

Well this is basically the same as this challenge. The vulnerability lies in the e value. When the e value is very small, in this case 3. It is vulnerable to small exponent attack.

Exploitation

In textbook RSA, ciphertext is calculated as this formula:

$$c \equiv m^e \ (mod\ n)$$

But when the e is too small, or the n is very big (In this case it both is). The c value essentially becomes:

$$c \equiv m^e$$

Which can then be computed as:

$$m \equiv \sqrt[e]{c}$$

Rendering the n value useless.

solve.py

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot

c = 759211273067433922963992034647885450662599416410705236429702408831148036835632595433847526546086813688570833808701975275299315436273155331214589388492267065915098739346525711455459119067892378083728620671330218258058824348856056826606451364057343700567134214801268864646738807454787259131276200506407505591472923510179106734251099762314168615280906595352809311538803600914921661888591173138706021
e = 3

m, exact = iroot(c, e)
print(long_to_bytes(m))

Flag: RAMADAN{Cube_2_root_just_c0nv3rt_l0ng_1nt3g3r_t0_byt3s}

Primer Puasa

Author: WanZKey

Gatau mau ngisi deskripsinya apa, intinya next!, 128!.

Initial Analysis

We are given two files:

chall.py

import os
from Crypto.Util.number import bytes_to_long, getRandomNBitInteger, isPrime, getPrime

def nextPrime(n):
    while not isPrime(n := n + 1):
        continue
    return n

def gen():
    attempts = 0
    max_attempts = 1000
    while attempts < max_attempts:
        q = getPrime(128)
        r = getRandomNBitInteger(128)
        p = q * nextPrime(r) + nextPrime(q) * r
        if p.bit_length() <= 256 and isPrime(p) and isPrime(q):
            return p, q, r
        attempts += 1

    raise ValueError("Failed to generate primes within attempts")

flag = b"TCP1P{testing}"
m = bytes_to_long(flag)
p, q, r = gen()
n = p * q
phi = (p - 1) * (q - 1)
e = 0x10001
d = pow(e, -1, phi)
c = pow(m, e, n)
print(f"{n=}")
print(f"{e=}")
print(f"{c=}")
print(f"{r=}")

output.txt

n=18307564183336174372957570419285112053386287578636115613810768749885553622091399241390778725602944089106231437595887
e=65537
c=14461562873315648876900863314412430050179928115118140218391238322269424888840823494182924552959513459002994495040816
r=272617646727976431124665621907966000454

TL;DR of the key generation is:

1. Get a 128-bit prime number and assign it as q.

2. Get a 128-bit number and assign it as r.

3. Then compute p so that:

$$p = nextPrime(r)\ + nextPrime(q)\ \cdot\ r$$

Exploitation

This challenge is the same as this challenge. So during the CTF, i just copied the solve script and got the flag :v . If you want an explanation maybe check out the writeup — I am not really good at Cryptography :(

solve.py

from Crypto.Util.number import long_to_bytes, inverse, isPrime
import math

n=18307564183336174372957570419285112053386287578636115613810768749885553622091399241390778725602944089106231437595887
e=65537
c=14461562873315648876900863314412430050179928115118140218391238322269424888840823494182924552959513459002994495040816
r=272617646727976431124665621907966000454

def nextPrime(n):
    while not isPrime(n):
        n += 1
    return n

r_next = nextPrime(r)
print(f"nextPrime(r)={r_next}")

# p * q = n
# p = q * r_next + (q + k) * r

# n = q ** 2 * r_next + q * (q + k) * r
#   = q ** 2 * (r_next + r) + q * (k * r)

# P(x) = x ** 2 * (r_next + r) + x * (k * r) - n
# P(q) = 0 (for some small k)

# q = (-(k * r) ± √((k * r) ** 2 + 4 * (r_next + r) * n)) / (2 * (r_next + r))
# But q > 0 , it's a getRandomNBitInteger(256) 

k = 1
while True:
    q = (- (k * r) + math.isqrt((k * r) ** 2 + 4 * (r_next + r) * n)) // (2 * (r_next + r))
    if n % q == 0 and q > 1:
        break
    k = k + 1


print(f"q={q}")
p = n // q
print(f"p={p}")

phi = (p - 1) * (q - 1)
e = 0x10001
d = inverse(e, phi)
m = pow(c, d, n)
print(bytes.fromhex(hex(m)[2:]))

Running this script, we will get the flag:

Flag: RAMADAN{Puas4-g4s_Crypt0-C0y_bi4r_Pr1me!!!}

Terix

Description

Author: WanZKey

Bulan Puasa ini cuacanya terix banget ya ges, pen minum rasanya:)

Initial Analysis

We are given a file:

output.txt

# Apa nih? pasti tau la ya!, gas solpken bang.

[
    [82, 65, 77, 65], 
    [68, 65, 78, 123], 
    [69, 52, 115, 121], 
    [45, 99, 104, 52], 
    [108, 108, 95, 77], 
    [52, 116, 114, 49], 
    [120, 33, 125, 33]
]

Exploitation (?)

This is just the flag, encoded to decimal value, to solve this, we can flatten the array to 1D array and decode it:

import numpy as np

a = [
    [82, 65, 77, 65], 
    [68, 65, 78, 123], 
    [69, 52, 115, 121], 
    [45, 99, 104, 52], 
    [108, 108, 95, 77], 
    [52, 116, 114, 49], 
    [120, 33, 125, 33]
]

a = np.array(a)
flattened = a.flatten()
print(''.join([chr(i) for i in flattened]))

Flag: RAMADAN{E4sy-ch4ll_M4tr1x!}

Es Coco Prime

Description

Author: WanZKey

Please verify first whether it is "coco" or not? If yes, maybe the "coco" seller, "Mr. Euclidean" will help you pour it, and yes, always remember the simple mathematics of "x" and "y" because they are the minimum formula for this "coco" which is very delicious.

Initial Analysis

We are given two files:

chall.py

from Crypto.Util.number import *
import random
from datetime import datetime

flag = bytes_to_long(b"RAMADAN{testing}")

def generatepub():
        a, b = 0, 0
        while GCD(a,b) != 1:
                random.seed(int(datetime.now().timestamp()))
                a = random.randint(128, 65536)
                b = random.randint(128, 65536)
        return a, b

p, q = getPrime(1024), getPrime(1024)
pq = p * q

a, b = generatepub()

msg1 = pow(flag, a, pq)
msg2 = pow(flag, b, pq)

print(f"{pq = }")
print(f"{a = }")
print(f"{b = }")
print(f"{msg1 = }")
print(f"{msg2 = }")

output.txt

pq = 8936396806210526376141535339320387823150632232768025074585150591450030342206739518984596873580048532158059431947151704989934421112343371270553045654957003707832178597263987770629732733312586314686634975339561970271092488597023151433664491322133177095608320300299786978779169268542548863459526287208102109014561040941363941559454093027421535766246401867857307704897740625661125317008732659703903812825923671450283119589909627550816583337750263847443638256518882885826501709869226134948243652941257691269039832456963313242820268668152500562964805729573667818693090015710068568308108426351178618148559207653302567726453
a = 32061
b = 25772
msg1 = 7695596237478159522452087218845013527373478230607104177524270309024459526033335750001151727866555570291892743979750985120897025450462055592528248478274362020113749559145555853098093830111817392492813273992088466078651780421143270914464677221287963762908081568342838834538516994647149568818015125152403393987410632675950398066466919926902308259336076973660543304070430193620256482213620575763644889245568141571033647659434287956659556787958083570354879801789295843963231617273422097444166050659303762035064451157393402922329616442321648473714835432708240321316535631852601475690117298226463949192488540950263855042907
msg2 = 8726827715731958059539441667281144076307125863408191935133153896621344848666078224840971961017467059048081311754984352770649072429357806259980769502126194401035117039555235808191275684416100769313649444316736944064888595183348029100504658610051446845811200104635286154291344738727317791921960633499241096213543147633334898592946532632215854688749781744916767484573725857756576525177360420560009768973850301523326349630709430357510669786471900807220296373417053854263624880781501015930954863096318711799739788646820945229128120530409860911356841163797303328058004651862646657441084726421343809574301546431146458406010

We can see that the flag is encrypted 2 times, msg1 and msg2. Each encrypted with a different e value but the same n value. This RSA scheme is vulnerable to common modulus attack.

Let:

$$msg_1 = m^{a} mod\ n\\ and \\ msg_2 = m^{b}\ mod\ n$$

Since $gcd(a,b)=1$ , knowing Bézout’s Identity and Extended Euclidean Algorithm, we get an identity like this:

$$a \cdot x + b \cdot y = 1 \\ Using\ Extended\ Euclidean\ Algorithm,\ we\ found\ x\ and\ y\\ m = {msg_1}{^x} \cdot {msg_2}{^y}\ mod\ n$$

If the recovered x or y is negative, we must compute for example:

msg1_inv = inverse(msg1, n) then msg1_inv^{-x}

Exploitation

I already explained it above how the maths work, so here's the solve script:

solve.py

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

def xgcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        g, x, y = xgcd(b, a % b)
        return g, y, x - (a // b) * y

def attack(n, e1, c1, e2, c2):
    g, u, v = xgcd(e1, e2)
    if g != 1:
        raise ValueError("e1 and e2 must be coprime")

    if u < 0:
        c1 = inverse(c1, n)
        u = -u
    if v < 0:
        c2 = inverse(c2, n)
        v = -v

    p1 = pow(c1, u, n)
    p2 = pow(c2, v, n)
    m = (p1 * p2) % n
    return long_to_bytes(gmpy2.iroot(m, g)[0])


def main():
    pq = 8936396806210526376141535339320387823150632232768025074585150591450030342206739518984596873580048532158059431947151704989934421112343371270553045654957003707832178597263987770629732733312586314686634975339561970271092488597023151433664491322133177095608320300299786978779169268542548863459526287208102109014561040941363941559454093027421535766246401867857307704897740625661125317008732659703903812825923671450283119589909627550816583337750263847443638256518882885826501709869226134948243652941257691269039832456963313242820268668152500562964805729573667818693090015710068568308108426351178618148559207653302567726453
    a = 32061
    b = 25772
    msg1 = 7695596237478159522452087218845013527373478230607104177524270309024459526033335750001151727866555570291892743979750985120897025450462055592528248478274362020113749559145555853098093830111817392492813273992088466078651780421143270914464677221287963762908081568342838834538516994647149568818015125152403393987410632675950398066466919926902308259336076973660543304070430193620256482213620575763644889245568141571033647659434287956659556787958083570354879801789295843963231617273422097444166050659303762035064451157393402922329616442321648473714835432708240321316535631852601475690117298226463949192488540950263855042907
    msg2 = 8726827715731958059539441667281144076307125863408191935133153896621344848666078224840971961017467059048081311754984352770649072429357806259980769502126194401035117039555235808191275684416100769313649444316736944064888595183348029100504658610051446845811200104635286154291344738727317791921960633499241096213543147633334898592946532632215854688749781744916767484573725857756576525177360420560009768973850301523326349630709430357510669786471900807220296373417053854263624880781501015930954863096318711799739788646820945229128120530409860911356841163797303328058004651862646657441084726421343809574301546431146458406010
    flag = attack(pq, a, msg1, b, msg2)
    print(flag.decode())

if __name__ == "__main__":
    main()s

Running this script and we will get the flag:

Flag: RAMADAN{bel4jar_common_modulus_attack_m4ke_coprime_coy!!!_very_easy_ga_sii?}

Motor CB-XR

Description

Author: WanZKey

Base64 and Base32 codes are very familiar, right? I don't know, but both of their numbers will help you get this "Motor CB-XR". Calculation is key, but a little analysis will help. Well whatever it is, congratulations if you get this "CB-XR Motorcycle"!.

Initial Analysis

We are given two files:

chall.py

import os
import struct

FLAG = os.getenv("FLAG", "RAMADAN{testing}").encode()
assert FLAG.startswith(b"RAMADAN{") and FLAG.endswith(b"}")

KEY_SIZE = 8
KEY = os.urandom(KEY_SIZE)

p64 = lambda x: struct.pack('<Q', x)
u64 = lambda x: struct.unpack('<Q', x)[0]

def encrypt(plaintext, key):
    padlen = KEY_SIZE - (len(plaintext) % KEY_SIZE)
    plaintext += bytes([padlen] * padlen)

    iv = os.urandom(KEY_SIZE)
    ciphertext = iv
    for i in range(0, len(plaintext), KEY_SIZE):
        p_block = plaintext[i:i+KEY_SIZE]
        c_block = p64(u64(iv) ^ u64(p_block) ^ u64(key))
        ciphertext += c_block
        iv = c_block

    return ciphertext

def decrypt(ciphertext, key):
    iv, ciphertext = ciphertext[:KEY_SIZE], ciphertext[KEY_SIZE:]

    plaintext = b''
    for i in range(0, len(ciphertext), KEY_SIZE):
        c_block = ciphertext[i:i+KEY_SIZE]
        p_block = p64(u64(iv) ^ u64(c_block) ^ u64(key))
        plaintext += p_block
        iv = c_block

    return plaintext.rstrip(plaintext[-1:])

if __name__ == '__main__':
    FLAG = FLAG.ljust(8 * 12, b'A')  
    ENC_FLAG = encrypt(FLAG, KEY)
    print("Nih Bang!, pecahin yak:", ENC_FLAG.hex())
    assert decrypt(ENC_FLAG, KEY) == FLAG

output.txt

Nih Bang!, pecahin yak: a6d869161e868078527902778bb36050aca976082df6ba6b550a126ba3ec244fac93043e2dffb968551d1169a3e7244880cd593433d2cb5a676c3e55a3e7244880cd593433d2cb5a676c3e55a3e7244880cd593433d2cb5a676c3e55a3e7244880cd593433d2cb5a2e25771ceaae6d01

We are given a custom cipher. The cipher works like this:

1. Generate a random key with 8 bytes size

2. Taking the plaintext, pad it to multiple of 8 bytes

3. Generate a random 8 bytes IV

4. Encrypt the plaintext, for the first 8 bytes, the encryption process is $c_1 = IV \oplus\ p_1 \oplus\ Key$ then for the subsequent remaining blocks, it encrypts using $c_i = c_{i-1} \oplus\ p_i\ \oplus\ Key$

Exploitation

So to decrypt it, we need to recover the key first, since we know the IV, the first 8 byte of plaintext and and the first 8 bytes of plaintext, to recover the key, we will use this formula:

$$Key = c_1 \oplus IV \oplus p_1$$

Then once we have the key, we can use the decrypt function on the chall.py file:

solve.py

from Crypto.Util.strxor import strxor
from pwn import p64, u64

ct = bytes.fromhex("a6d869161e868078527902778bb36050aca976082df6ba6b550a126ba3ec244fac93043e2dffb968551d1169a3e7244880cd593433d2cb5a676c3e55a3e7244880cd593433d2cb5a676c3e55a3e7244880cd593433d2cb5a676c3e55a3e7244880cd593433d2cb5a2e25771ceaae6d01")

IV = ct[:8]
blocks = [ct[i:i+8] for i in range(8, len(ct), 8)]
p1 = b"RAMADAN{"
key = strxor(strxor(IV, blocks[0]), p1)
print(key)

KEY_SIZE = 8

def decrypt(ciphertext, key):
    iv, ciphertext = ciphertext[:KEY_SIZE], ciphertext[KEY_SIZE:]

    plaintext = b''
    for i in range(0, len(ciphertext), KEY_SIZE):
        c_block = ciphertext[i:i+KEY_SIZE]
        p_block = p64(u64(iv) ^ u64(c_block) ^ u64(key))
        plaintext += p_block
        iv = c_block

    return plaintext.rstrip(plaintext[-1:])

print(decrypt(ct, key))

Running this script, we will get the flag:

Flag: RAMADAN{X0R_w1th_CBC_n0w_y0u_g3t_n3w_l3ss0n}