生成公私鑰過程
- 隨機選擇兩個大的質數(shù)
p、q - 由質數(shù)
p和q相乘得到n架馋， - 由歐拉函數(shù)求出
φ(n)狞山， - 隨機選擇與
r互質的數(shù)e，通常選擇65537 - 最后求出
e關于模數(shù)r的模反元素d叉寂，
此時得到的{n萍启，e}為公鑰，{n，d}為私鑰勘纯。
數(shù)學知識
互質關系
-
定義
如果兩個正整數(shù)局服，除了1以外，沒有其他公因子驳遵，那么這兩個數(shù)就是互質關系淫奔。
歐拉函數(shù)
-
定義
任意給定正整數(shù)
n， 在小于等于n的正整數(shù)之中堤结，有多少個與n構成互質關系（比如唆迁，在1到8之中，有多少個數(shù)與8構成互質關系）竞穷？計算這個值的方法就叫做歐拉函數(shù)唐责，以φ(n)表示。 -
公式
- 如果
n = 1瘾带，φ(1) = 1鼠哥； - 如果
n為質數(shù)，φ(n) = n - 1看政； - 如果
n是a的k次冪朴恳， - 如果
m，n互質帽衙，則φ(mn) = φ(m) * φ(n)
- 如果
歐拉定理
-
定義
若兩個正整數(shù)
n和m互質菜皂，則：
即m的φ(n)次方 整除n的余數(shù)是1贞绵，其中φ(n)表示在小于n的正整數(shù)中與n互質的個數(shù)厉萝。
費馬小定理
-
定義
若
m是不能被質數(shù)p整除的數(shù)，則：
其實就是歐拉定理的特殊情況榨崩，由于p是質數(shù)谴垫，所以φ(p) = p-1。
模反元素
-
定義
如果兩個正整數(shù)
e和r互質母蛛，那么一定可以找到整數(shù)d翩剪，使得e * d - 1被r整除，那么d就是e對于模數(shù)r的模反元素彩郊。
推導
由于
前弯，所以
由于
，所以
由模反元素的定義知道
比較公式
與
當式1中的與
式2中的相等時秫逝，
式1就變形成：
將上面的式3進行拆分得到加解密的流程：
其中m為要加密的數(shù)據(jù)恕出，{n，e}為公鑰违帆，{n浙巫，d}為私鑰，c為加密后的數(shù)據(jù)。
