实现RSA算法 [英] Implementing RSA algorithm
问题描述
我有任务来实现RSA算法，我在Cormen的书中读到它，并获得大部分信息来自那里。我想，直到我遇到大的 P 和①素数，它的工作好。有关250和较低的加密和解密工作良好，但是如果他们是更大的数字，模块化求幂返回负数，这是没有意义的。
我知道，加密的数字不能比更大的n 。我看，我也可以反算模通过使用扩展GCD算法，并采取 X 对值，但是当我试图调用 extendedEuclid（PHI，E ）[1] 它返回比RSA类的函数不同的值。我该如何解决这个问题？
下面是code为所有需要的组件来计算键。
Euclid算法
公共类欧几里得{
公共静态INT欧几里得（INT A，INT B）{
如果（A＆LT; B）{
INT TMP = A;
A = B;
B = TMP;
}
如果（B == 0）{
返回;
} 其他 {
返回欧几里得（B，A％B）;
}
}
公共静态INT [] extendedEuclid（INT A，INT B）{
如果（A＆LT; B）{
INT TMP = A;
A = B;
B = TMP;
}
如果（B == 0）{
返回新INT [] {A，1，0};
} 其他 {
INT瓦尔斯[] = extendedEuclid（B，A％B）;
INT D =瓦尔斯[0];
INT X =丘壑[2];
INT Y =瓦尔斯[1] - （int）的Math.floor（A / B）*瓦尔斯[2];
返回新INT [] {D，X，Y};
}
}
}
模块化求幂
公共类模块{
公共静态INT modularExponentation（INT A，INT B，INT N）{
INT C = 0;
INT D = 1;
字符串binaryString = Integer.toBinaryString（B）;
的for（int i = 0; I＆LT; binaryString.length（）;我++）{
C = 2 * C;
D =（D * D）％N;
如果（binaryString.charAt（ⅰ）=='1'）{
C = C + 1;
D =（D * A）％N;
}
}
返回D组;
}
}
RSA发电机
公共类RsaKeyGenerator {
INT D组;
INTê;
INT N;
公共RsaKeyGenerator（）{
INT P = 827;
INT Q = 907;
N = P * Q;
INT披=（P - 1）*（Q - 1）;
E = computeCoPrime（PHI）;
D = invMod（即PHI）;
的System.out.println（众：+ E）;
的System.out.println（私人+ D）;
}
私有静态诠释computeCoPrime（INT PHI）{
INT E = 2;
而（Euclid.euclid（即PHI）！= 1）{
Ë++;
}
返回e的;
}
私人诠释invMod（INT A，INT N）{
INT A0，N0，P0，P1，Q，R，吨;
P0 = 0;
P1 = 1;
A0 =一个;
N0 = N;
Q = N0 / A0;
R = N0％A0;
而（R＆0）{
T = P0 - Q * P1;
如果（T＆GT; = 0）{
T = T％N;
} 其他 {
吨=正 - （（-t）％N）;
}
P0 = P1;
P1 = T;
N0 = A0;
A0 = R;
Q = N0 / A0;
R = N0％A0;
}
返回P1;
}
公众诠释加密（INT NUM）{
返回Modular.modularExponentation（NUM，E，N）;
}
公众诠释解密（INT密码）{
返回Modular.modularExponentation（密码，D，N）;
}
公共静态无效的主要（字串[] args）{
RsaKeyGenerator RSA =新RsaKeyGenerator（）;
INT CIP = rsa.encrypt（1343）;
的System.out.println（CIP）;
的System.out.println（rsa.decrypt（CIP））;
}
}
你面临的问题是整数溢出，所以如果你想存储超过2 ^ 231-1一个数字高于有符号整数刚刚ISN 'T可能。那么，最终发生了，当你打的限制是，该数字环绕-2 ^ 31 -1。
您想要做的是寻找到可以让你存储更大的数字，应该很好地工作BigInteger类。
整数溢出发生在这条线的ModularExponentiation类：
D =（D * A）％N;
I had the task to implement RSA algorithm, I read about it in Cormen's book and got most of information from there. I thought it worked good until I faced large p and q primes. For numbers about 250 and lower encryption and decryption works good, however if they are larger, modular exponentation returns negative numbers, which doesn't make sense.
I know that encrypted number can't be larger than n. I read that I can also compute inverse modulo by using extended GCD algorithm and taking x as that value, but when I tried calling extendedEuclid(phi, e)[1] it returned different values than function in RSA class. How can I fix it ?
Here is code for all needed components to compute keys.
Euclid Algorithm
public class Euclid {
public static int euclid(int a, int b) {
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}
if (b == 0) {
return a;
} else {
return euclid(b, a % b);
}
}
public static int[] extendedEuclid(int a, int b) {
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}
if (b == 0) {
return new int[]{a, 1, 0};
} else {
int vals[] = extendedEuclid(b, a % b);
int d = vals[0];
int x = vals[2];
int y = vals[1] - (int) Math.floor(a / b) * vals[2];
return new int[]{d, x, y};
}
}
}
Modular Exponentation
public class Modular {
public static int modularExponentation(int a, int b, int n) {
int c = 0;
int d = 1;
String binaryString = Integer.toBinaryString(b);
for (int i = 0; i < binaryString.length(); i++) {
c = 2 * c;
d = (d * d) % n;
if (binaryString.charAt(i) == '1') {
c = c + 1;
d = (d * a) % n;
}
}
return d;
}
}
RSA generator
public class RsaKeyGenerator {
int d;
int e;
int n;
public RsaKeyGenerator() {
int p = 827;
int q = 907;
n = p * q;
int phi = (p - 1) * (q - 1);
e = computeCoPrime(phi);
d = invMod(e, phi);
System.out.println("Public: " + e);
System.out.println("Private: " + d);
}
private static int computeCoPrime(int phi) {
int e = 2;
while (Euclid.euclid(e, phi) != 1) {
e++;
}
return e;
}
private int invMod(int a, int n) {
int a0, n0, p0, p1, q, r, t;
p0 = 0;
p1 = 1;
a0 = a;
n0 = n;
q = n0 / a0;
r = n0 % a0;
while (r > 0) {
t = p0 - q * p1;
if (t >= 0) {
t = t % n;
} else {
t = n - ((-t) % n);
}
p0 = p1;
p1 = t;
n0 = a0;
a0 = r;
q = n0 / a0;
r = n0 % a0;
}
return p1;
}
public int encrypt(int num) {
return Modular.modularExponentation(num, e, n);
}
public int decrypt(int cipher) {
return Modular.modularExponentation(cipher, d, n);
}
public static void main(String[] args) {
RsaKeyGenerator rsa = new RsaKeyGenerator();
int cip = rsa.encrypt(1343);
System.out.println(cip);
System.out.println(rsa.decrypt(cip));
}
}
The problem you're facing is integer overflow so if you're trying to store a number higher than 2^31 -1 in a signed integer which just isn't possible. So what ends up happening when you hit that limit is that the number wraps around to -2^31 -1.
What you want to do is look into the BigInteger class which will let you store much bigger numbers and should work fine.
The integer overflow happens at this line in the ModularExponentiation class:
d = (d * a) % n;
这篇关于实现RSA算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
