陷门置换定义
一个陷门置换族是一个PPT算法元组
(
G
e
n
,
S
a
m
p
l
e
,
E
v
a
l
,
I
n
v
e
r
t
)
(Gen,Sample,Eval,Invert)
(Gen,Sample,Eval,Invert)：
- PPT，运行步数是安全参数的多项式函数。
G e n ( l K ) Gen(l^{\mathcal{K}}) Gen(lK)是一个概率性算法，输入为安全参数 l K l^{\mathcal{K}} lK，输出为 ( i , t d ) (i,td) (i,td)，其中 i i i是定义域 D i D_i Di上的一个置换 f i f_i fi的标号（“公钥”）， t d td td是允许求 f i f_i fi逆的陷门信息（“私钥”）。S a m p l e ( l K , i ) Sample(l^{\mathcal{K}},i) Sample(lK,i)是一个概率性算法，输入 i i i有 G e n Gen Gen产生，输出为 x ← R D i x\leftarrow _{R}D_i x←RDi。E v a l ( l K , i , x ) Eval(l^{\mathcal{K}},i,x) Eval(lK,i,x)是一个确定性算法，输出为 y ∈ D i y \in D_i y∈Di。即 E v a l ( l K , i , ⋅ ) : D i → D i Eval(l^{\mathcal{K}},i,\cdot):D_i \rightarrow D_i Eval(lK,i,⋅):Di→Di是 D i D_i Di上的一个置换。I n v e r t ( l K , t d , y ) Invert(l^{\mathcal{K}},td,y) Invert(lK,td,y)，输出为 x x x。
RSA加密算法就是一个典型的陷门置换：
6.
G
e
n
(
k
)
Gen(\mathcal{k})
Gen(k)：随机选取两个
K
\mathcal{K}
K比特素数
p
p
p和
q
q
q。计算
N
=
p
q
N=pq
N=pq，
φ
(
N
)
=
(
p
−
1
)
(
q
−
1
)
\varphi(N)=(p-1)(q-1)
φ(N)=(p−1)(q−1)。选取与
φ
(
N
)
\varphi(N)
φ(N)互素的
e
e
e，计算
e
d
=
1
m
o
d
φ
(
N
)
ed=1 mod \ \varphi(N)
ed=1mod φ(N)，输出为
(
(
N
,
e
)
,
(
N
,
d
)
)
((N,e),(N,d))
((N,e),(N,d))。分别对应
i
i
i和
t
d
td
td。定义域
D
N
,
e
D_{N,e}
DN,e就是
Z
N
Z_{N}
ZN。
7.
S
a
m
p
l
e
(
K
,
(
N
,
e
)
)
Sample(\mathcal{K},(N,e))
Sample(K,(N,e))：从
Z
N
Z_N
ZN中选取一个随机元素
x
x
x。
8.
E
v
a
l
(
K
,
(
N
,
e
)
,
x
)
Eval(\mathcal{K},(N,e),x)
Eval(K,(N,e),x)：
y
=
x
e
m
o
d
N
y=x^e mod \ N
y=xemod N。
9.
I
n
v
e
r
t
(
K
,
(
N
,
d
)
,
y
)
Invert(\mathcal{K},(N,d),y)
Invert(K,(N,d),y)，输出为
x
=
y
d
m
o
d
N
x=y^dmod \ N
x=ydmod N 。
单陷门置换定义
在陷门置换中没有考虑任何“困难性”和安全性的概念（可以为线性置换以及求逆），这在密码学上是没有意义的。所以一般认为密码学中的陷门置换是单陷门置换。单陷门置换是指当陷门信息
t
d
td
td未知时，一个随机陷门置换的求逆是困难的。具体定义如下：
一个陷门置换簇
(
G
e
n
,
S
a
m
p
l
e
,
E
v
a
l
,
I
n
v
e
r
t
)
(Gen,Sample,Eval,Invert)
(Gen,Sample,Eval,Invert)是单向的，如果对于任意的PPT敌手
A
\mathcal{A}
A，存在一个可忽略的函数
ϵ
(
K
)
\epsilon{(\mathcal{K})}
ϵ(K)，使得
A
\mathcal{A}
A在下面的对抗中，其优势
A
d
v
A
(
K
)
≤
ϵ
(
K
)
{Adv}_{\mathcal{A}}(\mathcal{K}) \leq \epsilon{(\mathcal{K})}
AdvA(K)≤ϵ(K)：
F
u
n
c
t
i
o
n
A
(
K
)
:
{Function}_{\mathcal{A}}(\mathcal{K}):
FunctionA(K):
(
i
,
t
d
)
←
G
e
n
(
K
)
(i,td)\leftarrow Gen(\mathcal{K})
(i,td)←Gen(K)；
y
←
S
a
m
p
l
e
(
K
,
i
)
y \leftarrow Sample(\mathcal{K},i)
y←Sample(K,i)；
x
←
A
(
K
,
i
,
y
)
x \leftarrow \mathcal{A}(\mathcal{K},i,y)
x←A(K,i,y)
如果
E
v
a
l
(
K
,
i
,
x
)
=
y
Eval(\mathcal{K},i,x)=y
Eval(K,i,x)=y，返回1；否则返回0。
A
\mathcal{A}
A的优势
A
d
v
A
(
K
)
{Adv}_{\mathcal{A}}(\mathcal{K})
AdvA(K)定义为
A
d
v
A
(
K
)
=
P
r
[
F
u
n
c
t
i
o
n
A
(
K
)
=
1
]
{Adv}_{\mathcal{A}}(\mathcal{K})=Pr[{Function}_{\mathcal{A}}(\mathcal{K})=1]
AdvA(K)=Pr[FunctionA(K)=1]，其中
P
r
Pr
Pr表示概率。
为了方便理解可以将
i
i
i表示为置换
f
f
f，
t
d
td
td表示为逆置换
f
−
1
f^{-1}
f−1。
本文转载自: https://blog.csdn.net/u012421101/article/details/128038062
版权归原作者 l齐天 所有， 如有侵权，请联系我们删除。
版权归原作者 l齐天 所有， 如有侵权，请联系我们删除。