Tag Info

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

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

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

Multiplication of bits matrices works just like multiplication of number matrices, except the rule of addition is modified to: $1+1\mapsto 0$. Let $U$ (resp. $V$) be a square matrix of $n\times n$ elements noted $u_{l,c}$ (resp. $v_{l,c}$) with $1\le l\le n$ and $1\le c\le n$. The product $U\cdot V$ is a square matrix $W$ of $n\times n$ elements noted ...

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

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