开发匿名投票系统时，RSA密钥C、D为何总是生成1？

问题原因分析 #

你的代码生成的C、D始终为1，核心问题出在三个地方：

• P、Q不是素数：你用new BigInteger(32, random)生成的是32位随机整数，而非素数。RSA要求P、Q必须是大素数，非素数会导致欧拉函数φ(N)=(P-1)(Q-1)的计算完全不符合RSA要求，后续的逆元计算逻辑失效。
• D的位数过小且未排除1：genCoPrime生成的是16位随机数，远小于32位的P，同时没有排除D=1的情况。当D=1时，它的模逆元C=1（因为1*1 mod φ(N)=1），而且循环条件D.compareTo(P) >0永远不成立，直接退出循环，最终得到C=D=1。
• 冗余的循环条件：genCoPrime已经保证了D和f互质，所以gcd = (C.multiply(D)).gcd(f)必然等于1，这个判断条件永远不会触发循环，导致错误的D（比如1）无法被过滤掉。

修复方案 #

1. 正确生成大素数P、Q #

使用BigInteger的素数生成构造方法，确保P、Q是素数：

do {
    // 第二个参数100表示素数确定性，数值越高越接近真正的素数
    P = new BigInteger(32, 100, random);
    Q = new BigInteger(32, 100, random);
} while (P.equals(Q));

2. 修正genCoPrime方法，排除D=1的情况 #

调整生成的随机数位数，同时确保生成的数不等于1且在合法范围内：

public static BigInteger genCoPrime(BigInteger value, int numBits) {
    BigInteger coPrime;
    do{
        coPrime = new BigInteger(numBits, new Random());
        // 排除1，同时保证coPrime小于value（RSA要求公钥在1<e<φ(N)范围内）
    } while ((value.gcd(coPrime)).compareTo(BigInteger.ONE) > 0 
             || coPrime.equals(BigInteger.ONE)
             || coPrime.compareTo(value) >= 0);
    return coPrime;
}

3. 简化循环条件，过滤C、D为1的情况 #

去掉冗余的gcd判断，增加对C、D是否为1的检查：

do {
    // 调整numBits，比如和f的位数一致，避免生成过小的数
    D = genCoPrime(f, f.bitLength());
    C = D.modInverse(f);
} while (C.equals(BigInteger.ONE) || D.equals(BigInteger.ONE) 
         || C.compareTo(P) > 0 || D.compareTo(P) > 0);

修正后的完整代码 #

Random random = new Random();

BigInteger P, Q, N, C, D, f;

// 生成不相等的大素数P、Q
do {
    P = new BigInteger(32, 100, random);
    Q = new BigInteger(32, 100, random);
} while (P.equals(Q));

N = P.multiply(Q);
f = (P.subtract(BigInteger.ONE)).multiply(Q.subtract(BigInteger.ONE));

// 生成符合要求的公钥D和私钥C
do {
    D = genCoPrime(f, f.bitLength());
    C = D.modInverse(f);
} while (C.equals(BigInteger.ONE) || D.equals(BigInteger.ONE) 
         || C.compareTo(P) > 0 || D.compareTo(P) > 0);

public static BigInteger genCoPrime(BigInteger value, int numBits) {
    BigInteger coPrime;
    do{
        coPrime = new BigInteger(numBits, new Random());
    } while ((value.gcd(coPrime)).compareTo(BigInteger.ONE) > 0 
             || coPrime.equals(BigInteger.ONE)
             || coPrime.compareTo(value) >= 0);
    return coPrime;
}

内容的提问来源于stack exchange，提问作者John Smith