rsa.c

RSA code with C in the POS

#include	<string.h>
#include	<stdlib.h>
#include	"../inc/gnn.h"
#include	"../inc/nn.h"
#include	"../inc/digit.h"

extern void tstr(char *str);
extern void test(int num);
extern void Dis_deg_buf(char *buf,int buflen);
static NN_DIGIT NN_LShift PROTO_LIST 
  ((NN_DIGIT *, NN_DIGIT *, unsigned int, unsigned int));
static NN_DIGIT NN_RShift PROTO_LIST
  ((NN_DIGIT *, NN_DIGIT *, unsigned int, unsigned int));
static void NN_Div PROTO_LIST
  ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int, NN_DIGIT *,
    unsigned int));

static NN_DIGIT NN_AddDigitMult PROTO_LIST 
  ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT, NN_DIGIT *, unsigned int));
static NN_DIGIT NN_SubDigitMult PROTO_LIST 
  ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT, NN_DIGIT *, unsigned int));

static unsigned int NN_DigitBits PROTO_LIST ((NN_DIGIT));

/* Decodes character string b into a, where character string is ordered
   from most to least significant.

   Length: a[digits], b[len].
   Assumes b[i] = 0 for i < len - digits * NN_DIGIT_LEN. (Otherwise most
   significant bytes are truncated.)
 */
void NN_Decode (a, digits, b, len)
NN_DIGIT *a;
unsigned char *b;
unsigned int digits, len;
{
  NN_DIGIT t;
  int j;
  unsigned int i, u;
  
  for (i = 0, j = len - 1; j >= 0; i++) {
    t = 0;
    for (u = 0; j >= 0 && u < NN_DIGIT_BITS; j--, u += 8)
      t |= ((NN_DIGIT)b[j]) << u;
    a[i] = t;
  }
  
  for (; i < digits; i++)
    a[i] = 0;
}

/* Encodes b into character string a, where character string is ordered
   from most to least significant.

   Lengths: a[len], b[digits].
   Assumes NN_Bits (b, digits) <= 8 * len. (Otherwise most significant
   digits are truncated.)
 */
void NN_Encode (a, len, b, digits)
NN_DIGIT *b;
unsigned char *a;
unsigned int digits, len;
{
  NN_DIGIT t;
  int j;
  unsigned int i, u;

  for (i = 0, j = len - 1; i < digits; i++) {
    t = b[i];
    for (u = 0; j >= 0 && u < NN_DIGIT_BITS; j--, u += 8)
      a[j] = (unsigned char)(t >> u);
  }

  for (; j >= 0; j--)
    a[j] = 0;
}

/* Assigns a = 0.

   Lengths: a[digits], b[digits].
 */
void NN_Assign (a, b, digits)
NN_DIGIT *a, *b;
unsigned int digits;
{
  unsigned int i;

  for (i = 0; i < digits; i++)
    a[i] = b[i];
}

/* Assigns a = 0.

   Lengths: a[digits].
 */
void NN_AssignZero (a, digits)
NN_DIGIT *a;
unsigned int digits;
{
  unsigned int i;

  for (i = 0; i < digits; i++)
    a[i] = 0;
}

/* Assigns a = 2^b.

   Lengths: a[digits].
   Requires b < digits * NN_DIGIT_BITS.
 */
void NN_Assign2Exp (a, b, digits)
NN_DIGIT *a;
unsigned int b, digits;
{
  NN_AssignZero (a, digits);

  if (b >= digits * NN_DIGIT_BITS)
    return;

  a[b / NN_DIGIT_BITS] = (NN_DIGIT)1 << (b % NN_DIGIT_BITS);
}

/* Computes a = b + c. Returns carry.

   Lengths: a[digits], b[digits], c[digits].
 */
NN_DIGIT NN_Add (a, b, c, digits)
NN_DIGIT *a, *b, *c;
unsigned int digits;
{
  NN_DIGIT ai, carry;
  unsigned int i;

//	tstr("NN_ADD");
	  carry = 0;

  for (i = 0; i < digits; i++) {
    if ((ai = b[i] + carry) < carry)
      ai = c[i];
    else if ((ai += c[i]) < c[i])
      carry = 1;
    else
      carry = 0;
    a[i] = ai;
  }

  return (carry);
}

/* Computes a = b - c. Returns borrow.

   Lengths: a[digits], b[digits], c[digits].
 */
NN_DIGIT NN_Sub (a, b, c, digits)
NN_DIGIT *a, *b, *c;
unsigned int digits;
{
  NN_DIGIT ai, borrow;
  unsigned int i;

  borrow = 0;

  for (i = 0; i < digits; i++) {
    if ((ai = b[i] - borrow) > (MAX_NN_DIGIT - borrow))
      ai = MAX_NN_DIGIT - c[i];
    else if ((ai -= c[i]) > (MAX_NN_DIGIT - c[i]))
      borrow = 1;
    else
      borrow = 0;
    a[i] = ai;
  }

  return (borrow);
}

/* Computes a = b * c.

   Lengths: a[2*digits], b[digits], c[digits].
   Assumes digits < MAX_NN_DIGITS.
 */
void NN_Mult (a, b, c, digits)
NN_DIGIT *a, *b, *c;
unsigned int digits;
{
  NN_DIGIT t[2*MAX_NN_DIGITS];
  unsigned int bDigits, cDigits, i;

  NN_AssignZero (t, 2 * digits);
  
  bDigits = NN_Digits (b, digits);
  cDigits = NN_Digits (c, digits);

  for (i = 0; i < bDigits; i++)
    t[i+cDigits] += NN_AddDigitMult (&t[i], &t[i], b[i], c, cDigits);
  
  NN_Assign (a, t, 2 * digits);
  
  /* Zeroize potentially sensitive information.
   */
  R_memset ((POINTER)t, 0, sizeof (t));
}

/* Computes a = b mod c.

   Lengths: a[cDigits], b[bDigits], c[cDigits].
   Assumes c > 0, bDigits < 2 * MAX_NN_DIGITS, cDigits < MAX_NN_DIGITS.
 */
void NN_Mod (a, b, bDigits, c, cDigits)
NN_DIGIT *a, *b, *c;
unsigned int bDigits, cDigits;
{
  NN_DIGIT t[2 * MAX_NN_DIGITS];
  
//	tstr("NN_MOD");
  NN_Div (t, a, b, bDigits, c, cDigits);
  
  /* Zeroize potentially sensitive information.
   */
  R_memset ((POINTER)t, 0, sizeof (t));
}

/* Computes a = b * c mod d.

   Lengths: a[digits], b[digits], c[digits], d[digits].
   Assumes d > 0, digits < MAX_NN_DIGITS.
 */
void NN_ModMult (a, b, c, d, digits)
NN_DIGIT *a, *b, *c, *d;
unsigned int digits;
{
  NN_DIGIT t[2*MAX_NN_DIGITS];

//	tstr("NN_MODMULT");
  NN_Mult (t, b, c, digits);
  NN_Mod (a, t, 2 * digits, d, digits);
  
  /* Zeroize potentially sensitive information.
   */
  R_memset ((POINTER)t, 0, sizeof (t));
}


/*
 * PGP 2.6's mpilib contains a faster modular exponentiation routine,
 * mp_modexp.  If USEMPILIB is defined, NN_ModExp is replaced in the
 * PGP 2.6 sources with a stub call to mp_modexp.  If USEMPILIB is
 * not defined, we'll get a pure (albeit slower) RSAREF
 * implementation.
 *
 * The RSAREF license, clause 1(c), permits "...modify[ing] the
 * Program in any manner for porting or performance improvement
 * purposes..."
 */
#ifndef USEMPILIB
/* Computes a = b^c mod d.

   Lengths: a[dDigits], b[dDigits], c[cDigits], d[dDigits].
   Assumes b < d, d > 0, cDigits > 0, dDigits > 0,
           dDigits < MAX_NN_DIGITS.
 */

void NN_ModExp (a, b, d, dDigits,type)
NN_DIGIT *a, *b, *d;
unsigned int dDigits;
unsigned int type;
{
	NN_DIGIT bPower[18][MAX_NN_DIGITS];//, ci, t[MAX_NN_DIGITS];
	int i;
//  unsigned int ciBits, j, s;

	//Store b, b^2 mod d, and b^3 mod d.

//  cDigits = NN_Digits (c, cDigits);
	NN_Assign (bPower[0], b, dDigits);
//	nop((char)type);
	if(type==0)
	{
		for(i=0;i<2;i++)
		{
			NN_ModMult (bPower[i+1], bPower[i], b, d, dDigits);
		}
	}
	else if(type==1)
	{
		for(i=0;i<16;i++)
		{
			NN_ModMult (bPower[i+1], bPower[i], bPower[i], d, dDigits);
		}
		NN_ModMult (bPower[17], bPower[16], b, d, dDigits);
	}
//  Dis_deg_buf((char *)bPower[2],dDigits*4);
//  NN_Assign (bPower[0], b, dDigits);
//  NN_ModMult (bPower[1], bPower[0], b, d, dDigits);
//  NN_ModMult (bPower[2], bPower[1], b, d, dDigits);
//  Dis_deg_buf((char *)bPower[2],dDigits*4);
  
//  NN_ASSIGN_DIGIT (t, 1, dDigits);

//  cDigits = NN_Digits (c, cDigits);
//  for (i = cDigits - 1; i >= 0; i--) {
//    ci = c[i];
//    ciBits = NN_DIGIT_BITS;
    
    /* Scan past leading zero bits of most significant digit.
     */
//    if (i == (int)(cDigits - 1)) {
//      while (! DIGIT_2MSB (ci)) {
//        ci <<= 2;
//        ciBits -= 2;
//      }
//   }

//    for (j = 0; j < ciBits; j += 2, ci <<= 2) {
      /* Compute t = t^4 * b^s mod d, where s = two MSB's of d.
       */
//      NN_ModMult (t, t, t, d, dDigits);
//      NN_ModMult (t, t, t, d, dDigits);
//      if (s = DIGIT_2MSB (ci))
//       NN_ModMult (t, t, bPower[s-1], d, dDigits);
//    }
//  }
	if(type==0)			NN_Assign (a, bPower[2], dDigits);
	else if(type==1)	NN_Assign (a, bPower[17], dDigits);
//  NN_Assign (a, t, dDigits);
  
  /* Zeroize potentially sensitive information.
   */
  R_memset ((POINTER)bPower, 0, sizeof (bPower));
//  R_memset ((POINTER)t, 0, sizeof (t));
/*
	NN_DIGIT bPower[3][MAX_NN_DIGITS], ci, t[MAX_NN_DIGITS];
	int i;
	unsigned int ciBits, j, s;

//	Store b, b^2 mod d, and b^3 mod d.
//	Dis_deg_buf((char *)c,4);
	NN_Assign (bPower[0], b, dDigits);
	NN_ModMult (bPower[1], bPower[0], b, d, dDigits);
	NN_ModMult (bPower[2], bPower[1], b, d, dDigits);

	NN_ASSIGN_DIGIT (t, 1, dDigits);

	cDigits = NN_Digits (c, cDigits);
//  test(cDigits);
	for (i = cDigits - 1; i >= 0; i--)
	{
		ci = c[i];
		ciBits = NN_DIGIT_BITS;
//		Scan past leading zero bits of most significant digit.
	    if (i == (int)(cDigits - 1))
	    {
			while (! DIGIT_2MSB (ci))
			{
				ci <<= 2;
				ciBits -= 2;
			}
		}