用Euler theorem 證明 RSA 演算法時, 有個缺陷:當想要加解密的整數值若剛好等於所挑選的兩個質數p或q, 因為 n=p*q, 所以GCD(p,n)=p, 且GCD(q,n)=q, 並非是 1,造成Euler theorem並不適用. 用Java寫個程式驗證看看,在 1~100 整數裏面, 任取兩個質數來測試,到底加解密是否仍然可行,底下是原始碼,若加解密過程出現不相等情況就會印出錯誤訊息,經測試結果顯示,任何選取兩個小於 100 的質數乘積所形成的整數空間Z={x|x < (p*q)},當將它用RSA演算法來將該所選取的質數拿去加解密,仍然是適用的.或許可以直接就認定任取兩個質數(p,q)下面式子是成立的:
p^(ed) mod n = p -- (1)
q^(ed) mod n = q -- (2)
其中 n = p*q, φ = (p-1) * (q-1), (e*d) mod φ =1, 1 < e < φ
另外測試程式顯示結果可以發現 e 是有機會等於 d 的, 如果用這組key (e,d) 加解密到底安不安全的?我也不知道
// RSA algorithm:
// ( p, q) are two prime number
// step1: n = p*q
// step2: φ = (p-1) * (q-1)
// step3: choose e : 1 < e < φ, GCD(e,φ) =1 to guarantee d exist
// step4: calculate d: e*d mod n = 1
// step5: encode and decode
// step5a: encode p and decode through: ( p^e )^d mod(n) to see if equals to p
// step5b: encode q and decode through: ( q^e)^d mod(n) to see if equals to q
import java.io.*;
import java.util.List;
import java.util.ArrayList;
import java.math.BigInteger;
import java.util.Base64;
class TestRSA {
private static boolean isPrime(int n) {
if ( n % 2 == 0 ) return false;
for(int i = 3; i * i <= n; i += 2) {
if(n%i==0) return false;
}
return true;
}
private static boolean coprime(int a, int m) {
int r;
while ( m > 0 ) {
r = a % m;
a = m;
m = r;
}
if( a==1 ) return true;
else return false;
}
private static int modinv(int d, int n) {
int a,q,r,tf;
int tt = 0;
int ts = 1;
a = n;
while ( d > 0 ) {
q = a / d;
tf = tt - q *ts ;
tt = ts;
ts = tf;
r = a % d;
a = d;
d = r;
}
if (a != 1) return 0;
return ( tt + n) % n;
}
public static void main(String[ ] args ) {
List < Integer > prime = new ArrayList < Integer > ( );
for(int i = 1; i < 100; i ++ ) { if( isPrime(i) ) prime.add(i); }
for(int pp : prime ) {
boolean test = true;
BigInteger p = new BigInteger(""+pp);
for(int qq:prime ) {
if( pp==qq ) continue ;
BigInteger q = new BigInteger(""+qq);
int nn = pp*qq; // step 1: n = p*q
BigInteger n = new BigInteger(""+nn);
int φ = (pp-1)*(qq-1); // step 2: φ = (p-1) * (q-1)
for(int ee=2; ee <φ; ee ++){// step 3: choose e such that 1 < e < φ and gcd(e,φ) =1
if( coprime(ee, φ) ) {
BigInteger e = new BigInteger(""+ee);
int dd = modinv(ee, φ); // step 4: d = modinv(e,φ);
BigInteger d = new BigInteger(""+dd);
BigInteger py = p.modPow(e,n); // step 5a: py = p^e mod n , px =py^d mod n
BigInteger px = py.modPow(d,n); // decode py
BigInteger qy = q.modPow(e,n); // step 5b: pq= q^e mod n , qx =pq^d mod n
BigInteger qx = qy.modPow(d,n); // decode qy
String text="(p,q) mod n =("+pp+","+qq+") mod "+nn+":enc-dec:("+px.toString()+","+qx.toString()+")\t(e,d) mod φ =("+ee+","+dd+") mod "+φ;
if( ee==dd ) text = text +"\tsame (e=d)";
if( ! ( q.toString().equals(qx.toString()) && p.toString().equals(px.toString()) ) ) {
text = text +"\tError!";
test = false;
System.out.println(text);
}
} // key pair exist
} // for all the key pair (e,d) need to test
} // for all the prime number need to test
if( test ) System.out.println(""+pp+"->全正確");
else System.out.println(""+pp+"->錯誤!!");
}// end of test loop
} // end of main
}// end of TestRSA
沒有留言:
張貼留言