Xø(N) = 1 mod N
for all x not divisible by p or q, ie gcd(x,ø(N))=1
where ø(N)=(p-1)(q-1) 但在 RSA 中，e & d 是特殊选择的 ie e.d=1 mod ø(N) 或e.d=1+Rø(N)
hence have: M = Cd = Me.d = M1+Rø(N) = M1.(Mø(N))R = M1.(1)R = M1 mod N
12。El Gamal 公钥加密方案
Diffie-Hellman key distribution scheme 的变形 能够用于安全交换密钥 published in 1985 by ElGamal:
T. ElGamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", IEEE Trans. Information Theory, vol IT-31(4), pp469-472, July 1985.
推论9.2.19.2.5：雅可比符号（Jacobi symbol）,记作J(a,n),是勒让德符号的一 般化表示，它定义在任意正整数a和奇整 数n上。设n的素数因子分解式为 pe1……pek,则
J(a，n)=L(a，p1)e1 …L(a，p)ek
15701019（mod 3337)=688
9。RSA 安全性
RSA 安全性基于计算 ø(N)的困难性 要求分解模N
10. RSA的实现问题
需要计算模 300 digits (or 1024+ bits) 的乘法
计算机不能直接处理这么大的数 （计算速度很慢）
需要考虑其它技术，加速RSA的实现
Bob 恢复明文 M = 31.22 = 3 mod 97
9.3.1离散对数问题算法
1. 计算 mi modp,i [0,m-1]，按第二个坐标排序 m 个有序对（i, mi modp），
得到表 T 1 .
2. 计 算 j modp,j [0,m-1] ， 按 第 二 个 坐 标 排 序 m 个 有 序 对 （ j, j modp），得到表 T 2 .
public-key/two-key/asymmetric 包 括两个密钥:
公开密钥(a public-key), 可以被任何人知 道, 用于加密或验证签名
私钥( private-key), 只能被消息的接收者 或签名者知道,用于解密或签名
加密或验证签名者不能解密或多或生成签 名.
是密码学几千年历史中最有意义的结果
钥密码 exhaustive search 但实际上,密钥足够长 (>512bits) 一般情况下,有一些已知的困难问题(hard
problem” 要求足够大的密钥长度 (>512 bits) 导致加密速度比对称算法慢
2. RSA (Rivest, Shamir, Adleman)
使用最广泛的公钥加密算法 Rivest, Shamir & Adleman (RSA) in
定义9.2.4：设p是一奇素数，对任何a≧0,我们定义勒让 德符号（Legendre symbol）L(a,p)为 0 如果a ≡ 0(modp) L(a,p)= 1 如果a是模p的二次剩余 -1 如果a是p的非二次剩余
定理9.2.1（欧拉准则）：设p是素数，那么x是模p的 二次剩余当且仅当 x(P-1)/2 ≡ 1(modp)
15. El Gamal 解密
首先计算 message key K K = C1xB mod p = ak.xB mod p 计算明文: M = C2.K-1 mod p
16. El Gamal Example
选择 p=97 及本原根 a=5 recipient Bob 选择 秘密钥xB=58 & 计算并发布公钥
解方程 M = M1 mod p
M = M2 mod q
具有唯一解（利用CRT ）：
:M = [((M2 +q - M1)u mod q] p + M1 其中 p.u mod q = 1
9.2.3概率素性检测
定义9.2.3：如果P是素数，且a小于p,如果至少存在一 个x∈ [1，p-1]满足x2≡a(modp)，则我们称a是模p的 二次剩余（quadratic residue）。
3. RSA Setup
每个用户生成自己的公钥\私钥对: 选择两个随机大素数 (~100 digit), p, q 计算模数 N=p.q 选择一个随机加密密钥匙 e : e<N,
gcd(e,ø(N))=1 解下列同余方程,求解密密钥 d:
e.d=1 mod ø(N) and 0<=d<=N 公开加密密钥: Kr={er,Nr} 保存其解密似钥: K-1r={d,p,q}
对一个奇整数n的Solovay-strassen素性测试
1. 选择一随机整数a，满足a∈ [1,n-1]
2.如果J(a,n)=a(n-1)/2modn
则
回答“n是素数”
否则
回答“n是合数”
7.Diffie-Hellman 密钥分配方案
公钥密码问世 Diffie & Hellman in 1976: 密钥交换的实际方法 公钥方案概念的提出
第九章 公钥密码学
对称密码体制的缺陷：
1 ） 密 钥 分 配 问 题 通 信 双 方 要 进 行 加 密 通 信 ，需 要 通 过 秘 密 的 安 全 信 道 协 商 加 密 密 钥 ，而 这 种 安 全 信 道 可 能 很 难 实 现 ；
2 ） 密 钥 管 理 问 题 在 有 多 个 用 户 的 网 络 中 ，任 何 两 个 用 户 之 间都需要有共享的秘密钥，当网络中的用户 n 很大时，需 要 管 理 的 密 钥 数 目 是 非 常 大 n(n 1) / 2 。
3. 从 T 1 、 T 2 中 分 别 各 自 寻 找 一 对 （ i,y ） T 1 和 （ j,y ） T 2 定 义
log =mi+jmod(p-1)
Shanks算法
1． 计算 j = ( p1) j q1 modp, j [0,q-1]. 2． i, i 的初始值为 i 0 和 i
yB=558=44 mod 97 Alice 要加密 M=3 to Bob 首先得到 Bob的公开密钥 yB=44 选择随机 k=36 计算:
K=4436=75 mod 97
计算密文对:
C1 = 536 = 50 mod 97 C2 = 75.3 mod 97 = 31 mod 97 发送 {50,31} to Bob Bob 恢复 message key K=5058=75 mod 97 Bob 计算 K-1 = 22 mod 97
安全性是基于离散对数 缺点：增加了消息长度（2倍）
13 密钥建立
密钥生成： 选取一个大素数p及本原元a mod p 接收者 Bob有一个密秘钥 xB 计算 yB = axB mod p
14. El Gamal 加密
为加密 M 发送者选择随机数k, 0<=k<=p-1 计算消息密钥 K : K = yBk mod p 计算密文对: C = {C1,C2} C1 = ak mod p C2 = K.M mod p 发送到接收者 k 需要永久保密
用于加密任何消息 任何人可以用公钥加密消息 私钥的拥有者可以解密消息 任何公钥加密方案能够用于密钥分配方案PKDS 许多公钥加密方案也是数字签名方案
Signature Schemes
用于生成对某消息的数字签名 私钥的拥有者生成数字签名 任何人可以用公钥验证签名
6.公钥的安全性
依赖于足够大大的困难性差别 类似与对称算法,穷搜索在理论上是能够破解公
11. RSA – 的快速实现
加密很快，指数小
解密比较慢，指数较大
利用中国剩余定理CRT，
CRT 对RSA解密算法生成两个解密方程 （利用M = Cd mod R ）
即: M1 = M mod p = (C mod p)d mod (p-1)
M2 = M mod q = (C mod q)d mod (q-1)
8。RSA举例
例子：
1. 选素数p=47和q＝71，得n=3337, (n)=46×70＝3220； 2. 选择e=79，求得私钥d=e -1 1019(mod
3220）。 3. 公开n=3337和e=79. 4. 现要发送明文688，计算： 68879(mod 3337)=1570 5.收到密文1570后，用私钥d＝1019进行解密：
计算: C=Mer mod Nr, where 0<=M<N 为解密 C， 接收者使用私钥 K-1r={d,p,q} 计算: M=Cd mod Nr
6. RSA理论
RSA 基于Fermat's Theorem: if N = pq where p, q are primes, then:
3.公钥加密方案
4.公钥密码理论
由私钥及其他密码信息容易计算出公开密钥 (a polynomial time (P-time) problem)
由公钥及算法描述,计算私钥是难的 (an NPtime problem)
因此,公钥可以发布给其他人(wishing to communicate securely with its owner )
While i c-1 do 计算 = i ( p1)q( j1) modp, 找一个 j 满足 = j , a i j, i1 i , aiqi i i+1.
W Diffie, M E Hellman, "New directions in Cryptography", IEEE Trans. Information Theory, IT-22, pp644-654, Nov 1976