从模数和指数重建 RSA 私钥失败

Question

我正在尝试从模数和私有/公共指数重建 RSA 密钥对。比较编码的私钥时，转换对于公钥正确，但对于私钥则失败。当使用此重建私钥/公钥对进行加密时，它在 Java 中可以工作（！），但是当在 PHP 中使用重建密钥对时，解密部分失败（加密正在工作），所以在我看来，重建私钥是不同的到“原始”私钥。仅供参考：使用“原始”密钥对，PHP 中一切正常。所以我的问题是：如何从（BigInteger）模数和私有指数中检索“原始”私钥？编辑：最后查看我的最终编辑我的示例代码显示了公钥与重建密钥的相等性，并且私钥是不同的：Rebuilding of a RSA PrivateKey from modulus & exponentprivateKey equals rebuild: falsepublicKey equals rebuild: true代码：import java.math.BigInteger;import java.security.*;import java.security.interfaces.RSAPrivateKey;import java.security.interfaces.RSAPublicKey;import java.security.spec.InvalidKeySpecException;import java.security.spec.RSAPrivateKeySpec;import java.security.spec.RSAPublicKeySpec;import java.util.Arrays;public class RebuildRSAPrivateKey {    public static void main(String[] args) throws NoSuchAlgorithmException, InvalidKeySpecException {        System.out.println("Rebuilding of a RSA PrivateKey from modulus & exponent");        // rsa key generation        KeyPairGenerator kpGen = KeyPairGenerator.getInstance("RSA");        //kpGen.initialize(2048, new SecureRandom());        kpGen.initialize(2048, new SecureRandom());        KeyPair keyPair = kpGen.generateKeyPair();        // private key        PrivateKey privateKey = keyPair.getPrivate();        // get modulus & exponent        RSAPrivateKey rsaPrivateKey = (RSAPrivateKey) privateKey;        BigInteger modulus = rsaPrivateKey.getModulus();        BigInteger privateExponent = rsaPrivateKey.getPrivateExponent();    }}编辑：以下程序将显示从编码密钥派生的 RSA 私钥/公钥对可以恢复，并且加密和解密可以在 Java 和 PHP 中进行。密钥是不安全的RSA 512 位密钥并经过 Base64 解码。然后从模数和私有/公共指数派生出相同的密钥，并且加密/解密在 Java 中有效，但在 PHP 中无效。这就是为什么我想从模数和指数中获取“原始”RSA 密钥，感谢您的好意帮助。

Answer 1

执行 RSA 解密操作所需的最少信息是模数n和解密指数d。有一种优化可以应用于涉及中国余数定理的 RSA 解密，其中分别对 RSA 素数进行求幂，然后组合以产生最终值，因此RSA 私钥语法中有一些用于此目的的额外字段以及RSAPrivateCrtKey模仿它的Java接口。

现在这里提出的问题是：两个 RSAPrivateCrtKey 实例何时相等？我认为当它们在 RSA 算法中功能相同时，它们是相等的。您要求更狭窄的定义，即当它们的编码形式相等时它们相等。这个定义的问题在于它过于特定于实现。目前，当“Sun”提供商生成密钥对时，它总是对素数进行排序p，q使得p> q。但我喜欢另一种方式，其中p< q。RSAPrivateCrtKey 接口不关心任何一种方式，因为它不进行检查。该接口的 Javadoc 没有指定顺序。您可以更改我的代码以生成与以下内容相同的编码形式当前的“Sun”实现只需反转p.compareTo(q) > 0. 但是，默认实现可以更改以符合我将来的偏好，如果我接管世界的计划成功的话，默认实现就会更改。Javadoc 是规范，只要符合 Javadocs，实现就可以更改。

下面我提供了一个相等函数的实现，其中我尝试合并与规范一致的尽可能广泛的相等概念。也就是说，在 RSA 算法中使用时，任何两个keyEquals返回的RSAPrivateCRTKey 实例都应该产生相同的结果，并且如果返回，则应该至少有一个值会产生不同的结果。truefalse




public static boolean keyEquals(RSAPrivateCrtKey k1, RSAPrivateCrtKey k2) {

    final BigInteger ZERO = BigInteger.ZERO;

    boolean result = true;

    result = result && isConsistent(k1) && isConsistent(k2);

    result = result && k1.getModulus().equals(k2.getModulus());

    BigInteger lambda = computeCarmichaelLambda(k1.getPrimeP(), k1.getPrimeQ());

    result = result && k1.getPublicExponent().subtract(k2.getPublicExponent()).mod(lambda).equals(ZERO);

    result = result && k1.getPrivateExponent().subtract(k2.getPrivateExponent()).mod(lambda).equals(ZERO);

    return result;

}

private static boolean isConsistent(RSAPrivateCrtKey k1) {

    final BigInteger ZERO = BigInteger.ZERO;

    final BigInteger ONE = BigInteger.ONE;

    BigInteger n = k1.getModulus();

    BigInteger p = k1.getPrimeP();

    BigInteger q = k1.getPrimeQ();

    BigInteger e = k1.getPublicExponent();

    BigInteger d = k1.getPrivateExponent();

    boolean result = true;

    result = p.multiply(q).equals(n);

    BigInteger lambda = computeCarmichaelLambda(p, q);

    result = result && e.multiply(d).mod(lambda).equals(ONE);

    result = result && d.subtract(key.getPrimeExponentP()).mod(p.subtract(ONE)).equals(ZERO);

    result = result && d.subtract(key.getPrimeExponentQ()).mod(q.subtract(ONE)).equals(ZERO);

    result = result && q.multiply(k1.getCrtCoefficient()).mod(p).equals(ONE);

    return result;

}

private static BigInteger computeCarmichaelLambda(BigInteger p, BigInteger q) {

    return lcm(p.subtract(BigInteger.ONE), q.subtract(BigInteger.ONE));

}

private static BigInteger lcm(BigInteger x, BigInteger y) {

    return x.multiply(y).divide(x.gcd(y));

}