基本原理陷门单向函数) One-way Trapdoor Function >正向计算容易。即如果知道密钥P和消息M,容易计 算C=f(M。 例如在RSA中，c=m^d mod n >在不知道密钥S的情况下，反向计算不可行。即如果只 知道加密后的消息C而不知道密钥S.,则计算不可 行M=(C。 RSA中，如果知道(n,e),则不易求出d,除非n=p 中(n)易求，e的逆元d易求，ed≡1mod中(n) >在知道密钥S的情况下，反向计算容易。 即如果同时知 道加密消息C和密钥S，则计算M=s(O是容易的。这 里的密钥S相当于陷门，它和P配对使用。 解密容易，m=cAd mod n 8 CNR@HEU http://machunguang.hrbeu.edu.cn基本原理(陷门单向函数) ¾正向计算容易 即如果知道密钥 和消息M 容易计 ( ) ¾正向计算容易。即如果知道密钥 P 和消息M，容易计 算 。 ( ) k CfM = p Pk ¾在不知道密钥 的情况下，反向计算不可行。即如果只 的情况下，反向计算不可行。即如果只 知道加密后的消息C而不知道密钥 ，则计算不可 Sk 知道加密后的消息C而不知道密钥 S ，则计算不可 行 。 ¾ k S 1 M f C( ) − = ¾在知道密钥 的情况下，反向计算容易。即如果同时知 的情况下，反向计算容易。即如果同时知 道加密消息C和密钥 ，则计算 是容易的。这 Sk S ( ) 1 M f S C − 道加密消息C和密钥 ，则计算 = 是容易的。这 里的密钥 相当于陷门，它和 相当于陷门，它和 配对使用。 Sk Sk M f (C) Sk Pk 8 例如在RSA中，c=m^d mod n RSA中，如果知道(n,e),则不易求出d，除非n=pq φ(n)易求，e的逆元d易求，ed≡1 mod φ(n) 解密容易，m=c^d mod n One-way Trapdoor Function