2010-5-14 1
第五章 公钥密码
2010-5-14 2
公钥密码
? 数论简介
? 公钥密码体制的基本概念
? RSA算法
? 椭圆曲线密码体制
2010-5-14 3
数论简介
2010-5-14 4
离散对数
? 定理：设 a的阶为 m，则 ak≡1mod n 的充分必
要条件是 k是 m的倍数。
? 推论,a的阶整除 j(n)。
? 本原根,a的阶 m等于 j(n),a为 n的本原根。
? 如果 a是 n的本原根,a1,a2,...,a j(n)在模 n下互不
相同且与 n互素。
? 本原根不唯一。
? 并非所有元素都有本原根，仅有以下形式的整
数才有本原根,2,4,pa,2pa,p是奇素数
2010-5-14 5
离散对数
? 指标
? y=ax(a>0,a≠1) 的逆函数称为以 a为底的对
数，记为 x=logay
? 设 p为素数,a是 p的本原根，则 a0,a1,...,a p-1
产生 1到 p-1中所有值，且每个值只出现一次。
对任一 b∈{1,…,p-1}，都存在唯一的 i(1≤ i
≤ p)，使 b≡a i mod p。 i称为模 p下以 a为底 b
的指标，记为 i=inda,p(d)
2010-5-14 6
离散对数
? 指标的性质
1,inda,p(1)=0
2,inda,p(a)=1
3,inda,p(xy)=[inda,p(x)+ inda,p(y)] mod
j(p)
4,inda,p(yr)=[r× inda,p(y)] mod j(p)
后两个性质基于下列结论
若 az≡a q mod p,a和 p互素，则 z ≡q mod j (p)
2010-5-14 7
离散对数
? 设 p是素数,a是 p的本原根。对
b∈{1,…,p-1},有唯一的 i ∈{1,…,p-1},使
b≡a i mod p。称 i为模 p下以 a为底 b的离
散对数，记为
i ≡log ab (mod p)
? 已知 a,p,i,求 b比较容易，以及 a,b,p,求 i非
常困难
2010-5-14 8
公钥密码体制的基本概念
Basic Concept of Public Key
Cryptography
2010-5-14 9
公钥密码体制的原理
公钥体制 (Public key system) (Diffie和 Hellman,1976)
每个用户都有一对选定的密钥 (公钥 k1；私钥 k2),公开的
密钥 k1可以像电话号码一样进行注册公布 。
主要特点：
? 加密和解密能力分开
? 多个用户加密的消息只能由一个用户解读, （ 用于公共
网络中实现保密通信 ）
? 只能由一个用户加密消息而使多个用户可以解读 （ 可用
于认证系统中对消息进行数字签字 ） 。
? 无需事先分配密钥 。
2010-5-14 10
公钥体制加密
公钥体制加、解密 m=D (c)=DSKB (EPKB(m))
安全保障
?从公开钥 PKB和密文 c要推出明文 m或解密钥 SKB在计算上是
不可行的。
?由于任一用户都可用用户 B的公开钥 PKB 向他发送机密消息，
因而密文 c不具有认证性。
发送者 A 加密算法
PKB
密钥源
SKB
解密算法 接收者 B
密码分析员
m c m
m’
SK’B
2010-5-14 11
公钥密码认证体制
用户 A以自己的秘密钥 SkA对消息 m进行 A的专用变换
DSKA,A计算密文,c=DSKA(m)送给用户 B,B验证 c：
m=EPKA（ c） =EPKA(DSKA(m))
安全性：
由于 SkA 是保密的，其他人都不可能伪造密文 c，可用 A
的 公开钥解密时得到有意义的消息 m。因此可以验证消息
m来自 A而不是其他人，而实现了对 A所发消息的认证。
2010-5-14 12
公钥密码认证体制
发送者 A 加密算法
SKA
密钥源
PKA
解密算法 接收者 B
密码分析员
m c m
SK’A
2010-5-14 13
公钥保密和认证体制
为了要同时实现保密性和确证性，要采用双重加、
解密
保密 公开 保密 公开
用户 A D
S K A
E
P K B
D
S K B
E
P K A
用户 B
m m
保密
认证
2010-5-14 14
公钥密码应满足的要求
? 接收方 B产生密钥对在计算上是容易的
? 发送方 A用收方的公开钥对消息 m加密以产生密文 c
在计算上是容易的。
? 收方 B用自己的秘密钥对密文 c解密在计算上是容易
的。
? 敌手由密文 c和 B的公开密钥恢复明文在计算上是不
可行的。
? 敌手由密文 c和 B的公开密钥恢复秘密密钥在计算上
是不可行的
? 加解密次序可换，即 EPKB[DSKB(m)]=DSKB[EPKB(m)],
不是对任何算法都做此要求。
2010-5-14 15
单向函数
一个可逆函数 f,A?B,若它满足：
1o 对所有 x?A,易于计算 f(x)。
2o 对, 几乎所有 x?A”由 f(x)求 x“极为困难,, 以
至于实际上不可能做到, 则称 f为一单向 (One-
way)函数 。
? 定义中的, 易于计算, 是指函数值能在其输入
长度的多项式时间内求出, 即若输入长度为 n，
计算函数的时间是 na的倍数, a为一固定的常
数 。
? 若计算函数时间是 an的倍数, 则为不可能做到
的 。
2010-5-14 16
限门单向函数
? 单向函数是求逆困难的函数，而单向陷门函
数 (Trapdoor one-way function)，是在不知
陷门信息 下求逆困难的函数，当知道陷门信
息后，求逆是易于实现的。
? 限门单向函数是一族可逆函数 fk，满足
1,Y=fk(X)易于计算（当 k和 X已知）
2,X＝ f-1k(Y)易于计算（当 k和 Y已知）
3,X＝ f-1k(Y)计算上不可行（ Y已知但 k未知）
研究公钥密码算法就是找出合适的单向限门函数
2010-5-14 17
RSA算法
RSA Algorithm
2010-5-14 18
概况
? MIT 三 位 年 青 数 学 家 R.L.Rivest,
A.Shamir 和 L.Adleman[Rivest 等 1978,
1979]发现了一种用数论构造双钥的方法,
称作 MIT体制, 后来被广泛称之为 RSA体
制 。
? 它既可用于加密, 又可用于数字签字 。
? RSA算法的安全性基于数论中大整数分解
的困难性 。
2010-5-14 19
算法描述－密钥产生
? 独立地选取两大素数 p和 q(各 100～ 200位十进
制数字 )
? 计算 n=p× q,其欧拉函数值 j(n)=(p－ 1)(q－
1)
? 随机选一整数 e,1?e<j(n),gcd(j(n),e)=1
? 在模 j(n)下, 计算 e的有逆元 d=e -1 mod j(n)
? 以 n,e为公钥 。 秘密钥为 d。 (p,q不再需要,
可以销毁 。 )
2010-5-14 20
算法描述－加密和解密
? 加密
将明文分组, 各组对应的十进制数小于 n
c=me mod n
? 解密
m=cd mod n
2010-5-14 21
解密正确性证明
? cd mod n ≡ med mod n ≡ m1 modj(n) mod n ≡
mkj(n)+1 mod n
? m与 n互素, 由欧拉定理
mj(n)≡ 1 mod n,mkj(n)≡ 1 mod n,mkj(n)+1≡ m
mod n
? gcd(m,n) ≠1,m是 p的倍数或 q的倍数, 设 m=cp，
此时 gcd(m,q)=1,由欧拉定理, mj(q)≡ 1 mod
q,mkj(q)≡ 1 mod q,[mkj(q)] j(p)≡ 1 mod q
mkj(n)≡ 1 mod q,存在一整数 r，使 mkj(n)≡ 1＋
rq
两边同乘 m=cp,mkj(n)+1≡ m+rcpq=m+rcn,即
mkj(n)+1≡ m mod n
2010-5-14 22
RSA的安全性
? RSA的安全性是基于分解大整数的困难性假定
（尚未证明分解大整数是 NP问题 ）
? 如果分解 n=p× q,则立即获得 j(n)=(p－ 1)(q
－ 1),从而能够确定 e的模 j(n)乘法逆 d
? RSA-129历时 8个月被于 1996年 4月被成功分
解,RSA－ 130于 1996年 4月被成功分解
? 密钥长度应该介于 1024bit到 2048bit之间
? 由 n直接求 j(n)等价于分解 n
第五章 公钥密码
2010-5-14 2
公钥密码
? 数论简介
? 公钥密码体制的基本概念
? RSA算法
? 椭圆曲线密码体制
2010-5-14 3
数论简介
2010-5-14 4
离散对数
? 定理：设 a的阶为 m，则 ak≡1mod n 的充分必
要条件是 k是 m的倍数。
? 推论,a的阶整除 j(n)。
? 本原根,a的阶 m等于 j(n),a为 n的本原根。
? 如果 a是 n的本原根,a1,a2,...,a j(n)在模 n下互不
相同且与 n互素。
? 本原根不唯一。
? 并非所有元素都有本原根，仅有以下形式的整
数才有本原根,2,4,pa,2pa,p是奇素数
2010-5-14 5
离散对数
? 指标
? y=ax(a>0,a≠1) 的逆函数称为以 a为底的对
数，记为 x=logay
? 设 p为素数,a是 p的本原根，则 a0,a1,...,a p-1
产生 1到 p-1中所有值，且每个值只出现一次。
对任一 b∈{1,…,p-1}，都存在唯一的 i(1≤ i
≤ p)，使 b≡a i mod p。 i称为模 p下以 a为底 b
的指标，记为 i=inda,p(d)
2010-5-14 6
离散对数
? 指标的性质
1,inda,p(1)=0
2,inda,p(a)=1
3,inda,p(xy)=[inda,p(x)+ inda,p(y)] mod
j(p)
4,inda,p(yr)=[r× inda,p(y)] mod j(p)
后两个性质基于下列结论
若 az≡a q mod p,a和 p互素，则 z ≡q mod j (p)
2010-5-14 7
离散对数
? 设 p是素数,a是 p的本原根。对
b∈{1,…,p-1},有唯一的 i ∈{1,…,p-1},使
b≡a i mod p。称 i为模 p下以 a为底 b的离
散对数，记为
i ≡log ab (mod p)
? 已知 a,p,i,求 b比较容易，以及 a,b,p,求 i非
常困难
2010-5-14 8
公钥密码体制的基本概念
Basic Concept of Public Key
Cryptography
2010-5-14 9
公钥密码体制的原理
公钥体制 (Public key system) (Diffie和 Hellman,1976)
每个用户都有一对选定的密钥 (公钥 k1；私钥 k2),公开的
密钥 k1可以像电话号码一样进行注册公布 。
主要特点：
? 加密和解密能力分开
? 多个用户加密的消息只能由一个用户解读, （ 用于公共
网络中实现保密通信 ）
? 只能由一个用户加密消息而使多个用户可以解读 （ 可用
于认证系统中对消息进行数字签字 ） 。
? 无需事先分配密钥 。
2010-5-14 10
公钥体制加密
公钥体制加、解密 m=D (c)=DSKB (EPKB(m))
安全保障
?从公开钥 PKB和密文 c要推出明文 m或解密钥 SKB在计算上是
不可行的。
?由于任一用户都可用用户 B的公开钥 PKB 向他发送机密消息，
因而密文 c不具有认证性。
发送者 A 加密算法
PKB
密钥源
SKB
解密算法 接收者 B
密码分析员
m c m
m’
SK’B
2010-5-14 11
公钥密码认证体制
用户 A以自己的秘密钥 SkA对消息 m进行 A的专用变换
DSKA,A计算密文,c=DSKA(m)送给用户 B,B验证 c：
m=EPKA（ c） =EPKA(DSKA(m))
安全性：
由于 SkA 是保密的，其他人都不可能伪造密文 c，可用 A
的 公开钥解密时得到有意义的消息 m。因此可以验证消息
m来自 A而不是其他人，而实现了对 A所发消息的认证。
2010-5-14 12
公钥密码认证体制
发送者 A 加密算法
SKA
密钥源
PKA
解密算法 接收者 B
密码分析员
m c m
SK’A
2010-5-14 13
公钥保密和认证体制
为了要同时实现保密性和确证性，要采用双重加、
解密
保密 公开 保密 公开
用户 A D
S K A
E
P K B
D
S K B
E
P K A
用户 B
m m
保密
认证
2010-5-14 14
公钥密码应满足的要求
? 接收方 B产生密钥对在计算上是容易的
? 发送方 A用收方的公开钥对消息 m加密以产生密文 c
在计算上是容易的。
? 收方 B用自己的秘密钥对密文 c解密在计算上是容易
的。
? 敌手由密文 c和 B的公开密钥恢复明文在计算上是不
可行的。
? 敌手由密文 c和 B的公开密钥恢复秘密密钥在计算上
是不可行的
? 加解密次序可换，即 EPKB[DSKB(m)]=DSKB[EPKB(m)],
不是对任何算法都做此要求。
2010-5-14 15
单向函数
一个可逆函数 f,A?B,若它满足：
1o 对所有 x?A,易于计算 f(x)。
2o 对, 几乎所有 x?A”由 f(x)求 x“极为困难,, 以
至于实际上不可能做到, 则称 f为一单向 (One-
way)函数 。
? 定义中的, 易于计算, 是指函数值能在其输入
长度的多项式时间内求出, 即若输入长度为 n，
计算函数的时间是 na的倍数, a为一固定的常
数 。
? 若计算函数时间是 an的倍数, 则为不可能做到
的 。
2010-5-14 16
限门单向函数
? 单向函数是求逆困难的函数，而单向陷门函
数 (Trapdoor one-way function)，是在不知
陷门信息 下求逆困难的函数，当知道陷门信
息后，求逆是易于实现的。
? 限门单向函数是一族可逆函数 fk，满足
1,Y=fk(X)易于计算（当 k和 X已知）
2,X＝ f-1k(Y)易于计算（当 k和 Y已知）
3,X＝ f-1k(Y)计算上不可行（ Y已知但 k未知）
研究公钥密码算法就是找出合适的单向限门函数
2010-5-14 17
RSA算法
RSA Algorithm
2010-5-14 18
概况
? MIT 三 位 年 青 数 学 家 R.L.Rivest,
A.Shamir 和 L.Adleman[Rivest 等 1978,
1979]发现了一种用数论构造双钥的方法,
称作 MIT体制, 后来被广泛称之为 RSA体
制 。
? 它既可用于加密, 又可用于数字签字 。
? RSA算法的安全性基于数论中大整数分解
的困难性 。
2010-5-14 19
算法描述－密钥产生
? 独立地选取两大素数 p和 q(各 100～ 200位十进
制数字 )
? 计算 n=p× q,其欧拉函数值 j(n)=(p－ 1)(q－
1)
? 随机选一整数 e,1?e<j(n),gcd(j(n),e)=1
? 在模 j(n)下, 计算 e的有逆元 d=e -1 mod j(n)
? 以 n,e为公钥 。 秘密钥为 d。 (p,q不再需要,
可以销毁 。 )
2010-5-14 20
算法描述－加密和解密
? 加密
将明文分组, 各组对应的十进制数小于 n
c=me mod n
? 解密
m=cd mod n
2010-5-14 21
解密正确性证明
? cd mod n ≡ med mod n ≡ m1 modj(n) mod n ≡
mkj(n)+1 mod n
? m与 n互素, 由欧拉定理
mj(n)≡ 1 mod n,mkj(n)≡ 1 mod n,mkj(n)+1≡ m
mod n
? gcd(m,n) ≠1,m是 p的倍数或 q的倍数, 设 m=cp，
此时 gcd(m,q)=1,由欧拉定理, mj(q)≡ 1 mod
q,mkj(q)≡ 1 mod q,[mkj(q)] j(p)≡ 1 mod q
mkj(n)≡ 1 mod q,存在一整数 r，使 mkj(n)≡ 1＋
rq
两边同乘 m=cp,mkj(n)+1≡ m+rcpq=m+rcn,即
mkj(n)+1≡ m mod n
2010-5-14 22
RSA的安全性
? RSA的安全性是基于分解大整数的困难性假定
（尚未证明分解大整数是 NP问题 ）
? 如果分解 n=p× q,则立即获得 j(n)=(p－ 1)(q
－ 1),从而能够确定 e的模 j(n)乘法逆 d
? RSA-129历时 8个月被于 1996年 4月被成功分
解,RSA－ 130于 1996年 4月被成功分解
? 密钥长度应该介于 1024bit到 2048bit之间
? 由 n直接求 j(n)等价于分解 n
