密码学复习资料

一、DES1.穷举攻击分析（1）穷举攻击就是对所有可能的密钥逐个进行解密测试,直到找到正确密钥为止的一种攻击方法.（2）穷举攻击判断正确密钥的方法将利用试验密钥解密得到的可能明文与已掌握的明文的信息相比较，并将最吻合的那个试验密钥作为算法输出的正确密钥。（3）穷举攻击又称为穷尽攻击、强力攻击、蛮干攻击等。只要明文不是随机的，就可实施穷举攻击。2.简述DES算法中S盒的特点：答：（1）具有良好的非线性，既输出的每一个比特与全部输入比特有关；（2）每一行包括所有的16种4位二进制；（3）两个输入相差1bit时，输出相差2bit；（4）如果两个输入刚在中间2个比特上不同，则输出至少有两个比特不同；（5）如果两个输入前两位比特不同而最后两位相同，则输出一定不同；（6）相差6bit的输入共有32对，在这32对中有不超过8对的输出相同；（7）S盒是DES中唯一非线性部分。3.为什么二重DES并不像人们想象的那样可以提高密钥长度到112bit，而相当于57bit？简要说明原因。答：已知明文攻击可以成功攻击密钥长度为112位的二重DES，其计算量级位2的56次方，与攻击DES所需的计算复杂度2的55次方相当，两者基本在同一个数量级，因此，二重DES并不能从根本上提高其安全性。4.DES的S盒的设计标准:1.S盒的每一位输出都不是输入的线性或仿射函数。2.S盒的输入发生1比特变化，输出至少有2比特发生变化。3.当固定S盒的1位输入时，S盒的每一位输出中0和1的个数尽可能平衡。5.在DES算法中，如果给定初始密钥K，经子密钥产生的各个子密钥都相同，则称该密钥K为弱密钥，DES算法弱密钥的个数为（4）6.DES算法可以划分两步：第一步是子密钥的生产，第二步是数据处理。它的分组长度是64位，有效密钥长度56位。3DES是DES的一种变种，如它采用3个不同的工作密钥，使得整个密钥的长度为【168】位。7.Feistel模型是分组密码的经典模型；它的实现依赖于哪些参数它们分别如何影响安全性?答：1分组长度：分组较长意味安全性越高，但是会降低加密和解密的速度。2密钥长度：密钥较长意味安全性越高，但是会降低加密和解密的速度。3迭代轮数;虽然本质在于单轮不能提供足够安全性而多轮加密可取很高安全性典型值164子密钥产生算法：子密钥产生越复杂，密码分析攻击就越困难。5轮函数;越复杂越安全。8.使用多个DES密钥执行多重加密可以增加安全性；但是双重DES由于中间相遇攻击而并没有相应地增加安全性。9.DES算法提出以后；密码分析方法也取得相应进展，提出了差分和线性密码分析，其中差分密码分析只有在有相当多的密文条件下，才具有理论意义。10.写出Feistel网络的算法步骤。答：将明文m分为等长的两部分m=(L(0),R(0))；使用由密钥k控制的高度非线性函数F，（1）计算：(L’,R’)=(L(0)‘+’F(R(0),k),R(0))；（2）计算密文：c=(L(1),R(1))=(R’,L’)。11.DES加密法需要经过E盒、S盒、P盒三个过程。二、AES,1.简述DES与AES的相同之处：二者的圈函数都是由3层构成，非线性层，线性混合层，子密钥异或，只是顺序不同；AES的子密钥异或对应于DES中S盒之前的子密钥异或；AES的列混合运算的目的是让不同的字节相互影响，而DES中的F函数的输出与左边的一半数据相加也有类似的效果；AES的非线性运算是字节代换，对应于DES中唯一的非线性运算S盒：行移位运算保证了每一行的字节不仅仅影响其他行对应的字节，而且影响其他行所有的字节，这与DES中置换P相似。2.AES算法由四个操作构成：字节代换、行移位、列混淆、轮密钥加。3.分组密码的加解密算法中最关键部分是非线性运算部分，那么，DES加密算法的非线性预算部分是指非线性代换，AES加密算法的非线性运算部分是指字节代换。4.在高级加密标准AES规范中，分组长度只能是128位，密钥的长度可以是128位、192位、256位中的任意一种。5.DES与AES不同之处：AES密钥长度可变DES不可变，DES面向比特运算AES面向字节运算。6.写出Rijndael轮函数（普通轮）的四个不同的计算部件名称。答：RIJNDAEL的轮函数由四个不同的计算部件所组成，分别是：字节代替（ByteSub）行移位（ShiftRow）列混合（MixColumn）加密钥（AddRoundKey）设Rijndael的字节代替函数为y=bytesub(x)。计算sub(0)。（1）首先，将字节看作GF(28)上的元素，映射到自己的乘法逆；0字节影射到它自身。（2）其次，将字节看作GF(2)上的8维向量，做如下的（GF(2)上的；可逆的）仿射变换：三、RSA,1.写出RSA的密钥生成过程。密钥的产生：（1）选择两个保密的大素数p和q；（2）计算n=p×q，j(n)=(p-1)(q-1)，其中j(n)是n的欧拉函数值；（3）选一整数e，满足1<e<j(n)，且gcd(j(n),e)=1；（4）计算d，满足d?e≡1modj(n)，即d是e在模j(n)下的乘法逆元。因e与j(n)互素，模j(n)的乘法逆元一定存在；（5）以{e,n}为公开钥,{d,p,q}为秘密钥。2.写出基本RSA的加密过程和解密过程。加密：加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n；然后对每个明文分组m，作加密运算：c≡mEmodn；解密：对密文分组的解密运算为：m≡cDmodn。3.RSA的数论基础是数论的欧拉定理，在现有的计算能力条件下，RSA被认为是安全的最小密钥长度是1024位。四、MD5,1.简述MD5算法？答：（1）附加填充位；（2）初始化链接变量；（3）分组处理；（4）步函数。五、费尔马定理：若p是素数，a是正整数且gcd(a,p)=1，则a（（p-1））≡1modp。六、欧拉函数：设n是一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为φ(n)欧拉定理：若a和n互素，则a（（φ(n)））≡1modn。七、中国剩余定理，八、简述密码分析者对密码系统的四种攻击。答：密码分析者对密码系统的常见的攻击方法有：1)唯密文攻击：攻击者有一些消息的密文，这些密文都是采用同一种加密方法生成的。2)已知明文攻击：攻击者知道一些消息的明文和相应的密文。3)选择明文攻击：攻击者不仅知道一些消息的明文和相应的密文，而且也可以选择被加密的明文。4)选择密文攻击：攻击者能选择不同的被加密的密文，并得到对应的明文。九、RSA计算过程，十、公钥分配过程。单钥密码体制在进行密钥分配时,要求通信双方或者已经有一个共享的密钥，或者可籍助于一个密钥分配中心。①用户A向公钥管理机构发送一个带时戳的消息，消息中有获取用户B的当前公钥的请求。②管理机构对A的请求作出应答，应答由一个消息表示，该消息由管理机构用自己的秘密钥SKAU加密，因此A能用管理机构的公开钥解密，并使A相信这个消息的确是来源于管理机构。③A用B的公开钥对一个消息加密后发往B，这个消息有两个数据项:一是A的身份IDA，二是一个一次性随机数N1，用于惟一地标识这次业务。④B以相同方式从管理机构获取A的公开钥（与步骤①、②类似）。这时，A和B都已安全地得到了对方的公钥，所以可进行保密通信。然而，他们也许还希望有以下两步，以认证对方。⑤B用PKA对一个消息加密后发往A，该消息的数据项有A的一次性随机数N1和B产生的一个一次性随机数N2。因为只有B能解密③的消息，所以A收到的消息中的N1可使其相信通信的另一方的确是B。⑥A用B的公开钥对N2加密后返回给B，可使B相信通信的另一方的确是A。十一、密码分类：代换密码、置换密码、HILL密码、轮转密码。密码学分类单钥体制双钥体制十二、攻击分类：1.被动攻击（窃听）2.主动攻击（中断、篡改、伪造）十三、预防十四、各种算法输入输出位数DES64比特明文56比特密钥输出64比特密文AES128192256比特RSA输入664比特MD5输入512比特分组128比特输出十五、秘钥分配管理，1密钥分配管理两个用户A和B获得共享密钥的方法包括：①密钥由A选取并通过物理手段发送给B。②密钥由第三方选取并通过物理手段发送给A和B。③如果A、B事先已有一密钥，则其中一方选取新密钥后，用已有的密钥加密新密钥并发送给另一方。④如果A和B与第三方C分别有一保密信道，则C为A、B选取密钥后，分别在两个保密信道上发送给A、B2密钥分配①A向KDC发出会话密钥请求②KDC为A的请求发出应答。②A存储会话密钥，并向B转发EKB[KS‖IDA]。④B用会话密钥KS加密另一个一次性随机数N2，并将加密结果发送给A。⑤A以f(N2)作为对B的应答，其中f是对N2进行某种变换（例如加1）的函数，并将应答用会话密钥加密后发送给B。3公钥分配①用户A向公钥管理机构发送一个带时戳的消息，消息中有获取用户B的当前公钥的请求。②管理机构对A的请求作出应答，应答由一个消息表示，该消息由管理机构用自己的秘密钥SKAU加密，因此A能用管理机构的公开钥解密，并使A相信这个消息的确是来源于管理机构。③A用B的公开钥对一个消息加密后发往B，这个消息有两个数据项:一是A的身份IDA，二是一个一次性随机数N1，用于惟一地标识这次业务。④B以相同方式从管理机构获取A的公开钥（与步骤①、②类似）。这时，A和B都已安全地得到了对方的公钥，所以可进行保密通信。然而，他们也许还希望有以下两步，以认证对方。⑤B用PKA对一个消息加密后发往A，该消息的数据项有A的一次性随机数N1和B产生的一个一次性随机数N2。因为只有B能解密③的消息，所以A收到的消息中的N1可使其相信通信的另一方的确是B。⑥A用B的公开钥对N2加密后返回给B，可使B相信通信的另一方的确是A。十六、杂凑、强单向杂凑，1.叙述杂凑函数应该满足的3条性质。答：1.等长性,2.单向性.3.无碰撞性.十七、欧几里得，扩展的欧几里得1.求最大公因子Euclid算法是基于下面一个基本结论：对任意非负整数a和正整数b，有gcd(a,b)=gcd(b,amodb)。2.求乘法逆元如果gcd(a,b)=1，则b在moda下有乘法逆元（不妨设b<a），即存在一x(x<a)，使得bx≡1moda。推广的Euclid算法先求出gcd(a,b)，当gcd(a,b)=1时，则返回b的逆元。1.求最大公因子Euclid算法是基于下面一个基本结论：对任意非负整数a和正整数b，有gcd(a,b)=gcd(b,amodb)。2.求乘法逆元如果gcd(a,b)=1，则b在moda下有乘法逆元（不妨设b<a），即存在一x(x<a)，使得bx≡1moda。推广的Euclid算法先求出gcd(a,b)，当gcd(a,b)=1时，则返回b的逆元。十八本原根，本原根的定义：素数p的原根定义：如果a是素数p的原根，则数amodp,a^2modp,…,a^(p-1)modp是不同的并且包含1到p-1的整数的某种排列。特别地，如果a是素数p的本原根，则a,a^2,…,a^(p-1)在modp下都不相同。本原根的性质：若A为模n的本原根，则A，A的平方，A的3次方，……，A的φ(n)次方模n的余数互不相同，而且构成一个模n的简化剩余系。本原根的应用：应用本原根可以证明：若x的[φ(n)/2]次方模n余1，则x为模n的二次剩余；若x的[φ(n)/2]次方模n余-1，则x为模n的非二次剩余。十九、数字签名1、执行方式:数字签字的执行方式有两类：直接方式和具有仲裁的方式(1)直接方式指数字签字的执行过程只有通信双方参与，并假定双方有共享的秘密钥或接收一方知道发方的公开钥(2)具有仲裁的方式:发方X对发往收方Y的消息签字后，将消息及其签字先发给仲裁者A，A对消息及其签字验证完后，再连同一个表示已通过验证的指令一起发往收方Y。此时由于A的存在，X无法对自己发出的消息予以否认。在这种方式中，仲裁者起着重要的作用并应取得所有用户的信任。2、数字证书产生过