2010-5-14 计算机算法设计与分析 1
第十一章
公钥密码学基础
2010-5-14 计算机算法设计与分析 2
密码、加密与解密
? 密码是通信双方按约定的法则进行信息
特殊变换的一种重要保密手段。
? 依照法则变明文为密文，称为加密变换；
? 依照法则变密文为明文，称为解密变换。
? 早期密码学仅对文字或数码进行加、解
密变换。现代密码学还可以对语音、图
像、数据等都可实施加、解密变换。
2010-5-14 计算机算法设计与分析 3
密码体制
? 进行明密变换的法则，称为密码体制。
? 密码体制可以分为四种基本类型：
? 错乱：按照规定方式改变明文符号的位置；
? 代替：用一个或多个代替表来代替明文符号；
? 密本：用预先编定的字母或数字密码组来代替
明文中一定的词组单词等；
? 加乱：用有限元素组成的一串序列作为乱数，
按规定的算法，同明文序列相结合变成密文。
? 这四种体制，既可单独使用，也可混合使用。
2010-5-14 计算机算法设计与分析 4
密钥和公钥密码的思想
? 1976年美国斯坦福大学的 Diffle和
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
为密码系统分别设计一个加密密钥 kc和
一个解密密钥 kd。
把 kc公开，而把 kd保密，同时 kc的公开
不会影响 kd的安全。这样：
? 加密的过程为,c = Ekc(m)，
? 解密的过程为,m = Dkd(c)。
2010-5-14 计算机算法设计与分析 5
秘钥与公钥
? 密码学分为秘钥密码学和公钥密码学。
? 秘钥密码学在加密和解密所使用的密钥
是相同的，又称为对称密码学。
? 公钥密码学加密和解密所使用的密钥是
不相同的，且前者 (签字密钥 )公开而 后者
(验证密钥 )保密，又称为 非对称密码学。
2010-5-14 计算机算法设计与分析 6
公钥密码学的各种技术及功能
? 1、保密通信
? 2、数字签名
? 3、秘密共享
? 4、认证功能
2010-5-14 计算机算法设计与分析 7
单向函数
? 加密的过程和解密的过程分别为：
c = E (m)和 m = D(c)
? 显然 D是 E的逆函数，即 D = E–1。
? 设 f(x) 是 En上的一个变换,En={0,1,…,n –1}，
f(x)是单向的，若由 x计算 y = f(x)是容易的，即
P问题，而由 y计算出 x是困难的，即 NPC问题。
? 因此，公钥密码学的思想就是让加密函数是一
个单向函数。 加密容易解密难！
2010-5-14 计算机算法设计与分析 8
单向陷门函数
? 加密容易解密难。要难住别人，却不要难住自
己。怎么办？
? f(x) 说是单向陷门函数，如果有陷门信息 K，
当 K未知时,f(x)是单向的，当 K已知时，由 y
计算出 x是容易的。
? 公约密码学的思想就是将加密函数设计为一个
单向陷门函数，而把陷门信息 K作为解密密码。
? 解密密码 K是保密的。有了解密密码，就很容
易解密，而不知道解密密码，就很难解密。
2010-5-14 计算机算法设计与分析 9
单向陷门函数
? 例如：取两个不相等的质数 p和 q,令 n = pq，
取函数 f(x) = xk mod n,且 (k,ф(n))=1,其中 ф(n)
是 n的欧拉函数 (即 ф(n)=(p – 1)*(q – 1)),则 f(x)
是一个单向函数。
? 如果有 d使得 kd ≡ 1(mod ф(n)),已知 d,由 y计
算出 x是容易的，因为 yd ≡ x (mod n)。 d就是它
的陷门信息。如果我们不知道 ф(n),而仅知道 k，
要想求出 d是很困难的，这是一个 NPC问题。
所以 f(x)还是一个单向陷门函数。
2010-5-14 计算机算法设计与分析 10
代表算法
? RSA(Rivest,Shamir,Adleman)
? 椭圆曲线 (ECC) (Eilliptic Curve
Croptography)
? 背包算法
2010-5-14 计算机算法设计与分析 11
RSA公钥密码体制
2010-5-14 计算机算法设计与分析 12
RSA公钥算法
? RSA公钥算法是由 R,Rivest,A,Shamir和
L,Adleman在 1977年提出来的。
? 该 算法的数学 基础 是 初 等数 论 中的 欧拉
(Euler)定理 并建立 在大整数 因子分解 的困
难性 之 上的
2010-5-14 计算机算法设计与分析 13
欧拉定理
? 若整数 a和 m互素，则
a?(n) ≡ 1 (mod n)
? 其中 ?(n)为比 n小但与 n互素的正整数个数,
称为 n的欧拉函数。
? 比如,?(10) = |{9,7,3,1}| = 4，
?(15)=|{14,13,11,8,7,4,2,1}| = 8。
? 计算 ?(n)很困难。但 可以证明，若 n = p*q
(p,q均为素数 ),?(n)=(p – 1)*(q – 1)。
2010-5-14 计算机算法设计与分析 14
用欧拉函数构造单向陷门函数
? 选取大整数 n和一个与 ?(n)互质的整数 e,将 n和
e公开。 若要对明文 m加密，则令
c = me (mod n)。
? 显然，这是一个单向函数。
? 若已知一个整数 d满足 e*d (mod ?(n)) = 1,则
cd = (me)d (mod n) = (med) (mod n)
= (m ?(n)+1) (mod n) = (m*m ?(n)) (mod n) = m。
? 这里，整数 d就是陷门。
2010-5-14 计算机算法设计与分析 15
RSA密码 体制 描述
? A,密钥的 生 成：
? 1,选 择两个素 数 p,q,计算 n = p*q和
?(n) = (p –1)*(q – 1)。
? 2、选取整数 b,使其满足 gcd(b,?(n)) = 1，
1 < b < ?(n)，
? 3,计算 a,满足 a*b ≡ 1 mod ?(n) 。
? 4、将 n和 b作为加密秘钥公开，将 p,q和
a作为解密秘 钥保密。
2010-5-14 计算机算法设计与分析 16
RSA密码 体制 描述
? B,加密 的过程：
? 1、将明文数字化，并选取长度小于 log n
位的数字作为明文信息块。
? 2、加密明文 m,令 c = E(m) = mb mod n。
? C,解密 的过程：
? 对密文 c计算, m = D(c) = ca mod n，得到
明文 m。
2010-5-14 计算机算法设计与分析 17
RSA算法 的举例
? A,密钥的生成
? 1、取素数 43和 59，则 n = 43*59 = 2537，
?(n) = 42*58 = 2436。
? 2、选取 b为 13，显然满足 gcd(b,?(n)) = 1，
1 < b < ?(n)。
? 3、解方程 ab≡1 mod 2436, a = 937。
? 4,将 2537和 13作为加密公钥,937和
2436保密。
2010-5-14 计算机算法设计与分析 18
RSA算法 的举例
? B,加密过程,
? 现有明文,public key encryptions”要加密。
首先将其以两个字符为一组进行分组为：
pu bl ic ke ye nc ry pt io ns
? 令 00表示 a,01表示 b,…, 将其数字化
编码为：
? 1520 0111 0802 1004 2404 1302 1742 1519
0814 1418
2010-5-14 计算机算法设计与分析 19
RSA算法 的举例
? 先讨论对第一个明文数字 m1 = 1520的加密：
? E(m1) = m1b mod n = 152013 mod 2537
? = (15202)6*1520 mod 2537 ∵ 15202 ?
1730 mod 2537?= (1730)6*1520 mod 2537
?= (17302)3*1520 mod 2537 ∵ 17302 ?
1777 mod 2537?= (1777)3*1520 mod 2537
?= (1777)2*(1777*1520) mod 2537
∵ 1777
01
1777*1520 ?
6 2
?= 1701*1672 mod 2537 = 0095
2010-5-14 计算机算法设计与分析 20
RSA算法 的举例
? 类似地，对其它数字加密后得到密文序列为：
? 0095 1648 1410 1299 1365 1379 2333 2132 1751
1289
? C,解密过程：
? 解密运算的过程与加密过程类似，只不过将 b
换成 a。 例如：
? m1 = D(0095) = 0095937 mod 2537
? = (952)468*95 mod 2537 = …… =1520
2010-5-14 计算机算法设计与分析 21
RSA算法 的讨论
? 若使 RSA安全,p与 q必为足够大的素数。
? 建议选择 p和 q为 100位以上的十进制素数。
? 模 n的长度要求至少是 512比特。 EDI攻击
标准使用的 RSA算法中规定 n的长度为
512至 1024比特位之间，但必须是 128的
倍数。
? 国际数字签名标准 ISO/IEC 9796中规定 n
的长度位 512比特位。
2010-5-14 计算机算法设计与分析 22
RSA算法 的讨论
? 为了抵抗现有的整数分解算法，对 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。
2010-5-14 计算机算法设计与分析 23
RSA算法的讨论
? 为了提高加密速度通常取 b为特定的小整数。
如 EDI国际标准中规定 b = 216 + 1,ISO/IEC9796
中甚至允许取 b = 3。 这时加密速度一般比解密
速度快 10倍以上。
? 加密和解密算 术运 算 主 要是 模 n的求 幂运 算。
著名的,平 方 -和 -乘 法”方法将计算 xc mod n的
模乘 法的数 目缩小 到至 多 为 2l。 这里的 l是指数
a的 二 进 制 表 示的比特 数。若设 n以 二 进 制形式
表 示 有 k比特 即 k=[log2n]+1 由 l k 这 样 xc mod n
能在 o(k3)时间 内 完成。
2010-5-14 计算机算法设计与分析 24
椭圆曲线密码体制
2010-5-14 计算机算法设计与分析 25
椭圆曲线
? 实数域上的一个椭圆曲线是指满足方程：
y2 = x3+ax+b (x,y,a,b?R)
? 的所有点 (x,y)所形成的平面曲线。
? 有限域上模 p,p为素数，的一个椭圆曲
线是指满足方程：
y2 = x3+ax+b mod p (x,y,a,b?Z)
? 的所有点 (x,y)所形成的平面曲线。
2010-5-14 计算机算法设计与分析 26
椭圆曲线群
? 若椭圆曲线 y2 = x3+ax+b满足
4a3 + 27b2 ? 0 mod p
? 则由该椭圆曲线上的点再加上一个无穷
远点 ?，可以形成一个 Abel群。
? 这里无穷远点 ?是一个抽象的点，可以想
象为平行线的交点。
? 有限域上模 p的椭圆曲线群记为 Ep(a,b)。
2010-5-14 计算机算法设计与分析 27
一个有限域上的椭圆曲线群
? 设 p = 23,令 y2 = x3 + x + 1,即 a = 1,b = 1。
? ∵ 4a3 + 27b2 ? 0 mod p ∴ 该 曲线在 F23上的点,
? (0,1) (0,22) (1,7) (1,16) (3,10) (3,13) (4,0) (5,4)
(5,19) (6,4) (6,19) (7,11) (7,12) (9,7) (9,16) (11,3)
(11,20) (12,4) (12,19) (13,7) (13,16) (17,3) (17,20)
(18,3) (18,20) (19,5) (19,18)，
? 再加上无穷远点 ?构成椭圆曲线群 E23(1,1)。
? 群 E23(1,1)包 括 无 穷远点 ?在内 有 28个 点 。
2010-5-14 计算机算法设计与分析 28
椭圆曲线群的加法 ?
? 定义 Ep(a,b)上点的 加法 ?为：
? ⑴ ? 为 单位 元素；
? ⑵ (x,y) ?(x,–y) = ?,即 点 (x,y)的 逆 为 (x,–y)。
? ⑶ 令 P = (x1,y1),Q = (x2,y2)且非 互逆,则
P ? Q = (x1,y1) ? (x2,y2) = (x3,y3),
? 其中,x3 = k2 – x1 – x2 mod p，
y3= k(x1 – x3) – y1 mod p，
k = (y2 – y1) / (x2 – x1)。
易证 Ep(a,b)
对 加法 ?构
成 Abel群。
2010-5-14 计算机算法设计与分析 29
? 椭圆曲线群的点加运算 P ? Q在几何上的
定义是 P,Q两点的连线与椭圆曲线 E的
交点的对称点。
? 而当 P = Q,P?Q在几何上的定义就成了
椭圆曲线 E在 P点的切线与 E的交点的对称
点。因此，倍点运算，即 2P = P ? P的计
算，有别于 P ? Q。
2010-5-14 计算机算法设计与分析 30
椭圆曲线群的倍点运算
? 令 P = (x1,y1),y1 ? 0,则
2P = 2(x1,y1) = (x3,y3),
? 其中,x3 = k2 – 2x1 mod p，
? y3= k(x1 – x3) – y1 mod p，
? k = (3x12 + a) / 2y1。
? 注意，虽然 x3和 y3的计算公式与点加公式中的
形式仍然完全是一样的，但是 k的计算却完全
不一样了。
2010-5-14 计算机算法设计与分析 31
椭圆曲线 点群 的 离散 对数问题
? 1985年 N,Koblitz和 V,Miller分别 独立 提
出了椭圆曲线密码 体制 (ECC),其 依据就
是椭圆曲线 点群 的 离散 对数问题的难解
性。
设 G = (x,y)是椭圆曲线点群 Ep(a,b)的一个生成
元，且 G的 周期 n是一个很 大素数。
? 所谓 G的 周期 n就是 使得 nP = ?的最小正整数 n。
? 设 Q是 Ep(a,b)中的点，则必有 正整数 m使得
Q = mG
于是，定义 m = log G Q。
? 已知 m和 G求 Q的计算是很容易的，但是已知 Q
和 G,要求 m却是非常困难的。
? 这就是 椭圆曲线点群上的离散对数问题。
2010-5-14 计算机算法设计与分析 32
椭圆曲线密码体制
? A,密钥的 生 成：
? 1、选择素数 p构造椭圆曲线群 Ep(a,b)。
? 2,选择 Ep(a,b)的一个点 G,使得 G的阶 n
是一个大素数。
? 3、秘密选择整数 d < n,计算 Q = dG。
? 4,将 (p,a,b,G,Q)作为加密公钥公开,
把整数 d作为解密思钥保密 。
2010-5-14 计算机算法设计与分析 33
椭圆曲线密码体制
? B,加密过程,
? 1、将明文 m编码为 Ep(a,b)的点 Pm。
? 2、随机选择 k,计算 kG和 kP。 (若 kG或 kP为 ?，
则要重新选择 k。 )
? 3,将 c = (kG,Pm ? kP)作为密文。
? C,解密过程,
? 1、计算 Pm ? kP – dkG = Pm。
? ∵ P = dG ∴ kP = dkG。2,将 Pm解码为 m。
2010-5-14 计算机算法设计与分析 34
椭圆曲线密码的举例
? A,密钥的生成：
? 1、取 y2 = x3 + ax + b mod p中的 a,b和 p
分别为 –1,188和 751，得到 E751(–1,188)。
? 2,选 G为 (0,376)，阶为 769(即 769G = ?)。
? 3,选 d = 85,计算 P = 85G = (671,558)
? 4,将 (751,–1,188,(671,558))作为公钥公
开。将 85作为私钥。
2010-5-14 计算机算法设计与分析 35
椭圆曲线密码的举例
? B,加密过程：
? 1、设明文 m编码为 E751(–1,188)的点 (443,253)。
? 2、随机选取 k = 113,计算：
kG = 113(0,376) = (34,633)；
kP = 113(671,558) = (47,416)
Pm ? kP = (443,253) ? (47,416) = (217,606)
? 3,最后将 ((34,633),(217,606))作为密文。
2010-5-14 计算机算法设计与分析 36
椭圆曲线密码的举例
? C,解密过程：
? 1、收到密文 ((34,633),(217,606)),利用私钥
85计算,85(34,633) = (47,416)；
? 2、计算,(217,606) – (47,416)
= (217,606) ? (47,–416)
= (217,606) ? (47,335)
= (443,253)；
? 3、将 (443,253)解码便得到明文 m。
两者互逆
335 = –416 mod 751
2010-5-14 计算机算法设计与分析 37
椭圆曲线密码体制的安全性
? 自从椭圆曲线密码体制提出来以后，它
一直受到数学界和密码学界的关注。但
是迄今为止，还未见相当有效的攻击算
法的报道。
? 如果有 1000MIPS的计算机 10000台，取
长约 160比特的素数，则计算椭圆曲线的
离散对数问题需要 96000年。因此椭圆曲
线密码体制被认为是安全的。
2010-5-14 计算机算法设计与分析 38
背包公钥密码体制
2010-5-14 计算机算法设计与分析 39
0-1背包问题
? 已知一容积为 b的背包及体积分别为 a1,a2,…a n
的 n个物品，从这些物品中选出若干个正好装
满这个背包，那么究竟是那些物品？
? 即求解,
n? a
ixi = b,xi ? {0,1},i=1,…,n,i=1
? 其中 ai和 b都是正整数。
2010-5-14 计算机算法设计与分析 40
背包公钥密码
? 选取正整数 a1,a2,…,a n作为公钥，设明
文位串为 m = m1m2…m n,mi ? {0,1} 。
? 利用公钥将明文加密为密文
c = a1m1 + a2m2 + … + a nmn。
? 这样，如果要将其解密，即从密文 c求得
明文 m等价于求解一个背包问题。
2010-5-14 计算机算法设计与分析 41
超递增序列
? 简单的说，序列 {a1,a2,…,a n}是超递增的，就
是该序列中的每个元素都大于序列中位于它
之前的所有元素之和。
i–1 ? a
j < ai,i = 2,3,……, nj=1
? 序列 {a1,a2,…,a n}是超递增的，如果满足
? 的序列 {a1,a2,……, an}。
2010-5-14 计算机算法设计与分析 42
超递增序列的背包问题易解
? 背包问题难解，但是超递增序列 {a1,…,an–1,an}
构成的背包问题却不难解。
? 设 序列 {a1,…,an–1,an}是超递增的。求背包问
题 a1x1 + … + a n–1xn–1 + anxn = c 。
? 显然，若 c > an,则 xn为 1，否则 xn为 0。
? 确定了 xn之后，将 c减去 an或不变，就得到一个
新的 m – 1个变量的背包问题。
? 用同样方法确定 xn–1。 重复进行，求出所有 xi。
2010-5-14 计算机算法设计与分析 43
MH背包公钥密码
? 显然，不能将 超递增序列 {a1,a2,…,a n}直接作
为公钥使用，而应将其超递增性掩盖起来，转
换为一个非超递增序列作为公钥使用。
? 这就是由 Merkle和 Martin Helman合作设计的一
个基于 0-1背包问题的公钥密码算法的思想。这
个算法简称为 MH背包密码算法。
2010-5-14 计算机算法设计与分析 44
将超递增性隐藏起来
? 选取一个超递增序列,a1,a2,…, an。
? 选取正整数 m和 w,m > a1 + a2 +…+ a n且
(w,m) = 1,作变换：
bi=wai mod m，
? 于是得到新序列,b1,b2,…,bn。
? 将新序列作为加密的公钥。
? {b1,b2,…,b n}不再是超递增序列。
2010-5-14 计算机算法设计与分析 45
将超递增性隐藏起来
? 例如：超递增序列为 {1,2,5,9,20,41,83,164}，
选取 m = 353,w = 233。做变换：
? b1 = 233*1 mod 353 = 233，
? b2 = 233*2 mod 353 = 113，
? ……
? 得到新序列 (233,113,106,332,71,22,277,88)。
? 这个序列不再是超递增序列，将它作为公钥。
? 这样，用新序列加密就成了一般的背包问题。
2010-5-14 计算机算法设计与分析 46
MH背包密码的陷门
? 若知道 w,由于 (w,m)=1,故存在 w–1满足：
ww–1 ≡1(mod m)
? w–1就是 MH背包密码的陷门 。
? 应用 w–1, 解密就变得很容易了：
? w–1c≡w–1b1m1+ w–1b2m2+… + w–1bnmn (mod m)
? 由于 w–1bi≡ w–1wai ≡ ai(mod m) i = 1,2,…,n
? 所以有 m1a1 + m2a2 +… + mnan≡ w–1c (mod m)。
? 这样, 就还原为超递增序列的背包问题 。
2010-5-14 计算机算法设计与分析 47
背包公钥密码的例子
? A,密钥的生成
? 选取超递增序列为 {1,2,5,9,20,41,83,164}，
m = 353,w = 233,计算得 w–1 = 50。 做变换：
? b1 = 233*1 mod 353 = 233，
? b2 = 233*2 mod 353 = 113，
? ……
? 得到新序列 (233,113,106,332,71,22,277,88)。
? 将新序列作为公钥，原超递增序列为私钥。
2010-5-14 计算机算法设计与分析 48
背包公钥密码的例子
? B,加密过程：
? 设发送的明文为,010110011100101010001001。
? 先将明文分块为：
01011001 11001010 10001001
? 01011001对应的密文为,a2+a4+a5+ a8
公钥序列：
(233,113,106,332,71,22,277,88)
= 113 +332 +71 + 88
= 604
604
? 11001010对应的密文为,a1+a2+a5+ a7
= 233 +113 +71 + 277
= 694
694
? 同样方法的出 10001001对应的密文为,392。
? 这样，密文为,604,694,392。
2010-5-14 计算机算法设计与分析 49
背包公钥密码的例子
? C,解密过程：
? 收到密文后，分别先计算 50乘以密文值模 353，
然后再解超递增序列 (私钥 )背包问题 。
? 比如，对 604，先计算 50*604 mod 353 = 195
? 然后解超递增序列 {1,2,5,9,20,41,83,164}的
背包问题，易得 2 + 9 + 20 + 164 = 195,于是
对应的明文为,01011001。
? 同样的方法求得,694和 392的明文。
2010-5-14 计算机算法设计与分析 50
背包公钥密码的安全性
? Merkle悬赏 $100请人破译背包密码。
? 1982年,Adi Shamir攻破了使用一次循环的背
包密码，他得到了 $100。
? 然后,Merkle又悬赏 $1000请人破译多次循环
的背包密码。
? Ernie Brikelld用超级计算机在一小时内攻破了
有 100个重物,40次循环的背包算法。他得到
了 $1000。
? MH背包算法未能成为可以实用的密码系统。
2010-5-14 计算机算法设计与分析 51
感谢合作，谢谢！
敬请多提批评意见和宝贵建议。
周经野
第十一章
公钥密码学基础
2010-5-14 计算机算法设计与分析 2
密码、加密与解密
? 密码是通信双方按约定的法则进行信息
特殊变换的一种重要保密手段。
? 依照法则变明文为密文，称为加密变换；
? 依照法则变密文为明文，称为解密变换。
? 早期密码学仅对文字或数码进行加、解
密变换。现代密码学还可以对语音、图
像、数据等都可实施加、解密变换。
2010-5-14 计算机算法设计与分析 3
密码体制
? 进行明密变换的法则，称为密码体制。
? 密码体制可以分为四种基本类型：
? 错乱：按照规定方式改变明文符号的位置；
? 代替：用一个或多个代替表来代替明文符号；
? 密本：用预先编定的字母或数字密码组来代替
明文中一定的词组单词等；
? 加乱：用有限元素组成的一串序列作为乱数，
按规定的算法，同明文序列相结合变成密文。
? 这四种体制，既可单独使用，也可混合使用。
2010-5-14 计算机算法设计与分析 4
密钥和公钥密码的思想
? 1976年美国斯坦福大学的 Diffle和
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
为密码系统分别设计一个加密密钥 kc和
一个解密密钥 kd。
把 kc公开，而把 kd保密，同时 kc的公开
不会影响 kd的安全。这样：
? 加密的过程为,c = Ekc(m)，
? 解密的过程为,m = Dkd(c)。
2010-5-14 计算机算法设计与分析 5
秘钥与公钥
? 密码学分为秘钥密码学和公钥密码学。
? 秘钥密码学在加密和解密所使用的密钥
是相同的，又称为对称密码学。
? 公钥密码学加密和解密所使用的密钥是
不相同的，且前者 (签字密钥 )公开而 后者
(验证密钥 )保密，又称为 非对称密码学。
2010-5-14 计算机算法设计与分析 6
公钥密码学的各种技术及功能
? 1、保密通信
? 2、数字签名
? 3、秘密共享
? 4、认证功能
2010-5-14 计算机算法设计与分析 7
单向函数
? 加密的过程和解密的过程分别为：
c = E (m)和 m = D(c)
? 显然 D是 E的逆函数，即 D = E–1。
? 设 f(x) 是 En上的一个变换,En={0,1,…,n –1}，
f(x)是单向的，若由 x计算 y = f(x)是容易的，即
P问题，而由 y计算出 x是困难的，即 NPC问题。
? 因此，公钥密码学的思想就是让加密函数是一
个单向函数。 加密容易解密难！
2010-5-14 计算机算法设计与分析 8
单向陷门函数
? 加密容易解密难。要难住别人，却不要难住自
己。怎么办？
? f(x) 说是单向陷门函数，如果有陷门信息 K，
当 K未知时,f(x)是单向的，当 K已知时，由 y
计算出 x是容易的。
? 公约密码学的思想就是将加密函数设计为一个
单向陷门函数，而把陷门信息 K作为解密密码。
? 解密密码 K是保密的。有了解密密码，就很容
易解密，而不知道解密密码，就很难解密。
2010-5-14 计算机算法设计与分析 9
单向陷门函数
? 例如：取两个不相等的质数 p和 q,令 n = pq，
取函数 f(x) = xk mod n,且 (k,ф(n))=1,其中 ф(n)
是 n的欧拉函数 (即 ф(n)=(p – 1)*(q – 1)),则 f(x)
是一个单向函数。
? 如果有 d使得 kd ≡ 1(mod ф(n)),已知 d,由 y计
算出 x是容易的，因为 yd ≡ x (mod n)。 d就是它
的陷门信息。如果我们不知道 ф(n),而仅知道 k，
要想求出 d是很困难的，这是一个 NPC问题。
所以 f(x)还是一个单向陷门函数。
2010-5-14 计算机算法设计与分析 10
代表算法
? RSA(Rivest,Shamir,Adleman)
? 椭圆曲线 (ECC) (Eilliptic Curve
Croptography)
? 背包算法
2010-5-14 计算机算法设计与分析 11
RSA公钥密码体制
2010-5-14 计算机算法设计与分析 12
RSA公钥算法
? RSA公钥算法是由 R,Rivest,A,Shamir和
L,Adleman在 1977年提出来的。
? 该 算法的数学 基础 是 初 等数 论 中的 欧拉
(Euler)定理 并建立 在大整数 因子分解 的困
难性 之 上的
2010-5-14 计算机算法设计与分析 13
欧拉定理
? 若整数 a和 m互素，则
a?(n) ≡ 1 (mod n)
? 其中 ?(n)为比 n小但与 n互素的正整数个数,
称为 n的欧拉函数。
? 比如,?(10) = |{9,7,3,1}| = 4，
?(15)=|{14,13,11,8,7,4,2,1}| = 8。
? 计算 ?(n)很困难。但 可以证明，若 n = p*q
(p,q均为素数 ),?(n)=(p – 1)*(q – 1)。
2010-5-14 计算机算法设计与分析 14
用欧拉函数构造单向陷门函数
? 选取大整数 n和一个与 ?(n)互质的整数 e,将 n和
e公开。 若要对明文 m加密，则令
c = me (mod n)。
? 显然，这是一个单向函数。
? 若已知一个整数 d满足 e*d (mod ?(n)) = 1,则
cd = (me)d (mod n) = (med) (mod n)
= (m ?(n)+1) (mod n) = (m*m ?(n)) (mod n) = m。
? 这里，整数 d就是陷门。
2010-5-14 计算机算法设计与分析 15
RSA密码 体制 描述
? A,密钥的 生 成：
? 1,选 择两个素 数 p,q,计算 n = p*q和
?(n) = (p –1)*(q – 1)。
? 2、选取整数 b,使其满足 gcd(b,?(n)) = 1，
1 < b < ?(n)，
? 3,计算 a,满足 a*b ≡ 1 mod ?(n) 。
? 4、将 n和 b作为加密秘钥公开，将 p,q和
a作为解密秘 钥保密。
2010-5-14 计算机算法设计与分析 16
RSA密码 体制 描述
? B,加密 的过程：
? 1、将明文数字化，并选取长度小于 log n
位的数字作为明文信息块。
? 2、加密明文 m,令 c = E(m) = mb mod n。
? C,解密 的过程：
? 对密文 c计算, m = D(c) = ca mod n，得到
明文 m。
2010-5-14 计算机算法设计与分析 17
RSA算法 的举例
? A,密钥的生成
? 1、取素数 43和 59，则 n = 43*59 = 2537，
?(n) = 42*58 = 2436。
? 2、选取 b为 13，显然满足 gcd(b,?(n)) = 1，
1 < b < ?(n)。
? 3、解方程 ab≡1 mod 2436, a = 937。
? 4,将 2537和 13作为加密公钥,937和
2436保密。
2010-5-14 计算机算法设计与分析 18
RSA算法 的举例
? B,加密过程,
? 现有明文,public key encryptions”要加密。
首先将其以两个字符为一组进行分组为：
pu bl ic ke ye nc ry pt io ns
? 令 00表示 a,01表示 b,…, 将其数字化
编码为：
? 1520 0111 0802 1004 2404 1302 1742 1519
0814 1418
2010-5-14 计算机算法设计与分析 19
RSA算法 的举例
? 先讨论对第一个明文数字 m1 = 1520的加密：
? E(m1) = m1b mod n = 152013 mod 2537
? = (15202)6*1520 mod 2537 ∵ 15202 ?
1730 mod 2537?= (1730)6*1520 mod 2537
?= (17302)3*1520 mod 2537 ∵ 17302 ?
1777 mod 2537?= (1777)3*1520 mod 2537
?= (1777)2*(1777*1520) mod 2537
∵ 1777
01
1777*1520 ?
6 2
?= 1701*1672 mod 2537 = 0095
2010-5-14 计算机算法设计与分析 20
RSA算法 的举例
? 类似地，对其它数字加密后得到密文序列为：
? 0095 1648 1410 1299 1365 1379 2333 2132 1751
1289
? C,解密过程：
? 解密运算的过程与加密过程类似，只不过将 b
换成 a。 例如：
? m1 = D(0095) = 0095937 mod 2537
? = (952)468*95 mod 2537 = …… =1520
2010-5-14 计算机算法设计与分析 21
RSA算法 的讨论
? 若使 RSA安全,p与 q必为足够大的素数。
? 建议选择 p和 q为 100位以上的十进制素数。
? 模 n的长度要求至少是 512比特。 EDI攻击
标准使用的 RSA算法中规定 n的长度为
512至 1024比特位之间，但必须是 128的
倍数。
? 国际数字签名标准 ISO/IEC 9796中规定 n
的长度位 512比特位。
2010-5-14 计算机算法设计与分析 22
RSA算法 的讨论
? 为了抵抗现有的整数分解算法，对 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。
2010-5-14 计算机算法设计与分析 23
RSA算法的讨论
? 为了提高加密速度通常取 b为特定的小整数。
如 EDI国际标准中规定 b = 216 + 1,ISO/IEC9796
中甚至允许取 b = 3。 这时加密速度一般比解密
速度快 10倍以上。
? 加密和解密算 术运 算 主 要是 模 n的求 幂运 算。
著名的,平 方 -和 -乘 法”方法将计算 xc mod n的
模乘 法的数 目缩小 到至 多 为 2l。 这里的 l是指数
a的 二 进 制 表 示的比特 数。若设 n以 二 进 制形式
表 示 有 k比特 即 k=[log2n]+1 由 l k 这 样 xc mod n
能在 o(k3)时间 内 完成。
2010-5-14 计算机算法设计与分析 24
椭圆曲线密码体制
2010-5-14 计算机算法设计与分析 25
椭圆曲线
? 实数域上的一个椭圆曲线是指满足方程：
y2 = x3+ax+b (x,y,a,b?R)
? 的所有点 (x,y)所形成的平面曲线。
? 有限域上模 p,p为素数，的一个椭圆曲
线是指满足方程：
y2 = x3+ax+b mod p (x,y,a,b?Z)
? 的所有点 (x,y)所形成的平面曲线。
2010-5-14 计算机算法设计与分析 26
椭圆曲线群
? 若椭圆曲线 y2 = x3+ax+b满足
4a3 + 27b2 ? 0 mod p
? 则由该椭圆曲线上的点再加上一个无穷
远点 ?，可以形成一个 Abel群。
? 这里无穷远点 ?是一个抽象的点，可以想
象为平行线的交点。
? 有限域上模 p的椭圆曲线群记为 Ep(a,b)。
2010-5-14 计算机算法设计与分析 27
一个有限域上的椭圆曲线群
? 设 p = 23,令 y2 = x3 + x + 1,即 a = 1,b = 1。
? ∵ 4a3 + 27b2 ? 0 mod p ∴ 该 曲线在 F23上的点,
? (0,1) (0,22) (1,7) (1,16) (3,10) (3,13) (4,0) (5,4)
(5,19) (6,4) (6,19) (7,11) (7,12) (9,7) (9,16) (11,3)
(11,20) (12,4) (12,19) (13,7) (13,16) (17,3) (17,20)
(18,3) (18,20) (19,5) (19,18)，
? 再加上无穷远点 ?构成椭圆曲线群 E23(1,1)。
? 群 E23(1,1)包 括 无 穷远点 ?在内 有 28个 点 。
2010-5-14 计算机算法设计与分析 28
椭圆曲线群的加法 ?
? 定义 Ep(a,b)上点的 加法 ?为：
? ⑴ ? 为 单位 元素；
? ⑵ (x,y) ?(x,–y) = ?,即 点 (x,y)的 逆 为 (x,–y)。
? ⑶ 令 P = (x1,y1),Q = (x2,y2)且非 互逆,则
P ? Q = (x1,y1) ? (x2,y2) = (x3,y3),
? 其中,x3 = k2 – x1 – x2 mod p，
y3= k(x1 – x3) – y1 mod p，
k = (y2 – y1) / (x2 – x1)。
易证 Ep(a,b)
对 加法 ?构
成 Abel群。
2010-5-14 计算机算法设计与分析 29
? 椭圆曲线群的点加运算 P ? Q在几何上的
定义是 P,Q两点的连线与椭圆曲线 E的
交点的对称点。
? 而当 P = Q,P?Q在几何上的定义就成了
椭圆曲线 E在 P点的切线与 E的交点的对称
点。因此，倍点运算，即 2P = P ? P的计
算，有别于 P ? Q。
2010-5-14 计算机算法设计与分析 30
椭圆曲线群的倍点运算
? 令 P = (x1,y1),y1 ? 0,则
2P = 2(x1,y1) = (x3,y3),
? 其中,x3 = k2 – 2x1 mod p，
? y3= k(x1 – x3) – y1 mod p，
? k = (3x12 + a) / 2y1。
? 注意，虽然 x3和 y3的计算公式与点加公式中的
形式仍然完全是一样的，但是 k的计算却完全
不一样了。
2010-5-14 计算机算法设计与分析 31
椭圆曲线 点群 的 离散 对数问题
? 1985年 N,Koblitz和 V,Miller分别 独立 提
出了椭圆曲线密码 体制 (ECC),其 依据就
是椭圆曲线 点群 的 离散 对数问题的难解
性。
设 G = (x,y)是椭圆曲线点群 Ep(a,b)的一个生成
元，且 G的 周期 n是一个很 大素数。
? 所谓 G的 周期 n就是 使得 nP = ?的最小正整数 n。
? 设 Q是 Ep(a,b)中的点，则必有 正整数 m使得
Q = mG
于是，定义 m = log G Q。
? 已知 m和 G求 Q的计算是很容易的，但是已知 Q
和 G,要求 m却是非常困难的。
? 这就是 椭圆曲线点群上的离散对数问题。
2010-5-14 计算机算法设计与分析 32
椭圆曲线密码体制
? A,密钥的 生 成：
? 1、选择素数 p构造椭圆曲线群 Ep(a,b)。
? 2,选择 Ep(a,b)的一个点 G,使得 G的阶 n
是一个大素数。
? 3、秘密选择整数 d < n,计算 Q = dG。
? 4,将 (p,a,b,G,Q)作为加密公钥公开,
把整数 d作为解密思钥保密 。
2010-5-14 计算机算法设计与分析 33
椭圆曲线密码体制
? B,加密过程,
? 1、将明文 m编码为 Ep(a,b)的点 Pm。
? 2、随机选择 k,计算 kG和 kP。 (若 kG或 kP为 ?，
则要重新选择 k。 )
? 3,将 c = (kG,Pm ? kP)作为密文。
? C,解密过程,
? 1、计算 Pm ? kP – dkG = Pm。
? ∵ P = dG ∴ kP = dkG。2,将 Pm解码为 m。
2010-5-14 计算机算法设计与分析 34
椭圆曲线密码的举例
? A,密钥的生成：
? 1、取 y2 = x3 + ax + b mod p中的 a,b和 p
分别为 –1,188和 751，得到 E751(–1,188)。
? 2,选 G为 (0,376)，阶为 769(即 769G = ?)。
? 3,选 d = 85,计算 P = 85G = (671,558)
? 4,将 (751,–1,188,(671,558))作为公钥公
开。将 85作为私钥。
2010-5-14 计算机算法设计与分析 35
椭圆曲线密码的举例
? B,加密过程：
? 1、设明文 m编码为 E751(–1,188)的点 (443,253)。
? 2、随机选取 k = 113,计算：
kG = 113(0,376) = (34,633)；
kP = 113(671,558) = (47,416)
Pm ? kP = (443,253) ? (47,416) = (217,606)
? 3,最后将 ((34,633),(217,606))作为密文。
2010-5-14 计算机算法设计与分析 36
椭圆曲线密码的举例
? C,解密过程：
? 1、收到密文 ((34,633),(217,606)),利用私钥
85计算,85(34,633) = (47,416)；
? 2、计算,(217,606) – (47,416)
= (217,606) ? (47,–416)
= (217,606) ? (47,335)
= (443,253)；
? 3、将 (443,253)解码便得到明文 m。
两者互逆
335 = –416 mod 751
2010-5-14 计算机算法设计与分析 37
椭圆曲线密码体制的安全性
? 自从椭圆曲线密码体制提出来以后，它
一直受到数学界和密码学界的关注。但
是迄今为止，还未见相当有效的攻击算
法的报道。
? 如果有 1000MIPS的计算机 10000台，取
长约 160比特的素数，则计算椭圆曲线的
离散对数问题需要 96000年。因此椭圆曲
线密码体制被认为是安全的。
2010-5-14 计算机算法设计与分析 38
背包公钥密码体制
2010-5-14 计算机算法设计与分析 39
0-1背包问题
? 已知一容积为 b的背包及体积分别为 a1,a2,…a n
的 n个物品，从这些物品中选出若干个正好装
满这个背包，那么究竟是那些物品？
? 即求解,
n? a
ixi = b,xi ? {0,1},i=1,…,n,i=1
? 其中 ai和 b都是正整数。
2010-5-14 计算机算法设计与分析 40
背包公钥密码
? 选取正整数 a1,a2,…,a n作为公钥，设明
文位串为 m = m1m2…m n,mi ? {0,1} 。
? 利用公钥将明文加密为密文
c = a1m1 + a2m2 + … + a nmn。
? 这样，如果要将其解密，即从密文 c求得
明文 m等价于求解一个背包问题。
2010-5-14 计算机算法设计与分析 41
超递增序列
? 简单的说，序列 {a1,a2,…,a n}是超递增的，就
是该序列中的每个元素都大于序列中位于它
之前的所有元素之和。
i–1 ? a
j < ai,i = 2,3,……, nj=1
? 序列 {a1,a2,…,a n}是超递增的，如果满足
? 的序列 {a1,a2,……, an}。
2010-5-14 计算机算法设计与分析 42
超递增序列的背包问题易解
? 背包问题难解，但是超递增序列 {a1,…,an–1,an}
构成的背包问题却不难解。
? 设 序列 {a1,…,an–1,an}是超递增的。求背包问
题 a1x1 + … + a n–1xn–1 + anxn = c 。
? 显然，若 c > an,则 xn为 1，否则 xn为 0。
? 确定了 xn之后，将 c减去 an或不变，就得到一个
新的 m – 1个变量的背包问题。
? 用同样方法确定 xn–1。 重复进行，求出所有 xi。
2010-5-14 计算机算法设计与分析 43
MH背包公钥密码
? 显然，不能将 超递增序列 {a1,a2,…,a n}直接作
为公钥使用，而应将其超递增性掩盖起来，转
换为一个非超递增序列作为公钥使用。
? 这就是由 Merkle和 Martin Helman合作设计的一
个基于 0-1背包问题的公钥密码算法的思想。这
个算法简称为 MH背包密码算法。
2010-5-14 计算机算法设计与分析 44
将超递增性隐藏起来
? 选取一个超递增序列,a1,a2,…, an。
? 选取正整数 m和 w,m > a1 + a2 +…+ a n且
(w,m) = 1,作变换：
bi=wai mod m，
? 于是得到新序列,b1,b2,…,bn。
? 将新序列作为加密的公钥。
? {b1,b2,…,b n}不再是超递增序列。
2010-5-14 计算机算法设计与分析 45
将超递增性隐藏起来
? 例如：超递增序列为 {1,2,5,9,20,41,83,164}，
选取 m = 353,w = 233。做变换：
? b1 = 233*1 mod 353 = 233，
? b2 = 233*2 mod 353 = 113，
? ……
? 得到新序列 (233,113,106,332,71,22,277,88)。
? 这个序列不再是超递增序列，将它作为公钥。
? 这样，用新序列加密就成了一般的背包问题。
2010-5-14 计算机算法设计与分析 46
MH背包密码的陷门
? 若知道 w,由于 (w,m)=1,故存在 w–1满足：
ww–1 ≡1(mod m)
? w–1就是 MH背包密码的陷门 。
? 应用 w–1, 解密就变得很容易了：
? w–1c≡w–1b1m1+ w–1b2m2+… + w–1bnmn (mod m)
? 由于 w–1bi≡ w–1wai ≡ ai(mod m) i = 1,2,…,n
? 所以有 m1a1 + m2a2 +… + mnan≡ w–1c (mod m)。
? 这样, 就还原为超递增序列的背包问题 。
2010-5-14 计算机算法设计与分析 47
背包公钥密码的例子
? A,密钥的生成
? 选取超递增序列为 {1,2,5,9,20,41,83,164}，
m = 353,w = 233,计算得 w–1 = 50。 做变换：
? b1 = 233*1 mod 353 = 233，
? b2 = 233*2 mod 353 = 113，
? ……
? 得到新序列 (233,113,106,332,71,22,277,88)。
? 将新序列作为公钥，原超递增序列为私钥。
2010-5-14 计算机算法设计与分析 48
背包公钥密码的例子
? B,加密过程：
? 设发送的明文为,010110011100101010001001。
? 先将明文分块为：
01011001 11001010 10001001
? 01011001对应的密文为,a2+a4+a5+ a8
公钥序列：
(233,113,106,332,71,22,277,88)
= 113 +332 +71 + 88
= 604
604
? 11001010对应的密文为,a1+a2+a5+ a7
= 233 +113 +71 + 277
= 694
694
? 同样方法的出 10001001对应的密文为,392。
? 这样，密文为,604,694,392。
2010-5-14 计算机算法设计与分析 49
背包公钥密码的例子
? C,解密过程：
? 收到密文后，分别先计算 50乘以密文值模 353，
然后再解超递增序列 (私钥 )背包问题 。
? 比如，对 604，先计算 50*604 mod 353 = 195
? 然后解超递增序列 {1,2,5,9,20,41,83,164}的
背包问题，易得 2 + 9 + 20 + 164 = 195,于是
对应的明文为,01011001。
? 同样的方法求得,694和 392的明文。
2010-5-14 计算机算法设计与分析 50
背包公钥密码的安全性
? Merkle悬赏 $100请人破译背包密码。
? 1982年,Adi Shamir攻破了使用一次循环的背
包密码，他得到了 $100。
? 然后,Merkle又悬赏 $1000请人破译多次循环
的背包密码。
? Ernie Brikelld用超级计算机在一小时内攻破了
有 100个重物,40次循环的背包算法。他得到
了 $1000。
? MH背包算法未能成为可以实用的密码系统。
2010-5-14 计算机算法设计与分析 51
感谢合作，谢谢！
敬请多提批评意见和宝贵建议。
周经野
