If you are interested in 128-bit block size IDEA, here is a working
model which is very close to original design. Instead of multiplication
(mod 2^16+1) it uses multiplication (mod 2^32+1).
"A naive variation might double the block size.
The algorithm (IDEA) would work just as well with 32-bit sub-blocks
instead of 16-bit sub-blocks and a 256-bit key. Encryption would be
quicker and security would increase 2^32 times. Or would it?
The theory behind the algorithm hinges on the fact
that (2^16 + 1) is a prime, (2^32 + 1) is not.
Perhaps the algorithm could be modified to work, but it
would have very different security properties.
Lai says it would be difficult to make it work..."
(B. Schneier "Applied Cryptography" 2-nd ed. p.325)
(Let's say that I was naive...)
From the point of view of encryption modular multiplication is just
equivalent to the S-box with the corresponding number of entries. It maps
the input subblock to the output subblock of the same size (16 or 32 bits).
The inverse transformation must be always possible, otherwise the subblock
will become undecryptable.
However, (2^32 + 1) is a composite number, equal to 641 x 6700417, and
there are 32-bit numbers which have no multiplicative inverses
(multiples of 641 or of 6700417). There are not a lot of numbers like this, but
they exist, and the algorithm must have an automatic way to avoid those.
The situation has another aspect. In 8 full rounds of IDEA only 34
multipliers are used for encryption. Thus if it would be possible to come
up with the way to set up 34 key-derived "long" multipliers and 34 inverses,
the algorithm would work with the double block length as easy as with
the original one.
The basic facts were as follows. (All operations (mod 2^32 + 1).)
1. If a 32-bit number is repeatedly multiplied by itself, yielding
consecutive powers (mod 2^32 + 1), this process cannot go forever.
(The number must be relatively prime to 2^32 + 1). After a certain
number of multiplications the product will become equal to 1, and
then the whole cycle will repeat. This is a 200-year old fact, due
to Euler, and the maximum possible length of the loop is equal to the
least common multiple of (641 - 1) and (6700417 - 1). This common
multiple is 33502080 and it is commonly known as Euler Totient.
2. The actual length of the loop can be a fraction of the maximum
possible, depending on the initial starting number (in future discussion
this number will be called SEED).
3. If the length of the loop is N, then SEED^N = 1. Also it follows
that SEED^(N-1) * SEED = 1, consequently SEED^(N-1) and SEED are
multiplicative inverses of one another, same is true for SEED^(N-2) and
SEED^2, for SEED^(N-3) and SEED^3, and so on. Interesting enough,
SEED^(N/2) is its own multiplicative inverse, just like 1.
4. The necessary multipliers can be set up as powers of an
appropriately chosen SEED, where the 16-bit subkeys will determine the
power to raise the SEED. Inverses can be set up in the same way.
Finding the necessary numbers turned out to be easy. I stopped after
finding 4 appropriate values for SEED, although probably could find a dozen
more without effort. Here are the numbers and inverses.
SEED INVERSE
0x6A5F92D5 0xB28409BC
0x25E6D746 0xC9868267
0x8B34DD6A 0x3EB4FD73
0x6A09E667 0x4520A9C6
(this last number pair is especially interesting. The SEED happens to be
the first 8 hex digits of SQRT(2), less initial 1, the use of this
number will dispel any suspicions about a "trap door" built into SEED).
From now on everything was clear. Each of the above numbers
produces a 33502080 long cycle of its powers, the same is true for inverses. It is
sufficient to take the 16-bit subkey, raise the SEED to the corresponding
power, raise the INVERSE to the same power, and "lo and behold!", here are
two fully functional modular multipliers, derived from the key and ready to be
used for encryption and decryption.
Practically it turned out that computations could be done very fast if
"fundamental" powers of SEED and INVERSE were precomputed and arranged
into a table.
Full source text of the program can be found at
< http://www.boriskazak.com/white/ciphers >. Later the content of this directory
will grow, however, all ciphers exposed will have one feature in common -
they will be all based on modular multiplication.
The algorithm works on the 128-bit block divided into 4 32-bit subblocks.
The sequence of operations is the same as in the original IDEA, the number of
rounds can be made variable by redefining the constant ROUNDS.
Key scheduling is different from original IDEA. It uses the same modular
multiplication and the same SEED to produce a randomized stream of subkeys. This
program will accept any length of key up to 64 bytes, in the posted version the
constant MAXKEY is #defined as 7, limiting the length of the user key to 7
characters (56 bytes), in order to comply with the USA export
restrictions.
Any ANSI-compliant version of C will compile this program. The
short "main" is used for illustration of the program functioning.
No attempt was made to optimize the program in any way. It is
intended to serve as a working model, not as a racing car.