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