《《次课公钥密码》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《次课公钥密码》PPT课件.ppt（49页珍藏版）》请在金锄头文库上搜索。
1、NCEPU-BD公钥密码公钥密码Public Key Cryptography公钥密码学思想公钥密码学思想v 公钥密码算法的基本工具不再是代换和置换，而是公钥密码算法的基本工具不再是代换和置换，而是数学函数数学函数。v 公钥密码算法是以非对称的形式使用两个密钥，两公钥密码算法是以非对称的形式使用两个密钥，两个密钥的使用对个密钥的使用对 保密性、密钥分配、认证保密性、密钥分配、认证 等都有等都有着深刻的意义。着深刻的意义。v 公钥密码体制的出现在密码学史上是一个最大的而公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。且是惟一真正的革命。公钥密码学是公钥密码学是1976年由年由Di
2、ffie和和Hellman在其在其“密码学新方向密码学新方向”一文中提出的一文中提出的W.Diffie and M.E.Hellman, New Directrions in Cryptography公钥密码体制的原理公钥密码体制的原理v采用两个相关密钥将加密和解密能力分开，其中一采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为个密钥是公开的，称为公开密钥公开密钥 ，用于加密；另一，用于加密；另一个密钥是为用户专用，因而是保密的，称为个密钥是为用户专用，因而是保密的，称为秘密密秘密密钥钥 ，用于解密。，用于解密。v因此公钥密码体制也称为因此公钥密码体制也称为双钥密码体制双钥密码
3、体制 。v算法有以下重要特性：算法有以下重要特性： 已知密码算法和加密密钥，求解密密钥在计算上是不可行的。已知密码算法和加密密钥，求解密密钥在计算上是不可行的。公钥密码体制的原理公钥密码体制的原理v公钥体制公钥体制(Public key system) (Diffie和和Hellman,1976) 每个用户都有一对选定的密钥每个用户都有一对选定的密钥( (公钥公钥k k1 1；私钥；私钥k k2 2) )，公开的密钥公开的密钥k k1 1可以像电话号码一样进行注册公布。可以像电话号码一样进行注册公布。v主要特点：主要特点：加密和解密能力分开。加密和解密能力分开。多个用户加密的消息只能由一个用户
4、解读，（用于公共网多个用户加密的消息只能由一个用户解读，（用于公共网络中实现保密通信）。络中实现保密通信）。只能由一个用户加密消息而使多个用户可以解读（可用于只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。认证系统中对消息进行数字签字）。无需事先分配密钥。无需事先分配密钥。公钥密码体制的意义公钥密码体制的意义v密钥分配密钥分配v数字签字数字签字1.公钥密码体制的概念在公钥密码体制的概念在密钥分配密钥分配 上的上的贡献；贡献；2.公钥密码体制的概念在公钥密码体制的概念在密钥创建密钥创建 上的上的贡献。贡献。考虑的是如何为数字化的消息或考虑的是如何为数字化的消息或
5、文件提供一种类似于为书面文件文件提供一种类似于为书面文件手书签字的方法。手书签字的方法。公钥体制公钥体制加密加密 的框图的框图B产生公钥和私钥：产生公钥和私钥：PKB、SKBA向向B发送消息发送消息m，利用利用PKB加密，得密加密，得密文文c 。B收到密文收到密文c ，利用，利用私钥私钥SKB解密，得明解密，得明文文m 。多个用户加密的消息多个用户加密的消息只能由一个用户解读。只能由一个用户解读。由于任一用户都可用用户由于任一用户都可用用户B的公开的公开钥钥PKB 向他发送机密消息，因而向他发送机密消息，因而密文密文c不具有认证性。不具有认证性。公钥密码体制公钥密码体制认证认证 框图框图只能由
6、一个用户加密消息而使多个只能由一个用户加密消息而使多个用户可以解读。用户可以解读。A向向B发送消息发送消息m，利用，利用SKA加密，加密，得密文得密文c 。A产生公钥和私钥：产生公钥和私钥：PKA、SKAB收到密文收到密文c ，利用，利用A的公钥的公钥PKA解密，解密，得明文得明文m 。安全性：安全性： 由于由于SkA 是保密的，其他人都不可能伪造是保密的，其他人都不可能伪造密文密文c，可用，可用A的的 公开钥解密时得到有意义公开钥解密时得到有意义的消息的消息m。因此可以验证消息。因此可以验证消息m来自来自A而不而不是其他人，而实现了对是其他人，而实现了对A所发消息的认证。所发消息的认证。不具
7、有保密性！不具有保密性！公钥密码体制的认证、保密框图公钥密码体制的认证、保密框图v以上认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不以上认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不能被他人篡改，能被他人篡改，但却能被他人窃听但却能被他人窃听。这是因为任何人都能用用户的公开。这是因为任何人都能用用户的公开钥对消息解密。为了同时提供认证功能和保密性，可使用双重加、解密。钥对消息解密。为了同时提供认证功能和保密性，可使用双重加、解密。公钥密码应满足的要求公钥密码应满足的要求v接收方接收方B B产生密钥对在计算上是容易的。产生密钥对在计算上是容易的。v发送方发送方A A用收方
8、的公开钥对消息用收方的公开钥对消息m m 加密以产生密文加密以产生密文c c 在计算在计算上是容易的。上是容易的。v收方收方B B用自己的秘密钥对密文用自己的秘密钥对密文c c 解密在计算上是容易的。解密在计算上是容易的。v敌手由密文敌手由密文c c 和和B B的公开密钥恢复明文在计算上是不可行的。的公开密钥恢复明文在计算上是不可行的。v敌手由密文敌手由密文c c 和和B B的公开密钥恢复秘密密钥在计算上是不可的公开密钥恢复秘密密钥在计算上是不可行的。行的。v加解密次序可换，即加解密次序可换，即E EPKBPKBDDSKBSKB(m)=D(m)=DSKBSKBEEPKBPKB(m) ,(m)
9、,不是对任不是对任何算法都做此要求。何算法都做此要求。以上要求的本质之处在于要求一个以上要求的本质之处在于要求一个陷门单向函数陷门单向函数。单向函数一个可逆函数一个可逆函数f f：A AB B，若它满足：，若它满足： 1 1o o 对所有对所有x x A A，易于计算，易于计算f f ( (x x) )。 2 2o o 对对“几几乎乎所所有有x x A A ”由由f f ( (x x) )求求x x “极极为为困困难难”，以以至至于于实实际际上上不不可可能能做做到到，则则称称f f 为为一一单单向向(One-way)(One-way)函数函数。定定义义中中的的“易易于于计计算算”是是指指函函数
10、数值值能能在在其其输输入入长长度度的的多多项项式式时时间间内内求求出出，即即若若输输入入长长度度为为n n，计计算算函函数数的的时时间间是是n na a的倍数，的倍数，a a为一固定的常数。为一固定的常数。若计算函数时间是若计算函数时间是a an n的倍数，则为的倍数，则为不可能做到不可能做到的。的。陷门单向函数v单向函数是求逆困难的函数，而单向函数是求逆困难的函数，而单向陷门函数单向陷门函数(Trapdoor one-way function)(Trapdoor one-way function)，是在不知，是在不知陷门信息下求逆困难的函数，当知道陷门信息后，求逆是易下求逆困难的函数，当知道
11、陷门信息后，求逆是易于实现的。于实现的。v陷门单向函数陷门单向函数是一族可逆函数是一族可逆函数f fk k，满足，满足1.Y=fk(X)易于计算（当k和X已知）2.Xf-1k(Y)易于计算（当k和Y已知）3.Xf-1k(Y)计算上不可行（Y已知但k未知） 研究公钥密码算法就是找出合适的单向限门函数。研究公钥密码算法就是找出合适的单向限门函数。对公钥密码体制的攻击对公钥密码体制的攻击v穷搜索攻击。穷搜索攻击。v寻找从公开钥计算秘密钥的方法。寻找从公开钥计算秘密钥的方法。v可能字攻击。可能字攻击。对称密码对称密码 公钥密码公钥密码一般要求：一般要求：1、加密解密用相同的密钥、加密解密用相同的密钥2
12、、收发双方必须共享密钥、收发双方必须共享密钥安全性要求：安全性要求：1、密钥必须保密、密钥必须保密2、没有密钥，解密不可行、没有密钥，解密不可行3、知道算法和若干密文不足以确定、知道算法和若干密文不足以确定密钥密钥一般要求：一般要求：1、加密解密算法相同，但使用不同、加密解密算法相同，但使用不同的密钥的密钥2、发送方拥有加密或解密密钥，而、发送方拥有加密或解密密钥，而接收方拥有另一个密钥接收方拥有另一个密钥安全性要求：安全性要求：1、两个密钥之一必须保密、两个密钥之一必须保密2、无解密密钥，解密不可行、无解密密钥，解密不可行3、知道算法和其中一个密钥以及若、知道算法和其中一个密钥以及若干密文不
13、能确定另一个密钥干密文不能确定另一个密钥关于公钥密码的几种误解关于公钥密码的几种误解v公钥密码比传统密码安全？公钥密码比传统密码安全？v公钥密码是通用方法，所以传统密码已经过时？公钥密码是通用方法，所以传统密码已经过时？v公钥密码实现密钥分配非常简单？公钥密码实现密钥分配非常简单？v公钥算法的种类很多，具有代表性的三种密码：公钥算法的种类很多，具有代表性的三种密码： 基于整数分解难题（基于整数分解难题（IFP）的算法体制）的算法体制 基于离散对数难题（基于离散对数难题（DLP）算法体制）算法体制基于椭圆曲线离散对数难题（基于椭圆曲线离散对数难题（ECDLP）的算法体制）的算法体制RSA算法RS
14、A AlgorithmRSA算法概况vMITMIT三三 位位 年年 青青 数数 学学 家家 R.L.RivestR.L.Rivest， A.ShamirA.Shamir和和L.AdlemanRivestL.AdlemanRivest等等1978, 1978, 19791979发发现现了了一一种种用用数数论论构构造造双双钥钥的的方方法法，称称作作MIT体制，后后来来被被广广泛泛称称之之为为RSA体制。v它既可用于加密、又可用于数字签字。它既可用于加密、又可用于数字签字。vRSARSA算法的安全性基于数论中算法的安全性基于数论中大整数分解的困难性大整数分解的困难性。Euler 函数函数v(n):
15、设设n是一个正整数，小于是一个正整数，小于n且与且与n互素的正整数的个互素的正整数的个数称为数称为n的的欧拉函数欧拉函数。v当当n是素数是素数时，小于时，小于n的所有整数均与的所有整数均与n互素，因此互素，因此(n)=n-1 .v对对n=pq, p和和q 是素数是素数，(n)=(p)(q)=(p-1)(q-1)Euler定理、定理、Fermat定理定理vEuler定理定理：设：设 x 和和 n 都是正整数，如果都是正整数，如果gcd(x，n)1，则，则 x (n)1 (mod n).vFermat定理定理:设设 x 和和 p 都是正整数，如果都是正整数，如果gcd(x，p)1，则，则 x p-
16、11 (mod p).算法描述算法描述v1. 密钥产生独立地选取两大素数独立地选取两大素数 p p 和和 q q ( (各各100100200200位十进制数字位十进制数字) )计算计算 n n= =p pq q，其欧拉函数值，其欧拉函数值 ( (n n)=()=(p p1)(1)(q q1)1) 随机选一整数随机选一整数e e，1 1 e e 253很快发现：很快发现：11*23=253，则得，则得 (n) =220 根据根据 139d(mod220)=1 d=19 v实际中使用实际中使用RSA，必选两个很大的素数，从而使，必选两个很大的素数，从而使n几乎不可分解因子。几乎不可分解因子。小结
17、小结 RSA使用的运算使用的运算vd=e -1 mod (n)d d是是e e的反模运算，利用欧几里德算法。的反模运算，利用欧几里德算法。v大素数的选择素性检验素性检验v大整数的幂的计算用于加（解）密时，手工完成不可能，计算机直接算也比用于加（解）密时，手工完成不可能，计算机直接算也比较慢。较慢。反模运算反模运算e d=1 mod (p-1)(q-1)v欧几里德欧几里德(Euclid)算法是数论中的一个基本技术，是算法是数论中的一个基本技术，是求两个求两个正整数的最大公因子正整数的最大公因子的简化过程。的简化过程。v推广推广Euclid算法，不仅可求两个正整数的最大公因子；而且算法，不仅可求两
18、个正整数的最大公因子；而且当两个正整数当两个正整数互素互素时，还可求出其中一个数关于另一个数的时，还可求出其中一个数关于另一个数的乘法逆元乘法逆元。Euclid算法算法 -求最大公因子求最大公因子v基于结论：任意非负整数基于结论：任意非负整数a和正整数和正整数b，有有gcd(gcd(a a, ,b b)=gcd)=gcd（b b, ,a(a(modmodb)b)v证明：是正整数证明：是正整数可表示为可表示为a=ka=k+r,+r,即即a(modb)=ra(modb)=rk是一整数是一整数a(modb)=a-kb又设是，的公因子，即又设是，的公因子，即d|a , d|bd|kbd|(a-kb)
19、,即即d|(amodb)整除的性质整除的性质是和是和amodb的公因子的公因子a，b的公因子集合与的公因子集合与b，amodb的公因子集合相等，两个的公因子集合相等，两个集合的最大值也相等。集合的最大值也相等。 证毕证毕Euclid算法算法 -求最大公因子（示例）求最大公因子（示例）vgcd(55,22)=gcd(22,55mod22) =gcd(22,11) =gcd(11,22mod11) =gcd(11,0)=11vgcd(18,12)=gcd(12,6)=gcd(6,0)=6vgcd(11,10)=gcd(10,1)=1Euclid算法算法 -求最大公因子（伪代码）求最大公因子（伪代码
20、）设输入两个正整数设输入两个正整数d，f，且，且fd1.X f ; Y d ;2.If(Y=0) then return X=gcd(f,d)3.If(Y=1) then return Y=gcd(f,d)4.R=XmodY5.X=Y6.Y=R7.goto 2gcd(18,12)=gcd(12,6)=gcd(6,0)=6f dX Y思考：思考：gcd(1970,1066)=?扩展扩展Euclid算法算法 -求乘法逆元求乘法逆元v整除中一个论断：整除中一个论断：如果如果gcd(a,b)=d，则存在，则存在m,n，使得，使得d=ma+nb，称这种关系，称这种关系为为a,b组合整数组合整数d，m,n
21、称为组合系数。称为组合系数。当当d=1，有，有ma+nb=1，此时可看出，此时可看出m是是a模模b的逆元，的逆元， n是是b模模a的逆元。的逆元。v推广推广Euclid算法先求出算法先求出gcd(a,b)，当，当gcd(a,b)=1时，则返回时，则返回b的逆元。的逆元。扩展扩展Euclid算法算法 -求乘法逆元（伪代码）求乘法逆元（伪代码）v设设ed(modm)=1，求，求e的值的值1.(X1, X2, X3)(1,0,m); (Y1, Y2, Y3)(0,1,d); 2.If Y3=0 then return X3=gcd(m,d) , stop;3.If Y3=1 then return
22、e=d-1(modm)=Y2 , stop;4.Q=X3/Y3 （整数除）（整数除）5.(T1, T2, T3)(X1-QY1 , X2-QY2 , X3-QY3) ;6.(X1, X2, X3) (Y1, Y2, Y3) ;7.(Y1, Y2, Y3) (T1, T2, T3)8.goto 2扩展扩展Euclid算法算法 -求乘法逆元（示例）求乘法逆元（示例）v求解求解11e(mod51)=1循环次数循环次数 Q X1 X2 X3 Y1 Y2 Y3 初值初值 1 0 51 0 1 11 1 40 1 111 -4 7(X1, X2, X3)(1,0,m); (Y1, Y2, Y3)(0,1,
23、d);Q=X3/Y3 （整数除）（整数除）(X1, X2, X3) (Y1, Y2, Y3)(T1, T2, T3)(X1-QY1 , X2-QY2 , X3-QY3)(Y1, Y2, Y3) (T1, T2, T3)2 11 -4 7-1 5 43 1-1 5 42 -9 34 1-3 14 12 -9 3算法中隐含：算法中隐含：mX1+dX2=X3 mY1+dY2=Y3当当Y3=1，Y1=d-1modmX3 和和Y3相当于相当于Euclid中的中的X和和YX3=前一轮的前一轮的Y3Y3=前一轮前一轮X3-QY3，即，即X3modY3v思考：思考：vgcd(1769,550)=1v550-1
24、mod1769=?小结小结 RSA使用的运算使用的运算vd=e -1 mod (n)d d是是e e的反模运算，利用欧几里德算法。的反模运算，利用欧几里德算法。v大素数的选择素性检验素性检验v大整数的幂的计算用于加（解）密时，手工完成不可能，计算机直接算也比用于加（解）密时，手工完成不可能，计算机直接算也比较慢。较慢。素性检验（素性检验（1）方法方法1：用：用2- 之间的每个素数去除之间的每个素数去除n，均除不尽，则，均除不尽，则n为素数。为素数。方法方法2：Fermat测试测试定理：底数定理：底数a和素数和素数p，其中，其中a不能被不能被p整除，那么有整除，那么有ap-1modp=1例如：例
25、如：6为底数，为底数，7为素数，为素数，67-1mod7=66mod7=46656mod7=1方法：若方法：若c可能是素数，则选一底数（可能是素数，则选一底数（eg，2），验算是否），验算是否2c-1modc=1正确理解：所有素数满足该等式，但使该等式成立的不一定是素数。正确理解：所有素数满足该等式，但使该等式成立的不一定是素数。例如：例如：2341-1mod341=1, 但但11*13=341问题：伪素数，问题：伪素数，eg 341， 91等。等。解决方案：使用不同的底数进行两次测试，可避免伪素数。解决方案：使用不同的底数进行两次测试，可避免伪素数。问题：卡米克尔数（问题：卡米克尔数（Car
26、michael),对所有底数都是伪素数。对所有底数都是伪素数。eg 561,1105,1729等。等。解决方法：多个底数进行解决方法：多个底数进行Fermat测试，若通过，再与测试，若通过，再与Carmichael数表比数表比较，若不在其中，则为素数。（小于较，若不在其中，则为素数。（小于25*109的数中，有的数中，有2163个个Carmichael数）数）素性检验（素性检验（2）方法：米勒罗宾（方法：米勒罗宾（Miller-Rabin）测试法）测试法引理：若引理：若p(2)为素数，则方程为素数，则方程x2=1(modp)的解只有的解只有x=1和和x=-1推论：若方程推论：若方程x2=1(m
27、odp)有一解有一解x0 -1,1 ,那么那么p不是素数。不是素数。 算法算法Witness(a,n): 先将先将n-1表示为二进制表示为二进制bk bk-1 b0 , d赋初值赋初值1 。For i=k downto 0 do xd;d(d*d)modn;if (d=1) and (x1) and (xn-1) then return False;if (bi=1) then d (d*a)modnIf d 1 then return False;return True;n是待测数，是待测数，a(n)是整数。是整数。for循环结束后，有循环结束后，有d=an-1modn(由由Fermat定理
28、，若定理，若n为素数，为素数，d=1)v米勒罗宾（米勒罗宾（Miller-Rabin）测试法）测试法对对s个不同的个不同的a，重复调用这一算法，只要有一次算法返回，重复调用这一算法，只要有一次算法返回为为False，就可肯定，就可肯定n不是素数；不是素数；如果算法每次都返回如果算法每次都返回True，则，则n为素数的概率至少为为素数的概率至少为1-2-s对于足够大的对于足够大的s，就可很肯定，就可很肯定n为素数。为素数。小结小结 RSA使用的运算使用的运算vd=e -1 mod (n)d d是是e e的反模运算，利用欧几里德算法。的反模运算，利用欧几里德算法。v大素数的选择素性检验素性检验v大
29、整数的幂的计算用于加（解）密时，手工完成不可能，计算机直接算也比用于加（解）密时，手工完成不可能，计算机直接算也比较慢。较慢。大整数的幂的计算（1）v问题问题1：中间结果很大，有可能超出计算机所允许的：中间结果很大，有可能超出计算机所允许的整数取值范围。整数取值范围。v问题：乘法次数很多。问题：乘法次数很多。v解决：每次乘法运算后取模。因为解决：每次乘法运算后取模。因为abmodn=(amodn)(bmodn)modnv解决：利用重复平方的方法来减少乘法的次数。解决：利用重复平方的方法来减少乘法的次数。例如例如2116，16次乘法次乘法因为因为16=2*2*2*2所以所以2116=212*2*
30、2*2=(212)2)2)2 4次乘法次乘法大整数的幂的计算（2）v此方法对所有指数是此方法对所有指数是2的乘幂都是可以的的乘幂都是可以的v如果指数不是如果指数不是2的乘幂，可通过指数的二进制表示改的乘幂，可通过指数的二进制表示改为为2的乘幂。的乘幂。例如例如2141 ，41=(101001)2 25+23+20所以所以 2141=2132218211例如例如7951mod90=79327916792791mod90=19 51: 11011大整数的幂的计算（3）v快速指数算法：快速指数算法：将将m表示为二进制表示为二进制bkbk-1b0，求，求ammodnc=0; d=1;for i=k d
31、ownto 0 do c=2*c; d=(d*d)modn; if bi=1 then c=c+1; d=(d*a)modn Return d;vd的终值是所求，的终值是所求，c的终值为指数的终值为指数m。m=bk2k+bk-12k-1+b12+b0在在i=k时，完成时，完成 abk在在i=k-1时，完成时，完成 (abk)2当当i=0时，即使时，即使 b0=1也不需要平方了也不需要平方了RSA的安全性vRSA的安全性是基于分解大整数的困难性假定（尚未证明分解大整数是NP问题）。）。v如果分解n=pq，则立即获得(n)=(p1)(q1)，从而能够确定e的模(n)乘法逆d。vRSA-129历时8
32、个月被于1996年4月被成功分解，RSA130于1996年4月被成功分解。v密钥长度应该介于1024bit到2048bit之间。v由n直接求(n)等价于分解n。v对对p、q要求：要求： |p-q|要大要大p-1和和q-1都应有大素因子都应有大素因子v如果如果en且且dn1/4，则，则d能被容易地确定。能被容易地确定。RSA的攻击的攻击v有些攻击是专门针对有些攻击是专门针对RSA的实现。的实现。v不攻击基本的算法，而是攻击协议。不攻击基本的算法，而是攻击协议。RSA的攻击（的攻击（1）v情况情况1：攻击者在发方：攻击者在发方A的通信中窃听，获得一个的通信中窃听，获得一个A的公开秘钥加密的密文的公
33、开秘钥加密的密文c，攻击者计算，攻击者计算mv方法：选一随机数方法：选一随机数rn，已知，已知A的的Pk=e，计算，计算x=remodn , y=xcmodn, t=r-1modnv现攻击者让现攻击者让A用其用其SK对对y签名，以便解密签名，以便解密y（A对消对消息息y签名，而非对消息的签名，而非对消息的Hash值签名），值签名），A计算计算u=ydmodnv现攻击者计算现攻击者计算 tu=r-1yd=r-1(xc)d=cd=mmodn若若 x=remodn则，则，r=xdmodnRSA的攻击（的攻击（2）v情况：情况：T是公开的计算机公证人，若是公开的计算机公证人，若M想让想让T对一个对一个
34、其不愿签名的消息其不愿签名的消息m签名。签名。v方法：方法：M选一选一x，计算，计算y=xemodn, 即即x=ydmodn,然后计算然后计算 m=ymmodn,将将m发送给发送给T签名。签名。vT回送回送mdmodnvM计算计算 (mdmodn)x-1modn=(ym)dx-1 = mdydx-1=(m)dmodnRSA的攻击（的攻击（3）v情况情况3：E想让想让A对对m3签名签名v方法：方法：E产生两份消息产生两份消息m1，m2，满足，满足m3=m1*m2(modn)v若若E能让能让A对对m1，m2签名，他就能计算签名，他就能计算m3的签名的签名 m3d=(m1dmodn)(m2dmodn
35、)(modn)v总结：不要对陌生人的随机消息进行签名，若要签总结：不要对陌生人的随机消息进行签名，若要签名，应对消息的名，应对消息的Hash值签名。值签名。RSA的攻击（的攻击（4）v另外，对另外，对RSA还存在公共模数攻击，低加密指数攻还存在公共模数攻击，低加密指数攻击，低解密指数攻击。击，低解密指数攻击。选择大选择大d加密前用随机位填充消息，加密前用随机位填充消息，确保确保m和和n的大小一样的大小一样不要在一组用户间共享不要在一组用户间共享n单向陷门函数v单向陷门函数单向陷门函数(One-way Trapdoor Function)定义：定义：v一一“可逆可逆”函数函数F若满足下列二条件，
36、则若满足下列二条件，则F称为称为单向陷门函数：单向陷门函数：v1.对于所有属于对于所有属于F定义域的任一定义域的任一x，可以很容易，可以很容易算出算出F(x) = y;v2.对于几乎所有属于对于几乎所有属于F值域的任一值域的任一y，则在计算，则在计算上除非获得陷门，否则不可能求出上除非获得陷门，否则不可能求出x，使得，使得x = F(-1)(y)，F（-1）为）为F的反函数。但若有一额外的反函数。但若有一额外数据数据z（称为陷门），则可以很容易的求出（称为陷门），则可以很容易的求出 x = F(-1)(y)。vv单向函数与单向陷门函数的差异在于可逆与不可逆。若单向陷门函数存在，则任何单向陷门函数均可用来设计公开密钥密码系统。同时，若单向函数满足交换性，则单向函数也可能用来设计公开密钥密码系统。
