【《Elgamal数字签名公共随机数攻击编程实现分析案例》4100字】

Elgamal数字签名公共随机数攻击编程实现分析案例目录TOC\o"1-3"\h\u27417Elgamal数字签名公共随机数攻击编程实现分析案例 119731.1实现思路 1314641.2程序整体框架 2308281.3关键函数 392121.4Elgamal签名与验证 8308831.5公共随机数攻击 10270301.6结果分析 121.1实现思路Elgamal数字签名方案公共随机数攻击的代码主要分为四大部分：密钥生成，签名生成，签名验证，公共随机数攻击。在密钥生成的这一步中，首先需要解决的是大素数问题，在第三部分中对Elgamal数字签名方案安全性分析中提到过，Elgamal数字签名的安全性非常依赖于大素数p及其原根g，因此必须保证大素数p是安全素数。在这一步中，我选择的做法是：由于大素数p需要随机生成，且p必须要是安全素数，那么可以根据p=2q+1，其中q也是素数，来保证大素数p的安全性。引入q除了能保证大素数p的安全性外，还能使大素数p的原根g的求法更方便。原根g的算法如下：随机选取一个整数g,令g满足1≤g≤p-1，假如g^qmodp不等于1，且g^2modp不等于1，就说明g模p的阶是2q，即p-1，那么g就是模p的原根；如果上述条件不成立的话，就再随机选择g，重复以上步骤，直到选取到满足条件的g为止。p，g都生成后，利用ramdon()函数随机生成私钥x，并通过Java.math包中的modpow()函数求得公钥y值。在签名生成的这一步中，实现的难点是消息散列值的求取。首先，利用ramdon()函数随机生成一个公共随机数K，令K满足1≤K≤p-1，在利用Java.math包中gcd()函数，保证（K，p-1）=1，返回公共随机数K的值。之后对消息M进行处理，在单向散列算法的选择中，我选择了用MD5算法，MD5算法的作用是把任意一个大数据量的信息加密成一个固定长度的大整数，之所以选择它，是因为它有以下几个优点：一是计算比较方便容易；二是该算法有很强的抗修改性，只要是对原数据进行了哪怕一个字节的修改，得到的MD5值都会非常不一样；三是该算法有很强的抗碰撞能力，数据与数据间所得到的的MD5值相似程度非常小，所以很难去伪造数据。总而言之，MD5算法既容易计算安全性又高，所以我选择了它。编码过程中，利用java.security包中的MessageDigest()可以轻松地得到消息M的MD5码，但是在调试过程中发现，得到的MD5码与网站提供值并不一致，出现了缺0的情况，在上网查询之后发现是，字符串在进行进制转换时会忽略开头的0，所以需要在进制转换后修改代码，把0值补上。因为得到的MD5值是32位的字符串形式，不能进行后续签名的计算。因此，利用了java中Biginteger()函数重新构造16位的大整数用于后续签名过程中的计算。在签名（r，s）求解的过程中，因为需要求公共随机数K在模p-1情况下的乘法逆元，利用了Java.math包中的modInverse()函数，对于该函数需要考虑模逆前的参数是否为0或负数，因此后续也对模逆前的参数做了一定的处理，来避免模逆过程会报错。在签名认证的这一步中，没有什么难点，只需要仔细核对公式写成代码时是否由错误即可，利用的是Java中Number类的compareTo()函数，对两个公式进行比较，该代码类设置为了boolean类型，最后会根据公式的比较，假如两者一致，那么就会返回true；假如两者不一致，就会返回Flase。在公共随机数攻击实现的这一步中，难点同签名生成中模逆报错这一点一致，因此，最后在完善了攻击的算法之后，在实现代码的过程中，首先对模逆前的值进行判断，奇偶情况不一时，所求的解也不一，可能会拥有两个解，一个为X，一个为X+q。Elgamal数字签名公共随机数攻击实现的整体的实现思路就是先实现Elgamal数字签名的过程，再对其进行公共随机数攻击的实现。Elgamal数字签名的实现思路为，先考虑前提条件，即大素数p、本原元g、私钥x、公钥y如何去生成，再解决自由输入的明文如何转换成定长的hash值，最后实现数字签名的认证过程。1.2程序整体框架生成大素数p，本原元g，密钥x、y，公共随机数k 生成大素数p，本原元g，密钥x、y，公共随机数k输入明文message输入明文message进行M进行MD5加密，输出消息M的散列值利用消息和签名值进行认证利用消息和签名值进行认证使用相同公共随机数进行攻击，对比私钥是否一致使用相同公共随机数进行攻击，对比私钥是否一致图5-1程序整体框架图1.3关键函数importjava.math.BigInteger;importjava.nio.charset.StandardCharsets;importjava.security.MessageDigest;importjava.util.Random;importjava.security.NoSuchAlgorithmException;importjava.util.Scanner;（1）密钥生成： //生成大素数ppublicstaticBigIntegerlargeProbablePrime()publicclassElgamalEncrypt{publicstaticBigIntegerlargeProbablePrime(){//生成安全素数p BigIntegerq=null;//初始化参数q BigIntegerp=null;//初始化参数p while(true){/while（true）的作用是无限循环语句，在内循环中需要有break才会停止 q=BigIbablePrime(100,newRandom());//生成可能素数q if(q.isProbablePrime(100)){//判断q是否为素数 p=q.multiply(BigInteger.valueOf(2)).add(BigInteger.ONE); //p=2q+1，由于p，q都为Biginteger型，要用multiply()，add()进行运算，BigInteger.valueOf()用来创建Biginteger的值。 if(p.isProbablePrime(100)){//判断生成的p是否为素数 break;//假如p是素数则跳出循环返回p值，假如p不是素数就重新生成随机值 } } } BigIntegerg=primitiveRoot(p);//求p的原根g System.out.println("p:"+p);//输出p System.out.println("g:"+g);//输出q returnp;//返回p}//生成原根gprivatestaticBigIntegerprimitiveRoot(BigIntegerp)privatestaticBigIntegerprimitiveRoot(BigIntegerp){BigIntegerq=p.subtract(BigInteger.ONE).divide(BigInteger.valueOf(2));//初始化参数q，q=(p-1)/2BigIntegerg;do{ g=randomBigInteger(BigInteger.ONE,p.subtract(BigInteger.ONE));//调用生成随机数的函数，生成一个随机数g，令g满足1<g<p-1}while(g.modPow(q,p).compareTo(BigInteger.ONE)==0||g.modPow(BigInteger.valueOf(2),p).compareTo(BigInteger.ONE)==0);//当g^qmodp!=1且g^2modp!=1时，输出g//dowhile语句中，不管while里的条件是否满足，do都会先执行一次，即都会先随机生成一个[1，p-1]的g值returng;} //生成随机数randomBigInteger(BigIntegerstart,BigIntegerend)privatestaticBigIntegerrandomBigInteger(BigIntegerstart,BigIntegerend){BigIntegerrandom;//初始化一个随机数randomdo{random=newBigInteger(100,newRandom());//定义一个Biginteger类}while(pareTo(start)<0||pareTo(end)>0);//当随机数与start和end不同时，输出随机数returnrandom;} //生成密钥generateKey(BigIntegerp,BigIntegerg)privatestaticBigInteger[]generateKey(BigIntegerp,BigIntegerg){BigInteger[]keys=newBigInteger[2];//初始化keys为一个BigInteger的数组BigIntegerprivateKey=randomBigInteger(BigInteger.ONE,p.subtract(BigInteger.ONE));//调用生成随机数的函数，随机生成私钥x，令x满足1≤x≤p-1BigIntegerpublicKey=g.modPow(privateKey,p); //利用modpow()函数，生成公钥y，y=g^xmodpkeys[0]=privateKey;//将私钥x的值放进数组keys中keys[1]=publicKey;//将公钥y的值放进数组keys中System.out.println("privateKey:"+privateKey); //输出私钥System.out.println("publicKey:"+publicKey); //输出公钥returnkeys;}（2）生成签名： //生成公共随机数KBigIntegerGetK(BigIntegerp)privatestaticBigIntegerGetK(BigIntegerp){BigIntegerk=null;//初始化参数Kwhile(true){k=randomBigInteger(BigInteger.ONE,p.subtract(BigInteger.ONE));//调用生成随机数的函数，生成随机数k，令k满足1≤k≤p-1if(k.gcd(p.subtract(BigInteger.ONE)).equals(BigInteger.ONE)){break;//当随机生成的k满足（k，p-1）=1，即k与p-1互质时，输出k}}System.out.println("公共随机数:"+k);//输出公共随机数kreturnk;//该函数返回值为k} //对消息M进行MD5算法求出散列值，stringTohash(Stringstr)publicstaticBigIntegerstringTohash(Stringstr){Stringresult="";//初始化一个resulttry{MessageDigestmd=MessageDigest.getInstance("md5");//初始化实例化mdbyte[]md5=md.digest(str.getBytes(StandardCharsets.UTF_8));//将字节数据转换为十六进制并进行散列函数计算获得密文for(byteb:md5){Stringtemp=Integer.toHexString(b&0xff);//将byte数组转换成16进制，b&0xff是为了取低8位；Integer.toHexString(b);方法传入的值是int类型的，所以当传入byte的时候会自动转换成int类型，又由于byte类型只占8位并且int类型占32位，所以会进行补位，若byte是整数时不会报错，因为前面补的是0。但是若是负数的话就会出现问题，例如byteb=-112；byte的2进制表示为：10010000，java中是以补码的形式进行表示的。这样前面补满22位个1的时候就会出现很多f。if(temp.length()==1){temp="0"+temp;//byte数组中有的值可能小于16，所以转换成16进制的时候用1位就可以表示了。这个时候我们应该在前面加上个0。}result=result+temp;}}catch(NoSuchAlgorithmExceptione){e.printStackTrace();}System.out.println("MD5值:"+result);//输出md5值BigIntegerstr_hash=newBigInteger(result,16);//将string转换成16进制的Biginteger类型System.out.println("hash值:"+str_hash);//输出hash值returnstr_hash;//返回hash值}1.4Elgamal签名与验证（1）签名Signature(BigIntegerp,BigInteger[]keys,BigIntegerk,BigIntegerr,BigIntegerstr_hash) publicstaticBigIntegerSignature(BigIntegerp,BigInteger[]keys,BigIntegerk,BigIntegerr,BigIntegerstr_hash){BigIntegersignature;//初始化参数signature//signature[0]=g.modPow(k,p);//由于r=g^kmodp，本研究讨论相同k情况下的Elgamal数字签名方案，所以最后会生成相同的r，于是就把r放在主函数中生成。//System.out.println("r:"+signature[0]);signature=str_hash.subtract(r.multiply(keys[0])).mod(p.subtract(BigInteger.ONE)).multiply(k.modInverse(p.subtract(BigInteger.ONE)).mod(p.subtract(BigInteger.ONE)));//S=(H(M)-r·x)·k^(-1)mod(p-1)System.out.println("s:"+signature);//输出Sreturnsignature;//返回signature}（2）验证verify(BigIntegerp,BigIntegerg,BigInteger[]keys,BigIntegerr,BigIntegersignature,BigIntegerStr_hash) publicstaticbooleanverify(BigIntegerp,BigIntegerg,BigInteger[]keys,BigIntegerr,BigIntegersignature,BigIntegerStr_hash){BigIntegertemp1=keys[1].modPow(r,p).multiply(r.modPow(signature,p)).mod(p); //初始化temp1=y^r·r^smodpBigIntegertemp2=g.modPow(Str_hash,p); //初始化temp2=g^H(m)modpreturnpareTo(temp2)==0;//因为temp1和temp2都为Biginteger型，所以只能使用compareTo()函数进行比较，当两者相等时，验证通过，返回True；当两者不一致时，返回False}1.5公共随机数攻击已知当使用同样的p、g，私钥x，公钥y下，使用相同的随机数k，对两条不同的消息m1，m2进行签名，得到（r1，S1）与（r2，S2）就可以恢复出私钥，x≡（s1·H(m2)-s2·H(m1))·(s1·r2-s2·r1)^(-1)mod(p-1)，即(S1·r2-S2·r1)·x≡(S1·H(m2)-S2·H(m1))mod(p-1)。令a=(S1·r2-S2·r1)，b=(S1·H(m2)-S2·H(m1))。当a为奇数时，可以模逆；当a为偶数，b为奇数时，可以模逆；当a为偶数，b为偶数时，公式两边同除以2，得：S求出x有两个解，另一解x+q。根据以上分析，代码如下：publicstaticBigIntegerAttack(BigIntegerp,BigIntegerr,BigIntegerS1,BigIntegerS2,BigIntegerstr_hash,BigIntegerstr_hash1){BigIntegera=(S1.multiply(str_hash1)).subtract(S2.multiply(str_hash)); //初始化a，a=(S1·r2-S2·r1)BigIntegerb=r.multiply(S1.subtract(S2)); //初始化b，b=(S1·H(m2)-S2·H(m1))BigIntegera1=a.divide(BigInteger.valueOf(2)); //初始化a1，a1=a/2BigIntegerb1=b.divide(BigInteger.valueOf(2)); //初始化b1，b1=b/2BigIntegerq=p.subtract(BigInteger.ONE).divide(BigInteger.valueOf(2)); //初始化q，q=(p-1)/2if((a.remainder(BigInteger.valueOf(2))).equals(BigInteger.valueOf(0))){//当a是偶数时if((b.remainder(BigInteger.valueOf(2))).equals(BigInteger.valueOf(0))){ //当b是偶数时BigIntegerx=a1.mod(q).multiply(b1.modInverse(q)).mod(q); //x=a1·b1^(-1)modq=(a/2)·(b/2)^(-1)modq=((S1·r2-S2·r1))/2·(((S1·H(m2)-S2·H(m1)))/2)^(-1)mod(p-1)或者x=x+qreturnx;//返回x的值}else{//当a是偶数，b是奇数时BigIntegerx=a.mod(p.subtract(BigInteger.ONE)).multiply(b.modInverse(p.subtract(BigInteger.ONE)).mod(p.subtract(BigInteger.ONE))); //x=a·b^(-1)mod(p-1)=(S1·r2-S2·r1)·(S1·H(m2)-S2·H(m1))^(-1)mod(p-1)returnx;//返回x的值}}else{ //当a是奇数，b是奇数时BigIntegerx=a.mod(p.subtract(BigInteger.ONE)).multip