背景

說到最知名、使用最廣泛的非對稱式加密,一定就是RSA演算法了,
RSA是由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）在1977年一起提出的(RSA 就是他們三人姓氏開頭字母拼在一起組成的),雖然不是第一個非對稱式加密,但是第一個提出完整流程的演算法,由於加密原理好懂,所以非常受大家青睞

數學難題

非對稱式加密幾乎都建立在無法逆運算的數學難題,而RSA所使用的就是......質因數分解
沒錯就是"質因數分解",連國中生都會的數學問題,但其實仔細想想,學校是不是沒教質因數分解的快速算法
而是要我們一個一個去試從2,3,5...直到完成分解,這不是老師懶得教,而是目前並沒有很有效的質因數分解的辦法
在學校考的頂多幾百幾千而已,所以感覺還ok,但如果給超超超大的質數相乘後叫我們分解哩?
像是2個2的2048次方等級的質數相乘,那在分解它還會容易嗎?
而RSA就是基於這種數學問題來保證其不可破解

如何運作

今天先介紹運作方法,數學原理以後再補
1.選擇兩個超超超大質數p,q,現在推薦2的2048或4096次方等級的質數(p,q不要太靠近不然會有問題)
2.把兩個質數p,q相乘成n(就這麼暴力)
3.計算phi(n)
- phi是歐拉函式,意為小於該數但和該數互質的數的有幾個
- ex:phi(5)=4,其中1,2,3,4都和5互質有4個, phi(7)=6,其中1,2,3,4,5,6都和7互質有6個
- phi是積性函式意為:n=pxq,而phi(n)=phi(p) x phi(q)
- 值得注意的是如果p是質數那phi(p)=p-1(質數的定義)
4.取一個公鑰e(常為65537)
5.計算私鑰d,其中ed=1 mod phi

• python能用pow(e,-1,phi)
• 也能用擴展歐幾里德
  6.對於明文pt,求pow(pt,e,n)
• python中pow(數,次方,模數)
  7.解密就pow(ct,d,n)就回到pt了

安全性

RSA用2048位元以上的質數目前都沒有暴力破解紀錄
但量子演算法秀爾演算法（英語：Shor's algorithm）預計能在未來量子電腦成熟後
快速分解RSA的質因數問題
所以現在已經在尋找替換RSA的新演算法