陷门置换定义
一个陷门置换族是一个PPT算法元组
(Gen,Sample,Eval,Invert)(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.
Gen(k)Gen(\mathcal{k})Gen(k)：随机选取两个K\mathcal{K}K比特素数ppp和qqq。计算N=pqN=pqN=pq，φ(N)=(p−1)(q−1)\varphi(N)=(p-1)(q-1)φ(N)=(p−1)(q−1)。选取与φ(N)\varphi(N)φ(N)互素的eee，计算ed=1modφ(N)ed=1 mod \ \varphi(N)ed=1mod φ(N)，输出为((N,e),(N,d))((N,e),(N,d))((N,e),(N,d))。分别对应iii和tdtdtd。定义域DN,eD_{N,e}DN,e就是ZNZ_{N}ZN。
7.
Sample(K,(N,e))Sample(\mathcal{K},(N,e))Sample(K,(N,e))：从ZNZ_NZN中选取一个随机元素xxx。
8.
Eval(K,(N,e),x)Eval(\mathcal{K},(N,e),x)Eval(K,(N,e),x)：y=xemodNy=x^e mod \ Ny=xemod N。
9.
Invert(K,(N,d),y)Invert(\mathcal{K},(N,d),y)Invert(K,(N,d),y)，输出为x=ydmodNx=y^dmod \ Nx=ydmod N 。
单陷门置换定义
在陷门置换中没有考虑任何“困难性”和安全性的概念（可以为线性置换以及求逆），这在密码学上是没有意义的。所以一般认为密码学中的陷门置换是单陷门置换。单陷门置换是指当陷门信息
tdtdtd未知时，一个随机陷门置换的求逆是困难的。具体定义如下：
一个陷门置换簇
(Gen,Sample,Eval,Invert)(Gen,Sample,Eval,Invert)(Gen,Sample,Eval,Invert)是单向的，如果对于任意的PPT敌手A\mathcal{A}A，存在一个可忽略的函数ϵ(K)\epsilon{(\mathcal{K})}ϵ(K)，使得A\mathcal{A}A在下面的对抗中，其优势AdvA(K)≤ϵ(K){Adv}_{\mathcal{A}}(\mathcal{K}) \leq \epsilon{(\mathcal{K})}AdvA(K)≤ϵ(K)：FunctionA(K):{Function}_{\mathcal{A}}(\mathcal{K}):FunctionA(K):(i,td)←Gen(K)(i,td)\leftarrow Gen(\mathcal{K})(i,td)←Gen(K)；y←Sample(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)
如果
Eval(K,i,x)=yEval(\mathcal{K},i,x)=yEval(K,i,x)=y，返回1；否则返回0。A\mathcal{A}A的优势AdvA(K){Adv}_{\mathcal{A}}(\mathcal{K})AdvA(K)定义为AdvA(K)=Pr[FunctionA(K)=1]{Adv}_{\mathcal{A}}(\mathcal{K})=Pr[{Function}_{\mathcal{A}}(\mathcal{K})=1]AdvA(K)=Pr[FunctionA(K)=1]，其中PrPrPr表示概率。
为了方便理解可以将
iii表示为置换fff，tdtdtd表示为逆置换f−1f^{-1}f−1。
本文转载自: https://blog.csdn.net/u012421101/article/details/128038062
版权归原作者 l齐天 所有， 如有侵权，请联系我们删除。
版权归原作者 l齐天 所有， 如有侵权，请联系我们删除。