Modular arithmetic and number theory toolkit
Modular inverse, Chinese remainder theorem, Tonelli-Shanks square roots, Jacobi symbols, and integer nth roots - arbitrary precision, in the browser.
Open in ctfpalThese are the primitives every crypto attack is assembled from. Having them at hand in arbitrary precision, without opening a Python REPL and importing sympy, is the difference between testing an idea in ten seconds and testing it in five minutes.
They are also the vocabulary the attacks are described in. A writeup that says 'recover the plaintext with CRT and an exact cube root' is only actionable if those two operations are one click away; otherwise the writeup is a research project. Keeping the primitives adjacent to the attacks is the difference between reading about a technique and running it.
What each one is for
- Modular inverse (extended Euclidean) - recovering
dfromeandphi, undoing multiplication in any modular attack. - Chinese remainder theorem - combining results from several moduli, the core of Hastad’s attack and of RSA-CRT decryption.
- Tonelli-Shanks - square roots mod a prime. Needed to recover a point’s y-coordinate on an elliptic curve, and to invert squaring-based challenges (Rabin cryptosystem).
- Jacobi symbol - deciding whether a value is a quadratic residue without computing the root. Some oracle challenges leak exactly this one bit.
- Integer nth root - exact, not floating point. Essential for the
e = 3cube-root case, where a floating-point root loses the low digits and silently gives the wrong answer.
Related tools
RSA decryption and attack runner
Paste n, e, and c and let ctfpal choose the attack: trial division, Fermat, Pollard’s rho, Wiener, common modulus, or Hastad broadcast. Arbitrary-precision, in-browser.
Discrete logarithm solver
Solve discrete logs with baby-step giant-step, Pollard’s rho, and Pohlig-Hellman - the last of which breaks any group with smooth order.
Hastad broadcast attack on RSA
Recover a message sent to several recipients under a small public exponent, using the Chinese remainder theorem and an exact integer root.
RSA common modulus attack
Recover a plaintext encrypted twice under the same modulus with two coprime exponents, using the extended Euclidean algorithm. No factoring needed.