信息安全导论复习

计算机考试复习

实时更新。

资料更新度：3更。

已完结。

发布地址：作业部落

发布总地址：Blog

2 古典密码

2.2.3 Playfair密码

明文 - 密文：

ar - RM
mu - CM
hs - BP
ea - IM/JM

如果balloon分解成ba-ll-oo-n有重复字母，就加一个x：ba-lx-lo-on。

2.2.5 Vigenere

d + w = z
e + e = i
c + a = c

3 分组密码DES

对称加密算法之DES介绍

DES真题及答案

5 分组密码AES

9 公钥密码RSA

10 公钥密码ECC、ElGamal和Diffie-Hellman

10.1 椭圆曲线密码ECC

$$y^2\ mod\ p = (x^3 + ax + b)\ mod\ p$$

对于Ep(a, b)有点(x, y)。

加法规则：

1. P + O = P
2. P + -P = O, (-P = (xp, -yp))
3. 对于R = P + Q：
   $$xr = (λ^2-xp-xq)mod p,\ \ yr = (λ(xp-xr)-yp)modp$$
   $$λ=\left\{\begin{matrix} \\ (\frac{yq-yp}{xq-xp})modp，P≠Q \\ (\frac{3xp^2+a}{2yp})modp，P=Q \end{matrix}\right.$$

10.2 Diffie-Hellman 密钥交换

ElGamal

11 HASH密码

14 Kerberos和X.509认证

16 IPSec

17 Web安全性SSL/TLS

零知识证明

题目1
假设有一扇用密码上门的锁，小明想要向小红证明，小明知道这个锁的密码，但同时又不告诉小明密码是什么，这个怎么办呢？

小明只需要先让小红进屋等着，然后小红通过门上的猫眼看着小明在门外开锁，因为是透过猫眼，所以小红可以确定不是别人开锁，但同时无法看到小明输入的密码。当门被小明打开的时候，小红就可以确信，小明确实是知道这个门的密码的。但重要的是，同时小红并不知道密码到底是什么。

题目2
A拥有B的公钥，A没有见过B，而B见过A的照片，偶然一天2人见面了，B认出了A，但A不能确定面前的人是否是B，这时B要向A证明自己是B，又不泄露自己的私钥。

A给出一个随机值，B用自己的私钥对其加密，然后把加密后的数据交给A，A用B的公钥解密，如果能够得到原来的随机值，则证明对方是B。

题目3
战争中你被俘了，敌人拷问你情报。你是这么想的：如果我把情报都告诉他们，他们就会认为我没有价值了，就会杀了我省粮食，但如果我死活不说，他们也会认为我没有价值而杀了我。怎样才能做到既让他们确信我知道情报，但又一丁点情报也不泄露呢？

这的确是一个令人纠结的问题，但阿里巴巴想了一个好办法，当强盗向他拷问打开山洞石门的咒语时，他对强盗说：“你们离我一箭之地，用弓箭指着我，你们举起右手我就念咒语打开石门，举起左手我就念咒语关上石门，如果我做不到或逃跑，你们就用弓箭射死我。”

强盗们当然会同意，因为这个方案不仅对他们没有任何损失，而且还能帮助他们搞清楚阿里巴巴到底是否知道咒语这个问题。阿里巴巴也没损失，因为处于一箭之地的强盗听不到他念的咒语，不必担心泄露了秘密，而且他确信自己的咒语有效，也不会发生被射死的杯具。

强盗举起了右手，只见阿里巴巴的嘴动了几下，石门果真打开了，强盗举起了左手，阿里巴巴的嘴动了几下后石门又关上了。强盗还是有点不信，说不准这是巧合呢，他们不断地换着节奏举右手举左手，石门跟着他们的节奏开开关关，最后强盗们想，如果还认为这只是巧合，自己未免是个傻瓜，那还是相信了阿里巴巴吧。

题目4
例如图论中有个哈米尔顿回路（Hamiltonian Cyclic）问题，说的是多个顶点的全连通图，若有一条通路通过了所有顶点，且每个顶点只通过一次，那这就是哈米尔顿回路。如果顶点较多的话，即使用计算机穷举计算很难找出这条回路，因为通路的可能性真在是太多了。
如果松鼠会贴了一张全连通图（命名为A图）悬赏哈米尔顿回路，而且任命我（奥卡姆剃刀）作为评审官，你幸运的找到了一条，那该怎么办呢，将结果直接发给我吗？千万不要，因为保不齐我会将你的成果让给了我的亲信。那你该怎么办呢？

应该这么办：

1. 你将A图的顶点搞乱了，并生成一张新图，只是顶点的位置变了，而新图顶点之间的连线关系与A图是完全一致的。这时，新图中每个顶点与A图中每个顶点的对应关系你是清楚的，而且新图中的哈米尔顿回路你也是知道的。
2. 你将这张新图发给我，没错，就是仅仅一张新图，上面并没有画着你发现的牛B回路。而我也无法判断这个图和原来的图一样。
3. 我收到后，对你提出两个问题中的一个：一是证明新图就是从A图变形过来的，所有顶点和连线的关系完全一致，二是画出新图中的哈米尔顿回路。
4. 如果你真的找到了A图的哈米尔顿回路，这两个问题当然都能轻松回答。需要注意的是：你只需要回答第3步的其中一个问题，千万不要两个问题一并回答，否则我就知道你关于A图的哈米尔顿回路了，你就SB了。
5. 我还是不相信你，因为有可能你只是将A图变了形，却根本不知道A图的哈米尔顿回路，而我在第3步时恰好要求你证明新图就是从A图变形过来的，你当然能证明。或者有可能你找了个你知道哈米尔顿回路的图，但这张图跟A图一点关系都没有，而我在第3步恰好要求你画出这张图的哈米尔顿回路。
6. 我要求你从第1步开始重复这个验证过程，随着次数的增加，第5步那种巧合的可能性就越来越低，如果你多次能回答对第3步中的问题，那我还不相信你已经找到了A图的哈米尔顿回路，那我就是一个傻瓜。
7. 为了表明我不是傻瓜，我在松鼠会群博里宣布你找到了A图的哈米尔顿回路，而这时我并没有看到你所画的A图的哈米尔顿回路。

题目5
你证明了一个世界级的数学难题，但在发表出来之前，总是要找个泰斗级的数学家审稿吧，于是你将证明过程发给了他，他看懂后却动了歪心思，他把你的稿子压住，把你的证明用自己的名义发表，他名利双收，你郁闷至死，你去告他也没用，因为学术界更相信的是这位泰斗，而不是你这个无名之辈。

你公开声称你解决了这个数学难题后，验证者会给你出一个其它的题，而能做出这道题的前提条件是已经解决了那个数学难题，否则的话无解，而且这个条件是学术界所公认的，这个题就是所谓的平行问题。不出所料，你靠着已经解开数学难题的基础把这个平行问题做出来了，但验证者还是不信，他又出了一道平行问题，你又做出来了，多次较量后，验证者就确信了你已经解决了那个数学难题，虽然他并没有看到具体的解法。

大家已经看出来了，零知识证明需要示证者和验证者的密切配合，但如果你只是一个数学界的无名之辈，即使你宣称你解决了数学难题，也不会有人跟你配合着玩零知识证明，那你该怎么办呢？

我告诉你一个可以在法庭上都能当作有效证据的招数，你将证明打印好，选择一个最可靠最权威的邮政公司，把它寄给自己，当你收到这个扣着邮戳的包裹后，不要打开，把它放好，然后就可以把证明寄给数学泰斗。如果他用自己的名义发表了，不必着急，等他依靠其影响力把这个证明炒热后再出手，你上法庭控告他，他当然不承认，在法庭上你将那个没开封的包裹拿出来，上面清清楚楚地盖着时间戳，这就证明了你包裹里的证明是发生在那个时间戳之前的，加上之后的你邮给泰斗论文的邮件存根，和泰斗以自己名义发表论文的时间，三者就构成了一个完整的证据链，泰斗灰头土脸名声扫地，而你大获全胜名利双收。

题型预测

8道题目：

• 零知识证明
• 椭圆曲线计算
• 求gcd和乘法逆元
• 认证协议分析
• 分组密码中的Feistel
• RSA计算或分析
• 经典加密算法（例如Playfair，Vigenere）

作业题

Exercise 1

1. TLS Protocol analysis

a. Now consider a man-in-the-middle attacker that sits between the client and server, and wishes to impersonate the server to the client. Assuming that the client knows the correct public key for the CA. Why does the attacker fail to impersonate the server to the client?
现在考虑一个位于客户端和服务器之间的中间人攻击者，并希望将服务器模拟到客户端。 假设客户端知道CA的正确公钥。 为什么攻击者无法模拟服务器到客户端？

由于攻击者无法伪造服务器的签名，因此必须使用服务器选择的ga。 但是由于离散日志的硬度，攻击者无法从ga中获取，因而无法计算gab，从而无法学习主密钥ms，从而无法提供正确的MAC，因此客户端将了解到有问题。

b. Now consider a passive attacker that has collected all the communication sent between the client and server that have been done in the past. Suppose this passive attacker has now stolen the secret key of the CA, SKCA. Can it use this secret key to decrypt the past communications that it has collected?
现在考虑一个被动攻击者，它已经收集了过去在客户端和服务器之间发送的所有通信。 假设这个被动攻击者现在窃取了CA，SKCA的密钥。 它可以使用此密钥来解密它收集的过去通信吗？

不可以。因为SKCA的知识不允许攻击者确定之前会话中使用的a或b。 这些是删除的短暂值。

c. The SuperFish malvertising software was shipped as part of Lenovo laptops in 2015.
Researchers discovered that the Superfish software modified the laptop’s browser so that the SuperFish Public Key was installed as trusted CA public key. The SuperFish software also made itself a man-in-the-middle between the browser and the laptop’s network connection. Explain exactly how this allowed SuperFish to decrypt any communication sent from the user to any webserver, without the user knowing, and modify this communication to inject SuperFish ads. (Hint, consider how SuperFish might forge a certificate for the Server.)
SuperFish恶意广告软件于2015年作为联想笔记本电脑的一部分发售。研究人员发现Superfish软件修改了笔记本电脑的浏览器，以便将SuperFish公钥作为可信CA公钥安装。 SuperFish软件也使自己成为浏览器和笔记本电脑网络连接之间的中间人。 准确地解释这是如何允许SuperFish解密从用户发送到任何网络服务器的任何通信，而无需用户知道，并修改此通信以注入SuperFish广告。 （提示，请考虑SuperFish如何为服务器伪造证书。）

Superfish软件在发布之前可以访问笔记本电脑，因此它将自己的superfish公钥作为可信CA公钥放在浏览器根存储中。 superfish密钥被硬编码到superfish软件中。 当用户请求网站时，SuperFish会向他们提供虚假证书，并使用其超级鱼密钥对其进行签名，并使用我们在“被盗CA密钥”攻击中看到的来拦截加密通信。 证书验证是因为用户的浏览器信任superfish公钥。 SuperFish现在可以解密发送给他们的流量（他们在路径上）并重新加密并发送，然后类似地解密他们收到的流量插入广告并重新加密它。

2. Analyze the following protocol and answer the question.
Refer to textbook for definition of Zq and G. x ← F(a) means value assignment, and R ← means randomly select a value.

Server需要验证根据U1、pw和S等信息构造出[pw, S, U1U2]并计算其哈希值，然后将此结果与U3比较，相同的话则证明user确实知道pw，user身份，验证通过。
以下是验证过程：
1)根据U1计算出g^U
2) U2=(S/h^pw)^u=g^su ,将1）中计算得到的g^U代入可得到U2
3）pw、S、U1U2对server来说都是已知的，据此计算H（pw，S，U1U2）并与user发过来的U3比较，相等则验证通过。

3. 认证分析
考虑下述 A 和 B 使用一个可信第三方 T 进行双向认证并建立会话密钥的协议。假定协议运行之前 A 和 T 共享一个对称密钥 KAT, B 和 T 共享一个对称密钥 KBT。A 和 B 分别产生一次性随机数 nA和 nB。协议共有四条消息，前三条消息如下(K{X}标识使用 K 对消息 X 进行对称加密)：

1) 在第四步 A 应该向 B 发送什么消息以完成协议？
2) 如果协议的第二步的消息变成：B,KTB{A, nB, nA}，协议是否依然安全？为什么?
3) 如果协议的第三步的消息变成：B,KAT {nA,KS},KBT {A,KS}, nB，协议是否依然安全？为什么？

1）KBT{A, KS}, KS{nB}

2) 安全。
为窃取密钥应该在第三步获得KBT {A, KS }，在没有B密钥的情况下，只能靠KAT {B, nA , KS }中的KS 获得其中K S 的值，没有其他方式构造KBT {A, KS }。而KS ，nA 是随机生成的，只能对同一条消息分析，除了暴力破解没有办法解出该条消息，协议中也没有其他的消息可以利用来进行加密或者破解。而随机数、KS 的随机性，使得重放不容易实现。

3) 不安全。如果攻击者C截获第一和第二条消息，可以将第二条消息换成[C, nB，KCT{A，nA}]，然后截获第三条消息[C,KAT{ nA ,Ks},KCT{A, Ks }, nB ],使用KCT解密获得Ks，并将此条消息替换为[B,KAT{ nA ,Ks},KCT{A, Ks }, nB]发送给A，然后截获A发送的第四条消息[KCT{A, KS}, KS{nB}], 然后C再冒充A发送[A,Ks]给B，然后截获B发给T的[B, nB，KBT{A，Ks}]，从中获得KBT{A，Ks}，这时C就可以伪造第四条消息[KBT{A, KS}, KS{nB}]发送给B，至此，C在A、B都不知情的情况下获得了A和B的会话密钥。

Exercise 2

1. Let E(k, m) be a block cipher where the message space is the same as the key space (e.g. 128-bit AES). Show that the following method does not convert a block cipher into a collision resistant function:
   令E（k，m）为块密码，其中消息空间与密钥空间相同（例如，128位AES）。 显示以下方法不会将块密码转换为抗冲突功能：
   

   $$f1(x, y) = E(y, x) ⊕ y$$
   That is, show an efficient algorithm for constructing collisions for f1. Recall that the block cipher E and the corresponding decryption algorithm D are both known to you.
   也就是说，显示了用于构造f1的冲突的有效算法。 回想一下，块密码E和相应的解密算法D都是您所知道的。

   

2. 

   a.
   根据签名算法可知
   

   $$g^y = u = g^m h^s = g^m g^{xs}= g^m g^{sx} = g^{m+sx}$$
   只需计算s，满足
   $$y ≡ m + sx\ mod\ q$$
   即 $$s ≡ (y - m)x-1\ mod\ q$$
   b.
   要伪造(m∗, s∗) 应满足
   $$y ≡ m∗ + s∗x\ mod\ q$$
   由于离散对数问题，根据已有m, pk = (g, h, u)无法直接推知sk = (x, y)，也无法直接通过上式计算得到s∗

3. Compute the following problems:
   Determine gcd(24140, 16762)

   gcd(24140, 16762)
   = gcd(16762, 7378)
   = gcd(7378, 2006)
   = gcd(2006, 1360)
   = gcd(1360, 646)
   = gcd (646, 68)
   = gcd(68, 34)
   = gcd(34, 0)
   = 34

4. Using the extended Euclidean algorithm, find the multiplicative inverse of 24140 mod 40902

   a = 24140, b = 40902,
   gcd(a, b) = 34
   24140%40902 = 24140
   40902%24140 = 16762
   24140%16762 = 7378
   16762%7378 = 9384
   7378%9384 = 7378
   9384%7378 = 2006
   7378%2006 = 1360
   2006%1360 = 646
   1360%646 = 68
   646%68 = 34
   反向带入：
   34 = 646 -68*9
   = 646 -(1360-646*2)*9
   = 646*19 -1360*9
   = (2006-1360*1)*19 -1360*9
   = 2006*19 -1360*28
   = 2006*19 -(7378-2006*3)*28
   = 2006*103 -7378*28
   = (9384-7378*1)*103 -7378*28
   = 9384*103 -7378*131
   = (16762-7378*1)*103 -7378*131
   = 16762*103 -7378*234
   = 16762*103 -(24140-16762)*234
   = 16762*337 -24140*234
   = (40902-24140)*337 -24140*234
   = 40902*337 -24140*571
   因此，24140%40902 的逆元为-571 即 40331，验证：(40331*40902)%40902 = 34。
   错了，存在乘法逆元的条件是两者相乘模同余为1，而两者不互素，因此不存在逆元。

5. The basic elements of the RSA algorithm can be summarized as follows. Given two prime numbers p and q, with n = pq and a message block M < n, two integers e and d are chosen with (e, n) being the public key and (d, n) being the private key. Please prove that Med mod n = M.
   RSA算法的基本要素可归纳如下。 给定两个素数p和q，其中n = pq且消息块M < n，选择两个整数e和d，其中（e，n）是公钥，（d，n）是私钥。 请证明Med mod n = M.

φ(n)为欧拉函数，因p、q都为素数，所以φ(n)=(p-1)(q-1)；
此外，RSA算法选择的e,d还要满足ed mod φ(n) =1, 1 因为ed mod φ(n) =1，所以ed = hφ(n)+1
要证Med mod n = M，即证M hφ(n)+1 = M(mod n).
下面分两种情况证明此式：
（1） 若M与n互素 根据欧拉定理有Mφ(n) = 1(mod n)
故M hφ(n) *M= M(mod n)
（2） 若M与n不互素 因n=pq,故M=kp,这时k与q必然互素（因M 根据欧拉定理有 (kp)q-1=1(mod q)，
再有[(kp)q-1]h(p-1) * kp=kp(mod q)
即(kp)ed =kp(mod q)
即(kp)ed =kp+tq
这时t必然能被p整除，即t=sp (kp)ed =kp+ spq
即Med =M+ sn，
即Med =M（mod n）

Exercise 3

1. For elliptic curve E11(1, 6), consider the point G = (2, 7). Compute the multiples of from 2G through 13G

   2G = G + G:
   λ= (3*2^2+1)/(2*7) mod11= 13/14 mod11=8
   x=(8^2-2-2)mod11=5
   y=(8(2-5)-7)mod11=2
   2G = (5, 2)

   3G = G + 2G：
   λ= (2-7)/(5-2) mod11=-5/3 mod11=2
   x=(2^2-2-5)mod11=8
   y=(2(2-8)-7)mod11=3
   3G=（8, 3）
   同样的方法可依次计算得到
   4G=(10, 2)
   5G=(3, 6)
   6G=(7, 9)
   7G=(7, 2)
   8G=(3, 5)
   9G=(10, 9)
   10G=(8, 8)
   11G=(5, 9)
   12G=(2, 4)
   13G=(∞, ∞)
   程序见附录。

2. Consider an ElGamal scheme with a common prime q = 71 and a primitive root α=7.
   a. If B has public key YB = 3 and A chose the random integer k = 2, what is the ciphertext of M = 30?
   b. If A now chooses a different value of k so that the encoding of M = 30 is C = (59, C2), what is the integer C2.
   考虑具有公共素数q = 71和原始根α= 7的ElGamal方案。
   a. 如果B有公钥YB = 3而A选择随机整数k = 2，那么M = 30的密文是什么？
   b. 如果A现在选择不同的k值使得M = 30的编码是C =（59，C2），那么整数C2是多少。

   a.
   C_1=α^k mod q=7^2 mod71=49
   K=〖Y_B〗^k modq=3^2 mod71=9
   C_2=KMmod q=(9*30)mod71=57
   密文为（49, 57）
   b.
   α^k mod q=7^k mod71=59 ，尝试k=3时发现此式成立，故k=3.
   K=〖Y_B〗^k modq=3^3 mod71=27
   C_2=KMmod q=(27*30)mod71=29

3. Attack MAC scheme:
   

   因为M1和M2均是single-block message，因此T1=AES(K, M1)，T2=AES(K, M2)，
   令 M3=M1||M1⊕T1 , 则 M3 可以分成两块：P1=M1，P2=M1⊕T1，则 M3 的加密可以分
   为两个阶段:
   第一阶段：C1=AES(K, M1)=T1;
   第二阶段：T3=AES(K, P2⊕C1)=AES(K, (M1⊕T1)⊕T1)=AES(K,M1)=T1
   T3=AES(K, M3)=T1
   Mallory 能够构造一个含有标签的密文（该密文不同于算法之前获得的含标签的
   密文，在原来的查询中没有出现）且能够通过验证算法，那么说明 Mallory 成功
   伪造了标签，所以即使 Mallory 不知道 K，Mallory 可以构造已知标签的消息 M3

关于考试 Q&A

考试主要以考察各种算法（经典加密算法、现代对称密码、现代非对称密码）、协议分析为主，所以请大家多参考作业题。

1.考题是中文还是英文？

考题一共8道，7道英文1道中文，英文很简单不用担心。

2.SDES, 3DES, HMAC, 多项式的模运算要求掌握吗？

SDES, 3DES, HMAC和多项式模只需知道基本原理即可。

3.DES的具体细节要求掌握吗？

DES的具体细节需要掌握，尤其是Fiestel计算过程。

4.模式是不是只掌握ECB和CBC就行了？

了解ECB、CBC，知道有几种模式即可。

5.SHA-1, Kerberos, SSL/TLS掌握到哪种程度，是需要记得每一步细节，还是只需知道每一步干什么和大概思想就可以？

SHA-1, Kerberos, SSL/TLS只需了解其基本原理，细节不需记住。

附录

椭圆曲线密码程序

# 椭圆曲线密码程序
class Ecc(object):
    p = None
    a = None
    b = None
    x1 = None
    x2 = None
    y1 = None
    y2 = None
    def __init__(self, p, a, b):
        self.p = p
        self.a = a
        self.b = b
    def set_points(self, x1, y1, x2, y2):
        self.x1 = x1
        self.y1 = y1
        self.x2 = x2
        self.y2 = y2
    # first set_points, then get sum
    def sum(self):
        if self.x1 == self.x2 and self.y1 == self.y2:
            lamuda = self.get_lamuda()
            print('λ:', lamuda)
            xr = (lamuda*lamuda - self.x1 - self.x2) % self.p
            yr = (lamuda*(self.x1-xr) - self.y1) % self.p
            return xr, yr
        elif self.x1 == self.x2:
            return 0, 0
        elif self.x2 == 0 and self.y2 == 0:
            return self.x1, self.y1
        else:
            lamuda = self.get_lamuda()
            print('λ:', lamuda)
            xr = (lamuda * lamuda - self.x1 - self.x2) % self.p
            yr = (lamuda * (self.x1 - xr) - self.y1) % self.p
            return xr, yr
    def get_lamuda(self):
        if self.x1 != self.x2 and self.y1 != self.y2:
            print('λ=', self.y2-self.y1, '/', self.x2-self.x1, ' mod ', self.p)
            return self.get_fraction_mod(self.y2-self.y1, self.x2-self.x1)
        else:
            print('λ=', 3*self.x1*self.x1+self.a, '/', 2*self.y1, ' mod ', self.p)
            return self.get_fraction_mod(3*self.x1*self.x1+self.a, 2*self.y1)
    # get (y/z)mod p
    def get_fraction_mod(self, y, z):
        for i in range(0, self.p):
            mod1 = (i*z) % self.p
            mod2 = y % self.p
            if mod1 == mod2:
                return i
        return -1
if __name__ == '__main__':
    pp = int(input('Input p:'))
    aa = int(input('Input a:'))
    bb = int(input('Input b:'))
    ecc = Ecc(pp, aa, bb)
    while True:
        xp = int(input('xp:'))
        yp = int(input('yp:'))
        xq = int(input('xq:'))
        yq = int(input('yq:'))
        ecc.set_points(xp, yp, xq, yq)
        xrr, yrr = ecc.sum()
        print('Question:', xrr, yrr)