Unencryptable

cryptohack

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.