公钥密码技术PPT课件

1、RSA公钥密码算法及其用于加密和签名的实现。ElGamal公钥密码算法及其用于加密和签名的实现。ECC公钥密码算法及其用于加密和签名的实现。公钥密码算法的设计基本方法和安全性原理。公钥密码体制加密密钥公开，解决了密钥管理与分公钥密码体制加密密钥公开，解决了密钥管理与分发的问题。那么如何实现公钥密码呢？本章介绍几个典型发的问题。那么如何实现公钥密码呢？本章介绍几个典型的公钥密钥算法，包括基于大数分解难题的的公钥密钥算法，包括基于大数分解难题的RSARSA算法，基算法，基于有限域上求解离散对数难解问题的于有限域上求解离散对数难解问题的ElGamalElGamal算法，以及算法，以及基于椭圆曲线上求

2、解离散对数难解问题的基于椭圆曲线上求解离散对数难解问题的ECCECC算法。算法。 25.1 RSA公钥密码算法5.2 Diffie-Hellman密钥协商机制5.3 ElGamal公钥密码体制5.4 椭圆曲线密码体制34 RSA（public-key cryptography），以当时在MIT的提出者Rivest、Shamir和Adleman三个人的名字命名，于1978年公开描述的。 RSA既可以用于加密也可以用于签名。 RSA包括公钥和私钥两个密钥，公钥可以让任何人知道并用于加密消息，使用公钥加密的消息只能使用对应的私钥解密。5信息安全技术基础 张浩军678 定义1（同余）：设a、b、m是正

3、整数，如果m|(a-b)，即m整除(a-b)，则称a和b模m同余，记为 定理1：（素数分解定理）：对任意正整数n，存在唯一的正素数序列 ，以及正整数 ，使得： 。 定义2（欧拉数）：设n是一个正整数， ，即小于n的与n互素的正整数，称为欧拉数。 特别地，当p是一个素数时，则 。9)(modmba mppp.21m,.,21mmpppn.2121| 1),gcd(, 11 | |)(nxnxxn1)( pp 定理2：如果n1和n2互素，则 。 定理3：如果一个正整数n按“定理1”分解并表示为 ，则 。 定理4：（Euler定理，欧拉定理）设x和n都是正整数，如果gcd(x,n)=1，则 定理5（

4、Fermat小定理）：设x和p都是正整数。如果p是素数，则10)()()(2121nnnnmmpppn.2121)/11).(/11)(/11 ()(21mpppnn)(mod1)(nxn)(mod pxxp 概率测试方法，选取特定比特长度的随机数，通过多次迭代进行概率素性测试。 例如Fermat素性测试：给定整数给定整数n，选择一些与，选择一些与n互素整数互素整数a，计算，计算an-1 mod n，如果结果不是如果结果不是1，则，则n是合数；若结果是是合数；若结果是1，n可能是也可可能是也可能不是素数能不是素数。11如何快速如何快速产生素数产生素数？ Miller-Rabin素性测试和Sol

5、ovay-Stassen素性测试算法，对于任意合数n，至少3/4（Miller-Rabin）、1/2（Solovay-Stassen）的a可以作为n是合数的证据。也称合数测试。 Miller-Rabin方法：给定整数n，选择一些整数an，令 ，d为奇数。对于所有的 如果： 而且 ，则n是合数；否则n可能是素数，也可能不是素数。通过多次迭代，提高判定n是素数概率。12如何快速如何快速产生素数产生素数？10sr 模幂运算满足分配律 (a mod n) (b mod n) mod n = (a b) mod n利用中间结果对利用中间结果对n n取模，即降低了存储要求，并可实现高取模，即降低了存储要求

6、，并可实现高效算法。效算法。 递进式指数计算例如计算ad (mod n)，为了便于计算机实现，其中指数d可以表示为k比特二进制(bk-1bk-2.b1b0)2，因此，d可以记为：有：13如何快速进行模指数运算？如何快速进行模指数运算？02ibidmodmodmod0)2(0)2(iiiibbdnanana 采用扩展欧几里得算法快速计算d：ax+by = gcd(a,b)gcd(a,b)表示a和b的最大公约数 即求解x和y，使得上面等式成立。对应地，求解式子ed+(-k)(n) =1中d和-k。14如何如何求解私钥求解私钥？ （1）穷举攻击即列出所有可能的私钥，显然这是缺乏效率和困难的。 （2）

7、因数分解攻击给定某个整数 ，求c的模n的e次方根 是一个困难问题，但如果整数n的素数分解已知，则上述问题易解。因此，因数分解攻击RSA途径包括： 分解n为p和q。 直接确定 ，而不确定p和q。 直接确定d，而不确定 。15)(n)(n （3）参数选取不当造成的攻击选取p和q时应该是随机的且不应太接近。因为， ，当(p-q)/2很小时，那么(p+q)/2只比 大一点，因此逐个检查大于 的整数x，使得 是一个完全平方数，记为y2，那么就有 ： 和 。164/)(4/)(22qpqppqnnnnx 2yxpyxq （4）选择密文攻击攻击者得到两个明/密文对 、 ，则可以获得 的密文结果，因为 由明密

8、文对 ，可以获得对 的加密结果，因为 此外， 能够获得 的解密结果，就可以恢复出c对应的明文。17),(00cm),(11cm10mm )(mod)(mod )(101010nccnmmmmeee),(00cmrm0)(mod)(00ncmrer)(mod2(nce1819（6）小）小 e 攻击攻击 采用很小加密指数，如采用很小加密指数，如 e=3，加密值很小的消息，加密值很小的消息 m，如，如 mn1/e，即，即me远小于模数远小于模数 n，这，这样样，直接计算，直接计算 e 的指数的指数，密文很容易被破解。，密文很容易被破解。 此外，若多个人使用相同的此外，若多个人使用相同的 e=3，但彼

9、此，但彼此 n 不同，设有不同，设有 3 个人分个人分别使用别使用 n1、n2、n3，若他们加密相同消息，若他们加密相同消息 m，即有：即有： )(mod131nmc 、)(mod232nmc 、)(mod333nmc ， 因为一般情况下因为一般情况下 n1、n2、n3是互素的，使用中国剩余定理可得：是互素的，使用中国剩余定理可得： )(mod3213nnnmc， 又因为又因为 m n1,n2,n3，所以所以 m3 n1 n2 n3，则，则3cm 。 随机填充机制加密消息优化非对称加密填充OAEP（Optimal Asymmetric Encryption Padding）机制 添加随机元素将

10、确定密码机制（如基本RSA）转换为一个概率机制。 部分密文解密（或其他信息泄露），只要不能翻转单向陷门函数，攻击者仍不能解密任何密文部分。20使用相同公钥，加密相同明文能否得到不同密文？（1）明文m后面填充k1个0。（2）产生k0比特随机数r。（3）使用G将k0比特随机数r扩展为(n-k0)长度比特串。（4）计算x=m000G(r)。（5）使用H将(n-k0)长度x压缩为长度k0比特串。（6）计算y=rH(x)。（7）最后输出x|y。21解密操作：（1）恢复随机串r= yH(x)。（2）恢复消息m000 = x G(r)。 22235.1 RSA公钥密码算法5.2 Diffie-Hellman

11、密钥协商机制5.3 ElGamal公钥密码体制5.4 椭圆曲线密码体制24 D-H密钥协商机制，可以实现在不安全信道中为两个实体建立一个共享秘密，协商的秘密可以作为后续对称密码体制的密钥使用。25信息安全技术基础 张浩军26D-H协商协议描述及实例27D-H协议中间人攻击285.1 RSA公钥密码算法5.2 Diffie-Hellman密钥协商机制5.3 ElGamal公钥密码体制5.4 椭圆曲线密码体制293031pmggmababakakkkmod/ 离散对数难解问题，即给定ga，求解a是困难的。323334355.1 RSA公钥密码算法5.2 Diffie-Hellman密钥协商机制5.

12、3 ElGamal公钥密码体制5.4 椭圆曲线密码体制363738394041424344454647484950515253 椭圆曲线上点群法则规定如下：设P、Q是E上的两个点，连接两个点得到一条直线，如果直线与曲线交叉，则得到第3个点（如图所示得到点R）；如果该直线在其中一个点与曲线相切，则该点计两次；如果直线与y轴平行，则定义第3个点为无穷远点。3椭圆曲线上加法运算几何含义椭圆曲线上加法运算几何含义543椭圆曲线上加法运算几何含义椭圆曲线上加法运算几何含义性质：（1）曲线上三个点在一条直线上，则它们的和等于O。（2）曲线上点P，则存在一个负点，记为-P，P+(-P)=O。（3）若一条垂直

13、x轴的竖线交于曲线上两点P、Q，则P+Q+O=O，于是有P=-Q。（4）如果曲线上两个点P和Q的x坐标不同，则连接P和Q得到一条直线与曲线交于R点，则P+Q+R=O，若R是R的负点，则P+Q=-R=R。（5）倍数运算，定义一个点P的两倍是它的切线与曲线的另一个交点R，则P+P=2P=-R=R。553椭圆曲线上加法运算几何含义椭圆曲线上加法运算几何含义563椭圆曲线上加法运算几何含义椭圆曲线上加法运算几何含义57585960616263646566本章介绍公钥密码体制的工作原理和具体实现方法。本章介绍公钥密码体制的工作原理和具体实现方法。介绍了典型公钥密码算法，如介绍了典型公钥密码算法，如RSARSA、ElGamalElGamal，以及强度更高，以及强度更高的椭圆曲线密码体制。描述了相关公钥密码算法的实现机理的椭圆曲线密码体制。描述了相关公钥密码算法的实现机理和对应密码体制的工作过程，讨论了和对应密码体制的工作过程，讨论了RSARSA算法具体实现过程算法具体实现过程中素数产生、模数运算等