信息安全技术基础第5章

第5章公钥密码技术学习目标RSA公钥密码算法及其用于加密和签名的实现。ElGamal公钥密码算法及其用于加密和签名的实现。ECC公钥密码算法及其用于加密和签名的实现。公钥密码算法的设计基本方法和安全性原理。公钥密码体制加密密钥公开，解决了密钥管理与分发的问题。那么如何实现公钥密码呢？本章介绍几个典型的公钥密钥算法，包括基于大数分解难题的RSA算法，基于有限域上求解离散对数难解问题的ElGamal算法，以及基于椭圆曲线上求解离散对数难解问题的ECC算法。2目录5.1RSA公钥密码算法5.2Diffie-Hellman密钥协商机制5.3ElGamal公钥密码体制5.4椭圆曲线密码体制3如何实现加密密钥公开的加密算法？45.1.1RSA基本算法RSA（public-keycryptography），以当时在MIT的提出者Rivest、Shamir和Adleman三个人的名字命名，于1978年公开描述的。RSA既可以用于加密也可以用于签名。RSA包括公钥和私钥两个密钥，公钥可以让任何人知道并用于加密消息，使用公钥加密的消息只能使用对应的私钥解密。5信息安全技术基础张浩军675.1.1RSA基本算法85.1.2RSA加密算法的数论基础定义1（同余）：设a、b、m是正整数，如果m|(a-b)，即m整除(a-b)，则称a和b模m同余，记为定理1：（素数分解定理）：对任意正整数n，存在唯一的正素数序列

，以及正整数

，使得：

。定义2（欧拉数）：设n是一个正整数，

，即小于n的与n互素的正整数，称为欧拉数。特别地，当p是一个素数时，则

。95.1.2RSA加密算法的数论基础定理2：如果n1和n2互素，则

。定理3：如果一个正整数n按“定理1”分解并表示为

，则

。定理4：（Euler定理，欧拉定理）设x和n都是正整数，如果gcd(x,n)=1，则定理5（Fermat小定理）：设x和p都是正整数。如果p是素数，则105.1.3RSA算法实现中的计算问题概率测试方法，选取特定比特长度的随机数，通过多次迭代进行概率素性测试。例如Fermat素性测试：

给定整数n，选择一些与n互素整数a，计算an-1modn，如果结果不是1，则n是合数；若结果是1，n可能是也可能不是素数。11如何快速产生素数？5.1.3RSA算法实现中的计算问题Miller-Rabin素性测试和Solovay-Stassen素性测试算法，对于任意合数n，至少3/4（Miller-Rabin）、1/2（Solovay-Stassen）的a可以作为n是合数的证据。也称合数测试。Miller-Rabin方法：给定整数n，选择一些整数a<n，令

，d为奇数。对于所有的

如果：

而且

，则n是合数；否则n可能是素数，也可能不是素数。通过多次迭代，提高判定n是素数概率。12如何快速产生素数？5.1.3RSA算法实现中的计算问题模幂运算满足分配律

[(amodn)×(bmodn)]modn=(a×b)modn

利用中间结果对n取模，即降低了存储要求，并可实现高效算法。递进式指数计算

例如计算ad(modn)，为了便于计算机实现，其中指数d可以表示为k比特二进制(bk-1bk-2...b1b0)2，因此，d可以记为：

有：13如何快速进行模指数运算？5.1.3RSA算法实现中的计算问题采用扩展欧几里得算法快速计算d：

ax+by=gcd(a,b)

gcd(a,b)表示a和b的最大公约数即求解x和y，使得上面等式成立。对应地，求解式子

ed+(-k)φ(n)=1中d和-k。14如何求解私钥？5.1.4RSA体制安全性分析（1）穷举攻击

即列出所有可能的私钥，显然这是缺乏效率和困难的。（2）因数分解攻击

给定某个整数

，求c的模n的e次方根

是一个困难问题，但如果整数n的素数分解已知，则上述问题易解。因此，因数分解攻击RSA途径包括：分解n为p和q。直接确定

，而不确定p和q。直接确定d，而不确定

。155.1.4RSA体制安全性分析（3）参数选取不当造成的攻击

选取p和q时应该是随机的且不应太接近。

因为，

，当(p-q)/2很小时，那么(p+q)/2只比

大一点，因此逐个检查大于

的整数x，使得

是一个完全平方数，记为y2，那么就有

：

和

。165.1.4RSA体制安全性分析（4）选择密文攻击

攻击者得到两个明/密文对

、

，则可以获得

的密文结果，因为

由明密文对

，可以获得对

的加密结果，因为

此外，能够获得

的解密结果，就可以恢复出c对应的明文。175.1.4RSA体制安全性分析185.1.4RSA体制安全性分析195.1.5RSA填充加密机制随机填充机制加密消息——优化非对称加密填充OAEP（OptimalAsymmetricEncryptionPadding）机制添加随机元素将确定密码机制（如基本RSA）转换为一个概率机制。部分密文解密（或其他信息泄露），只要不能翻转单向陷门函数，攻击者仍不能解密任何密文部分。20使用相同公钥，加密相同明文能否得到不同密文？5.1.5RSA填充加密机制（1）明文m后面填充k1个0。（2）产生k0比特随机数r。（3）使用G将k0比特随机数r扩展为(n-k0)长度比特串。（4）计算x=m00…0

G(r)。（5）使用H将(n-k0)长度x压缩为长度k0比特串。（6）计算y=r

H(x)。（7）最后输出x||y。21解密操作：（1）恢复随机串r=

y

H(x)。（2）恢复消息m00…0=x

G(r)。

5.1.6RSA签名算法22能否在不安全的通信信道上传输一些公开信息，最终使得双方获得秘密信息？23目录5.1RSA公钥密码算法5.2Diffie-Hellman密钥协商机制5.3ElGamal公钥密码体制5.4椭圆曲线密码体制245.2Diffie-Hellman密钥协商机制D-H密钥协商机制，可以实现在不安全信道中为两个实体建立一个共享秘密，协商的秘密可以作为后续对称密码体制的密钥使用。25信息安全技术基础张浩军5.2Diffie-Hellman密钥协商机制26D-H协商协议描述及实例5.2Diffie-Hellman密钥协商机制27D-H协议中间人攻击基于离散对数难解问题设计的公钥密码算法？28目录5.1RSA公钥密码算法5.2Diffie-Hellman密钥协商机制5.3ElGamal公钥密码体制5.4椭圆曲线密码体制29305.3.1ElGamal加密算法315.3.2ElGamal公钥密码体制的安全性离散对数难解问题，即给定ga，求解a是困难的。325.3.2ElGamal公钥密码体制的安全性335.3.3ElGamal签名算法34如何发现可用于公钥密码体制的代数系统？35目录5.1RSA公钥密码算法5.2Diffie-Hellman密钥协商机制5.3ElGamal公钥密码体制5.4椭圆曲线密码体制365.4.1椭圆曲线基本概念375.4.1椭圆曲线基本概念385.4.1椭圆曲线基本概念395.4.1椭圆曲线基本概念405.4.1椭圆曲线基本概念415.4.1椭圆曲线基本概念425.4.1椭圆曲线基本概念435.4.1椭圆曲线基本概念445.4.1椭圆曲线基本概念455.4.1椭圆曲线基本概念465.4.1椭圆曲线基本概念475.4.1椭圆曲线基本概念485.4.1椭圆曲线基本概念495.4.1椭圆曲线基本概念505.4.1椭圆曲线基本概念515.4.1椭圆曲线基本概念525.4.1椭圆曲线基本概念53椭圆曲线上点群法则规定如下：设P、Q是E上的两个点，连接两个点得到一条直线，如果直线与曲线交叉，则得到第3个点（如图所示得到点R）；如果该直线在其中一个点与曲线相切，则该点计两次；如果直线与y轴平行，则定义第3个点为无穷远点。3．椭圆曲线上加法运算几何含义5.4.1椭圆曲线基本概念543．椭圆曲线上加法运算几何含义5.4.1椭圆曲线基本概念性质：（1）曲线上三个点在一条直线上，则它们的和等于O。（2）曲线上点P，则存在一个负点，记为-P，P+(-P)=O。（3）若一条垂直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．椭圆曲线上加法运算几何含义5.4.1椭圆曲线基本概念563．椭圆曲线上加法运算几何含义5.4.2基于椭圆曲线的加密体制575.4.2基于椭圆曲线的加密体制585.4.2基于椭圆曲线的加密体制595.4.2基于椭圆曲线的加密体制605.4.2基于椭圆曲线的加密体制615.4.2基于椭圆曲线的加密体制625.4.3椭圆曲线D-H密钥协商635.4.4基于椭圆曲线的数字签名算法645.4.4基于椭圆曲线的数字签名算法655.4.5ECC安全强度分析66小结本章介绍公钥密码体制的工作原理和具体实现方法。介绍了典型公钥密码算法，如RSA、ElGamal，以及强度