Schmidt–Samoa

A guided worksheet for the Schmidt–Samoa cryptosystem. Paste the numbers in, and it explains what each one is, checks it fits, and does the big-number math, from factoring to decryption. Nothing leaves this page; your work is saved in this browser only.

How Schmidt–Samoa works two minutes, with tiny numbers

Katja Schmidt-Samoa's system looks a lot like RSA, with one twist: the public key is a prime squared times another prime, and that same number is used as the exponent. So the whole public key is one number.

Making the keys

  1. Pick two secret primes p and q (neither may divide the other minus 1).
  2. Publish N = p2 × q. That's the entire public key.
  3. Privately work out d = N−1 mod lcm(p − 1, q − 1), the inverse of N modulo the least common multiple.

Locking and unlocking

  1. Encrypt a message m smaller than p × q: c = mN mod N.
  2. Decrypt: m = cd mod (p × q). Note the modulus here is p × q, not N.

Why it's safe, and why a puzzle isn't

Finding d needs p and q, which means factoring N. At puzzle size this page does that in a second or two.

The whole thing with tiny numbers

p = 5, q = 7 → N = 5² × 7 = 175, p × q = 35 lcm(4, 6) = 12, d = 175⁻¹ mod 12 = 7 (175 × 7 = 1225 = 102 × 12 + 1) encrypt m = 12: c = 12^175 mod 175 = 68 decrypt: m = 68^7 mod 35 = 12 ✓
Step 1

What the puzzle gives you

A Schmidt–Samoa puzzle gives one public number N and a ciphertext c. Paste each one into its own box. Spaces and line breaks are fine.

Already know p and q?

If the puzzle hands you the private primes, fill them in and the worksheet uses them instead of factoring.

Step 2

Split N into p × p × q

The repeated prime is p; the one that appears once is q.

    Step 3

    The private exponent d

    d is the inverse of N modulo lcm(p − 1, q − 1). The extended Euclidean algorithm finds it.

      Step 4

      Decrypt: m = cd mod pq

      Raise the ciphertext to d, and keep the remainder after dividing by p × q, not by N.

        Step 5

        Read the message

        m is a number, and the puzzle decides how it turns back into words or coordinates. If the puzzle says how the message was encoded, use that reading.

        If none of these look like anything

        Decryption scrambles everything when even one digit of an input is off, so a wrong input doesn’t give a slightly wrong answer; it gives noise. Recount the digits of each number against the puzzle (the counts are shown next to every box).

        If the inputs are right, the message may use a different encoding: the puzzle text usually says which one. Lining the blocks up from the end, or skipping some digits first, helps when a short message is tacked onto something else.

        If every digit matches the puzzle and every reading is still noise, you may be using the wrong system. Check that the puzzle really describes this one: what it calls each number, how many public numbers it gives, and how it says the message was locked.