第五章公钥密钥

❖这是因为通过共享秘密的方式只能在小范围内 实现认证，因为你不可能同时和很多人共享秘 密，而且与你共享秘密的人必须在以前有过某 种意义上的接触，否则你们怎么能够共享秘密 呢？
口令机制和数字证书的比较
❖ 而通过数字证书则能够实现证书持有者得到在大范围的 身份认证，而且不要求他曾经和认证方有过接触，只要 某人持有数字证书，就能够让所有以前与他从未有过接 触的实体认证他，这就像我们持有身份证可以在全国范 围内得到身份认证一样。
照片 签章
数字证书项目 主体名 序列号 相同 相同 发证机构 公钥 数字签名
如何建立主体与其公钥的关联的？
❖数字证书，是一个由使用数字证书的用户群所 公认和信任的权威机构（CA）签署了其数字签 名的信息集合。
❖主体将其身份信息和公钥以安全的方式提交给 CA认证中心，CA用自己的私钥对主体的公钥和 身份ID的混合体进行签名，将签名信息附在公 钥和身份ID等信息后，这样就生成了一张证书， 它主要由公钥、身份ID和CA的签名三部分组成，
数字证书
❖数字证书的概念: Kohnfelder于1978年提出的 ❖所谓数字证书，就是公钥证书，是一个包含有
用户身份信息、用户公钥以及一个可信第三方 认证机构CA的数字签名的数据文件 ❖提示：数字证书其实就是一个小的计算机文件
tang.cer
数字证书的直观概念
数字证书
我以官方名义正式 批准该证书持有者 （用户）与他的这 个公钥之间存在关 联。
有效期
主体的X.500名称
主体的 公钥信息
算法标识符 公钥值
认证机构的数字签名
认证机构的私钥 散列 生成数字签名
X.500目录系统简介
❖ 一个X.500目录由一系列目录项组成。每个目录项对应 一个现实世界中的对象。X.500每个对象都有一个无二 义性的名称，称为区别名（distinguished name, DN）。

下面我们首先计算
γ
2,0
=α
0×(p-1)/2
mod 29
= 20 mod 29 = 1, γ
2,1
=α
1×(p-1)/2mod
29
= 228/2 mod 29
= 28. 因为 = 28 =γ
2,1 ,
0
ß mod 29 = 1828/2 mod 29
所以 a = 1.令
ß = ß α 1 因为
0, 1 e i 1
i

根据目前的计算能力，只有当p-1 的素因子是小素数时，才 能有效分解 p-1求得 。因此，Pohlig-Hellman 算法适用于p1 的素因子是小素数的情况。 例5.8 设p = 29, 则 p-1= 28 = 22×7.设α = 2, ß 18. = 求log 。令log a .
s ( p 1 ) qi
mod p
qi ,s
· ,k, · ·
s = 0, 1,2, ·· i －1. 将这些 q ·
ei i
排成一个
下面利用表L求 a mod q
a mod q
ei i
, i= 1,2,
1 i
· ,k. · ·
e i 1
设
q
ei 1 i
a a q a
0
ß=αd mod p,
所以
k c2(c1d)–1≡mß (α
dk
)
–1
(mod p)
–1(mod
≡mα
dk
(α
dk
)
p) α ∈zp*
≡m(mod p). 因此，解密变换能正确的从密文恢复相应的明文。
5.4.2. ElGamal公钥密码体制的安全性

DES算法的迭代过程为：密钥与初始置换后的右半部分相结合，然后再与左半部 分相结合，其结果作为新的右半部分。结合前的右半部分作为新的左半部分。这 样一些步骤组成一轮。这种过程要重复16次。在最后一次迭代之后，所得的左右 两部分不再交换，这样可以使加密和解密使用同一算法。如图所示：
5.3 常用加密技术介绍
5.3 常用加密技术介绍
5.3 常用加密技术介绍
IDEA密码系统在加密和解密运算中，仅仅使用作用于16比特子块对的 一些基本运算，因此效率很高。IDEA密码系统具有规则的模块化结构， 有利于加快其硬件实现速度。由于IDEA的加密和解密过程是相似的，所 以有可能采用同一种硬件器件来实现加密和解密。
5.3 常用加密技术介绍
从上述要求可以看出，公开密钥密码体制下，加密密钥不等于解密密钥。加密 密钥可对外公开，使任何用户都可将传送给此用户的信息用公开密钥加密发送， 而该用户唯一保存的私有密钥是保密的，也只有它能将密文恢复为明文。虽然解 密密钥理论上可由加密密钥推算出来，但实际上在这种密码体系中是不可能的， 或者虽然能够推算出，但要花费很长的时间而成为不可行的，所以将加密密钥公 开也不会危害密钥的安全。
5.3.2 IDEA算法
国 际 数 据 加 密 算 法 IDEA（International Data Encryption Algorithm）是瑞士的著名学者提出的。IDEA是在DES算法的基础 上发展起来的一种安全高效的分组密码系统。
IDEA密码系统的明文和密文长度均为64比特，密钥长度则 为128比特。其加密由8轮类似的运算和输出变换组成，主要有异 或、模加和模乘三种运算。其加密概况如图所示：
在上例中，因为质数选择得很小，所以P必须小于33，因此，每个明文块只能包 含一个字符。结果形成了一个普通的单字母表替换密码。但它与DES还是有很大区 别的，如果p，q的选择为10100 ，就可得到n= 10200 ，这样，每个明文块就可多达 664比特，而DES只有64比特。

5.3 基于离散对数的公钥密码体制
5.3.2 离散对数Diffie-Hellman算法 设p是一个满足要求的大素数，0 < α < p, α是循环群Z p的生成元，α和p公开，它 们也将在一组用户中共用。 在两个用户Alice与Bob要通信时，他们可 通过下面的步骤协商通信时所使用的密钥：
5.3 基于离散对数的公钥密码体制
while r > 0
5.2 RSA 公钥密码体制
if b0 ≠ 1 then b 没有模a的逆 else return(t)
5.2 RSA 公钥密码体制
中国剩余定理及欧拉定理 定理 5.2.2(中国剩余定理)假设m1 ,…, mr是 两两互素的正整数，a1 ,…, ar为整数。那么 同余方程组 x ≡ ai ( mod mi ) (1≤ i ≤ m) 有模M = m1 m2 … , m 的唯一解，具体解表 r r 达式为 x = ∑ a i M i y i mod M i =1 −1 M 其中 M i = ，且 yi = Mi modmi ,1 ≤ i ≤ r。 mi
5.2 RSA 公钥密码体制
算法5.2.3 Multiplication Inverse(a , b)
a0 ← a b0 ← b t0 ← 0
t←1
5.2 RSA 公钥密码体制
⎧ temp ← ( t 0 − qt ⎪ ← t t 0 ⎪ ⎪ t ← temp ⎪ ⎪ a 0 ← b0 do ⎨ b0 ← r ⎪ ⎪ ⎢ a0 ⎥ ⎪ q← ⎢ ⎥ ⎪ ⎣ b0 ⎦ ⎪ ⎩ r ← a 0 − qb 0
5.2 RSA 公钥密码体制
算法5.2.1 Euclidean Algorithm(a ,b) r0 ←a ⎧ ⎢ rm − 1 ⎥ qm ← ⎢ r1 ←b ⎪ ⎥ rm ⎦ ⎣ ⎪ m ←1 ⎪ while rm ≠ 0 do ⎨ rm + 1 ← rm −1 − q m rm m ←m - 1 ⎪ m ← m +1 ⎪ return ( q1,…, qm, rm ) ⎪(a,b) Comment ： rm = gcd ⎩