2 Life Modulo The Field Prime (2026-08-12)

This post’s ID is 3634679381154800797.

I am by night an embedded engineer. By day, I work on systems security and manageability. Where do the two collide?

I have an upcoming project involving doing some weird cryptography on a smart card. This is a rough endeavour, as it’s a 16-bit chip with ~4KiB of usable RAM for our purposes and on which I can only run JVM bytecode. Additionally, I can only use the opcodes supported by JavaCard. Finally, I intend to produce as much of this bytecode as I can using a Python script so that I don’t have to write Java.

Thankfully, many modern signature schemes don’t require things like efficient multiplication of 2048-bit numbers modulo a field prime anymore (looking at you, RSA). Nevertheless, I cannot guarantee:

• Multiplications are fast
• Multiplications are constant-time
• Division and modular reduction are fast
• Division and modular reduction are constant time
• Bit-shifts are constant time with respect to the shift amount

What I can guarantee is that this microcontroller does not have a cache (therefore, no cache timing attacks, therefore, we can probably index on secrets in constant time). In fact, I will assume that the following are constant-time:

• Nonvolatile memory reads
• Addition and subtraction
• Bitwise operations
• Bit-shifts with respect to the number being shifted

The scheme I’m considering implementing requires a lot of arithmetic modulo a very small Mersenne prime (127 or 31, depending on the parameter set, at the targeted security level). We will assume without loss of generality that the prime is 127.

How do we do this efficiently and in constant time?

2.1 Addition and subtraction

Since the field elements fit into 7 bits, we can store them in an unsigned byte and simply add them without worrying about overflow. For reduction, we could try and do a conditional subtraction in constant time, but that would require some pretty involved bitwise arithmetic.

What if we just do a table lookup?

We can store a 256-element table that contains, for each index $i$, $i \mod 127$. Maybe inefficient in space, but effortless and constant-time under our assumptions.

// Assume x is a short at the top of the stack
getstatic_a $REDUCTION_LUT
swap_x 0x11 // Swap the top two values
baload

For subtraction, it gets a little more difficult, since we need a special case for zero.

// Assume x is a short at the top of the stack
dup
s2i
iconst_0
icmp

// Smear so that 1 becomes ~0, ~0 stays as ~0, and 0 stays as 0.
dup
sconst_1
sushl
sor
dup
sconst_2
sushl
sor
dup
sconst_4
sushl
sor

bspush 127
sand
swap_x 0x11
ssub

2.2 Multiplication and inversion (make division)

NOTE (2026-08-18): a previous version of this post said “(however, for order $p^k$, $k > 1$, $p$ prime, $\log_p 0 \equiv k \pmod{p^k}$)”. This isn’t true. I’m not sure why I thought it was true. $\mathbb{Z}/p^k\mathbb{Z}$ for $p$ prime and $k > 1$ forms a ring, not a group, so logarithms are not well-defined.

This gets slightly more interesting. We can do a log-antilog table for these, it’s conceptually really easy; there’s just one small problem. What about multiplication by zero? Zero doesn’t have a logarithm in any base for fields of prime order. So how do we, in constant time, support multiplication by zero using a log table?

The answer is it doesn’t really matter what we put in the zero slot, so long as we check afterwards and replace it in constant time. The extra cost of that bites, though.

// Assume x and y are shorts at the top of the stack
dup2
getstatic_a $LOG_TABLE
swap_x 0x11
baload

// Stack is now x, y, x, log_y
swap_x 0x11
getstatic_a $LOG_TABLE
swap_x 0x11

// Stack is now x, y, log_y, log_x
sadd
getstatic_a $REDUCTION_LUT
swap_x 0x11
baload

// Stack is now x, y, log_xy
getstatic_a $ANTILOG_TABLE
swap_x 0x11
baload

// Stack is now x, y, xy. Time to compare y to zero:
swap_x 0x11
s2i
iconst_0
icmp

// Smear so that 1 becomes ~0, ~0 stays as ~0, and 0 stays as 0.
dup
sconst_1
sushl
sor
dup
sconst_2
sushl
sor
dup
sconst_4
sushl
sor

// Stack is now x, xy, (y == 0)? 0x0 : 0xff
sand

// Stack is now x, xy
swap_x 0x11
s2i
iconst_0
icmp

// Smear so that 1 becomes ~0, ~0 stays as ~0, and 0 stays as 0.
dup
sconst_1
sushl
sor
dup
sconst_2
sushl
sor
dup
sconst_4
sushl
sor

sand
// And now we have the actual multiplied version!

Inversion is easier, we can just assume inverting zero never happens and put a sentinel value (I’m a Zoomer, so I like 0x67) in our antilog table for debugging.

That’s all I have to say on the topic, I really just thought it was interesting.

Comments