util/gdss/lib/crypto/algorithm/RSAcrypto.h

   1 /* RSAcrypto.h */
   2 /*
   3  * COPYRIGHT (C) 1990 DIGITAL EQUIPMENT CORPORATION
   4  * ALL RIGHTS RESERVED
   5  *
   6  * "Digital Equipment Corporation authorizes the reproduction,
   7  * distribution and modification of this software subject to the following
   8  * restrictions:
   9  *
  10  * 1.  Any partial or whole copy of this software, or any modification
  11  * thereof, must include this copyright notice in its entirety.
  12  *
  13  * 2.  This software is supplied "as is" with no warranty of any kind,
  14  * expressed or implied, for any purpose, including any warranty of fitness
  15  * or merchantibility.  DIGITAL assumes no responsibility for the use or
  16  * reliability of this software, nor promises to provide any form of
  17  * support for it on any basis.
  18  *
  19  * 3.  Distribution of this software is authorized only if no profit or
  20  * remuneration of any kind is received in exchange for such distribution.
  21  *
  22  * 4.  This software produces public key authentication certificates
  23  * bearing an expiration date established by DIGITAL and RSA Data
  24  * Security, Inc.  It may cease to generate certificates after the expiration
  25  * date.  Any modification of this software that changes or defeats
  26  * the expiration date or its effect is unauthorized.
  27  *
  28  * 5.  Software that will renew or extend the expiration date of
  29  * authentication certificates produced by this software may be obtained
  30  * from RSA Data Security, Inc., 10 Twin Dolphin Drive, Redwood City, CA
  31  * 94065, (415)595-8782, or from DIGITAL"
  32  *
  33  */
  34
  35 /* This code was derived in large part from Mark Shand's PRL Montgomery code. */
  36
  37 /* In-line code for basic RSA routines */
  38
  39 static void rsaencrypt_1();
  40 static void rsadecrypt_1();
  41 static void BnnModularProduct_1();
  42 static void BnnDyRaise_1 ();
  43 static unsigned BnnDyCanon_1 ();
  44
  45 /*
  46  *********************************************************************
  47  *********************************************************************
  48  **                                                                 **
  49  **                       W A R N I N G                             **
  50  **                                                                 **
  51  **  This software is subject to export restrictions under the      **
  52  **  U.S. Department of State's International Traffic in Arms       **
  53  **  Regulations (ITAR).  This software must not be transmitted     **
  54  **  IN SOURCE FORM outside the United States or to a foreign       **
  55  **  national in the United States without a valid U.S. State       **
  56  **  Department export license.                                     **
  57  **                                                                 **
  58  *********************************************************************
  59  *********************************************************************
  60 */
  61
  62 #ifndef SPHINX_RSACRYPTO
  63 #define SPHINX_RSACRYPTO
  64
  65 #ifndef SPHINX_ITAR
  66 #define SPHINX_ITAR
  67 static char copyright[] = "\n Copyright, 1989, 1990, Digital Equipment Corporation ";
  68 static char warning[]= "\n  This software is subject to export restrictions under \
  69 \n  the U.S. Department of State's International Traffic in Arms \
  70 \n  Regulations (ITAR).  This software must not be transmitted \
  71 \n  in source form outside the United States or to a foreign \
  72 \n  national in the United States without a valid U.S. State \
  73 \n  Department export license. ";
  74 #endif
  75
  76 #define assert(x) ((x)?0:dumpcore("x",__FILE__,__LINE__))
  77 #define TopBitInWord ((BigNumDigit)(1<<(BN_DIGIT_SIZE-1)))
  78
  79 static BigNumDigit one[2*2*DigitLim] = { 1 };
  80
  81 static int dumpcore(s,f,n)
  82 char *s,*f;
  83 int n;
  84 {
  85     fflush(stdout);
  86     fclose(stdout);
  87     fprintf(stderr, "\nassertion failed file %s line %d: %s\n",  f, n, s);
  88     fclose(stderr);
  89     abort();
  90 }
  91
  92 static void rsaencrypt_1(inblk,outblk,keys)
  93 BigNum  inblk, outblk;
  94 RSAKeyStorage * keys;
  95 {
  96     static BigNumDigit x[1] ;
  97     char *charp;
  98     register int shift = 0;
  99     BigNum n = keys->n, e = keys->e;
 100     int nl = keys->nl, el = keys->el;
 101     int nTop = BnnNumDigits(n,nl) ;
 102     int BLOCKLEN = nTop*BN_DIGIT_SIZE - BnnNumLeadingZeroBitsInDigit(n[nTop-1]) - 1;
 103     int BLOCKBYTES = BLOCKLEN/8;
 104     int BLOCKWDS = BLOCKLEN/BN_DIGIT_SIZE + 1;
 105     BnnInit();
 106     x[0] = 0;
 107     charp = (char *) x;
 108     *charp = 1;
 109     if (x[0] != (BigNumDigit) 1 && BLOCKBYTES % sizeof(BigNumDigit) != 0)
 110     {
 111         /* This machine is big-endian */
 112         shift = ((sizeof(BigNumDigit) * BLOCKWDS) - BLOCKBYTES) * 8;
 113     }
 114     *charp = 0;
 115
 116     inblk[nl-1] >>= shift;
 117     BnnDyRaise_1 (outblk, inblk, e, el, n, keys->beta2n, keys->nINV, nl);
 118     BnnClose();
 119 }
 120
 121 static void rsadecrypt_1(inblk, outblk,keys)
 122 BigNum inblk, outblk;
 123 RSAKeyStorage * keys ;
 124 {
 125     static BigNumDigit x[3*DigitLim], xp[2*DigitLim], xq[2*DigitLim] ;
 126     char *charp;
 127     register int shift = 0;
 128     BigNum n = keys->n, p = keys->p, q = keys->q ,
 129            pINV = keys->pINV, qINV = keys->qINV;
 130     int nl = keys->nl, pl = keys->pl, ql = keys->ql ;
 131     int nTop = BnnNumDigits(n,nl) ;
 132     int BLOCKLEN = nTop*BN_DIGIT_SIZE - BnnNumLeadingZeroBitsInDigit(n[nTop-1]) - 1;
 133     int BLOCKBYTES = BLOCKLEN/8;
 134     int BLOCKWDS = BLOCKLEN/BN_DIGIT_SIZE + 1;
 135
 136     BnnInit();
 137     x[nl]=0;
 138     charp = (char *) (x+nl);
 139     *charp = 1;
 140     if (x[nl] != (BigNumDigit) 1)
 141     {
 142         /* This machine is big-endian */
 143         shift = ((sizeof(BigNumDigit) * BLOCKWDS) - BLOCKBYTES) * 8;
 144     }
 145     {
 146         /* xp <- inblk/B^PL [p] */
 147         BnnSetToZero(xp, 2*pl);
 148         BnnAssign(xp+pl, inblk+pl, nl-pl);
 149         BnnModularProduct_1 (xp, pl+pl, inblk, pl, one, pl, p, pl, pINV);
 150         /* xq <- inblk/B^QL [q] */
 151         BnnSetToZero(xq, 2*ql);
 152         BnnAssign(xq+ql, inblk+ql, nl-ql);
 153         BnnModularProduct_1 (xq, ql+ql, inblk, ql, one, ql, q, ql, qINV);
 154         /* pass beta3[pq] coeff. to compensate for prediv by B^[PQ]L */
 155         BnnDyRaise_1 (xp, xp+pl, keys->dp, keys->dpl, p, keys->beta3p, pINV, pl);
 156         BnnDyRaise_1 (xq, xq+ql, keys->dq, keys->dql, q, keys->beta3q, qINV, ql);
 157         BnnSetToZero(xp+pl, nl-pl);
 158         BnnSetToZero(xq+ql, nl-ql);
 159         BnnSubtract(xp,pl,xq,ql,1);
 160         while((BnnGetDigit(xp+(pl-1))&TopBitInWord)!=0) BnnAdd(xp,pl,p,pl,0);
 161         BnnSetToZero(x,3*pl);
 162         BnnModularProduct_1 (x+pl,pl+pl,xp,pl,keys->cr,pl,p,pl,pINV);
 163         BnnModularProduct_1 (x,pl+pl,keys->beta2p,pl,x+pl+pl,pl,p,pl,pINV);
 164         BnnDyCanon_1 (x+pl, p, pl);
 165         BnnMultiply(xq, nl, x+pl, pl, q , ql);
 166         xq[2*pl-1] <<= shift;
 167     }
 168     BnnClose();
 169     BnnAssign(outblk, xq, nl);
 170 }
 171
 172
 173 static void BnnModularProduct_1 (p,pl,a,al,b,bl,m,ml,mu)
 174 BigNum p,b,a,m,mu;
 175 unsigned pl,al,bl,ml;
 176 {
 177     /* p is length pl */
 178     /* a has length al, b has length bl, m has length ml, mu has length >= 2 */
 179     /* mu is -m[0..1..] mod BN_DIGIT_SIZE*2 */
 180     /* after computation
 181         p[0..bl-1] = 0
 182         (p[bl..pl-1] * beta^bl) mod m = p+(a*b) mod m
 183     */
 184     BigNumDigit qt[2*DigitLim];
 185     assert(pl <= 2*DigitLim);
 186
 187     BnnMultiply(p, pl, a, al, b, bl);
 188     BnnSetToZero(qt, pl);
 189     BnnMultiply(qt, pl, p, pl-ml, mu, ml);
 190     BnnMultiply(p, pl, m, ml, qt, pl-ml);
 191 }
 192
 193 static unsigned BnnDyCanon_1 (x, m, ml)
 194 BigNum x, m;
 195 unsigned ml;
 196 {
 197     int redcount = 0;
 198     while (BnnCompare(x, ml, m, ml) > 0)
 199     {
 200         BnnSubtract(x, ml, m, ml, 1);
 201         redcount++;
 202     }
 203     return redcount;
 204 }
 205
 206 #define MAX_LN2PWR 4
 207 #define MAXPWR (1<<MAX_LN2PWR)
 208
 209 static void BnnDyRaise_1 (x, a, e, el, m, beta2ml, mu, ml)
 210 BigNum x, a, e, m, beta2ml;
 211 BigNum mu;
 212 unsigned ml, el;
 213 {
 214     static BigNumDigit sBUF[DigitLim];
 215     static BigNumDigit tBUF[DigitLim*10];
 216     register BigNum s = sBUF, t = tBUF;
 217     static BigNum aCache[MAXPWR];
 218     BigNumDigit ed;
 219     BigNumDigit mask;
 220     int eindex, eoffset, nibble, i;
 221     static BigNumDigit aCacheBUF[MAXPWR*2*DigitLim];
 222     int pwr,ln2pwr;
 223
 224     /* Exponentiate: x = a^e mod m */
 225     if (BnnNumDigits(e, el) > 1)
 226         ln2pwr = MAX_LN2PWR;
 227     else
 228         ln2pwr = 1;
 229     pwr = (1<<ln2pwr);
 230     /* We work high to low in the exponent and make a special case
 231         of the topmost bit in e */
 232     /* check that m is within range */
 233     assert((m[ml-1] & (3<<(BN_DIGIT_SIZE-2))) == 0);
 234
 235     /* prime the aCache */
 236     t = aCacheBUF+2*DigitLim-ml;
 237     aCache[1] = s = aCacheBUF+2*DigitLim;
 238     BnnSetToZero(t, 2*ml);
 239     BnnModularProduct_1 (t, ml+ml, a, ml, beta2ml, ml, m, ml, mu);
 240     for (i = 2; i < pwr; i++)
 241     {
 242         t += 2*DigitLim;
 243         BnnSetToZero(t, 2*ml);
 244         BnnModularProduct_1 (t, ml+ml, s, ml, aCache[1], ml, m, ml, mu);
 245         aCache[i] = (s += 2*DigitLim);
 246     }
 247
 248     eindex = BnnNumDigits(e, el)-1;
 249     ed = e[eindex];
 250     eoffset = ((BN_DIGIT_SIZE-BnnNumLeadingZeroBitsInDigit(ed)-1) & ~(ln2pwr-1));
 251     mask = (pwr-1) << eoffset;
 252     nibble = (ed&mask)>>eoffset;
 253     mask >>= ln2pwr;
 254     eoffset -= ln2pwr;
 255     s = aCache[nibble];
 256
 257     while (eindex >= 0)
 258     {
 259         ed = e[eindex--];
 260         while (mask)
 261         {
 262             /* Square ln2pwr times */
 263             t = tBUF;
 264             BnnSetToZero(t, 2*(ln2pwr+1)*ml);
 265             for (i = 0; i < ln2pwr; i++)
 266             {
 267                 BnnModularProduct_1 (t, ml+ml, s, ml, s, ml, m, ml, mu);
 268                 s = t+ml; t += 2*ml;
 269             }
 270             nibble = (ed&mask)>>eoffset;
 271             if (nibble)
 272             {
 273                 /* Multiply */
 274                 BnnModularProduct_1 (t, ml+ml, s, ml, aCache[nibble], ml, m, ml, mu);
 275                 BnnAssign(sBUF, t+ml, ml);
 276             }
 277             else
 278                 BnnAssign(sBUF, s, ml);
 279             mask >>= ln2pwr;
 280             eoffset -= ln2pwr;
 281             s = sBUF;
 282         }
 283         eoffset = BN_DIGIT_SIZE-ln2pwr;
 284         mask = (pwr-1) << eoffset;
 285     }
 286     /* restore representation */
 287
 288     t = tBUF;
 289     BnnSetToZero(t, 2*ml);
 290     BnnModularProduct_1 (t, ml+ml, s, ml, one, ml, m, ml, mu);
 291     BnnAssign(x, t+ml, ml);
 292 }
 293
 294 #endif