How to perform Multiplicative Inverse Modulo in IDEA

Question

How to perform the Multiplicative Inverse Modulo in International Data Encryption Algorithm? I don't understand on how to perform it…

For example, let's say I have a value of cf80 and the value that is appearing to me is this 3080. This is the thing that I've done based on my understanding:

answer = 53120 % 65537  
53120(integer value of 3080) = 3080

When I convert the result in hexadecimal, the value is 3080 but the correct result should be 9194.

Answer 1

Well, the multiplicative inverse of $a$ is defined to be that value $b$ for which $a \times b = 1$, where $\times$ is the multiplication operation in the field/ring/group in question.

Because we're talking about the group of multiplication modulo 65537, that means that the problem is, given $a$, find $b$ such that $ab \bmod 65537 = 1$.

Now, the % operator is C doesn't do it. The classical way is to use the Extended Euclidean algorithm, where the two inputs to the algorithm is $a$ and $65537$; and have it find a solution to the equation $ax + 65537y = GCD(a, 65537) = 1$; the value $x$ is the multiplicative inverse you're looking for.

Of course, since there are only 65536 possible inverses, another possibility is simply have a table of the 65536 possible inverses, and just do a lookup. In that case, you can use the Extended Euclidean algorithm to build the table.

Oh, and as a reminder; idea interprets the 0000 bit pattern as the value 65536 as far as multiplication is concerned (as the value 0 doesn't have an inverse).

Answer 2

One way to do it is to exponentiate the value you want to invert by $65537-2$. You can do this quickly using the shortest addition chain for powering $65535$ modulo $65537$:

$$ \begin{eqnarray} a_0 &=& {\tt\text{0xcf80}} \\ a_1 &=& a_0 \cdot a_0 \\ a_2 &=& a_1 \cdot a_0 \\ a_3 &=& a_2 \cdot a_2 \\ a_4 &=& a_3 \cdot a_3 \\ a_5 &=& a_4 \cdot a_2 \\ a_6 &=& a_5 \cdot a_5 \\ a_7 &=& a_6 \cdot a_6 \\ a_8 &=& a_7 \cdot a_7 \\ a_9 &=& a_8 \cdot a_8 \\ a_{10} &=& a_9 \cdot a_5 \\ a_{11} &=& a_{10} \cdot a_{10} \\ a_{12} &=& a_{11} \cdot a_{11} \\ a_{13} &=& a_{12} \cdot a_{12} \\ a_{14} &=& a_{13} \cdot a_{13} \\ a_{15} &=& a_{14} \cdot a_{14} \\ a_{16} &=& a_{15} \cdot a_{15} \\ a_{17} &=& a_{16} \cdot a_{16} \\ a_{18} &=& a_{17} \cdot a_{17} \\ a_{19} &=& a_{18} \cdot a_{10} \\ inv &=& {\tt\text{0x9194}} = a_{19}. \end{eqnarray} $$

Beware that depending on how you perform the modular multiplications in IDEA, you may be susceptible to some timing attacks.

Answer 3

You don't need to compute a multiplicative inverse to encrypt or decrypt, in IDEA. All you need is the ability to multiply modulo $2^{16}+1$. See How can I implement the "Multiplication Modulo" and "Addition Modulo" operations in IDEA?

Key generation involves computing a multiplicative inverse. One way to compute the multiplicative inverse is using the extended Euclidean algorithm. Another way is to raise to the power $2^{16}-1$. Either way works.

Answer 4

Below is a small ruby program which calculates the inverse with respect to the IDEA multiplication. The IDEA multiplication is defined on [0..65535] by identifying 0 with 65536 and multiplying mod 65537 (the 4-th Fermat prime). The IDEA-multiplication can be calculated with data-independent timing as you can see below in mult. The addition chain used by Samuel Neves for the exponentiation can be obtained by the factorization 65535 = 3*5*17*257 so that can write it in a double loop (in the outer loop "4.times do |i|" the variable i takes the values 0,1,2,3).

#!/usr/bin/env ruby

def mult(x, y)
  x, y = (x-1) & 0xffff, (y-1)& 0xffff
  z = (x+y+x*y) % 0x10001
  z = (z+1) & 0xffff
end

def inv(x)
  4.times do |i|
    y = mult(x, x)
    ((1<<i)-1).times do
      y = mult(y, y)
    end
    x = mult(x, y)
  end
  x
end

puts('0x%x' % inv(0xcf80))

The output of the program is

0x9194