[u/mdw/catacomb] / idea.c

/* -*-c-*-
 *
 * $Id: idea.c,v 1.1 1999/09/03 08:41:12 mdw Exp $
 *
 * Implementation of the IDEA cipher
 *
 * (c) 1999 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: idea.c,v $
 * Revision 1.1  1999/09/03 08:41:12  mdw
 * Initial import.
 *
 */

/*----- Header files ------------------------------------------------------*/

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <mLib/bits.h>

#include "blkc.h"
#include "idea.h"

/*----- Main code ---------------------------------------------------------*/

/* --- @inv@ --- *
 *
 * Arguments:	@uint16 n@ = number to invert
 *
 * Returns:	Multiplicative inverse of @n@ %$\pmod{2^{16} + 1}$%.
 *
 * Use:		Computes multiplicative inverses.  This is handy for the
 *		decryption key scheduling.
 */

static uint16 inv(uint16 n)
{
  uint32 m = 0x10001;
  uint32 a = 1, b = 0;

  for (;;) {
    uint32 q, r, t;
    if (!(r = m % n))
      break;
    q = m / n;
    m = n; n = r;
    t = a; a = b - q * a; b = t;
  }
  if (a > MASK16)
    a += 1;
  return (U16(a));
}

/* --- @MUL@ --- *
 *
 * Arguments @x@ and @y@ are two 32-bit values to multiply.  On exit, @x@ is
 * the product of the two arguments.  The result is not normalized back to 16
 * bits; the arguments are not expected to be normalized.
 */

#define MUL(x, y) do {							\
  uint32 _mx, _my = (y);						\
  if ((_mx = U16(x)) == 0)						\
    (x) = 1 - _my;							\
  else if (_my == 0)							\
    (x) = 1 - _mx;							\
  else {								\
    _my *= _mx;								\
    _mx = U16(_my); _my >>= 16;						\
    if (_mx < _my)							\
      (x) = _mx - _my + 1;						\
    else								\
      (x) = _mx - _my;							\
  }									\
} while (0)

/* --- @idea_init@ --- *
 *
 * Arguments:	@idea_ctx *k@ = pointer to key block
 *		@const void *buf@ = pointer to key buffer
 *		@size_t sz@ = size of key material
 *
 * Returns:	---
 *
 * Use:		Initializes an IDEA key buffer.  The buffer must be exactly
 *		16 bytes in size, because IDEA is only defined with a key
 *		size of 128 bits.
 */

void idea_init(idea_ctx *k, const void *buf, size_t sz)
{
  assert(((void)"IDEA key must be 128 bits", sz == IDEA_KEYSZ));

  /* --- Unpack the encryption key --- */

  {
    const octet *p = buf;
    uint16 *q = k->e;
    uint32 a = LOAD32(p +  0);
    uint32 b = LOAD32(p +  4);
    uint32 c = LOAD32(p +  8);
    uint32 d = LOAD32(p + 12);
    int i;

    /* --- Main unpacking loop --- */

    for (i = 0; i < 6; i++) {

      /* --- Spit out the next 8 subkeys --- */

      q[0] = U16(a >> 16);
      q[1] = U16(a >>  0);
      q[2] = U16(b >> 16);
      q[3] = U16(b >>  0);
      q[4] = U16(c >> 16);
      q[5] = U16(c >>  0);
      q[6] = U16(d >> 16);
      q[7] = U16(d >>  0);
      q += 8;

      /* --- Rotate and permute the subkeys --- */

      {
	uint32 t = a;
	a = U32((a << 25) | (b >> 7));
	b = U32((b << 25) | (c >> 7));
	c = U32((c << 25) | (d >> 7));
	d = U32((d << 25) | (t >> 7));
      }
    }

    /* --- Write out the tail-enders --- */

    q[0] = U16(a >> 16);
    q[1] = U16(a >>  0);
    q[2] = U16(b >> 16);
    q[3] = U16(b >>  0);
  }

  /* --- Convert this into the decryption key --- */

  {
    uint16 *p = k->e + 52;
    uint16 *q = k->d;
    int i;

    /* --- Translate the main round keys --- */

    for (i = 0; i < 8; i++) {
      p -= 6;
      q[4] = p[0];
      q[5] = p[1];
      q[0] = inv(p[2]);
      q[3] = inv(p[5]);
      if (i) {
	q[1] = 0x10000 - p[4];
	q[2] = 0x10000 - p[3];
      } else {
	q[1] = 0x10000 - p[3];
	q[2] = 0x10000 - p[4];
      }
      q += 6;
    }

    /* --- Translate the tail-enders --- */

    p -= 4;
    q[0] = inv(p[0]);
    q[1] = 0x10000 - p[1];
    q[2] = 0x10000 - p[2];
    q[3] = inv(p[3]);
  }
}

/* --- @ROUND@ --- */

#define MIX(k, a, b, c, d) do {						\
  MUL(a, (k)[0]);							\
  (b) += (k)[1];							\
  (c) += (k)[2];							\
  MUL(d, (k)[3]);							\
} while (0)

#define MA(k, a, b, c, d) do {						\
  unsigned _u = (a) ^ (c);						\
  unsigned _v = (b) ^ (d);						\
  MUL(_u, (k)[4]);							\
  _v += _u;								\
  MUL(_v, (k)[5]);							\
  _u += _v;								\
  (a) ^= _v;								\
  (b) ^= _u;								\
  (c) ^= _v;								\
  (d) ^= _u;								\
} while (0);

#define ROUND(k, a, b, c, d) do {					\
  MIX((k), (a), (b), (c), (d));						\
  MA((k), (a), (b), (c), (d));						\
  (k) += 6;								\
} while (0)

/* --- Encryption --- */

#define EBLK(k, a, b, c, d) do {					\
  unsigned _a = U16(a >> 16);						\
  unsigned _b = U16(a >>  0);						\
  unsigned _c = U16(b >> 16);						\
  unsigned _d = U16(b >>  0);						\
  const uint16 *_k = (k);						\
									\
  ROUND(_k, _a, _b, _c, _d);						\
  ROUND(_k, _a, _c, _b, _d);						\
  ROUND(_k, _a, _b, _c, _d);						\
  ROUND(_k, _a, _c, _b, _d);						\
  ROUND(_k, _a, _b, _c, _d);						\
  ROUND(_k, _a, _c, _b, _d);						\
  ROUND(_k, _a, _b, _c, _d);						\
  ROUND(_k, _a, _c, _b, _d);						\
  MIX  (_k, _a, _c, _b, _d);						\
  (c) = (U16(_a) << 16) | U16(_c);					\
  (d) = (U16(_b) << 16) | U16(_d);					\
} while (0)

#define DBLK(k, a, b) EBLK((k), (a), (b))

/* --- @idea_eblk@, @idea_dblk@ --- *
 *
 * Arguments:	@const idea_ctx *k@ = pointer to a key block
 *		@const uint32 s[2]@ = pointer to source block
 *		@uint32 d[2]@ = pointer to destination block
 *
 * Returns:	---
 *
 * Use:		Low-level block encryption and decryption.
 */

void idea_eblk(const idea_ctx *k, const uint32 *s, uint32 *d)
{
  EBLK(k->e, s[0], s[1], d[0], d[1]);
}

void idea_dblk(const idea_ctx *k, const uint32 *s, uint32 *d)
{
  EBLK(k->d, s[0], s[1], d[0], d[1]);
}

BLKC_TEST(IDEA, idea)

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
d03ab969	1	/* --c--
	2	*
	3	* $Id: idea.c,v 1.1 1999/09/03 08:41:12 mdw Exp $
	4	*
	5	* Implementation of the IDEA cipher
	6	*
	7	* (c) 1999 Straylight/Edgeware
	8	*/
	9
	10	/----- Licensing notice --------------------------------------------------
	11	*
	12	* This file is part of Catacomb.
	13	*
	14	* Catacomb is free software; you can redistribute it and/or modify
	15	* it under the terms of the GNU Library General Public License as
	16	* published by the Free Software Foundation; either version 2 of the
	17	* License, or (at your option) any later version.
	18	*
	19	* Catacomb is distributed in the hope that it will be useful,
	20	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	21	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	22	* GNU Library General Public License for more details.
	23	*
	24	* You should have received a copy of the GNU Library General Public
	25	* License along with Catacomb; if not, write to the Free
	26	* Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
	27	* MA 02111-1307, USA.
	28	*/
	29
	30	/----- Revision history --------------------------------------------------
	31	*
	32	* $Log: idea.c,v $
	33	* Revision 1.1 1999/09/03 08:41:12 mdw
	34	* Initial import.
	35	*
	36	*/
	37
	38	/----- Header files ------------------------------------------------------/
	39
	40	#include <assert.h>
	41	#include <stdio.h>
	42	#include <stdlib.h>
	43	#include <string.h>
	44
	45	#include <mLib/bits.h>
	46
	47	#include "blkc.h"
	48	#include "idea.h"
	49
	50	/----- Main code ---------------------------------------------------------/
	51
	52	/* --- @inv@ --- *
	53	*
	54	* Arguments: @uint16 n@ = number to invert
	55	*
	56	* Returns: Multiplicative inverse of @n@ %$\pmod{2^{16} + 1}$%.
	57	*
	58	* Use: Computes multiplicative inverses. This is handy for the
	59	* decryption key scheduling.
	60	*/
	61
	62	static uint16 inv(uint16 n)
	63	{
	64	uint32 m = 0x10001;
65	uint32 a = 1, b = 0;
66
67	for (;;) {
68	uint32 q, r, t;
69	if (!(r = m % n))
70	break;
71	q = m / n;
72	m = n; n = r;
73	t = a; a = b - q * a; b = t;
74	}
75	if (a > MASK16)
76	a += 1;
77	return (U16(a));
78	}
79
80	/* --- @MUL@ --- *
81	*
82	* Arguments @x@ and @y@ are two 32-bit values to multiply. On exit, @x@ is
83	* the product of the two arguments. The result is not normalized back to 16
84	* bits; the arguments are not expected to be normalized.
85	*/
86
87	#define MUL(x, y) do { \
88	uint32 _mx, _my = (y); \
89	if ((_mx = U16(x)) == 0) \
90	(x) = 1 - _my; \
91	else if (_my == 0) \
92	(x) = 1 - _mx; \
93	else { \
94	_my *= _mx; \
95	_mx = U16(_my); _my >>= 16; \
96	if (_mx < _my) \
97	(x) = _mx - _my + 1; \
98	else \
99	(x) = _mx - _my; \
100	} \
101	} while (0)
102
103	/* --- @idea_init@ --- *
104	*
105	* Arguments: @idea_ctx *k@ = pointer to key block
106	* @const void *buf@ = pointer to key buffer
107	* @size_t sz@ = size of key material
108	*
109	* Returns: ---
110	*
111	* Use: Initializes an IDEA key buffer. The buffer must be exactly
112	* 16 bytes in size, because IDEA is only defined with a key
113	* size of 128 bits.
114	*/
115
116	void idea_init(idea_ctx k, const void buf, size_t sz)
117	{
118	assert(((void)"IDEA key must be 128 bits", sz == IDEA_KEYSZ));
119
120	/* --- Unpack the encryption key --- */
121
122	{
123	const octet *p = buf;
124	uint16 *q = k->e;
125	uint32 a = LOAD32(p + 0);
126	uint32 b = LOAD32(p + 4);
127	uint32 c = LOAD32(p + 8);
128	uint32 d = LOAD32(p + 12);
129	int i;
130
131	/* --- Main unpacking loop --- */
132
133	for (i = 0; i < 6; i++) {
134
135	/* --- Spit out the next 8 subkeys --- */
136
137	q[0] = U16(a >> 16);
138	q[1] = U16(a >> 0);
139	q[2] = U16(b >> 16);
140	q[3] = U16(b >> 0);
141	q[4] = U16(c >> 16);
142	q[5] = U16(c >> 0);
143	q[6] = U16(d >> 16);
144	q[7] = U16(d >> 0);
145	q += 8;
146
147	/* --- Rotate and permute the subkeys --- */
148
149	{
150	uint32 t = a;
151	a = U32((a << 25) \| (b >> 7));
152	b = U32((b << 25) \| (c >> 7));
153	c = U32((c << 25) \| (d >> 7));
154	d = U32((d << 25) \| (t >> 7));
155	}
156	}
157
158	/* --- Write out the tail-enders --- */
159
160	q[0] = U16(a >> 16);
161	q[1] = U16(a >> 0);
162	q[2] = U16(b >> 16);
163	q[3] = U16(b >> 0);
164	}
165
166	/* --- Convert this into the decryption key --- */
167
168	{
169	uint16 *p = k->e + 52;
170	uint16 *q = k->d;
171	int i;
172
173	/* --- Translate the main round keys --- */
174
175	for (i = 0; i < 8; i++) {
176	p -= 6;
177	q[4] = p[0];
178	q[5] = p[1];
179	q[0] = inv(p[2]);
180	q[3] = inv(p[5]);
181	if (i) {
182	q[1] = 0x10000 - p[4];
183	q[2] = 0x10000 - p[3];
184	} else {
185	q[1] = 0x10000 - p[3];
186	q[2] = 0x10000 - p[4];
187	}
188	q += 6;
189	}
190
191	/* --- Translate the tail-enders --- */
192
193	p -= 4;
194	q[0] = inv(p[0]);
195	q[1] = 0x10000 - p[1];
196	q[2] = 0x10000 - p[2];
197	q[3] = inv(p[3]);
198	}
199	}
200
201	/* --- @ROUND@ --- */
202
203	#define MIX(k, a, b, c, d) do { \
204	MUL(a, (k)[0]); \
205	(b) += (k)[1]; \
206	(c) += (k)[2]; \
207	MUL(d, (k)[3]); \
208	} while (0)
209
210	#define MA(k, a, b, c, d) do { \
211	unsigned _u = (a) ^ (c); \
212	unsigned _v = (b) ^ (d); \
213	MUL(_u, (k)[4]); \
214	_v += _u; \
215	MUL(_v, (k)[5]); \
216	_u += _v; \
217	(a) ^= _v; \
218	(b) ^= _u; \
219	(c) ^= _v; \
220	(d) ^= _u; \
221	} while (0);
222
223	#define ROUND(k, a, b, c, d) do { \
224	MIX((k), (a), (b), (c), (d)); \
225	MA((k), (a), (b), (c), (d)); \
226	(k) += 6; \
227	} while (0)
228
229	/* --- Encryption --- */
230
231	#define EBLK(k, a, b, c, d) do { \
232	unsigned _a = U16(a >> 16); \
233	unsigned _b = U16(a >> 0); \
234	unsigned _c = U16(b >> 16); \
235	unsigned _d = U16(b >> 0); \
236	const uint16 *_k = (k); \
237	\
238	ROUND(_k, _a, _b, _c, _d); \
239	ROUND(_k, _a, _c, _b, _d); \
240	ROUND(_k, _a, _b, _c, _d); \
241	ROUND(_k, _a, _c, _b, _d); \
242	ROUND(_k, _a, _b, _c, _d); \
243	ROUND(_k, _a, _c, _b, _d); \
244	ROUND(_k, _a, _b, _c, _d); \
245	ROUND(_k, _a, _c, _b, _d); \
246	MIX (_k, _a, _c, _b, _d); \
247	(c) = (U16(_a) << 16) \| U16(_c); \
248	(d) = (U16(_b) << 16) \| U16(_d); \
249	} while (0)
250
251	#define DBLK(k, a, b) EBLK((k), (a), (b))
252
253	/* --- @idea_eblk@, @idea_dblk@ --- *
254	*
255	* Arguments: @const idea_ctx *k@ = pointer to a key block
256	* @const uint32 s[2]@ = pointer to source block
257	* @uint32 d[2]@ = pointer to destination block
258	*
259	* Returns: ---
260	*
261	* Use: Low-level block encryption and decryption.
262	*/
263
264	void idea_eblk(const idea_ctx k, const uint32 s, uint32 *d)
265	{
266	EBLK(k->e, s[0], s[1], d[0], d[1]);
267	}
268
269	void idea_dblk(const idea_ctx k, const uint32 s, uint32 *d)
270	{
271	EBLK(k->d, s[0], s[1], d[0], d[1]);
272	}
273
274	BLKC_TEST(IDEA, idea)
275
276	/----- That's all, folks -------------------------------------------------/