Challenge: Angry Shamir · CTF: DalCTF 2026 · Category: Crypto · Difficulty: Easy

Reading the room

The flavor text is doing a lot of work here. The S in RSA stands for Adi Shamir (Rivest–Shamir–Adleman). So when the author says Shamir would be angry about what they did to “his algorithm,” we already know two things before we even open the file:

  1. This is an RSA challenge.
  2. The author broke RSA on purpose by misusing it somehow.

Half of crypto CTF is figuring out which mistake was made. Let’s look at what we were given.

1
2
3
4
5
6

Public Key:
n = 1838728184695871659965012189610295270665548277743170978477811033285784122401925676473091945840761097230358112793269159175523352904583082710661432383586054756989336914086267086282261815103722709523091728221623957702900301124878651337623985822069898206814203104595126969177996998431362486639056055349584704987009282334768918035439577276111964948640918939110460050009666129310410354538866707598179087805495281114570426986316731323553476567423888230008826031200982236779868885532826970566394829392616541380902228086261386950569625906913931124943742837569848435973408085296846480875452543065548991901360785409742687475380901
e = 65537

Encrypted Flag:
c = 789545866347439920710445699573254153680505782482756993843356750980220383218945019393920653402758903298961579834860269864723264413119811332414724945575026435841383953497751702639326431362640371689770093794458588005697099946848826383795374803739641872724604053825535708973930008279621031161769534300009342429497648284351686580075106498405528267107474469195434707074304510989598742806146185572482356930204310432254906432917437583495091279111823135243990442691262246628875356373201376815813508297361384609829242597557658901077250276402989705573487361905198470585599080421232703134641467570445229006472956517079740557680862

A standard RSA public key: a modulus n, the very common public exponent e = 65537, and a ciphertext c. Nothing here tells us the bug yet — the secret is hiding inside n.

Step 1 — Size up the modulus

First instinct with any RSA challenge: how big is n?

1
2

n = 1838728184695871659965012189610295270665548277743170978477811033285784122401925676473091945840761097230358112793269159175523352904583082710661432383586054756989336914086267086282261815103722709523091728221623957702900301124878651337623985822069898206814203104595126969177996998431362486639056055349584704987009282334768918035439577276111964948640918939110460050009666129310410354538866707598179087805495281114570426986316731323553476567423888230008826031200982236779868885532826970566394829392616541380902228086261386950569625906913931124943742837569848435973408085296846480875452543065548991901360785409742687475380901
print(n.bit_length())   # 2054

2054 bits. That’s bigger than a standard 2048-bit RSA modulus. On the surface this looks strong — you certainly can’t factor a healthy 2048-bit semiprime in a CTF. But “Shamir would be angry” is a promise that something is wrong, so before reaching for any heavy machinery, we do the cheapest possible check.

Step 2 — Ask FactorDB first, always

FactorDB is a public database of known integer factorizations. For real-world keys it’s useless, but CTF authors love generating keys with structural weaknesses, and those weak n values are very often already sitting in FactorDB. It costs one HTTP request, so it’s always the first move.

1
2
3
4
5
6
7
8

import urllib.request, json

d = json.loads(
    urllib.request.urlopen(f'http://factordb.com/api?query={n}', timeout=20).read().decode()
)
print('status', d['status'])
for f, mult in d['factors']:
    print(mult, 'x', f)

Output:

1
2
3

status FF
1 x 67
1 x 27443704249192114327836002830004407024858929518554790723549418407250509289...

Two things jump out:

  • status: FF means Fully Factored — FactorDB knows the complete factorization.
  • The first factor is 67.

That’s the whole challenge right there.

Step 3 — Realize what just happened

A secure RSA modulus is n = p · q where p and q are two large primes of similar size (e.g. two ~1024-bit primes for a 2048-bit modulus). The security rests entirely on factoring n being infeasible.

Here, instead, the author built:

1

n = 67 × q

where 67 is a tiny prime and q is one enormous (~2048-bit) prime carrying almost the entire bit-length of n. The modulus looks big and healthy, but it is trivially factorable: trial division finds 67 in microseconds. (You don’t even need FactorDB — a for loop over small primes catches it instantly.)

This is the “what I’ve done with his algorithm” that would make Shamir angry: the math of RSA is intact, but the key generation is broken. The strength of RSA is exactly that you cannot find p and q — and here one of them is a two-digit number.

Once you can factor n, RSA falls apart completely, because knowing p and q lets you reconstruct the private key.

Step 4 — Reconstruct the private key and decrypt

With the factorization in hand, decryption is just textbook RSA:

  1. p = 67, q = n / p
  2. Euler’s totient: φ(n) = (p − 1)(q − 1)
  3. Private exponent: d = e⁻¹ mod φ(n)
  4. Plaintext: m = c^d mod n
  5. Convert the integer m back to bytes
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

n = 1838728184695871659965012189610295270665548277743170978477811033285784122401925676473091945840761097230358112793269159175523352904583082710661432383586054756989336914086267086282261815103722709523091728221623957702900301124878651337623985822069898206814203104595126969177996998431362486639056055349584704987009282334768918035439577276111964948640918939110460050009666129310410354538866707598179087805495281114570426986316731323553476567423888230008826031200982236779868885532826970566394829392616541380902228086261386950569625906913931124943742837569848435973408085296846480875452543065548991901360785409742687475380901
e = 65537
c = 789545866347439920710445699573254153680505782482756993843356750980220383218945019393920653402758903298961579834860269864723264413119811332414724945575026435841383953497751702639326431362640371689770093794458588005697099946848826383795374803739641872724604053825535708973930008279621031161769534300009342429497648284351686580075106498405528267107474469195434707074304510989598742806146185572482356930204310432254906432917437583495091279111823135243990442691262246628875356373201376815813508297361384609829242597557658901077250276402989705573487361905198470585599080421232703134641467570445229006472956517079740557680862

p = 67
q = n // p
assert p * q == n          # sanity check: 67 really divides n

phi = (p - 1) * (q - 1)
d   = pow(e, -1, phi)      # modular inverse (Python 3.8+)
m   = pow(c, d, n)

flag = m.to_bytes((m.bit_length() + 7) // 8, 'big')
print(flag.decode())

Output:

1

dalctf{sm4ll_f4ct0rs_4r3_d4ng3r0us_1n_rs4}

Flag

1

dalctf{sm4ll_f4ct0rs_4r3_d4ng3r0us_1n_rs4}

The flag even spells out the moral: small factors are dangerous in RSA.

Takeaways

  • Don’t trust the bit-length. A 2054-bit n looks stronger than 2048-bit RSA, but bit-length means nothing if the prime structure is broken. The security comes from two large, balanced primes — not from a big number.
  • Always hit FactorDB first. It’s a one-line, no-cost check that solves a surprising fraction of CTF RSA challenges outright. Trial division by small primes is an equally cheap second check.
  • RSA is only as strong as your key generation. The encryption/decryption math here is perfectly correct. The single mistake — picking 67 as one of the “primes” — destroys the entire scheme. This is the classic unbalanced / smooth modulus failure mode.
  • Read the flavor text. “Shamir” pointed straight at RSA, and “what I’ve done with his algorithm” told us the algorithm wasn’t broken — the usage was. That framing narrowed the search before a single line of code.

Shamir is, understandably, still angry.