📄 function_lib_c.c
字号:
/*本文件是函数库，为各应用函数提供调用函数*/
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "head.h"
/******************************************************
全局变量
******************************************************/
BIG val2;
BIG list[1<<(XX_STEP-1)];
/*
生成密钥对
*/
void KG(ENCODEBLOCK *pY,DECODEBLOCK *pX,INT nn)
{
void PG(BIG,INT,INT),NN_Assign(),NN_Assign2Exp(),NN_Mod(),NN_ModMult(),NN_AssignZero(),NN_ModInv(),NN_Mult();
NN_DIGIT m2mp();
INT k;
BIG p_1,q_1;
BIG R,tmp;
INT digits=(nn/2+NN_DIGIT_BITS_1)/NN_DIGIT_BITS;
Next:
/*产生两个大素数p,q,并要求p>q */
PG(pX->p,nn/2,MAX_MILER_RABIN_TEST);
/* printf("First Prime\n"); */
PG(pX->q,nn/2,MAX_MILER_RABIN_TEST);
/* printf("Second Prime\n"); */
k=NN_Cmp(pX->p,pX->q,digits);
if(k==0)goto Next;
if(k<0) /*swap p,q */
{
NN_Assign(tmp,pX->p,digits);
NN_Assign(pX->p,pX->q,digits);
NN_Assign(pX->q,tmp,digits);
}
/*计算p*q */
NN_Mult(pY->pq,pX->p,pX->q,digits);
/*计算(p-1)*(q-1) */
NN_Assign(p_1,pX->p,digits);p_1[0]&=(~1);
NN_Assign(q_1,pX->q,digits);q_1[0]&=(~1);
NN_Mult(pX->p1q1,p_1,q_1,digits);
/*保存公钥,实际实现中不需要，因为公钥固定为65537 */
NN_AssignZero(pY->Ke,digits*2);
pY->Ke[0]=65537;
/*计算私钥de=1 mod (p-1)*(q-1) */
NN_ModInv (pX->Kd, pY->Ke, pX->p1q1, digits*2) ;
/*为实现快速脱密而预先计算的数值
包括 d mod (p-1)
d mod (q-1)
q逆 mod p
*********************************/
NN_Mod(pX->dModp_1,pX->Kd,digits*2,p_1,digits);
NN_Mod(pX->dModq_1,pX->Kd,digits*2,q_1,digits);
NN_ModInv (pX->qInv, pX->q,pX->p, digits);
digits=(nn+NN_DIGIT_BITS-1)/NN_DIGIT_BITS;
pY->bits=nn;
pX->bits=nn;
/*为加密准备的预先计算 */
NN_Assign2Exp (R, digits*(NN_DIGIT_BITS/2), digits);
NN_ModMult (pY->Rmodm, R, R, pY->pq, digits);
pY->mp=m2mp(pY->pq);
}
/*
生产大素数,times为概率测试次数
*/
void PG(BIG A,INT bits,INT times)
{
INT grp;
INT restbits;
BIG B;
NN_DIGIT t[2];
void erandbig();
void NN_Assign(),NN_Mod(),NN_AssignZero();
int SmallFactor();
grp=(bits+NN_DIGIT_BITS-1)/NN_DIGIT_BITS;
restbits=bits&NN_DIGIT_BITS_1;
NN_ASSIGN_DIGIT(val2,2,grp);
while(1)
{
/*随机产生一个指定比特数bits的大数 */
erandbig(A,grp);
/* printf("rand %d\n",A[0]); */
A[0]|=1;
if(NN_Cmp(A,val2,grp)<0)continue;
if(restbits)
{
A[grp-1]&=(1<<restbits)-1;
A[grp-1]|=1<<(restbits-1);
}
else
A[grp-1]|=((NN_DIGIT)1<<NN_DIGIT_BITS_1);
/*检测是否含有小因子 */
if(SmallFactor(A, grp)) continue;
/*检测(A-1)!=0 mod 65537 */
NN_Assign(B,A,grp); B[0]&=~(1);
NN_ASSIGN_DIGIT (t, 65537, 1);
NN_Mod (t, B, grp, t, 1);
if (NN_Zero (t, 1))continue;
/*是否通过素性测定 */
if(Miler_Rabin(A,grp,times)) return;
}
}
/* Miler_Rabin概率法判定素数,tt为测试次数*/
INT Miler_Rabin(BIG n,INT digits,INT tt)
{
INT i,j,k,l,aa;
BIG b,m,z,n_1;
void erandbig();
void NN_Assign(),NN_Mod(),SlidingWindowExpWithMont(),NN_ModMult();
NN_Assign(n_1,n,digits);
for(i=0;i<digits;i++)
{
if(n_1[i]>0)
{
n_1[i]--;
break;
}
n_1[i]--;
}
j=digits*NN_DIGIT_BITS;
for(i=1;i<j;i++)if(BIT(n,i))break;
l=i;
j=i%NN_DIGIT_BITS;
for(i/=NN_DIGIT_BITS,k=0;i<digits-1;i++,k++)
m[k]=(n[i]>>j)^(n[i+1]<<(NN_DIGIT_BITS-j));
m[k++]=(n[i]>>j);
for(;k<digits;k++)
m[k]=0;
k=1;
for(aa=0;aa<tt;aa++)
{
next_rand:
erandbig(b,digits); /*random b=(1,n-1) */
NN_Mod(b,b,digits,n,digits);
if(NN_Cmp(b,val2,digits)<=0)goto next_rand;
MODEXP(z, b, m, n, digits);
if(z[0]==1) /*测试z是否等于1 */
{
for(j=1;j<digits;j++)
if(z[j])break;
if(j==digits)continue;
}
i=1;
step4:
if(NN_Cmp(z,n_1,digits)==0)
continue; /*测试z是否等于 n-1 */
if(i==l)return 0;
i++;
NN_ModMult(z,z,z,n,digits);
goto step4;
}
return 1;
}
/*小因子试除*/
static NN_DIGIT SMALL_PRIMES[] = { 3, 5, 7, 11};
#define SMALL_PRIME_COUNT 4
INT SmallFactor (NN_DIGIT *a,
UINT aDigits)
{
INT status;
NN_DIGIT t[1];
UINT i;
void NN_Mod(),NN_AssignZero();
status = 0;
for (i = 0; i < SMALL_PRIME_COUNT; i++) {
NN_ASSIGN_DIGIT (t, SMALL_PRIMES[i], 1);
NN_Mod (t, a, aDigits, t, 1);
if (NN_Zero (t, 1)) {
status = 1;
break;
}
}
return (status);
}
/* Returns sign of a - b.
Lengths: a[digits], b[digits].
*/
INT NN_Cmp (a, b, digits)
NN_DIGIT *a, *b;
UINT digits;
{
INT i;
for (i = digits - 1; i >= 0; i--)
{
if (a[i]< b[i]) return (-1);
if (a[i]> b[i]) return (1);
}
return (0);
}
/* Assigns a = b.
Lengths: a[digits], b[digits].
*/
void NN_Assign (a,b,digits)
NN_DIGIT *a,*b;
UINT digits;
{
UINT i;
for (i=0; i<digits; i++)
a[i] = b[i];
}
/* 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;
UINT bDigits, cDigits;
{
void NN_Div();
NN_DIGIT t[2 * MAX_NN_DIGITS];
NN_Div (t, a, b, bDigits, c, cDigits);
}
/* Computes a = c div d and b = c mod d.
Lengths: a[cDigits], b[dDigits], c[cDigits], d[dDigits].
Assumes d > 0, cDigits < 2 * MAX_NN_DIGITS,
dDigits < MAX_NN_DIGITS.
*/
void NN_Div (a, b, c, cDigits, d, dDigits)
NN_DIGIT *a, *b, *c, *d;
UINT cDigits, dDigits;
{
NN_DIGIT cc[2*MAX_NN_DIGITS+1];
NN_DIGIT ai, dd[MAX_NN_DIGITS], t;
INT i;
UINT ddDigits, shift;
void NN_AssignZero(),NN_DigitDiv();
NN_DIGIT NN_Sub(),NN_LShift(),NN_RShift(),NN_SubDigitMult();
UINT NN_Digits(),NN_DigitBits();
ddDigits = NN_Digits (d, dDigits);
if (ddDigits == 0)
return;
/* Normalize operands.
*/
shift = NN_DIGIT_BITS - NN_DigitBits (d[ddDigits-1]);
NN_AssignZero (cc, ddDigits);
cc[cDigits] = NN_LShift (cc, c, shift, cDigits);
NN_LShift (dd, d, shift, ddDigits);
t = dd[ddDigits-1];
NN_AssignZero (a, cDigits);
for (i = cDigits-ddDigits; i >= 0; i--) {
/* Underestimate quotient digit and subtract.
*/
if (t == MAX_NN_DIGIT)
ai = cc[i+dDigits];
else
NN_DigitDiv (&ai, &cc[i+ddDigits-1], t + 1);
cc[i+ddDigits] -= NN_SubDigitMult (&cc[i], &cc[i], ai, dd, ddDigits);
/* Correct estimate.
*/
while (cc[i+ddDigits] || (NN_Cmp (&cc[i], dd, ddDigits) >= 0)) {
ai++;
cc[i+ddDigits] -= NN_Sub (&cc[i], &cc[i], dd, ddDigits);
}
a[i] = ai;
}
/* Restore result.
*/
NN_AssignZero (b, dDigits);
NN_RShift (b, cc, shift, ddDigits);
return;
}
/* Returns nonzero if a is zero.
Lengths: a[digits].
*/
INT NN_Zero (a, digits)
NN_DIGIT *a;
UINT digits;
{
UINT i;
for (i = 0; i < digits; i++)
if (a[i])
return (0);
return (1);
}
/*==============================
使用滑动窗和Montgomery约化计算
_A=g^e (mod m)
WindowBit为窗的大小
==================================*/
void SlidingWindowExpWithMont(BIG _A,BIG g,BIG e,BIG m,
INT digits,
INT WindowBit)
{
NN_DIGIT m2mp();
INT i0,i,j,l,FindNextl,id;
BIG A;
NN_DIGIT mp=m2mp(m);
BIG R,Rmodm,gg;
void NN_Assign2Exp(),NN_ModMult(),SquareMod(),Mont(),NN_AssignZero();
/**********初始化表
list[0]=Mont(g,R^2) // mod m
g2=Mont(g1,g1);
list[i+1]=Mont(list[i],g2);
*****************************/
NN_Assign2Exp (R, digits*(NN_DIGIT_BITS/2), digits);
NN_ModMult (Rmodm, R, R, m, digits);
NN_ModMult(list[0],g,Rmodm,m,digits);
SQUAREMOD(gg,list[0],m,mp,digits);
for(i=1;i<(1<<(WindowBit-1));i++)
Mont(list[i],list[i-1],gg,m,mp,digits);
for(i=digits*NN_DIGIT_BITS-1;i>=0;i--)if(BIT(e,i))break;
i0=i;
while(i>=0)
if(BIT(e,i)==0)
{
SquareMod(A,A,m,mp,digits);
i--;
}
else
{
/*
查找比特串e(i), e(i+1),...e(i+t)
使e(i+t)=1 而且t<WindowBit
*/
l=i;
for(FindNextl=i;FindNextl>=0;FindNextl--)
if(i-FindNextl+1>WindowBit)break;
else if(BIT(e,FindNextl))
l=FindNextl;
/*e(i) ,e(i+1)....e(i+t-1)的二进制表示*/
for(id=0,j=i;j>l;j--) id=(id<<1)^BIT(e,j);
/**********************************
计算：
1)
for i From 0 To t-1 do
A=SquareMod(A)
2) A=Mont(A,list[e(i),e(i+1)....])
由于算法中A的初值为R,而
SquareMod(R)=R
Mont(R,b)=b
因此在第一次运算中上面的两步运算可化简为：
A=list[e(i),e(i+1)....]
***********************************/
if(i!=i0)
{
for(j=0;j<i-l+1;j++)SquareMod(A,A,m,mp,digits);
Mont(A,A,list[id],m,mp,digits);
}
else
NN_Assign(A,list[id],digits);
i=l-1;
}
/*计算_A=Mont(A,1); */
NN_ASSIGN_DIGIT(R,1,digits);
Mont(_A,A,R,m,mp,digits);
}
/* Assigns a = 2^b.
Lengths: a[digits].
Requires b < digits * NN_DIGIT_BITS.
*/
void NN_Assign2Exp (a, b, digits)
NN_DIGIT *a;
UINT b, digits;
{
void NN_AssignZero();
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 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;
UINT digits;
{
void NN_Mult(),NN_Mod();
NN_DIGIT t[2*MAX_NN_DIGITS];
NN_Mult (t, b, c, digits);
NN_Mod (a, t, 2 * digits, d, digits);
}
/*==========平方模 (X^2)*(R逆) mod m*/
void SquareMod(BIG _A,BIG x,BIG m,
NN_DIGIT mp,INT t)
{
void MontMod(),NN_AssignZero(),NN_DigitMult();
BIG2 w;
BIG2 highw;
NN_AssignZero(w,(NN_DIGIT)(t*2));
NN_AssignZero(highw,t*2);
{
NN_DIGIT uv[3],c[2],xi;
INT i,j;
for(i=0;i<t-1;i++)
{
/*计算uv=w[2*i]+x[i]*x[i] */
uv[2]=0;
NN_DigitMult (uv,x[i],x[i]);
ADD3(uv,w[2*i]);
ADD3(uv+1,highw[2*i]);
w[2*i]=uv[0];
highw[2*i]=0;
c[0]=uv[1];c[1]=uv[2];
xi=x[i];
for(j=i+1;j<t;j++)
{
NN_DigitMult (uv,xi,x[j]);
uv[2]=uv[1]>>NN_DIGIT_BITS_1;
uv[1]<<=1;
uv[1]|=(uv[0]>>NN_DIGIT_BITS_1);
uv[0]<<=1;
if((uv[0]+=c[0])<c[0])
if(++uv[1]==0)uv[2]++;
if((uv[0]+=w[i+j])<w[i+j])
if(++uv[1]==0)uv[2]++;
ADD3(uv+1,c[1]);
ADD3(uv+1,highw[i+j]);
w[i+j]=uv[0];
highw[i+j]=0;
c[0]=uv[1],c[1]=uv[2];
}
/*---------------------------------------
w[i+t]=Mid(A)
highw[i+t]=High(A) //8 bit
*/
w[i+t]=uv[1];
highw[i+t]=uv[2];
/*-------------------------------------- */
}
uv[2]=0;
NN_DigitMult (uv,x[t-1],x[t-1]);
ADD3(uv,w[2*t-2]);
uv[1]+=highw[2*t-2];
w[2*t-2]=uv[0];
w[2*t-1]=uv[1];
}
MontMod(_A,w,m,mp,t);
}
/*-----------------------
使用Montgomery约化计算
_A=xy(R的逆) (mod m)
------------------------*/
void Mont(BIG _A,BIG x,BIG y,BIG m,
NN_DIGIT mp,
INT digits)
{
NN_DIGIT cfLow;
BIG A;
NN_DIGIT NN_Sub();
void NN_AssignZero(),NN_DigitMult();
/*step 1: clear A */
NN_AssignZero(A,digits);
/*step 2:
--------------------------------------------*/
{
NN_DIGIT ui,xi,cfHigh;
NN_DIGIT aa,cf1,cf2;
NN_DIGIT t[2];
INT i,j;
cfLow=cfHigh=0;
for(i=0;i<digits;i++)
{
ui=((A[0]+x[i]*y[0])*mp); /*mod (b=2^N)*/
xi=x[i];
cf1=cf2 = 0;
for(j=0;j<digits;j++)
{
NN_DigitMult (t, ui, m[j]);
if ((aa = A[j] + cf1) < cf1)
cf1 = t[1]+1;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -