Okamoto–Uchiyama

A guided worksheet for the Okamoto–Uchiyama cryptosystem. Paste the numbers in, and it explains what each one is, checks it fits, and does the big-number math, working modulo p². Nothing leaves this page; your work is saved in this browser only.

How Okamoto–Uchiyama works two minutes, with tiny numbers

Tatsuaki Okamoto and Shigenori Uchiyama's system uses a key of the form p2 × q, and a trick that works modulo p2. Messages have to be smaller than the secret prime p, so they're short compared with the key.

Making the keys

  1. Pick secret primes p and q, and publish n = p2 × q.
  2. Pick a base g whose power gp−1 mod p2 isn't 1, and publish it.
  3. Publish h = gn mod n as well. The public key is (n, g, h).

The L function

Decryption uses L(x) = (x − 1) / p. Raising anything to the power p − 1 modulo p2 leaves a number that's 1 more than a multiple of p, so the division is exact.

Locking and unlocking

  1. Encrypt a message m smaller than p: pick a random r and send c = gm × hr mod n.
  2. Work out a = L(cp−1 mod p2) and b = L(gp−1 mod p2).
  3. Decrypt: m = a × b−1 mod p. The random r drops out, because hp−1 leaves L equal to 0.

The whole thing with tiny numbers

p = 7, q = 11 → n = 7² × 11 = 539, p² = 49 g = 2 (2^6 mod 49 = 15, not 1), h = 2^539 mod 539 = 116 encrypt m = 4 with r = 3: c = 2^4 × 116^3 mod 539 = 310 a = L(310^6 mod 49) = 1, b = L(2^6 mod 49) = L(15) = 2, b⁻¹ mod 7 = 4 m = 1 × 4 mod 7 = 4 ✓
Step 1

What the puzzle gives you

An Okamoto–Uchiyama puzzle gives a public key (n, g, h) and a ciphertext c. Paste each one into its own box.

Already know p?

If the puzzle hands you the secret prime, fill it in and the worksheet uses it instead of factoring.

Step 2

Split n into p × p × q

Only p, the repeated prime, is needed to decrypt.

    Step 3

    Work modulo p2

    Raise c and g to the power p − 1 modulo p2, and apply L(x) = (x − 1) / p to each.

      Step 4

      Decrypt: m = a × b−1 mod p

      Divide a by b modulo p: multiply by the inverse of b.

        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.