java - RSA私钥生成问题

Question

我正在使用 Java 开发 RSA 项目。我相信我遇到的唯一问题是我的私钥 (d) 返回 0。计算它的代码:

privateKey = (one.mod(phi)).divide(publicKey); //phi is (p-1)*(q-1), publicKey = 65537

这会返回 0，这实际上没有意义，因为虽然 1/publicKey 很小，但也没有小到无法用 BigInteger 表示，对吗？或者我应该使用 bigDecimal 而不是 bigInteger 吗？

无论如何，这是我的其余代码，也许我的问题在其他地方，有人可以发现它:

package encryptionalgorithms;

import java.math.BigInteger;
import java.util.*;

/**
 *
 * @author YAZAN Sources:
 * http://introcs.cs.princeton.edu/java/78crypto/RSA.java.html
 * http://www.math.rutgers.edu/~greenfie/gs2004/euclid.html
 * http://www.youtube.com/watch?v=ejppVhOSUmA
 * http://stackoverflow.com/questions/5818842/problems-encrypting-a-string-using-rsa-algorithm-in-java
 */
public class EncryptionAlgorithms {

    private static BigInteger p, q, product, phi, publicKey, r, a, b, privateKey, encrypt, decrypt, message, userN, userE, userD;
    private static BigInteger one = new BigInteger("1");
    private static BigInteger badData = new BigInteger("-1");
    private static BigInteger zero = new BigInteger("0");

    public static void main(String[] args) {
        System.out.println(1%5);
        System.out.println(1%7);
        System.out.println(1%15);       


        PKE();
    }

    public static void PKE() { //Private Key Encryption
        Scanner input = new Scanner(System.in);
        Random rand1 = new Random(System.nanoTime());
        Random rand2 = new Random(System.nanoTime() * 16); //to create a second obscure random number

        p = BigInteger.probablePrime(1024, rand1);
        q = BigInteger.probablePrime(1024, rand2);

        product = p.multiply(q); // n = p * q
        phi = (p.subtract(one)).multiply(q.subtract(one)); // m = (p-1) * (q-1)


        publicKey = new BigInteger("65537"); //must be a prime. GCD(e,m)=1  //65537 = 2^16 + 1  // will have to make an algorith for this later
        privateKey = (one.mod(phi)).divide(publicKey); //weakest link <============

//        System.out.println("Public Keys:");
//        System.out.println("e = " + e + " and n = " + n);
//        System.out.println("Private Keys:");
//        System.out.println("d = " + d + " and n = " + n);

        System.out.println("p = " + p);
        System.out.println("q = " + q);
        System.out.println("product = " + product);
        System.out.println("phi = " + phi);
        System.out.println("public key = " + publicKey);
        System.out.println("private key = " + privateKey);
        System.out.println("");


        System.out.println("please enther the message to be encrypted");
        BigInteger mes = new BigInteger(input.next());
        BigInteger ans = encrypt(mes, product, publicKey);
        decrypt(ans, product, privateKey);
    }

    public static BigInteger encrypt(BigInteger num, BigInteger n, BigInteger e) {
        encrypt = num.modPow(e, n);
        System.out.println("encrypted: " + encrypt);
        return encrypt;
    }

    public static BigInteger decrypt(BigInteger enc, BigInteger n, BigInteger d) {
        decrypt = enc.modPow(d, n);
        System.out.println("decrypted: " + decrypt);
        return decrypt;
    }
}

编辑:

我的 println 显示:

1 1 1

p = 11683651600562056634005477385776403179794418655971624032795085543163503940300975548639330643798615166093896158585504 276769992169929021315450826160958799278496700797377192095268145233123067920400723174987798533899537537705553087457675467156 6809579320008488587254143483816119529551389602238180023655212196118671

q = 11844584124366095978365543956926326008887578088031834073074939382672946287878705260334318584438111328291431340401026 502146083483203134993667544626532201979143362560161876857333286102410136255126355930990143722966889344481985463744791592423 4885201092336165962514242782328851534270944932858310655258614396326481

产品 = 13838799426264186334752007568314388817999080436393046698822718780049594131958339754285122812528703328831770507600346 387196178828551045467705258918741851385458709465331658531514221228970233180703647270287552837753141448222019771566054259160 450349111420609315305712076175614925637533331760969764529465148575554436909984186174819968350087737759092473439388442979008 215287412729873605743307221889589355321080925515130587917789192951804915620770181045927041436295136776421205411332865156021 777271758200515616012524267222882737764344732490495401547779959227857738842827307140880624719496653055925158630393545977988 735826751

phi = 13838799426264186334752007568314388817999080436393046698822718780049594131958339754285122812528703328831770507600346 387196178828551045467705258918741851385458709465331658531514221228970233180703647270287552837753141448222019771566054259160 450349111420609315305712076175614925637533331760969764529465148575554201627626936893293844639874310731800586619421002944427 156587163471509103461510413799852863038713660571277312927923885162644159089448617954743333561385124200020571835942175630007 463916426158760345221464487800314073495522857104983376877184157533077326498172757372494358574525589233590623533902867064162 143381600

公钥 = 65537

私钥=0

Answer 1

你不想 split ，

privateKey = (one.mod(phi)).divide(publicKey); //phi is (p-1)*(q-1), publicKey = 65537

您需要模逆，因此使用 BigInteger.modInverse :

privateKey = publicKey.modInverse(phi);

获取一个值使得

privateKey * publicKey ≡ 1 (mod phi)