Unencryptable

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-22 | Status: Solved Techniques: iterated_squaring_gcd, recover_private_key, rsa_fixed_point_factoring

Summary

Task: RSA where a known DATA blob is an 'unencryptable' fixed point: pow(DATA,e,N)==DATA, with only N,e,c published and primes unknown. Solution: DATA^(e-1)≡1 mod N, so iteratively square DATA (x=DATA, then x=x^2 mod N) and test gcd(x-1, N); at some intermediate exponent 2^k the value is 1 mod one prime but not the other, so gcd yields a nontrivial factor (k=6 here). Factor N, compute d=inverse(e,phi), decrypt c.

Unencryptable — cryptohack (Mathematics)

Description

"I swear I knew what I was doing, but I encrypted some data on my hard drive and nothing happened? RSA is so confusing. Luckily my flag is safe..."

Files: source.py, output.txt. The generator prints RSA broken!? whenever m == m^e mod N (an "unencryptable" message), and ships a DATA blob that triggers exactly that:

 python read-only • copy allowed Copy
DATA = bytes.fromhex("372f0e88...e2921")   # m with pow(m, e, N) == m
N = 0x7fe8cafec5...56b41                    # primes unknown
e = 0x10001
c = 0x5233da71...d677b                       # the encrypted flag

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

DATA is a fixed point of RSA (an unconcealed message): DATA^e ≡ DATA (mod N). Dividing out DATA (it is a unit) gives:

DATA^(e-1) ≡ 1 (mod N),   e - 1 = 65536 = 2^16

So the multiplicative order of DATA divides 2^16. By CRT, DATA has some 2-power order mod p and another mod q. As we iteratively square DATA, at some step 2^k it becomes ≡ 1 modulo one prime while still ≢ 1 modulo the other. At that moment:

gcd(DATA^(2^k) - 1, N)

is a nontrivial factor of N. (Equivalently, an intermediate square root of 1 mod N that is ≠ ±1 splits N.) ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

gcd(DATA - 1, N) and gcd(DATA^(e-1) - 1, N) give the trivial answers, so loop over k.

Solution

 python read-only • copy allowed Copy
from Crypto.Util.number import long_to_bytes, inverse, GCD

DATA = int("372f0e88f6f7189da7c06ed49e87e0664b988ecbee583586dfd1c6af99bf20345ae7442012c6807b3493d8936f5b48e553f614754deb3da6230fa1e16a8d5953a94c886699fc2bf409556264d5dced76a1780a90fd22f3701fdbcb183ddab4046affdc4dc6379090f79f4cd50673b24d0b08458cdbe509d60a4ad88a7b4e2921", 16)
N = 0x7fe8cafec59886e9318830f33747cafd200588406e7c42741859e15994ab62410438991ab5d9fc94f386219e3c27d6ffc73754f791e7b2c565611f8fe5054dd132b8c4f3eadcf1180cd8f2a3cc756b06996f2d5b67c390adcba9d444697b13d12b2badfc3c7d5459df16a047ca25f4d18570cd6fa727aed46394576cfdb56b41
e = 0x10001
c = 0x5233da71cc1dc1c5f21039f51eb51c80657e1af217d563aa25a8104a4e84a42379040ecdfdd5afa191156ccb40b6f188f4ad96c58922428c4c0bc17fd5384456853e139afde40c3f95988879629297f48d0efa6b335716a4c24bfee36f714d34a4e810a9689e93a0af8502528844ae578100b0188a2790518c695c095c9d677b
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

x = DATA
for k in range(20):
    g = GCD(x - 1, N)
    if 1 < g < N:                 # found a factor (k = 6)
        p, q = g, N // g
        d = inverse(e, (p-1)*(q-1))
        print(long_to_bytes(pow(c, d, N)))
        break
    x = pow(x, 2, N)              # square -> climb the 2-power order

Output:

b'crypto{REDACTED}'

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍