Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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
add comment

4 Answers

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
2  
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
add comment

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.

share|improve this answer
add comment

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
share|improve this answer
add comment

Your Answer

 
discard

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.