Java - BigInteger 奇怪的行为
Java - BigInteger strange behaviour
BigInteger 发生了一些奇怪的事情。我正在尝试为一项任务实施我自己的 RSA。
代码如下,适用于小数字。
如果我选择 p=11、q=5、e=7 和 d=23,那么终端上的输出是
Original message is: 19
Encryption of message is: 24
Decryption of message is: 19
但是,如果我将数字更改为更大的数字,它就不再起作用了。以下代码:
import java.math.BigInteger;
class RSAdumb{
public static void main(String[] args) {
BigInteger m = new BigInteger("19");
BigInteger p = new BigInteger("99989");
BigInteger q = new BigInteger("99991");
BigInteger n = p.multiply(q);
BigInteger e = new BigInteger("65537");
BigInteger d = new BigInteger("4232182107");
BigInteger c = m.modPow(e,n); //Returns a BigInteger whose value is (this^e mod n)
BigInteger check = c.modPow(d,n);
System.out.println("Original message is: "+m.toString());
System.out.println("Encryption of message is: "+c.toString());
System.out.println("Decryption of message is: "+check.toString());
}
}
输出这个:
Original message is: 19
Encryption of message is: 5609974360
Decryption of message is: 2710593036
我已经检查过两次,这些数字适合 RSA。准确地说
e*d = 4232182107 * 65537 = 1 mod 9998000099
哪里
9998000099 = 99989 * 99991 (both primes)
现在,根据我的理解,BigInteger 应该是无限的,所以它不应该是一个边界问题......而不是什么?我总是可以用少量的数字来完成我的任务,但这很荒谬...
e
和d
的要求不是他们的乘积等于1(modn),而是根据 Wikipedia page on RSA.
,它们的乘积必须等于 1 (mod φ(n))
即totient函数,2个素数相乘为(p - 1)(q - 1)
,即997800120
ed (mod φ(n)) 的结果不是1
,而是32589339
.
你的较小数字起作用的原因是因为 5 和 11 的 φ(n) 是 4 * 10 = 40,而 7 * 23 (mod 40 ) 是 1
.
您需要为较大的数字选择一个合适的 d
常量。这是 mode
相对于 φ(n)
的倒数,可以用 BigInteger
's modInverse
method.
计算
BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
BigInteger d = e.modInverse(phi);
这表明 d
为 2598113033
。使用 d
会产生正确的输出。
Original message is: 19
Encryption of message is: 5609974360
Decryption of message is: 19
您在计算私有指数 d 时出错。
首先你需要计算 n 的 phi: φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1)
BigInteger phi = n.subtract(p.add(q).subtract(BigInteger.ONE));
然后你需要取 e 的模逆,以 phi 作为模数得到 d:
d = e.modInverse(phi);
结果是 d = 2598113033
.
供参考:Wikipedia
BigInteger 发生了一些奇怪的事情。我正在尝试为一项任务实施我自己的 RSA。 代码如下,适用于小数字。 如果我选择 p=11、q=5、e=7 和 d=23,那么终端上的输出是
Original message is: 19
Encryption of message is: 24
Decryption of message is: 19
但是,如果我将数字更改为更大的数字,它就不再起作用了。以下代码:
import java.math.BigInteger;
class RSAdumb{
public static void main(String[] args) {
BigInteger m = new BigInteger("19");
BigInteger p = new BigInteger("99989");
BigInteger q = new BigInteger("99991");
BigInteger n = p.multiply(q);
BigInteger e = new BigInteger("65537");
BigInteger d = new BigInteger("4232182107");
BigInteger c = m.modPow(e,n); //Returns a BigInteger whose value is (this^e mod n)
BigInteger check = c.modPow(d,n);
System.out.println("Original message is: "+m.toString());
System.out.println("Encryption of message is: "+c.toString());
System.out.println("Decryption of message is: "+check.toString());
}
}
输出这个:
Original message is: 19
Encryption of message is: 5609974360
Decryption of message is: 2710593036
我已经检查过两次,这些数字适合 RSA。准确地说
e*d = 4232182107 * 65537 = 1 mod 9998000099
哪里
9998000099 = 99989 * 99991 (both primes)
现在,根据我的理解,BigInteger 应该是无限的,所以它不应该是一个边界问题......而不是什么?我总是可以用少量的数字来完成我的任务,但这很荒谬...
e
和d
的要求不是他们的乘积等于1(modn),而是根据 Wikipedia page on RSA.
即totient函数,2个素数相乘为(p - 1)(q - 1)
,即997800120
ed (mod φ(n)) 的结果不是1
,而是32589339
.
你的较小数字起作用的原因是因为 5 和 11 的 φ(n) 是 4 * 10 = 40,而 7 * 23 (mod 40 ) 是 1
.
您需要为较大的数字选择一个合适的 d
常量。这是 mode
相对于 φ(n)
的倒数,可以用 BigInteger
's modInverse
method.
BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
BigInteger d = e.modInverse(phi);
这表明 d
为 2598113033
。使用 d
会产生正确的输出。
Original message is: 19
Encryption of message is: 5609974360
Decryption of message is: 19
您在计算私有指数 d 时出错。
首先你需要计算 n 的 phi: φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1)
BigInteger phi = n.subtract(p.add(q).subtract(BigInteger.ONE));
然后你需要取 e 的模逆,以 phi 作为模数得到 d:
d = e.modInverse(phi);
结果是 d = 2598113033
.
供参考:Wikipedia