]> git.cryptolib.org Git - avr-crypto-lib.git/blob - des.c
0ad3361cbd6188a99b06229a6717c52eeb45499c
[avr-crypto-lib.git] / des.c
1 /* des.c */
2 /*
3     This file is part of the This file is part of the AVR-Crypto-Lib.
4     Copyright (C) 2008  Daniel Otte (daniel.otte@rub.de)
5
6     This program is free software: you can redistribute it and/or modify
7     it under the terms of the GNU General Public License as published by
8     the Free Software Foundation, either version 3 of the License, or
9     (at your option) any later version.
10
11     This program is distributed in the hope that it will be useful,
12     but WITHOUT ANY WARRANTY; without even the implied warranty of
13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14     GNU General Public License for more details.
15
16     You should have received a copy of the GNU General Public License
17     along with this program.  If not, see <http://www.gnu.org/licenses/>.
18 */
19 /**
20  * \file     des.c
21  * \author   Daniel Otte
22  * \email    daniel.otte@rub.de
23  * \date     2007-06-16
24  * \brief    DES and EDE-DES implementation
25  * \license      GPLv3 or later
26  * 
27  */
28 #include "config.h"
29 #include "debug.h"
30 #include "uart.h"
31 #include <stdint.h>
32 #include <string.h>
33 #include <util/delay.h>
34 #include <avr/pgmspace.h>
35
36 prog_uint8_t sbox[256]  = {
37   /* S-box 1 */
38   0xE4, 0xD1, 0x2F, 0xB8, 0x3A, 0x6C, 0x59, 0x07,
39   0x0F, 0x74, 0xE2, 0xD1, 0xA6, 0xCB, 0x95, 0x38,
40   0x41, 0xE8, 0xD6, 0x2B, 0xFC, 0x97, 0x3A, 0x50,
41   0xFC, 0x82, 0x49, 0x17, 0x5B, 0x3E, 0xA0, 0x6D,
42   /* S-box 2 */
43   0xF1, 0x8E, 0x6B, 0x34, 0x97, 0x2D, 0xC0, 0x5A,
44   0x3D, 0x47, 0xF2, 0x8E, 0xC0, 0x1A, 0x69, 0xB5,
45   0x0E, 0x7B, 0xA4, 0xD1, 0x58, 0xC6, 0x93, 0x2F,
46   0xD8, 0xA1, 0x3F, 0x42, 0xB6, 0x7C, 0x05, 0xE9,
47   /* S-box 3 */
48   0xA0, 0x9E, 0x63, 0xF5, 0x1D, 0xC7, 0xB4, 0x28,
49   0xD7, 0x09, 0x34, 0x6A, 0x28, 0x5E, 0xCB, 0xF1,
50   0xD6, 0x49, 0x8F, 0x30, 0xB1, 0x2C, 0x5A, 0xE7,
51   0x1A, 0xD0, 0x69, 0x87, 0x4F, 0xE3, 0xB5, 0x2C,
52   /* S-box 4 */
53   0x7D, 0xE3, 0x06, 0x9A, 0x12, 0x85, 0xBC, 0x4F,
54   0xD8, 0xB5, 0x6F, 0x03, 0x47, 0x2C, 0x1A, 0xE9,
55   0xA6, 0x90, 0xCB, 0x7D, 0xF1, 0x3E, 0x52, 0x84,
56   0x3F, 0x06, 0xA1, 0xD8, 0x94, 0x5B, 0xC7, 0x2E,
57   /* S-box 5 */
58   0x2C, 0x41, 0x7A, 0xB6, 0x85, 0x3F, 0xD0, 0xE9,
59   0xEB, 0x2C, 0x47, 0xD1, 0x50, 0xFA, 0x39, 0x86,
60   0x42, 0x1B, 0xAD, 0x78, 0xF9, 0xC5, 0x63, 0x0E,
61   0xB8, 0xC7, 0x1E, 0x2D, 0x6F, 0x09, 0xA4, 0x53,
62   /* S-box 6 */
63   0xC1, 0xAF, 0x92, 0x68, 0x0D, 0x34, 0xE7, 0x5B,
64   0xAF, 0x42, 0x7C, 0x95, 0x61, 0xDE, 0x0B, 0x38,
65   0x9E, 0xF5, 0x28, 0xC3, 0x70, 0x4A, 0x1D, 0xB6,
66   0x43, 0x2C, 0x95, 0xFA, 0xBE, 0x17, 0x60, 0x8D,
67   /* S-box 7 */
68   0x4B, 0x2E, 0xF0, 0x8D, 0x3C, 0x97, 0x5A, 0x61,
69   0xD0, 0xB7, 0x49, 0x1A, 0xE3, 0x5C, 0x2F, 0x86,
70   0x14, 0xBD, 0xC3, 0x7E, 0xAF, 0x68, 0x05, 0x92,
71   0x6B, 0xD8, 0x14, 0xA7, 0x95, 0x0F, 0xE2, 0x3C,
72   /* S-box 8 */
73   0xD2, 0x84, 0x6F, 0xB1, 0xA9, 0x3E, 0x50, 0xC7,
74   0x1F, 0xD8, 0xA3, 0x74, 0xC5, 0x6B, 0x0E, 0x92,
75   0x7B, 0x41, 0x9C, 0xE2, 0x06, 0xAD, 0xF3, 0x58,
76   0x21, 0xE7, 0x4A, 0x8D, 0xFC, 0x90, 0x35, 0x6B
77 };
78
79 prog_uint8_t e_permtab[] ={ 
80          4,  6,                                         /* 4 bytes in 6 bytes out*/
81         32,  1,  2,  3,  4,  5,
82          4,  5,  6,  7,  8,  9,
83          8,  9, 10, 11, 12, 13,
84         12, 13, 14, 15, 16, 17,
85         16, 17, 18, 19, 20, 21,
86         20, 21, 22, 23, 24, 25,
87         24, 25, 26, 27, 28, 29,
88         28, 29, 30, 31, 32,  1
89 };
90
91 prog_uint8_t p_permtab[] ={ 
92          4,  4,                                         /* 32 bit -> 32 bit */
93         16,  7, 20, 21,
94         29, 12, 28, 17,
95          1, 15, 23, 26,
96          5, 18, 31, 10,
97          2,  8, 24, 14,
98         32, 27,  3,  9,
99         19, 13, 30,  6,
100         22, 11,  4, 25
101 };
102
103 prog_uint8_t ip_permtab[] ={ 
104          8,  8,                                         /* 64 bit -> 64 bit */
105         58, 50, 42, 34, 26, 18, 10, 2,
106         60, 52, 44, 36, 28, 20, 12, 4,
107         62, 54, 46, 38, 30, 22, 14, 6,
108         64, 56, 48, 40, 32, 24, 16, 8,
109         57, 49, 41, 33, 25, 17,  9, 1,
110         59, 51, 43, 35, 27, 19, 11, 3,
111         61, 53, 45, 37, 29, 21, 13, 5,
112         63, 55, 47, 39, 31, 23, 15, 7
113 };
114
115 prog_uint8_t inv_ip_permtab[] ={ 
116          8, 8,                                          /* 64 bit -> 64 bit */
117         40, 8, 48, 16, 56, 24, 64, 32,
118         39, 7, 47, 15, 55, 23, 63, 31,
119         38, 6, 46, 14, 54, 22, 62, 30,
120         37, 5, 45, 13, 53, 21, 61, 29,
121         36, 4, 44, 12, 52, 20, 60, 28,
122         35, 3, 43, 11, 51, 19, 59, 27,
123         34, 2, 42, 10, 50, 18, 58, 26,
124         33, 1, 41,  9, 49, 17, 57, 25
125 };
126
127 prog_uint8_t pc1_permtab[] ={ 
128          8,  7,                                         /* 64 bit -> 56 bit*/
129         57, 49, 41, 33, 25, 17,  9,
130          1, 58, 50, 42, 34, 26, 18,
131         10,  2, 59, 51, 43, 35, 27,
132         19, 11,  3, 60, 52, 44, 36,
133         63, 55, 47, 39, 31, 23, 15,
134          7, 62, 54, 46, 38, 30, 22,
135         14,  6, 61, 53, 45, 37, 29,
136         21, 13,  5, 28, 20, 12,  4
137 };
138
139 prog_uint8_t pc2_permtab[] ={ 
140          7,      6,                                     /* 56 bit -> 48 bit */
141         14, 17, 11, 24,  1,  5,
142          3, 28, 15,  6, 21, 10,
143         23, 19, 12,  4, 26,  8,
144         16,  7, 27, 20, 13,  2,
145         41, 52, 31, 37, 47, 55,
146         30, 40, 51, 45, 33, 48,
147         44, 49, 39, 56, 34, 53,
148         46, 42, 50, 36, 29, 32
149 };
150
151 prog_uint8_t splitin6bitword_permtab[] = {
152          8,  8,                                         /* 64 bit -> 64 bit */
153         64, 64,  1,  6,  2,  3,  4,  5, 
154         64, 64,  7, 12,  8,  9, 10, 11, 
155         64, 64, 13, 18, 14, 15, 16, 17, 
156         64, 64, 19, 24, 20, 21, 22, 23, 
157         64, 64, 25, 30, 26, 27, 28, 29, 
158         64, 64, 31, 36, 32, 33, 34, 35, 
159         64, 64, 37, 42, 38, 39, 40, 41, 
160         64, 64, 43, 48, 44, 45, 46, 47 
161 };
162
163 prog_uint8_t shiftkey_permtab[] = {
164          7,  7,                                         /* 56 bit -> 56 bit */
165          2,  3,  4,  5,  6,  7,  8,  9,
166         10, 11, 12, 13, 14, 15, 16, 17,
167         18, 19, 20, 21, 22, 23, 24, 25, 
168         26, 27, 28,  1, 
169         30, 31, 32, 33, 34, 35, 36, 37, 
170         38, 39, 40, 41, 42, 43, 44, 45, 
171         46, 47, 48, 49, 50, 51, 52, 53, 
172         54, 55, 56, 29
173 };
174
175 prog_uint8_t shiftkeyinv_permtab[] = {
176          7,  7,
177         28,  1,  2,  3,  4,  5,  6,  7,
178          8,  9, 10, 11, 12, 13, 14, 15,
179         16, 17, 18, 19, 20, 21, 22, 23,
180         24, 25, 26, 27,
181         56, 29, 30, 31, 32, 33, 34, 35, 
182         36, 37, 38, 39, 40, 41, 42, 43, 
183         44, 45, 46, 47, 48, 49, 50, 51, 
184         52, 53, 54, 55
185 };
186
187 /*
188 1 0
189 1 0
190 2 1
191 2 1
192 2 1
193 2 1
194 2 1
195 2 1
196 ----
197 1 0
198 2 1
199 2 1
200 2 1
201 2 1
202 2 1
203 2 1
204 1 0
205 */
206 #define ROTTABLE      0x7EFC 
207 #define ROTTABLE_INV  0x3F7E
208 /******************************************************************************/
209
210 void permute(prog_uint8_t *ptable, const uint8_t *in, uint8_t *out){
211         uint8_t ib, ob; /* in-bytes and out-bytes */
212         uint8_t byte, bit; /* counter for bit and byte */
213         ib = pgm_read_byte(&(ptable[0]));
214         ob = pgm_read_byte(&(ptable[1]));
215         ptable = &(ptable[2]);
216         for(byte=0; byte<ob; ++byte){
217                 uint8_t x,t=0;
218                 for(bit=0; bit<8; ++bit){
219                         x=pgm_read_byte(&(ptable[byte*8+bit])) -1 ;
220                                 t<<=1;
221                         if((in[x/8]) & (0x80>>(x%8)) ){
222                                 t|=0x01;
223                         }
224                 }
225                 out[byte]=t;
226         }
227 }
228
229 /******************************************************************************/
230
231 void changeendian32(uint32_t * a){
232         *a = (*a & 0x000000FF) << 24 |
233                  (*a & 0x0000FF00) <<  8 |
234                  (*a & 0x00FF0000) >>  8 |
235                  (*a & 0xFF000000) >> 24;
236 }
237
238 /******************************************************************************/
239 static inline
240 void shiftkey(uint8_t *key){
241         uint8_t k[7];
242         memcpy(k, key, 7);
243         permute((prog_uint8_t*)shiftkey_permtab, k, key);       
244 }
245
246 /******************************************************************************/
247 static inline
248 void shiftkey_inv(uint8_t *key){
249         uint8_t k[7];
250         memcpy(k, key, 7);
251         permute((prog_uint8_t*)shiftkeyinv_permtab, k, key);
252         
253 }
254
255 /******************************************************************************/
256 static inline
257 uint64_t splitin6bitwords(uint64_t a){
258         uint64_t ret=0;
259         a &= 0x0000ffffffffffffLL;
260         permute((prog_uint8_t*)splitin6bitword_permtab, (uint8_t*)&a, (uint8_t*)&ret);  
261         return ret;
262 }
263
264 /******************************************************************************/
265
266 static inline
267 uint8_t substitute(uint8_t a, prog_uint8_t * sbp){
268         uint8_t x;      
269         x = pgm_read_byte(&(sbp[a>>1]));
270         x = (a&1)?x&0x0F:x>>4;
271         return x;
272         
273 }
274
275 /******************************************************************************/
276
277 uint32_t des_f(uint32_t r, uint8_t* kr){
278         uint8_t i;
279         uint32_t t=0,ret;
280         uint64_t data;
281         prog_uint8_t *sbp; /* sboxpointer */ 
282         permute((prog_uint8_t*)e_permtab, (uint8_t*)&r, (uint8_t*)&data);
283         for(i=0; i<7; ++i)
284                 ((uint8_t*)&data)[i] ^= kr[i];
285         
286         /* Sbox substitution */
287         data = splitin6bitwords(data);
288         sbp=(prog_uint8_t*)sbox;
289         for(i=0; i<8; ++i){
290                 uint8_t x;
291                 x = substitute(((uint8_t*)&data)[i], sbp);
292                 t<<=4;
293                 t |= x;
294                 sbp += 32;
295         }
296         changeendian32(&t);
297                 
298         permute((prog_uint8_t*)p_permtab,(uint8_t*)&t, (uint8_t*)&ret);
299
300         return ret;
301 }
302
303 /******************************************************************************/
304
305 void des_enc(void* out, const void* in, const void* key){
306 #define R *((uint32_t*)&(data[4]))
307 #define L *((uint32_t*)&(data[0]))
308
309         uint8_t data[8],kr[6],k[7];
310         uint8_t i;
311         
312         permute((prog_uint8_t*)ip_permtab, (uint8_t*)in, data);
313         permute((prog_uint8_t*)pc1_permtab, (uint8_t*)key, k);
314         for(i=0; i<8; ++i){
315                 shiftkey(k);
316                 if(ROTTABLE&((1<<((i<<1)+0))) )
317                         shiftkey(k);
318                 permute((prog_uint8_t*)pc2_permtab, k, kr);
319                 L ^= des_f(R, kr);
320                 
321                 shiftkey(k);
322                 if(ROTTABLE&((1<<((i<<1)+1))) )
323                         shiftkey(k);
324                 permute((prog_uint8_t*)pc2_permtab, k, kr);
325                 R ^= des_f(L, kr);
326
327         }
328         /* L <-> R*/
329         R ^= L;
330         L ^= R;
331         R ^= L;
332         
333         permute((prog_uint8_t*)inv_ip_permtab, data, (uint8_t*)out);
334 }
335
336 /******************************************************************************/
337
338 void des_dec(void* out, const void* in, const uint8_t* key){
339 #define R *((uint32_t*)&(data[4]))
340 #define L *((uint32_t*)&(data[0]))
341
342         uint8_t data[8],kr[6],k[7];
343         int8_t i;
344         
345         permute((prog_uint8_t*)ip_permtab, (uint8_t*)in, data);
346         permute((prog_uint8_t*)pc1_permtab, (uint8_t*)key, k);
347         for(i=7; i>=0; --i){
348                 
349                 permute((prog_uint8_t*)pc2_permtab, k, kr);
350                 L ^= des_f(R, kr);
351                 shiftkey_inv(k);
352                 if(ROTTABLE&((1<<((i<<1)+1))) ){
353                         shiftkey_inv(k);
354                 }
355
356                 permute((prog_uint8_t*)pc2_permtab, k, kr);
357                 R ^= des_f(L, kr);
358                 shiftkey_inv(k);
359                 if(ROTTABLE&((1<<((i<<1)+0))) ){
360                         shiftkey_inv(k);
361                 }
362
363         }
364         /* L <-> R*/
365         R ^= L;
366         L ^= R;
367         R ^= L;
368         
369         permute((prog_uint8_t*)inv_ip_permtab, data, (uint8_t*)out);
370 }
371
372 /******************************************************************************/
373
374 void tdes_enc(void* out, void* in, const void* key){
375         des_enc(out,  in, (uint8_t*)key + 0);
376         des_dec(out, out, (uint8_t*)key + 8);
377         des_enc(out, out, (uint8_t*)key +16);
378 }
379
380 /******************************************************************************/
381
382 void tdes_dec(void* out, void* in, const uint8_t* key){
383         des_dec(out,  in, (uint8_t*)key + 0);
384         des_enc(out, out, (uint8_t*)key + 8);
385         des_dec(out, out, (uint8_t*)key +16);
386 }
387
388 /******************************************************************************/
389
390