2022年elgamaml签名设计报告 .pdf

《2022年elgamaml签名设计报告 .pdf》由会员分享，可在线阅读，更多相关《2022年elgamaml签名设计报告 .pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、专业课程设计 I 报告（ 2008 / 2009 学年 第 二 学期）题目：ElGamal 签名设计专业信息安全学生姓名吴俊锋班级学号B08030216 指导教师王志伟指导单位南京邮电大学日期2010.4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 17 页 - - - - - - - - - 1 指导教师成绩评定表学生姓名班级学号专业评分内容评分标准优秀良好中等差平时成绩认真对待课程设计，遵守实验室规定，上机不迟到早退，不做和设计无关的事设计成果设计的科学、合理性功

2、能丰富、符合题目要求界面友好、外观漂亮、大方程序功能执行的正确性程序算法执行的效能设计报告设计报告正确合理、反映系统设计流程文档内容详实程度文档格式规范、排版美观验收答辩简练、准确阐述设计内容，能准确有条理回答各种问题，系统演示顺利。评分等级指导教师简短评语指导教师签名日期备注评分等级有五种：优秀、良好、中等、及格、不及格名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 17 页 - - - - - - - - - 2 Elgamal 签名设计一、课题内容和要求主要实现的模

3、块包括，计算体系参数，计算密钥，对文件签名，验证签名文件。该部分可参考前面给出的问题描述再加以细化一些计算体系参数随机素数 p，用户的私有密钥 x，g 和 x 计算得到的整数 y，消息 m，随机数 k。计算密钥公开密钥（ p，g，y） ，私有密钥 x 对文件签名任何一个给定的消息都可以产生多个有效的ELGamal 签名。验证签名文件验证算法能够将上述多个ELGamal 签名中的任何一个当作可信的签名接受。二、设计思路分析ElGamal 算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。密钥对产生办法首先选择一个素数p，两个随机数 , g 和 x，g, x p,

4、计算 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 p ) = gM ( mod p ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整

5、理 - - - - - - - 第 3 页，共 17 页 - - - - - - - - - 3 同时一定要检验是否满足1= a p。否则签名容易伪造。ElGamal 签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。 素数 p 必须足够大， 且 p-1至少包含一个大素数。因子以抵抗Pohlig & Hellman算法的攻击。 M一般都应采用信息的 HASH 值( 如 SHA 算法)。ElGamal 的安全性主要依赖于p 和 g，若选取不当则签名容易伪造，应保证g 对于 p-1 的大素数因子不可约。一般的 ElGam数字签名方案在系统中有两个用户A和 B，A要发送消息到 B，并对发送的消

6、息进行签名。 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= (mod p) 作为公钥。将公钥 y 存放于公用的文件中。第二步： 随机选取 k 1,p-1且 gcd(k,(p-1)=1，计算 r= (mod p)。对 一般的ElGa

7、mal 型 数字签 名方 案有 签名 方 程（ Signature Equation ） ：ax=bk+c(mod(p-1) 。其中(a ，b，c) 是(h(m),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) 是否成立。在该部分中叙述每个模块的功能要求或者如何开展此题目的求解？三、

8、概要设计在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明 （如果指定存储结构请写出该存储结构的定义，如果用面向对象的方法，应该给出类中成员变量和成员函数原型声明）。整个程序的流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 17 页 - - - - - - - - - 4 产生素数 p 由用户选择素数 p 的范围，来算出p 函数定义为int prime_number_p(); 产生随机数 g g 是一个在 1-（p-1）中的一

9、个随机数函数为 int random_number_g(int p) 产生一个随机数g 输入私钥x 计算出公钥y 输入 m 计算出签名（a，b）验证签名产生一个素数p 由用户输入产生素数的范围 n,m P-m 判断 m 是否为素数m=m-1 mn Y N N Y 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 17 页 - - - - - - - - - 5 p 是选择的大素数利用随机函数 rand()%p来得 g。产生公钥 y 自定义函数为 int PKI_y(int

10、p,int g,int x) P 是产生的大素数， g 是大素数的生成元， x 是私钥计算公式 y=gx(mod p) 产生 m 签名（ a，b）自定义函数void elg_sign_develop(int g,int p,int x,int m) g 是 p 的生成元， p 是大素数， x 是私钥， m 是要签名的数据验证签名自定义函数名 void elg_sign_test(int y,int p,int m,int g,char name) y 是公钥， p 是大素数， m 是签名的数据， g 是大素数的生成元b=i 计算a= gk ( mod p )i=1 x*a+k*b)%(p-1)

11、=m i=i+1 输出 a 产生一个随机数 k K 与 p-1 互质Y N Y N 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 17 页 - - - - - - - - - 6 四、详细设计#include #include #include int 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

12、-) if(prime(p)=1) return p; 计算i=(ya)*(ab)%p; 计算j=(gm)%p; i=j Y N 输出签名正确输 出 不 是name 的签名名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 17 页 - - - - - - - - - 7 / 求出 n,m 之间的最大素数/*-*/ int prime_number_p() int p,m,n; cout 为一组用户产生一个公钥P(p 为素数 )endl; cout 请输入 p 所在范围n，

13、m(系统将选择最大的素数P)endl; coutn; coutm; p=prime_number_max(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; else 名师资料总结 - - -精

14、品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 17 页 - - - - - - - - - 8 s0=a; s1=b; for(int i=1;im; if (mp) cout 无法对输入的m 进行签名 ,请重新输入 endl; m=m_develop(p); return m; int 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

15、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+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 17 页 - - - - - - - - - 9 a*=g; a%=p; /while(m!=(a*x+k*i)%(p-1) /i+;b=i; for(i=0;ip-1;i+) b=i;

16、 if(x*a+k*b)%(p-1)=m) break; k=0;/丢弃随即数K coutm 的数字签名是（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 是用户

17、name 签名的。 endl; else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 17 页 - - - - - - - - - 10 cout 不是用户 name 签名的 endl; / 验证签名/*/ main() int p,g,x,y,m,i; a=b=1; char name; p=prime_number_p();/ 产生大素数p g=Random_number_g(p);/ 产生随即数g cout此用户组的公共参数为p=p g=gendl; cout

18、输入用户名 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:cout 结束程序请输入0i; if(i=0) exit(0); else goto jj; 五、测试数据及其结果分析运行 exe文件的大素数 p的产生和 g 的产生用户名

19、以及密钥x，和公钥 y 的生成名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 17 页 - - - - - - - - - 11 签名（ a，b）的产生和验证进行第 2次测试名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 17 页 - - - - - - - - - 12 由以上两幅截图可知，在私有密钥x、要签名的消息m相同，但素数 p、g 的生

20、成元、随机数 k 不相同的情况下，签名都是有效的，说明源程序代码正确。对于不同的私钥x，和要签名的 m 不同，产生的签名也不一样。六、调试过程中的问题此程序仅仅局限于int 型，int 对于文件还有安全性较差。超过int 就会出现错误这就出现错误了。我们可以进行扩充。把int 的数用一个数组来表示。大家都扩到128 位。密码也名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 17 页 - - - - - - - - - 13 按照一定方法扩到128 位。对于 m 则可以使

21、用 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

22、l=0;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 ；

23、a = b；b = c；int gcd(int a ，int 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, 1

24、7707, 17713, 17729, 17737, 17747, 17749, 17761, 17783, 17789, 17791, 17807, 17827, 17837, 17839, 17851, 17863;/ 此为一张大素数表srand(time(NULL); int p_index=rand()%LEN; return PTablep_index; 算法中验证一个数是否为素数，使用了方法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 17 页 - - -

25、 - - - - - - 15 int prime(int p) int i,j; for(i=2;ip;i+) j=p%i; if(j=0)return 0; return 1; / 判断是否为素数,若为素数则返回1 其中不需要检测要p，其中有重复，只要检测到p程序修改为int prime(int p) int i,j,n; n=(int)sqrt(p);/ 对 q 取一下开方n+; for(i=2;in;i+) j=p%i; if(j=0)return 0; return 1; / 判断是否为素数,若为素数则返回1 七、专业课程设计总结总结可以包括：课程设计过程的收获、遇到的问题，遇到问题

26、解决问题过程的思考、程序调试能力的思考，对该课程组织和考核方式的建议等。其次，学会了通过数组随机选取其中的一个数，例如：srand(time(NULL); int p_index=rand()%LEN; return PTablep_index; 然后，又练习了一下程序调试，先通过取固定值得到一个正确的结果，再注释掉，取一般值得到一个结果，两相比较来发现并解决问题。同时，在遇到困难问题时，可以通过查书或上网寻找解决问题的办法，但是一定要有自己的思考。并且，我发现，当素数很大时，计算它的生产元时速度会很慢，等的时间很长，因此，我设定当算出一定数量的生成元时就停止继续运算，从算出来的生成元当中选取

27、一个生成元即可。最后，对 ELGamal数字签名有了更好的理解，ElGamal算法既能用于数据加名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 17 页 - - - - - - - - - 16 密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 17 页 - - - - - - - - -