rsa.c

rsa加密算法源码

  ((NN_DIGIT *, unsigned int, NN_DIGIT *, unsigned int));
static int RelativelyPrime PROTO_LIST
  ((NN_DIGIT *, unsigned int, NN_DIGIT *, unsigned int));

/* Generates an RSA key pair with a given length and public exponent.
 */
int R_GeneratePEMKeys (publicKey, privateKey, protoKey, randomStruct)
R_RSA_PUBLIC_KEY *publicKey;       /* new RSA public key */
R_RSA_PRIVATE_KEY *privateKey;     /* new RSA private key */
R_RSA_PROTO_KEY *protoKey;         /* RSA prototype key */
R_RANDOM_STRUCT *randomStruct;     /* random structure */
{
  NN_DIGIT d[MAX_NN_DIGITS], dP[MAX_NN_DIGITS], dQ[MAX_NN_DIGITS],
    e[MAX_NN_DIGITS], n[MAX_NN_DIGITS], p[MAX_NN_DIGITS], phiN[MAX_NN_DIGITS],
    pMinus1[MAX_NN_DIGITS], q[MAX_NN_DIGITS], qInv[MAX_NN_DIGITS],
    qMinus1[MAX_NN_DIGITS], t[MAX_NN_DIGITS], u[MAX_NN_DIGITS],
    v[MAX_NN_DIGITS];
  int status;
  unsigned int nDigits, pBits, pDigits, qBits;
  
  if ((protoKey->bits < MIN_RSA_MODULUS_BITS) || 
      (protoKey->bits > MAX_RSA_MODULUS_BITS))
    return (RE_MODULUS_LEN);
  nDigits = (protoKey->bits + NN_DIGIT_BITS - 1) / NN_DIGIT_BITS;
  pDigits = (nDigits + 1) / 2;
  pBits = (protoKey->bits + 1) / 2;
  qBits = protoKey->bits - pBits;

  /* NOTE: for 65537, this assumes NN_DIGIT is at least 17 bits. */
  NN_ASSIGN_DIGIT
    (e, protoKey->useFermat4 ? (NN_DIGIT)65537 : (NN_DIGIT)3, nDigits);

  /* Generate prime p between 3*2^(pBits-2) and 2^pBits-1, searching
       in steps of 2, until one satisfies gcd (p-1, e) = 1.
   */
  NN_Assign2Exp (t, pBits-1, pDigits);
  NN_Assign2Exp (u, pBits-2, pDigits);
  NN_Add (t, t, u, pDigits);
  NN_ASSIGN_DIGIT (v, 1, pDigits);
  NN_Sub (v, t, v, pDigits);
  NN_Add (u, u, v, pDigits);
  NN_ASSIGN_DIGIT (v, 2, pDigits);
  do {
    if (status = GeneratePrime (p, t, u, v, pDigits, randomStruct))
      return (status);
  }
  while (! RSAFilter (p, pDigits, e, 1));
  
  /* Generate prime q between 3*2^(qBits-2) and 2^qBits-1, searching
       in steps of 2, until one satisfies gcd (q-1, e) = 1.
   */
  NN_Assign2Exp (t, qBits-1, pDigits);
  NN_Assign2Exp (u, qBits-2, pDigits);
  NN_Add (t, t, u, pDigits);
  NN_ASSIGN_DIGIT (v, 1, pDigits);
  NN_Sub (v, t, v, pDigits);
  NN_Add (u, u, v, pDigits);
  NN_ASSIGN_DIGIT (v, 2, pDigits);
  do {
    if (status = GeneratePrime (q, t, u, v, pDigits, randomStruct))
      return (status);
  }
  while (! RSAFilter (q, pDigits, e, 1));
  
  /* Sort so that p > q. (p = q case is extremely unlikely.)
   */
  if (NN_Cmp (p, q, pDigits) < 0) {
    NN_Assign (t, p, pDigits);
    NN_Assign (p, q, pDigits);
    NN_Assign (q, t, pDigits);
  }

  /* Compute n = pq, qInv = q^{-1} mod p, d = e^{-1} mod (p-1)(q-1),
     dP = d mod p-1, dQ = d mod q-1.
   */
  NN_Mult (n, p, q, pDigits);
  NN_ModInv (qInv, q, p, pDigits);
  
  NN_ASSIGN_DIGIT (t, 1, pDigits);
  NN_Sub (pMinus1, p, t, pDigits);
  NN_Sub (qMinus1, q, t, pDigits);
  NN_Mult (phiN, pMinus1, qMinus1, pDigits);

  NN_ModInv (d, e, phiN, nDigits);
  NN_Mod (dP, d, nDigits, pMinus1, pDigits);
  NN_Mod (dQ, d, nDigits, qMinus1, pDigits);
  
  publicKey->bits = privateKey->bits = protoKey->bits;
  NN_Encode (publicKey->modulus, MAX_RSA_MODULUS_LEN, n, nDigits);
  NN_Encode (publicKey->exponent, MAX_RSA_MODULUS_LEN, e, 1);
  R_memcpy 
    ((POINTER)privateKey->modulus, (POINTER)publicKey->modulus,
     MAX_RSA_MODULUS_LEN);
  R_memcpy
    ((POINTER)privateKey->publicExponent, (POINTER)publicKey->exponent,
     MAX_RSA_MODULUS_LEN);
  NN_Encode (privateKey->exponent, MAX_RSA_MODULUS_LEN, d, nDigits);
  NN_Encode (privateKey->prime[0], MAX_RSA_PRIME_LEN, p, pDigits);
  NN_Encode (privateKey->prime[1], MAX_RSA_PRIME_LEN, q, pDigits);
  NN_Encode (privateKey->primeExponent[0], MAX_RSA_PRIME_LEN, dP, pDigits);
  NN_Encode (privateKey->primeExponent[1], MAX_RSA_PRIME_LEN, dQ, pDigits);
  NN_Encode (privateKey->coefficient, MAX_RSA_PRIME_LEN, qInv, pDigits);
   
  /* Zeroize sensitive information.
   */
  R_memset ((POINTER)d, 0, sizeof (d));
  R_memset ((POINTER)dP, 0, sizeof (dP));
  R_memset ((POINTER)dQ, 0, sizeof (dQ));
  R_memset ((POINTER)p, 0, sizeof (p));
  R_memset ((POINTER)phiN, 0, sizeof (phiN));
  R_memset ((POINTER)pMinus1, 0, sizeof (pMinus1));
  R_memset ((POINTER)q, 0, sizeof (q));
  R_memset ((POINTER)qInv, 0, sizeof (qInv));
  R_memset ((POINTER)qMinus1, 0, sizeof (qMinus1));
  R_memset ((POINTER)t, 0, sizeof (t));
  
  return (0);
}

/* Returns nonzero iff GCD (a-1, b) = 1.

   Lengths: a[aDigits], b[bDigits].
   Assumes aDigits < MAX_NN_DIGITS, bDigits < MAX_NN_DIGITS.
 */
static int RSAFilter (a, aDigits, b, bDigits)
NN_DIGIT *a, *b;
unsigned int aDigits, bDigits;
{
  int status;
  NN_DIGIT aMinus1[MAX_NN_DIGITS], t[MAX_NN_DIGITS];
  
  NN_ASSIGN_DIGIT (t, 1, aDigits);
  NN_Sub (aMinus1, a, t, aDigits);
  
  status = RelativelyPrime (aMinus1, aDigits, b, bDigits);

  /* Zeroize sensitive information.
   */
  R_memset ((POINTER)aMinus1, 0, sizeof (aMinus1));
  
  return (status);
}

/* Returns nonzero iff a and b are relatively prime.

   Lengths: a[aDigits], b[bDigits].
   Assumes aDigits >= bDigits, aDigits < MAX_NN_DIGITS.
 */
static int RelativelyPrime (a, aDigits, b, bDigits)
NN_DIGIT *a, *b;
unsigned int aDigits, bDigits;
{
  int status;
  NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS];
  
  NN_AssignZero (t, aDigits);
  NN_Assign (t, b, bDigits);
  NN_Gcd (t, a, t, aDigits);
  NN_ASSIGN_DIGIT (u, 1, aDigits);

  status = NN_EQUAL (t, u, aDigits);
  
  /* Zeroize sensitive information.
   */
  R_memset ((POINTER)t, 0, sizeof (t));
  
  return (status);
}

/* Generates Diffie-Hellman parameters.
 */
int R_GenerateDHParams (params, primeBits, subPrimeBits, randomStruct)
R_DH_PARAMS *params;            /* new Diffie-Hellman parameters */
unsigned int primeBits;         /* length of prime in bits */
unsigned int subPrimeBits;      /* length of subprime in bits */
R_RANDOM_STRUCT *randomStruct;  /* random structure */
{
  int status;
  NN_DIGIT g[MAX_NN_DIGITS], p[MAX_NN_DIGITS], q[MAX_NN_DIGITS],
    t[MAX_NN_DIGITS], u[MAX_NN_DIGITS], v[MAX_NN_DIGITS];
  unsigned int pDigits;

  pDigits = (primeBits + NN_DIGIT_BITS - 1) / NN_DIGIT_BITS;
  
  /* Generate subprime q between 2^(subPrimeBits-1) and
       2^subPrimeBits-1, searching in steps of 2.
   */
  NN_Assign2Exp (t, subPrimeBits-1, pDigits);
  NN_Assign (u, t, pDigits);
  NN_ASSIGN_DIGIT (v, 1, pDigits);
  NN_Sub (v, t, v, pDigits);
  NN_Add (u, u, v, pDigits);
  NN_ASSIGN_DIGIT (v, 2, pDigits);
  if (status = GeneratePrime (q, t, u, v, pDigits, randomStruct))
    return (status);
  
  /* Generate prime p between 2^(primeBits-1) and 2^primeBits-1,
       searching in steps of 2*q.
   */
  NN_Assign2Exp (t, primeBits-1, pDigits);
  NN_Assign (u, t, pDigits);
  NN_ASSIGN_DIGIT (v, 1, pDigits);
  NN_Sub (v, t, v, pDigits);
  NN_Add (u, u, v, pDigits);
  NN_LShift (v, q, 1, pDigits);
  if (status = GeneratePrime (p, t, u, v, pDigits, randomStruct))
    return (status);
  
  /* Generate generator g for subgroup as 2^((p-1)/q) mod p.
   */
  NN_ASSIGN_DIGIT (g, 2, pDigits);
  NN_Div (t, u, p, pDigits, q, pDigits);
  NN_ModExp (g, g, t, pDigits, p, pDigits);

  params->generatorLen = params->primeLen = DH_PRIME_LEN (primeBits);
  NN_Encode (params->prime, params->primeLen, p, pDigits);
  NN_Encode (params->generator, params->generatorLen, g, pDigits);

  return (0);
}

/* Sets up Diffie-Hellman key agreement. Public value has same length
   as prime.
 */
int R_SetupDHAgreement
  (publicValue, privateValue, privateValueLen, params, randomStruct)
unsigned char *publicValue;    /* new public value */
unsigned char *privateValue;   /* new private value */
unsigned int privateValueLen;  /* length of private value */
R_DH_PARAMS *params;           /* Diffie-Hellman parameters */
R_RANDOM_STRUCT *randomStruct; /* random structure */
{
  int status;
  NN_DIGIT g[MAX_NN_DIGITS], p[MAX_NN_DIGITS], x[MAX_NN_DIGITS],
    y[MAX_NN_DIGITS];
  unsigned int pDigits, xDigits;

  NN_Decode (p, MAX_NN_DIGITS, params->prime, params->primeLen);
  pDigits = NN_Digits (p, MAX_NN_DIGITS);
  NN_Decode (g, pDigits, params->generator, params->generatorLen);

  /* Generate private value.
   */
  if (status = R_GenerateBytes (privateValue, privateValueLen, randomStruct))
    return (status);
  NN_Decode (x, pDigits, privateValue, privateValueLen);
  xDigits = NN_Digits (x, pDigits);
  
  /* Compute y = g^x mod p.
   */
  NN_ModExp (y, g, x, xDigits, p, pDigits);

  NN_Encode (publicValue, params->primeLen, y, pDigits);
  
  /* Zeroize sensitive information.
   */
  R_memset ((POINTER)x, 0, sizeof (x));

  return (0);
}

/* Computes agreed key from the other party's public value, a private
   value, and Diffie-Hellman parameters. Other public value and
   agreed-upon key have same length as prime.

   Requires otherPublicValue < prime.
 */
int R_ComputeDHAgreedKey
  (agreedKey, otherPublicValue, privateValue, privateValueLen, params)
unsigned char *agreedKey;           /* new agreed key */
unsigned char *otherPublicValue;    /* other's public value */
unsigned char *privateValue;        /* private value */
unsigned int privateValueLen;       /* length of private value */
R_DH_PARAMS *params;                /* Diffie-Hellman parameters */
{
  NN_DIGIT p[MAX_NN_DIGITS], x[MAX_NN_DIGITS], y[MAX_NN_DIGITS],
    z[MAX_NN_DIGITS];
  unsigned int pDigits, xDigits;

  NN_Decode (p, MAX_NN_DIGITS, params->prime, params->primeLen);
  pDigits = NN_Digits (p, MAX_NN_DIGITS);
  NN_Decode (x, pDigits, privateValue, privateValueLen);
  xDigits = NN_Digits (x, pDigits);
  NN_Decode (y, pDigits, otherPublicValue, params->primeLen);

  if (NN_Cmp (y, p, pDigits) >= 0)
    return (RE_DATA);
  
  /* Compute z = y^x mod p.
   */
  NN_ModExp (z, y, x, xDigits, p, pDigits);

  NN_Encode (agreedKey, params->primeLen, z, pDigits);
  
  /* Zeroize sensitive information.
   */
  R_memset ((POINTER)x, 0, sizeof (x));
  R_memset ((POINTER)z, 0, sizeof (z));

  return (0);
}

/*
 * memory funciton
 */

void R_memset (output, value, len)
POINTER output;                                             /* output block */
int value;                                                         /* value */
unsigned int len;                                        /* length of block */
{
  if (len)
    memset (output, value, len);
}

void R_memcpy (output, input, len)
POINTER output;                                             /* output block */
POINTER input;                                               /* input block */
unsigned int len;                                       /* length of blocks */
{
  if (len)
    memcpy (output, input, len);
}

int R_memcmp (firstBlock, secondBlock, len)
POINTER firstBlock;                                          /* first block */
POINTER secondBlock;                                        /* second block */
unsigned int len;                                       /* length of blocks */
{
  if (len)
    return (memcmp (firstBlock, secondBlock, len));
  else
    return (0);
}