e1bacfe55eab8bca2a7e97d2e1d92d5c79631c8a
3 * $Id: idea.c,v 1.1 1997/07/21 13:47:49 mdw Exp $
5 * IDEA encryption routines
6 * Based on Straylight ARM assembler routines
8 * (c) 1996, 1997 Mark Wooding
11 /*----- Licencing 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
27 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.1 1997/07/21 13:47:49 mdw
38 /*----- Notes -------------------------------------------------------------*
40 * This code is optimised for 32-bit processors with reasonable numbers of
41 * registers. Hopefully it should still work on a Spectrum, although rather
42 * slowly. I do assume two's complement arithmetic.
44 * Since this is actually /decompiled/, by hand, from some existing assembler
45 * code, you can expect some parts to be a little strange.
48 /*----- Header files ------------------------------------------------------*/
56 /*----- Low-level support functions ---------------------------------------*/
58 /* --- @idea__inv@ --- *
60 * Arguments: @int n@ = number to invert
62 * Returns: Multiplicative inverse of n, mod 2^{16} + 1
65 static int idea__inv(int n
)
67 long m
, a
, b
, q
, r
, t
;
69 /* --- Check the easy case --- */
74 /* --- Start off the loop --- */
84 t
= a
, a
= b
- q
* a
, b
= t
;
87 /* --- Get return value in range --- */
91 return ((int) a
& 0xFFFF);
96 * An evil macro to do multiplication. Satan lives here.
103 ((y = x * y), x = y & ffff, y = y >> 16, x < y ? \
104 (x = x - y + 1) : (x = x - y)) : \
109 /*----- Key unpacking functions -------------------------------------------*/
111 /* --- @idea_ekeys@ --- *
113 * Arguments: @idea_key *k@ = the expanded key buffer
114 * @const unsigned char *key@ = the user's key encryption key
118 * Use: Unpacks an encryption key.
121 void idea_ekeys(idea_key
*k
, const unsigned char *key
)
123 /* --- Convince compiler to do this properly --- */
125 register const int ffff
= 0xFFFF;
127 uint_32 ka
, kb
, kc
, kd
;
131 /* --- Load the 4 words from the block --- *
136 ka
= load32(key
+ 0);
137 kb
= load32(key
+ 4);
138 kc
= load32(key
+ 8);
139 kd
= load32(key
+ 12);
141 for (count
= 48; count
> 0; count
-= 8) {
143 /* --- Unpack halfwords into the block --- */
145 *p
++ = (ka
>> 16) & ffff
;
147 *p
++ = (kb
>> 16) & ffff
;
149 *p
++ = (kc
>> 16) & ffff
;
151 *p
++ = (kd
>> 16) & ffff
;
154 /* --- Now rotate the 128-bit key --- */
158 ka
= ((ka
<< 25) | (kb
>> 7)) & 0xffffffffu
;
159 kb
= ((kb
<< 25) | (kc
>> 7)) & 0xffffffffu
;
160 kc
= ((kc
<< 25) | (kd
>> 7)) & 0xffffffffu
;
161 kd
= ((kd
<< 25) | (kx
>> 7)) & 0xffffffffu
;
165 /* --- Write the tail-enders over --- */
167 *p
++ = (ka
>> 16) & ffff
;
169 *p
++ = (kb
>> 16) & ffff
;
173 /* --- @idea_invertKey@ --- *
175 * Arguments: @const idea_key *in@ = pointer to input expanded key buffer
176 * @idea_key *out@ = pointer to output expanded key buffer
180 * Use: Computes the inverse (decryption) key given an expanded
181 * IDEA encryption key.
184 void idea_invertKey(const idea_key
*in
, idea_key
*out
)
187 unsigned a
, b
, c
, d
, e
, f
;
188 int *ibuf
= in
->k
, *obuf
= out
->k
;
190 /* --- Deal with identical input and output buffers --- */
194 memcpy(&t
, in
, sizeof(t
));
195 idea_invertKey(&t
, out
);
199 /* --- Do the real work --- */
201 ibuf
+= IDEA_EXPKEYSIZE
;
202 for (i
= 8; i
; i
--) {
217 d
^= e
, e
^= d
, d
^= e
;
228 /* --- Deal with the tail-enders --- */
247 /* --- @idea_dkeys@ --- *
249 * Arguments: @idea_key *k@ = the expanded key buffer
250 * @const unsigned char *key@ = the user's key encryption key
254 * Use: Unpacks a decryption key.
257 void idea_dkeys(idea_key
*k
, const unsigned char *key
)
261 idea_invertKey(&t
, k
);
264 /*----- Main IDEA cipher --------------------------------------------------*/
266 /* --- @idea_encrypt@ --- *
268 * Arguments: @const idea_key *k@ = key to use
269 * @const void *src@ = block to encrypt
270 * @void *dest@ = where to store the result
274 * Use: Encrypts (or decrypts) a block, using the IDEA cryptosystem.
275 * Since the decryption operation is the same as encryption
276 * except that a different key buffer is used, this is all we
277 * need to complete the simple bits.
279 * For people following this at home: I've been very sloppy
280 * about chopping off excess bits from the ints here. Most of
281 * the time it doesn't matter, and when it does, in the
282 * multiplication stage, the macro does this for us.
284 * Our @register const int ffff@ makes another appearance. This
285 * might suggest to compilers that having this constant
286 * available would be beneficial.
288 * Registers are in short supply here. So is legibility.
291 #if defined(TEST_RIG) && defined(DUMPROUNDS)
292 # define _dump(a,b,c,d) \
293 printf(" %5lu %5lu %5lu %5lu\n", \
294 a & ffff, b & ffff, c & ffff, d & ffff)
296 # define _dump(a,b,c,d) ((void)0)
299 #define _round(a, b, c, d) do { \
301 u = kp[0]; v = kp[1]; w = kp[2]; x = kp[3]; y = kp[4]; z = kp[5]; \
303 _mul(a, u); b += v; c += w; _mul(d, x); \
304 u = a ^ c; v = b ^ d; _mul(u, y); v += u; _mul(v, z); u += v; \
305 a ^= v; b ^= u; c ^= v; d ^= u; \
309 void idea_encrypt(const idea_key *k, const void *src, void *dest)
311 register const int ffff
= 0xFFFF;
312 const unsigned char *usrc
= src
;
313 unsigned char *udest
= dest
;
317 uint_32 u
, v
, w
, x
, y
, z
;
319 /* --- Unpack next block into registers --- */
321 a
= (usrc
[0] << 8) | usrc
[1];
322 b
= (usrc
[2] << 8) | usrc
[3];
323 c
= (usrc
[4] << 8) | usrc
[5];
324 d
= (usrc
[6] << 8) | usrc
[7];
326 /* --- Now run the block through the eight rounds --- *
328 * Notice how the arguments swap around so as I don't have to move the
342 /* --- Do the output transformation --- */
353 /* --- Repack and store the block --- */
355 udest
[0] = (a
>> 8) & 0xFF; udest
[1] = a
& 0xFF;
356 udest
[2] = (c
>> 8) & 0xFF; udest
[3] = c
& 0xFF;
357 udest
[4] = (b
>> 8) & 0xFF; udest
[5] = b
& 0xFF;
358 udest
[6] = (d
>> 8) & 0xFF; udest
[7] = d
& 0xFF;
361 /*----- Debugging driver --------------------------------------------------*/
365 #define TESTENCRYPTION
371 for (i
= 1; i
<= 6; i
++)
373 for (i
= 0; i
< 52; i
++) {
375 printf("\n %i ", i
/ 6 + 1);
376 printf("%5i ", *k
++);
381 void dumpblk(char *bb
)
383 unsigned char *b
= (unsigned char *)bb
;
384 printf("++ %5u %5u %5u %5u\n",
403 sscanf(buf
, "%u%u", &i
, &j
);
410 #ifdef TESTENCRYPTION
415 unsigned char k
[] = { 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8 };
417 unsigned char b
[] = { 0, 0, 0, 1, 0, 2, 0, 3 };
419 static idea_key correct_e
= { {
421 7, 8, 1024, 1536, 2048, 2560,
422 3072, 3584, 4096, 512, 16, 20,
423 24, 28, 32, 4, 8, 12,
424 10240, 12288, 14336, 16384, 2048, 4096,
425 6144, 8192, 112, 128, 16, 32,
426 48, 64, 80, 96, 0, 8192,
427 16384, 24576, 32768, 40960, 49152, 57345,
431 static idea_key correct_d
= { {
432 65025, 65344, 65280, 26010, 49152, 57345,
433 65533, 32768, 40960, 52428, 0, 8192,
434 42326, 65456, 65472, 21163, 16, 32,
435 21835, 65424, 57344, 65025, 2048, 4096,
436 13101, 51200, 53248, 65533, 8, 12,
437 19115, 65504, 65508, 49153, 16, 20,
438 43670, 61440, 61952, 65409, 2048, 2560,
439 18725, 64512, 65528, 21803, 5, 6,
440 1, 65534, 65533, 49153
443 static unsigned char correct_encrypt
[] = {
444 4603 / 256, 4603 % 256,
445 60715 / 256, 60715 % 256,
446 408 / 256, 408 % 256,
447 28133 / 256, 28133 % 256
450 static unsigned char correct_decrypt
[] = {
451 0, 0, 0, 1, 0, 2, 0, 3
458 for (i
= 0; i
< IDEA_EXPKEYSIZE
; i
++) {
459 if (e
.k
[i
] != correct_e
.k
[i
]) {
461 printf("!!! bad encryption key values!\n\n");
465 printf("*** expanded encryption key correct\n\n");
471 for (i
= 0; i
< IDEA_EXPKEYSIZE
; i
++) {
472 if (d
.k
[i
] != correct_d
.k
[i
]) {
474 printf("!!! bad decryption key values!\n\n");
478 printf("*** expanded decryption key correct\n\n");
480 idea_encrypt(&e
, b
, b
);
482 if (memcmp(b
, correct_encrypt
, 8) == 0)
483 printf("*** correct encipherment\n\n");
485 printf("!!! bad encipherment\n\n");
487 idea_encrypt(&d
, b
, b
);
489 if (memcmp(b
, correct_decrypt
, 8) == 0)
490 printf("*** correct decipherment\n");
492 printf("!!! bad decipherment\n");
501 /*----- That's all, folks -------------------------------------------------*/