projects / u / mdw / putty / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Single-DES encryption, patch courtesy of Murphy Lam
[u/mdw/putty] / sshdes.c
1 #include <assert.h>
2 #include "ssh.h"
3
4 /*
5
6 DES implementation; 1995 Tatu Ylonen <ylo@cs.hut.fi>
7
8 This implementation is derived from libdes-3.06, which is copyright
9 (c) 1993 Eric Young, and distributed under the GNU GPL or the ARTISTIC licence
10 (at the user's option). The original distribution can be found e.g. from
11 ftp://ftp.dsi.unimi.it/pub/security/crypt/libdes/libdes-3.06.tar.gz.
12
13 This implementation is distributed under the same terms. See
14 libdes-README, libdes-ARTISTIC, and libdes-COPYING for more
15 information.
16
17 */
18
19 typedef struct
20 {
21 word32 key_schedule[32];
22 } DESContext;
23
24 /* Sets the des key for the context. Initializes the context. The least
25 significant bit of each byte of the key is ignored as parity. */
26 static void des_set_key(unsigned char *key, DESContext *ks);
27
28 /* Encrypts 32 bits in l,r, and stores the result in output[0] and output[1].
29 Performs encryption if encrypt is non-zero, and decryption if it is zero.
30 The key context must have been initialized previously with des_set_key. */
31 static void des_encrypt(word32 l, word32 r, word32 *output, DESContext *ks,
32 int encrypt);
33
34 /* Encrypts len bytes from src to dest in CBC modes. Len must be a multiple
35 of 8. iv will be modified at end to a value suitable for continuing
36 encryption. */
37 static void des_cbc_encrypt(DESContext *ks, unsigned char *iv, unsigned char *dest,
38 const unsigned char *src, unsigned int len);
39
40 /* Decrypts len bytes from src to dest in CBC modes. Len must be a multiple
41 of 8. iv will be modified at end to a value suitable for continuing
42 decryption. */
43 static void des_cbc_decrypt(DESContext *ks, unsigned char *iv, unsigned char *dest,
44 const unsigned char *src, unsigned int len);
45
46 /* Encrypts in CBC mode using triple-DES. */
47 static void des_3cbc_encrypt(DESContext *ks1, unsigned char *iv1,
48 DESContext *ks2, unsigned char *iv2,
49 DESContext *ks3, unsigned char *iv3,
50 unsigned char *dest, const unsigned char *src,
51 unsigned int len);
52
53 /* Decrypts in CBC mode using triple-DES. */
54 static void des_3cbc_decrypt(DESContext *ks1, unsigned char *iv1,
55 DESContext *ks2, unsigned char *iv2,
56 DESContext *ks3, unsigned char *iv3,
57 unsigned char *dest, const unsigned char *src,
58 unsigned int len);
59
60 #define GET_32BIT_LSB_FIRST(cp) \
61 (((unsigned long)(unsigned char)(cp)[0]) | \
62 ((unsigned long)(unsigned char)(cp)[1] << 8) | \
63 ((unsigned long)(unsigned char)(cp)[2] << 16) | \
64 ((unsigned long)(unsigned char)(cp)[3] << 24))
65
66 #define PUT_32BIT_LSB_FIRST(cp, value) do { \
67 (cp)[0] = (value); \
68 (cp)[1] = (value) >> 8; \
69 (cp)[2] = (value) >> 16; \
70 (cp)[3] = (value) >> 24; } while (0)
71
72 /*
73
74 DES implementation; 1995 Tatu Ylonen <ylo@cs.hut.fi>
75
76 This implementation is derived from libdes-3.06, which is copyright
77 (c) 1993 Eric Young, and distributed under the GNU GPL or the ARTISTIC licence
78 (at the user's option). The original distribution can be found e.g. from
79 ftp://ftp.dsi.unimi.it/pub/security/crypt/libdes/libdes-3.06.tar.gz.
80
81 This implementation is distributed under the same terms. See
82 libdes-README, libdes-ARTISTIC, and libdes-COPYING for more
83 information.
84
85 A description of the DES algorithm can be found in every modern book on
86 cryptography and data security, including the following:
87
88 Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1994.
89
90 Jennifer Seberry and Josed Pieprzyk: Cryptography: An Introduction to
91 Computer Security. Prentice-Hall, 1989.
92
93 Man Young Rhee: Cryptography and Secure Data Communications. McGraw-Hill,
94 1994.
95
96 */
97
98 /* Table for key generation. This used to be in sk.h. */
99 /* Copyright (C) 1993 Eric Young - see README for more details */
100 static const word32 des_skb[8][64]={
101 /* for C bits (numbered as per FIPS 46) 1 2 3 4 5 6 */
102 { 0x00000000,0x00000010,0x20000000,0x20000010,
103 0x00010000,0x00010010,0x20010000,0x20010010,
104 0x00000800,0x00000810,0x20000800,0x20000810,
105 0x00010800,0x00010810,0x20010800,0x20010810,
106 0x00000020,0x00000030,0x20000020,0x20000030,
107 0x00010020,0x00010030,0x20010020,0x20010030,
108 0x00000820,0x00000830,0x20000820,0x20000830,
109 0x00010820,0x00010830,0x20010820,0x20010830,
110 0x00080000,0x00080010,0x20080000,0x20080010,
111 0x00090000,0x00090010,0x20090000,0x20090010,
112 0x00080800,0x00080810,0x20080800,0x20080810,
113 0x00090800,0x00090810,0x20090800,0x20090810,
114 0x00080020,0x00080030,0x20080020,0x20080030,
115 0x00090020,0x00090030,0x20090020,0x20090030,
116 0x00080820,0x00080830,0x20080820,0x20080830,
117 0x00090820,0x00090830,0x20090820,0x20090830 },
118 /* for C bits (numbered as per FIPS 46) 7 8 10 11 12 13 */
119 { 0x00000000,0x02000000,0x00002000,0x02002000,
120 0x00200000,0x02200000,0x00202000,0x02202000,
121 0x00000004,0x02000004,0x00002004,0x02002004,
122 0x00200004,0x02200004,0x00202004,0x02202004,
123 0x00000400,0x02000400,0x00002400,0x02002400,
124 0x00200400,0x02200400,0x00202400,0x02202400,
125 0x00000404,0x02000404,0x00002404,0x02002404,
126 0x00200404,0x02200404,0x00202404,0x02202404,
127 0x10000000,0x12000000,0x10002000,0x12002000,
128 0x10200000,0x12200000,0x10202000,0x12202000,
129 0x10000004,0x12000004,0x10002004,0x12002004,
130 0x10200004,0x12200004,0x10202004,0x12202004,
131 0x10000400,0x12000400,0x10002400,0x12002400,
132 0x10200400,0x12200400,0x10202400,0x12202400,
133 0x10000404,0x12000404,0x10002404,0x12002404,
134 0x10200404,0x12200404,0x10202404,0x12202404 },
135 /* for C bits (numbered as per FIPS 46) 14 15 16 17 19 20 */
136 { 0x00000000,0x00000001,0x00040000,0x00040001,
137 0x01000000,0x01000001,0x01040000,0x01040001,
138 0x00000002,0x00000003,0x00040002,0x00040003,
139 0x01000002,0x01000003,0x01040002,0x01040003,
140 0x00000200,0x00000201,0x00040200,0x00040201,
141 0x01000200,0x01000201,0x01040200,0x01040201,
142 0x00000202,0x00000203,0x00040202,0x00040203,
143 0x01000202,0x01000203,0x01040202,0x01040203,
144 0x08000000,0x08000001,0x08040000,0x08040001,
145 0x09000000,0x09000001,0x09040000,0x09040001,
146 0x08000002,0x08000003,0x08040002,0x08040003,
147 0x09000002,0x09000003,0x09040002,0x09040003,
148 0x08000200,0x08000201,0x08040200,0x08040201,
149 0x09000200,0x09000201,0x09040200,0x09040201,
150 0x08000202,0x08000203,0x08040202,0x08040203,
151 0x09000202,0x09000203,0x09040202,0x09040203 },
152 /* for C bits (numbered as per FIPS 46) 21 23 24 26 27 28 */
153 { 0x00000000,0x00100000,0x00000100,0x00100100,
154 0x00000008,0x00100008,0x00000108,0x00100108,
155 0x00001000,0x00101000,0x00001100,0x00101100,
156 0x00001008,0x00101008,0x00001108,0x00101108,
157 0x04000000,0x04100000,0x04000100,0x04100100,
158 0x04000008,0x04100008,0x04000108,0x04100108,
159 0x04001000,0x04101000,0x04001100,0x04101100,
160 0x04001008,0x04101008,0x04001108,0x04101108,
161 0x00020000,0x00120000,0x00020100,0x00120100,
162 0x00020008,0x00120008,0x00020108,0x00120108,
163 0x00021000,0x00121000,0x00021100,0x00121100,
164 0x00021008,0x00121008,0x00021108,0x00121108,
165 0x04020000,0x04120000,0x04020100,0x04120100,
166 0x04020008,0x04120008,0x04020108,0x04120108,
167 0x04021000,0x04121000,0x04021100,0x04121100,
168 0x04021008,0x04121008,0x04021108,0x04121108 },
169 /* for D bits (numbered as per FIPS 46) 1 2 3 4 5 6 */
170 { 0x00000000,0x10000000,0x00010000,0x10010000,
171 0x00000004,0x10000004,0x00010004,0x10010004,
172 0x20000000,0x30000000,0x20010000,0x30010000,
173 0x20000004,0x30000004,0x20010004,0x30010004,
174 0x00100000,0x10100000,0x00110000,0x10110000,
175 0x00100004,0x10100004,0x00110004,0x10110004,
176 0x20100000,0x30100000,0x20110000,0x30110000,
177 0x20100004,0x30100004,0x20110004,0x30110004,
178 0x00001000,0x10001000,0x00011000,0x10011000,
179 0x00001004,0x10001004,0x00011004,0x10011004,
180 0x20001000,0x30001000,0x20011000,0x30011000,
181 0x20001004,0x30001004,0x20011004,0x30011004,
182 0x00101000,0x10101000,0x00111000,0x10111000,
183 0x00101004,0x10101004,0x00111004,0x10111004,
184 0x20101000,0x30101000,0x20111000,0x30111000,
185 0x20101004,0x30101004,0x20111004,0x30111004 },
186 /* for D bits (numbered as per FIPS 46) 8 9 11 12 13 14 */
187 { 0x00000000,0x08000000,0x00000008,0x08000008,
188 0x00000400,0x08000400,0x00000408,0x08000408,
189 0x00020000,0x08020000,0x00020008,0x08020008,
190 0x00020400,0x08020400,0x00020408,0x08020408,
191 0x00000001,0x08000001,0x00000009,0x08000009,
192 0x00000401,0x08000401,0x00000409,0x08000409,
193 0x00020001,0x08020001,0x00020009,0x08020009,
194 0x00020401,0x08020401,0x00020409,0x08020409,
195 0x02000000,0x0A000000,0x02000008,0x0A000008,
196 0x02000400,0x0A000400,0x02000408,0x0A000408,
197 0x02020000,0x0A020000,0x02020008,0x0A020008,
198 0x02020400,0x0A020400,0x02020408,0x0A020408,
199 0x02000001,0x0A000001,0x02000009,0x0A000009,
200 0x02000401,0x0A000401,0x02000409,0x0A000409,
201 0x02020001,0x0A020001,0x02020009,0x0A020009,
202 0x02020401,0x0A020401,0x02020409,0x0A020409 },
203 /* for D bits (numbered as per FIPS 46) 16 17 18 19 20 21 */
204 { 0x00000000,0x00000100,0x00080000,0x00080100,
205 0x01000000,0x01000100,0x01080000,0x01080100,
206 0x00000010,0x00000110,0x00080010,0x00080110,
207 0x01000010,0x01000110,0x01080010,0x01080110,
208 0x00200000,0x00200100,0x00280000,0x00280100,
209 0x01200000,0x01200100,0x01280000,0x01280100,
210 0x00200010,0x00200110,0x00280010,0x00280110,
211 0x01200010,0x01200110,0x01280010,0x01280110,
212 0x00000200,0x00000300,0x00080200,0x00080300,
213 0x01000200,0x01000300,0x01080200,0x01080300,
214 0x00000210,0x00000310,0x00080210,0x00080310,
215 0x01000210,0x01000310,0x01080210,0x01080310,
216 0x00200200,0x00200300,0x00280200,0x00280300,
217 0x01200200,0x01200300,0x01280200,0x01280300,
218 0x00200210,0x00200310,0x00280210,0x00280310,
219 0x01200210,0x01200310,0x01280210,0x01280310 },
220 /* for D bits (numbered as per FIPS 46) 22 23 24 25 27 28 */
221 { 0x00000000,0x04000000,0x00040000,0x04040000,
222 0x00000002,0x04000002,0x00040002,0x04040002,
223 0x00002000,0x04002000,0x00042000,0x04042000,
224 0x00002002,0x04002002,0x00042002,0x04042002,
225 0x00000020,0x04000020,0x00040020,0x04040020,
226 0x00000022,0x04000022,0x00040022,0x04040022,
227 0x00002020,0x04002020,0x00042020,0x04042020,
228 0x00002022,0x04002022,0x00042022,0x04042022,
229 0x00000800,0x04000800,0x00040800,0x04040800,
230 0x00000802,0x04000802,0x00040802,0x04040802,
231 0x00002800,0x04002800,0x00042800,0x04042800,
232 0x00002802,0x04002802,0x00042802,0x04042802,
233 0x00000820,0x04000820,0x00040820,0x04040820,
234 0x00000822,0x04000822,0x00040822,0x04040822,
235 0x00002820,0x04002820,0x00042820,0x04042820,
236 0x00002822,0x04002822,0x00042822,0x04042822 }
237 };
238
239 /* Tables used for executing des. This used to be in spr.h. */
240 /* Copyright (C) 1993 Eric Young - see README for more details */
241 static const word32 des_SPtrans[8][64]={
242 /* nibble 0 */
243 { 0x00820200, 0x00020000, 0x80800000, 0x80820200,
244 0x00800000, 0x80020200, 0x80020000, 0x80800000,
245 0x80020200, 0x00820200, 0x00820000, 0x80000200,
246 0x80800200, 0x00800000, 0x00000000, 0x80020000,
247 0x00020000, 0x80000000, 0x00800200, 0x00020200,
248 0x80820200, 0x00820000, 0x80000200, 0x00800200,
249 0x80000000, 0x00000200, 0x00020200, 0x80820000,
250 0x00000200, 0x80800200, 0x80820000, 0x00000000,
251 0x00000000, 0x80820200, 0x00800200, 0x80020000,
252 0x00820200, 0x00020000, 0x80000200, 0x00800200,
253 0x80820000, 0x00000200, 0x00020200, 0x80800000,
254 0x80020200, 0x80000000, 0x80800000, 0x00820000,
255 0x80820200, 0x00020200, 0x00820000, 0x80800200,
256 0x00800000, 0x80000200, 0x80020000, 0x00000000,
257 0x00020000, 0x00800000, 0x80800200, 0x00820200,
258 0x80000000, 0x80820000, 0x00000200, 0x80020200 },
259
260 /* nibble 1 */
261 { 0x10042004, 0x00000000, 0x00042000, 0x10040000,
262 0x10000004, 0x00002004, 0x10002000, 0x00042000,
263 0x00002000, 0x10040004, 0x00000004, 0x10002000,
264 0x00040004, 0x10042000, 0x10040000, 0x00000004,
265 0x00040000, 0x10002004, 0x10040004, 0x00002000,
266 0x00042004, 0x10000000, 0x00000000, 0x00040004,
267 0x10002004, 0x00042004, 0x10042000, 0x10000004,
268 0x10000000, 0x00040000, 0x00002004, 0x10042004,
269 0x00040004, 0x10042000, 0x10002000, 0x00042004,
270 0x10042004, 0x00040004, 0x10000004, 0x00000000,
271 0x10000000, 0x00002004, 0x00040000, 0x10040004,
272 0x00002000, 0x10000000, 0x00042004, 0x10002004,
273 0x10042000, 0x00002000, 0x00000000, 0x10000004,
274 0x00000004, 0x10042004, 0x00042000, 0x10040000,
275 0x10040004, 0x00040000, 0x00002004, 0x10002000,
276 0x10002004, 0x00000004, 0x10040000, 0x00042000 },
277
278 /* nibble 2 */
279 { 0x41000000, 0x01010040, 0x00000040, 0x41000040,
280 0x40010000, 0x01000000, 0x41000040, 0x00010040,
281 0x01000040, 0x00010000, 0x01010000, 0x40000000,
282 0x41010040, 0x40000040, 0x40000000, 0x41010000,
283 0x00000000, 0x40010000, 0x01010040, 0x00000040,
284 0x40000040, 0x41010040, 0x00010000, 0x41000000,
285 0x41010000, 0x01000040, 0x40010040, 0x01010000,
286 0x00010040, 0x00000000, 0x01000000, 0x40010040,
287 0x01010040, 0x00000040, 0x40000000, 0x00010000,
288 0x40000040, 0x40010000, 0x01010000, 0x41000040,
289 0x00000000, 0x01010040, 0x00010040, 0x41010000,
290 0x40010000, 0x01000000, 0x41010040, 0x40000000,
291 0x40010040, 0x41000000, 0x01000000, 0x41010040,
292 0x00010000, 0x01000040, 0x41000040, 0x00010040,
293 0x01000040, 0x00000000, 0x41010000, 0x40000040,
294 0x41000000, 0x40010040, 0x00000040, 0x01010000 },
295
296 /* nibble 3 */
297 { 0x00100402, 0x04000400, 0x00000002, 0x04100402,
298 0x00000000, 0x04100000, 0x04000402, 0x00100002,
299 0x04100400, 0x04000002, 0x04000000, 0x00000402,
300 0x04000002, 0x00100402, 0x00100000, 0x04000000,
301 0x04100002, 0x00100400, 0x00000400, 0x00000002,
302 0x00100400, 0x04000402, 0x04100000, 0x00000400,
303 0x00000402, 0x00000000, 0x00100002, 0x04100400,
304 0x04000400, 0x04100002, 0x04100402, 0x00100000,
305 0x04100002, 0x00000402, 0x00100000, 0x04000002,
306 0x00100400, 0x04000400, 0x00000002, 0x04100000,
307 0x04000402, 0x00000000, 0x00000400, 0x00100002,
308 0x00000000, 0x04100002, 0x04100400, 0x00000400,
309 0x04000000, 0x04100402, 0x00100402, 0x00100000,
310 0x04100402, 0x00000002, 0x04000400, 0x00100402,
311 0x00100002, 0x00100400, 0x04100000, 0x04000402,
312 0x00000402, 0x04000000, 0x04000002, 0x04100400 },
313
314 /* nibble 4 */
315 { 0x02000000, 0x00004000, 0x00000100, 0x02004108,
316 0x02004008, 0x02000100, 0x00004108, 0x02004000,
317 0x00004000, 0x00000008, 0x02000008, 0x00004100,
318 0x02000108, 0x02004008, 0x02004100, 0x00000000,
319 0x00004100, 0x02000000, 0x00004008, 0x00000108,
320 0x02000100, 0x00004108, 0x00000000, 0x02000008,
321 0x00000008, 0x02000108, 0x02004108, 0x00004008,
322 0x02004000, 0x00000100, 0x00000108, 0x02004100,
323 0x02004100, 0x02000108, 0x00004008, 0x02004000,
324 0x00004000, 0x00000008, 0x02000008, 0x02000100,
325 0x02000000, 0x00004100, 0x02004108, 0x00000000,
326 0x00004108, 0x02000000, 0x00000100, 0x00004008,
327 0x02000108, 0x00000100, 0x00000000, 0x02004108,
328 0x02004008, 0x02004100, 0x00000108, 0x00004000,
329 0x00004100, 0x02004008, 0x02000100, 0x00000108,
330 0x00000008, 0x00004108, 0x02004000, 0x02000008 },
331
332 /* nibble 5 */
333 { 0x20000010, 0x00080010, 0x00000000, 0x20080800,
334 0x00080010, 0x00000800, 0x20000810, 0x00080000,
335 0x00000810, 0x20080810, 0x00080800, 0x20000000,
336 0x20000800, 0x20000010, 0x20080000, 0x00080810,
337 0x00080000, 0x20000810, 0x20080010, 0x00000000,
338 0x00000800, 0x00000010, 0x20080800, 0x20080010,
339 0x20080810, 0x20080000, 0x20000000, 0x00000810,
340 0x00000010, 0x00080800, 0x00080810, 0x20000800,
341 0x00000810, 0x20000000, 0x20000800, 0x00080810,
342 0x20080800, 0x00080010, 0x00000000, 0x20000800,
343 0x20000000, 0x00000800, 0x20080010, 0x00080000,
344 0x00080010, 0x20080810, 0x00080800, 0x00000010,
345 0x20080810, 0x00080800, 0x00080000, 0x20000810,
346 0x20000010, 0x20080000, 0x00080810, 0x00000000,
347 0x00000800, 0x20000010, 0x20000810, 0x20080800,
348 0x20080000, 0x00000810, 0x00000010, 0x20080010 },
349
350 /* nibble 6 */
351 { 0x00001000, 0x00000080, 0x00400080, 0x00400001,
352 0x00401081, 0x00001001, 0x00001080, 0x00000000,
353 0x00400000, 0x00400081, 0x00000081, 0x00401000,
354 0x00000001, 0x00401080, 0x00401000, 0x00000081,
355 0x00400081, 0x00001000, 0x00001001, 0x00401081,
356 0x00000000, 0x00400080, 0x00400001, 0x00001080,
357 0x00401001, 0x00001081, 0x00401080, 0x00000001,
358 0x00001081, 0x00401001, 0x00000080, 0x00400000,
359 0x00001081, 0x00401000, 0x00401001, 0x00000081,
360 0x00001000, 0x00000080, 0x00400000, 0x00401001,
361 0x00400081, 0x00001081, 0x00001080, 0x00000000,
362 0x00000080, 0x00400001, 0x00000001, 0x00400080,
363 0x00000000, 0x00400081, 0x00400080, 0x00001080,
364 0x00000081, 0x00001000, 0x00401081, 0x00400000,
365 0x00401080, 0x00000001, 0x00001001, 0x00401081,
366 0x00400001, 0x00401080, 0x00401000, 0x00001001 },
367
368 /* nibble 7 */
369 { 0x08200020, 0x08208000, 0x00008020, 0x00000000,
370 0x08008000, 0x00200020, 0x08200000, 0x08208020,
371 0x00000020, 0x08000000, 0x00208000, 0x00008020,
372 0x00208020, 0x08008020, 0x08000020, 0x08200000,
373 0x00008000, 0x00208020, 0x00200020, 0x08008000,
374 0x08208020, 0x08000020, 0x00000000, 0x00208000,
375 0x08000000, 0x00200000, 0x08008020, 0x08200020,
376 0x00200000, 0x00008000, 0x08208000, 0x00000020,
377 0x00200000, 0x00008000, 0x08000020, 0x08208020,
378 0x00008020, 0x08000000, 0x00000000, 0x00208000,
379 0x08200020, 0x08008020, 0x08008000, 0x00200020,
380 0x08208000, 0x00000020, 0x00200020, 0x08008000,
381 0x08208020, 0x00200000, 0x08200000, 0x08000020,
382 0x00208000, 0x00008020, 0x08008020, 0x08200000,
383 0x00000020, 0x08208000, 0x00208020, 0x00000000,
384 0x08000000, 0x08200020, 0x00008000, 0x00208020 }};
385
386 /* Some stuff that used to be in des_locl.h. Heavily modified. */
387 /* IP and FP
388 * The problem is more of a geometric problem that random bit fiddling.
389 0 1 2 3 4 5 6 7 62 54 46 38 30 22 14 6
390 8 9 10 11 12 13 14 15 60 52 44 36 28 20 12 4
391 16 17 18 19 20 21 22 23 58 50 42 34 26 18 10 2
392 24 25 26 27 28 29 30 31 to 56 48 40 32 24 16 8 0
393
394 32 33 34 35 36 37 38 39 63 55 47 39 31 23 15 7
395 40 41 42 43 44 45 46 47 61 53 45 37 29 21 13 5
396 48 49 50 51 52 53 54 55 59 51 43 35 27 19 11 3
397 56 57 58 59 60 61 62 63 57 49 41 33 25 17 9 1
398
399 The output has been subject to swaps of the form
400 0 1 -> 3 1 but the odd and even bits have been put into
401 2 3 2 0
402 different words. The main trick is to remember that
403 t=((l>>size)^r)&(mask);
404 r^=t;
405 l^=(t<<size);
406 can be used to swap and move bits between words.
407
408 So l = 0 1 2 3 r = 16 17 18 19
409 4 5 6 7 20 21 22 23
410 8 9 10 11 24 25 26 27
411 12 13 14 15 28 29 30 31
412 becomes (for size == 2 and mask == 0x3333)
413 t = 2^16 3^17 -- -- l = 0 1 16 17 r = 2 3 18 19
414 6^20 7^21 -- -- 4 5 20 21 6 7 22 23
415 10^24 11^25 -- -- 8 9 24 25 10 11 24 25
416 14^28 15^29 -- -- 12 13 28 29 14 15 28 29
417
418 Thanks for hints from Richard Outerbridge - he told me IP&FP
419 could be done in 15 xor, 10 shifts and 5 ands.
420 When I finally started to think of the problem in 2D
421 I first got ~42 operations without xors. When I remembered
422 how to use xors :-) I got it to its final state.
423 */
424 #define PERM_OP(a,b,t,n,m) ((t)=((((a)>>(n))^(b))&(m)),\
425 (b)^=(t),\
426 (a)^=((t)<<(n)))
427
428 #define IP(l,r,t) \
429 PERM_OP(r,l,t, 4,0x0f0f0f0f); \
430 PERM_OP(l,r,t,16,0x0000ffff); \
431 PERM_OP(r,l,t, 2,0x33333333); \
432 PERM_OP(l,r,t, 8,0x00ff00ff); \
433 PERM_OP(r,l,t, 1,0x55555555);
434
435 #define FP(l,r,t) \
436 PERM_OP(l,r,t, 1,0x55555555); \
437 PERM_OP(r,l,t, 8,0x00ff00ff); \
438 PERM_OP(l,r,t, 2,0x33333333); \
439 PERM_OP(r,l,t,16,0x0000ffff); \
440 PERM_OP(l,r,t, 4,0x0f0f0f0f);
441
442 #define D_ENCRYPT(L,R,S) \
443 u=(R^s[S ]); \
444 t=R^s[S+1]; \
445 t=((t>>4)+(t<<28)); \
446 L^= des_SPtrans[1][(t )&0x3f]| \
447 des_SPtrans[3][(t>> 8)&0x3f]| \
448 des_SPtrans[5][(t>>16)&0x3f]| \
449 des_SPtrans[7][(t>>24)&0x3f]| \
450 des_SPtrans[0][(u )&0x3f]| \
451 des_SPtrans[2][(u>> 8)&0x3f]| \
452 des_SPtrans[4][(u>>16)&0x3f]| \
453 des_SPtrans[6][(u>>24)&0x3f];
454
455 /* This part is based on code that used to be in ecb_enc.c. */
456 /* Copyright (C) 1993 Eric Young - see README for more details */
457
458 static void des_encrypt(word32 l, word32 r, word32 *output, DESContext *ks,
459 int encrypt)
460 {
461 register word32 t,u;
462 register int i;
463 register word32 *s;
464
465 s = ks->key_schedule;
466
467 IP(l,r,t);
468 /* Things have been modified so that the initial rotate is
469 * done outside the loop. This required the
470 * des_SPtrans values in sp.h to be rotated 1 bit to the right.
471 * One perl script later and things have a 5% speed up on a sparc2.
472 * Thanks to Richard Outerbridge <71755.204@CompuServe.COM>
473 * for pointing this out. */
474 t=(r<<1)|(r>>31);
475 r=(l<<1)|(l>>31);
476 l=t;
477
478 /* I don't know if it is worth the effort of loop unrolling the
479 * inner loop */
480 if (encrypt)
481 {
482 for (i=0; i<32; i+=4)
483 {
484 D_ENCRYPT(l,r,i+0); /* 1 */
485 D_ENCRYPT(r,l,i+2); /* 2 */
486 }
487 }
488 else
489 {
490 for (i=30; i>0; i-=4)
491 {
492 D_ENCRYPT(l,r,i-0); /* 16 */
493 D_ENCRYPT(r,l,i-2); /* 15 */
494 }
495 }
496 l=(l>>1)|(l<<31);
497 r=(r>>1)|(r<<31);
498
499 FP(r,l,t);
500 output[0]=l;
501 output[1]=r;
502 }
503
504 /* Code based on set_key.c. */
505 /* Copyright (C) 1993 Eric Young - see README for more details */
506
507 #define HPERM_OP(a,t,n,m) ((t)=((((a)<<(16-(n)))^(a))&(m)),\
508 (a)=(a)^(t)^(t>>(16-(n))))
509
510 static void des_set_key(unsigned char *key, DESContext *ks)
511 {
512 register word32 c, d, t, s, shifts;
513 register int i;
514 register word32 *schedule;
515
516 schedule = ks->key_schedule;
517
518 c = GET_32BIT_LSB_FIRST(key);
519 d = GET_32BIT_LSB_FIRST(key + 4);
520
521 /* I now do it in 47 simple operations :-)
522 * Thanks to John Fletcher (john_fletcher@lccmail.ocf.llnl.gov)
523 * for the inspiration. :-) */
524 PERM_OP(d,c,t,4,0x0f0f0f0f);
525 HPERM_OP(c,t,-2,0xcccc0000);
526 HPERM_OP(d,t,-2,0xcccc0000);
527 PERM_OP(d,c,t,1,0x55555555);
528 PERM_OP(c,d,t,8,0x00ff00ff);
529 PERM_OP(d,c,t,1,0x55555555);
530 d = ((d & 0xff) << 16) | (d & 0xff00) |
531 ((d >> 16) & 0xff) | ((c >> 4) & 0xf000000);
532 c&=0x0fffffff;
533
534 shifts = 0x7efc;
535 for (i=0; i < 16; i++)
536 {
537 if (shifts & 1)
538 { c=((c>>2)|(c<<26)); d=((d>>2)|(d<<26)); }
539 else
540 { c=((c>>1)|(c<<27)); d=((d>>1)|(d<<27)); }
541 shifts >>= 1;
542 c&=0x0fffffff;
543 d&=0x0fffffff;
544
545 /* could be a few less shifts but I am to lazy at this
546 * point in time to investigate */
547
548 s = des_skb[0][ (c )&0x3f ] |
549 des_skb[1][((c>> 6)&0x03)|((c>> 7)&0x3c)] |
550 des_skb[2][((c>>13)&0x0f)|((c>>14)&0x30)] |
551 des_skb[3][((c>>20)&0x01)|((c>>21)&0x06)|((c>>22)&0x38)];
552
553 t = des_skb[4][ (d )&0x3f ] |
554 des_skb[5][((d>> 7)&0x03)|((d>> 8)&0x3c)] |
555 des_skb[6][ (d>>15)&0x3f ] |
556 des_skb[7][((d>>21)&0x0f)|((d>>22)&0x30)];
557
558 /* table contained 0213 4657 */
559 *schedule++ = ((t << 16) | (s & 0xffff));
560 s = ((s >> 16) | (t & 0xffff0000));
561 *schedule++ = (s << 4) | (s >> 28);
562 }
563 }
564
565 static void des_cbc_encrypt(DESContext *ks, unsigned char *iv,
566 unsigned char *dest, const unsigned char *src,
567 unsigned int len)
568 {
569 word32 iv0, iv1, out[2];
570 unsigned int i;
571
572 assert((len & 7) == 0);
573
574 iv0 = GET_32BIT_LSB_FIRST(iv);
575 iv1 = GET_32BIT_LSB_FIRST(iv + 4);
576
577 for (i = 0; i < len; i += 8)
578 {
579 iv0 ^= GET_32BIT_LSB_FIRST(src + i);
580 iv1 ^= GET_32BIT_LSB_FIRST(src + i + 4);
581 des_encrypt(iv0, iv1, out, ks, 1);
582 iv0 = out[0];
583 iv1 = out[1];
584 PUT_32BIT_LSB_FIRST(dest + i, iv0);
585 PUT_32BIT_LSB_FIRST(dest + i + 4, iv1);
586 }
587 PUT_32BIT_LSB_FIRST(iv, iv0);
588 PUT_32BIT_LSB_FIRST(iv + 4, iv1);
589 }
590
591 static void des_cbc_decrypt(DESContext *ks, unsigned char *iv,
592 unsigned char *dest, const unsigned char *src,
593 unsigned int len)
594 {
595 word32 iv0, iv1, d0, d1, out[2];
596 unsigned int i;
597
598 assert((len & 7) == 0);
599
600 iv0 = GET_32BIT_LSB_FIRST(iv);
601 iv1 = GET_32BIT_LSB_FIRST(iv + 4);
602
603 for (i = 0; i < len; i += 8)
604 {
605 d0 = GET_32BIT_LSB_FIRST(src + i);
606 d1 = GET_32BIT_LSB_FIRST(src + i + 4);
607 des_encrypt(d0, d1, out, ks, 0);
608 iv0 ^= out[0];
609 iv1 ^= out[1];
610 PUT_32BIT_LSB_FIRST(dest + i, iv0);
611 PUT_32BIT_LSB_FIRST(dest + i + 4, iv1);
612 iv0 = d0;
613 iv1 = d1;
614 }
615 PUT_32BIT_LSB_FIRST(iv, iv0);
616 PUT_32BIT_LSB_FIRST(iv + 4, iv1);
617 }
618
619 static void des_3cbc_encrypt(DESContext *ks1, unsigned char *iv1,
620 DESContext *ks2, unsigned char *iv2,
621 DESContext *ks3, unsigned char *iv3,
622 unsigned char *dest, const unsigned char *src,
623 unsigned int len)
624 {
625 des_cbc_encrypt(ks1, iv1, dest, src, len);
626 des_cbc_decrypt(ks2, iv2, dest, dest, len);
627 des_cbc_encrypt(ks3, iv3, dest, dest, len);
628 }
629
630 static void des_3cbc_decrypt(DESContext *ks1, unsigned char *iv1,
631 DESContext *ks2, unsigned char *iv2,
632 DESContext *ks3, unsigned char *iv3,
633 unsigned char *dest, const unsigned char *src,
634 unsigned int len)
635 {
636 des_cbc_decrypt(ks3, iv3, dest, src, len);
637 des_cbc_encrypt(ks2, iv2, dest, dest, len);
638 des_cbc_decrypt(ks1, iv1, dest, dest, len);
639 }
640
641 DESContext ekey1, ekey2, ekey3;
642 unsigned char eiv1[8], eiv2[8], eiv3[8];
643
644 DESContext dkey1, dkey2, dkey3;
645 unsigned char div1[8], div2[8], div3[8];
646
647 static void des3_sesskey(unsigned char *key) {
648 des_set_key(key, &ekey1);
649 des_set_key(key+8, &ekey2);
650 des_set_key(key+16, &ekey3);
651 memset(eiv1, 0, sizeof(eiv1));
652 memset(eiv2, 0, sizeof(eiv2));
653 memset(eiv3, 0, sizeof(eiv3));
654 des_set_key(key, &dkey1);
655 des_set_key(key+8, &dkey2);
656 des_set_key(key+16, &dkey3);
657 memset(div1, 0, sizeof(div1));
658 memset(div2, 0, sizeof(div2));
659 memset(div3, 0, sizeof(div3));
660 }
661
662 static void des3_encrypt_blk(unsigned char *blk, int len) {
663 des_3cbc_encrypt(&ekey1, eiv1, &ekey2, eiv2, &ekey3, eiv3, blk, blk, len);
664 }
665
666 static void des3_decrypt_blk(unsigned char *blk, int len) {
667 des_3cbc_decrypt(&dkey1, div1, &dkey2, div2, &dkey3, div3, blk, blk, len);
668 }
669
670 struct ssh_cipher ssh_3des = {
671 des3_sesskey,
672 des3_encrypt_blk,
673 des3_decrypt_blk
674 };
675
676 static void des_sesskey(unsigned char *key) {
677 des_set_key(key, &ekey1);
678 memset(eiv1, 0, sizeof(eiv1));
679 des_set_key(key, &dkey1);
680 memset(div1, 0, sizeof(div1));
681 }
682
683 static void des_encrypt_blk(unsigned char *blk, int len) {
684 des_cbc_encrypt(&ekey1, eiv1, blk, blk, len);
685 }
686
687 static void des_decrypt_blk(unsigned char *blk, int len) {
688 des_cbc_decrypt(&dkey1, div1, blk, blk, len);
689 }
690
691 struct ssh_cipher ssh_des = {
692 des_sesskey,
693 des_encrypt_blk,
694 des_decrypt_blk
695 };
696
697 #ifdef DES_TEST
698
699 void des_encrypt_buf(DESContext *ks, unsigned char *out,
700 const unsigned char *in, int encrypt)
701 {
702 word32 in0, in1, output[0];
703
704 in0 = GET_32BIT_LSB_FIRST(in);
705 in1 = GET_32BIT_LSB_FIRST(in + 4);
706 des_encrypt(in0, in1, output, ks, encrypt);
707 PUT_32BIT_LSB_FIRST(out, output[0]);
708 PUT_32BIT_LSB_FIRST(out + 4, output[1]);
709 }
710
711 int main(int ac, char **av)
712 {
713 FILE *f;
714 char line[1024], *cp;
715 int i, value;
716 unsigned char key[8], data[8], result[8], output[8];
717 DESContext ks;
718
719 while (fgets(line, sizeof(line), stdin))
720 {
721 for (i = 0; i < 8; i++)
722 {
723 if (sscanf(line + 2 * i, "%02x", &value) != 1)
724 {
725 fprintf(stderr, "1st col, i = %d, line: %s", i, line);
726 exit(1);
727 }
728 key[i] = value;
729 }
730 for (i = 0; i < 8; i++)
731 {
732 if (sscanf(line + 2 * i + 17, "%02x", &value) != 1)
733 {
734 fprintf(stderr, "2nd col, i = %d, line: %s", i, line);
735 exit(1);
736 }
737 data[i] = value;
738 }
739 for (i = 0; i < 8; i++)
740 {
741 if (sscanf(line + 2 * i + 2*17, "%02x", &value) != 1)
742 {
743 fprintf(stderr, "3rd col, i = %d, line: %s", i, line);
744 exit(1);
745 }
746 result[i] = value;
747 }
748 des_set_key(key, &ks);
749 des_encrypt_buf(&ks, output, data, 1);
750 if (memcmp(output, result, 8) != 0)
751 fprintf(stderr, "Encrypt failed: %s", line);
752 des_encrypt_buf(&ks, output, result, 0);
753 if (memcmp(output, data, 8) != 0)
754 fprintf(stderr, "Decrypt failed: %s", line);
755 }
756 exit(0);
757 }
758 #endif /* DES_TEST */
759
Local modifications for Simon Tatham's `PuTTY' SSH client and terminal emulator