RSA Wiki 練習筆記

在 Wiki 上看到這篇 RSA加密演算法 想說來玩玩看，這邊使用 java。

稍微規劃了一些步驟：
1. 定義 p, q
2. 依照 p, q 生成 r, N
3. 找一個符合條件的 e
4. 依照 e, r 找出 d
5. public key 及 private key
6. 選一個數字 n 用 public key 做加密取得密文 c
7. 用 private key 做解密看是否相同
8. 試試看已知 public key 和 密文來破解

---

1. 定義 p, q

以簡單原則來玩，我選擇

p = 5, q = 7

選得非常小看等等反解會不會簡單一點….

---

2. 依照 p, q 生成 r, N

r = (p - 1) * (q - 1) = 4 * 6 = 24
N = p * q = 35

---

3. 找一個符合條件的 e

e 要小於 r 並且和 r 互質，所以這邊隨意指定了
e = 19

---

4. 依照 e, r 找出 d

d 要與 e 互質而且要符合

d * e (mod r) = 1

用很粗淺的 while 迴圈來找看看 (其實不知道會不會無窮迴圈…)

int d = 1;
while ( d * e % r != 1) {
    d++;
}

找到的 d = 43

---

5. public key 及 private key

依照 Wiki 上的敘述，可獲得

public key: (N, e) = (35, 19)
private key: (N, d) = (35, 43)

---

6. 選一個數字用 public key 做加密

這邊選擇
n = 13

依照公式

n^e mod N = c

原本最簡單的做法就是使用 API 來作取餘數的動作

int c = Math.pow(n, e) % N

可是一下子就溢位了哈哈，所以用了簡單的 for 來找

int temp = 1;
for(int i = 0; i < e; i++) {
    temp = (temp * n) % N;
}
int c = temp;

這邊找到的密文
c = 27

---

7. 用 private key 做解密看是否相同

公式

c^d mod N = n

有上面的經驗就知道直接使用 API 會有溢位問題，所以就直接用 for 來取餘數

temp = 1;
for(int i = 0; i < d; i++) {
    temp = (temp * c) % N;
}
int decrypted = temp;

這邊解密後取得
decrypted = 13

喔喔真的成功了!!

---

8. 試試看已知 public key 和 密文來破解

好如果已經知道 (N,e), c 那是否可以破解呢? 因為選的質數都很小，應該不難解吧?
已知條件

(N,e) = (35, 19)
c = 27 

首先 N = p * q
所以可以推測 (其實已經夠明顯了XD)

N = 35 = 5 * 7
p = 5, q = 7

這邊就可以知道

r = (p-1) * (q-1) = 4 * 6 = 24

那這樣回到第 4 步，就可以解開密文了。wwwwwwww

所以難怪說 p 和 q 都要很大，不然公鑰被知道攔截一下訊息就被看光了~~

---

java 程式碼

public static void main(String[] args) {
    int p = 5, q = 7;
    int N = p * q; // 35
    int r = (p - 1) * (q - 1); // 24 
    int e = 19;
    int d = 1;
    while ( d * e % r != 1) {
        d++;
    }
    // found d
    System.out.printf("Public key: (%d, %d)\n", N, e);
    System.out.printf("Private key: (%d, %d)\n", N, d);
    int n = 13;
    int temp = 1;
    for(int i = 0; i < e; i++) {
        temp = (temp * n) % N;
    }
    int c = temp; // get c
    System.out.printf("origin: %d, encrypted: %d\n", n, c);
    temp = 1;
    for(int i = 0; i < d; i++) {
        temp = (temp * c) % N;
    }
    int decrypted = temp; 
    System.out.printf("encrypted: %d, decrypted: %d\n", c, decrypted);
}