陷门置换定义
一个陷门置换族是一个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)：
成都创新互联公司是专业的濮阳网站建设公司，濮阳接单;提供成都网站设计、成都做网站、
外贸网站建设,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行濮阳网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
- 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。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享名称：单陷门置换-创新互联
网站URL：
http://cdkjz.cn/article/ccopih.html
