V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
xiangyuecn
V2EX  ›  程序员

求助: RSA 密钥,已知 modulus、publicExponent、D(privateExponent) 如何推算出 P(prime1)、Q、DP、DQ、InverseQ(coefficient)

  •  
  •   xiangyuecn ·
    xiangyuecn · 2020-04-12 19:13:01 +08:00 · 2293 次点击
    这是一个创建于 1684 天前的主题,其中的信息可能已经有所发展或是发生改变。

    正在写一个 RSA 私钥 PEM 文件的生成,用于轻量级的转换 PKCS#1 、PKCS#8,但卡在了这个反向计算上,不会算😂

    正在写 java 版代码:

    /***
     * 通过公钥指数和私钥指数构造一个 PEM
     * @param modulus 必须提供模数
     * @param exponent 必须提供公钥指数
     * @param dOrNull 私钥指数可以不提供,导出的 PEM 就只包含公钥
     */
    public RSA_PEM(byte[] modulus, byte[] exponent, byte[] dOrNull) {
    	Key_Modulus=modulus;//modulus
    	Key_Exponent=exponent;//publicExponent
    	
    	if(dOrNull!=null) {
    		Key_D=dOrNull;//privateExponent
    		
    		//TODO 如何计算?
    		Val_P=null;//prime1
    		Val_Q=null;//prime2
    		Val_DP=null;//exponent1
    		Val_DQ=null;//exponent2
    		Val_InverseQ=null;//coefficient
    	}
    }
    
    //这些 byte[] 通过 BigInteger 转成大数进行运算
    

    PEM 的解析以前已经写好了,现在 java 代码直接 copy 的 c#的代码,https://github.com/xiangyuecn/RSA-csharp/blob/master/RSA_PEM.cs 以前也是不会算,所有没有加由 Modulus 、Exponent 、D 的直接构造方法,要是加上就完美了

    那么,是怎么样反向计算出 P 、Q 、DP 、DQ 、InverseQ 呢?

    第 1 条附言  ·  2020-04-13 12:31:17 +08:00

    代码已经好了,综合的#5 和 #7 链接中的算法,经过简单测试没有问题。还需要更多的测试,有时间这个java版的也会开源

    /***
     * 通过公钥指数和私钥指数构造一个PEM
     **/
    public RSA_PEM(byte[] modulus, byte[] exponent, byte[] dOrNull) {
    	Key_Modulus=modulus;//modulus
    	Key_Exponent=exponent;//publicExponent
    	
    	if(dOrNull!=null) {
    		Key_D=dOrNull;//privateExponent
    		
    		//反推P、Q
    		BigInteger n = BigX(modulus);
    		BigInteger e = BigX(exponent);
    		BigInteger d = BigX(dOrNull);
    		BigInteger p = findFactor(e, d, n);
    		BigInteger q = n.divide(p);
    		if (p.compareTo(q) > 0) {
    			BigInteger t = p;
    			p = q;
    			q = t;
    		}
    		BigInteger exp1 = d.mod(p.subtract(BigInteger.ONE));
    		BigInteger exp2 = d.mod(q.subtract(BigInteger.ONE));
    		BigInteger coeff = q.modInverse(p);
    		
    		Val_P=p.toByteArray();//prime1
    		Val_Q=q.toByteArray();//prime2
    		Val_DP=exp1.toByteArray();//exponent1
    		Val_DQ=exp2.toByteArray();//exponent2
    		Val_InverseQ=coeff.toByteArray();//coefficient
    	}
    }
    /**java byte是负数,需要加前导0转成正整数**/
    static public BigInteger BigX(byte[] data) {
    	if(data[0]<0) {
    		byte[] c=new byte[data.length+1];
    		System.arraycopy(data,0,c,1,data.length);
    		data=c;
    	}
    	return new BigInteger(data);
    }
    private static BigInteger findFactor(BigInteger e, BigInteger d, BigInteger n) {
    	BigInteger edMinus1 = e.multiply(d).subtract(BigInteger.ONE);
    	int s = edMinus1.getLowestSetBit();
    	BigInteger t = edMinus1.shiftRight(s);
    	
    	long now=System.currentTimeMillis();
    	for (int aInt = 2; true; aInt++) {
    		if(aInt%1000==0 && System.currentTimeMillis()-now>3000) {
    			throw new RuntimeException("推算RSA.P超时");
    		}
    		
    		BigInteger aPow = BigInteger.valueOf(aInt).modPow(t, n);
    		for (int i = 1; i <= s; i++) {
    			if (aPow.equals(BigInteger.ONE)) {
    				break;
    			}
    			if (aPow.equals(n.subtract(BigInteger.ONE))) {
    				break;
    			}
    			BigInteger aPowSquared = aPow.multiply(aPow).mod(n);
    			if (aPowSquared.equals(BigInteger.ONE)) {
    				return aPow.subtract(BigInteger.ONE).gcd(n);
    			}
    			aPow = aPowSquared;
    		}
    	}
    }
    
    第 2 条附言  ·  2020-04-13 16:53:20 +08:00

    BigInteger.toByteArray 对于 RSA的这些字段也有问题,RSA里面正整数应当去掉保证正整数的前导0,生成PEM的时候再加上,不然多出来的这个首位0就是多出了一个字节。

    public RSA_PEM(byte[] modulus, byte[] exponent, byte[] dOrNull) {
    	.....
    		Val_P=BigB(p);//prime1
    		Val_Q=BigB(q);//prime2
    		Val_DP=BigB(exp1);//exponent1
    		Val_DQ=BigB(exp2);//exponent2
    		Val_InverseQ=BigB(coeff);//coefficient
    	.....
    }
    
    /**java byte是负数,需要加前导0转成正整数**/
    static public BigInteger BigX(byte[] data) {
    	if(data[0]<0) {
    		byte[] c=new byte[data.length+1];
    		System.arraycopy(data,0,c,1,data.length);
    		data=c;
    	}
    	return new BigInteger(data);
    }
    /**BigInt导出byte整数首字节>0x7F的会加0前导,保证正整数,因此需要去掉0**/
    static public byte[] BigB(BigInteger bigx) {
    	byte[] val=bigx.toByteArray();
    	if(val[0]==0) {
    		byte[] c=new byte[val.length-1];
    		System.arraycopy(val,1,c,0,c.length);
    		val=c;
    	}
    	return val;
    }
    
    9 条回复    2020-04-14 11:46:48 +08:00
    terencelau
        1
    terencelau  
       2020-04-12 21:12:27 +08:00   ❤️ 1
    如果是 CRT-RSA 的话:
    DP = P mod d
    DQ = Q mod d
    InvQ * Q \equiv 1 mod P

    所以,没有 P, Q 反向计算就是做大数分解
    terencelau
        2
    terencelau  
       2020-04-12 21:13:11 +08:00
    @terencelau 写错了
    DP = d mod P-1
    DQ = d mod Q-1
    xiangyuecn
        3
    xiangyuecn  
    OP
       2020-04-12 22:16:31 +08:00
    @terencelau 要大数分解的意思就是无解了😂
    terencelau
        4
    terencelau  
       2020-04-12 22:20:36 +08:00
    @xiangyuecn 就我的知识水平来看,只有这些是算不出来的
    qwerthhusn
        5
    qwerthhusn  
       2020-04-13 10:09:35 +08:00   ❤️ 1
    lapulasi
        6
    lapulasi  
       2020-04-13 11:53:15 +08:00   ❤️ 1
    如果相对于 N,D 的值比较小,那么通过 Wiener Attack 可以分解 N,得到 P 和 Q 。有了 P 和 Q,就可以算出 DP 、DQ 、InverseQ 。
    xiangyuecn
        7
    xiangyuecn  
    OP
       2020-04-13 12:27:14 +08:00
    @qwerthhusn 这个算法可以,1024 位的只需要 4ms 进行反解

    我另外找到一个算法 https://stackoverflow.com/questions/2921406/calculate-primes-p-and-q-from-private-exponent-d-public-exponent-e-and-the 但需要 8ms 进行反解

    测试生成的 pem 虽然和原 pem 的 P 、Q 不相同,但能正常拿这个 pem 解密公钥加密的内容,不提供 P 、Q 的私钥直接报错,有了就不会报错了

    @terencelau 似乎搞定了😁
    xiangyuecn
        8
    xiangyuecn  
    OP
       2020-04-13 12:33:08 +08:00
    @lapulasi 已经有算法了,1024 位处理速度还可以😁
    terencelau
        9
    terencelau  
       2020-04-14 11:46:48 +08:00
    @xiangyuecn 噢噢,因为我不熟悉 PEM :( 所以,只能看数学方面的问题 😂,这个算法学习了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   973 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 20:47 · PVG 04:47 · LAX 12:47 · JFK 15:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.