4.3BSD - /usr/src/old/berknet/nbs.c

   1: static char sccsid[] = "@(#)nbs.c	4.1	(Berkeley)	9/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[];
  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:     }
  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 */
  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: 
 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: }
 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: }
 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:     }
 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:     }
 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:     }
 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: 
 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: 
 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: }

Defined functions

Defined variables