elgamaml签名设计报告

专业课程设计I报告（2008/2009学年第二学期）题目：ElGamal签名设计专业信息安全学生姓名吴俊锋班级学号B08030216指导教师王志伟指导单位南京邮电大学日期2010.41指导教师成绩评定表学生姓名班级学号专业评分内容评分标准优秀良好中等差平时成绩认真对待课程设计，遵守实验室规定，上机不迟到早退，不做和设计无关的事设计成果设计的科学、合理性功能丰富、符合题目要求界面友好、外观漂亮、大方程序功能执行的正确性程序算法执行的效能设计报告设计报告正确合理、反映系统设计流程文档内容详实程度文档格式规范、排版美观验收答辩简练、准确阐述设计内容，能准确有条理回答各种问题，系统演示顺利。评分等级指导教师简短评语指导教师签名日期备注评分等级有五种：优秀、良好、中等、及格、不及格2Elgamal签名设计一、课题内容和要求主要实现的模块包括，计算体系参数，计算密钥，对文件签名，验证签名文件。该部分可参考前面给出的问题描述再加以细化一些计算体系参数随机素数p，用户的私有密钥x，g和x计算得到的整数y，消息m，随机数k。计算密钥公开密钥（p，g，y），私有密钥x对文件签名任何一个给定的消息都可以产生多个有效的ELGamal签名。验证签名文件验证算法能够将上述多个ELGamal签名中的任何一个当作可信的签名接受。二、设计思路分析ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。密钥对产生办法首先选择一个素数p，两个随机数,g和x，g,xp,计算y=g^x(modp)，则其公钥为y,g和p。私钥是x。g和p可由一组用户共享。ElGamal用于数字签名。被签信息为M，首先选择一个随机数k,k与p-1互质，计算a=g^k(modp)再用扩展Euclidean算法对下面方程求解b：M=xa+kb(modp-1)签名就是(a,b)。随机数k须丢弃。验证时要验证下式：y^a*a^b(modp)=g^M(modp)3同时一定要检验是否满足1=ap。否则签名容易伪造。ElGamal签名的安全性依赖于乘法群(IFp)*上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数。因子以抵抗Pohlig&Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。一般的ElGam数字签名方案在系统中有两个用户A和B，A要发送消息到B，并对发送的消息进行签名。B收到A发送的消息和签名后进行验证。1系统初始化选取一个大的素数p，g是GF(p)的本原元。h：GF(p)→GF(p)，是一个单向Hash函数。系统将参数p、g和h存放于公用的文件中，在系统中的每一个用户都可以从公开的文件中获得上述参数。2对发送的消息进行数字签名的过程假定用户A要向B发送消息m[1,p-1]，并对消息m签字。第一步：用户A选取一个x[1,p-1]作为秘密密钥，计算y=(modp)作为公钥。将公钥y存放于公用的文件中。第二步：随机选取k[1,p-1]且gcd(k,(p-1))=1，计算r=(modp)。对一般的ElGamal型数字签名方案有签名方程（SignatureEquation）：ax=bk+c(mod(p-1))。其中(a，b，c)是(h(m),r,s)数学组合的一个置换。由签名方程可以解出s。那么(m,(r,s))就是A对消息m的数字签名。第三步：A将(m,(r,s))发送到B3数字签名的验证过程当B接收到A发送的消息(m,(r,s))，再从系统公开文件和A的公开文件中获得系统公用参数p，g，h和A的公钥y。由(m,(r,s))计算出(a，b，c)验证等式：=(modp)是否成立。在该部分中叙述每个模块的功能要求或者如何开展此题目的求解？三、概要设计在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义，如果用面向对象的方法，应该给出类中成员变量和成员函数原型声明）。整个程序的流程图4产生素数p由用户选择素数p的范围，来算出p函数定义为intprime_number_p();产生随机数gg是一个在1-（p-1）中的一个随机数函数为intrandom_number_g(intp)产生一个随机数g输入私钥x计算出公钥y输入m计算出签名（a，b）验证签名产生一个素数p由用户输入产生素数的范围n,mP-m判断m是否为素数m=m-1mnYNNY5p是选择的大素数利用随机函数rand()%p来得g。产生公钥y自定义函数为intPKI_y(intp,intg,intx)P是产生的大素数，g是大素数的生成元，x是私钥计算公式y=g^x(modp)产生m签名（a，b）自定义函数voidelg_sign_develop(intg,intp,intx,intm)g是p的生成元，p是大素数，x是私钥，m是要签名的数据验证签名自定义函数名voidelg_sign_test(inty,intp,intm,intg,charname)y是公钥，p是大素数，m是签名的数据，g是大素数的生成元b=i计算a=g^k(modp)i=1x*a+k*b)%(p-1)==mi=i+1输出a产生一个随机数kK与p-1互质YNYN6四、详细设计#includeiostream.h#includestdlib.h#includetime.hinta,b;intprime_number_p();intrandom(int);intm_develop(int);/*---------------------------------*/intprime(intp){inti,j;for(i=2;ip;i++){j=p%i;if(j==0)return0;}return1;}//判断是否为素数,若为素数则返回1/*------------------------------------*/intprime_number_max(intn,intm){intp;for(p=m;p=n;p--){if(prime(p)==1)returnp;}计算i=((y^a)*(a^b))%p;计算j=(g^m)%p;i=jYN输出签名正确输出不是name的签名7}//求出n,m之间的最大素数/*--------------------------------*/intprime_number_p(){intp,m,n;cout为一组用户产生一个公钥P(p为素数)endl;cout请输入p所在范围n，m(系统将选择最大的素数P)endl;coutn=;cinn;coutm=;cinm;p=prime_number_max(n,m);if(p==0){coutn,m中无素数;p=prime_number_p();}returnp;}//p的产生/*-------------------------------*/intRandom_number_g(intp){intg;srand((int)time(NULL));g=rand()%p;returng;}//g的产生intPKI_y(intp,intg,intx){inty;inti;y=1;for(i=0;ix;i++){y*=g;y%=p;}returny;}//公钥y的产生intgcd(inta,intb){ints[50],q[50];if(ab){s[0]=a;s[1]=b;}else8{s[0]=a;s[1]=b;}for(inti=1;i100;i++){s[i+1]=s[i-1]%s[i];q[i]=s[i-1]/s[i];if(s[i+1]==0)break;}returns[i];}//求a，b的最大公约数/*----------------------------------*/intm_develop(intp){intm;cinm;if(mp){cout无法对输入的m进行签名,请重新输入endl;m=m_develop(p);}returnm;}intprime_k(intp){intk,i;k=rand()%p;i=gcd(k,p-1);if(i!=1){k=prime_k(p);}returnk;}//随即数k的产生/*-----------------------------------*/voidelg_sign_develop(intg,intp,intx,intm){intk;inti=1;k=prime_k(p);//产生一个k的随机数,k与p-1互质//a=(g^k)%p;for(i=0;ik;i++)9{a*=g;a%=p;}//while(m!=(a*x+k*i)%(p-1))//{i++;}b=i;for(i=0;ip-1;i++){b=i;if((x*a+k*b)%(p-1)==m)break;}k=0;//丢弃随即数Kcoutm的数字签名是（a,b）endl;}//产生签名/*———————————————————*/voidelg_sign_test(inty,intp,intm,intg,charname){inti,c1,d1,j;c1=d1=j=1;//i=((y^a)*(a^b))%p;for(i=0;ia;i++){c1*=y;c1%=p;}for(i=0;ib;i++){d1*=a;d1%=p;}d1*=c1;d1%=p;//j=(g^m)%p;for(i=0;im;i++){j*=g;j%=p;}if(d1==j){cout是用户name签名的。endl;}else{10cout不是用户name签名的endl;}}//验证签名/*——————————————————*/main(){intp,g,x,y,m,i;a=b=1;charname;p=prime_number_p();//产生大素数pg=Random_number_g(p);//产生随即数gcout此用户组的公共参数为p=pg=gendl;cout输入用户名endl;cinname;x=p+1;while(x=p){cout输入用户密码endl;cinx;if(x=p)cout密码格式错误;endl;}y=PKI_y(p,g,x);//公钥y的产生cout用户name公钥y是yendl;cout输入要签名的字符mendl;m=m_develop(p);elg_sign_develop(g,p,x,m);elg_sign_test(y,p,m,g,name);jj:cout结束程序请输入0endl;cini;if(i==0)exit(0);elsegotojj;}五、测试数据及其结果分析运行exe文件的大素数p的产生和g的产生用户名以及密钥x，和公钥y的生成11签名（a，b）的产生和验证进行第2次测试12由以上两幅截图可知，在私有密钥x、要签名的消息m相同，但素数p、g的生成元、随机数k不相同的情况下，签名都是有效的，说明源程序代码正确。对于不同的私钥x，和要签名的m不同，产生的签名也不一样。六、调试过程中的问题此程序仅仅局限于int型，int对于文件还有安全性较差。超过int就会出现错误这就出现错误了。我们可以进行扩充。把int的数用一个数组来表示。大家都扩到128位。密码也13按照一定方法扩到128位。对于m则可以使用hash值。这样可以可以对几乎所有的文件进行签名了。对于g，此处我使用的随机数g，这会使得签名容易破译。g应该为p的生成元在，然后再生成元中随机取一个。若一个群G的每一个元都是G的某一个固定元a的乘方，我们就把G叫做循环群；我们也说，G是由元a生成的，并且用符号G=