Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ⊙).

enter image description here

share|improve this question
up vote 3 down vote accepted

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.

share|improve this answer
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 at 21:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.