西华大学：《密码学 Cryptology》课程教学资源（习题）第1章 公钥密码体制习题

第1章公钥密码体制习题 1.在群Z*1中:(有多少生成元?(n)找出它的所有生成元。(i)找出它的 所有子群。 2.令n是一个奇合数且不是素数的幂,群Z*有生成元吗? 3.为什么有限环或域的特征一定是素数? 4.利用多项式的长除法作为子程序,构造多项式的扩展欧几里德算法 5.令n是任意自然数,构造n比特整数{0,1}n的有限域 6.査阅文献,举例说明NTRU的加密解密方法。NRU的安全性基础是什么? 7.离散对数问题与计算 Diffie-Hellman问题有什么关系? 8.在RSA公钥数据(e,N)中,为什么加密指数e必须与O(N)互素? 9.通常情况下分解奇合数是困难问题。那么分解素数的幂也是困难问题吗?( 个素数幂是N=p,其中p是素数,i是整数。分解N)提示:对任意>1,计 算N的次根需要尝试多少个指数值i? 10.假设N是一个素数幂,前面问题中“计算N的i次根”的其中一种方法是 二分查找。设计一个二分査找算法求p的i次(i是知道的)根。证明这是 种有效的方法 11.RSA加密函数是模RSA模数的乘群的一个置换,所以RSA函数也称为单向 陷门置换。 Rabin(elgamal)加密函数是单向陷门置换吗? 12.假设N≈21024。在Z*中随机选取元素,选取的元素小于264的概率是多少? 用这个结果解释不应当把一个64比特的随机密码口令当作RSA ( Rabin, ElGamal)加密算法的随机明文原因。 13.在什么情况下可以把 EIGamal密码体制看作确定的算法? 14.什么是混合密码体制?混合密码体制的优点是什么? 15.什么是CPA,CCA,CCA2?请解释这些概念

第1章 公钥密码体制 习题 1. 在群Z*11 中：(i) 有多少生成元？(ii) 找出它的所有生成元。(iii) 找出它的 所有子群。 2. 令n 是一个奇合数且不是素数的幂，群 Z*n有生成元吗？ 3. 为什么有限环或域的特征一定是素数？ 4. 利用多项式的长除法作为子程序，构造多项式的扩展欧几里德算法。 5. 令n 是任意自然数，构造 n 比特整数{0，1}n 的有限域。 6. 查阅文献，举例说明NTRU的加密解密方法。NTRU的安全性基础是什么？ 7. 离散对数问题与计算Diffie-Hellman 问题有什么关系？ 8. 在RSA 公钥数据(e, N)中，为什么加密指数e 必须与¦Õ(N)互素？ 9. 通常情况下分解奇合数是困难问题。那么分解素数的幂也是困难问题吗？（一 个素数幂是N=p i，其中p 是素数，i 是整数。分解N） 提示：对任意i>1，计 算N 的i 次根需要尝试多少个指数值i？ 10. 假设N 是一个素数幂，前面问题中“计算N 的i 次根”的其中一种方法是 二分查找。设计一个二分查找算法求p i 的i 次（i 是知道的）根。证明这是一 种有效的方法。 11. RSA 加密函数是模RSA 模数的乘群的一个置换，所以RSA 函数也称为单向 陷门置换。 Rabin(ElGamal)加密函数是单向陷门置换吗？ 12. 假设N≈2 1024。在ZN*中随机选取元素，选取的元素小于2 64 的概率是多少？ 用这个结果解释不应当把一个64 比特的随机密码口令当作RSA （Rabin,ElGamal）加密算法的随机明文原因。 13. 在什么情况下可以把ElGamal 密码体制看作确定的算法？ 14. 什么是混合密码体制？混合密码体制的优点是什么？ 15. 什么是CPA，CCA，CCA2？请解释这些概念