数论与密码学报告.docx

数论与密码学报告.docx

《数论与密码学报告.docx》由会员分享，可在线阅读，更多相关《数论与密码学报告.docx（100页珍藏版）》请在冰点文库上搜索。

数论与密码学报告

数论与密码学报告

指导老师：

宋军

姓名：

罗斌

班级：

192091-27

学号：

20091003757

数学基础与密码学实验

一、信息安全数学基础部分

1、埃拉托斯散（Eratosthenes）素数筛法

关键程序代码：

intprime（inta[],intn）

{

inti,j,k,x,num;

bool*b;

n++;n/=2;

b=newbool[（n+1）*2];

a[0]=2;a[1]=3;num=2;

memset（b,0,（n+1）*2）;

for（i=3;i<=n;i+=3）

for（j=0;j<2;j++）{

x=2*（i+j）-1;

while（b[x]==0）{

a[num++]=x;

for（k=x;k<=2*n;k+=x）

b[k]=1;

}

}

returnnum;

}

运行截图：

2、使用VC++编程语言设计实现一个算法程序库

1）欧几里德算法求a，b的最大公倍数；

/*欧几里得算法

语法：

intgcd（inta,intb）

返回：

最大公约数*/

intgcd（inta,intb）

{

if（b==0）returna;

elsereturngcd（b,a%b）;

}

2）扩展的欧几里德算法，求出gcd（a,b）和满足gcd（a,b）=ax+by的整数x和y；

/*扩展欧几里得算法，求x、y;

参数：

a、b对应intgcd（a,b）=ax+by

返回：

最大公约数*/

intext_euclid（inta,intb,int&x,int&y）

{

intt,d;

if（b==0）{x=1;y=0;returna;}

d=ext_euclid（b,a%b,x,y）;

t=x;

x=y;

y=t-a/b*y;

returnd;

}

3）求解模线性方程ax≡b（modn）其中n>0；

/*求模线性方程

result＝modular_equation（inta,intb,intn）;

参数：

a、b、n：

ax=b（modn）的对应参数*/

voidmodular_equation（inta,intb,intn）

{

inte,i,d;

intx,y;

d=ext_euclid（a,n,x,y）;

if（b%d>0）

printf（"Noanswer!

\n"）;

else

{

e=（x*（b/d））%n;

for（i=0;i

printf（"The%dthansweris:

%ld\n",i+1,（e+i*（n/d））%n）;

}

}

4）求解模线性方程组（中国余数定理）；

/*求解模线性方程组（中国余数定理）

语法：

result=China（intB[],intW[],intk）;

参数：

B[]、W[]：

a=B[]（modW[]）的对应参数

返回：

a*/

intChina（intB[],intW[],intk）

{

inti;

intd,x,y,a=0,m,n=1;

for（i=0;i

n*=W[i];

for（i=0;i

{

m=n/W[i];

d=ext_euclid（W[i],m,x,y）;

a=（a+y*m*B[i]）%n;

}

if（a>0）returna;

elsereturn（a+n）;

}

5）模取幂运算，计算abmodn（a,b>1032）；

/*模取幂运算x=a^bmodn

参数：

a、b、n

返回：

x*/

intmodular_exponent（inta,intb,intn）

{

intret=1;

for（;b;b>>=1,a=（int）（（__int64）a）*a%n）

if（b&1）

ret=（int）（（__int64）ret）*a%n;

returnret;

}

6）Miller-Rabin随机性素数测试算法；

/*Miller-Rabin随机性素数测试算法

用法：

输入N，可以测定2^32以内的数

返回：

判定结果*/

intMiller_Rabin（intN）

{

inttag=1;

intt,m,s,b;

__int64r0,r1;

t=N-1;m=0;

while（t%2==0）{m++;t>>=1;}

srand（N）;

for（inti=0;i<20;i++）{

b=rand（）%N;

if（b<2）b+=2;

s=m;r0=1;

for（intj=0;j

{r0*=b;r0%=N;}

while（s）{

if（r0==1||r0==N-1）break;

else{

s--;

r1=r0*r0;

r0=r1%N;

}

}

if（s>0）continue;

else

if（r0%N==1）continue;

else{tag=0;break;}

}

returntag;

}

运行截图

3、Euler素数验证

令f（n）=n2+n+41，使用MillerRabin素性检测方法验证，当n=0,1,…,39时，f（n）都是素数，但f（40）是合数。

程序运行结果如下所示，其中f（40）和f（41）均为合数。

二、密码学部分

1、大数运算库（代码见附录1）

大整数类

classCBigInt

{

public:

unsignedm_nLength;//大数在0x100000000进制下的长度

unsignedlongm_ulValue[BI_MAXLEN];//用数组记录大数在0x100000000进制下每一位的值

CBigInt（）;

~CBigInt（）;

voidMov（unsigned__int64A）;

voidMov（CBigInt&A）;//赋值

CBigIntAdd（CBigInt&A）;//加法

CBigIntAnd（CBigInt&A）;//与运算

CBigIntSub（CBigInt&A）;//减法

CBigIntMul（CBigInt&A）;//乘法

CBigIntDiv（CBigInt&A）;//除法

CBigIntMod（CBigInt&A）;//求模

CBigIntOr（CBigInt&A）;//或运算

CBigIntXor（CBigInt&A）;//异或

CBigIntRev（）;//求反

CBigIntAdd（unsignedlongA）;

CBigIntSub（unsignedlongA）;

CBigIntMul（unsignedlongA）;

CBigIntDiv（unsignedlongA）;

CBigIntGcd（CBigInt&A,CBigInt&B）;//求最大公约数

unsignedlongAnd（unsignedlongA）;

unsignedlongMod（unsignedlongA）;

intCmp（CBigInt&A）;//比较大小

/*****************************************************************

输入输出

Get，从字符串按10进制或16进制格式输入到大数

Put，将大数按10进制或16进制格式输出到字符串

*****************************************************************/

voidGet（CString&str,unsignedintsystem=DEC）;

voidPut（CString&str,unsignedintsystem=DEC）;

/*****************************************************************

Rab，拉宾米勒算法进行素数测试

Euc，欧几里德算法求解同余方程

RsaTrans，反复平方算法进行幂模运算

GetPrime，产生指定长度的随机大素数

*****************************************************************/

intRab（）;

CBigIntEuc（CBigInt&A）;

CBigIntRsaTrans（CBigInt&A,CBigInt&B）;

voidGetPrime（intbits）;

};

运行截图

2、Kasiski测试法（代码见附录2）

算法原理：

用Vigenere密码加密，明文中的相同字母在密文中不会对应相同的字母。

但是，如果两个相同字母序列间距正好是密钥长度的倍数时，也可能产生相同的密文序列。

寻找重复出现的字母序列，并求其长度的过程被称为Kasiski试验，即Kasiski法。

基于Kasiski法的基本思想，Kasiski法测试过程如下：

首先对密文中任意两个紧邻字符的出现位置进行统计，然后记下它们各次间出现的间隔。

然后写出这些间隔对应数字的因数，最后对这些因数进行统计，一般来说，次数出现最多的几个因数极有可能就是密钥字符串的长度。

其依据是，对于两个连续出现的字符在这次与下次出现的间隔极有可能是采用相同密钥加密形成的，从而这之间的间隔也极有可能就是密钥长度的倍数。

运行结果：

3、DES算法实现（代码见附录3）

运行截图

4、MD5算法实现（代码见附录4）

算法简介：

MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。

MD5中有四个32位被称作链接变量（ChainingVariable）的整数参数，他们分别为：

A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。

主循环有四轮（MD4只有三轮），每轮循环都很相似。

第一轮进行16次操作。

每次操作对a、b、c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组和一个常数。

再将所得结果向右环移一个不定的数，并加上a、b、c或d中之一。

最后用该结果取代a、b、c或d中之一。

以一下是每次操作中用到的四个非线性函数（每轮一个）。

F（X,Y,Z）=（X&Y）|（（~X）&Z）　　

G（X,Y,Z）=（X&Z）|（Y&（~Z））　　

H（X,Y,Z）=X^Y^Z　　

I（X,Y,Z）=Y^（X|（~Z））　　

这四个函数的说明：

如果X、Y和Z的对应位是独立和均匀的，那么结果的每一位也应是独立和均匀的。

F是一个逐位运算的函数。

即，如果X，那么Y，否则Z。

函数H是逐位奇偶操作符。

假设Mj表示消息的第j个子分组（从0到15），（x）<<（n）表示把x循环左移n位　　

FF（a,b,c,d,Mj,s,ti）表示a=b+（（a+（F（b,c,d）+Mj+ti））<

GG（a,b,c,d,Mj,s,ti）表示a=b+（（a+（G（b,c,d）+Mj+ti））<

HH（a,b,c,d,Mj,s,ti）表示a=b+（（a+（H（b,c,d）+Mj+ti））<

II（a,b,c,d,Mj,s,ti）表示a=b+（（a+（I（b,c,d）+Mj+ti））<

运行结果：

5、AES算法实现（代码见附录5）

5.1加密步骤

AES每一轮变换由以下三个层组成:

非线性层——进行Subbyte变换；

线行混合层——进行ShiftRow和MixColumn运算；

①Subbyte变换是作用在状态中每个字节上的一种非线性字节转换,可以通过计算出来的S盒进行映射。

②ShiftRow是一个字节换位。

它将状态中的行按照不同的偏移量进行循环移位，而这个偏移量也是根据Nb的不同而选择的[3]。

钥加层——进行AddRoundKey运算。

③在MixColumn变换中,把状态中的每一列看作GF（28）上的多项式a（x）与固定多项式c（x）相乘的结果。

④密钥加层运算（addround）是将圈密钥状态中的对应字节按位“异或”。

5.2密钥扩展　　

AES算法利用外部输入密钥K（密钥串的字数为Nk）,通过密钥的扩展程序得到共计4（Nr+1）字的扩展密钥。

它涉及如下三个模块:

①位置变换（rotword）——把一个4字节的序列[A,B,C,D]变化成[B,C,D,A]；

②S盒变换（subword）——对一个4字节进行S盒代替；

③变换Rcon[i]——Rcon[i]表示32位比特字[xi-1,00,00,00]。

这里的x是（02），如Rcon[1]=[01000000]；Rcon[2]=[02000000]；Rcon[3]=[04000000]……　　

扩展密钥的生成：

扩展密钥的前Nk个字就是外部密钥K；以后的字W[[ｉ]]等于它前一个字W[[i-1]]与前第Nk个字W[[i-Nk]]的“异或”,即W[[ｉ]]=W[[i-1]]W[[ｉ-Nk]]。

但是若ｉ为Nk的倍数,则W[ｉ]=W[i-Nk]Subword（Rotword（W[[ｉ-1]]））Rcon[i/Nk]。

6、SMS算法实现（代码见附录6）

6.1SMS4密码算法结构：

基本运算：

●模2加：

，32比特异或运算

●循环移位：

<<

基本密码部件：

Ø非线性字节变换部件S盒：

8位输入、8位输出。

设输入位a，输出位b，表示为：

b=S_Box（a）

S盒的置换规则：

以输入的前半字节为行号，后半字节为列号，行列交叉点处的数据即为输出。

Ø非线性字变换：

32位字的非线性变换

4个S盒并行置换；

设输入字A=（a0,a1,a2,a3）,输出字B=（b0,b1,b2,b3）,

B=（A）=（S_box（a0）,S_box（a1）,S_box（a2）,S_box（a3））

Ø字线性部件L变换：

32位输入、32位输出。

设输入位B，输出位C，表为：

C=L（B）

运算规则：

C=L（B）

=B（B<<<2）（B<<<10）（B<<<18）（B<<<24）

Ø字合成变换T：

由非线性变换和线性变换L复合而成；

T（X）=L（（X））。

先S盒变换，再L变换。

轮函数F：

输入数据：

（X0，X1，X2，X3），128位，四个32位字。

输入轮密钥：

rk，32位字。

输出数据：

32位字。

轮函数F：

F（X0，X1，X2，X3，rk）

=X0T（X1X2X3rk）

密钥扩展算法：

输入加密密钥：

MK=（MK0，MK1，MK2，MK3）

输出轮密钥：

rki，i=0，1…,30，31

中间数据：

Ki，i=0，1…,34，35

①（K0,K1,K2,K3）=（MK0FK0,MK1FK1,MK2FK2,MK3FK3）

②Fori=0，1…,30，31Do

iki=Ki+4=KiT'（Ki+1Ki+2Ki+3CKi）

说明：

T'变换与加密算法轮函数中的T基本相同，只将其中的线性变换L修改为以下：

L'

L'（B）=B（B<<<13）（B<<<23）

6.2运行结果

附录：

1、大数运算库

//BigInt.h

/******************************************************************/

//允许生成1120位（二进制）的中间结果

#ifndefBI_MAXLEN

#defineBI_MAXLEN35

#defineDEC10

#defineHEX16

/*****************************************************************

基本操作与运算

Mov，赋值运算，可赋值为大数或普通整数，可重载为运算符“=”

Cmp，比较运算，可重载为运算符“==”、“!

=”、“>=”、“<=”等

Add，加，求大数与大数或大数与普通整数的和，可重载为运算符“+”

Sub，减，求大数与大数或大数与普通整数的差，可重载为运算符“-”

Mul，乘，求大数与大数或大数与普通整数的积，可重载为运算符“*”

Div，除，求大数与大数或大数与普通整数的商，可重载为运算符“/”

Mod，模，求大数与大数或大数与普通整数的模，可重载为运算符“%”

*****************************************************************/

classCBigInt

{

public:

//大数在0x100000000进制下的长度

unsignedm_nLength;

//用数组记录大数在0x100000000进制下每一位的值

unsignedlongm_ulValue[BI_MAXLEN];

CBigInt（）;

~CBigInt（）;

voidMov（unsigned__int64A）;

voidMov（CBigInt&A）;

CBigIntAdd（CBigInt&A）;

CBigIntAnd（CBigInt&A）;

CBigIntSub（CBigInt&A）;

CBigIntMul（CBigInt&A）;

CBigIntDiv（CBigInt&A）;

CBigIntMod（CBigInt&A）;

CBigIntOr（CBigInt&A）;

CBigIntXor（CBigInt&A）;

CBigIntRev（）;

CBigIntAdd（unsignedlongA）;

CBigIntSub（unsignedlongA）;

CBigIntMul（unsignedlongA）;

CBigIntDiv（unsignedlongA）;

CBigIntGcd（CBigInt&A,CBigInt&B）;

unsignedlongAnd（unsignedlongA）;

unsignedlongMod（unsignedlongA）;

intCmp（CBigInt&A）;

/*****************************************************************

输入输出

Get，从字符串按10进制或16进制格式输入到大数

Put，将大数按10进制或16进制格式输出到字符串

*****************************************************************/

voidGet（CString&str,unsignedintsystem=DEC）;

voidPut（CString&str,unsignedintsystem=DEC）;

/*****************************************************************

Rab，拉宾米勒算法进行素数测试

Euc，欧几里德算法求解同余方程

RsaTrans，反复平方算法进行幂模运算

GetPrime，产生指定长度的随机大素数

*****************************************************************/

intRab（）;

CBigIntEuc（CBigInt&A）;

CBigIntRsaTrans（CBigInt&A,CBigInt&B）;

voidGetPrime（intbits）;

};

//BigInt.cpp

#include"stdafx.h"

#include"BigInt.h"

#ifdef_DEBUG

#definenewDEBUG_NEW

#undefTHIS_FILE

staticcharTHIS_FILE[]=__FILE__;

#endif

/////////////////////////////////////////////////////////////////////////////

//Theoneandonlyapplicationobject

CWinApptheApp;

usingnamespacestd;

//小素数表

conststaticintPrimeTable[550]=

{3,5,7,11,13,17,19,23,29,31,

37,41,43,47,53,59,61,67,71,73,

79,83,89,97,101,103,107,109,113,127,

131,137,139,149,151,157,163,167,173,179,

181,191,193,197,199,211,223,227,229,233,

239,241,251,257,263,269,271,277,281,283,

293,307,311,313,317,331,337,347,349,353,

359,367,373,379,383,389,397,401,409,419,

421,431,433,439,443,449,457,461,463,467,

479,487,491,499,503,509,521,523,541,547,

557,563,569,571,577,587,593,599,601,607,

613,617,619,631,641,643,647,653,659,661,

673,677,683,691,701,709,719,727,733,739,

743,751,757,761,769,773,787,797,809,811,

821,823,827,829,8