网络信息安全 课程第三讲 公钥密码算法主讲 段云所 副教授北京大学计算机系
1 密钥管理量的困难传统密钥管理 两两分别用一对密钥时 则n个用户需要C(n,2)=n(n-1)/2个密钥 当用户量增大时 密钥空间急剧增大 如:
n=100 时 C(100,2)=4,995
n=5000时 C(5000,2)=12,497,500
2 数字签名的问题传统加密算法无法实现抗抵赖的需求问题的提出公钥加密模型明文明文密文加密算法解密算法加密密钥解密密钥
1 什么是公钥密码体制
公钥密码又称为双钥密码和非对称密码 是1976年由Diffie和
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
单向陷门函数是满足下列条件的函数f
(1)给定x 计算y=f(x)是容易的
(2)给定y,计算x使y=f(x)是困难的
(所谓计算x=f
-1
(Y)困难是指计算上相当复 无实 )
(3) 在 时,对给定的 y 相 的x 在则计算x使y=f(x)是容易的
1
*
,满足(1) (2)两条的称为单向函数 (3)条称为陷门 称为陷门
2
*,
当用陷门函数f 为加密函数时 f公
相当 公 加密密钥 时加密密钥 称为公 钥
为Pk f函数的 计 密 用 解密密钥
时 称为 密钥 为Sk 由 加密函数是公
的? x加密￠y=f(x) ￡?￥给函数的 计 当￡§currency1',?传￥ 由
计Sk fifl￡?解出x=f
-1
(y)
3
*
.单向陷门函数的 (2)条 –明 由· 的密文y=f(x)x是currency1?的
”算法
RSA(Rivest,Shamir,Adleman)
…‰ ECC,Eilliptic Curve Croptography)
算法代–
2 背包问题
”问题? 一`′为b的?”?`′分别为a
1
,a
2
,…a
n
的n
个?ˉ?定 ˙?ˉ的¨”相? ˙?ˉ中?出
个ˇ— 满 个?” 是 ˙?ˉ
求解
n
Σ a
i
x
i
=b
i=1
其中ai和b 是ˇ 数
”问题是 名的np 困难问题?—的求解方法
对2
n
中 a 实 上是currency1 的
MH背包公钥密码
”公钥密码
ˇ 数a
1
,a
2
,…a
n
为公钥 明文 为m=m
1
m
2
…m
n
用公钥加密问题c= a
1
m
1
+ a
2
m
2
+… +a
n
m
n.
明文c求明文m”问题
MH?”公钥密码
i-1
其?”?列a
1
,a
2
,…a
n
是由o 增?列b
1
,b
2
,…b
n,
b
i
> Σ b
j
)
j=1
MH(Merkle-Hellman) a
k
=wb
k
(mod m)?的 ￡a
1
,a
2
,…a
n
currency1
o 增?￠为o 增?列求解
3.Diffie-Hellman密钥交换算法
Diffie和Hellman在其? 的文?中 ￡给出?
密码的 是?给出 ˇ 上的公钥密码实
出一个 ˇ带陷门的单向函数 ￡ fi们给出单向函数的实 并且基 提出Diffie-Hellman密钥交 算法
个算法是基?限域中计算离散对数的困难 问题之上
F为?限域 g F是F的乘法群F
*
=F\{0}=<g> 并且对
ˇ 数x 计算g
x
是容易的 是 g和y求x使y= g
x
是计算上几乎currency1 的 一问题称为?限域F上的离散对数问题 公钥密码学中使用最广泛的?限域为素域F
P
.
对Diffie-Hellman密钥交 协议? Alice和Bob协商
—一个大素数p 和大的 数g 1<g<p p和g无须 密
为网络上的所?用户共享当Alice和Bob要 密? 时 fi们?按如下步骤来做
(1)Alice? 大的随机数x 并计算 X=g
x
(mod P)
(2)Bob? 大的随机数x′ 并计算 X ′ = gx ′(mod P)
(3)Alice X传￥给Bob Bob X ′传￥给Alice
(4)Alice计算K=(X ′)
X
(mod P);Bob计算K ′ X) X ′(mod P),
易见 K=K ′′′ =g
xx ′′′
(mod P)
由(4) Alice和Bob?相?的 密值K 双方?K 为加解密钥?传统对称密钥算法 密?
Diffie-Hellman密钥交 算法美国和加拿大的专
4 RSA公钥算法
RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的 见Communitions of the ACM,Vol.21.No.2,Feb,1978,
PP.120-126)该算法的数学基础是初?数论中的Euler 欧拉)定理 并建立在大 数因子的困难 之上欧拉定理
– 1 Z/(n –示为Z
n
其中n=pq; p,q为素数且相异
Z*
n
≡{g Zn|(g,n)=1} 易见Z*
n
为? (n)阶的乘法群 且?
g
(n)
≡1(mod n)? (n)=(p-1)(q-1).
– 2 数g和n互素 则
g
(n)
≡1(mod n)
其中? (n)为比n小?n互素的ˇ 数个数,称为n的欧拉函数
RSA密码体制? 如下首先 明文空间P 密文空间C=Zn
A.密钥的生￠
择p,q p,q为互异素数 计算n=p*q,? (n)=(p-1)(q-1),?择
数e使(? (n),e)=1,1<e<? (n)),计算d,使d=e
-1
(mod? (n))),公钥
Pk={e,n};私钥Sk={d,p,q}
当0<M<n时,M
(n)
=1(mod n)fl￡?
M
K? (n)+1
≡M(mod n),ed ≡ 1 (mod? (n)),易见(M
e
)
d
≡ M(mod n)
B.加密(用e,n)
明文 M<n 密文 C=M
e
(mod n).
C.解密(用d,p,q)
密文 C 明文 M=C
d
mod n)
1
*
,加密和解密是一对逆运算
2
*
,对 0<M<n时 (M,n) 1 则M为p或q的 数倍? M=cp 由(cp,q)=1?
M
(q)
≡ 1(mod q) M
(q)? (p)
≡ 1(mod q)
M
(q)
= 1+kq 对其两边?乘M=cp?
M
(q) 1
=M+kcpq=M+kcn 是
M
(q) 1
≡ M(mod n)
子 Bob?择?p=101和q 113 n=11413,
(n)=100 112 11200 ￡ 11200 2
6
5
2
7 一个
ˇ 数e 用 加密指数 当且 当ecurrency1 被2 5 7所
除 事实上 Bobcurrency1会分解 (n) 是用辗转相除法 欧式算法 来求 e 使 e,(n)=1)? Bob?
择?e=3533 用辗转相除法 求
d=e
-1
≡ 6597(mod 11200),是Bob的解密密钥d=6597.
Bob在一个目录中公 n=11413和e=3533,现? Alice?发
￥明文9726给Bob 她计算
9726
3533
(mod 11413)=5761
且在一个?上发￥密文5761 当Bob接收?密文5761时
fi用fi的 密解密指数 私钥 d 6597解密
5761
6597
mod 11413)=9726
RSA的',是基 加密函数e
k
(x)=x
e
(mod n)是一个单向函数 所?对的 来说求逆计算currency1? Bob
解密的陷门是分解n=pq? (n)=(p-1)(q-1) 用欧氏算法解出解密私钥d.
RSA密码体制的实现实现的步骤如下 Bob为实现
(1)Bob寻 出两个大素数p和q
(2)Bob计算出n=pq和? (n)=(p-1)(q-1).
(3)Bob?择一个随机数e(0<e<? (n)) 满足 e? (n) 1
(4)Bob使用辗转相除法计算d=e
-1
(mod? (n))
(5)Bob在目录中公 n和e 为她的公 钥密码分析 攻击RSA体制的关键点在 如 分解n 分解￠功使n=pq 则?算出 (n) p-1)(q-1) ￡?由公
的e 解出 密的d
是要求 使RSA',p?q必为足够大的素数 使分析?办法在多项式时间 n分解出来 建议?择
p和q大 是100 的?制素数 n的`′要求 是
512比 EDI攻击 使用的RSA算法中 定n的`′为
512 1024比 之间 必须是128的倍数 国 数字签名 ISO/IEC 9796中 定n的`′ 512比
为?抵抗现?的 数分解算法 对RSA n的素因子
p和q?如下要求
(1)|p-q| 大? p和q的`′相?
(2)p-1 和q-1分别?大素因子p
1
和q
1
(3)P
1
-1和q
1
-1分别?大素因子p
2
和q
2
(4)p+1和q+1分别?大素因子p
3
和q
3
为?提 加密 ′? e为 定的小 数 如EDI
国 中 定e 2
16
1 ISO/IEC9796中 e
3 时加密 ′一 比解密 ′ 10倍?上下 加解密算 运算 个运算 要是 n的求
运算 名的,方-和-乘法”方法 计算x
c
(mod n)的
乘法的数目 小? 多为2l?的l是指数c的?制–
示比 数 n制 式–示?k比
k=[log
2
n]+1 由l k x
c
(mod n) 在o(k
3
)时间
￠
方 和 乘法算法指数c制 式–示为
c=
t-1
c
i
2
i
=c
0
+c
1
2+…+c
t-1
2
t-1
c
i
{0,1}
i=0
X
c
=x
c0
x
2
)
c1
… (x
2
t
-1
)
c
t-1
计算 x
2
=xx
x
4
=x
2
2
=x
2
x
2
.
.
.
x
2
t
-1
=x
2
t
-
2
*x
2
t
-
2
X
c
计算 ˙c
i
=1对 的x
2
i
,乘在一? x
c
多用?t-1￠乘法 给出计算x
c
(mod n)算法 ￡
A=x
c
c=c
0
+c
1
2+..+c
t-1
2
t-1
= [c
t-1
,....,c
1
,c
0
]
2
t-1￠乘法
X,[c
t-1
,..,c
1
,c
0
]
S x
i 1
C
0
=1?
A 1
A x
yn
S s s
Ci=1?
A A S
i= t-1?
i=i+1
A
￥?
y
n
ny
5.椭圆曲线密码学椭圆曲线有关的基本概念
(1) 无§currency1'素 无§currency1点 无§currency1¨
上 两相异¨ 的,关相交和?两?
无§currency1点 是两?currency1?关?统一
AB L
1
L
2
L
1
¨ AP由AB?fiA点fl逆时 方向转
– P为AP?L
1
的交点
L
2
L
1
P
B
A
P
Q
Q= BAP π /2 AP L
2
L
1
上?一点P?为L
2
和L
1
的交点 称之为无§
currency1点
¨ L1上的无§currency1点一个因为§A点一条? L
1
的¨ L
2
两¨
的交点一个
￥论
1
*
,上一·相互?的¨?公共的无§currency1点为?无§currency1点相 别?来 上的点?做
点
2
*
,上 相交的两¨ L
1
,L
2
currency1?的无§currency1点
因? 则L
1
和L
2
公共的无§currency1点P 则§两相异点A和P?相异两¨?公理相?”
3
*
.,体无§currency1点?￠一条无§currency1¨
欧式 …加上无§currency1点和无§currency1¨ fl￡?￠‰
(2)?￠
解析几 中 用代数的方法 欧氏空间 的 法?广 ` 上 建立 `
上两相异¨ L
1
,L
2
其方 分别为
L
1
,a
1
x+b
1
y+c
1
=0
L
2
,a
2
x+b
2
y+c
2
=0
A
L
1
L
2
P
其中a
1
,b
1
currency1?时为0 a
2
,b
2
currency1?时为0
D= a
1
b
1
D
x
= b
1
c
1
D
y
= c
1
a
1
a
2
b
2
b
2
c
2
c
2
a
2
D 0 则两¨ L
1
,L
2
相交 一 点P(x,y) 其 为
x=D
x
/D y=D
y
/D.
·解 –为 x/D
x
=y/D
y
=1/D
( 定 分′D
x
D
y
为0时 对 的分子 要为0
上 –示为 D
x
D
y
D).
D=0 则L
1
L
2
时L
1
和L
2
交 一个无§currency1点P
个点P 用§?点O且? L
2
的一条¨ L来指出fi
的方向 条¨ L的方 ˉ是 a
2
x+b
2
y=0.
为 点和无§currency1点的 统一?来 点的 用
X Y Z)–示 X Y Zcurrency1?时为0 且对 点
x y)来说?Z 0 x=X/Z y=Y/Z 是?
i.e.
X / Dx = Y / Dy = Z / D
—的 X,Y,Z),对 无§currency1点则?Z=0
￠立
a),实数p 0 则(pX,pY,pZ)? X,Y,Z)–示?一个点实 上用 X:Y:Z)–示 3个分量中两个是˙立的 ¨的 ˉ?
￠
i.e.
DD
Z
Y
D
Z
X
yx
1
==
b),?欧氏¨ L?在 ¨?Oxy上的方 为
ax+by+c=0
则L上 一 点(x,y)的?￠ 为(X,Y,Z)
Z 0
代?
aX+bY+cZ=0
给L…加的无§currency1点的 (X,Y,Z) 满足
aX+bY=0
Z=0; 上无§currency1¨ 方 fl￡为
Z=0
!!
(3) 域上的?…‰
K为域 K上的? P
2
(K)是一˙ 的?
{(X:Y:Z)}下 的Weierstrass方 (￠数为3的?
￠方 )
Y
2
Z+a
1
XYZ+a
3
YZ
2
=X
3
+a
2
X
2
z+a
4
XZ
2
+a
6
Z
3
(其中?数a
i
K 或a
i
K为K的代数ˇ域
Weierstrass方 被称为— 的或非 异的是指对所?
下方 的‰ 点P=(X:Y:Z) P
2
(K)来说
F(X,Y,Z)=Y
2
Z+a
1
XYZ+a
3
YZ
2
-X
3
-a
2
X
2
Z-a
4
XZ
2
-a
6
Z
3
=0
在P点的 个 数 之中?一个currency1为
0?称 个方 为 异的
…‰ E
的定
…‰ E是一个— 的Weierstrass方 在P
2
(K)中的
,解?
Y
2
Z+a
1
XYZ+a
3
YZ
2
=X
3
+a
2
X
2
Z+a
4
XZ
2
+a
6
Z
3
a) 在?…‰ E上?一个点 称之为无§currency1点 (0:1:0)
用 –示
Z
F
Y
F
X
F
,,
b) 用非?￠ 的 式来–示?…‰ 的Weierstrass
方,
x=X/Z y=Y/Z 是?方 转 为
y
2
+a
1
xy+a
3
y=x
3
+a
2
x
2
+a
4
x+a
6
(1)
时?…‰ Eˉ是方 1)在‰ P
2
(K)上的
,点解 加一个无§currency1点 ·￠的?
c) a
1
,a
2
,a
3
,a
4
,a
6
K 时?…‰ E被称为定 在K上用E/K–示 如 E 被限定在K上 E的K——?
理点? –示为E(K)?为E中的“体?理 点的
加无§currency1点,
(4)实域R上的?…‰
K=R 时的?…‰ –为 上的? ‰ 上的点 加无§currency1点实域R上?…‰ 的点的加法运算法则
L P
2
(R)为一条¨ 因为E的方 是 ￠的所?L?E在P
2
(R)? 个交点 为P,Q,R
如 L?E相 P,Q,R?currency1是相异的 按下
方式定 E上运算⊕
P,Q E L为 接P,Q的¨ P=Q 则L
§P点的 R为L?E的 一个交点 接
R?无§currency1点的¨ L 则L?E的 一个交点定
为P ⊕ Q
P
Q
P=Q
L
L
L
L
(P⊕Q) ⊕R=
T⊕T=
(P=Q=R)
P⊕Q
P⊕Q
R
R
T
上 的实? 为?…‰ y
2
=x
3
-x的一 来fl对 体‰
的 对运算? 体一˙
P=(x
1
,y
1
) Q=(x
2
,y
2
) P⊕Q=(x
3
,y
3
),
由P⊕Q的定 y= x+ 为?§P,Q两点¨ L的方
算出
=( y
2
-y
1
)/(x
2
-x
1
),=y
1
- x
1
易见 ¨ L上的一个点 x,x+ )是在?…‰ E上当且 当( x+ )
2
= x
3
–x
P⊕Q=(x
1
,y
1
) ⊕(x
2
,y
2
)=(x
3
,y
3
) =(x3,-( x
3
+ ))
其中 x
3
=
2
-x
1
-x
2
=((y
2
-y
1
) / (x
2
-x
1
) )
2
-x
1
-x
2
y
3
=-y
1
+((y
2
-y
1
)/(x
2
-x
1
))(x
1
-x
3
)
当P=Q时 P⊕Q= x
3
y
3
算
x
3
=((3x
1
2
-1)/2y
1
)
2
-2x
1; y
3
= -y
1
+((3x
1
2
-1)/2y
1
)(x
1
-x
3
)
a) 如 ¨ L?E相交? 点P,Q,R(currency1一定相异
(P⊕Q)⊕R= (?中 见
b) 给P E,P ⊕ =P ( 时 Q= 易见L=L )
c) 给P,Q E? P ⊕ Q =Q ⊕ P
d) P E-P E使P ⊕ -P=
e) 给P,Q,R E?(P ⊕ Q) ⊕ R= P ⊕(Q ⊕ R)
a上所 E对⊕运算 ￠一个Abel群
f) 上 则? 域上 别是?限域上?定
…‰ 是定 在?限域F
q
上 q=p
m
)
E(F
q
)={(x,y) F
q
F
q
| y
2
+a
1
xy+a
3
y=x
3
+a
2
x
2
+a
4
x+a
6
}
{ }
对“⊕,￠一个群 为Abel群有限域上椭圆曲线的⊕运算
F
q
–示q个'素的?限域 用E(F
q
)–示定 在F
q
上的一个?…‰ E
定理1.(Hass定理) E(F
q
)的点数用
#
E(F
q
)–示 则
|
#
E(F
q
)-q-1| 2q
1/2
(1) F
p
素域 p为素数 上?…‰
p>3 a,b F
p
满足4a
3
+27b
2
0 由 数a和b定
的F
p
上的一个?…‰ 方 为
y
2
=x
3
+ax+b (2)
的所?解(x,y) (x∈F
p
y∈F
p
)?一个称为“无§currency1
点” 为 的'素·￠的? 为E(F
p
) 由Hass定理
p+1-2p
1/2 #
E(F
p
) p+1+2p
1/2
E(F
p
)对 下 的加法 则 且对加法⊕ ￠
一个Abel群
(i) ⊕ = 单 '素
(ii) (x,y) ⊕ =(x,y),给(x,y) E(F
p
)
(iii) (x,y) ⊕(x,-y)= 给(x,y) E(F
p
),点(x,y)的逆'
为(x,-y).
(iv) (x
1
,y
1
),(x
2
,y
2
)为E(F
p
)中非互逆' 则
(x
1
,y
1
) ⊕(x
2
,y2)=(x
3
,y
3
),其中
x
3
=
2
-2x
1
y
3
= (x
1
-x
3
)-y
1
且 =(y
2
-y
1
)/(x
2
-x
1
) 3
(v) 倍点运算 则
(x
1
,y
1
) E(F
p
),y
1
0 则2(x
1
,y
1
)=(x
3
,y
3
) 其中
x
3
=
2
-2x
1
,y
3
= (x
1
-x
3
)-y
1
=(3x
1
2
+a)/(2y
1
) (4)
#
E(F
p
)=p+1 ‰ E(F
p
)称为o 异的?则称为非o 异的
子 F
23
上的一个?…‰
y
2
=x
3
+x+1是F
23
上的一个方 (a=b=1) 则该?…‰
方 在F
23
上的解为(y
2
=x
3
+x+1的点)
(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)
群E(F
23
)?28个点,无§currency1点
(2) F
2
m上的?…‰
F
2
m上由 数a,b F
2
m b 0定 的一个非o 异?
…‰ E(F
2
m)是方
y
2
+xy=x
3
+ax
2
+b (5)
的解? (x,y) 其中x,y F
2
m?
E(F2m)的加法 则如下
(i) + =
(ii) 给(x,y) E(F
2
m) 则(x,y) ⊕ =(x,y)
(iii) 给(x,y) E(F
2
m) 则(x,y)+(x,x+y)=
点(x,y)的逆为(x,x+y).
(iv) 两个相异且currency1互逆的点的加法 则
(x
1
,y
1
),(x
2
,y
2
) E(F
2
m)且?x
1
x
2
则
(x
1
,y
1
)⊕(x
2
,y
2
)=(x
3
,y
3
) 其中
x
3
=
2
+ +x
1
+x
2
+a
y
3
= (x
1
+x
3
)+x
3
+y
1
.
其中 = (y
2
+y
1
)/(x
2
+x
1
)
(v) 倍点 则
(x
1
,y
1
) E(F
2
m) 其中x
1
0 则
2(x
1
,y
1
)=(x
3
,y
3
) 其中
x
3
=
2
+ +a,y
3
=x
1
2
+( +1)x
3
,? =(x
1
+y
1
/x
1
)
易见 群E(F
2
m)为Abel群
F
2
4上的一个?…‰
f(x)=x
4
+x+1为F
2
上的一个currency1 多项式 易见
F
2
4=F
2
[x] / (f(x)) = {(k
0
,k
1
,k
2
,k
3
) |
(k
0
,k
1
,k
2
,k
3
)=k
0
+k
1
+k
2
2
+k
3
3
为f(x)的?点
k
i
F
2
}
定F
2
4
上的非o 异?…‰?下 方 定
y
2
+xy=x
3
+
4
x
2
+1 f( )=0
方 –为
(1000)y
2
+ (1000)xy = (1000)x
3
+ (1100)x
2
+(1000)
椭圆曲线密码体制
1985年 N,Koblitz和V,Miller分别˙立提出
…‰ 密码体制(ECC) 其fl?ˉ是定 在?…‰ 点群上的离散对数问题的难解
1 E(F
q
)对点的“⊕”运算 ￠一个Abel群
p E(F
q
) p的?o 大 使
p⊕ p ⊕…… ⊕ p= (共?t个p相加
￠立的最小ˇ 数t t 大
(t = p的?o –示为 (p)=t)
并且对Q E(Fq) 定? 个ˇ 数m使
Q=m·p=p ⊕ …… ⊕ p (共?t个p相加)
定
m=
p
Q
(m为?p为 Q的对数
…‰ 上的点 ￠的群E(F
q
) 相关?的离散对数问题是难?理的
2 建立?…‰ 密码体制
基域F
q
F
q
的?…‰ 体给定为 定的 式在E(F
q
)中?一个?o 大的点 如一个点P=(x
p
,y
p
)
的?o为一个大的素数n (P)=n(素数)
在 个密码体制中 体的‰?点P和?的n
是公 密码体制的 式 用EIGamal体制 是,
比§来
a)密钥的生￠
Bob(使用下列计算
i)在 间[1,n-1]中随机? 一个 数d
ii) 计算点Q:=dP (d个P相⊕
iii) Bob公 fl?的公 密钥—— (E(F
q
),p,n,Q)
iv) Bob的私钥为 数d
Alice要发￥ m给Bob Alice?
i) Bob的公钥(E(F
q
),p,n,Q),
ii) m–示￠一个域'素m F
q
,
iii) 在 间[1 n-1]? 一个随机数k,
iv) fl?Bob的公钥计算点(x
1
,y
1
):=kP(k个P相⊕
v) 计算点(x
2
,y
2
):=kQ,如 x
2
=0,则 iii)步
.
) 计算C:=m·x2
) 传￥加密数?(x
1
,y
1
,C)给Bob
b) Bob的解密§
Bob收?Alice的密文(x
1
,y
1
,C)
i) 使用私钥d 计算点(x
2
y
2
):=d(x
1
,y
1
) 计算F
q
中x
2
-1
=?
Ii)?§计算m:=C·x
2
-1
复出明文数?m
101681200001200
107821000600
10365120320
10121024160
MIPS-年RSA密钥`′ECC密钥`′m
ECC和RSA 比?
2304128
1792112
51264
38456
RSA密钥`′
(bit)
DES密钥`′
(bit)
DES和RSA 比?(′
1 在使用RSA公钥?统中 如 ·?发￥给其fi用户的密文C=10,用户的公钥为e=5,n=35,问明文的 容是
2一个 用 数q=11,? a=2的Diffie_Hellman方案
1 如 用户A的公钥为Y
A
=9,则A的私钥X
A
是多
2 如 用户B的公钥为Y
B
=3,则共享的密钥K是多
1 密钥管理量的困难传统密钥管理 两两分别用一对密钥时 则n个用户需要C(n,2)=n(n-1)/2个密钥 当用户量增大时 密钥空间急剧增大 如:
n=100 时 C(100,2)=4,995
n=5000时 C(5000,2)=12,497,500
2 数字签名的问题传统加密算法无法实现抗抵赖的需求问题的提出公钥加密模型明文明文密文加密算法解密算法加密密钥解密密钥
1 什么是公钥密码体制
公钥密码又称为双钥密码和非对称密码 是1976年由Diffie和
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
单向陷门函数是满足下列条件的函数f
(1)给定x 计算y=f(x)是容易的
(2)给定y,计算x使y=f(x)是困难的
(所谓计算x=f
-1
(Y)困难是指计算上相当复 无实 )
(3) 在 时,对给定的 y 相 的x 在则计算x使y=f(x)是容易的
1
*
,满足(1) (2)两条的称为单向函数 (3)条称为陷门 称为陷门
2
*,
当用陷门函数f 为加密函数时 f公
相当 公 加密密钥 时加密密钥 称为公 钥
为Pk f函数的 计 密 用 解密密钥
时 称为 密钥 为Sk 由 加密函数是公
的? x加密￠y=f(x) ￡?￥给函数的 计 当￡§currency1',?传￥ 由
计Sk fifl￡?解出x=f
-1
(y)
3
*
.单向陷门函数的 (2)条 –明 由· 的密文y=f(x)x是currency1?的
”算法
RSA(Rivest,Shamir,Adleman)
…‰ ECC,Eilliptic Curve Croptography)
算法代–
2 背包问题
”问题? 一`′为b的?”?`′分别为a
1
,a
2
,…a
n
的n
个?ˉ?定 ˙?ˉ的¨”相? ˙?ˉ中?出
个ˇ— 满 个?” 是 ˙?ˉ
求解
n
Σ a
i
x
i
=b
i=1
其中ai和b 是ˇ 数
”问题是 名的np 困难问题?—的求解方法
对2
n
中 a 实 上是currency1 的
MH背包公钥密码
”公钥密码
ˇ 数a
1
,a
2
,…a
n
为公钥 明文 为m=m
1
m
2
…m
n
用公钥加密问题c= a
1
m
1
+ a
2
m
2
+… +a
n
m
n.
明文c求明文m”问题
MH?”公钥密码
i-1
其?”?列a
1
,a
2
,…a
n
是由o 增?列b
1
,b
2
,…b
n,
b
i
> Σ b
j
)
j=1
MH(Merkle-Hellman) a
k
=wb
k
(mod m)?的 ￡a
1
,a
2
,…a
n
currency1
o 增?￠为o 增?列求解
3.Diffie-Hellman密钥交换算法
Diffie和Hellman在其? 的文?中 ￡给出?
密码的 是?给出 ˇ 上的公钥密码实
出一个 ˇ带陷门的单向函数 ￡ fi们给出单向函数的实 并且基 提出Diffie-Hellman密钥交 算法
个算法是基?限域中计算离散对数的困难 问题之上
F为?限域 g F是F的乘法群F
*
=F\{0}=<g> 并且对
ˇ 数x 计算g
x
是容易的 是 g和y求x使y= g
x
是计算上几乎currency1 的 一问题称为?限域F上的离散对数问题 公钥密码学中使用最广泛的?限域为素域F
P
.
对Diffie-Hellman密钥交 协议? Alice和Bob协商
—一个大素数p 和大的 数g 1<g<p p和g无须 密
为网络上的所?用户共享当Alice和Bob要 密? 时 fi们?按如下步骤来做
(1)Alice? 大的随机数x 并计算 X=g
x
(mod P)
(2)Bob? 大的随机数x′ 并计算 X ′ = gx ′(mod P)
(3)Alice X传￥给Bob Bob X ′传￥给Alice
(4)Alice计算K=(X ′)
X
(mod P);Bob计算K ′ X) X ′(mod P),
易见 K=K ′′′ =g
xx ′′′
(mod P)
由(4) Alice和Bob?相?的 密值K 双方?K 为加解密钥?传统对称密钥算法 密?
Diffie-Hellman密钥交 算法美国和加拿大的专
4 RSA公钥算法
RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的 见Communitions of the ACM,Vol.21.No.2,Feb,1978,
PP.120-126)该算法的数学基础是初?数论中的Euler 欧拉)定理 并建立在大 数因子的困难 之上欧拉定理
– 1 Z/(n –示为Z
n
其中n=pq; p,q为素数且相异
Z*
n
≡{g Zn|(g,n)=1} 易见Z*
n
为? (n)阶的乘法群 且?
g
(n)
≡1(mod n)? (n)=(p-1)(q-1).
– 2 数g和n互素 则
g
(n)
≡1(mod n)
其中? (n)为比n小?n互素的ˇ 数个数,称为n的欧拉函数
RSA密码体制? 如下首先 明文空间P 密文空间C=Zn
A.密钥的生￠
择p,q p,q为互异素数 计算n=p*q,? (n)=(p-1)(q-1),?择
数e使(? (n),e)=1,1<e<? (n)),计算d,使d=e
-1
(mod? (n))),公钥
Pk={e,n};私钥Sk={d,p,q}
当0<M<n时,M
(n)
=1(mod n)fl￡?
M
K? (n)+1
≡M(mod n),ed ≡ 1 (mod? (n)),易见(M
e
)
d
≡ M(mod n)
B.加密(用e,n)
明文 M<n 密文 C=M
e
(mod n).
C.解密(用d,p,q)
密文 C 明文 M=C
d
mod n)
1
*
,加密和解密是一对逆运算
2
*
,对 0<M<n时 (M,n) 1 则M为p或q的 数倍? M=cp 由(cp,q)=1?
M
(q)
≡ 1(mod q) M
(q)? (p)
≡ 1(mod q)
M
(q)
= 1+kq 对其两边?乘M=cp?
M
(q) 1
=M+kcpq=M+kcn 是
M
(q) 1
≡ M(mod n)
子 Bob?择?p=101和q 113 n=11413,
(n)=100 112 11200 ￡ 11200 2
6
5
2
7 一个
ˇ 数e 用 加密指数 当且 当ecurrency1 被2 5 7所
除 事实上 Bobcurrency1会分解 (n) 是用辗转相除法 欧式算法 来求 e 使 e,(n)=1)? Bob?
择?e=3533 用辗转相除法 求
d=e
-1
≡ 6597(mod 11200),是Bob的解密密钥d=6597.
Bob在一个目录中公 n=11413和e=3533,现? Alice?发
￥明文9726给Bob 她计算
9726
3533
(mod 11413)=5761
且在一个?上发￥密文5761 当Bob接收?密文5761时
fi用fi的 密解密指数 私钥 d 6597解密
5761
6597
mod 11413)=9726
RSA的',是基 加密函数e
k
(x)=x
e
(mod n)是一个单向函数 所?对的 来说求逆计算currency1? Bob
解密的陷门是分解n=pq? (n)=(p-1)(q-1) 用欧氏算法解出解密私钥d.
RSA密码体制的实现实现的步骤如下 Bob为实现
(1)Bob寻 出两个大素数p和q
(2)Bob计算出n=pq和? (n)=(p-1)(q-1).
(3)Bob?择一个随机数e(0<e<? (n)) 满足 e? (n) 1
(4)Bob使用辗转相除法计算d=e
-1
(mod? (n))
(5)Bob在目录中公 n和e 为她的公 钥密码分析 攻击RSA体制的关键点在 如 分解n 分解￠功使n=pq 则?算出 (n) p-1)(q-1) ￡?由公
的e 解出 密的d
是要求 使RSA',p?q必为足够大的素数 使分析?办法在多项式时间 n分解出来 建议?择
p和q大 是100 的?制素数 n的`′要求 是
512比 EDI攻击 使用的RSA算法中 定n的`′为
512 1024比 之间 必须是128的倍数 国 数字签名 ISO/IEC 9796中 定n的`′ 512比
为?抵抗现?的 数分解算法 对RSA n的素因子
p和q?如下要求
(1)|p-q| 大? p和q的`′相?
(2)p-1 和q-1分别?大素因子p
1
和q
1
(3)P
1
-1和q
1
-1分别?大素因子p
2
和q
2
(4)p+1和q+1分别?大素因子p
3
和q
3
为?提 加密 ′? e为 定的小 数 如EDI
国 中 定e 2
16
1 ISO/IEC9796中 e
3 时加密 ′一 比解密 ′ 10倍?上下 加解密算 运算 个运算 要是 n的求
运算 名的,方-和-乘法”方法 计算x
c
(mod n)的
乘法的数目 小? 多为2l?的l是指数c的?制–
示比 数 n制 式–示?k比
k=[log
2
n]+1 由l k x
c
(mod n) 在o(k
3
)时间
￠
方 和 乘法算法指数c制 式–示为
c=
t-1
c
i
2
i
=c
0
+c
1
2+…+c
t-1
2
t-1
c
i
{0,1}
i=0
X
c
=x
c0
x
2
)
c1
… (x
2
t
-1
)
c
t-1
计算 x
2
=xx
x
4
=x
2
2
=x
2
x
2
.
.
.
x
2
t
-1
=x
2
t
-
2
*x
2
t
-
2
X
c
计算 ˙c
i
=1对 的x
2
i
,乘在一? x
c
多用?t-1￠乘法 给出计算x
c
(mod n)算法 ￡
A=x
c
c=c
0
+c
1
2+..+c
t-1
2
t-1
= [c
t-1
,....,c
1
,c
0
]
2
t-1￠乘法
X,[c
t-1
,..,c
1
,c
0
]
S x
i 1
C
0
=1?
A 1
A x
yn
S s s
Ci=1?
A A S
i= t-1?
i=i+1
A
￥?
y
n
ny
5.椭圆曲线密码学椭圆曲线有关的基本概念
(1) 无§currency1'素 无§currency1点 无§currency1¨
上 两相异¨ 的,关相交和?两?
无§currency1点 是两?currency1?关?统一
AB L
1
L
2
L
1
¨ AP由AB?fiA点fl逆时 方向转
– P为AP?L
1
的交点
L
2
L
1
P
B
A
P
Q
Q= BAP π /2 AP L
2
L
1
上?一点P?为L
2
和L
1
的交点 称之为无§
currency1点
¨ L1上的无§currency1点一个因为§A点一条? L
1
的¨ L
2
两¨
的交点一个
￥论
1
*
,上一·相互?的¨?公共的无§currency1点为?无§currency1点相 别?来 上的点?做
点
2
*
,上 相交的两¨ L
1
,L
2
currency1?的无§currency1点
因? 则L
1
和L
2
公共的无§currency1点P 则§两相异点A和P?相异两¨?公理相?”
3
*
.,体无§currency1点?￠一条无§currency1¨
欧式 …加上无§currency1点和无§currency1¨ fl￡?￠‰
(2)?￠
解析几 中 用代数的方法 欧氏空间 的 法?广 ` 上 建立 `
上两相异¨ L
1
,L
2
其方 分别为
L
1
,a
1
x+b
1
y+c
1
=0
L
2
,a
2
x+b
2
y+c
2
=0
A
L
1
L
2
P
其中a
1
,b
1
currency1?时为0 a
2
,b
2
currency1?时为0
D= a
1
b
1
D
x
= b
1
c
1
D
y
= c
1
a
1
a
2
b
2
b
2
c
2
c
2
a
2
D 0 则两¨ L
1
,L
2
相交 一 点P(x,y) 其 为
x=D
x
/D y=D
y
/D.
·解 –为 x/D
x
=y/D
y
=1/D
( 定 分′D
x
D
y
为0时 对 的分子 要为0
上 –示为 D
x
D
y
D).
D=0 则L
1
L
2
时L
1
和L
2
交 一个无§currency1点P
个点P 用§?点O且? L
2
的一条¨ L来指出fi
的方向 条¨ L的方 ˉ是 a
2
x+b
2
y=0.
为 点和无§currency1点的 统一?来 点的 用
X Y Z)–示 X Y Zcurrency1?时为0 且对 点
x y)来说?Z 0 x=X/Z y=Y/Z 是?
i.e.
X / Dx = Y / Dy = Z / D
—的 X,Y,Z),对 无§currency1点则?Z=0
￠立
a),实数p 0 则(pX,pY,pZ)? X,Y,Z)–示?一个点实 上用 X:Y:Z)–示 3个分量中两个是˙立的 ¨的 ˉ?
￠
i.e.
DD
Z
Y
D
Z
X
yx
1
==
b),?欧氏¨ L?在 ¨?Oxy上的方 为
ax+by+c=0
则L上 一 点(x,y)的?￠ 为(X,Y,Z)
Z 0
代?
aX+bY+cZ=0
给L…加的无§currency1点的 (X,Y,Z) 满足
aX+bY=0
Z=0; 上无§currency1¨ 方 fl￡为
Z=0
!!
(3) 域上的?…‰
K为域 K上的? P
2
(K)是一˙ 的?
{(X:Y:Z)}下 的Weierstrass方 (￠数为3的?
￠方 )
Y
2
Z+a
1
XYZ+a
3
YZ
2
=X
3
+a
2
X
2
z+a
4
XZ
2
+a
6
Z
3
(其中?数a
i
K 或a
i
K为K的代数ˇ域
Weierstrass方 被称为— 的或非 异的是指对所?
下方 的‰ 点P=(X:Y:Z) P
2
(K)来说
F(X,Y,Z)=Y
2
Z+a
1
XYZ+a
3
YZ
2
-X
3
-a
2
X
2
Z-a
4
XZ
2
-a
6
Z
3
=0
在P点的 个 数 之中?一个currency1为
0?称 个方 为 异的
…‰ E
的定
…‰ E是一个— 的Weierstrass方 在P
2
(K)中的
,解?
Y
2
Z+a
1
XYZ+a
3
YZ
2
=X
3
+a
2
X
2
Z+a
4
XZ
2
+a
6
Z
3
a) 在?…‰ E上?一个点 称之为无§currency1点 (0:1:0)
用 –示
Z
F
Y
F
X
F
,,
b) 用非?￠ 的 式来–示?…‰ 的Weierstrass
方,
x=X/Z y=Y/Z 是?方 转 为
y
2
+a
1
xy+a
3
y=x
3
+a
2
x
2
+a
4
x+a
6
(1)
时?…‰ Eˉ是方 1)在‰ P
2
(K)上的
,点解 加一个无§currency1点 ·￠的?
c) a
1
,a
2
,a
3
,a
4
,a
6
K 时?…‰ E被称为定 在K上用E/K–示 如 E 被限定在K上 E的K——?
理点? –示为E(K)?为E中的“体?理 点的
加无§currency1点,
(4)实域R上的?…‰
K=R 时的?…‰ –为 上的? ‰ 上的点 加无§currency1点实域R上?…‰ 的点的加法运算法则
L P
2
(R)为一条¨ 因为E的方 是 ￠的所?L?E在P
2
(R)? 个交点 为P,Q,R
如 L?E相 P,Q,R?currency1是相异的 按下
方式定 E上运算⊕
P,Q E L为 接P,Q的¨ P=Q 则L
§P点的 R为L?E的 一个交点 接
R?无§currency1点的¨ L 则L?E的 一个交点定
为P ⊕ Q
P
Q
P=Q
L
L
L
L
(P⊕Q) ⊕R=
T⊕T=
(P=Q=R)
P⊕Q
P⊕Q
R
R
T
上 的实? 为?…‰ y
2
=x
3
-x的一 来fl对 体‰
的 对运算? 体一˙
P=(x
1
,y
1
) Q=(x
2
,y
2
) P⊕Q=(x
3
,y
3
),
由P⊕Q的定 y= x+ 为?§P,Q两点¨ L的方
算出
=( y
2
-y
1
)/(x
2
-x
1
),=y
1
- x
1
易见 ¨ L上的一个点 x,x+ )是在?…‰ E上当且 当( x+ )
2
= x
3
–x
P⊕Q=(x
1
,y
1
) ⊕(x
2
,y
2
)=(x
3
,y
3
) =(x3,-( x
3
+ ))
其中 x
3
=
2
-x
1
-x
2
=((y
2
-y
1
) / (x
2
-x
1
) )
2
-x
1
-x
2
y
3
=-y
1
+((y
2
-y
1
)/(x
2
-x
1
))(x
1
-x
3
)
当P=Q时 P⊕Q= x
3
y
3
算
x
3
=((3x
1
2
-1)/2y
1
)
2
-2x
1; y
3
= -y
1
+((3x
1
2
-1)/2y
1
)(x
1
-x
3
)
a) 如 ¨ L?E相交? 点P,Q,R(currency1一定相异
(P⊕Q)⊕R= (?中 见
b) 给P E,P ⊕ =P ( 时 Q= 易见L=L )
c) 给P,Q E? P ⊕ Q =Q ⊕ P
d) P E-P E使P ⊕ -P=
e) 给P,Q,R E?(P ⊕ Q) ⊕ R= P ⊕(Q ⊕ R)
a上所 E对⊕运算 ￠一个Abel群
f) 上 则? 域上 别是?限域上?定
…‰ 是定 在?限域F
q
上 q=p
m
)
E(F
q
)={(x,y) F
q
F
q
| y
2
+a
1
xy+a
3
y=x
3
+a
2
x
2
+a
4
x+a
6
}
{ }
对“⊕,￠一个群 为Abel群有限域上椭圆曲线的⊕运算
F
q
–示q个'素的?限域 用E(F
q
)–示定 在F
q
上的一个?…‰ E
定理1.(Hass定理) E(F
q
)的点数用
#
E(F
q
)–示 则
|
#
E(F
q
)-q-1| 2q
1/2
(1) F
p
素域 p为素数 上?…‰
p>3 a,b F
p
满足4a
3
+27b
2
0 由 数a和b定
的F
p
上的一个?…‰ 方 为
y
2
=x
3
+ax+b (2)
的所?解(x,y) (x∈F
p
y∈F
p
)?一个称为“无§currency1
点” 为 的'素·￠的? 为E(F
p
) 由Hass定理
p+1-2p
1/2 #
E(F
p
) p+1+2p
1/2
E(F
p
)对 下 的加法 则 且对加法⊕ ￠
一个Abel群
(i) ⊕ = 单 '素
(ii) (x,y) ⊕ =(x,y),给(x,y) E(F
p
)
(iii) (x,y) ⊕(x,-y)= 给(x,y) E(F
p
),点(x,y)的逆'
为(x,-y).
(iv) (x
1
,y
1
),(x
2
,y
2
)为E(F
p
)中非互逆' 则
(x
1
,y
1
) ⊕(x
2
,y2)=(x
3
,y
3
),其中
x
3
=
2
-2x
1
y
3
= (x
1
-x
3
)-y
1
且 =(y
2
-y
1
)/(x
2
-x
1
) 3
(v) 倍点运算 则
(x
1
,y
1
) E(F
p
),y
1
0 则2(x
1
,y
1
)=(x
3
,y
3
) 其中
x
3
=
2
-2x
1
,y
3
= (x
1
-x
3
)-y
1
=(3x
1
2
+a)/(2y
1
) (4)
#
E(F
p
)=p+1 ‰ E(F
p
)称为o 异的?则称为非o 异的
子 F
23
上的一个?…‰
y
2
=x
3
+x+1是F
23
上的一个方 (a=b=1) 则该?…‰
方 在F
23
上的解为(y
2
=x
3
+x+1的点)
(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)
群E(F
23
)?28个点,无§currency1点
(2) F
2
m上的?…‰
F
2
m上由 数a,b F
2
m b 0定 的一个非o 异?
…‰ E(F
2
m)是方
y
2
+xy=x
3
+ax
2
+b (5)
的解? (x,y) 其中x,y F
2
m?
E(F2m)的加法 则如下
(i) + =
(ii) 给(x,y) E(F
2
m) 则(x,y) ⊕ =(x,y)
(iii) 给(x,y) E(F
2
m) 则(x,y)+(x,x+y)=
点(x,y)的逆为(x,x+y).
(iv) 两个相异且currency1互逆的点的加法 则
(x
1
,y
1
),(x
2
,y
2
) E(F
2
m)且?x
1
x
2
则
(x
1
,y
1
)⊕(x
2
,y
2
)=(x
3
,y
3
) 其中
x
3
=
2
+ +x
1
+x
2
+a
y
3
= (x
1
+x
3
)+x
3
+y
1
.
其中 = (y
2
+y
1
)/(x
2
+x
1
)
(v) 倍点 则
(x
1
,y
1
) E(F
2
m) 其中x
1
0 则
2(x
1
,y
1
)=(x
3
,y
3
) 其中
x
3
=
2
+ +a,y
3
=x
1
2
+( +1)x
3
,? =(x
1
+y
1
/x
1
)
易见 群E(F
2
m)为Abel群
F
2
4上的一个?…‰
f(x)=x
4
+x+1为F
2
上的一个currency1 多项式 易见
F
2
4=F
2
[x] / (f(x)) = {(k
0
,k
1
,k
2
,k
3
) |
(k
0
,k
1
,k
2
,k
3
)=k
0
+k
1
+k
2
2
+k
3
3
为f(x)的?点
k
i
F
2
}
定F
2
4
上的非o 异?…‰?下 方 定
y
2
+xy=x
3
+
4
x
2
+1 f( )=0
方 –为
(1000)y
2
+ (1000)xy = (1000)x
3
+ (1100)x
2
+(1000)
椭圆曲线密码体制
1985年 N,Koblitz和V,Miller分别˙立提出
…‰ 密码体制(ECC) 其fl?ˉ是定 在?…‰ 点群上的离散对数问题的难解
1 E(F
q
)对点的“⊕”运算 ￠一个Abel群
p E(F
q
) p的?o 大 使
p⊕ p ⊕…… ⊕ p= (共?t个p相加
￠立的最小ˇ 数t t 大
(t = p的?o –示为 (p)=t)
并且对Q E(Fq) 定? 个ˇ 数m使
Q=m·p=p ⊕ …… ⊕ p (共?t个p相加)
定
m=
p
Q
(m为?p为 Q的对数
…‰ 上的点 ￠的群E(F
q
) 相关?的离散对数问题是难?理的
2 建立?…‰ 密码体制
基域F
q
F
q
的?…‰ 体给定为 定的 式在E(F
q
)中?一个?o 大的点 如一个点P=(x
p
,y
p
)
的?o为一个大的素数n (P)=n(素数)
在 个密码体制中 体的‰?点P和?的n
是公 密码体制的 式 用EIGamal体制 是,
比§来
a)密钥的生￠
Bob(使用下列计算
i)在 间[1,n-1]中随机? 一个 数d
ii) 计算点Q:=dP (d个P相⊕
iii) Bob公 fl?的公 密钥—— (E(F
q
),p,n,Q)
iv) Bob的私钥为 数d
Alice要发￥ m给Bob Alice?
i) Bob的公钥(E(F
q
),p,n,Q),
ii) m–示￠一个域'素m F
q
,
iii) 在 间[1 n-1]? 一个随机数k,
iv) fl?Bob的公钥计算点(x
1
,y
1
):=kP(k个P相⊕
v) 计算点(x
2
,y
2
):=kQ,如 x
2
=0,则 iii)步
.
) 计算C:=m·x2
) 传￥加密数?(x
1
,y
1
,C)给Bob
b) Bob的解密§
Bob收?Alice的密文(x
1
,y
1
,C)
i) 使用私钥d 计算点(x
2
y
2
):=d(x
1
,y
1
) 计算F
q
中x
2
-1
=?
Ii)?§计算m:=C·x
2
-1
复出明文数?m
101681200001200
107821000600
10365120320
10121024160
MIPS-年RSA密钥`′ECC密钥`′m
ECC和RSA 比?
2304128
1792112
51264
38456
RSA密钥`′
(bit)
DES密钥`′
(bit)
DES和RSA 比?(′
1 在使用RSA公钥?统中 如 ·?发￥给其fi用户的密文C=10,用户的公钥为e=5,n=35,问明文的 容是
2一个 用 数q=11,? a=2的Diffie_Hellman方案
1 如 用户A的公钥为Y
A
=9,则A的私钥X
A
是多
2 如 用户B的公钥为Y
B
=3,则共享的密钥K是多
