一，基本數學知識
1.素數：
也叫質數，特點是除了1和自身，再沒有其他數字能整除它。例如9除了1和9，還有3能整除9，是以9不是素數。
2.歐拉函數：
任意給定正整數n，請問在小于等于n的正整數之中，有多少個與n構成互質關系？（比如，在1到8之中，有多少個數與8構成互質關系？），計算這個值的方法就叫做歐拉函數，以φ(n)表示。
3.因數分解
例如 15可以分解為 15 = 3x5
4.互質關系
例如9和17之間沒有公因數(當然1是不能算的)，是以9和17之間構成互質關系。
5.同餘
例如 ed ≡ 1 (mod φ(n)) 表示ed和1對n同餘。意思是 ed對n求餘的結果和 1對n求餘的結果一樣，即他們有同樣的餘數
二，RSA原理
RSA加密算法主要 由這幾個參數有關：p，q，n，φ(n)，e，d，m，c
p和q：首先p和q是兩個質數，可以任取，但p，q越大RSA越安全
n：n=pxq，n為p和q的乘積，n表示密鑰的長度(公鑰和私鑰)。
φ(n)：φ(n) = (p-1)(q-1)
e：随機選擇的一個整數，要滿足 1<e<φ(n)，且e與φ(n)互質。而且e為公鑰的組成元素
d：e 的模反元素(下面有說怎麼求)，而且e為私鑰的組成元素。求d的公式
m：明文
c：密文
RSA的公鑰，私鑰和加密，解密方式如下表：
| 公鑰KU (由n和e組成) | n：兩個素數p和q的乘積 e：與(p-1)和(q-1)互質的數 |
| 私鑰KR (由d和n組成) | d和n |
| 加密方式 |  |
| 解密方式 | |
三，例子描述
（1）求得公鑰和私鑰
令p=3，q=11，則 n=p*q = 3x11 = 33，φ(n)=(p-1)(q-1)=20；再取 e =3( 3與20互質)，接下來要求d：
d為e的模反元素，模反元素即是指有一個整數d，可以使得ed被φ(n)除的餘數為1，寫成數學式子是：
又e=3，φ(n)=20是以：
又因為1模上任何數都是1，是以上式又表示為 3d%20 = 1，這個式子正規的話要使用擴充歐幾裡得算法求解，但基于數字比較小，我們可以看出來，當d = 7時，21%20 = 1成立，是以取 d = 7
n，e，d出來後，公鑰和私鑰就出來了：
公鑰KU = (e，n)=（3，33）
私鑰KR = （d，n）=（7，33）
（2）英文轉數字
将明文的英文資訊數字化，就需要一個編碼表，假設我們的編碼表a~z對應數字01~26：
| 字母 | a | b | c | d | e | f | g | h | i | j | k | l | m |
| 碼值 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 |
| 字母 | n | o | p | q | r | s | t | u | v | w | x | y | z |
| 碼值 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
假設我們要編碼的明文為 hi，則将hi轉化為編碼則是： 08，09
（3）明文加密
加密方式為：
，代入 e =3，n=33，得：
，代入明文08，09：
，由于512%33 = 17，是以 c1%33也要等于17，是以取c1=17
，由于729%33= 3，是以c2%33也要等于3，是以取c2=3
是以hi加密後的密文為：17，3
（4）密文解密
解密方式為：
（n是公開的，是以d絕對不能洩露，d洩露了，就等于私鑰洩露了），代入d=7，n=33，
得：
，代入密文17，3：
，由于410338673%33=8，是以m1%33也要等于8，是以取m1為8
，由于2187%33=9，是以m2%33也要等于9，是以取m2為9
是以解密後的明文為 8，9，對應編碼表，則為 hi。
（5）破解RSA
由于公鑰是公開的，若要破解RSA則要破解私鑰，由于私鑰KR為(d，n)，n是公鑰組成部分，是以n也是公開的，是以問題等價于破解d即可。
由
，e是公鑰裡的，是以e也是公開的，是以要求d就要知道φ(n)
由于：φ(n) = (p-1)(q-1)，是以，問題又等價于要求p和q，根據已有的資訊，n=p*q，是以從n入手，把 n 作因數分解就行了，
因數分解的意思是，例如45，可以分解為45=3x3x5，這樣的分解結果是獨一無二的，這也是p和q必須是質數的原因，因為當p和q都是質數，則 n = pxq 是獨一無二的，p和q越大，則n越難被分解。
當n=629這樣小的數時，通過程式可進行窮舉式的暴力破解：
num = 629
for p in range(num):
for q in range(num):
if p*q==num:
print('p=%d,q=%d' %(p,q))
但當n很大時，程式運作時間就會很長，是以一般p和q都是非常大的質數。
當p，q求出來後，d就可以算出來了，這樣私鑰也就出來了