单陷门置换-创新互联

  一个陷门置换族是一个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)：

1. PPT，运行步数是安全参数的多项式函数。
2. 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​逆的陷门信息（“私钥”）。
3. 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←R​Di​。
4. 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​上的一个置换。
5. 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元起，快前往官网查看详情吧