◄ WORLD V · SONNY 5DART 116 · a helldive at the net

RABIN CRYPTO breaking it is exactly factoring

Encrypt a message by squaring it mod n = pq. Decrypting means taking a square root mod n — which needs the factors p and q. Its beauty is a proof: recovering the plaintext is provably as hard as factoring n, a guarantee RSA (dart 050) only conjectures. Its quirk: every ciphertext has four square roots, so you must add redundancy to know which is the message.

THE TECHNIQUE square to encrypt, root to decrypt

Public key n = pq. Encrypt: c = m² mod n. Decrypt (with p, q): take the square root of c mod p and mod q (easy when p, q ≡ 3 mod 4), then combine by the Chinese Remainder Theorem — giving four candidate roots, of which one is m. Below: encrypt a message and see all four roots on decrypt. live demo

HISTORY & CREDIT the first provably-hard-as-factoring scheme

“RSA is proven as hard as factoring” — RSA Rabin is; RSA only conjectures it. That proof is Rabin’s whole point. cited

1978 · the squaring trapdoor first appears in Rabin’s “Digitalized Signatures” (in Foundations of Secure Computation; “Digitalized,” often mis-spelled “Digitized”).
1979 · Michael O. Rabin — MIT/LCS/TR-212, “Digitalized Signatures and Public Key Functions as Intractable as Factorization” — the cryptosystem with the reduction proof: an algorithm that decrypts can be turned into one that factors n.
the four roots · mod a product of two primes, every quadratic residue has four square roots — so decryption is ambiguous without redundancy (a header, a hash) in the message.
the sharp edge · that same proof makes Rabin vulnerable to a chosen-ciphertext attack: a decryption oracle that returns a different root than you sent lets gcd factor n — the proof cuts both ways.

Provable security and a built-in ambiguity, from one line: c = m² mod n. Rabin 1979

RECOMMEND FOR I-13 square, root mod p and q, CRT

Encryption is one modular square; decryption is two roots plus CRT — all the RSA machinery, reused:

$ i13 run rabin.i13 # p=7 q=11 n=77, m=20 c = 20^2 mod 77 = 15 four roots {13, 20, 57, 64}, each squares to 15
Recommend: nothing new — encryption c = m² mod n is one step of the bignum modexp (darts 032/035/050, exponent 2); decryption is two modexps (the p ≡ 3 mod 4 root shortcut) plus a CRT recombine (dart 047). The four candidate roots come out cleanly (verified {13, 20, 57, 64} all square to 15 mod 77). It ties RSA (050) on primitives.
Note: a real modulus wants a 2048-bit prime — bignum (dart 050’s addition), which the corpus has; the toy case runs in f64.