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应该是不受限制的,所以它不应是一个边界问题……比可能的是什么?我总是可以用少量的数字来实现这个任务,但这很荒谬...
根据RSA上的Wikipedia页面,对e
且d
不是他们的乘积等于1(mod n)的要求,不是因为他们的乘积必须等于1(modφ(n))。
那就是totient函数,对于2个质数乘以(p - 1)(q - 1)
,即997800120。
结果ED(MODφ(ñ))不是1
,它的32589339
。
您的较小数字起作用的原因是因为5和11的φ(n)是4 * 10 = 40,而7 * 23(mod 40)是1
。
您将需要d
为更大的数字选择适当的常数。这是模逆e
相对于φ(n)
,其可与被计算BigInteger
的modInverse
方法。
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
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句