📄 libnn.cpp
字号:
/*
Library Function
--------------------------------------------------------------------------
FILE libnn.c
--------------------------------------------------------------------------
INTRODUCTION
============
Created : 2005-07-27 Xiaoxi Jiang
Last modified : 2005-07-27 Xiaoxi Jiang
Module :
Purpose :
Source file.
List of routines in file :
File history :
*/
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "librsa.h"
#include "libnn.h"
static NN_DIGIT NN_AddDigitMult(NN_DIGIT *, NN_DIGIT *, NN_DIGIT, NN_DIGIT *, unsigned int);
static NN_DIGIT NN_SubDigitMult(NN_DIGIT *, NN_DIGIT *, NN_DIGIT, NN_DIGIT *, unsigned int);
static unsigned int NN_DigitBits(NN_DIGIT);
/* Decodes character string b into a, where character string is ordered
from most to least significant.
Lengths: a[digits], b[len].
Assumes b[i] = 0 for i < len - digits * NN_DIGITLEN. (Otherwise most
significant bytes are truncated.)
*/
void NN_Decode (NN_DIGIT *pDigit, unsigned int uiDigit, unsigned char *pucInData, unsigned int
uiInLen)
{
NN_DIGIT Digit;
unsigned int uiI;
unsigned int uiJ;
int iJ;
for (uiI = 0, iJ= uiInLen - 1; uiI < uiDigit && iJ >= 0; uiI++)
{
Digit = 0;
for (uiJ = 0; iJ >= 0 && uiJ < NN_DIGITBITS; iJ--, uiJ += 8)
Digit |= ((NN_DIGIT)pucInData[iJ]) << uiJ;
*(pDigit+uiI) = Digit;
}
for (; uiI < uiDigit; uiI++)
*(pDigit+uiI) = 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 (unsigned char *pucOutData, unsigned int uiLen, NN_DIGIT *pDigit, unsigned int
uiDigit)
{
NN_DIGIT Digit;
unsigned int uiI;
unsigned int uiJ;
int iJ;
for (uiI = 0, iJ = uiLen - 1; uiI < uiDigit && iJ >= 0; uiI++)
{
Digit = *(pDigit+uiI);
for (uiJ = 0; iJ >= 0 && uiJ < NN_DIGITBITS; iJ--, uiJ += 8)
pucOutData[iJ] = (unsigned char)(Digit >> uiJ);
}
for (; iJ >= 0; iJ--)
pucOutData[iJ] = 0;
}
/* Assigns a = b.
Lengths: a[digits], b[digits].
*/
void NN_Assign (NN_DIGIT *pDest, NN_DIGIT *pSrc, unsigned int uiDigit)
{
unsigned int uiI;
for (uiI = 0; uiI < uiDigit; uiI++)
*(pDest+uiI) = *(pSrc+uiI);
}
/* Assigns a = 0.
Lengths: a[digits].
*/
void NN_AssignZero (NN_DIGIT *pDigit, unsigned int uiDigit)
{
unsigned int uiI;
for (uiI = 0; uiI < uiDigit; uiI++)
*(pDigit+uiI) = 0;
}
/* Assigns a = 2^b.
Lengths: a[digits].
Requires b < digits * NN_DIGITBITS.
*/
void NN_Assign2Exp (NN_DIGIT *pDigit,unsigned int uiLen,unsigned int uiDigit)
{
NN_AssignZero (pDigit, uiDigit);
if (uiLen >= uiDigit * NN_DIGITBITS)
return;
*(pDigit+uiLen/NN_DIGITBITS) = (NN_DIGIT)1 << (uiLen%NN_DIGITBITS);
}
/* Computes pDest = pSrc1 + pSrc2. Returns carry.
Lengths: pDest[digits], pSrc1[digits], pSrc2[digits].
*/
NN_DIGIT NN_Add (NN_DIGIT *pDest, NN_DIGIT *pSrc1, NN_DIGIT *pSrc2,unsigned int uiDigit)
{
NN_DIGIT Digit;
NN_DIGIT Carry;
unsigned int uiI;
Carry = 0;
for (uiI = 0; uiI < uiDigit; uiI++)
{
if ((Digit = pSrc1[uiI] + Carry) < Carry)
Digit = pSrc2[uiI];
else
if ((Digit += pSrc2[uiI]) < pSrc2[uiI])
Carry = 1;
else
Carry = 0;
pDest[uiI] = Digit;
}
return (Carry);
}
/* Computes pDest = pSrc1 - pSrc2. Returns borrow.
Lengths: pDest[uiDigit], pSrc1[uiDigit], pSrc2[uiDigit].
*/
NN_DIGIT NN_Sub (NN_DIGIT *pDest,NN_DIGIT * pSrc1,NN_DIGIT * pSrc2,unsigned int uiDigit)
{
NN_DIGIT Digit;
NN_DIGIT Borrow;
unsigned int uiI;
Borrow = 0;
for (uiI = 0; uiI < uiDigit; uiI++)
{
if ((Digit = pSrc1[uiI] - Borrow) > (NN_MAXDIGIT - Borrow))
Digit = NN_MAXDIGIT - pSrc2[uiI];
else
if ((Digit -= pSrc2[uiI]) > (NN_MAXDIGIT - pSrc2[uiI]))
Borrow = 1;
else
Borrow = 0;
pDest[uiI] = Digit;
}
return (Borrow);
}
/* Computes pDest = pSrc1 * pSrc2.
Lengths: pDest[2*uiDigit], pSrc1[uiDigit], pSrc2[uiDigit].
Assumes uiDigit < NN_MAXDIGITS.
*/
void NN_Mult (NN_DIGIT *pDest,NN_DIGIT * pSrc1,NN_DIGIT * pSrc2,unsigned int uiDigit)
{
NN_DIGIT aDigit[2*NN_MAXDIGITS];
unsigned int uiDigit1;
unsigned int uiDigit2;
unsigned int uiI;
NN_AssignZero (aDigit, 2 * uiDigit);
uiDigit1 = NN_Digits (pSrc1, uiDigit);
uiDigit2 = NN_Digits (pSrc2, uiDigit);
for (uiI = 0; uiI < uiDigit1; uiI++)
aDigit[uiI+uiDigit2] += NN_AddDigitMult (&aDigit[uiI], &aDigit[uiI], pSrc1[uiI], pSrc2,
uiDigit2);
NN_Assign (pDest, aDigit, 2 * uiDigit);
memset (aDigit, 0, sizeof (aDigit));
}
/* Computes pDest = pSrc1 * 2^uiSrc2 (i.e., shifts left c bits), returning carry.
Lengths: pDest[uiDigit], pSrc1[uiDigit].
Requires pSrc2 < NN_DIGITBITS.
*/
NN_DIGIT NN_LShift (NN_DIGIT *pDest,NN_DIGIT * pSrc1,unsigned int uiSrc2,unsigned int uiDigit)
{
NN_DIGIT Digit;
NN_DIGIT Carry;
unsigned int uiI;
unsigned int uiJ;
if (uiSrc2 >= NN_DIGITBITS)
return (0);
uiJ = NN_DIGITBITS - uiSrc2;
Carry = 0;
for (uiI = 0; uiI < uiDigit; uiI++)
{
Digit = pSrc1[uiI];
pDest[uiI] = (Digit << uiSrc2) | Carry;
Carry = uiSrc2 ? (Digit >> uiJ) : 0;
}
return (Carry);
}
/* Computes pDest = pSrc1 div 2^uiSrc2 (i.e., shifts right c bits), returning carry.
Lengths: pDest[uiDigit], pSrc1[uiDigit].
Requires: uiSrc2 < NN_DIGITBITS.
*/
NN_DIGIT NN_RShift (NN_DIGIT *pDest,NN_DIGIT * pSrc1,unsigned int uiSrc2,unsigned int uiDigit)
{
NN_DIGIT Digit;
NN_DIGIT Carry;
int iI;
unsigned int uiJ;
if (uiSrc2 >= NN_DIGITBITS)
return (0);
uiJ = NN_DIGITBITS - uiSrc2;
Carry = 0;
for (iI = uiDigit - 1; iI >= 0; iI--)
{
Digit = pSrc1[iI];
pDest[iI] = (Digit >> uiSrc2) | Carry;
Carry = uiSrc2 ? (Digit << uiJ) : 0;
}
return (Carry);
}
/* Computes pDest1 = pSrc1 div pSrc2 and pDest2 = pSrc1 mod pSrc2.
Lengths: pDest1[uiDigit1], pDest2[uiDigit2], pSrc1[uiDigit1], pSrc2[uiDigit2].
Assumes pSrc2 > 0, uiDigit1 < 2 * NN_MAXDIGITS,
uiDigit2 < NN_MAXDIGITS.
*/
void NN_Div(NN_DIGIT *pDest1,NN_DIGIT * pDest2,NN_DIGIT * pSrc1,unsigned int uiDigit1,NN_DIGIT *
pSrc2,unsigned int uiDigit2)
{
NN_DIGIT Digit1;
NN_DIGIT Digit2;
NN_DIGIT aDigit1[2*NN_MAXDIGITS+1], aDigit2[NN_MAXDIGITS];
int iI;
unsigned int uiDigit3, uiShift;
uiDigit3 = NN_Digits (pSrc2, uiDigit2);
if (uiDigit3 == 0)
return;
/* Normalize operands.
*/
uiShift = NN_DIGITBITS - NN_DigitBits (pSrc2[uiDigit3-1]);
NN_AssignZero (aDigit1, uiDigit3);
aDigit1[uiDigit1] = NN_LShift (aDigit1, pSrc1, uiShift, uiDigit1);
NN_LShift (aDigit2, pSrc2, uiShift, uiDigit3);
Digit2 = aDigit2[uiDigit3-1];
NN_AssignZero (pDest1, uiDigit1);
for (iI = uiDigit1-uiDigit3; iI >= 0; iI--)
{
/* Underestimate quotient digit and subtract.
*/
if (Digit2 == NN_MAXDIGIT)
Digit1 = aDigit1[iI+uiDigit3];
else
NN_DigitDiv (&Digit1, &aDigit1[iI+uiDigit3-1], Digit2 + 1);
aDigit1[iI+uiDigit3] -= NN_SubDigitMult (&aDigit1[iI], &aDigit1[iI], Digit1, aDigit2,
uiDigit3);
/* Correct estimate.
*/
while (aDigit1[iI+uiDigit3] || (NN_Cmp (&aDigit1[iI], aDigit2, uiDigit3) >= 0))
{
Digit1++;
aDigit1[iI+uiDigit3] -= NN_Sub (&aDigit1[iI], &aDigit1[iI], aDigit2, uiDigit3);
}
pDest1[iI] = Digit1;
}
/* Restore result.
*/
NN_AssignZero (pDest2, uiDigit2);
NN_RShift (pDest2, aDigit1, uiShift, uiDigit3);
/* Zeroize potentially sensitive information.
*/
memset (aDigit1, 0, sizeof (aDigit1));
memset (aDigit2, 0, sizeof (aDigit2));
}
/* Computes pDest = pSrc1 mod pSrc2.
Lengths: pDest[uiDigit2], pSrc1[uiDigit1], pSrc2[uiDigit2].
Assumes pSrc2 > 0, uiDigit1 < 2 * NN_MAXDIGITS, uiDigit2 < NN_MAXDIGITS.
*/
void NN_Mod (NN_DIGIT *pDest,NN_DIGIT *pSrc1,unsigned int uiDigit1,NN_DIGIT *pSrc2,unsigned int
uiDigit2)
{
NN_DIGIT aDigit[2 * NN_MAXDIGITS];
NN_Div (aDigit, pDest, pSrc1, uiDigit1, pSrc2, uiDigit2);
/* Zeroize potentially sensitive information.
*/
memset(aDigit, 0, sizeof (aDigit));
}
/* Computes pDest = pSrc1 * pSrc2 mod pSrc3.
Lengths: pDest[uiDigit], pSrc1[uiDigit], pSrc2[uiDigit], pSrc3[uiDigit].
Assumes pSrc3 > 0, uiDigit < NN_MAXDIGITS.
*/
void NN_ModMult (NN_DIGIT *pDest, NN_DIGIT *pSrc1, NN_DIGIT *pSrc2, NN_DIGIT *pSrc3,unsigned int
uiDigit)
{
NN_DIGIT aDigit[2*NN_MAXDIGITS];
NN_Mult (aDigit, pSrc1, pSrc2, uiDigit);
NN_Mod (pDest, aDigit, 2 * uiDigit, pSrc3, uiDigit);
/* Zeroize potentially sensitive information.
*/
memset(aDigit, 0, sizeof (aDigit));
}
/* Computes pDest = pSrc1^pSrc2 mod pSrc3.
Lengths: pDest[uiDigit2], pSrc1[uiDigit2], pSrc2[uiDigit1], pSrc3[uiDigit2].
Assumes pSrc3 > 0, uiDigit1 > 0, uiDigit2 < NN_MAXDIGITS.
*/
void NN_ModExp (NN_DIGIT *pDest,NN_DIGIT * pSrc1,NN_DIGIT * pSrc2,unsigned int uiDigit1,NN_DIGIT
* pSrc3,unsigned int uiDigit2)
{
NN_DIGIT aPower[3][NN_MAXDIGITS];
NN_DIGIT Digit;
NN_DIGIT aDigit[NN_MAXDIGITS];
int iI;
unsigned int uiBits;
unsigned int uiJ;
unsigned int uiS;
/* Store pSrc1, pSrc1^2 mod pSrc3, and pSrc1^3 mod pSrc3.
*/
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -