Berlian Gabriel

1337UP CTF 2023

Cryptography

1-10

(31 Solves, 464 Points)

In the equation, xs, which is only 64 bits, is much smaller than cs, which is 1000 bits. Since the values of cs are known, LLL lattice reduction can be used to retrieve the values of new xs.

The following operation to generate the new xs basically only replaces the last 3 digits of the original xs with the integers representing the Unicode of the FLAG content (which are also 3 digits). Hence, once we retrieve the new xs using LLL, we can get the flag characters by converting the last 3 digits of each of the new xs values using chr() function.

xs = [ord(f) + i - (i%1000)  for i, f in zip(xs, search("{(.*)}", FLAG).group(1))]

Below is the solver using the LLL technique:

from sage.all import Matrix

cs = [8508903290440008966939565321248693758153261635170177499193552423579929500027826696702216711413627480472568726828904707392607240309148374882044455682656477650413559779578913981575195542381602155806438946382809049847521263107908111429547314575039079118614485792613461747911710760754291582134293099750060, 10234293217173095983648586990138462404689872504690765936890158736280331352728086141006820545673419953576281340699793983414878095413526583845311613647542879798224462254801103246845064675391113534349390649562211376117941776588135441368773636568930887968431002105334751994385414474789708434897717472259757, 6001064586644974650131784742218587067958465984737568290249286706923485137083921908971767187010824715217158349948368322929900720010489749231105336650564421771867089333709608235963711368415685056362117910529113580811922176651335662802405504434103542105450330213217418470901029864459362153866361049469621, 5859510800336462649673113647904370677448984650623412649303149431740483580968255760095323745895405406649271411277663981671465673293279417168147656423009231087547991428322779036740050269460373254323377738756038706795196225547099530503996157675637620918729310987613041873955654973230573780794437230183289, 8212120161226957435594246142362544687871307206030517377713172267061914524817671684448986080347503212333314134144272096534190656954277299391948626024244379808998220515649968150824587976113971840005858079163744362874678111323034234960076591622752217194796532407435861854992608669653483268713825154541681, 4292538496747452556903766205458518557016170261915268175117554973221631407580344459540989898488936014316805799620957521118332103032738032797936315597220903773140347787977387271254963436603728977128756213671653297994336981775219965231686927050793105808729293803455246360077380768093287937551667515822737, 8583458084429417950887051233123781099671792568724013361916924355046040863544385972858215904752358387759143712618915109914726815547284050405347634520790328222420443989299783668017365846692013464579110450651166600940834254189911732107856656458621485902792541383514622551498513045029193930072821693821256, 927938350277846540058170699346614173130036388369329189433895716040551556863284640834396837739290832786836335265440745786025530973467859153202044442045287145528583412999497854136387626360287750242048999254798532603013016406637079389023297629455299864761196574249382738851682248453939600976884575974199, 4606866838328488359534883828872534448488908284003992208192170511899852596906485417934690617926601159129473558885893097400239110669875450476234618534668886892219546199419412794765402627731086862572263105282498567494065303352715044800789544479262215220148659740517187562922289802434925672447697743660640, 5696622808956926263797513675882969816326582766528835713485415099018508834817057303528828064039948371652175876967703746446602159940653502950606513683435185458750394450192106019388424601807240033502531431423705043713657847236861816929000927218441444067742560786753091009546483807078198791541719979069795]
s = 605466527953516222016485516214431809590993588699320208021845670703468281059947406248463347211427615855012720451029976981068579151311047123161756448068506197424807516350675172131826275005312472029312861168498961728971558322943730466676859739724928104907194812943584226111451426124864722285484117269190235012612078303171378
m = [
    [cs[0], 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [cs[1], 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [cs[2], 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [cs[3], 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [cs[4], 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [cs[5], 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [cs[6], 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [cs[7], 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [cs[8], 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [cs[9], 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [-s,    0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]

solution = Matrix(m).LLL()[0]

flag=""
for i in solution:
    flag+=chr(i%1000)
print(flag)

INTIGRITI{3a8a32c7f6}

Not So Smooth

(49 Solves, 408 Points)

The given python code resembles a Diffie-Hellman Key Change, but with unusual mechanism for public integer and shared secret generation. The flaw in that mechanism was that, without the secret integer a or b, the shared secret can be calculated. Knowing only either pow(u,a,p) and B or pow(u,b,p) and A will be enough to calculate the shared secret in this case.

To solve this, we will perform 2 steps: 1. Recover pow(u,a,p) from the equation used to generate A 2. Use the recovered pow(u,a,p) value to calculate the key (shared_secret) and then XOR it with enc to get flag

Step 1: Finding pow(u,a,p)

# Given Value
p = 97201997431130462639713476119411091922677381239967611061717766639853376871260165905989218335681560177626304205941143288128749532327607316527719299945637260643711897738116821179208534292854942631428531228316344113303402450588666012800739695018334321748049518585617428717505851025279186520225325765864212731597
u = 14011530787746260724685809284106528245188320623672333581950055679051366424425259006994945665868546765648275822501035229606171697373122374288934559593175958252416643298136731105775907857798815936190074350794406666922357841091849449562922724459876362600203284195621546769313749721476449207319566681142955460891977927184371401451946649848065952527323468939007868874410618846898618148752279316070498097254384228565132693552949206926391461108714034141321700284318834819732949544823937032615318011463993204345644038210938407875147446570896826729265366024224612406740371824999201173579640264979086368843819069035017648357042
v = 16560637729264127314502582188855146263038095275553321912067588804088156431664370603746929023264744622682435376065011098909463163865218610904571775751705336266271206718700427773757241393847274601309127403955317959981271158685681135990095066557078560050980575698278958401980987514566688310172721963092100285717921465575782434632190913355536291988686994429739581469633462010143996998589435537178075521590880467628369030177392034117774853431604525531066071844562073814187461299329339694285509725214674761990940902460186665127466202741989052293452290042871514149972640901432877318075354158973805495004367245286709191395753
w = 30714296289538837760400431621661767909419746909959905820574067592409316977551664652203146506867115455464665524418603262821119202980897986798059489126166547078057148348119365709992892615014626003313040730934533283339617856938614948620116906770806796378275546490794161777851252745862081462799572448648587153412425374338967601487603800379070501278705056791472269999767679535887678042527423534392867454254712641029797659150392148648565421400107500607994226410206105774620083214215531253544274444448346065590895353139670885420838370607181375842930315910289979440845957719622069769102831263579510660283634808483329218819353
A = 7393401480034113709683683682039780458211722756040975666277858366986963864147091724359492764726999692812421940595309756560491142512219957986281425163574890752574157617546760386852366936945888357800966704941013951530688031419816817272581287237223765833452303447283089906937413964658335387593899889933721262202

# A = (w * pow(u, a, p) + v * (1 - pow(u, a, p)) * pow(1 - u, -1 , p)) % p
# From the equation above, we can solve for pow(u,a,p), which will be denoted as uap
# rearranged the equation to extract uap 
uap = (((1 - u) * A * pow(v, -1, p) - 1) * pow(w * (1 - u) * pow(v, -1, p) - 1, -1, p)) % p

print(uap)

Step 2: Calculating key

from Crypto.Util.number import long_to_bytes
from Crypto.Util.strxor import strxor

# Given values
p = 97201997431130462639713476119411091922677381239967611061717766639853376871260165905989218335681560177626304205941143288128749532327607316527719299945637260643711897738116821179208534292854942631428531228316344113303402450588666012800739695018334321748049518585617428717505851025279186520225325765864212731597
u = 14011530787746260724685809284106528245188320623672333581950055679051366424425259006994945665868546765648275822501035229606171697373122374288934559593175958252416643298136731105775907857798815936190074350794406666922357841091849449562922724459876362600203284195621546769313749721476449207319566681142955460891977927184371401451946649848065952527323468939007868874410618846898618148752279316070498097254384228565132693552949206926391461108714034141321700284318834819732949544823937032615318011463993204345644038210938407875147446570896826729265366024224612406740371824999201173579640264979086368843819069035017648357042
v = 16560637729264127314502582188855146263038095275553321912067588804088156431664370603746929023264744622682435376065011098909463163865218610904571775751705336266271206718700427773757241393847274601309127403955317959981271158685681135990095066557078560050980575698278958401980987514566688310172721963092100285717921465575782434632190913355536291988686994429739581469633462010143996998589435537178075521590880467628369030177392034117774853431604525531066071844562073814187461299329339694285509725214674761990940902460186665127466202741989052293452290042871514149972640901432877318075354158973805495004367245286709191395753
B = 6919381992041136573008188094979879971060160509085428532054694712745921654244468113796582501225839242977870949915769181804595896718922228206397860738237256125972615830799470450058633231003927061049289907097099916321068776956652172887225970642896455423957706532253349472544176183473470843719479781727784095989
enc = b'\xcfW\x85\x8d\xedU\xdd\xd9`\x16f\xb8j(\xeb9-\x1b\xb8\x18 0av\xe5\xabK\xc6'

# Calculated value from earlier
uap = 5800980130514258729493356556586783550353646717888270388491933914063108065007903832238070114788244453263394724831189244416895679045112824281971233965519258692178030960290284529331750854542713233479046433081108283523744593200782176684631158126353686866717059523327810880424579407438436788499136872937463068642

# key = (pow(u,a,p)*B + v*(1-pow(u,a,p))*pow(1-u, -1, p)) % p
# After substition of pow(u,a,p) with uap:
key = (uap*B + v*(1-uap)*pow(1-u, -1, p)) % p

FLAG = strxor(enc, long_to_bytes(key)[:len(enc)])
print(FLAG.decode())

INTIGRITI{1e863724be1ea6d3e}

Really Secure Apparently

(201 Solves, 100 Points)

A very big e indicates that d might be small. We can use Wiener attack from this script below: https://gist.github.com/mananpal1997/73d07cdc91d58b4eb5c818aaab2d38bd

from continued_fractions import *
from Crypto.Util.number import *

n = 689061037339483636851744871564868379980061151991904073814057216873412583484720768694905841053416938972235588548525570270575285633894975913717130070544407480547826227398039831409929129742007101671851757453656032161443946817685708282221883187089692065998793742064551244403369599965441075497085384181772038720949

e = 98161001623245946455371459972270637048947096740867123960987426843075734419854169415217693040603943985614577854750928453684840929755254248201161248375350238628917413291201125030514500977409961838501076015838508082749034318410808298025858181711613372870289482890074072555265382600388541381732534018133370862587

with open('ciphertext', 'rb') as file:
    c=bytes_to_long(file.read())

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

def mod_inv(a, m):
    g, x, _ = egcd(a, m)
    return (x + m) % m

def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x
  
def crack_rsa(e, n):
    frac = rational_to_contfrac(e, n)
    convergents = convergents_from_contfrac(frac)
    
    for (k, d) in convergents:
        if k != 0 and (e * d - 1) % k == 0:
            phi = (e * d - 1) // k
            s = n - phi + 1
            # check if x*x - s*x + n = 0 has integer roots
            D = s * s - 4 * n
            if D >= 0:
                sq = isqrt(D)
                if sq * sq == D and (s + sq) % 2 == 0: return d

d = crack_rsa(e, n)
print(d)
m = pow(c, d, n)
print(long_to_bytes(m))

INTIGRITI{0r_n07_50_53cur3_m4yb3}

Keyless

(282 Solves, 100 Points)

We only need to reverse the mathematical operation performed by the encrypt function, step-by-step as shown below:

def decrypt(encrypted_message):
    decrypted_message = ""
    for char in encrypted_message:
        encrypted_char = ord(char)
        c = encrypted_char ^ 23
        b = (c + 7)//3
        a = (b - 5) ^ 42
        decrypted_char = chr((a - 10)//2)
        decrypted_message += decrypted_char
    return decrypted_message


with open("flag.txt.enc", "r", encoding="utf-8") as file:
    encrypted_message = file.read()

print(decrypt(encrypted_message))

INTIGRITI{m4yb3_4_k3y_w0uld_b3_b3773r_4f73r_4ll}