公钥密码体制

• 每个用户生成一个**对，公钥pk，私钥sk
• 公钥在系统被公开
• 私钥由本人安全保管
• 公钥由系统中其他用户使用，私钥本人私用
• 公钥密码体制也称非对称密码体制
• 公钥密码体制主要用于**分发

公钥密码体制优势

**分发：公钥采用公开信道传输
**管理：在N个用户的系统中，每个用户只需要保管自己的私钥以及其他N-1个用户的公钥，整个系统只需要维护N个公钥

密码学数学基础之数论

Fermat定理

若p是素数，a是正整数且gcd（a,p)=1,则a^p-1$\equiv$≡ 1modp即a^p$\equiv$≡ amodp

Euler定理

小于n且与n互素的正整数个数称为n的欧拉函数$\varphi$φ(n)
若n为素数，$\varphi$φ(n）=n-1
若n等于两个素数乘积，$n=p\times$n=p×q，$\varphi(n)=\varphi(p)\varphi(q),\varphi=(p-1)(q-1)$φ(n)=φ(p)φ(q),φ=(p−1)(q−1)
欧拉定理：若a,n互素，$a^\varphi$aφ⁽ⁿ⁾$\equiv$≡ 1modn,注：当n为素数，$\varphi(n)=n-1$φ(n)=n−1,欧拉定理也是费马定理,即费马定理是欧拉定理的特例.

欧几里得除法Euclid

a,b两个正整数,b>0,存在唯一整数q,r使得a=bq+r,0$\leq$≤r<b
gcd(a,b)=r_n，sa+tb=r_n
若a,b互素，sa+tb=1，b在模a下有乘法逆元，bx$\equiv$≡ 1moda,x<a.

中国剩余定理

离散对数

p是素数，a为p的本原根
a¹、a²、…、a^p-1在modp下等到1到p-1的所有值
b$\in$∈{1，2，…,p-1},有唯一的i$\in$∈{1，2，…,p-1},使得b$\equiv$≡ aⁱmodp
i$\equiv$≡ log_ab(modp)

平方剩余

gcd(a,n)=1
x²$\equiv$≡a mod n
称a为modn的二次剩余
欧拉判别法则
p为奇素数，若a为modn的二次剩余
a^(p-1)/2=1 mod p
若a不是modn的二次剩余
a^(p-1)/2=-1 mod p

RSA

**生成

加密解密

RSA算法中计算问题

(a x b)mod n=[(amodn)(bmodn)]防止内存单元溢出
平方乘算法、快速指数算法。提高加密解密指数运算的有效性

RSA安全性

共模攻击


RSA为确定性加密，不是概率性加密。

ElGamal

ElGamal公钥加密体制原理

ElGamal公钥加密举例

ElGamal与RSA区别

Rabin

Rabin密码体制总结