2.9BSD - /usr/src/ucb/berknet/nbs.c

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

Defined functions

Defined variables