密码学复习

选择判断：
1. 什么人提出什么思想？
a。 MD5 1992年 R.Rivest
SHA系列 (SHA-0、SHA-1、SHA-2) 时间：1993年，1995年的修改版称为SHA-1 开发者：NIST、NSA 比MD5慢
二者被王小云破译
b。 哥伦布三假设：在一个周期内，0和1出现的个数至多相差1；
在一个周期内，长度为i的游程个数占游程总数的1/2的i次方，i=1,2,3..且在长度为i的游程中，“0游程”与“1游程”数目至多相差一个；
异相自相关函数是一个常数。
c. 1971年，IBM公司由Horst Feistel领导研究出LUCIFER密码算法，并应用于商业领域。
1973年，美国NBS公布征求加密标准的建议。IBM 提交了研究成果。
1977年1月15日，被批准为联邦标准[FIPS PUB 46]，并设计推出DES芯片(LUCIFER的改进版)。
美国ANSI、ISO先后将其作为标准 1998年，NSA宣布不再批准DES作为联邦标准。
DES虽然已有替代的数据加密标准(AES)，但它是一种最有代表性的分组加密体制。
DES发展史确定了发展公用标准算法的模式。
d. 1999年1月，电子前沿基金会(Electronic Frontier Foundation)仅用22小时15分钟，就宣告破解了一个DES的密钥。
1985年，3DES成为美国的商用加密标准[RFC 2420]。
RSA公司的R.Rivest提出DESX作为DES的扩充版本。e. IDEA 由来学嘉与J.Massey提出 明文分组/密文分组：64比特 密钥：128比特 目前是PGP的一部分KASUMI 3G的标准加密算法
2001年11月，最终标准[FIPS PUB197]出版。Rijndael改名为AES.
e. 对CBC-MAC变长消息抗伪造的改进：
@追加消息长度为最后一个分组 被Bellare和Rogaway等人所破译
@前缀长度
@长度密钥分离
@再加密
f. 1996年，Bellare等人提出HMAC
1997年，作为RFC2104发表，成为事实上的Internet标准 IPSec协议等安全协议都使用HMAC算法
g. 1976年，Diffie与Hellman提出公钥密码体制的设想，和Diffie-Hellman密钥交换方案 h. 1978年，由MIT的三位密码学家Rivest，Shamir，Adleman联合发明RSA加密算法。
1992年，ISO颁布的国际标准X.509中，将RSA算法正式纳入国际标准。 i. 1994年，美国正式颁发美国数字签名标准DSS
1995年，我国制定自己的签名标准(GB15851-1995)
1999年，美国参议院已通过了立法，规定电子数字签名与手写签名的文件、邮件在美国具有同等的法律效力。
2004年，我国颁发《中华人民共和国电子签名法》
j. ELGAMAL签名方案于1985年提出，其变型已被NIST采纳为数字签名算法。（DSA）
k. 1985年，N.Koblitz(华盛顿大学) 和 https://www.doczj.com/doc/f01734464.html,ler(IBM)分别独立提出了椭圆曲线密码体制(ECC)的思想
国外已有用ECC进行加解密的产品出现在市场上。
目前，ECC标准化正在进行中。虽然还没有统一的标准方案，但已有一些较为成熟的标准出现
如 IEEE（P1363

）， ANSI X9F1工作组（X9.42，X9.62和X9.63）， ISO/IEC L. Menezes,Okamoto,Vanstone发表一篇论文，公布有限域上一种特殊的椭圆曲线——超奇异椭圆曲线。 存在被称为双线性映射(pairing)的有效算法，将该类曲线上的两个点映射到基域上的一个元素。
m. 基于身份的密码学（IBC）的提出 Adi Shamir 1984年


2.很多算法中，哪些属于公钥密码，哪些属于对称密码
对称密码加解密使用相同的密钥，包含流密码（序列密码）【不可预测性是流密码理论的核心】、分组密码【两种基本技术：混乱方法代换和扩散方法置换】；一次一密，DES,
公钥密码加解密时使用不同的密码，公钥用于加密，私钥用于解密【单向函数的概念是公钥密码学的中心概念】椭圆曲线密码体制ECC，双线性映射、MOV规约，基于身份的密码学IBC,公钥证书 PKI，

3. DES里面明文多长，密文多长，密钥有效长度
明文分组、密文分组、密钥长度都是64比特， 有效密钥长度56比特(有8比特奇偶校验位)。

4. 公钥理论
加密与解密由不同的密钥完成
公钥——用于加密，任何人都可以知道(包括攻击者)
私钥——用于解密，必须保密
公钥密码算法应满足的条件：
产生密钥对是计算上容易的
用公钥加密明文是计算上容易的
知道私钥，解密密文是计算上容易的
通过密文和公钥，恢复出明文，或计算出私钥是计算上不可行的
以上要求的本质在于，公钥密码算法需要一个陷门单向函数， 研究公钥密码算法就是先找出合适的陷门单向函数，在其基础上构造算法
5. “P是否等于NP”是计算复杂性理论的中心问题。
p用确定性图灵机在多项式时间内解决问题，np问题存在证书，非确定性图灵机通过猜测解决。
存在两种可能的关系，p属于np，或者p等于np
BPP是概率图灵机，已知p属于Bpp，儿np不属于bpp，所以推出p不等于np
P不等于NP猜想是安全加密算法存在的必要条件，但不是充分条件。

6。 信息安全三要素
机密性、完整性、可用性

7. 单向函数（存在，不存在）
没有人证明单向函数是否真的存在，也没有实际的证据能够构造出真正的单向函数 。
但是，有很多函数看起来像单向函数， 我们能有效地计算它们，且至今还不知道有什么办法能容易地求出它们的逆

8.椭圆曲线
非奇异椭圆曲线：E:y^2=x^3+ax+b 包含所有解及无穷远点O 条件为 4a^3+27b^2≠0(保证有三个不同解的充要条件）=0时为奇异椭圆曲线
单位元：无穷远点O 逆元：设P=(x,y)∈E，则P的逆元定义为-P=(x,-y)
对任意P,Q∈E，设P=(x1,y1),Q=(x2,y2)，计算P+Q时考虑以下三种情况：
1>x1≠x2 时 画一条通过P、Q的直线

与椭圆曲线交于R，R的逆元便是P+Q的结果
设p+q=（x3，y3） x3=λ^2-x1-x2 y3=λ(x1-x3)-y1 其中λ=(y2-y1)/(x2-x1)
2>x1=x2 且 y1=-y2 时，P与Q互为逆元 此时，P+Q=O
3>x1=x2 且 y1=y2 时，则P=Q (点P与自己相加) 画一条通过P的切线，与椭圆曲线交于R，R的逆元便是P+P的结果
设p+q=（x3，y3） x3=λ^2-2*x1 y3=λ(x1-x3)-y1 其中λ=(3*x1^2+a)/(2*y1)
[图位于ppt第8单元第10,11,12页]

大题：
一：
1.欧拉函数怎么计算

性质：若p、q都是素数，则 φ(p) = p - 1 φ(p×q) = φ(p)φ(q) = (p - 1)(q - 1)
上述性质成立的基本原理 小于p的正整数都与p互素，因此φ(p) = p - 1。
定理：若p为素数，k为正整数，则 φ(p^k)＝p^k-1*(p－1)
推论：若gcd(a,b)＝1，则 φ(ab)＝φ(a)φ(b)
2.欧拉定理怎么用

欧拉定理
设n≥2，如果gcd(a,n)=1，则 a^φ(n)≡1 (mod n),
同理有 a^φ(n)＋1≡ a (mod n)
求 13^2001 mod 60
解: 因为gcd(13，60)＝1，则可用欧拉定理计算，故而有13^φ(60)≡1(mod 60)
容易求得 φ(60)＝16
故而，13^16≡1(mod 60)
所以，13^2001＝13^(16×125+1) ≡ 13 (mod 60)
3.费马小定理

费马小定理：
若p是素数, 且gcd(a,p)=1,则
a^p-1 ≡ 1 (mod p)
同理有 a^p ≡ a (mod p)
例:求310^198 mod 199。
解: 因为199是素数,且gcd(310,199)=1，
根据费马小定理，有 310^(199-1 )≡1 (mod 199)
所以, 310^198 ≡1 (mod 199)

二：
1·MAC算法是不安全的。
证明：
证明以下MAC算法在选择消息攻击下是不安全的
MACk(m)=Ek(x1)⊕...⊕Ek(xn),期中m=x1...xn,其中Ek(?)是一个加密算法。
证明：
1>攻击者向Oracle询问消息m=x1...xn
2>oracle返回相应的MAC，记为y，即有y=MACk(m)=Ek(x1)⊕...⊕Ek(xn)
3>于是，攻击者可以概率1产生一个有效伪造（m',y),其中m'=xn...x1,y=MACk(m)=MACk(m'),伪造了一个合法的mac。

2.hash函数不是单向的
例子：设f:{0,1}^m->{0,1}^m是一个原象稳固的双射。
给定消息x∈{0,1}^2m，记为 x=x'‖x''，其中 x',x''∈{0,1}^m
定义Hash函数H:{0,1}^2m->{0,1}^m如下：
H(x)=f(x'⊕x'') 证明不是第二原象稳固的
思路： 给定任意x，以及其散列值H(x)=y，寻找x的碰撞m，使之有相同的散列值，即H(m)=y证明：给定任意消息x=x'‖x''，其散列值为H(x)=f(x'⊕x'')=y
1>如果x'≠x''，则令m=x''‖x’，有H(m)=f(x''⊕x')=(x'⊕x'')=y，因此m和x是一对碰撞
2>如果x'=x''，则H(x)=f(0)=y，令m=m'‖m'，有H(m)=f(0)=y 故而, m和x是一对碰撞 因此，H不是第二原象稳固的，所以此hash函数不是单向的。
三：
1.RSA..ELGAMAL..签名算法怎么描述
RSA算法：
系统建立
随机选择大素数p、q，计算n＝pq
随机选取e <φ(n)，且gcd(e,φ(n))=1计算d，使 ed≡1 mod φ(n)
(e，n)为公钥
d 为私钥 【与RSA加密方案的系统建立过程完

全一样】
签名：s＝m^d mod n, m∈Z*n(*为星花)
验证：m ?＝s^e mod n
【加解密：
加密：c＝m^e mod n, m∈Z*n
解密：m＝c^d mod n】

ELGAMAL算法签名：
系统建立
随机选择大素数p, 及生成元g∈Z*p
随机选取0＜x≤p-2，计算 y=g^x mod p公钥是(p,g,y)
私钥是x 【与ElGamal加密方案的系统建立过程完全一样】
签名 :对消息m，随机选择0＜r≤p-2，然后计算：u = g^r mod p s = r^-1*(m - xu) mod (p-1) m的签名为(u,s)
验证 :对于消息/签名 (m,(u,s))，如果： y^u*u^s ≡ g^m (mod p) 则(u,s)是m的有效签名
【加解密：
加密: 设明文m∈Z*p 随机选择整数r (0＜r≤p-2) 计算c1= g^r mod p, c2=y^r*m mod p 密文是(c1,c2)
解密： 计算明文 m = c2c1^-x mod p 】

2.存在性伪造的原理，如何抵抗存在性伪造，改版以后的算法
存在性伪造的原理：
基本思想是将产生签名的思路反过来：
先选择s，再构造相应的消息m,使得Ver pk(m,s)=true
这样不知道私钥sk，也可以产生满足验证算法的消息和签名

如何抵抗：
利用hash函数的单向，抗碰撞等性质抵抗“存在性伪造”
将对消息m签名改为对H（m）或H(m,u)签名

改版后的算法：
针对RSA算法
签名：s = H(m)^d mod n
验证：H(m) ?= s^e mod n
改版后可以抵抗存在性伪造：攻击者随机选择s,用签名者公钥计算h=s^e mod n但计算一个m，使得H(m)=h在计算上不可行
改版后可以抵抗利用两个消息的签名产生新消息的签名：
因为(H(m1)H(m2))^d ≠ H(m1m2)^d (mod n)针对ELGAMAL算法
签名 ：u=g^r mod p, s=r^-1*(H(m,u) - xu) mod (p-1) 其中Hash函数H:{0,1}*->Zp 则m的签名为(u,s)验证 :对于消息/签名(m,(u,s))，如果: y^u*u^s = g^H(m,u) mod p 则(u,s)是m的有效签名。

四：实体认证
第九章口令认证机制怎么样，优缺点
口令是最常用的认证机制，利用口令进行实体认证,但安全性较差
1.Needham口令认证协议:
利用Hash函数存储口令，防范攻击者偷取数据库后得到口令 .简单有效，广泛应用于各种系统中.
但缺点是 无法防范攻击者在线窃听口令， 无法防范离线字典攻击。
2.一次性口令机制：
可防范在线窃听口令，每次认证使用不同的口令 。
要求用户和系统共享很多口令 ，但管理和保护大量的口令在技术上很困难 。
为克服这一缺点，Lamport提出利用多次Hash的方法实现一次性口令机制。
这种实现必须保持同步 ，但可能因为不可靠信道或死机出现丢失同步的情况(有可能是攻击者的破坏所致)


利用SSL建立安全信道，再进行基于口令的认证 。应用方便，安全保护对用户透明。


加密的密钥交换(EKE)协议：
可以抵抗在线口令窃听、离线字典攻击
EKE的独创性在于前两轮：
第①轮中，pk是随机选择的，是一次

性随机串。
第②轮中，利用双重加密包含另一个一次性随机串：会话密钥K
K和pk实际起到salt的作用，通过加密将PWD隐藏起来
挑战-应答机制中使用的随机数，同样很好的隐藏了K*************************************************************************************
对称密钥管理：基于口令的加密PBE，基于硬件的密钥存储，生物统计学。
设计流密码的关键：如何生成伪随机性好的密钥流。
密钥流生成器分为驱动部分（反馈移位寄存器FSR）和非线性组成部分。
DES的核心模块：乘积网络F（三个关键函数：扩展函数E,选择压缩运算S,置换运算P）,Feistel网络。
选择压缩运算S是DES里唯一的非线性部分。

分组密码的五种工作模式：
模式名称 缩写 英文全称
电子密码本ECB Electronic CodeBook
密码分组链CBC Cipher Block Chaining
密码反馈 CFB Cipher FeedBack
输出反馈 OFB Output FeedBack
计数器 CTR Counter

抗伪造是数字签名最核心的安全要求。
认证包括实体认证和数据源认证。
对认证协议的典型攻击:中间人攻击, 旧消息重放 ,交错攻击 ,平行会话攻击 ,反射攻击.
保证新鲜性的基本技术: 时间戳机制 ,挑战-应答机制(利用随机数) .
如果单向函数存在，任何一个NP问题都存在零知识证明 。