公钥密码学1
Diffie-Hellman**交换协议
对称**加密需要通信双方有共享和保密的**，在公开的信道中，这些**无法安全的传送。对此，Diffie和Hellman提出了Diffie-Hellman**交换协议。这个协议可以使得通信双方在公开的信道中生成**，即便窃听敌手可以监听到整个过程，也无法知道**的任何信息，这种**交换协议是需要双方同时在线交互的。
原理：
但是，Diffie-Hellman协议无法抵抗中间人攻击。
公钥加密
ElGamal加密
其安全性基于判定性Diffie-Hellman问题的困难性。
1、生成
(
G
,
q
,
g
)
(G,q,g)
(G,q,g)，计算
h
=
g
x
h=g^x
h=gx。公钥为
(
G
,
q
,
g
,
h
)
(G,q,g,h)
(G,q,g,h)，私钥为
(
G
,
q
,
g
,
x
)
(G,q,g,x)
(G,q,g,x)
2、
c
=
<
g
y
,
h
y
⋅
m
>
=
<
c
1
,
c
2
>
c=<g^y,h^y·m>=<c_1,c_2>
c=<gy,hy⋅m>=<c1,c2>
3、
m
=
c
2
c
1
x
m=\frac{c_2}{{c_1}^x}
m=c1xc2
陷门函数
从集合
X
\mathbb{X}
X映射到集合
Y
\mathbb{Y}
Y，它定义为
3
3
3个算法，
(
G
，
F
，
F
−
1
)
(G，F，F^{-1})
(G，F，F−1)
G
(
)
G()
G()：会生成一对**对
(
s
k
,
p
k
)
(sk,pk)
(sk,pk)
F
(
p
k
,
⋅
)
F(pk,·)
F(pk,⋅)：
p
p
pk定义了一个从集合
X
\mathbb{X}
X到集合
Y
\mathbb{Y}
Y的特定函数
F
F
F
F
−
1
(
s
k
,
⋅
)
F^{-1}(sk,·)
F−1(sk,⋅)：
s
k
sk
sk定义了这个函数
F
F
F的逆，从集合
Y
\mathbb{Y}
Y到集合
X
\mathbb{X}
X
即，你可以使用
p
k
pk
pk计算
F
F
F在任意点的值，可以用
s
k
sk
sk计算
F
F
F的逆。"
F
−
1
(
s
k
,
F
(
p
k
,
x
)
)
=
x
F^{-1}( sk, F(pk, x) )=x
F−1(sk,F(pk,x))=x"
安全的陷门函数：如果
F
(
p
k
,
⋅
)
F(pk,·)
F(pk,⋅)是单向函数，那么
(
G
，
F
，
F
−
1
)
(G，F，F^{-1})
(G，F，F−1)是安全的。
RSA陷门置换
是一个函数，从集合
X
\mathbb{X}
X映射到集合
X
\mathbb{X}
X，它定义为
3
3
3个算法，
(
G
，
F
，
F
−
1
)
(G，F，F^{-1})
(G，F，F−1)
G
(
)
G()
G()：会生成一对**对
(
s
k
,
p
k
)
(sk,pk)
(sk,pk)
F
(
p
k
,
x
)
F(pk,x)
F(pk,x)：
p
k
pk
pk定义了一个从集合
X
\mathbb{X}
X到集合
X
\mathbb{X}
X的特定函数
F
F
F；"
R
S
A
(
x
)
=
x
e
RSA(x) = x^e
RSA(x)=xe"
F
−
1
(
s
k
,
y
)
F^{-1}(sk,y)
F−1(sk,y)："
F
−
1
(
s
k
,
y
)
=
y
d
;
y
d
=
R
S
A
(
x
)
d
=
x
e
d
=
x
k
ϕ
(
N
)
+
1
=
(
x
ϕ
(
N
)
)
k
⋅
x
=
x
F^{-1}(sk,y)=y^d;y^d=RSA(x)^d=x^{ed}=x^{k\phi(N)+1}=(x^{\phi(N)})^k·x=x
F−1(sk,y)=yd;yd=RSA(x)d=xed=xkϕ(N)+1=(xϕ(N))k⋅x=x"
如果函数
F
(
p
k
,
⋅
)
F(pk,·)
F(pk,⋅)事实上是一个单向函数，意味着它是容易计算的，但如果没有陷门（即私钥），是很难求逆的。
RSA加密
G
(
)
G()
G()：随机选择质数
p
p
p,
q
q
q，
N
=
p
q
N=pq
N=pq，选择
e
e
e,
d
d
d，使得
e
d
=
1
m
o
d
ϕ
(
N
)
ed=1~~mod~~\phi(N)
ed=1 mod ϕ(N)，然后输出
p
k
=
(
N
,
e
)
pk=(N,e)
pk=(N,e)，
s
k
=
(
N
,
d
)
sk=(N,d)
sk=(N,d)
E
(
p
k
,
m
)
E(pk,m)
E(pk,m)：在
Z
n
Z_n
Zn中随机选择
x
x
x，
y
←
R
S
A
(
x
)
=
x
e
y \leftarrow RSA(x)=x^e
y←RSA(x)=xe，
k
←
H
(
x
)
k \leftarrow H(x)
k←H(x)，输出
(
y
,
E
s
(
k
,
m
)
)
(y,E_s(k,m))
(y,Es(k,m))，其中，
H
H
H是将
Z
n
\mathbb{Z}_n
Zn映射到
K
\mathbb{K}
K的随机函数。
D
(
s
k
,
(
y
,
c
)
)
D(sk,(y,c))
D(sk,(y,c))：输出
D
s
(
H
(
R
S
A
−
1
(
y
)
)
,
c
)
=
m
D_s(H(RSA^{-1}(y)),c)=m
Ds(H(RSA−1(y)),c)=m
教科书式RSA加密（实际并不安全）
$pk=<N,e>
，
，
，sk=<N,d>$
加密：
c
=
m
e
m
o
d
N
c=m^e mod N
c=memodN
解密：
m
=
c
d
m
o
d
N
m=c^d mod N
m=cdmodN
PKCS 1–公钥密码学一号标准
PKCS1 v1.5（CPA安全，CCA不安全）
模式2表示加密，模式1表示签名
x
x
x为下图
c
←
R
S
A
(
x
)
=
x
e
c \leftarrow RSA(x)=x^e
c←RSA(x)=xe
c
d
=
x
c^d=x
cd=x
PKCS1 v1.5的不安全性导致新的方案——OAEP的出现