# 學習筆記：RSA非對稱加密(python)

## 簡介&基本原理
RSA是一種非對稱加密，也就是加密與解密分別由公鑰與私鑰進行。公鑰用於加密，私鑰用於解密，公鑰加密的訊息只有私鑰解的開。(用於數位簽名時，可能變成私鑰加密，公鑰解密)
過去使用對稱式加密時，加解密兩方都需要知道密鑰，而密鑰傳輸的過程難免會有風險。這種風險可以由非對稱式加密避免，因為只要將公鑰傳遞出去就好，私鑰只要不洩漏就是安全的。(不考慮時間攻擊的話)

## 擴展歐幾里得
#### 歐幾里得算法(輾轉相除法)
就是普通的輾轉相除法
$gcd(a,b)=gcd(b,a\%b)$
$gcd(a,0) = a$
實作也很簡單

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

#### 擴展歐幾里得
擴展歐幾里得算法是用來求只知$a$、$b$下$ax+by=gcd(a,b)$的$x$、$y$

$ax+by=gcd(a,b)$
$\ \ \ \ \ \ \ \ \ \ \ \ \ =gcd(b,a\ mod \ b)$
$\ \ \ \ \ \ \ \ \ \ \ \ \ =gcd(b,a-\lfloor\frac{a}{b} \rfloor b$
$\ \ \ \ \ \ \ \ \ \ \ \ \ =bx^{\prime}+(a-\lfloor\frac{a}{b} \rfloor b)y^{\prime}$
$\ \ \ \ \ \ \ \ \ \ \ \ \ =ay^{\prime}+b(x^{\prime}-\lfloor\frac{a}{b} \rfloor y^{\prime})$
得$x=y^{\prime}$、$y=x^{\prime}-\lfloor\frac{a}{b} \rfloor y^{\prime}$
所以只要先求出$x^{\prime}$和$y^{\prime}$就好了
因為$gcd(a,0)=a$，遞迴到$gcd(a,0)$時$y^{\prime}=1$，$x^{\prime}=0$
代入公式就可以得到前一層遞迴的$x$,$y$了

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    gcd, x, y = extended_gcd(b, a % b)
    
    return gcd, y, x - a//b * y

## 算模擬元
當使用擴展歐幾里得找到一組$x$、$y$滿足$ax+by=1=gcd(a,b)$時，可得出$ax≡1(mod\ b)$，$x$就是$a$的模反元素

## 密鑰生成
1. 挑選兩個質數$p、q$ ，$n = pq$
2. $φ(n)=φ(p)φ(q)=(p-1)(q-1)$
3. 求$e$，在1到$φ(n)$之間選一數$e$，且滿足$gcd(e,φ(n))=1$
(滿足此條件才能算模反元素，第四步會用到)
5. 計算$e$與$φ(n)$的模逆元$d$，也就是滿足$ed≡1\ mod\ φ(n)$(這是同餘，詳見[模運算](/564I9dxSTf6crJP95qRnlQ))

$p$、$q$、$φ(n)$、$d$皆要避免洩漏
公鑰對$(e,n)$
私鑰對$(d,n)$

## 加密
$M$為明文換成的整數，$C$為加密成的整數
加密:$C=M^{e}\ mod\ n$(其中$M<n$，因為會$mod\ n$)
解密:$M = C^{d}\ mod\ n$
## 解密
解密$M = C^{d}\ mod\ n$
### 原理
>[證明參考wiki](https://zh.wikipedia.org/zh-tw/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95)

$C=M^{e}\ mod\ n$
$C^{d}=(M^{e})^{d}\ mod\ n$
因$ed≡1\ mod\ φ(n)$
故存在整數$k$，使$ed=kφ(n)+1$
$M^{ed}=M^{1+φ(n)}=M*M^{kφ(n)}=M(M^{φ(n)})^{k}$
若$n$與$M$互質，則由歐拉定理可得
$M^{ed}≡M(M^{φ(n)})^{k}≡M(1)^k≡M\ mod\ n$
故$M^{ed}≡M\ mod\ n$
得證

## 實作
github:https://github.com/samsonjaw/RSA

import random
import math

def extended_gcd(a, b):#ax + by = gcd
    if b == 0:
        return a, 1, 0
    gcd, x, y = extended_gcd(b, a % b)
    
    return gcd, y, x - a//b * y

def mod_inverse(a, m):# a x b ≡ 1 (mod n)
    #e x d ≡ (mod phi(n) )
    g, x, y = extended_gcd(a, m)
    
    if(g != 1):
        print('don\'t have inv')
    return x % m

def generate_key(p,q):
    n = p * q
    # phi(n) = phi(p) * phi(q) = (p-1)(q-1)
    phi = (p - 1) * (q - 1)
    e = random.randrange(1, phi)
    g, _, _= extended_gcd(e, phi)
    while g != 1:
        e = random.randrange(1, phi)
        g, _, _= extended_gcd(e, phi)
    d = mod_inverse(e,phi)
    return (e, n), (d ,n)

def encrypt(public_key, plaintext):
    #ciphertext = m^e mod n
    e, n = public_key
    if isinstance(plaintext, int):
        return plaintext ** e % n
    elif isinstance(plaintext, (tuple, list)):
        return [s ** e % n for s in plaintext]

def decrypt(private_key, ciphertext):
    d, n = private_key
    if isinstance(ciphertext, int):
        return ciphertext ** d % n
    elif isinstance(ciphertext, (tuple, list)):
        return [s ** d % n for s in ciphertext]

def encode_int(str):
    int_list = []
    for i in range (len(str)):
        int_list.append(ord(str[i]))
    return int_list

def decode_chr(nums):
    chr_list = []
    for i in range(len(nums)):
        chr_list.append(chr(nums[i]))
    return "".join(chr_list)

# n > plaintext, 2q > p > q
#plaintext(ascii) should < n, or plaintext will loss when decrypt
def main():
    p, q = 181, 281
    print('This program is just for studying. p and q is small, so it is not safe.')
    while True:
        print('=================choose the function=================')
        print('                 k.generate key')
        print('                 e.encrypt')
        print('                 d.decrypy')
        print('                 0.end')
        func = input('input the letter to choose the function:')
        
        if func == 'k':
            public_key, private_key = generate_key(p, q)
            tmp1 = ' '.join(map(str, public_key))
            tmp2 = ' '.join(map(str, private_key))
            print(f'public_key:{tmp1},private_key:{tmp2}')

        elif func == 'e':
            plaintext = input('Input your plaintext.(make sure that each char is < p*q):')
            
            while True:
                u_input = input('please input public key, and split e n by a space:')
                try:
                    e, n = map(int,u_input.split())
                    public_key = (e, n)
                    break
                except ValueError:
                    print('Invalid input. Please ensure your two numbers separated by a space.')

            plaintext_int = encode_int(plaintext)
            tmp = ' '.join(map(str, plaintext_int))
            print(f'plaintext(int): {tmp}')
            ciphertext_int = encrypt(public_key, plaintext_int)
            tmp = ' '.join(map(str, ciphertext_int))
            print(f'ciphertext(int): {tmp}')
            ciphertext = decode_chr(ciphertext_int)
            print(f'ciphertext: {ciphertext}')

        elif func == 'd':
            while True:
                try:
                    u_inpur = input('Input your ciphertext(int) which is split by a space:')

                    ciphertext = [int(x.strip()) for x in u_input.split(' ')]
                    break
                except:
                    print('Invalid input. Please ensure your all numbers separated by a space.')


            while True:
                u_input = input('please input public key, and split e n by a space:')
                try:
                    d, n = map(int, u_input.split())
                    private_key = (d, n)
                    break
                except ValueError:
                    print('Invalid input. Please ensure your two numbers separated by a space.')

            plaintext_int = decrypt(private_key, ciphertext_int)
            tmp = ' '.join(map(str, plaintext_int))
            print(f'plaintext(int):{tmp}')
            plaintext = decode_chr(plaintext_int)
            print(f'plaintext:{plaintext}')
        elif func == '0':
            break
        else:
            print('Invalid input')

if __name__ == "__main__":
    main()

## 安全性
根據上述理論，由於公鑰和私鑰都包含n
要破解RSA似乎只要將n質因數分解，得到p,q就可以算出$φ(n)=(p-1)(q-1)$，進而得到私鑰中的d
然而，就現代數學而言，分解一個足夠大的n是沒有有效算法的，隨著p、q大小的增加，分解n所需的時間也會急遽增加，故只要n夠大，破解RSA幾乎不可能
(以目前的算力而言2048為的n被認為是安全的最小長度)(不考慮時間攻擊的話)

## 應用
1. HTTPS協議就是用RSA傳輸數據
2. 數位簽名 (詳見[數位簽名](/2h6yNrrDSYWD8eDGaAgcsQ))
3. 安全電子郵件
4. 身分認證
5. VPN
.
.
.