密碼學的平方乘演算法

⑴ 平方乘演算法的正確性

底數不變，指數相乘。
平方乘演算法是快速冪的其中一種，冪的乘方，底數不變，指數相乘。
平方是一種運算，比如a的平方表示a×a簡寫成a2。

⑵ 平方怎麼計算

平方的計算方法如下：

1、如果是個位的數字，計算時直接將個位的數字本身相乘即可。

2、如果是兩位數(大於兩位數方法相同)，可以將這個數拆分成兩個個位數，然後將兩個個位數各自相乘後，再將其相乘即可得出結果。例如12的平方：12*12=3*4*3*4=3*3*4*4=9*16=144。

3、如果數字為十的倍數，即可拆分成十乘以後的數字，然後將這個數字本身相乘，再乘以一百即可得出數據，例如:20的平方，可拆分為20*20=2*2*100=400。

(2)密碼學的平方乘演算法擴展閱讀：

a的平方表示a×a，簡寫成a，也可寫成a×a(a的一次方乘a的一次方等於a的2次方），例如4×4=16，8×8=64，平方符號為2。

邊長的平方（即邊長×邊長）=正方形的面積。平方又叫二次方，平方的逆運算就是開平方,也叫做求平方根，平方根寫作：±√。

一個數的平方具有非負性。即a²≥0.應用：若a²+b²=0,則有a=0且b=0。

⑶ RSA演算法中11^7mod(15)怎麼算

平方－乘演算法，計算形如x^c(mod n)
c的二進製表示為c=c0*2^0+c1*2^1+..+ci*2^i+..+cL*2^L
其中c的二進製表示位數為L+1,
平方－乘演算法 square-multiple(x,c,n)
z <- 1
for i <- L downto 0
do
z <- z^2 mod n
if ci = 1
then z <- (z*x)mod n
return (z)
平方-乘演算法可以把計算x^c mod n 所需模乘次數降低為最多2L次。
計算11^7mod(15)
7 = 1*2^0 + 1*2^1 + 1*2^2

i bi z
2 1 1^2 * 11 mod 15 =11
1 1 11^2 * 11 mod 15 = 11
0 1 ... = 11
其中bi為c的二進製表示的的各二進制位上的值

⑷ 密碼學里的加密演算法：e=13,x=5,n=77.請問：c=x^e mod n=26mod77, 得

5的13次方（13個5相乘） 等於1220703125，1220703125 mod 77 相當於 1220703125除77 所得的余數就為26，所以c=26

⑸ 密碼學基礎1：RSA演算法原理全面解析

本節內容中可能用到的符號說明如下：

質數和合數： 質數是指除了平凡約數1和自身之外，沒有其他約數的大於1的正整數。大於1的正整數中不是素數的則為合數。如 7、11 是質數，而 4、9 是合數。在 RSA 演算法中主要用到了質數相關性質，質數可能是上帝留給人類的一把鑰匙，許多數學定理和猜想都跟質數有關。

[定理1] 除法定理： 對任意整數 a 和 任意正整數 n，存在唯一的整數 q 和 r，滿足 。其中， 稱為除法的商，而 稱為除法的余數。

整除： 在除法定理中，當余數 時，表示 a 能被 n 整除，或者說 a 是 n 的倍數，用符號 表示。

約數和倍數 ： 對於整數 d 和 a，如果 ，且 ，則我們說 d 是 a 的約數，a 是 d 的倍數。

公約數： 對於整數 d，a，b，如果 d 是 a 的約數且 d 也是 b 的約數，則 d 是 a 和 b 的公約數。如 30 的約數有 1，2，3，5，6，10，15，30，而 24 的約數有 1，2，3，4，6，8，12，24，則 30 和 24 的公約數有 1，2，3，6。其中 1 是任意兩個整數的公約數。

公約數的性質：

最大公約數： 兩個整數最大的公約數稱為最大公約數，用 來表示，如 30 和 24 的最大公約數是 6。 有一些顯而易見的性質：

[定理2] 最大公約數定理： 如果 a 和 b 是不為0的整數，則 是 a 和 b 的線性組合集合 中的最小正元素。

由定理2可以得到一個推論：

[推論1] 對任意整數 a 和 b，如果 且 ，則 。

互質數： 如果兩個整數 a 和 b 只有公因數 1，即 ，則我們就稱這兩個數是互質數(coprime）。比如 4 和 9 是互質數，但是 15 和 25 不是互質數。

互質數的性質：

歐幾里得演算法分為樸素歐幾里得演算法和擴展歐幾里得演算法，樸素法用於求兩個數的最大公約數，而擴展的歐幾里得演算法則有更多廣泛應用，如後面要提到的求一個數對特定模數的模逆元素等。

求兩個非負整數的最大公約數最有名的是 輾轉相除法，最早出現在偉大的數學家歐幾里得在他的經典巨作《幾何原本》中。輾轉相除法演算法求兩個非負整數的最大公約數描述如下：

例如， ，在求解過程中，較大的數縮小，持續進行同樣的計算可以不斷縮小這兩個數直至其中一個變成零。

歐幾里得演算法的python實現如下：

擴展歐幾里得演算法在 RSA 演算法中求模反元素有很重要的應用，定義如下：

定義： 對於不全為 0 的非負整數 ，則必然存在整數對 ，使得

例如，a 為 3，b 為 8，則 。那麼，必然存在整數對 ，滿足 。簡單計算可以得到 滿足要求。

擴展歐幾里得演算法的python實現如下：

同餘： 對於正整數 n 和 整數 a，b，如果滿足 ，即 a-b 是 n 的倍數，則我們稱 a 和 b 對模 n 同餘，記號如下： 例如，因為 ，於是有 。
對於正整數 n，整數 ，如果 則我們可以得到如下性質：

譬如，因為 ，則可以推出 。

另外，若 p 和 q 互質，且 ，則可推出：

此外，模的四則運算還有如下一些性質，證明也比較簡單，略去。

模逆元素： 對整數 a 和正整數 n，a 對模數 n 的模逆元素是指滿足以下條件的整數 b。 a 對 模數 n 的 模逆元素不一定存在，a 對 模數 n 的模逆元素存在的充分必要條件是 a 和 n 互質，這個在後面我們會有證明。若模逆元素存在，也不是唯一的。例如 a=3，n=4，則 a 對模數 n 的模逆元素為 7 + 4k，即 7，11，15，...都是整數 3 對模數 4 的模逆元素。如果 a 和 n 不互質，如 a = 2，n = 4，則不存在模逆元素。

[推論2] 模逆元素存在的充分必要條件是整數 a 和 模數 n 互質。

[定理3] 唯一質數分解定理： 任何一個大於1的正整數 n 都可以 唯一分解 為一組質數的乘積，其中 都是自然數(包括0)。比如 6000 可以唯一分解為 。

由質數唯一分解定理可以得到一個推論： 質數有無窮多個 。

[定理4] 中國剩餘定理(Chinese remainder theorem，CRT) ，最早見於《孫子算經》(中國南北朝數學著作，公元420-589年)，叫物不知數問題，也叫韓信點兵問題。

翻譯過來就是已知一個一元線性同餘方程組求 x 的解：

宋朝著名數學家秦九韶在他的著作中給出了物不知數問題的解法，明朝的數學家程大位甚至編了一個《孫子歌訣》：

意思就是：將除以 3 的余數 2 乘以 70，將除以 5 的余數 3 乘以 21，將除以 7 的余數 2 乘以 15，最終將這三個數相加得到 。再將 233 除以 3，5，7 的最小公倍數 105 得到的余數 ，即為符合要求的最小正整數，實際上， 都符合要求。

物不知數問題解法本質

求解通項公式

中國剩餘定理相當於給出了以下的一元線性同餘方程組的有解的判定條件，並用構造法給出了解的具體形式。

模數 兩兩互質 ，則對任意的整數： ，方程組 有解，且解可以由如下構造方法得到：

並設 是除 以外的其他 個模數的乘積。

中國剩餘定理通項公式證明

⑹ 如何進行冪模運算

模冪乘運算採用平方乘演算法，將模冪乘運算轉化為模乘和模平方運算實現．
平方-乘演算法：一般地，求S=ABmodN，其中A<N，B<N；將指數B表示為二進制，即
觀察演算法，由於指數B化為二進制後的長度不確定，多數情況下高位會存在很多個0．如果完全按照該演算法實現，指數B從最高位起開始運算，在第一個1出現以前，雖進行了多次運算，但D的值一直為1；當B出現第一個1後才進入有效的模乘運算．在具體實現時，設計專門的電路從高到低掃描指數B的每一位，當在找到第一個1之前，不做任何運算，找到第一個1時，使D=A，以後根據每次掃描的6[i]值，調用模乘實現運算．
經過對多種公鑰加解密演算法的分析——如RSA演算法，通常公鑰的有效位較短，而私鑰有效位較長．加密中的模冪乘運算，指數有效位很少，所以上面的改進可大大減少模乘次數，加快加密過程．以目前常用的私鑰和模數1 024 bit，公鑰128bit情況為例，採用上述改進可減少896次不必要的模乘．解密過程使用中國余數定理(CRT)，可有效降低解密指數的長度，整個演算法的執行效率得到進一步提高．
2．2 模乘及模加的實現方法
模乘採用改進的Blakley加法型演算法，原理與平方-乘演算法類似，核心是將模乘轉化為模加實現．如通常S=(A×B)modN，A<N，B<N可以按如下方式考慮．
將B表示成二進制：
由上式可知，可以像平方一乘演算法一樣，將模乘轉化為模加實現．
一般模加運算表示為S=(A+B)modN，觀察以上模乘及模冪乘演算法原理描述，可知在其調用的模加運算中，因為A<N且B<N，則(A+B)<2N，所以，
因此考慮在運算中同時計算(A+B)和(A+B-N)兩個結果，運算完成後通過判斷加法器與減法器的進位輸出(CO)與借位輸出(BO)．決定哪個為本次模加的正確結果．同上，A，B，N均為l位的二進制數，若CO=1，則說明(A+B)為l+1位二進制數，必大於l位的N；若CO=0，則(A+B)和N同為l位，當BO=1時(A+B)<N，當BO=0時N≤(A+B)．
從而可以在一次運算中完成加法和求模過程，使模加的運算速度提高1倍．

⑺ 現在密碼學採用的演算法主要有什麼

現代密碼學將演算法分為具有不同功能的幾種
常用的主要有三種：
1.對稱密碼演算法
DES演算法——二十世紀七十年代提出，曾經稱霸對稱加密領域30年
AES演算法——二十一世紀初提出用以取代DES演算法
IDEA演算法——二十世紀九十年代初提出，也是一種流行演算法
RC4演算法——經典的流密碼演算法
2.公鑰密碼演算法
D-H演算法——用於密鑰協商，是第一種使用的公鑰演算法，基於離散對數難解問題
RSA演算法——最常用的公鑰演算法，功能強大
3.哈希函數(雜湊函數)
MD5——常用演算法，用於產生80比特的輸出
SHA-1——也是常用演算法，用於產生128比特輸出
---
這是最經典的若干種演算法
說的不對之處請指正

------
個人意見 僅供參考

⑻ 平方乘演算法是怎樣的

m^2 * n^2 = (m*n)^2;

比如：
3^2 * 4^2
=(3*4)^2
=12^2

⑼ 想聽大家對於一道密碼設計的數學建模題

公鑰密碼又稱為雙鑰密碼和非對稱密碼，是1976年由Daffy和Hellman在其「密碼學新方向」一文中提出的，見劃時代的文獻：
W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654
單向陷門函數是滿足下列條件的函數f：
(1)給定x，計算y=f(x)是容易的；
(2)給定y, 計算x使y=f(x)是困難的。
(所謂計算x=f-1(Y)困難是指計算上相當復雜，已無實際意義。)
(3)存在δ，已知δ 時,對給定的任何y，若相應的x存在，則計算x使y=f(x)是容易的。
註：1*. 僅滿足(1)、(2)兩條的稱為單向函數；第(3)條稱為陷門性，δ 稱為陷門信息。
2*. 當用陷門函數f作為加密函數時，可將f公開，這相當於公開加密密鑰。此時加密密鑰便稱為公開鑰，記為Pk。 f函數的設計者將δ 保密，用作解密密鑰，此時δ 稱為秘密鑰匙，記為Sk。由於加密函數時公開的，任何人都可以將信息x加密成y=f(x)，然後送給函數的設計者（當然可以通過不安全信道傳送）；由於設計者擁有Sk，他自然可以解出x=f-1(y)。
3*.單向陷門函數的第(2)條性質表明竊聽者由截獲的密文y=f(x)推測x是不可行的。
Diffie和Hellman在其里程碑意義的文章中，雖然給出了密碼的思想，但是沒有給出真正意義上的公鑰密碼實例，也既沒能找出一個真正帶陷門的單向函數。然而，他們給出單向函數的實例，並且基於此提出Diffie-Hellman密鑰交換演算法。這個演算法是基於有限域中計算離散對數的困難性問題之上的：設F為有限域，g∈ F是F的乘法群F*=F\{0}=<g>。並且對任意正整數x，計算gx是容易的；但是已知g和y求x使y= gx，是計算上幾乎不可能的。這已問題稱為有限域F上的離散對數問題。公鑰密碼學種使用最廣泛的有限域為素域FP.
對Diffie-Hellman密鑰交換協議描述：Alice和Bob協商好一個大素數p，和大的整數g，1<g<p，g最好是FP中的本原元，即FP*＝<g>。p和g無須保密，可為網路上的所有用戶共享。
當Alice和Bob要進行保密通信時，他們可以按如下步驟來做：
(1)Alice送取大的隨機數x，並計算
X=gx(mod P)
(2)Bob選取大的隨機數x，並計算X  = gx (mod P)
(3)Alice將X傳送給Bob；Bob將X 傳送給Alice。
(4)Alice計算K=(X )X(mod P);Bob計算K  ＝（X) X (mod P),易見，K=K  =g xx (mod P)。
由(4)知，Alice和Bob已獲得了相同的秘密值K。雙方以K作為加解密鑰以傳統對稱密鑰演算法進行保密通信。
註：Diffie-Hellman密鑰交換演算法擁有美國和加拿大的專利。
3 RSA公鑰演算法
RSA公鑰演算法是由Rivest,Shamir和Adleman在1978年提出來的（見Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126)該演算法的數學基礎是初等數論中的Euler（歐拉)定理，並建立在大整數因子的困難性之上。
將Z/(n）表示為 Zn，其中n=pq; p,q為素數且相異。若
Z*n{g∈ Zn|(g,n)=1}，易見Z*n為  (n)階的乘法群，且有 g  (n)1(mod n)，而  (n)=(p-1)(q-1).
RSA密碼體制描述如下：
首先，明文空間P＝密文空間C=Zn.(見P175).
A.密鑰的生成
選擇p,q，p,q為互異素數，計算n=p*q,  (n)=(p-1)(q-1), 選擇整數e使( (n),e)=1,1<e< (n)),計算d,使d=e-1(mod  (n))),公鑰Pk={e,n};私鑰Sk={d,p,q}。
注意，當0<M<n時,M (n) =1(mod n)自然有：
MK (n)+1M(mod n), 而ed  1 (mod  (n)),易見(Me)d  M(mod n)
B.加密 (用e,n)明文：M<n 密文：C=Me(mod n).
C.解密 (用d,p,q)
密文：C 明文：M=Cd（mod n)
註：1*, 加密和解密時一對逆運算。
2*, 對於0<M<n時，若(M,n) ≠ 1，則M為p或q的整數倍，假設M=cp，由(cp,q)=1 有 M (q)  1(mod q) M  (q)  (p)  1(mod q)
有M (q) = 1+kq 對其兩邊同乘M=cp有
有M (q)＋1=M+kcpq=M+kcn於是
有M (q)＋1  M(mod n)
例子：若Bob選擇了p=101和q＝113，那麼，n=11413,  (n)=100×112＝11200；然而11200＝26×52×7，一個正整數e能用作加密指數，當且僅當e不能被2，5，7所整除（事實上，Bob不會分解φ(n)，而且用輾轉相除法（歐式演算法）來求得e，使（e, φ(n)=1)。假設Bob選擇了e=3533，那麼用輾轉相除法將求得：
d=e -1  6597(mod 11200), 於是Bob的解密密鑰d=6597.
Bob在一個目錄中公開n=11413和e=3533, 現假設Alice想發送明文9726給Bob，她計算：
97263533(mod 11413)=5761
且在一個信道上發送密文5761。當Bob接收到密文5761時，他用他的秘密解密指數（私鑰）d＝6597進行解密：57616597（mod 11413)=9726
註：RSA的安全性是基於加密函數ek(x)=xe(mod n)是一個單向函數，所以對的人來說求逆計算不可行。而Bob能解密的陷門是分解n=pq，知 (n)=(p-1)(q-1)。從而用歐氏演算法解出解密私鑰d.
4 RSA密碼體制的實現
實現的步驟如下：Bob為實現者
(1)Bob尋找出兩個大素數p和q
(2)Bob計算出n=pq和 (n)=(p-1)(q-1).
(3)Bob選擇一個隨機數e(0<e<  (n))，滿足（e，  (n)）＝1
(4)Bob使用輾轉相除法計算d=e-1(mod  (n))
(5)Bob在目錄中公開n和e作為她的公開鑰。
密碼分析者攻擊RSA體制的關鍵點在於如何分解n。若分
解成功使n=pq，則可以算出φ(n)＝（p-1)(q-1)，然後由公
開的e，解出秘密的d。（猜想：攻破RSA與分解n是多項式
等價的。然而，這個猜想至今沒有給出可信的證明！！！）
於是要求：若使RSA安全，p與q必為足夠大的素數，使
分析者沒有辦法在多項式時間內將n分解出來。建議選擇
p和q大約是100位的十進制素數。 模n的長度要求至少是
512比特。EDI攻擊標准使用的RSA演算法中規定n的長度為
512至1024比特位之間，但必須是128的倍數。國際數字
簽名標准ISO/IEC 9796中規定n的長度位512比特位。
為了抵抗現有的整數分解演算法，對RSA模n的素因子
p和q還有如下要求：
(1)|p-q|很大，通常 p和q的長度相同；
(2)p-1 和q-1分別含有大素因子p1和q1
(3)P1-1和q1-1分別含有大素因子p2和q2
(4)p+1和q+1分別含有大素因子p3和q3

為了提高加密速度，通常取e為特定的小整數，如EDI國際標准中規定 e＝216＋1，ISO/IEC9796中甚至允許取e＝3。這時加密速度一般比解密速度快10倍以上。 下面研究加解密算術運算，這個運算主要是模n的求冪運算。著名的「平方-和-乘法」方法將計算xc(mod n)的模乘法的數目縮小到至多為2l，這里的l是指數c的二進製表示比特數。若設n以二進制形式表示有k比特，即k=[log2n]+1。 由l≤ k，這樣xc(mod n)能在o(k3)時間內完成。（注意，不難看到，乘法能在o(k2)時間內完成。）

平方－和－乘法演算法：
指數c以二進制形式表示為：

c=
Xc=xc0×（x2)c1×…×(x2t-1)ct-1
預計算： x2=xx
x4=x22=x2x2
.
.
.
x2t-1 =x2t-2*x2t-2
Xc計算：把那些ci=1對應的x2i全部乘在一起，便得xc。至
多用了t-1次乘法。請參考書上的177頁，給出計算
xc(mod n)演算法程序：
A=xc c=c0+c12+..+ct-12t-1= [ct-1,....,c1,c0]2
5 RSA簽名方案

簽名的基本概念
傳統簽名（手寫簽名）的特徵：
（1）一個簽名是被簽文件的物理部分；
（2）驗證物理部分進行比較而達到確認的目的。(易偽造)
（3）不容易忠實地「」!!!
定義： (數字簽名方案）一個簽名方案是有簽署演算法與驗
證演算法兩部分構成。可由五元關系組（P,A,K,S,V）來刻化：
(1)P是由一切可能消息(messages)所構成的有限集合；
(2)A是一切可能的簽名的有限集合；
(3)k為有限密鑰空間，是一些可能密鑰的有限集合；
(4)任意k ∈K，有簽署演算法Sigk ∈ S且有對應的驗證演算法Verk∈V,對每一個
Sigk:p A 和Verk:P×A {真，假} 滿足條件：任意x∈ P,y∈ A.有簽名方案的一個簽名：Ver(x,y)= ｛
註：1*.任意k∈K, 函數Sigk和Verk都為多項式時間函數。
2*.Verk為公開的函數，而Sigk為秘密函數。
3*.如果壞人（如Oscar)要偽造Bob的對X的簽名，在計算上是不可能的。也即,給定x，僅有Bob能計算出簽名y使得Verk(x,y)＝真。
4*.一個簽名方案不能是無條件安全的，有足夠的時間，Oscar總能偽造Bob的簽名。
RSA簽名：n=pq,P=A=Zn,定義密鑰集合K={(n,e,p,q,d)}|n=pq,d*e1(mod (n))}
注意：n和e為公鑰；p,q,d為保密的（私鑰）。對x∈P, Bob要對x簽名，取k∈K。Sigk(x) xd(mod n)y(mod n)
於是
Verk(x,y)=真 xye(mod n)
（注意：e,n公開；可公開驗證簽名(x,y)對錯！！也即是否為Bob的簽署）
註：1*.任何一個人都可對某一個簽署y計算x=ek(y)，來偽造Bob對隨機消息x的簽名。
2*.簽名消息的加密傳遞問題：假設Alice想把簽了名的消息加密送給Bob，她按下述方式進行：對明文x，Alice計算對x的簽名，y=SigAlice(x)，然後用Bob的公開加密函數eBob,算出
Z=eBob(x,y) ,Alice 將Z傳給Bob，Bob收到Z後，第一步解密，
dBob(Z)=dBobeBob(x,y)=(x,y)
然後檢驗
VerAlice(x,y)= 真
問題：若Alice首先對消息x進行加密，然後再簽名，結果
如何呢？Y=SigAlice(eBob(x))
Alice 將（z,y)傳給Bob，Bob先將z解密，獲取x;然後用
VerAlice檢驗關於x的加密簽名y。這個方法的一個潛在問
題是，如果Oscar獲得了這對（z,y)，他能用自己的簽名來
替代Alice的簽名
y=SigOscar(eBob(x))
(注意：Oscar能簽名密文eBob(x)，甚至他不知明文x也能做。Oscar傳送（z,y )給Bob,Bob可能推斷明文x來自Oscar。所以，至今人么還是推薦先簽名後加密。）
6.EIGamal方案

EIGamal公鑰密碼體制是基於離散對數問題的。設P
至少是150位的十進制素數，p-1有大素因子。Zp為有限域，
若α為Zp中的本原元，有Zp* ＝<α>。若取β∈Zp*=Zp\{0}，
如何算得一個唯一得整數a,（要求，0≤a≤ p-2)，滿足
αa=β(mod p)
將a記為a=logαβ
一般來說，求解a在計算上是難處理的。
Zp*中的Egamal公鑰體制的描述：設明文空間為P=Zp*,密文空
間為C=Zp*×Zp*,定義密鑰空間K={(p, α,a, β )|β=αa(mod p)}
公開鑰為：p, α ,β
秘密鑰（私鑰）：a
Alice 取一個秘密隨機數k∈ Zp-1，對明文x加密
ek(x,k)=(y1,y2)
其中， y1=αk(mod p),y2=xβk(mod p)
Bob解密，
dk(y1,y2)=y2(y1α)-1(mod p)
註：1*.容易驗證y2(y1α)-1=x(αa)k(αka)-1=x !!
2*.利用EIGamal加密演算法可給出基於此的簽名方案：
Alice 要對明文x進行簽名，她首先取一個秘密隨機數k作
為簽名
Sigk(x,k)=( ,  )
其中 ＝αk(mod p), =(x-a )k-1(mod p-1)
對x, ∈Zp*和 ∈ Zp-1，定義Verk(x, ,)＝真等價於
βα＝αx(mod p)
要說明的是，如果正確地構造了這個簽名，那麼驗證將
是成功的，因為
βα＝ αa αk (mod p)= αa+k (mod p)
由上面知道， ＝（x- a)k-1(mod p-1)可以推出
k=x- a(mod p-1)有a+kx(mod p)
所以 β  ＝ αx (mod p)
該簽名方案已經被美國NIST(國家標准技術研究所）確定為簽名標准（1985）。

有關RSA方面的內容，請訪問網址：
www.RSAsecurity.com

⑽ 密碼學 RSA演算法

明文，密文，密鑰

明文，密文，公鑰，私鑰

（n，e1）（n，e2）就是密鑰對。其中（n，e1）為公鑰，（n，e2）為私鑰。

1、找到兩個質數p，q
2、n=p q 歐拉函數：φ(N) =(p-1) (q-1)
3、選擇一個小於φ(N)隨機整數數e ：1<e<φ(N)的整數 e和φ(N)互質
4、計算出e與φ(N)的模反元素d:
所謂"模反元素"就是指有一個整數d，可以使得ed被φ(n)除的余數為1。
ed ≡ 1 (mod φ(n))
這個式子等價於
ed - 1 = kφ(n)
於是，找到模反元素d，實質上就是對下面這個二元一次方程求解。
ex + φ(n)y = 1
這個方程可以用 "擴展歐幾里得演算法" 求解，
5、將n和e封裝成公鑰，n和d封裝成私鑰。
私鑰d：e*d/F(n)余數為1
6、加密： 加密要用公鑰 (n,e) me ≡ c (mod n) 即m^e/n余數為c
7、解密：解密要用私鑰(n,d) cd ≡ m (mod n) 即 c^d/n的余數為m

1、取p=103，q=349
2、計算n=p q=103 349=35947
3、計算歐拉函數φ(N) =(p-1) (q-1)=35496
4、取隨機整數 e小於φ(N)且互質e=773
5、 e 關於 r的模反元素 e d(mod φ(n))=1 d=45
6、公鑰就是 (35496 ,773)，私鑰就是（35496 , 45）

傳播：n,e,c
解密：n,d,c
那麼，有無可能在已知n和e的情況下，推導出d？
（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n=pq。只有將n因數分解，才能算出p和q。
結論：如果n可以被因數分解，d就可以算出，也就意味著私鑰被破解。
可是，大整數的因數分解，是一件非常困難的事情。目前，除了暴力破解，還沒有發現別的有效方法。