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.

Diagram of IDEA round function

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$?

share|improve this question
    
Where did you get that image from? $\;$ –  Ricky Demer Oct 13 '13 at 20:22
    
@RickyDemer most likely from the Wikipedia page. For some reason it doesn't have a notational description of the algorithm (which would have been useful in this case) –  rath Oct 14 '13 at 19:15
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
Thanks alot, I got it, group is the right trick for this. –  user1422847 Oct 15 '13 at 3:59
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.