Massey–Omura · Tools of the Trade

How Massey–Omura works two minutes, with tiny numbers

James Massey and Jim Omura's system, built on Adi Shamir's three-pass protocol, sends a message with no shared key and no public key at all. Picture a box sent back and forth with two padlocks.

The three passes

Alice and Bob agree on a public prime p. Each picks a secret exponent that shares no factor with p − 1: Alice a, Bob b.
Pass 1: Alice locks the message: c₁ = m^a mod p.
Pass 2: Bob adds his lock: c₂ = c₁^b mod p.
Pass 3: Alice removes her lock, raising to her unlocking exponent u = a⁻¹ mod (p − 1): c₃ = c₂^u mod p, which equals m^b.
Bob removes his own lock with b⁻¹ mod (p − 1) and reads m.

Being the eavesdropper

All three numbers travel in the open. Since c₂ = c₁^b, finding Bob's b is a discrete logarithm, and so is finding Alice's u from c₃ = c₂^u. With b, undo Bob's lock on c₃. With u, use it on c₁ just as Alice would have. A discrete log is practical when p − 1 splits into fairly small primes (Pohlig–Hellman), and puzzles pick primes like that.

The whole thing with tiny numbers

p = 23 (p − 1 = 22). Alice a = 3, u = 15 (3 × 15 = 45 = 2 × 22 + 1). Bob b = 5, b⁻¹ = 9. message m = 10 pass 1: c1 = 10^3 mod 23 = 11 pass 2: c2 = 11^5 mod 23 = 5 pass 3: c3 = 5^15 mod 23 = 19 (= 10^5 mod 23, the message under Bob's lock only) Bob: 19^9 mod 23 = 10 ✓

Step 1

What the puzzle gives you

A three-pass puzzle gives the public prime and the three numbers that went back and forth, in order. Puzzles often show them as a conversation, so work out which pass is which.

Already know b or u?

If the puzzle gives away either exponent, fill it in and the worksheet skips the search.

Step 2

Pick a lock to break

Either one is enough. Both are discrete logarithms modulo p.

Bob's lock b, from c₂ = c₁^b mod p,
then take it off c₃: m = c₃^b⁻¹ mod p Alice's unlocking exponent u, from c₃ = c₂^u mod p,
then use it on c₁: m = c₁^u mod p

Step 3

Break `p − 1` into primes

The discrete-log search splits into one smaller search for each prime factor of p − 1. The biggest factor decides how long it takes, so that's the first thing to find out.

Step 4

The discrete logarithm

Show the Pohlig–Hellman pieces

For each prime power dividing the order of the base, the page raises both sides to a power that leaves a much smaller problem. Small pieces are solved by baby-step giant-step, a lookup table of powers. Big pieces are solved by Pollard's rho, which takes random-looking walks on every processor core until two walks land on the same number. The Chinese Remainder Theorem then glues the pieces into one exponent.

Step 5

Take the lock off

With one exponent in hand, do what its owner would do.

Step 6

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.