Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
As we can see in the picture we have a multiplication in this algorithm, we know that two 16 bit inputs should have a 32 bit output, but here we just use 16 bits of the 32 bit output.
For decryption we can reverse the algorithm from bottom of the algorithm to top, but how can we invert the multiplication that produced value of $a$ to recover $I$?
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 Edition, which had a good description (as well as the provided diagram):
Decryption is exactly the same, except that the subkeys are reversed and slightly different. The decryption subkeys are either the additive or multiplicative inverses of the encryption subkeys. (For the purposes of IDEA, the all-zero sub-block is considered to represent $2^{16} = –1$ for multiplication modulo $2^{16} + 1$; thus the multiplicative inverse of 0 is 0.)
For decryption you would take the result of the original multiplication operation and multiply that by the multiplicative inverse of the subkey that was used. (The subkey was derived from the original key, and the multiplicative inverse of a subkey can be calculated from the subkey.) This yields the original input value.
This works mathematically because the multiplication operation is performed modulo $2^{16}+1$ which (combined with with the provided special case treatment of 0) forms a mathematical group structure. Within a group, every multiplication operation is guaranteed to have an inverse value that can be used to reverse the operation.
It forms a group because, in general, the numbers $1, 2, ..., p-1$ form a multiplicative group modulo a prime $p$ (this group can denoted by $\mathbb{Z}^*_p$), and in our case $2^{16}+1$ is prime. The special case for 0 is necessary because of a minor implementation complication: A variable value of $0$ isn't in the group and $2^{16}$ can't be stored in a 16-bit variable. This was easy to resolve: Define the unused $0$ to represent $2^{16}$.
