elgamaml签名设计报告.doc

1、专业课程设计I报告（ 2008 / 2009 学年 第 二 学期）题目： ElGamal签名设计 专 业 信息安全 学 生 姓 名 吴俊锋 班 级 学 号 B08030216 指 导 教 师 王志伟 指 导 单 位 南京邮电大学 日 期 2010.4 指导教师成绩评定表学生姓名班级学号专业评分内容评分标准优秀良好中等差平时成绩认真对待课程设计，遵守实验室规定，上机不迟到早退，不做和设计无关的事设计成果设计的科学、合理性功能丰富、符合题目要求 界面友好、外观漂亮、大方程序功能执行的正确性程序算法执行的效能设计报告设计报告正确合理、反映系统设计流程文档内容详实程度文档格式规范、排版美观验收答辩简练

2、、准确阐述设计内容，能准确有条理回答各种问题，系统演示顺利。评分等级指导教师简短评语指导教师签名日期备注评分等级有五种：优秀、良好、中等、及格、不及格Elgamal签名设计一、 课题内容和要求主要实现的模块包括，计算体系参数，计算密钥，对文件签名，验证签名文件。该部分可参考前面给出的问题描述再加以细化一些计算体系参数随机素数p，用户的私有密钥x，g和x计算得到的整数y，消息m，随机数k。计算密钥公开密钥（p，g，y），私有密钥x对文件签名任何一个给定的消息都可以产生多个有效的ELGamal签名。验证签名文件验证算法能够将上述多个ELGamal签名中的任何一个当作可信的签名接受。二、 设计思路分

3、析ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。 密钥对产生办法首先选择一个素数p，两个随机数, g 和x，g, x p, 计算 y = gx ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。 ElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算 a= gk ( mod p ) 再用扩展 Euclidean 算法对下面方程求解b： M = xa + kb ( mod p - 1 ) 签名就是( a, b )。随机数k须丢弃。 验证时要验证下式： ya * ab ( mod

4、 p ) = gM ( mod p ) 同时一定要检验是否满足1= a p。否则签名容易伪造。 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(

5、p)的本原元。h：GF(p)GF(p)，是一个单向Hash函数。系统将参数p、g和h存放于公用的文件中，在系统中的每一个用户都可以从公开的文件中获得上述参数。 2对发送的消息进行数字签名的过程 假定用户A要向B发送消息m 1,p-1，并对消息m签字。第一步：用户A选取一个x 1,p-1作为秘密密钥，计算y= (mod p)作为公钥。将公钥y存放于公用的文件中。第二步：随机选取k 1,p-1且gcd(k,(p-1)=1，计算r= (mod p)。对一般的ElGamal型数字签名方案有签名方程（Signature Equation）：ax=bk+c(mod(p-1)。 其中(a，b，c)是(h(m

6、),r,s)数学组合的一个置换。由签名方程可以解出s。那么(m,(r,s)就是A对消息m的数字签名。第三步：A将(m,(r,s)发送到B 3数字签名的验证过程 当B接收到A发送的消息(m,(r,s)，再从系统公开文件和A的公开文件中获得系统公用参数p，g，h和A的公钥y。由(m,(r,s)计算出(a，b，c)验证等式： = (mod p)是否成立。 在该部分中叙述每个模块的功能要求或者如何开展此题目的求解？三、概要设计 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义，如果用面向对象的方法，应该给出类中成员变量和

7、成员函数原型声明）。整个程序的流程图产生一个随机数g输入私钥x计算出公钥y输入m计算出签名（a，b）验证签名产生一个素数p产生素数p由用户选择素数p的范围，来算出p函数定义为 int prime_number_p();由用户输入产生素数的范围n,mP-m判断m是否为素数m=m-1mnYNNY产生随机数gg是一个在1-（p-1）中的一个随机数函数为int random_number_g(int p)p是选择的大素数利用随机函数rand()%p来得g。产生公钥y自定义函数为int PKI_y(int p,int g,int x)P是产生的大素数，g是大素数的生成元，x是私钥计算公式y=gx(mod

8、 p)产生m签名（a，b）自定义函数 void elg_sign_develop(int g,int p,int x,int m)g是p的生成元，p是大素数，x是私钥，m是要签名的数据b=i计算a= gk ( mod p )i=1x*a+k*b)%(p-1)=mi=i+1输出a产生一个随机数kK与p-1互质YNYN验证签名自定义函数名void elg_sign_test(int y,int p,int m,int g,char name)y是公钥，p是大素数，m是签名的数据，g是大素数的生成元计算i=(ya)*(ab)%p;计算j=(gm)%p;i=jYN输出签名正确输出不是name的签名四、

9、详细设计 #include#include #includeint a,b;int prime_number_p();int random(int);int m_develop(int );/*-*/int prime(int p)int i,j;for(i=2;i=n;p-)if(prime(p)=1)return p;/求出n,m之间的最大素数/*-*/int prime_number_p()int p,m,n;cout为一组用户产生一个公钥P(p为素数)endl;cout请输入p所在范围n，m(系统将选择最大的素数P)endl;coutn;coutm;p=prime_number_max

10、(n,m);if(p=0) coutn,m中无素数;p=prime_number_p();return p;/p的产生/*-*/int Random_number_g(int p) int g;srand(int) time (NULL);g=rand()%p;return g;/g的产生int PKI_y(int p,int g,int x)int y;int i;y=1;for(i=0;ib)s0=a;s1=b;elses0=a;s1=b;for(int i=1;im;if (mp)cout无法对输入的m进行签名,请重新输入endl;m=m_develop(p);return m;int

11、prime_k(int p)int k,i;k=rand()%p;i=gcd(k,p-1);if(i!=1)k=prime_k(p);return k;/随即数k的产生/*-*/void elg_sign_develop(int g,int p,int x,int m) int k;int i=1;k=prime_k(p);/产生一个k的随机数,k与p-1互质/a=(gk)%p;for(i=0;ik;i+)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;/

12、丢弃随即数Kcoutm的数字签名是（a,b）endl;/产生签名/*/void elg_sign_test(int y,int p,int m,int g,char name)int i,c1,d1,j;c1=d1=j=1;/i=(ya)*(ab)%p;for(i=0;ia;i+)c1*=y;c1%=p;for(i=0;ib;i+)d1*=a;d1%=p;d1*=c1;d1%=p;/j=(gm)%p;for(i=0;im;i+)j*=g;j%=p;if(d1=j)cout是用户name签名的。endl;elsecout不是用户name签名的endl;/验证签名/*/main()int p,g,

13、x,y,m,i;a=b=1;char name;p=prime_number_p();/产生大素数pg=Random_number_g(p);/产生随即数gcout此用户组的公共参数为p=p g=gendl;cout输入用户名name;x=p+1;while(x=p)cout输入用户密码x;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

14、:cout结束程序请输入0i; if(i=0) exit(0); else goto jj;五、测试数据及其结果分析运行exe文件的大素数p的产生和g的产生用户名以及密钥x，和公钥y的生成签名（a，b）的产生和验证进行第2次测试由以上两幅截图可知，在私有密钥x、要签名的消息m相同，但素数p、g的生成元、随机数k不相同的情况下，签名都是有效的，说明源程序代码正确。对于不同的私钥x，和要签名的m不同，产生的签名也不一样。六、调试过程中的问题此程序仅仅局限于int型，int对于文件还有安全性较差。超过int就会出现错误这就出现错误了。我们可以进行扩充。把int的数用一个数组来表示。大家都扩到128位

15、。密码也按照一定方法扩到128位。对于m则可以使用hash值。这样可以可以对几乎所有的文件进行签名了。对于g，此处我使用的随机数g，这会使得签名容易破译。g应该为p的生成元在，然后再生成元中随机取一个。若一个群G的每一个元都是G的某一个固定元a的乘方，我们就把G叫做循环群；我们也说，G是由元a生成的，并且用符号G=（a）来表示。a叫做G的一个生成元。关于生成元g产生的方法 int getGenerator(int p)int gTableLEN;int len=0;int q=p;for(int i=2;iq;i+)for(int j=2;jq-1;j+)int g=1;for(int l=0

16、;l=40)break;cout素数p的生成元有：endl;for(int s=0;slen;s+)coutgTables ; coutb 且a mod b 不为0)证明：a可以表示成a = kb + r，则r = a mod b假设d是a,b的一个公约数，则有d|a, d|b，而r = a - kb，因此d|r因此d也是(b,a mod b)的公约数因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。欧几里德算法的c+实现方法void swap(int &； a， int &； b)int c = a；a = b；b = c；int gcd(int a，in

17、t b)if(0 = a )return b；if( 0 = b)return a；if(a b)swap(a，b)；int c； 大素数p的算法，也可以用在一张素数表中随机取一个数int getPrime()int PTableLEN=2, 3, 5, 7, 。17519, 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599, 17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683, 17707, 17713, 17729, 17737, 17747, 17749, 17761,

18、17783, 17789, 17791, 17807, 17827, 17837, 17839, 17851, 17863;/此为一张大素数表srand(time(NULL); int p_index=rand()%LEN; return PTablep_index;算法中验证一个数是否为素数，使用了方法int prime(int p)int i,j;for(i=2;ip;i+)j=p%i;if(j=0)return 0;return 1;/判断是否为素数,若为素数则返回1其中不需要检测要p，其中有重复，只要检测到程序修改为int prime(int p)int i,j,n;n=(int)sq

19、rt(p);/对q取一下开方n+;for(i=2;in;i+)j=p%i;if(j=0)return 0;return 1;/判断是否为素数,若为素数则返回1七、专业课程设计总结总结可以包括：课程设计过程的收获、遇到的问题，遇到问题解决问题过程的思考、程序调试能力的思考，对该课程组织和考核方式的建议等。 其次，学会了通过数组随机选取其中的一个数，例如：srand(time(NULL); int p_index=rand()%LEN; return PTablep_index;然后，又练习了一下程序调试，先通过取固定值得到一个正确的结果，再注释掉，取一般值得到一个结果，两相比较来发现并解决问题。同时，在遇到困难问题时，可以通过查书或上网寻找解决问题的办法，但是一定要有自己的思考。并且，我发现，当素数很大时，计算它的生产元时速度会很慢，等的时间很长，因此，我设定当算出一定数量的生成元时就停止继续运算，从算出来的生成元当中选取一个生成元即可。最后，对ELGamal数字签名有了更好的理解，ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。 16