基本原理陷门单向函数) 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
公钥密码算法应满足的要求 >接收方B产生密钥对（公钥PK和私钥SK?)在计算上是容易 的。 >发送方A用接收方的公钥对消息m加密以产生密文c,即 c=Et,(m)在计算上是容易的。 >接收方B用自己的私钥对c解密，即m=Dk,(C)在计算上是容 易的。 >攻击方由B的公钥PK求私钥SK在计算上是不可行的。 >攻击方由密文c和B的公钥PK恢复明文m或求私钥SKg (选择 明文攻击)在计算上是不可行的。 9 CNR@HEU http://machunguang.hrbeu.edu.cn
公钥密码算法应满足的要求 ¾接收方 B产生密钥对 （公钥PK B和私钥SK B ）在计算上是容易 在计算上是容易 的。 ¾发送方A用接收方的公钥对消息 用接收方的公钥对消息m加密以产生密文 加密以产生密文c，即 cE m = pk ( ) 在计算上是容易的 在计算上是容易的 。 ¾接收方B用自己的私钥对 用自己的私钥对c解密，即 在计算上是容 易的 。 ( ) B pk ( ) B mD c = sk 易的 。 ¾攻击方由B的公钥PK B求私钥SK B在计算上是不可行的。 ¾攻击方由密文c和B的公钥PK B恢复明文m或求私钥SKB (选择 明文攻击 )在计算上是不可行的 。 9 明文攻击 )在计算上是不可行的
公钥密码算法思考的主要问题 >私钥和公钥是如何生成的，它们之间有着怎样的关系； 》>安全的密钥长度是多少； >公钥密码体制的安全性依赖的数学难题是什么； >如何实现加密算法（公钥加密），以及解密算法（私钥解密）， 反之亦然（数字签名)； >现在这种公钥密码体制的安全分析。 10 CNR@HEU http://machunguang.hrbeu.edu.cn
公钥密码算法思考的主要问题 ¾私钥和公钥是如何生成的，它们之间有着怎样的关系； ¾安全的密钥长度是多少； ¾公钥密码体制的安全性依赖的数学难题是什么； ¾如何实现加密算法 如何实现加密算法 (公钥加密 )，以及解密算法 (私钥解密 )， 反之亦然（数字签名）； ¾现在这种公钥密码体制的安全分析。 10
常用算法 ●背包问题(NP问题)。 背包算法 ●基于大整数素因子分解问题。 RSA,Rabin等 ●基于有限域乘法群上的离散对数问题。 Elgamal(DS)。 ●椭园曲线上的离散对数问题。 ECC。 ●基于身份的密码体制 IBE。 11 CNR@HEU http://machunguang.hrbeu.edu.cn
常用算法 背包问题（NP问题）。 背包算法 基于大整数素因子分解问题。 RSA，Rabin等 基于有限域乘法群上的离散对数问题。 Elgamal Elgamal（DS）。 椭园曲线上的离散对数问题。 ECC。 基于身份的密码体制 IBE。 11
背包算法简介 (略，自学) >由默克尔 (Merkle)和赫尔曼(Hellman)提出的； >最早提出的公开密钥算法； >安全性源于背包问题，是一个NP问题； >大部分是不安全的，很少使用； 12 CNR@HEU http://machunguang.hrbeu.edu.cn
背包算法简介 ¾由默克尔（Merkle）和赫尔曼（Hellman）提出的； ¾最早提出的公开密钥算法； ¾安全性源于背包问题，是一个NP问题； ¾大部分是不安全的，很少使用； 12 （略，自学）