# **RSA_初體驗**
### Team: `I<3ITLAB`

## 題目：利用提供的e、N、ciphertext，解出Flag
## RSA觀念及介紹
1976年以前，所有的加密方法都是同一種模式：

(1) A選擇某一種加密規則，對信息進行加密。
(2) B使用同一種規則，對信息進行解密。

此方法稱為對稱式加密。這種加密方法有一個最大弱點，A必須把加密規則告訴B，否則無法解密。保存和傳遞密鑰，便是這方法的最大挑戰。

為了解決上述方法遇到的問題，非對稱式加密被提了出來。它的操作方法如下:

(1) B生成兩把密鑰(公鑰和私鑰)。公鑰是公開的，任何人都可以獲得，私鑰則是保密的。
(2) A獲取B的公鑰，然後用它對信息加密。
(3) B得到加密後的信息，用私鑰解密。

RSA加密法即屬於非對稱加密。
在使用RSA加密法時主要會使用到幾個數學觀念:

(1) 尤拉函數 φ(n) : 它代表的是小於或等於n的正整數中與n互質的數的數目。
(2) 尤拉定理 :若n,a為正整數，且n,a互質(即gcd(a,n)=1，則 。
(3) 費馬小定理 : ，它為尤拉定理的特例。
(4) 模反元素 : 。

## RSA的密鑰生成步驟
STEP.1 隨機選擇兩個不相等的質數p和q值。
STEP.2 計算p和q的乘積n。
STEP.3 計算n的尤拉函數φ(n)。 ( φ(n) = (p-1)*(q-1) )
STEP.4 隨機選擇一個整數e，條件是1 <e <φ(n)，且e與φ(n)互質。
STEP.5 計算e對於φ(n)的的模反元素d。
STEP.6 將n和e封裝成公鑰，n和d封裝成私鑰。

## RSA的加密與解密
使用(n,e)對要發送的訊息m加密，利用下面公式求出c:

m^e ≡ c (mod n)

而解密則是使用私鑰(n,d)求出m:

c^d ≡ m (mod n)

## 解題思路
由於私鑰為(n,d)，從上式可以看到只要知道d，就能從c求出m。而d則是從φ(n)和e得知，目前e是已知，所以只要去分解題目提供的n，在根據上述的加密步驟還有公式就可以把m解出來。

## 解題過程
1. 首先瞭了RSA的原理及步驟後，透過GOOGLE找到了 **[FactorDB](http://www.factordb.com)** 這個網站可以線上做因數的分解。

2. 解完後得到
N = p * q
= 1073272790751895298208115032919109 * 1206130192985321597931861298372079

3. 有了p和q之後，就可以求出φ(n)，並且透過φ(n)和e進一步的得知私鑰d(密鑰生成的STEP.6)，d是由歐幾里得演算法求得。這些動作在網路上可以找到簡單的python程式碼實作

from fractions import gcd
import sys

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
def fastExpMod(b, e, m):
    result = 1
    while e != 0:
        if (e&1) == 1:
            # ei = 1, then mul
            result = (result * b) % m
        e >>= 1
        # b, b^2, b^4, b^8, ... , b^(2^n)
        b = (b*b) % m
    return result

ciphertext = 26391362288757932254855463314223757853307296781294155211094052683
p = 1073272790751895298208115032919109 
q = 1206130192985321597931861298372079
e = 65537
phi = (p - 1) * (q - 1)
n = p * q
d = modinv( e, phi )
print(d)

4. 接著從私鑰公式求出餘式m，把m轉換成文字就能求出答案。

m = fastExpMod(ciphertext, d, n)
strm = str(hex(m))
print(strm)


## RSA的可靠性
回顧上面的步驟，可以看到公鑰(n,e)是公開出來的，而n又能推導出最關鍵的私鑰(n,d)。所以乍看之下RSA的加密方法是可以直接被破解。但在實際的狀況之下，n的這個數字通常是非常的大，造成要解出它的質因數p和q並沒有那麼容易。所以，RSA加密的可靠性就建立於有沒有辦法能快速地做出質因數分解的動作上了。

## Reference
[WIKI](https://zh.wikipedia.org/wiki/Wikipedia:%E9%A6%96%E9%A1%B5)
[ITREAD01](https://www.itread01.com/content/1543285398.html)
[jeremy5189](https://gist.github.com/jeremy5189/8916602)
[阮一峰的网络日志](http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html)