# RSA_初體驗
###### tags: `ns107`
組名：ls
## 題目
e = 65537

N = 1294506718235478161592096722917508216492977651068363875076991157611

ciphertext = 26391362288757932254855463314223757853307296781294155211094052683

## 簡介
RSA會利用以下方式加密、解密：
* 先找出兩個質數p、q，令 N = p * q
* 根據歐拉函數求得：r = Φ(N) = (p-1) * (q-1)
* 選擇一個小於 r 的整數 e，使得 e 和 r 互質
* 找到符合 e*d mod(Φ(N)) = 1 的 d ( 即：d是e在模數Φ(N) 下的模反元素 )
* (N,e) 為公鑰，(N,d) 為私鑰
* 加密：C(ciphertext) = M^e mod N
* 解密：M(plaintext) = C^d mod N

## 解題
對N進行質因數分解，找出p、q，得出N再計算d，即可進行解密。

1. 對N進行質因數分解
利用[此網頁](http://factordb.com/)對N進行質因數分解，分解結果如下圖：
可得到
p = <font color=blue>1073272790751895298208115032919109</font>
q = <font color=blue>1206130192985321597931861298372079</font>

2. 計算N、d，並對C進行解密
使用python計算，程式碼如下：

    from Crypto.Util.number import *
    import gmpy2

    e = 65537
    N = 1294506718235478161592096722917508216492977651068363875076991157611
    
    #從factordb.com得出的p、q
    p = 1073272790751895298208115032919109
    q = 1206130192985321597931861298372079

    phi_n = (p-1)*(q-1)
    d = inverse(e, phi_n)

    C = 26391362288757932254855463314223757853307296781294155211094052683
    m = pow(C, d, N)

    print long_to_bytes(m)

3. 解密結果

## 補充 - 安裝gmpy2
這題不難，比較麻煩的是安裝gmpy2，所以對安裝gmpy2進行補充。

環境：kali linux (原本想在windows上安裝但一直沒成功)

1. 在linux輸入`pip install gmyp2`會發現缺少兩個文件：mpfr.h、mpc.h，所以要先下載此兩個文件
2. 下載mpfr.h
* 從 ftp://ftp.gnu.org/gnu/mpfr/ 下載最新版本的mpfr壓縮包，我下載的版本是mpfr-4.0.2
* 在下載目錄下進行解壓縮 `unzip mpfr-4.0.2.zip`
* 輸入以下指令完成安裝：

    cd mpfr-3.1.5

    ./configure

    make

    make check

    VERBOSE=1 make check

    make install

3. 下載mpc.h
* 從 ftp://ftp.gnu.org/gnu/mpc/ 下載最新版本的mpc壓縮包，我下載的是mpc-1.1.0
* 在下載目錄下進行解壓縮 `tar -zxvf mpc-${v}.tar.gz && cd mpc-${v}`
* 輸入以下指令完成安裝：

    ./configure

    make && make check && make install

4. 輸入 `pip install gmpy2` 即可順利安裝gmpy2

## Reference
https://www.twblogs.net/a/5b8c22c02b7177188330b511
https://www.cnblogs.com/pcat/p/5746821.html
https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95