Tyco

The brief

🫠🤖

• tyco.zip, 690 bytes

In short

The flag was encrypted twice under one RSA key, once as r and once as r + d, and d was printed with the results. Both ciphertexts give polynomials with the same root, and their greatest common divisor hands that root back without factoring N.

One flag, encrypted twice

The description was two emoji. The script encrypts the flag r under a 511 bit RSA key with e = 56,263, then encrypts r + d under the same key and prints d next to both results.

The distance between them was public

Textbook RSA has no padding, so the two plaintexts keep their exact relation. With d known, the second message is the first one shifted by a known amount, and that is all the Franklin-Reiter attack needs.

Two polynomials, one shared root

Modulo N, x^e minus t1 and (x + d)^e minus t2 are both zero at x = r. So both contain the factor x minus r, and a common factor survives in their greatest common divisor.

From degree 56,263 down to 1

Both polynomials have degree 56,263. The lab took their gcd modulo N without ever factoring N, and in about 17 seconds it came back linear, Ax + B.

The root is the flag

The root is r = minus B over A modulo N, a 223 bit number. It encrypts back to t1 exactly, r + d encrypts back to t2, and its 28 bytes spell the flag.

The insight

RSA without padding keeps the relation between two messages. Encrypt r and r + d under one key, print d, and a polynomial gcd hands back r.

The flag

hiCTF{your_ai_slop_bores_me}