2011-2012研究生《密码学理论与实践》期末试题

1/222011-2012学年数学专业研究生《密码学理论与实践》期末考试年级：2011学号：2011020680姓名：刘海专业（二级学科）：应用数学研究方向：密码学理论与工程一、解释相关概念及方法（15分）1.计算安全与理论安全；2.IND-CCA2；3.可证明安全方法。二、关于对称密码，完成如下问题（20分）1.叙述DES和AES分别采用什么乘法密码结构？试做一点比较分析；2.选择一个常用的轻量级分组密码与AES进行相关比较分析。三、关于公钥密码学，完成如下问题：（30分）1.简要介绍单向陷门函数的原理，解释如何利用IFP、DLP、ECDLP三大问题构造单向陷门函数实现公钥加密方案的；2.对于RSA方案，试一试解释分解模n和求解n的欧拉函数)(n的难度是一样的；3.设椭圆曲线81132xxy定义在有限域23F上。(1)若椭圆曲线上的二点为P(9,10)、Q(14,13)，求P+Q和2P；(2)求如上椭圆曲线的一个基点G及它的阶，并构造一个简单的ECC-ElGamal密码方案；(3)以如上的G为基点，为Alice和Bob选择一个私钥，用D-H密钥协商方法求出共享密钥。四、请利用多项式19mod)1127()(2xxxh设计一个（3,5）Shamir门限方案来共享密钥k=11。（10分）五、选择一个现代密码方法与技术论述其在某电子商务领域中的应用。（20分）2/22一、答：1、计算安全是指满足以下的标准：破译密码的代价超出密文信息的价值；破译密码的时间超出密文信息的有效生命期；理论安全是指：无论有多少可使用的密文，攻击者无论花费多少时间，都不足以惟一的确定由密文解密得到的明文信息。2、IND(不可区分性)：对已知给定的两个明文，加密者随机一致的选择其中一个进行加密，攻击者无法从密文中知道是对哪个明文的加密。CCA2(适应性选择密文攻击)：敌手在得到目标密文y前后都可询问解密机，但不可询问目标密文y。IND-CCA2是指对于任意的有效CCA2敌手攻击，它的优势都是可忽略的。3、可证明安全方法是是一种归约方法，它通过定义适当的安全目标（一般地，加密方案的安全目标是保密性，签名方案的安全目标是不可伪造性），然后在一定的敌手模型下证明方案或协议能够达到既定的安全目标。二、答：1、Shannon提出的乘积密码是指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果。其示意图如下：3/22f位位，wLi1位位，wRi1K位位，wLi位位，wRi通常使用的技术是将代替密码和置换密码做乘积。DES采用的是Feistel乘法密码结构。其原理是采用对合密码:一种加密函数),(kxf，实现：ntnFFF222的映射。其中，n是分组长度，t是密钥长度。若对每个密钥取值都有xkkxff)),,((，则称之为对合变换。对合加密函数在自密钥控制下对明文进行r轮迭代，后得到密文，密文在其逆序子密钥作用下，进行r轮迭代，就可恢复出明文。Feistel网络将输入（w2位）分成相同长度的两部分iL和iR，按如下方式进行变换：Feistel网络的轮函数可表示为：),(),,(11iiniiRLKRLg其中：1iiRL，),(11iiiikRfLR函数f并不要求是可逆的，因为只要密钥给定，轮函数g一定是可逆的。具体为：),(1iiiikLfRL，iiLR14/22Feistel加解密过程如下图：Feistel网络结构的特点：逆向操作和正向操作具有相同的结构唯一不同之处是轮子密钥的使用次序相反。每轮只对轮输入的一半进行变换，虽然实现速度较慢，但可以不要求f函数可逆。AES采用的是SP（代换—置换）网络乘法密码结构。其原理是采用迭代密码：以一个简单函数，进行多次迭代。每次迭代，称为一轮，相应的迭代函数称为轮函数。迭代密码明确定义了一个轮函数和一个密钥编排方案，一个明文的加密5/22SSS1tKSSSPSSSP1K2KSSSPtK经过了t轮类似的过程。设k是一个确定长度的随机二元密钥，用k通过密钥编排方案来生成t个轮密钥。一个SP网络就是一类特殊的迭代密码。设l和m都是正整数，明密文都是长为lm的二元向量，一个SP网络包含两个变换，分别记为s和p：lls}1,0{}1,0{:实现l比特的代换，即S盒；},,2,1{},,2,1{:lmlmp实现lm比特的置换；在SP网络中，前t轮都先经过非线性变换S，然后再进行P置换，而最后1t轮中，只使用非线性变换S。SP网络的框图结构如下：在SP网络中，非线性代换S得到分组小块的混乱和扩散；再利用P置换，将S盒输出的结果实现整体扩散的效果。这样，若干轮的局部混乱、整体扩散之后，达到足够的混乱和扩散。在SP网络结构中，常使用的基本代换有：左循环移位代换：),,,,(),,,(:0121110xxxxxxxfnn；右循环移位代换：),,,(),,,(:201110nnnxxxxxxf；模12n代换；6/22线性变换：Txy；仿射变换：bTxy；通过上述比较，我们发现：Feistel网络乘法密码结构，每轮对一半数据进行变换，密码变换不要求可逆，几乎没有任何数学理论的支撑。SP网络乘法密码结构：每轮对所有输入数据进行变换，要求所有密码变换都可逆，具有良好的数学理论的支撑。2、作为信息传递和处理的网络，全面感知、可靠传送和智能处理是物联网的核心功能。要实现可靠传送必须以密码算法为基础提供相应的安全服务。而与物联网关系密切，也需要密码算法作为基础支撑的无线传感网络也是近年来发展迅猛的领域之一。作为密码算法的使用环境，无线传感器和物联网具有共同的特征：它们的应用组件不同于传统的台式机和高性能计算机，而是计算能力相对较弱的嵌入式处理器；由于应用环境的关系，计算可使用的存储往往较小；考虑到各种设备的功能需求，能耗必须限制在某个范围内。因此传统密码无法很好的适用于这种环境中，就使得受限环境中密码算法的研究成为一个热点。适宜于资源受限环境使用的算法就是所谓的轻量级密码。轻量级分组密码与传统分组密码相比有几个特点：资源受限的应用环境通常处理的数据规模比较小。RFID和传感器等应用通常对安全性要求不是很高。轻量级分组密码大多采用硬件实现，追求的首要目标是实现占用的空间及实现效率。7/22现有的典型轻量级分组密码大致有以下几种：PRESENT、HIGHT、mCryoton、CGEN、DESL、MIBS、TWIS、KATAN&KTANTAN、TEA&XTEA、SEA和LBlock。LBlock是我国学者吴文玲等人在2010年设计的一个轻量级分组密码，中文名为“鲁班锁”，LBlock是LuBanlock的缩写，也有LightweightBlockcipher的意思。其分组长度为64bit，密钥长度为80bit，采用Fesitel类结构，每轮有一半数据进入轮函数，另一半做简单的循环移位。其加密算法由32轮迭代运算组成，对64bit的明文01||XXP，加密过程如下：对33,,2,1i，计算)8(),(2111iiiXKXFXCXX3332||为64bit的密文。其中，基本模块如下定义：轮函数323232}1,0{}1,0{}1,0{:F，))((},{iiKXSPUKX。函数S函数S是函数F的一部分，由8个44的S盒并置而成，定义为：3232}1,0{}1,0{:S0123456701234567||||||||||||||||||||||||||||ZZZZZZZZZYYYYYYYYY)(777YsZ，)(666YsZ，)(555YsZ，)(444YsZ，)(333YsZ，)(222YsZ，)(111YsZ，)(000YsZ函数P由8个4bit字的位置变换，定义为：3232}1,0{}1,0{:P8/220123456701234567||||||||||||||||||||||||||||UUUUUUUUUZZZZZZZZZ67ZU，46ZU，75ZU，54ZU，23ZU，02ZU，31ZU，10ZU其解密算法是加密算法的逆。而其密钥扩展算法为将密钥01767879kkkkkK放在80bit的寄存器中，取寄存器左边的32位作为轮密钥1K，然后执行如下步骤：对31,,2,1i，按如下方式更新寄存器29K。][][76777879767778799kkkkkkkks，][][72737475727374758kkkkkkkks。24647484950][][ikkkkk取寄存器左边的32位作为轮密钥1iK。LBlock与AES的比较：在AES中，其密钥长度可以为128位、192位和256位，而LBlock其密钥长度为80bit。在AES中，其分组长度为128位，而LBlock其密钥长度为80bit。AES采用SP结构，每轮对所有输入数据进行变换，要求所有密码变换都可逆。而LBlock采用Feistel网络乘法密码结构，每轮对一半数据进行变换，但其密码变换也可逆。在AES中，S盒被定义为1616个字节组成的矩阵，而在LBlock中，S盒被定义为44个字节组成的矩阵。在硬件实现中，AES的S盒最好的实现需要200多GE，而LBlock的10个S盒都可以用大约22个GE实现。三、答：9/221、单向陷门函数RDxft:)(，是一个单向函数，即对任意的Dx，容易计算，而对几乎所有的Dx，求逆困难。但是，如果知道门限信息t，则对所有的Ry，容易计算满足)(xfyt的Dx。IFP（整数分解问题）：假设pqN是大整数，p，q为两个素数，且p，7682q。输入：N。输出：素数p，q。这一困难问题就称为IFP（整数分解问题）。利用IFP构造的公钥加密方案，如RSA方案：假设M为明文，C为密文。选择两个大素数p，q；计算pqN，)1)(1()(qpN；选择整数e，使得1))(,gcd(Ne计算)(mod1Ned。公钥},{NeKU，私钥},{ndKR加密算法：nMCemod；解密算法：nCMdmod；DLP（离散对数问题）：假设p为素数，定义一个pZ的子集}1),gcd(|{*paZaZpp。输入：*pZ的生成元和一个元素*pZ。输出：x，使得pxmod。这一困难问题称为DLP（离散对数问题）。10/22利用DLP构造的公钥加密方案，如ElGamal方案：假设明文为M，密文为),(21CC。密钥创建：随即选择素数p；计算*pZ上的一个随机生成元g；随机选取1pZx作为其私钥；计算pgyxmod；把),,(ygp作为其公钥公开，把x作为私钥进行保存。加密算法：随即选择1pZk；计算pgCkmod1；计算pMyCkmod2；解密算法：计算pCCMxmod12ECDLP（椭圆曲线离散对数问题）：假设E是定义在有限域pF上的一个椭圆曲线，P是)(pFE上的一个点，并且假设P的阶为素数n，令dPQ，其中]1,1[nd。输入：P,Q输出：d这一困难问题就称为ECDLP（椭圆曲线离散对数问题）。利用ECDLP构造公钥加密方案，公开参数),,,(nPEp，将d作为私钥，Q作为公钥。假设m为明文，),(21CC为密文：11/22加密算法：Mm，M是)(pFE上的一个点；选择]1,1[nk；计算kPC1；计算KQMC2;输出密文),(21CC解密算法：计算12dCCM；mM；输出明文m；在上述描述中，将输出作为单向陷门信息，即私钥，而将输入作为2、在RSA方案中，在密钥建立阶段，用户Alice要执行：1)随机选择两个素数p和q，满足qp；2)计算pqn；3)计算)1)(1()(qpn；如果已知n的分解pqn