# How can I implement the “Multiplication Modulo” and “Addition Modulo” operations in IDEA?

I am currently working on IDEA (International Data Encryption Algorithm), and I don't know how to perform Multiplication Modulo and Addition Modulo.

This is how IDEA operates:

IDEA operates on 64-bit blocks using a 128-bit key, and consists of a series of eight identical transformations (a round, see the illustration) and an output transformation (the half-round). The processes for encryption and decryption are similar. IDEA derives much of its security by interleaving operations from different groups — modular addition and multiplication, and bitwise eXclusive OR (XOR) — which are algebraically "incompatible" in some sense.

• Bitwise eXclusive OR (denoted with a circled plus ⊕).

• Addition modulo $2^{16}$ (denoted with a boxed plus ⊞).

• Multiplication modulo $2^{16}+1$, where the all-zero word (0x0000) is interpreted as $2^{16}$ (denoted by a circled dot ⊙).

## 1 Answer

Addition modulo $2^{16}$ just means, add the two numbers as you normally would, and subtract $2^{16}$ from the result until the sum is less than $2^{16}$. So suppose you wanted to add, say, 51995 and 29291 modulo $2^{16}$:

51995 + 29291 = 81286

Subtract 2^16 = 65536, you get 81286 - 65536 = 15750

This is less than 65536, so 51995 + 29291 = 15750 modulo 2^16.


Multiplication modulo $2^{16} + 1$ is exactly the same, except you multiply the two numbers instead of adding and you subtract $2^{16} + 1 = 65537$ repeatedly instead of $2^{16}$. And note the extra condition required by IDEA to prevent entropy destruction, that if one of the operands is zero, it is replaced by $2^{16}$ (this is not part of the definition of modular multiplication, but it is required to ensure reversibility - can you see why?).

This is a bit long-winded, fortunately there is a modulo operation available in most programming languages, usually called "mod" or "%", which you can use. Finite data types also have an implicit $2^n$ modulo operation where $n$ is the data type's bit width, through overflow (for instance, if you have a 1-byte variable set to 255, and increment it by one, it'll become zero), unless they are explicitly designed to saturate. There are also bitwise shortcuts you can use for IDEA to make it much faster since multiplication is slow, but I guess you don't really need those.

For a more detailed explanation, please see this link.

• addition mod 2^16 can be achieved by using a 16 bit integer and simply adding. For most programming languages the overflow takes care of the modulo operation. (In c you need to use an unsigned integer to avoid undefined behavior) – CodesInChaos Oct 18 '12 at 9:04
• @CodesInChaos thanks, I will add this to my answer. – Thomas Oct 18 '12 at 12:32
• While it's possible to use x % 65537 that's apt to be a bit slow. An alternative is to split the upper and lower halves and observe that modulus is equal to (lower+65537-upper) % 65537, with the range of the latter formula being sufficiently limited to allow use of 16-bit maths along with some comparisons. – supercat Jul 1 '16 at 21:39
• @Thomas how (2^16)+1 ensures reversibility in case of multiplication? – R. Sam Mar 25 '18 at 15:22
• @R.Sam Try it with 2^4 + 1 = 17, which is also prime (2^16 + 1 = 65537 is prime). Since 17 is prime, numbers 1 to 16 have modular inverses modulo N, but 0 doesn't. Of course, since our input is only 4 bits (0 to 15) we don't have a "number 16" to work with, so instead we say that 0 becomes 16. So now all our inputs have inverses modulo 17, so multiplication is reversible. Does that help? – Thomas Mar 26 '18 at 6:26