# How to perform Multiplicative Inverse Modulo in IDEA

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.

-
I can't understand your example or your explanation of what you have tried. Do you want to try to edit it, to explain more clearly? – D.W. Mar 14 '13 at 18:26
Straighten notations. CF80 in hexadecimal is 53120 in decimal, but not 3080 by any stretch of imagination; that is -3080 modulo 65536, or -3081 modulo 65537; also, 3080 converted to hexadecimal is 0C08, not 3080. In the context you want unsigned numbers, and displaying them as such (in decimal or hexadecimal). Most importantly, the multiplicative inverse of $x$ is $y$ such that $x⋅y=1$ in the multiplicative group $\pmod{65537}$ (with 65536 mapped to the 16-bit value 0x0000), and you make absolutely no step towards computing that $y$ when $x$ is 53120 or hexadecimal CF80, your goal. – fgrieu Mar 15 '13 at 7:37

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

-
I can't understand how can I get the value of "9194" in Extended Euclidean Algorithm... – goldroger Mar 14 '13 at 18:55
@goldroger: if you run the EEA exactly as given on the wiki page, you come up with a value $x=-28269$. If we take this value modulo 65537 (e.g. add 65537 to it), we find it is equivalent to 37268, which is exactly the value you're looking for. – poncho Mar 14 '13 at 19:50

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.

-
That solution uses that for $p$ prime and $x\not=0\bmod p$, we can compute $x^{-1}\bmod p$ as $x^{p-2}\bmod p$; and builds the 65535th power by a (non-obvious) addition chain. Of course, operator $⋅$ is multiplication $\pmod{65537}$ (with $65536$ mapped to the 16-bit value 0x0000), as used elsewhere in IDEA. This is useful in the context of preparing a key for decryption in IDEA, for it gives the right result without any test, thus no timing dependency beyond that of $⋅$, which would leak information about the key. – fgrieu Mar 15 '13 at 6:58

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.

-

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

-