Cryptography Reference
In-Depth Information
The definition mentioned last is normally quoted uncritically (and not ex-
plained), but it is apparently contradictory. The thing is, we only have 2
16
num-
bers available to represent 2
16
+
1 remainders — the remainder zero is missing
here, or is it? Well, zero can never occur as a remainder: since 2
16
+
1
=
65 537
'happens' to be a prime number, the product of two numbers is divisible only
by 2
16
+
1, if this holds at least for one of the factors. In this arithmetic, how-
ever, we multiply only numbers between 1 and 2
16
together, and none of these
numbers is divisible by the prime number 65 537.
Expressed mathematically: together with '
', we have defined an algebraic
operation within the set of numbers 0, 1,
...
,2
16
−
1, which is always exe-
cutable within this set.
Before describing IDEA any further, we can already see why it calculates with
16-bit numbers rather than, for example, 32-bit numbers: 2
32
+
1 is not a prime
number; rather the following holds:
2
32
+ 1 = 641 * 6700417
We wouldn't be able to define this analogously to the '
' operation for 32-bit
operands.
These three algebraic operations are 'incompatible'. This blurred statement
needs some explanation.
We all know the distributive law
a(b+c)=ab+ac
from school. There is no pair of operations among these three for which the
distributive law holds, i.e., for all 16-bit numbers,
a, b
, and
c
. For instance,
there is the counterexample
a=b=c=1
a+(b
⊕
c)=1+0
=
0+0=(a
⊕
⊕
b) + (a
c)
for the '
+
' and '
⊕
' operations.
