1 static char sccsid[] = "@(#)nbs.c 4.1 (Berkeley) 09/12/82";
2
3 # include <stdio.h>
4 /* sccs id variable */
5 static char *nbs_sid = "@(#)nbs.c 1.2";
6
7 /* file nbs.c
8 This file has the necessary procedures to use the NBS algorithm
9 to encrypt and decrypt strings of arbitrary length.
10
11 Basically
12
13 ciphertext = nbsencrypt(cleartext,secretkey,ciphertext);
14
15 yields a string ciphertext from string cleartext using
16 the secret string secretkey.
17 Then
18
19 cleartext = nbsdecrypt(ciphertext,secretkey,cleartext);
20
21 yields the original string cleartext IF the string secretkey
22 is the same for both calls.
23 The third parameter is filled with the result of the call-
24 it must be (11/8)*size(firstarg).
25 The first and third areguments must be different.
26 The cleartext must be ASCII - the top eighth bit is ignored,
27 so binary data won't work.
28 The plaintext is broken into 8 character sections,
29 encrypted, and concatenated separated by $'s to make the ciphertext.
30 The first 8 letter section uses the secretkey, subsequent
31 sections use the cleartext of the previous section as
32 the key.
33 Thus the ciphertext depends on itself, except for
34 the first section, which depends on the key.
35 This means that sections of the ciphertext, except the first,
36 may not stand alone.
37 Only the first 8 characters of the key matter.
38 */
39 char *deblknot(), *deblkclr();
40 char *nbs8decrypt(), *nbs8encrypt();
41 static char E[48];
42 char e[];
nbsencrypt(str,key,result)43 char *nbsencrypt(str,key,result)
44 char *result;
45 char *str, *key; {
46 static char buf[20],oldbuf[20];
47 register int j;
48 result[0] = 0;
49 strcpy(oldbuf,key);
50 while(*str){
51 for(j=0;j<10;j++)buf[j] = 0;
52 for(j=0;j<8 && *str;j++)buf[j] = *str++;
53 strcat(result,nbs8encrypt(buf,oldbuf));
54 strcat(result,"$");
55 strcpy(oldbuf,buf);
56 }
57 return(result);
58 }
nbsdecrypt(cpt,key,result)59 char *nbsdecrypt(cpt,key,result)
60 char *result;
61 char *cpt,*key; {
62 char *s;
63 char c,oldbuf[20];
64 result[0] = 0;
65 strcpy(oldbuf,key);
66 while(*cpt){
67 for(s = cpt;*s && *s != '$';s++);
68 c = *s;
69 *s = 0;
70 strcpy(oldbuf,nbs8decrypt(cpt,oldbuf));
71 strcat(result,oldbuf);
72 if(c == 0)break;
73 cpt = s + 1;
74 }
75 return(result);
76 }
77 /* make key to be sent across the network */
makeuukey(skey,sn,mch)78 makeuukey(skey,sn,mch)
79 char *skey, *sn, mch;
80 {
81 skey[0] = mch;
82 skey[1] = 0;
83 strcat(skey,sn);
84 }
85
86 /* all other calls are private */
87 /*
88 char _sobuf[BUFSIZ];
89 testing(){
90 static char res[BUFSIZ];
91 char *s;
92 char str[BUFSIZ];
93 setbuf(stdout,_sobuf);
94 while(!feof(stdin)){
95 fprintf(stderr,"String:\n");
96 fgets(str,BUFSIZ,stdin);
97 if(feof(stdin))break;
98 strcat(str,"\n");
99 s = nbsencrypt(str,"hellothere",res);
100 fprintf(stderr,"encrypted:\n%s\n",s);
101 fprintf(stderr,"decrypted:\n");
102 printf("%s",nbsdecrypt(s,"hellothere",str));
103 fprintf(stderr,"\n");
104 }
105 }
106 */
107 /*
108 To encrypt:
109 The first level of call splits the input strings into strings
110 no longer than 8 characters, for encryption.
111 Then the encryption of 8 characters breaks all but the top bit
112 of each character into a 64-character block, each character
113 with 1 or 0 corresponding to binary.
114 The key is set likewise.
115 The encrypted form is then converted, 6 bits at a time,
116 into an ASCII string.
117
118 To decrypt:
119 We take the result of the encryption, 6 significant bits
120 per character, and convert it to the block(64-char) fmt.
121 This is decrypted by running the nbs algorithm in reverse,
122 and transformed back into 7bit ASCII.
123
124 The subroutines to do ASCII blocking and deblocking
125 are .....clr and the funny 6-bit code are .....not.
126
127 */
128
nbs8encrypt(str,key)129 char *nbs8encrypt(str,key)
130 char *str, *key; {
131 static char keyblk[100], blk[100];
132 register int i;
133
134 enblkclr(keyblk,key);
135 nbssetkey(keyblk);
136
137 for(i=0;i<48;i++) E[i] = e[i];
138 enblkclr(blk,str);
139 blkencrypt(blk,0); /* forward dir */
140
141 return(deblknot(blk));
142 }
nbs8decrypt(crp,key)143 char *nbs8decrypt(crp,key)
144 char *crp, *key; {
145 static char keyblk[100], blk[100];
146 register int i;
147
148 enblkclr(keyblk,key);
149 nbssetkey(keyblk);
150
151 for(i=0;i<48;i++) E[i] = e[i];
152 enblknot(blk,crp);
153 blkencrypt(blk,1); /* backward dir */
154
155 return(deblkclr(blk));
156 }
enblkclr(blk,str)157 enblkclr(blk,str) /* ignores top bit of chars in string str */
158 char *blk,*str; {
159 register int i,j;
160 char c;
161 for(i=0;i<70;i++)blk[i] = 0;
162 for(i=0; (c= *str) && i<64; str++){
163 for(j=0; j<7; j++, i++)
164 blk[i] = (c>>(6-j)) & 01;
165 i++;
166 }
167 }
deblkclr(blk)168 char *deblkclr(blk)
169 char *blk; {
170 register int i,j;
171 char c;
172 static char iobuf[30];
173 for(i=0; i<10; i++){
174 c = 0;
175 for(j=0; j<7; j++){
176 c <<= 1;
177 c |= blk[8*i+j];
178 }
179 iobuf[i] = c;
180 }
181 iobuf[i] = 0;
182 return(iobuf);
183 }
enblknot(blk,crp)184 enblknot(blk,crp)
185 char *blk;
186 char *crp; {
187 register int i,j;
188 char c;
189 for(i=0;i<70;i++)blk[i] = 0;
190 for(i=0; (c= *crp) && i<64; crp++){
191 if(c>'Z') c -= 6;
192 if(c>'9') c -= 7;
193 c -= '.';
194 for(j=0; j<6; j++, i++)
195 blk[i] = (c>>(5-j)) & 01;
196 }
197 }
deblknot(blk)198 char *deblknot(blk)
199 char *blk; {
200 register int i,j;
201 char c;
202 static char iobuf[30];
203 for(i=0; i<11; i++){
204 c = 0;
205 for(j=0; j<6; j++){
206 c <<= 1;
207 c |= blk[6*i+j];
208 }
209 c += '.';
210 if(c > '9')c += 7;
211 if(c > 'Z')c += 6;
212 iobuf[i] = c;
213 }
214 iobuf[i] = 0;
215 return(iobuf);
216 }
217 /*
218 * This program implements the
219 * Proposed Federal Information Processing
220 * Data Encryption Standard.
221 * See Federal Register, March 17, 1975 (40FR12134)
222 */
223
224 /*
225 * Initial permutation,
226 */
227 static char IP[] = {
228 58,50,42,34,26,18,10, 2,
229 60,52,44,36,28,20,12, 4,
230 62,54,46,38,30,22,14, 6,
231 64,56,48,40,32,24,16, 8,
232 57,49,41,33,25,17, 9, 1,
233 59,51,43,35,27,19,11, 3,
234 61,53,45,37,29,21,13, 5,
235 63,55,47,39,31,23,15, 7,
236 };
237
238 /*
239 * Final permutation, FP = IP^(-1)
240 */
241 static char FP[] = {
242 40, 8,48,16,56,24,64,32,
243 39, 7,47,15,55,23,63,31,
244 38, 6,46,14,54,22,62,30,
245 37, 5,45,13,53,21,61,29,
246 36, 4,44,12,52,20,60,28,
247 35, 3,43,11,51,19,59,27,
248 34, 2,42,10,50,18,58,26,
249 33, 1,41, 9,49,17,57,25,
250 };
251
252 /*
253 * Permuted-choice 1 from the key bits
254 * to yield C and D.
255 * Note that bits 8,16... are left out:
256 * They are intended for a parity check.
257 */
258 static char PC1_C[] = {
259 57,49,41,33,25,17, 9,
260 1,58,50,42,34,26,18,
261 10, 2,59,51,43,35,27,
262 19,11, 3,60,52,44,36,
263 };
264
265 static char PC1_D[] = {
266 63,55,47,39,31,23,15,
267 7,62,54,46,38,30,22,
268 14, 6,61,53,45,37,29,
269 21,13, 5,28,20,12, 4,
270 };
271
272 /*
273 * Sequence of shifts used for the key schedule.
274 */
275 static char shifts[] = {
276 1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1,
277 };
278
279 /*
280 * Permuted-choice 2, to pick out the bits from
281 * the CD array that generate the key schedule.
282 */
283 static char PC2_C[] = {
284 14,17,11,24, 1, 5,
285 3,28,15, 6,21,10,
286 23,19,12, 4,26, 8,
287 16, 7,27,20,13, 2,
288 };
289
290 static char PC2_D[] = {
291 41,52,31,37,47,55,
292 30,40,51,45,33,48,
293 44,49,39,56,34,53,
294 46,42,50,36,29,32,
295 };
296
297 /*
298 * The C and D arrays used to calculate the key schedule.
299 */
300
301 static char C[28];
302 static char D[28];
303 /*
304 * The key schedule.
305 * Generated from the key.
306 */
307 static char KS[16][48];
308
309 /*
310 * Set up the key schedule from the key.
311 */
312
nbssetkey(key)313 nbssetkey(key)
314 char *key;
315 {
316 register i, j, k;
317 int t;
318
319 /*
320 * First, generate C and D by permuting
321 * the key. The low order bit of each
322 * 8-bit char is not used, so C and D are only 28
323 * bits apiece.
324 */
325 for (i=0; i<28; i++) {
326 C[i] = key[PC1_C[i]-1];
327 D[i] = key[PC1_D[i]-1];
328 }
329 /*
330 * To generate Ki, rotate C and D according
331 * to schedule and pick up a permutation
332 * using PC2.
333 */
334 for (i=0; i<16; i++) {
335 /*
336 * rotate.
337 */
338 for (k=0; k<shifts[i]; k++) {
339 t = C[0];
340 for (j=0; j<28-1; j++)
341 C[j] = C[j+1];
342 C[27] = t;
343 t = D[0];
344 for (j=0; j<28-1; j++)
345 D[j] = D[j+1];
346 D[27] = t;
347 }
348 /*
349 * get Ki. Note C and D are concatenated.
350 */
351 for (j=0; j<24; j++) {
352 KS[i][j] = C[PC2_C[j]-1];
353 KS[i][j+24] = D[PC2_D[j]-28-1];
354 }
355 }
356 }
357
358 /*
359 * The E bit-selection table.
360 */
361 static char e[] = {
362 32, 1, 2, 3, 4, 5,
363 4, 5, 6, 7, 8, 9,
364 8, 9,10,11,12,13,
365 12,13,14,15,16,17,
366 16,17,18,19,20,21,
367 20,21,22,23,24,25,
368 24,25,26,27,28,29,
369 28,29,30,31,32, 1,
370 };
371
372 /*
373 * The 8 selection functions.
374 * For some reason, they give a 0-origin
375 * index, unlike everything else.
376 */
377 static char S[8][64] = {
378 14, 4,13, 1, 2,15,11, 8, 3,10, 6,12, 5, 9, 0, 7,
379 0,15, 7, 4,14, 2,13, 1,10, 6,12,11, 9, 5, 3, 8,
380 4, 1,14, 8,13, 6, 2,11,15,12, 9, 7, 3,10, 5, 0,
381 15,12, 8, 2, 4, 9, 1, 7, 5,11, 3,14,10, 0, 6,13,
382
383 15, 1, 8,14, 6,11, 3, 4, 9, 7, 2,13,12, 0, 5,10,
384 3,13, 4, 7,15, 2, 8,14,12, 0, 1,10, 6, 9,11, 5,
385 0,14, 7,11,10, 4,13, 1, 5, 8,12, 6, 9, 3, 2,15,
386 13, 8,10, 1, 3,15, 4, 2,11, 6, 7,12, 0, 5,14, 9,
387
388 10, 0, 9,14, 6, 3,15, 5, 1,13,12, 7,11, 4, 2, 8,
389 13, 7, 0, 9, 3, 4, 6,10, 2, 8, 5,14,12,11,15, 1,
390 13, 6, 4, 9, 8,15, 3, 0,11, 1, 2,12, 5,10,14, 7,
391 1,10,13, 0, 6, 9, 8, 7, 4,15,14, 3,11, 5, 2,12,
392
393 7,13,14, 3, 0, 6, 9,10, 1, 2, 8, 5,11,12, 4,15,
394 13, 8,11, 5, 6,15, 0, 3, 4, 7, 2,12, 1,10,14, 9,
395 10, 6, 9, 0,12,11, 7,13,15, 1, 3,14, 5, 2, 8, 4,
396 3,15, 0, 6,10, 1,13, 8, 9, 4, 5,11,12, 7, 2,14,
397
398 2,12, 4, 1, 7,10,11, 6, 8, 5, 3,15,13, 0,14, 9,
399 14,11, 2,12, 4, 7,13, 1, 5, 0,15,10, 3, 9, 8, 6,
400 4, 2, 1,11,10,13, 7, 8,15, 9,12, 5, 6, 3, 0,14,
401 11, 8,12, 7, 1,14, 2,13, 6,15, 0, 9,10, 4, 5, 3,
402
403 12, 1,10,15, 9, 2, 6, 8, 0,13, 3, 4,14, 7, 5,11,
404 10,15, 4, 2, 7,12, 9, 5, 6, 1,13,14, 0,11, 3, 8,
405 9,14,15, 5, 2, 8,12, 3, 7, 0, 4,10, 1,13,11, 6,
406 4, 3, 2,12, 9, 5,15,10,11,14, 1, 7, 6, 0, 8,13,
407
408 4,11, 2,14,15, 0, 8,13, 3,12, 9, 7, 5,10, 6, 1,
409 13, 0,11, 7, 4, 9, 1,10,14, 3, 5,12, 2,15, 8, 6,
410 1, 4,11,13,12, 3, 7,14,10,15, 6, 8, 0, 5, 9, 2,
411 6,11,13, 8, 1, 4,10, 7, 9, 5, 0,15,14, 2, 3,12,
412
413 13, 2, 8, 4, 6,15,11, 1,10, 9, 3,14, 5, 0,12, 7,
414 1,15,13, 8,10, 3, 7, 4,12, 5, 6,11, 0,14, 9, 2,
415 7,11, 4, 1, 9,12,14, 2, 0, 6,10,13,15, 3, 5, 8,
416 2, 1,14, 7, 4,10, 8,13,15,12, 9, 0, 3, 5, 6,11,
417 };
418
419 /*
420 * P is a permutation on the selected combination
421 * of the current L and key.
422 */
423 static char P[] = {
424 16, 7,20,21,
425 29,12,28,17,
426 1,15,23,26,
427 5,18,31,10,
428 2, 8,24,14,
429 32,27, 3, 9,
430 19,13,30, 6,
431 22,11, 4,25,
432 };
433
434 /*
435 * The current block, divided into 2 halves.
436 */
437 static char L[32], R[32];
438 static char tempL[32];
439 static char f[32];
440
441 /*
442 * The combination of the key and the input, before selection.
443 */
444 static char preS[48];
445
446 /*
447 * The payoff: encrypt a block.
448 */
449
blkencrypt(block,edflag)450 blkencrypt(block, edflag)
451 char *block;
452 {
453 int i, ii;
454 register t, j, k;
455
456 /*
457 * First, permute the bits in the input
458 */
459 for (j=0; j<64; j++)
460 L[j] = block[IP[j]-1];
461 /*
462 * Perform an encryption operation 16 times.
463 */
464 for (ii=0; ii<16; ii++) {
465 /*
466 * Set direction
467 */
468 if (edflag)
469 i = 15-ii;
470 else
471 i = ii;
472 /*
473 * Save the R array,
474 * which will be the new L.
475 */
476 for (j=0; j<32; j++)
477 tempL[j] = R[j];
478 /*
479 * Expand R to 48 bits using the E selector;
480 * exclusive-or with the current key bits.
481 */
482 for (j=0; j<48; j++)
483 preS[j] = R[E[j]-1] ^ KS[i][j];
484 /*
485 * The pre-select bits are now considered
486 * in 8 groups of 6 bits each.
487 * The 8 selection functions map these
488 * 6-bit quantities into 4-bit quantities
489 * and the results permuted
490 * to make an f(R, K).
491 * The indexing into the selection functions
492 * is peculiar; it could be simplified by
493 * rewriting the tables.
494 */
495 for (j=0; j<8; j++) {
496 t = 6*j;
497 k = S[j][(preS[t+0]<<5)+
498 (preS[t+1]<<3)+
499 (preS[t+2]<<2)+
500 (preS[t+3]<<1)+
501 (preS[t+4]<<0)+
502 (preS[t+5]<<4)];
503 t = 4*j;
504 f[t+0] = (k>>3)&01;
505 f[t+1] = (k>>2)&01;
506 f[t+2] = (k>>1)&01;
507 f[t+3] = (k>>0)&01;
508 }
509 /*
510 * The new R is L ^ f(R, K).
511 * The f here has to be permuted first, though.
512 */
513 for (j=0; j<32; j++)
514 R[j] = L[j] ^ f[P[j]-1];
515 /*
516 * Finally, the new L (the original R)
517 * is copied back.
518 */
519 for (j=0; j<32; j++)
520 L[j] = tempL[j];
521 }
522 /*
523 * The output L and R are reversed.
524 */
525 for (j=0; j<32; j++) {
526 t = L[j];
527 L[j] = R[j];
528 R[j] = t;
529 }
530 /*
531 * The final output
532 * gets the inverse permutation of the very original.
533 */
534 for (j=0; j<64; j++)
535 block[j] = L[FP[j]-1];
536 }
537