信息安全技术基础 张浩军 杨卫东 谭玉波 等编著 第5章

第5章公钥密码技术学习目标RSA公钥密码算法及其用于加密和签名的实现。ElGamal公钥密码算法及其用于加密和签名的实现。ECC公钥密码算法及其用于加密和签名的实现。公钥密码算法的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 基本方法和安全性原理。公钥密码体制加密密钥公开，解决了密钥管理与分发的问题。那么如何实现公钥密码呢？本章介绍几个典型的公钥密钥算法，包括基于大数分解难题的RSA算法，基于有限域上求解离散对数难解问题的ElGamal算法，以及基于椭圆曲线上求解离散对数难解问题的ECC算法。目录5.1RSA公钥密码算法5.2Diffie-Hellman密钥协商机制5.3ElGamal公钥密码体制5.4椭圆曲线密码体制如何实现加密密钥公开的加密算法？5.1.1RSA基本算法RSA（public-keycryptography），以当时在MIT的提出者Rivest、Shamir和Adleman三个人的名字命名，于1978年公开描述的。RSA既可以用于加密也可以用于签名。RSA包括公钥和私钥两个密钥，公钥可以让任何人知道并用于加密消息，使用公钥加密的消息只能使用对应的私钥解密。信息安全技术基础张浩军5.1.1RSA基本算法5.1.2RSA加密算法的数论基础定义1（同余）：设a、b、m是正整数，如果m|(a-b)，即m整除(a-b)，则称a和b模m同余，记为定理1：（素数分解定理）：对任意正整数n，存在唯一的正素数序列，以及正整数，使得：。定义2（欧拉数）：设n是一个正整数，，即小于n的与n互素的正整数，称为欧拉数。特别地，当p是一个素数时，则。5.1.2RSA加密算法的数论基础定理2：如果n1和n2互素，则。定理3：如果一个正整数n按“定理1”分解并表示为，则。定理4：（Euler定理，欧拉定理）设x和n都是正整数，如果gcd(x,n)=1，则定理5（Fermat小定理）：设x和p都是正整数。如果p是素数，则5.1.3RSA算法实现中的计算问题概率测试方法，选取特定比特长度的随机数，通过多次迭代进行概率素性测试。例如Fermat素性测试：给定整数n，选择一些与n互素整数a，计算an-1modn，如果结果不是1，则n是合数；若结果是1，n可能是也可能不是素数。如何快速产生素数？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是素数概率。如何快速产生素数？5.1.3RSA算法实现中的计算问题模幂运算满足分配律[(amodn)×(bmodn)]modn=(a×b)modn利用中间结果对n取模，即降低了存储要求，并可实现高效算法。递进式指数计算例如计算ad(modn)，为了便于计算机实现，其中指数d可以表示为k比特二进制(bk-1bk-2...b1b0)2，因此，d可以记为：有：如何快速进行模指数运算？5.1.3RSA算法实现中的计算问题采用扩展欧几里得算法快速计算d：ax+by=gcd(a,b)gcd(a,b)表示a和b的最大公约数即求解x和y，使得上面等式成立。对应地，求解式子ed+(-k)φ(n)=1中d和-k。如何求解私钥？5.1.4RSA体制安全性分析（1）穷举攻击即列出所有可能的私钥，显然这是缺乏效率和困难的。（2）因数分解攻击给定某个整数，求c的模n的e次方根是一个困难问题，但如果整数n的素数分解已知，则上述问题易解。因此，因数分解攻击RSA途径包括：分解n为p和q。直接确定，而不确定p和q。直接确定d，而不确定。5.1.4RSA体制安全性分析（3）参数选取不当造成的攻击选取p和q时应该是随机的且不应太接近。因为，，当(p-q)/2很小时，那么(p+q)/2只比大一点，因此逐个检查大于的整数x，使得是一个完全平方数，记为y2，那么就有：和。5.1.4RSA体制安全性分析（4）选择密文攻击攻击者得到两个明/密文对、，则可以获得的密文结果，因为由明密文对，可以获得对的加密结果，因为此外，能够获得的解密结果，就可以恢复出c对应的明文。5.1.4RSA体制安全性分析5.1.4RSA体制安全性分析5.1.5RSA填充加密机制随机填充机制加密消息——优化非对称加密填充OAEP（OptimalAsymmetricEncryptionPadding）机制添加随机元素将确定密码机制（如基本RSA）转换为一个概率机制。部分密文解密（或其他信息泄露），只要不能翻转单向陷门函数，攻击者仍不能解密任何密文部分。使用相同公钥，加密相同明文能否得到不同密文？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。解密操作：（1）恢复随机串r=yH(x)。（2）恢复消息m00…0=xG(r)。5.1.6RSA签名算法能否在不安全的通信信道上传输一些公开信息，最终使得双方获得秘密信息？目录5.1RSA公钥密码算法5.2Diffie-Hellman密钥协商机制5.3ElGamal公钥密码体制5.4椭圆曲线密码体制5.2Diffie-Hellman密钥协商机制D-H密钥协商机制，可以实现在不安全信道中为两个实体建立一个共享秘密，协商的秘密可以作为后续对称密码体制的密钥使用。信息安全技术基础张浩军5.2Diffie-Hellman密钥协商机制D-H协商 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 描述及实例5.2Diffie-Hellman密钥协商机制D-H协议中间人攻击基于离散对数难解问题设计的公钥密码算法？目录5.1RSA公钥密码算法5.2Diffie-Hellman密钥协商机制5.3ElGamal公钥密码体制5.4椭圆曲线密码体制5.3.1ElGamal加密算法5.3.2ElGamal公钥密码体制的安全性离散对数难解问题，即给定ga，求解a是困难的。5.3.2ElGamal公钥密码体制的安全性5.3.3ElGamal签名算法如何发现可用于公钥密码体制的代数系统？目录5.1RSA公钥密码算法5.2Diffie-Hellman密钥协商机制5.3ElGamal公钥密码体制5.4椭圆曲线密码体制5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念5.4.1椭圆曲线基本概念椭圆曲线上点群法则 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 如下：设P、Q是E上的两个点，连接两个点得到一条直线，如果直线与曲线交叉，则得到第3个点（如图所示得到点R）；如果该直线在其中一个点与曲线相切，则该点计两次；如果直线与y轴平行，则定义第3个点为无穷远点。3．椭圆曲线上加法运算几何含义5.4.1椭圆曲线基本概念3．椭圆曲线上加法运算几何含义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。3．椭圆曲线上加法运算几何含义5.4.1椭圆曲线基本概念3．椭圆曲线上加法运算几何含义5.4.2基于椭圆曲线的加密体制5.4.2基于椭圆曲线的加密体制5.4.2基于椭圆曲线的加密体制5.4.2基于椭圆曲线的加密体制5.4.2基于椭圆曲线的加密体制5.4.2基于椭圆曲线的加密体制5.4.3椭圆曲线D-H密钥协商5.4.4基于椭圆曲线的数字签名算法5.4.4基于椭圆曲线的数字签名算法5.4.5ECC安全强度分析小结本章介绍公钥密码体制的工作原理和具体实现方法。介绍了典型公钥密码算法，如RSA、ElGamal，以及强度更高的椭圆曲线密码体制。描述了相关公钥密码算法的实现机理和对应密码体制的工作过程，讨论了RSA算法具体实现过程中素数产生、模数运算等实际问题。对各种公钥密码体制安全性进行了分析。作业1．使用RSA加密消息，设选取两个素数为71和83，加密明文消息1234，请选择密钥并计算密文，并验证是否能正确解密。2.编写一个RSA加密算法实现程序。3.什么是DH密钥协商机制的中间人攻击，如何避免中间人攻击。4.请验证DSA算法的正确性，即对于合法签名，签名验证算法能够验证签名的有效性。