2
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ 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) $\endgroup$
    – CodesInChaos
    Commented Oct 18, 2012 at 9:04
  • $\begingroup$ @CodesInChaos thanks, I will add this to my answer. $\endgroup$
    – Thomas
    Commented Oct 18, 2012 at 12:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – supercat
    Commented Jul 1, 2016 at 21:39
  • $\begingroup$ @Thomas how (2^16)+1 ensures reversibility in case of multiplication? $\endgroup$
    – R. Sam
    Commented Mar 25, 2018 at 15:22
  • $\begingroup$ @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? $\endgroup$
    – Thomas
    Commented Mar 26, 2018 at 6:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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