UIUCTF 2025 featured four crypto challenges of easy difficulty, from a short Diophantine equation solver to more complex algebraic systems. All challenges provided source code and required mathematical insight combined with efficient implementation.

Challenge 1: The Shortest Crypto Challenge

The first challenge presents a Diophantine equation with AES encryption:

from Crypto.Cipher import AES
from hashlib import md5
from secret import a,b,c,d, FLAG

assert a**4 + b**4 == c**4 + d**4 + 17 and max(a,b,c,d) < 2e4 and AES.new( f"{a*b*c*d}".zfill(16).encode() , AES.MODE_ECB).encrypt(FLAG).hex() == "41593455378fed8c3bd344827a193bde7ec2044a3f7a3ca6fb77448e9de55155"

We need to find four integers a, b, c, d such that a^4 + b^4 = c^4 + d^4 + 17 with all values under 20,000.

Solution Approach

The key insight is to precompute all possible sums of fourth powers and store them in a hash table. For each sum, we check if there exists another sum that differs by exactly 17. This reduces the problem from O(n^4) to O(n^2).

The assignment suggests, that all factors are <20000, but in reality, they are <2000, so we have to brute force a way smaller space, making this approach 10x faster.

A programming language like Nim is better suited for this task than something like python, as numbers are stored more efficiently, and all of them are smaller than 20k^2*2 = 800_000_000, so int64 is sufficient.

import nimcrypto, nimcrypto/utils, std/strutils, std/tables

const upperBound = 2000
const targetHex = "41593455378fed8c3bd344827a193bde7ec2044a3f7a3ca6fb77448e9de55155"

var sums = initTable[int, seq[tuple[a, b: int]]]()

for a in 1..upperBound:
  for b in a..upperBound:
    let key = (a * a * a * a) + (b * b * b * b)
    if not sums.hasKey(key):
      sums[key] = @[]
    sums[key].add((a: a, b: b))

for sum_cd, pairs_cd in sums:
  if sums.hasKey(sum_cd + 17):
    for (a, b) in sums[sum_cd + 17]:
      for (c, d) in pairs_cd:
        let aesKey = align($(a.uint64 * b.uint64 * c.uint64 * d.uint64), 16, '0')
        if aesKey.len != 16: continue

        var ctx: ECB[aes128]
        var cipherText: array[targetHex.len div 2, byte]
        hexToBytes(targetHex, cipherText)

        var plainText: array[cipherText.len, byte]
        var keyAsArray: array[aes128.sizeKey, byte]
        copyMem(keyAsArray.addr, aesKey.cstring, aesKey.len)

        ctx.init(keyAsArray)
        ctx.decrypt(cipherText, plainText)
        ctx.clear()

        var flag = newString(plainText.len)
        copyMem(flag.cstring, plainText.addr, plainText.len)

        echo flag

The algorithm finds exactly one solution where the product a*b*c*d serves as the AES key to decrypt the flag.

Flag: uiuctf{D1oPh4nTine__Destr0yer__}

Challenge 2: Too Many Primes

This challenge modifies RSA by using multiple consecutive primes instead of just two:

from sympy import nextprime, randprime
from sympy.core.random import seed
from math import prod, gcd
from Crypto.Util.number import bytes_to_long
# from secret import phi_N, FLAG

p = randprime(2**127, 2**128)
N = 1
while N < 2**2048:
	N *= p
	p = nextprime(p)

assert gcd(phi_N, 65537) == 1

pt = bytes_to_long(FLAG)
ct = pow(pt, 65537, N)
print("N = ", N)
print("ct = ", ct)

The modulus N is the product of K consecutive primes starting from a random 128-bit prime, continuing until N exceeds 2^2048. This results in approximately 15-17 prime factors.

Solution Approach

Since N ≈ 2^2048 and each prime is around 2^128, we need roughly 16 consecutive primes (turned out: 17, via running the script with 15, 16, 17). We can binary search for the starting prime and test if the product of consecutive primes matches N:

import math
from sympy import nextprime
from Crypto.Util.number import bytes_to_long, long_to_bytes

N = 34546497157207880069779144631831207265231460152307441189118439470134817451040294541962595051467936974790601780839436065863454184794926578999811185968827621504669046850175311261350438632559611677118618395111752688984295293397503841637367784035822653287838715174342087466343269494566788538464938933299114092019991832564114273938460700654437085781899023664719672163757553413657400329448277666114244272477880443449956274432819386599220473627937756892769036756739782458027074917177880632030971535617166334834428052274726261358463237730801653954955468059535321422372540832976374412080012294606011959366354423175476529937084540290714443009720519542526593306377
ct = 32130352215164271133656346574994403191937804418876038099987899285740425918388836116548661879290345302496993945260385667068119439335225069147290926613613587179935141225832632053477195949276266017803704033127818390923119631817988517430076207710598936487746774260037498876812355794218544860496013734298330171440331211616461602762715807324092281416443801588831683678783343566735253424635251726943301306358608040892601269751843002396424155187122218294625157913902839943220894690617817051114073999655942113004066418001260441287880247349603218620539692362737971711719433735307458772641705989685797383263412327068222383880346012169152962953918108171850055943194
e = 65537
num_factors = 17

# Step 1: Factor N
low = 2**127
high = 2**128
primes = []
while low <= high:
    mid = (low + high) // 2
    p_candidate = nextprime(mid)
    temp_primes = [p_candidate]
    p_curr = p_candidate
    for _ in range(num_factors - 1):
        p_curr = nextprime(p_curr)
        temp_primes.append(p_curr)
    test_N = math.prod(temp_primes)
    if test_N == N:
        primes = temp_primes
        break
    elif test_N < N:
        low = mid + 1
    else:
        high = mid - 1

if not primes:
    print("Factoring failed.")
else:
    # Step 2: Decrypt ct
    phi_N = math.prod(p - 1 for p in primes)
    d = pow(e, -1, phi_N)
    print(long_to_bytes(pow(ct, d, N)))

The binary search efficiently finds the starting prime, after which we can compute φ(N) and decrypt normally.

Flag: uiuctf{D0nt_U5e_Cons3cUt1vE_PriMeS}

Challenge 3: Back to Roots

This challenge leaks the decimal part of a square root and challenges us to recover the original number:

from random import randint
from decimal import Decimal, getcontext
from hashlib import md5

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

from secret import FLAG

K = randint(10**10, 10**11)
print('K', K)
leak = int( str( Decimal(K).sqrt() ).split('.')[-1] )

print(f"leak = {leak}")
ct = AES.new(
	md5(f"{K}".encode()).digest(),
	AES.MODE_ECB
).encrypt(pad(FLAG, 16))

print(f"ct = {ct.hex()}")

Given output:

leak = 4336282047950153046404
ct = 7863c63a4bb2c782eb67f32928a1deceaee0259d096b192976615fba644558b2ef62e48740f7f28da587846a81697745

Solution Approach

The brute force approach would take approximately 0.5 hours on 380 cores. However, there’s a more elegant mathematical solution.

The key insight is that when (i + k)^2 is computed, numbers whose fractional parts are very close to 0 or 1 correspond to values near perfect squares. We can exploit this property:

import numpy as np
from hashlib import md5

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import unpad

k = 0.4336282047950153046404
a = (np.array(range(10**6), dtype=np.float128) + k) ** 2
a = a - a.astype(int)

for candidate in [np.argmin(a), np.argmax(a)]:
    candidate = round((candidate+k)**2)
    CT = long_to_bytes(0x7863c63a4bb2c782eb67f32928a1deceaee0259d096b192976615fba644558b2ef62e48740f7f28da587846a81697745)
    key_hash = md5(f"{candidate}".encode()).digest()
    try:
        print(unpad(AES.new(key_hash, AES.MODE_ECB).decrypt(CT), AES.block_size).decode())
    except:
        pass

The mathematical reasoning is that (i+k)^2 = i^2 + k^2 + 2*i*k, and the fractional part (modulo 1) must be very close to 1.0 or 0.0, with the i term canceling out in the analysis.

Flag: uiuctf{SQu4Re_Ro0T5_AR3nT_R4nD0M}

Challenge 4: Symmetric

The final challenge involves four 512-bit primes with symmetric polynomial hints:

from Crypto.Util.number import *
from secret import FLAG

p, q, r, s = [getPrime(512) for _ in "1234"]

print(f"h1 = {p + q + r + s}")
print(f"h2 = {p**2 + q**2 + r**2 + s**2}")
print(f"h3 = {p**3 + q**3 + r**3 + s**3}")

N = p*q*r*s
print(f"N = {N}")
pt = bytes_to_long(FLAG)
ct = pow(pt, 65537, N)
print(f"ct = {ct}")

We’re given the power sums h₁, h₂, h₃ (sum, sum of squares, sum of cubes) of four primes, along with their product N.

Solution Approach

This is a classical problem involving symmetric polynomials. We can use Newton’s identities to convert power sums to elementary symmetric polynomials, then solve the resulting quartic equation:

import sage.all as sage
from Crypto.Util.number import long_to_bytes

h1 = 44626154099651354925697068610752642661842459492769931945027538340211738148995902544351457443643808803963130274930824732652561687395268828472477422919262224
h2 = 516671113554555861164166966331322883848052630063409185414998284127910160310316421085219788291486248715029393774584960034375836715001130337767354512063372620828300201147366138270597133744747341658011663632381219284289144790858167258162656417236910634201286428763727072739569460623482985066956478781223378673732
h3 = 6147718474663450187001867904227777991349731066494841442199681943204194617136760567222545181562592364728655444222576167723225771866335920325045525027985716792468801076590684892140052786942251780392395274059384743594570343510311801194684613435002073956759521242578078411431891501758484581445964234548107005826532945720412531638919892681259687552977883437895032963223761216846303917338652743754915155934118353066174102436448393348040719582422022713292561416343278608
N = 14184841414933523698606245433393907034474143715949896731683874356940146602876788990832087413915033843120975580859113356518777762025417525571528638829956003882418585702756644491932279294535883798799580861254646149745925137179207140600356428758736111639677698862407787386573263961111978517446397007747429416079059195916290615125084899002162504424765939524455434579218079962808920072946861658695379491917567048202142417165204141307476222251547098848515065051745905180788313450494477967398727631152936238366581978379130450660235139256967936160718128731512409111209840405772933034600016694225294481603355934917366484109057
ct = 720607330561370237459911161481490697044029472780348552630924063963226757984368356580217337982783395620115957442082471977614781910209933696251479615689667675958354681196823652299435457532944189300223816303315625302472302494905575910600277892375951366031061219173465155686586206246661009612156094695841741309002508535764511343569015518587247600796520847856011377777228749182958947015029731456117404560626347774985507275302882865400315045173501559082431672490227728580592379740508214726249635835834752208899970446910850569489282065524329936561486377823093465841715608716032843259935185417766702677708267102415636848129

e2 = (h1*h1 - h2) // 2
e3 = (h3 - h2*h1 + h1*e2) // 3

x = sage.var('x')
roots = sage.solve(x**4 - h1*x**3 + e2*x**2 - e3*x + N == 0, x)

p, q, r, s = [int(root.rhs()) for root in roots]

pt = pow(ct, pow(65537, -1, (p-1)*(q-1)*(r-1)*(s-1)), N)
print(f"Flag: {long_to_bytes(pt).decode()}")

The solution uses Newton’s identities to compute:

  • e₁ = h₁ (sum of roots)
  • e₂ = (h₁² - h₂)/2 (sum of products of pairs)
  • e₃ = (h₃ - h₂h₁ + h₁e₂)/3 (sum of products of triples)
  • e₄ = N (product of all roots)

This gives us the quartic equation x⁴ - e₁x³ + e₂x² - e₃x + e₄ = 0 whose roots are the four primes.

Flag: uiuctf{5yMmeTRiC_P0lyS_FoRM_A_B4S15}