《应用密码学》课程设计RSA加解密的设计与实现

1、上海电力学院应用密码学课程设计 题目： rsa加解密的设计与实现 院系： 计算机与信息工程学院 专业年级： 信息安全专业 2009252班 学生姓名： 学号： 20093464 指导教师： 温蜜 2011年1月 6日目录1、 设计要求.32、 开发环境与工具.33、 设计原理.34、 系统功能描述与软件模块划分.45、 设计核心代码.66、 设计结果及验证.167、 软件使用说明.178、 参考资料.189、 设计体会.18一、设计要求1、随机搜索大素数，随机生成公钥和私钥； 2、用公钥对任意长度的明文加密；3、用私钥对密文解密； 4、界面简洁、交互操作性强。 5、（可选）实现对汉字的加解密，

2、把加密结果存放在文本文档二、开发环境与工具开发环境：win7 64位操作系统开发工具：vc+6.03、 设计原理（算法工作原理）首先设计一个能存放足够大数的类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); (b

25、1,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)cbigint tmp;tmp.fromstring(m,len);return tmp.modexp(e,n);这个函数为对明文进行加密的函数，具体过程是把=先把char类

26、型的数据复制到大数tmp，然后对tmp进行tmp.modexp(e,n)操作，得到密文rsajiemi(cbigint miwen,cbigint d,cbigint n,char *outs)cbigint tmp=miwen.modexp(d,n);tmp.tostring(outs); 这个函数为解密函数，对密文miwen进行解密操作，具体是先对miwen进行miwen.modexp(d,n)操作，得到二进制明文，再把二进制还原成char类型，就得到了明文。六、设计结果及验证 此为明文、密钥长度的输入，然后进行公钥私钥产生运算，此处明文为rsa加解密的设计与实现,设定的公钥长为512位而实际：公钥e为十进制145，约为二进制482位，在误差范围内。此验证了明文rsa加解密的设计与实现的解密结果是正确的，同时验证了程序的正确性。七、软件使用说明本软件设计明文一次输入最多为10000 bits，密钥最多16610位，但因实际运算速度和保密性的影响，一般二进制密钥生成512位最为合适，在输入明文和生成密钥长度以后，你需等待一段时间，让计算机计算密钥，密钥生成后会自动保存到d:工具vc+6.0msdev98myprojectsrsa text new密钥.txt 文本文档中，然后你可以选择加密操作，然后你需要等待一段时间，让计算机进行加密操作，加密得到的密文会自动