Tag Info

5

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

5

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

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

3

The multiplication operation is indeed not uniquely reversible given just the output. But we also have one of the inputs, namely, the subkey. We can use that to reverse the multiplication. Decryption for IDEA requires changing the subkeys in the key schedule. I didn't find a good description of IDEA online, so I went back to Applied Cryptography, 2nd ...

1

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

Only top voted, non community-wiki answers of a minimum length are eligible