《《应用密码学》课程设计RSA加解密的设计与实现 .doc》由会员分享，可在线阅读，更多相关《《应用密码学》课程设计RSA加解密的设计与实现 .doc（19页珍藏版）》请在三一办公上搜索。
1、上海电力学院应用密码学课程设计 题目： RSA加解密的设计与实现 院系： 计算机与信息工程学院 专业年级： 信息安全专业 2009252班 学生姓名： 学号： 20093464 指导教师： 温蜜 2011年1月 6日目录一、 设计要求.3二、 开发环境与工具.3三、 设计原理.3四、 系统功能描述与软件模块划分.4五、 设计核心代码.6六、 设计结果及验证.16七、 软件使用说明.17八、 参考资料.18九、 设计体会.18一、设计要求1、随机搜索大素数，随机生成公钥和私钥； 2、用公钥对任意长度的明文加密；3、用私钥对密文解密； 4、界面简洁、交互操作性强。 5、（可选）实现对汉字的加解密，
2、把加密结果存放在文本文档二、开发环境与工具开发环境：win7 64位操作系统开发工具：VC+6.0三、 设计原理（算法工作原理）首先设计一个能存放足够大数的类CBigInt，这个类是把很大的数分解成一个个int类型的数来i存储的。输入你要求的密钥位数，然后用rand（）函数生成一个个32位数，拼接成大数，进行素性检测，是素数就返回，就这样就产生了公钥（e,n)和私钥(d,n),然后利用 公式c=me mod n，得到密文，保存得到的密文到文本文档，再用公式m=cd mod n ，得到明文。算法路程图如下：开始输入明文输入需要生成的密钥长度产生随机大数进行拉宾-米勒 素性检测通过？NY 加密 结
3、束解密验证四、系统功能描述与软件模块划分CBigInt类的功能：class CBigInt public: unsigned m_nLength; unsigned long m_ulValueBI_MAXLEN; CBigInt(); CBigInt(); void Mov(unsigned _int64 A); void Mov( CBigInt& A); CBigInt Add( CBigInt& A); /加法CBigInt Sub(CBigInt& A); /减法CBigInt Mul(CBigInt& A); /乘法CBigInt Div(CBigInt& A); /除法CBigI
4、nt Mod( CBigInt& A); /模CBigInt Add(unsigned long A); CBigInt Sub(unsigned long A); CBigInt Mul(unsigned long A); CBigInt Div(unsigned long A); void FromString(char *,int len);int ToString(char *);unsigned long Mod(unsigned long A); int Cmp( CBigInt& A); CBigInt ModExp(CBigInt& A, CBigInt& B);CBigInt
5、 RsaTrans( CBigInt& A, CBigInt& B);int RabinMiller(); CBigInt Euc(CBigInt& A);void GetPrime( unsigned bits);void Put(char *str, unsigned int system) ;void Get(char* str, unsigned int system);friend CBigInt operator +(CBigInt&a,CBigInt&b);friend CBigInt operator -(CBigInt&a,CBigInt&b);friend CBigInt
6、operator *(CBigInt&a,CBigInt&b);friend CBigInt operator /(CBigInt&a,CBigInt&b);friend CBigInt operator %(CBigInt&a,CBigInt&b);CBigInt operator +( unsigned long b);CBigInt operator -( unsigned long b);CBigInt operator *( unsigned long b);CBigInt operator /( unsigned long b);void Mov( CBigInt& A); voi
7、d Mov(unsigned _int64 A)是实现大数复制的功能用法为a.Mov(b),就是把大数b赋给aCBigInt Add( CBigInt& A) 实现大数加法功能，用法为a.Add(b),等介于a+b；CBigInt Sub(CBigInt& A)实现大数减法功能，用法为a.Sub(b),等价于a-b；CBigInt Mul(CBigInt& A)实现大数乘法功能，用法为a.Mul（b），等价于a*b；CBigInt Div(CBigInt& A)实现大数除法功能，用法为a.Div(b),等价于a/b;CBigInt Mod( CBigInt& A)实现大数的模功能，用法为a.M
8、od(b)等价于a%b;void FromString(char *,int len)实现字符型的数转换成大数的功能，用法为a.FromString(m,n),意思是把n位 的字符型m赋给大数a；int ToString(char *)实现把大数转变成字符型输出，用法为a.ToString(m),意思是把大数转换成字符型m；int Cmp( CBigInt& A)实现大数比较，用法为C=a.Cmp(b),如果ab，则c=1，如果a=b则c=0，如果aA.m_nLength)return 1; if(m_nLength=0;i-) if(m_ulValueiA.m_ulValuei)return
9、 1; if(m_ulValueiA.m_ulValuei)return -1; return 0; 这个函数实现了大数的比较，如果a的长度小于b，那么ab，如果ab的长度相等，那么，我们就从他们的高位开始比较，谁的高位比较大，那么谁就大。Mov(CBigInt& A) m_nLength=A.m_nLength; for(int i=0;i0xffffffff) m_nLength=2; m_ulValue1=(unsigned long)(A32); m_ulValue0=(unsigned long)A; else m_nLength=1; m_ulValue0=(unsigned lo
10、ng)A; for(int i=m_nLength;iBI_MAXLEN;i+)m_ulValuei=0; 这个函数是把一个64位的数赋值给一个大数，如果这个64位的大数前32位为0，那么就直接把这个64位数的后32位赋给这个大数，如果这个64位数前32位不为0，那么就把这个64位数拆分为两部分，前32位赋给大数的高位，后32位赋值给大数的地位。Add(CBigInt& A) CBigInt X; X.Mov(*this); unsigned carry=0; unsigned _int64 sum=0; if(X.m_nLengthA.m_nLength) X.m_nLength=A.m_n
11、Length; for(unsigned i=0;i32); X.m_ulValueX.m_nLength=carry; X.m_nLength+=carry; return X; 这个函数实现大数的相加，基本原理是把两个大数的对应位相加再加上进位就得到大数的对应位，如果想加的数大于32位，那么就取得数的后32位作为大数的对应位，32位之前的数作为进位，留给下一位做加法运算，如果两个数相加的到的结果位数大于当前的位数，那么把该数扩展32位，把进位赋给它。Add(unsigned long A) CBigInt X; X.Mov(*this); unsigned _int64 sum; sum=
12、X.m_ulValue0; sum+=A; X.m_ulValue0=(unsigned long)sum; if(sum0xffffffff) unsigned i=1; while(X.m_ulValuei=0xffffffff)X.m_ulValuei=0;i+; X.m_ulValuei+; if(m_nLength=i)m_nLength+; return X; 这个函数实现大数与一个32位的数相加，先把该32位数与大数的末位相加，若产生进位，则把进位与倒数第二位相加，依次类推，就得到所求的数。Sub(CBigInt& A) CBigInt X; X.Mov(*this); if(X
13、.Cmp(A)=0)X.Mov(0);return X; unsigned carry=0; unsigned _int64 num; unsigned i; for(i=0;iA.m_ulValuei)|(m_ulValuei=A.m_ulValuei)&(carry=0) X.m_ulValuei=m_ulValuei-carry-A.m_ulValuei; carry=0; else num=0x100000000+m_ulValuei; X.m_ulValuei=(unsigned long)(num-carry-A.m_ulValuei); carry=1; while(X.m_ul
14、ValueX.m_nLength-1=0)X.m_nLength-; return X; 这个函数实现两个大数的相减。具体过程如下：把两大数的对应位相减，若需要借位，则向高位借一位，然后高位进行减一操作，一次类推就得到所求的数。Sub(unsigned long A) CBigInt X; X.Mov(*this); if(X.m_ulValue0=A)X.m_ulValue0-=A;return X; if(X.m_nLength=1)X.Mov(0);return X; unsigned _int64 num=0x100000000+X.m_ulValue0; X.m_ulValue0=(
15、unsigned long)(num-A); int i=1; while(X.m_ulValuei=0)X.m_ulValuei=0xffffffff;i+; X.m_ulValuei-; if(X.m_ulValuei=0)X.m_nLength-; return X; 这个函数实现一个大数与一个32位的数相减，如果大数的末位大于此32位数，那么就直接相减，如果末位需要借位，那么末位就向倒数第二位借位，如果倒数第二位为0，那么就向倒数第三位借位，一次类推。Mul( CBigInt& A) if(A.m_nLength=1)return Mul(A.m_ulValue0); CBigInt
16、X; unsigned _int64 sum,mul=0,carry=0; unsigned i,j; X.m_nLength=m_nLength+A.m_nLength-1; for(i=0;iX.m_nLength;i+) sum=carry; carry=0; for(j=0;j=0)&(i-j)32; mul=mul&0xffffffff; sum+=mul; carry+=sum32; X.m_ulValuei=(unsigned long)sum; if(carry)X.m_nLength+;X.m_ulValueX.m_nLength-1=(unsigned long)carry
17、; return X; 这个函数实现两大数相乘，次算法模拟我们笔算的方法，先是地位与大数被乘数相乘，若产生进位，则取后32位作为得数的末位，32之前的作为进位，然后大数各位交叉相乘，结果相加并加上进位，得到相应位，就这样逐位获取，得到所求的数。Mul(unsigned long A) CBigInt X; unsigned _int64 mul; unsigned long carry=0; X.Mov(*this); for(unsigned i=0;i32); if(carry)X.m_nLength+;X.m_ulValueX.m_nLength-1=carry; return X; 这
18、个函数实现大数与一个32位的数相乘，原理很简单，就是把这个32位的数依次与大数的各位（从地位到高位）相乘，再加上进位就得到大数的对应位，如果产生进位，这个后32位作为对应位的数，把32之前的数作为进位，就这样循环相乘，就得到所得的数。Div( CBigInt& A) if(A.m_nLength=1)return Div(A.m_ulValue0); CBigInt X,Y,Z; unsigned i,len; unsigned _int64 num,div; Y.Mov(*this); while(Y.Cmp(A)=0) div=Y.m_ulValueY.m_nLength-1; num=A
19、.m_ulValueA.m_nLength-1; len=Y.m_nLength-A.m_nLength; if(div=num)&(len=0)X.Mov(X.Add(1);break; if(div=num)&len)len-;div=(div=len;i-)Z.m_ulValuei=Z.m_ulValuei-len; for(i=0;ilen;i+)Z.m_ulValuei=0; X.Mov(X.Add(Z); Y.Mov(Y.Sub(A.Mul(Z); return X; 这个函数实现两个大数相除，此算法也是模拟笔算，假设两个数为a=223，b=3，那么令div=2，num=3，显然2
20、3，那么就向后借位，那么div=22，num=3，div=22/(3+1)=5,那么z1=50，a=223-50*3=73，那么现在令div=7，num=3，那么div=7/（3+1）=1，那么z2=10，a=73-10*3=43，现在令div=4，num=3，则div=4/(3+1)=1,那么z3=10，a=43-10*3=13，z4=13/3=4,余数为1，因为1=0;i-) div=carry; div=(div=0) div=X.m_ulValueX.m_nLength-1; num=A.m_ulValueA.m_nLength-1; len=X.m_nLength-A.m_nLeng
21、th; if(div=num)&(len=0)X.Mov(X.Sub(A);break; if(div=num)&len)len-;div=(div=len;i-)Y.m_ulValuei=Y.m_ulValuei-len; for(i=0;i=0;i-) div=m_ulValuei; div+=carry*0x100000000; carry=(unsigned long)(div%A); return carry; 这个函数是实现大数与一个32位数的模，具体过程：从大数的高位开始，逐个模该32位数，余数与下一位数结合，再模该32位数，直到余数小于该32位数，那么该余数就是所求的数。Mod
22、Exp(CBigInt& A, CBigInt& B)CBigInt X,Y,Z;X.Mov(1);Y.Mov(*this);Z.Mov(A);while(Z.m_nLength!=1)|Z.m_ulValue0)if(Z.m_ulValue0&1)Z.Mov(Z.Sub(1);X.Mov(X.Mul(Y);X.Mov(X.Mod(B);elseZ.Mov(Z.Div(2);Y.Mov(Y.Mul(Y);Y.Mov(Y.Mod(B);return X;这个函数是实现大数的模幂，用法为a=bc mod d等价于a=bc mod d，具体的实现过程为：假设该数为 4 ，12，5即412 mod 5
23、，先分成4*411 mod 5,由于4%5=4，那么再分成4*4*410 mod 5由于16%5=1，那么可写成 410 mod 5，进一步写成（4*4）5 mod 5，即165 mod 5，一次类推，就可求出所得结果。GetPrime(unsigned bits) unsigned i; m_nLength=bits; begin: for(i=0;i0;i-) m_ulValuei=m_ulValuei1; /if(m_ulValuei-1&0x80000000)m_ulValuei+; m_ulValue0=m_ulValue01; m_ulValue0+; for(i=0;i550;i
24、+)if(Mod(PrimeTablei)=0)goto begin; CBigInt S,A,I,K; K.Mov(*this); K.m_ulValue0-; for(i=0;i=0)Y.Mov(X.Sub(Y); elseY.Mov(Y.Sub(X);y=0; elseY.Mov(X.Add(Y);x=1-x;y=1-y; X.Mov(J); if(x=0)X.Mov(A.Sub(X); return X; 这是扩展欧几里德求乘法逆元，这是一个循环运算，下面用伪代码来叙述其具体的工作过程：已知b*b_1=1 mod m，b，m。求b_1。1. （A1,A2,A3)=(1,0,m); (B1,B2,B3)=(0,1,b)2. If B3=0 return A3;表示无值3. If B3=1 return B34. Q=A3/B35. (T1,T2,T3)=(A1-Q*B1,A2-Q*B2,A3-Q*B3)6. (A1,A2,A3)=(B1,B2,B3)7. (B1,B2,B3)=(T1,T2,T3)8. Goto 2.Rsajiami(char* m,int len,CBigInt e,CBigInt n)
