3 * $Id: idea.c,v 1.2 1997/08/04 10:24:22 mdw Exp $
5 * IDEA encryption routines
6 * Based on Straylight ARM assembler routines
8 * (c) 1996, 1997 Mark Wooding
11 /*----- Licensing notice --------------------------------------------------*
13 * This file is part of `become'
15 * `Become' is free software; you can redistribute it and/or modify
16 * it under the terms of the GNU General Public License as published by
17 * the Free Software Foundation; either version 2 of the License, or
18 * (at your option) any later version.
20 * `Become' is distributed in the hope that it will be useful,
21 * but WITHOUT ANY WARRANTY; without even the implied warranty of
22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 * GNU General Public License for more details.
25 * You should have received a copy of the GNU General Public License
26 * along with `become'; if not, write to the Free Software Foundation,
27 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.2 1997/08/04 10:24:22 mdw
34 * Sources placed under CVS control.
36 * Revision 1.1 1997/07/21 13:47:49 mdw
41 /*----- Notes -------------------------------------------------------------*
43 * This code is optimised for 32-bit processors with reasonable numbers of
44 * registers. Hopefully it should still work on a Spectrum, although rather
45 * slowly. I do assume two's complement arithmetic.
47 * Since this is actually /decompiled/, by hand, from some existing assembler
48 * code, you can expect some parts to be a little strange.
51 /*----- Header files ------------------------------------------------------*/
60 /*----- Low-level support functions ---------------------------------------*/
62 /* --- @idea__inv@ --- *
64 * Arguments: @int n@ = number to invert
66 * Returns: Multiplicative inverse of n, mod 2^{16} + 1
69 static int idea__inv(int n
)
71 long m
, a
, b
, q
, r
, t
;
73 /* --- Check the easy case --- */
78 /* --- Start off the loop --- */
88 t
= a
, a
= b
- q
* a
, b
= t
;
91 /* --- Get return value in range --- */
95 return ((int) a
& 0xFFFF);
100 * An evil macro to do multiplication. Satan lives here.
107 ((y = x * y), x = y & ffff, y = y >> 16, x < y ? \
108 (x = x - y + 1) : (x = x - y)) : \
113 /*----- Key unpacking functions -------------------------------------------*/
115 /* --- @idea_ekeys@ --- *
117 * Arguments: @idea_key *k@ = the expanded key buffer
118 * @const unsigned char *key@ = the user's key encryption key
122 * Use: Unpacks an encryption key.
125 void idea_ekeys(idea_key
*k
, const unsigned char *key
)
127 /* --- Convince compiler to do this properly --- */
129 register const int ffff
= 0xFFFF;
131 uint_32 ka
, kb
, kc
, kd
;
135 /* --- Load the 4 words from the block --- *
140 ka
= load32(key
+ 0);
141 kb
= load32(key
+ 4);
142 kc
= load32(key
+ 8);
143 kd
= load32(key
+ 12);
145 for (count
= 48; count
> 0; count
-= 8) {
147 /* --- Unpack halfwords into the block --- */
149 *p
++ = (ka
>> 16) & ffff
;
151 *p
++ = (kb
>> 16) & ffff
;
153 *p
++ = (kc
>> 16) & ffff
;
155 *p
++ = (kd
>> 16) & ffff
;
158 /* --- Now rotate the 128-bit key --- */
162 ka
= ((ka
<< 25) | (kb
>> 7)) & 0xffffffffu
;
163 kb
= ((kb
<< 25) | (kc
>> 7)) & 0xffffffffu
;
164 kc
= ((kc
<< 25) | (kd
>> 7)) & 0xffffffffu
;
165 kd
= ((kd
<< 25) | (kx
>> 7)) & 0xffffffffu
;
169 /* --- Write the tail-enders over --- */
171 *p
++ = (ka
>> 16) & ffff
;
173 *p
++ = (kb
>> 16) & ffff
;
177 /* --- @idea_invertKey@ --- *
179 * Arguments: @const idea_key *in@ = pointer to input expanded key buffer
180 * @idea_key *out@ = pointer to output expanded key buffer
184 * Use: Computes the inverse (decryption) key given an expanded
185 * IDEA encryption key.
188 void idea_invertKey(const idea_key
*in
, idea_key
*out
)
191 unsigned a
, b
, c
, d
, e
, f
;
192 int *ibuf
= in
->k
, *obuf
= out
->k
;
194 /* --- Deal with identical input and output buffers --- */
198 memcpy(&t
, in
, sizeof(t
));
199 idea_invertKey(&t
, out
);
203 /* --- Do the real work --- */
205 ibuf
+= IDEA_EXPKEYSIZE
;
206 for (i
= 8; i
; i
--) {
221 d
^= e
, e
^= d
, d
^= e
;
232 /* --- Deal with the tail-enders --- */
251 /* --- @idea_dkeys@ --- *
253 * Arguments: @idea_key *k@ = the expanded key buffer
254 * @const unsigned char *key@ = the user's key encryption key
258 * Use: Unpacks a decryption key.
261 void idea_dkeys(idea_key
*k
, const unsigned char *key
)
265 idea_invertKey(&t
, k
);
268 /*----- Main IDEA cipher --------------------------------------------------*/
270 /* --- @idea_encrypt@ --- *
272 * Arguments: @const idea_key *k@ = key to use
273 * @const void *src@ = block to encrypt
274 * @void *dest@ = where to store the result
278 * Use: Encrypts (or decrypts) a block, using the IDEA cryptosystem.
279 * Since the decryption operation is the same as encryption
280 * except that a different key buffer is used, this is all we
281 * need to complete the simple bits.
283 * For people following this at home: I've been very sloppy
284 * about chopping off excess bits from the ints here. Most of
285 * the time it doesn't matter, and when it does, in the
286 * multiplication stage, the macro does this for us.
288 * Our @register const int ffff@ makes another appearance. This
289 * might suggest to compilers that having this constant
290 * available would be beneficial.
292 * Registers are in short supply here. So is legibility.
295 #if defined(TEST_RIG) && defined(DUMPROUNDS)
296 # define _dump(a,b,c,d) \
297 printf(" %5lu %5lu %5lu %5lu\n", \
298 a & ffff, b & ffff, c & ffff, d & ffff)
300 # define _dump(a,b,c,d) ((void)0)
303 #define _round(a, b, c, d) do { \
305 u = kp[0]; v = kp[1]; w = kp[2]; x = kp[3]; y = kp[4]; z = kp[5]; \
307 _mul(a, u); b += v; c += w; _mul(d, x); \
308 u = a ^ c; v = b ^ d; _mul(u, y); v += u; _mul(v, z); u += v; \
309 a ^= v; b ^= u; c ^= v; d ^= u; \
313 void idea_encrypt(const idea_key *k, const void *src, void *dest)
315 register const int ffff
= 0xFFFF;
316 const unsigned char *usrc
= src
;
317 unsigned char *udest
= dest
;
321 uint_32 u
, v
, w
, x
, y
, z
;
323 /* --- Unpack next block into registers --- */
325 a
= (usrc
[0] << 8) | usrc
[1];
326 b
= (usrc
[2] << 8) | usrc
[3];
327 c
= (usrc
[4] << 8) | usrc
[5];
328 d
= (usrc
[6] << 8) | usrc
[7];
330 /* --- Now run the block through the eight rounds --- *
332 * Notice how the arguments swap around so as I don't have to move the
346 /* --- Do the output transformation --- */
357 /* --- Repack and store the block --- */
359 udest
[0] = (a
>> 8) & 0xFF; udest
[1] = a
& 0xFF;
360 udest
[2] = (c
>> 8) & 0xFF; udest
[3] = c
& 0xFF;
361 udest
[4] = (b
>> 8) & 0xFF; udest
[5] = b
& 0xFF;
362 udest
[6] = (d
>> 8) & 0xFF; udest
[7] = d
& 0xFF;
365 /*----- Debugging driver --------------------------------------------------*/
369 #define TESTENCRYPTION
375 for (i
= 1; i
<= 6; i
++)
377 for (i
= 0; i
< 52; i
++) {
379 printf("\n %i ", i
/ 6 + 1);
380 printf("%5i ", *k
++);
385 void dumpblk(char *bb
)
387 unsigned char *b
= (unsigned char *)bb
;
388 printf("++ %5u %5u %5u %5u\n",
407 sscanf(buf
, "%u%u", &i
, &j
);
414 #ifdef TESTENCRYPTION
419 unsigned char k
[] = { 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8 };
421 unsigned char b
[] = { 0, 0, 0, 1, 0, 2, 0, 3 };
423 static idea_key correct_e
= { {
425 7, 8, 1024, 1536, 2048, 2560,
426 3072, 3584, 4096, 512, 16, 20,
427 24, 28, 32, 4, 8, 12,
428 10240, 12288, 14336, 16384, 2048, 4096,
429 6144, 8192, 112, 128, 16, 32,
430 48, 64, 80, 96, 0, 8192,
431 16384, 24576, 32768, 40960, 49152, 57345,
435 static idea_key correct_d
= { {
436 65025, 65344, 65280, 26010, 49152, 57345,
437 65533, 32768, 40960, 52428, 0, 8192,
438 42326, 65456, 65472, 21163, 16, 32,
439 21835, 65424, 57344, 65025, 2048, 4096,
440 13101, 51200, 53248, 65533, 8, 12,
441 19115, 65504, 65508, 49153, 16, 20,
442 43670, 61440, 61952, 65409, 2048, 2560,
443 18725, 64512, 65528, 21803, 5, 6,
444 1, 65534, 65533, 49153
447 static unsigned char correct_encrypt
[] = {
448 4603 / 256, 4603 % 256,
449 60715 / 256, 60715 % 256,
450 408 / 256, 408 % 256,
451 28133 / 256, 28133 % 256
454 static unsigned char correct_decrypt
[] = {
455 0, 0, 0, 1, 0, 2, 0, 3
462 for (i
= 0; i
< IDEA_EXPKEYSIZE
; i
++) {
463 if (e
.k
[i
] != correct_e
.k
[i
]) {
465 printf("!!! bad encryption key values!\n\n");
469 printf("*** expanded encryption key correct\n\n");
475 for (i
= 0; i
< IDEA_EXPKEYSIZE
; i
++) {
476 if (d
.k
[i
] != correct_d
.k
[i
]) {
478 printf("!!! bad decryption key values!\n\n");
482 printf("*** expanded decryption key correct\n\n");
484 idea_encrypt(&e
, b
, b
);
486 if (memcmp(b
, correct_encrypt
, 8) == 0)
487 printf("*** correct encipherment\n\n");
489 printf("!!! bad encipherment\n\n");
491 idea_encrypt(&d
, b
, b
);
493 if (memcmp(b
, correct_decrypt
, 8) == 0)
494 printf("*** correct decipherment\n");
496 printf("!!! bad decipherment\n");
505 /*----- That's all, folks -------------------------------------------------*/