util/gdss/lib/crypto/algorithm/bigkeygen.c

   1 /*
   2  * COPYRIGHT (C) 1990 DIGITAL EQUIPMENT CORPORATION
   3  * ALL RIGHTS RESERVED
   4  *
   5  * "Digital Equipment Corporation authorizes the reproduction,
   6  * distribution and modification of this software subject to the following
   7  * restrictions:
   8  *
   9  * 1.  Any partial or whole copy of this software, or any modification
  10  * thereof, must include this copyright notice in its entirety.
  11  *
  12  * 2.  This software is supplied "as is" with no warranty of any kind,
  13  * expressed or implied, for any purpose, including any warranty of fitness
  14  * or merchantibility.  DIGITAL assumes no responsibility for the use or
  15  * reliability of this software, nor promises to provide any form of
  16  * support for it on any basis.
  17  *
  18  * 3.  Distribution of this software is authorized only if no profit or
  19  * remuneration of any kind is received in exchange for such distribution.
  20  *
  21  * 4.  This software produces public key authentication certificates
  22  * bearing an expiration date established by DIGITAL and RSA Data
  23  * Security, Inc.  It may cease to generate certificates after the expiration
  24  * date.  Any modification of this software that changes or defeats
  25  * the expiration date or its effect is unauthorized.
  26  *
  27  * 5.  Software that will renew or extend the expiration date of
  28  * authentication certificates produced by this software may be obtained
  29  * from RSA Data Security, Inc., 10 Twin Dolphin Drive, Redwood City, CA
  30  * 94065, (415)595-8782, or from DIGITAL"
  31  *
  32  */
  33
  34 /* This code was derived from Mark Shand's PRL Montgomery code. */
  35
  36 #include <stdio.h>
  37 #include <time.h>
  38 #include <sys/types.h>
  39
  40 #include "BigZ.h"
  41 #include "BigRSA.h"
  42 #include "bigrsacode.h"
  43 #include "bigkeygen.h"
  44
  45 #ifdef mips
  46 #undef BnnSetToZero
  47 #endif
  48
  49 #define KEY_LINE 64
  50 #define KEY_RADIX 16
  51
  52 /*
  53 #define DEBUG_1
  54 */
  55
  56 /* Global storage indicating whether to print prime progress reports */
  57
  58 int bigkeygenPrintStatistics = 0;
  59
  60 #ifdef DEBUG
  61 #undef DEBUG
  62 #endif
  63
  64 /*
  65  * One-half the difference between the lengths of p and q, in bits
  66  */
  67 #define PRIME_BIT_DIFF 3
  68
  69 /*
  70  * Local modular product routines
  71  */
  72
  73 /* put in-line RSA routines here */
  74
  75 #include "RSAcrypto.h"
  76
  77 static void BnnGCD_1();
  78 static void modpwr2_1();
  79 static BigNum muB_1();
  80 static int bigprime();
  81
  82 /*
  83  * newRSAKey generates a new RSA key instance.
  84  *
  85  *      bitlen  length of primes, in bits.  Modulus will be
  86  *              approximately 2*bitlen
  87  *      keys    RSAKeyStorage structure for new key
  88  */
  89
  90 int newRSAKey ( bitlen , keys )
  91 int bitlen ;
  92 RSAKeyStorage *keys ;
  93 {
  94     BigNum  p = keys->p, q = keys->q ;
  95     unsigned lowbits = 1, confidence = 20, pl, ql;
  96 #ifdef DEBUG
  97     clock_t mark, tenths;
  98     struct timeb start_time , end_time ;
  99 #endif
 100
 101     if ((bitlen<128)||(bitlen>MaxPrimeBits)) return (0);
 102
 103     memset(keys,0,sizeof(RSAKeyStorage));
 104     BnnInit();
 105
 106 #ifdef DEBUG
 107     mark = clock();
 108     ftime (&start_time);
 109 #endif
 110
 111     bigprime(p, &pl, bitlen+PRIME_BIT_DIFF, lowbits, confidence, 0);
 112     do {
 113         bigprime(q, &ql, bitlen-PRIME_BIT_DIFF, lowbits, confidence, 0);
 114     } while (BnnCompare(p, pl, q, ql) == 0);
 115
 116 #ifdef DEBUG
 117     mark = clock() - mark ;
 118     ftime (&end_time);
 119
 120 #ifdef ultrix
 121 #ifndef CLOCKS_PER_SEC
 122 #define CLOCKS_PER_SEC  1000000
 123 #endif
 124     tenths = (100*(mark%CLOCKS_PER_SEC))/CLOCKS_PER_SEC ;
 125     mark /= CLOCKS_PER_SEC ;
 126 #else
 127     tenths = (100*(mark%CLK_TCK))/CLK_TCK ;
 128     mark /= CLK_TCK ;
 129 #endif
 130
 131     printf ("\n/* Primes found in %d.%02d seconds of process time*/\n", mark, tenths );
 132     mark = end_time.time - start_time.time ;
 133     { long xt = (unsigned long) end_time.millitm - (unsigned long) start_time.millitm ;
 134       if (xt<0) { mark--; xt = 1000 - xt;}
 135       printf ("\n/* Primes found in %d.%03d elapsed seconds */\n",
 136                  end_time.time-start_time.time, xt );
 137     }
 138 #endif
 139
 140     if (BnnCompare(p, pl, q, ql) == -1) {
 141         unsigned tpl = pl;
 142         BigNumDigit tp[DigitLim];
 143         BnnSetToZero(tp,DigitLim);
 144         BnnAssign(tp,p,pl);
 145         BnnSetToZero(p,pl);
 146         BnnAssign(p,q,ql);
 147         BnnAssign(q,tp,pl);
 148         pl = ql;
 149         ql = tpl;
 150     }
 151
 152     keys->pl = pl;
 153     keys->ql = ql;
 154
 155     /*
 156      * Set exponent to F16 and compute modulus.
 157      */
 158     BnnSetDigit(keys->e, (BigNumDigit) ((1<<16)+1));
 159     keys->el = 1;
 160
 161     BnnMultiply(keys->n, pl+ql, p, pl, q, ql),
 162     keys->nl = pl+ql;
 163
 164     if (FinishKey(keys)==0) return (0);
 165
 166     if (TestRSAKeys(keys)!=1) {
 167 #ifdef DEBUG
 168 printf("\nFailed.\n");
 169 #endif
 170         return(0);
 171     }
 172
 173     BnnClose();
 174     return(1);
 175 }
 176
 177
 178 /*
 179  * Prime-finding routines
 180  */
 181
 182
 183 static BigNumDigit smallprime[]=
 184 {3,5,7,11,13,17,19,23,29,31,37,41,43,53,59,
 185 61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,
 186 163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,
 187 257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,
 188 359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,
 189 461,463,467,479,487,491,499 };
 190
 191
 192 /*
 193  * Test for primality.
 194  */
 195
 196 static int IsPrime(n,nl,confidence)
 197 BigNum n;
 198 int nl;
 199 {
 200         int i;
 201         static BigNumDigit x[DigitLim],
 202                            y[2*DigitLim],
 203                            beta2n[2*DigitLim+1],
 204                            nINV [2*DigitLim] ;
 205
 206         for(i=0;i<=(sizeof(smallprime)/sizeof(BigNumDigit));i++)
 207           if(BnnDivideDigit(y,n,nl+1,smallprime[i])==0) goto exit ;
 208
 209         muB_1(nINV, n, nl*BN_DIGIT_SIZE);
 210         modpwr2_1(beta2n, 2, n, nl);
 211         BnnSetToZero (x, nl);
 212
 213         for(i=0;i<=confidence;i++) {
 214                 x[0]+= smallprime[i] ;
 215                 BnnDyRaise_1(y, x, n, nl, n, beta2n, nINV, nl);
 216                 BnnDyCanon_1(y, n, nl);
 217                 if (BnnCompare(y, nl, x, nl)) goto exit;
 218                 }
 219         return(1);
 220
 221 exit:
 222         return(0);
 223 }
 224
 225 /*
 226  * Generate a big prime.
 227  */
 228 static bigprime (n,nlen,bitlen,lowbits,confidence,stats)
 229 BigNum n;
 230 unsigned *nlen;
 231 int bitlen;
 232 BigNumDigit lowbits;
 233 int confidence;
 234 unsigned *stats;
 235 {
 236   char * z ;
 237   static char sieve [1000];
 238   int i,j;
 239   BigNumDigit r, s, q[DigitLim] ;
 240   unsigned nl =(bitlen+(BN_DIGIT_SIZE-1))/BN_DIGIT_SIZE ;
 241   unsigned ntop = nl;
 242
 243   if((((bitlen-1)%BN_DIGIT_SIZE)+1)>=(BN_DIGIT_SIZE-1)) nl++;
 244   *nlen = nl;
 245   BnnSetToZero(n,nl+1);
 246   while(1) {
 247     random_BigNum(n,ntop);
 248     n[nl-1]&=(1<<((BN_DIGIT_SIZE)-(nl*(BN_DIGIT_SIZE)-bitlen))) -1 ;
 249     n[(bitlen-1)/BN_DIGIT_SIZE] |= 1<<((bitlen-1)%BN_DIGIT_SIZE);
 250     n[(bitlen-2)/BN_DIGIT_SIZE] |= 1<<((bitlen-2)%BN_DIGIT_SIZE);
 251     n[0]&=~1;
 252
 253     if(bigkeygenPrintStatistics)
 254         printf("\nCandidate Random Number: %s\n",BzToString(BzFromBigNum(n,nl),16));
 255
 256     z = &sieve[0] ;
 257     for (i=0;i<1000;i=i+2){*z++=1;*z++=0;};
 258     r = BnnDivideDigit(q,n,nl+1,(BigNumDigit)3);
 259     if (r==0) r = (BigNumDigit) 3;
 260     r--;
 261     z = &sieve[3-r] ;
 262     for (j=3-r;j<1000;j+=3) {*z=1;z+=3;}
 263
 264     for (s=3;s<10000;s+=2) {
 265       for (j=0; j<5; j++)if ((s>smallprime[j])&&(0==(s%smallprime[j]))) goto nexts;
 266       r = BnnDivideDigit(q,n,nl+1,s);
 267       if (r==0) r = s;
 268       z = &sieve[s-r] ;
 269       for (j=s-r;j<1000;j+=s) {*z=1;z+=s;}
 270     nexts: ;
 271     }
 272     for(i=0;i<1000;i++) {
 273       if (!sieve[i]) {
 274
 275     if(bigkeygenPrintStatistics) printf("|"),fflush(stdout);
 276
 277          if (IsPrime(n,nl,5)) goto exit;
 278       }
 279       BnnAddCarry(n,nl,1);  /* try next one */
 280     }
 281   }
 282 exit:
 283
 284 if(bigkeygenPrintStatistics) printf(""), fflush(stdout);
 285
 286 }
 287
 288
 289 /*
 290  * This routine expects modulus n and exponent e to be initialized
 291  * in the RSAKeyStorage structure supplied.  It computes the rest of
 292  * the key components based on what is provided.  If p and q are there
 293  * it also makes sure a complete private key is initialized.
 294  */
 295 int FinishKey (keys)
 296 RSAKeyStorage *keys;
 297 {
 298     static BigNumDigit g[4*DigitLim], wgcd[12*DigitLim],
 299         r[4*DigitLim], pq[4*DigitLim], d[4*DigitLim], z[4*DigitLim];
 300
 301     BigNum n = keys->n, dp = keys->dp, dq = keys->dq, cr = keys->cr,
 302            e = keys->e, p = keys->p, q = keys->q ;
 303
 304     unsigned nl=keys->nl, pl=keys->pl, ql=keys->ql, tmp,
 305              dpl = keys->dpl, dql = keys->dql ;
 306
 307     /*
 308      * If primes are supplied, generate dp, dq, and cr if needed.
 309      * Assume cr there if dp and dq are.
 310      */
 311
 312     if (pl && ql && ((dpl == 0)||(dql ==0)) ) {
 313         BnnAssign(pq, n, nl);
 314         BnnSubtract(pq, nl, p, pl, 1);
 315         BnnSubtract(pq, nl, q, ql, 1);
 316         BnnAddCarry(pq, nl, 1);
 317         BnnGCD_1(g, d, r, e, pq, wgcd, nl);
 318         if (BnnCompare(g,nl,one,nl)!=0) {
 319 #ifdef DEBUG
 320 printf("GCD failed to generate private key exponent.\n");
 321 #endif
 322                 return(0);
 323         }
 324         BnnAssign(z, d, nl);
 325         z[nl] = 0;
 326         BnnAssign(pq, p, pl);
 327         BnnSubtractBorrow(pq, pl, 0);
 328         BnnDivide(z, nl+1, pq, tmp=BnnNumDigits(pq, pl));
 329         BnnSetToZero(z+tmp, nl+1-tmp);
 330         BnnAssign(dp, z, (keys->dpl)=BnnNumDigits(z,nl));
 331
 332         BnnAssign(z, d, nl);
 333         z[nl] = 0;
 334         BnnAssign(pq, q, ql);
 335         BnnSubtractBorrow(pq, ql, 0);
 336         BnnDivide(z, nl+1, pq, tmp=BnnNumDigits(pq, ql));
 337         BnnSetToZero(z+tmp, nl+1-tmp);
 338         BnnAssign(dq, z, (keys->dql)=BnnNumDigits(z,nl));
 339
 340         BnnGCD_1(g,r,cr,p,q,wgcd,pl);
 341         if ((BnnGetDigit(cr+(pl-1))&TopBitInWord)!=0) BnnAdd(cr,pl,p,pl,0);
 342     }
 343
 344     modpwr2_1(z, 2, n, nl);
 345     BnnAssign(keys->beta2n, z, nl);
 346     muB_1(keys->nINV, n, nl*BN_DIGIT_SIZE);
 347
 348     if (pl&&ql)  {
 349         modpwr2_1(z, 3, p, pl);
 350         BnnAssign(keys->beta3p, z, pl);
 351         modpwr2_1(z, 2, p, pl);
 352         BnnAssign(keys->beta2p, z, pl);
 353         modpwr2_1(z, 3, q, ql);
 354         BnnAssign(keys->beta3q, z, ql);
 355         muB_1(keys->pINV, p, pl*BN_DIGIT_SIZE);
 356         muB_1(keys->qINV, q, ql*BN_DIGIT_SIZE);
 357     }
 358
 359 #ifdef DEBUG_1
 360     printf("\n");
 361     printf("p = %s\n", BzToString(BzFromBigNum(p, pl), 16));
 362     printf("q = %s\n", BzToString(BzFromBigNum(q, ql), 16));
 363     printf("n = %s\n", BzToString(BzFromBigNum(n, nl), 16));
 364     printf("e = %s\n", BzToString(BzFromBigNum(e, nl), 16));
 365     printf("d = %s\n", BzToString(BzFromBigNum(d, nl), 16));
 366     printf("dp = %s\n", BzToString(BzFromBigNum(dp, dpl), 16));
 367     printf("dq = %s\n", BzToString(BzFromBigNum(dq, dql), 16));
 368     printf("cr = %s\n", BzToString(BzFromBigNum(cr, pl), 16));
 369     fflush(stdout);
 370 #endif
 371
 372
 373     return(1);
 374 }
 375
 376
 377 static BigNum muB_1(res, zz, bits)
 378 BigNum res, zz;
 379 int bits;
 380 {
 381     /* Compute -z^-1 mod 2^bits */
 382 #define muBLIM 40
 383     BigNumDigit n[muBLIM];
 384     BigNumDigit msk[muBLIM], z[muBLIM];
 385     unsigned nl = (bits+BN_DIGIT_SIZE-1)/BN_DIGIT_SIZE;
 386     int i;
 387
 388     if (nl > muBLIM)
 389     {
 390         fprintf(stderr, "Limit check in %s:muB_1 line %d\n", __FILE__, __LINE__);
 391         abort();
 392     }
 393
 394     BnnSetToZero(n, nl);
 395     BnnComplement(n,nl);
 396     BnnSetToZero(res, nl);
 397     BnnSetToZero(msk, nl);
 398     BnnSetDigit(msk, 1);
 399     BnnAssign(z, zz, nl);
 400     BnnShiftRight(z,nl,1);
 401     while (bits--)
 402     {
 403         if (BnnIsDigitOdd(*n))
 404         {
 405             for (i = 0; i < nl; i++)
 406                 BnnOrDigits(res+i, msk[i]);
 407             BnnShiftRight(n,nl,1);
 408             BnnSubtract(n, nl, z, nl, 1);
 409         }
 410         else
 411            BnnShiftRight(n,nl,1);
 412         BnnShiftLeft(msk,nl,1);
 413     }
 414     return res;
 415 }
 416
 417 static void modpwr2_1(result, pwr, m, ml)
 418 BigNum result, m;
 419 unsigned pwr, ml;
 420 {       unsigned tmp;
 421         BnnSetToZero(result, pwr*ml);
 422         BnnSetDigit(result+pwr*ml, (BigNumDigit) 1);
 423         BnnDivide(result, pwr*ml+1, m, tmp=BnnNumDigits(m, ml));
 424         BnnSetToZero(result+tmp, pwr*ml+1-tmp);
 425 }
 426
 427
 428 static void BnnGCD_1(gcd, A, B, U, V, work, len)
 429 BigNum gcd, A, B, U, V, work;
 430 int len;
 431 {
 432     /* Extended binary GCD
 433        code based on Knuth Vol.2 Second Edition
 434        section 4.5.2 Answers to Exercises page 599
 435     */
 436     /* Note: len must be large enough to hold 2*U or 2*V */
 437     /* "work" is a BigNum of length 3*len */
 438     BigNumDigit k;
 439     BigNum u1,u2,u3, v1,v2,v3;
 440     BigNum t1,t2,t3;
 441     u1 = A; u2 = B; u3 = gcd;
 442     v1 = work; v2 = work + len; v3 = work + 2*len;
 443
 444     k = 0;
 445     while (!BnnIsDigitOdd(*U) && !BnnIsDigitOdd(*V))
 446     {
 447         BnnShiftRight(U, len, 1);
 448         BnnShiftRight(V, len, 1);
 449         k++;
 450     }
 451     BnnSetToZero(u1, len); BnnSetDigit(u1, (BigNumDigit) 1);
 452     BnnSetToZero(u2, len);
 453     BnnAssign(u3, U, len);
 454     if (BnnIsDigitOdd(*U))
 455     {
 456         t1 = v1; t2 = v2; t3 = v3;
 457         BnnSetToZero(v1, len);
 458         BnnSetToZero(v2, len); BnnComplement(v2, len);
 459         BnnSetToZero(v3, len); BnnSubtract(v3, len, V, len, 1);
 460     }
 461     else
 462     {
 463         t1 = u1; t2 = u2; t3 = u3;
 464         BnnAssign(v1, V, len);
 465         BnnSetToZero(v2, len); BnnSetDigit(v2, (BigNumDigit) 1);
 466             BnnSubtract(v2, len, U, len, 1);
 467         BnnAssign(v3, V, len);
 468     }
 469 #ifdef PRINT_LEVEL2
 470     printf("#[%d %d %d ] [ %d %d %d ]\n", *u1,*u2,*u3, *v1,*v2,*v3);
 471 #endif
 472     while (!BnnIsZero(t3, len))
 473     {
 474         while (!BnnIsDigitOdd(*t3))
 475         {
 476             BigNumDigit sign;
 477             if (!BnnIsDigitOdd(*t1) && !BnnIsDigitOdd(*t2))
 478             {
 479                 sign = BnnGetDigit(t1+(len-1)) & TopBitInWord;
 480                 BnnShiftRight(t1, len, 1);
 481                 BnnOrDigits(t1+(len-1), sign);
 482                 sign = BnnGetDigit(t2+(len-1)) & TopBitInWord;
 483                 BnnShiftRight(t2, len, 1);
 484                 BnnOrDigits(t2+(len-1), sign);
 485             }
 486             else
 487             {
 488                 BnnAdd(t1, len, V, len, 0);
 489                 sign = BnnGetDigit(t1+(len-1)) & TopBitInWord;
 490                 BnnShiftRight(t1, len, 1);
 491                 BnnOrDigits(t1+(len-1), sign);
 492                 BnnSubtract(t2, len, U, len, 1);
 493                 sign = BnnGetDigit(t2+(len-1)) & TopBitInWord;
 494                 BnnShiftRight(t2, len, 1);
 495                 BnnOrDigits(t2+(len-1), sign);
 496             }
 497             sign = BnnGetDigit(t3+(len-1)) & TopBitInWord;
 498             BnnShiftRight(t3, len, 1);
 499             BnnOrDigits(t3+(len-1), sign);
 500         }
 501         if (t1 == v1) /* a cheap way to recall what state we are in */
 502         {
 503             BnnComplement(v1, len);
 504             BnnAdd(v1, len, V, len, 1);
 505             BnnComplement(v2, len);
 506             BnnAddCarry(v2, len, 1);
 507             BnnSubtract(v2, len, U, len, 1);
 508             BnnComplement(v3, len);
 509             BnnAddCarry(v3, len, 1);
 510         }
 511         if (BnnCompare(u3, len, v3, len) > 0)
 512         {
 513             BnnSubtract(u1, len, v1, len, 1);
 514             BnnSubtract(u2, len, v2, len, 1);
 515             BnnSubtract(u3, len, v3, len, 1);
 516             t1 = u1; t2 = u2; t3 = u3;
 517         }
 518         else
 519         {
 520             BnnComplement(v1, len);
 521             BnnAdd(v1, len, u1, len, 1);
 522             BnnComplement(v2, len);
 523             BnnAdd(v2, len, u2, len, 1);
 524             BnnComplement(v3, len);
 525             BnnAdd(v3, len, u3, len, 1);
 526             t1 = v1; t2 = v2; t3 = v3;
 527         }
 528
 529         if (BnnGetDigit(t1+(len-1)) & TopBitInWord)
 530         {
 531             BnnAdd(t1, len, V, len, 0);
 532             BnnSubtract(t2, len, U, len, 1);
 533         }
 534 #ifdef PRINT_LEVEL2
 535     printf(">[%d %d %d ] [ %d %d %d ]\n", *u1,*u2,*u3, *v1,*v2,*v3);
 536 #endif
 537     }
 538     while (k-- > 0)
 539         BnnShiftLeft(u3, len, 1);
 540 }
 541
 542
 543 /**********************************************************************/
 544
 545 static char *TestData = "Now is the time for all good men to come to the aid of their" ;
 546 static BigNumDigit test_in [2*DigitLim], test1 [2*DigitLim], test2 [2*DigitLim] ;
 547
 548 int TestRSAKeys(key)
 549 RSAKeyStorage *key ;
 550 {
 551         int nl=key->nl;
 552         int ll = BnnNumDigits(key->n,nl);
 553
 554         memset(test_in,0,sizeof(test_in));
 555         memset(test1,0,sizeof(test1));
 556         memset(test2,0,sizeof(test2));
 557         strcpy((char *)test_in,TestData);
 558         BnnSetToZero(test_in+ll-2,(nl-ll)+3);
 559 #ifdef DEBUG
 560 printf("\nPrivate Key Encrypt/Decrypt Test.");
 561 printf("\nInput(hex): %s", BzToString(BzFromBigNum(test_in, nl), 16));
 562 printf("\nInput(string): %s", test_in);
 563 #endif
 564         rsaencrypt_1(test_in,test1,key);
 565 #ifdef DEBUG
 566 printf("\nEncrypted: %s", BzToString(BzFromBigNum(test1, nl), 16));
 567 #endif
 568         rsadecrypt_1(test1,test2,key);
 569 #ifdef DEBUG
 570 printf("\nDecrypted: %s", BzToString(BzFromBigNum(test2, nl), 16));
 571 printf("\n");
 572 #endif
 573         if (BnnCompare(test_in,nl,test2,nl) != 0) {
 574 #ifdef DEBUG
 575 printf("\nKey Test Failed.\n");
 576 #endif
 577                 return(0);
 578         }
 579 #ifdef DEBUG
 580 printf("\nKey Test Passed.\n");
 581 #endif
 582         return(1);
 583 }
 584
 585 static int Test2RSAPrivate_1(key)
 586 RSAKeyStorage *key ;
 587 {
 588         int nl=key->nl;
 589         int ll = BnnNumDigits(key->n,nl);
 590
 591         memset(test_in,0,sizeof(test_in));
 592         memset(test1,0,sizeof(test1));
 593         memset(test2,0,sizeof(test2));
 594         strcpy((char *)test_in,TestData);
 595         BnnSetToZero(test_in+ll-2,(nl-ll)+3);
 596 #ifdef DEBUG
 597         printf("\nPrivate Key Decrypt/Encrypt Test.");
 598         printf("\nInput(hex): %s", BzToString(BzFromBigNum(test_in, nl), 16));
 599         printf("\nInput(string): %s", test_in);
 600 #endif
 601         rsadecrypt_1(test_in,test1,key);
 602 #ifdef DEBUG
 603 printf("\nSigned: %s", BzToString(BzFromBigNum(test1, nl), 16));
 604 #endif
 605         rsaencrypt_1(test1,test2,key);
 606 #ifdef DEBUG
 607 printf("\nVerified: %s", BzToString(BzFromBigNum(test2, nl), 16));
 608 printf("\n");
 609 #endif
 610         if (BnnCompare(test_in,nl,test2,nl) != 0) {
 611 #ifdef DEBUG
 612 printf("\nKey Test Failed.\n");
 613 #endif
 614                 return(0);
 615         }
 616         return(1);
 617 }
 618
 619
 620 PrintBigNum(n,nl,radix)
 621 BigNum n;
 622 int radix, nl;
 623 {
 624      static char oneline [KEY_LINE+1];
 625      char *p = BzToString(BzFromBigNum(n,nl), radix);
 626
 627      oneline[KEY_LINE]='\0';
 628      while(*p != '\0'){
 629         strncpy(oneline,p,KEY_LINE);
 630         printf("\n     %s",oneline);
 631         p+=((strlen(p)>KEY_LINE)?KEY_LINE:strlen(p));
 632      }
 633 }
 634
 635 int PrintTestKey (Keys)
 636 RSAKeyStorage *Keys;
 637 {
 638     int i;
 639
 640     printf("\ne: (%d BigNumDigit", Keys->el);
 641     if(Keys->el > 1) printf("s) "); else printf(")");
 642     PrintBigNum(Keys->e,Keys->el,KEY_RADIX);
 643     printf("\nn: (%d BigNumDigits) ", Keys->nl);
 644     PrintBigNum(Keys->n,Keys->nl,KEY_RADIX);
 645
 646     if (Keys->pl) { printf("\np: (%d BigNumDigits) ", Keys->pl);
 647               PrintBigNum(Keys->p,Keys->pl,KEY_RADIX);
 648               printf("\nq: (%d BigNumDigits) ", Keys->ql);
 649               PrintBigNum(Keys->q,Keys->ql,KEY_RADIX);
 650               printf("\ndp: (%d BigNumDigits) ", Keys->dpl);
 651               PrintBigNum(Keys->dp, Keys->dpl,KEY_RADIX);
 652               printf("\ndq: (%d BigNumDigits) ", Keys->dql);
 653               PrintBigNum(Keys->dq, Keys->dql,KEY_RADIX);
 654               printf("\ncr: ");
 655               PrintBigNum(Keys->cr, Keys->pl,KEY_RADIX);
 656     }
 657
 658     i=BnnNumDigits(Keys->nINV,sizeof(*Keys->nINV)*sizeof(int));
 659     printf("\nnINV: (%d BigNumDigits) ", i);
 660     PrintBigNum(Keys->nINV, i, KEY_RADIX);
 661
 662     i=BnnNumDigits(Keys->beta2n,sizeof(*Keys->beta2n)*sizeof(int));
 663     printf("\nbeta2n: (%d BigNumDigits) ", i);
 664     PrintBigNum(Keys->beta2n, i,KEY_RADIX);
 665
 666     if(Keys->pl) {
 667         i=BnnNumDigits(Keys->pINV,sizeof(*Keys->pINV)*sizeof(int));
 668         printf("\npINV: (%d BigNumDigits) ", i);
 669         PrintBigNum(Keys->pINV, i,KEY_RADIX);
 670
 671         i=BnnNumDigits(Keys->qINV,sizeof(*Keys->qINV)*sizeof(int));
 672         printf("\nqINV: (%d BigNumDigits) ", i);
 673         PrintBigNum(Keys->qINV, i,KEY_RADIX);
 674
 675
 676         i=BnnNumDigits(Keys->beta2p,sizeof(*Keys->beta2p)*sizeof(int));
 677         printf("\nbeta2p: (%d BigNumDigits) ", i);
 678         PrintBigNum(Keys->beta2p, i,KEY_RADIX);
 679
 680         i=BnnNumDigits(Keys->beta3p,sizeof(*Keys->beta3p)*sizeof(int));
 681         printf("\nbeta3p: (%d BigNumDigits) ", i);
 682         PrintBigNum(Keys->beta3p, i,KEY_RADIX);
 683
 684         i=BnnNumDigits(Keys->beta3q,sizeof(*Keys->beta3q)*sizeof(int));
 685         printf("\nbeta3q: (%d BigNumDigits) ", i);
 686         PrintBigNum(Keys->beta3q, i,KEY_RADIX);
 687     }
 688
 689     printf("\n");
 690     fflush(stdout);
 691 }
 692
 693
 694 int PrintPubKey (Keys)
 695 RSAKeyStorage *Keys;
 696 {
 697     int i=BnnNumDigits(Keys->n,Keys->nl);
 698     i = i*BN_DIGIT_SIZE - BnnNumLeadingZeroBitsInDigit(Keys->n[i-1]);
 699
 700     printf("\ne: (%d BigNumDigit", Keys->el);
 701     if(Keys->el > 1) printf("s) "); else printf(")");
 702     PrintBigNum(Keys->e,Keys->el,KEY_RADIX);
 703     printf("\nn: (%d BigNumDigits, %d bits) ", Keys->nl, i);
 704     PrintBigNum(Keys->n,Keys->nl,KEY_RADIX);
 705
 706     printf("\n");
 707     fflush(stdout);
 708 }
 709
 710 int PrintPrivKey (Keys)
 711 RSAKeyStorage *Keys;
 712 {
 713     int i=BnnNumDigits(Keys->n,Keys->nl);
 714     i = i*BN_DIGIT_SIZE - BnnNumLeadingZeroBitsInDigit(Keys->n[i-1]);
 715
 716     printf("\ne: (%d BigNumDigit", Keys->el);
 717     if(Keys->el > 1) printf("s) "); else printf(")");
 718     PrintBigNum(Keys->e,Keys->el,KEY_RADIX);
 719     printf("\nn: (%d BigNumDigits, %d bits) ", Keys->nl, i);
 720     PrintBigNum(Keys->n,Keys->nl,KEY_RADIX);
 721
 722     if (Keys->pl) { printf("\np: (%d BigNumDigits) ", Keys->pl);
 723               PrintBigNum(Keys->p,Keys->pl,KEY_RADIX);
 724               printf("\nq: (%d BigNumDigits) ", Keys->ql);
 725               PrintBigNum(Keys->q,Keys->ql,KEY_RADIX);
 726               printf("\ndp: (%d BigNumDigits) ", Keys->dpl);
 727               PrintBigNum(Keys->dp, Keys->dpl,KEY_RADIX);
 728               printf("\ndq: (%d BigNumDigits) ", Keys->dql);
 729               PrintBigNum(Keys->dq, Keys->dql,KEY_RADIX);
 730               printf("\ncr: ");
 731               PrintBigNum(Keys->cr, Keys->pl,KEY_RADIX);
 732     }
 733     else printf("\n no private key parameters.");
 734
 735     printf("\n");
 736     fflush(stdout);
 737     }
 738
 739
 740 /*********************************************************************/
 741
 742 /* In-line DES routines here. */
 743
 744 #include "DEScrypto.h"
 745
 746 static KEYschedule local_key_schedule;
 747 static RSAKeyStorage tempkey;
 748
 749 /*
 750  * Decrypts an RSA private key.
 751  */
 752 int recover_private(deskey, encrypted_key, encrypted_key_len, key)
 753 DESblock *deskey;               /* derived from password */
 754 char *encrypted_key;            /* input to be decrypted */
 755 unsigned encrypted_key_len;     /* must be multiple of 8 bytes */
 756 RSAKeyStorage *key;             /* output with new key in it */
 757 {
 758    unsigned char *outbuf;
 759    int rt=0;
 760
 761    if((outbuf=(unsigned char *)calloc(encrypted_key_len,1))==0)return(0);
 762
 763    DES_load_key_local( deskey, &local_key_schedule);
 764    if (DES_CBC_decrypt_local(0, encrypted_key, encrypted_key_len,
 765                                 outbuf, &local_key_schedule)==0)
 766                                                         goto clean;
 767    memset(&tempkey,0,sizeof(tempkey));
 768    if (key->nl) tempkey.nl=key->nl, BnnAssign(tempkey.n,key->n,key->nl);
 769 #ifdef DEBUG
 770 printf("\nDecrypted private key:\n");
 771 dumphex(outbuf,encrypted_key_len-sizeof(long));
 772 #endif
 773    if (DecodePrivate(outbuf, &tempkey) != NULL) {
 774 #ifdef DEBUG
 775 printf("\nRecovered Key:\n");
 776 PrintTestKey(&tempkey);
 777 #endif
 778         if (rt=TestRSAKeys(&tempkey)) memcpy(key,&tempkey,sizeof(RSAKeyStorage));
 779    }
 780 #ifdef DEBUG
 781    else printf("\nDecode Failed.\n");
 782 #endif
 783
 784    memset(outbuf,0,encrypted_key_len);
 785    memset(&tempkey,0,sizeof(tempkey));
 786 clean:
 787    free(outbuf);
 788    return(rt);
 789 }
 790
 791 /*
 792  * Decrypts an RSA private key.
 793  */
 794 int recover_privateP(deskey, encrypted_key, encrypted_key_len, key)
 795 DESblock *deskey;               /* derived from password */
 796 char *encrypted_key;            /* input to be decrypted */
 797 unsigned encrypted_key_len;     /* must be multiple of 8 bytes */
 798 RSAKeyStorage *key;             /* output with new key in it */
 799 {
 800    unsigned char *outbuf;
 801    int rt=0;
 802
 803    if((outbuf=(unsigned char *)calloc(encrypted_key_len,1))==0)return(0);
 804
 805    DES_load_key_local( deskey, &local_key_schedule);
 806    if (DES_CBC_decrypt_local(0, encrypted_key, encrypted_key_len,
 807                                 outbuf, &local_key_schedule)==0)
 808                                                         goto clean;
 809    memset(&tempkey,0,sizeof(tempkey));
 810    if (key->nl) tempkey.nl=key->nl, BnnAssign(tempkey.n,key->n,key->nl);
 811 #ifdef DEBUG
 812 printf("\nDecrypted private key:\n");
 813 dumphex(outbuf,encrypted_key_len-sizeof(long));
 814 #endif
 815    /*  make sure that we decode the private key with only the prime p  */
 816    if (DecodePrivateP(outbuf, &tempkey) != NULL) {
 817 #ifdef DEBUG
 818 printf("\nRecovered Key:\n");
 819 PrintTestKey(&tempkey);
 820 #endif
 821         if (rt=TestRSAKeys(&tempkey)) memcpy(key,&tempkey,sizeof(RSAKeyStorage));
 822    }
 823 #ifdef DEBUG
 824    else printf("\nDecode Failed.\n");
 825 #endif
 826
 827    memset(outbuf,0,encrypted_key_len);
 828    memset(&tempkey,0,sizeof(tempkey));
 829 clean:
 830    free(outbuf);
 831    return(rt);
 832 }
 833
 834 /*
 835  * Encrypts an RSA private key.
 836  *
 837  * NOTE: Contains components to foil use as a general encrypt/decrypt
 838  *       facility.
 839  *
 840  */
 841 int hide_private(deskey, encrypted_key, encrypted_key_len, key)
 842 DESblock *deskey;               /* derived from password */
 843 char **encrypted_key;           /* storage will be allocated */
 844 unsigned *encrypted_key_len;    /* will be written */
 845 RSAKeyStorage *key;             /* input must be a valid private key */
 846 {
 847    unsigned char *outbuf, *encoded_key;
 848    int len, klen;
 849
 850    if (TestRSAKeys(key)!=1) return(0);
 851    if ((encoded_key=EncodePrivate(key))==0) return(0) ;
 852    len = (((klen=DecodeTotalLength(encoded_key))+7)/8)*8; /* pad */
 853    if ((outbuf = (unsigned char *)calloc(len,1)) ==0)
 854                         {FreePrivate(encoded_key); return(0);};
 855    memcpy(outbuf,encoded_key,klen);
 856    FreePrivate(encoded_key);
 857    DES_load_key_local(deskey, &local_key_schedule);
 858    DES_CBC_encrypt_local (0, outbuf, len, outbuf, &local_key_schedule);
 859    *encrypted_key = (char *)outbuf;
 860    *encrypted_key_len = len;
 861    return(1);
 862 }
 863
 864
 865 /*
 866  * Same as above, but only encrypts prime P
 867  */
 868 int hide_privateP(deskey, encrypted_key, encrypted_key_len, key)
 869 DESblock *deskey;               /* derived from password */
 870 char **encrypted_key;           /* storage will be allocated */
 871 unsigned *encrypted_key_len;    /* will be written */
 872 RSAKeyStorage *key;             /* input must be a valid private key */
 873 {
 874    unsigned char *outbuf, *encoded_key;
 875    int len, klen;
 876
 877    if (TestRSAKeys(key)!=1) return(0);
 878    if ((encoded_key=EncodePrivateP(key))==0) return(0) ;
 879    len = (((klen=DecodeTotalLength(encoded_key))+7)/8)*8;
 880    if ((outbuf = (unsigned char *)calloc(len,1)) ==0)
 881                         {FreePrivate(encoded_key); return(0);};
 882    memcpy(outbuf,encoded_key,klen);
 883    FreePrivate(encoded_key);
 884    DES_load_key_local(deskey, &local_key_schedule);
 885    DES_CBC_encrypt_local (0, outbuf, len, outbuf, &local_key_schedule);
 886    *encrypted_key = (char *)outbuf;
 887    *encrypted_key_len = len;
 888    return(1);
 889 }