《密码学基础复习提要》(2)

证明：

N?an10?an?110inn?1类型二：证明题：

1 证明DES的解密算法是加密算法的逆。 证明：加密过程的最后一轮的输出是RE16||LE16,且有：

LE16?RE15RE16?LE15?F(RE15,K16)?...?a0只要证明ai10模9和ai同余?

4 p和q是素数，n=pq证明φ(n)= φ(p)φ(q)=(p-1)(q-1) 证明：考虑余数集合{0, 1, …, (pq-1)}中不与n互素的余数集合是{p, 2p, …, (q-1)p}, {q, 2q, …, (p-1)q}和0，所以φ(n)= pq-[(q-1)+(p-1)+1]=pq-(p+q)+1= (p-1)(q-1)=φ(p)φ(q)

5 如果ac=bd mod n 且 c=d mod n, gcd(c,n)=1,则 a=b mod n.

证明：c=d mod n ?d=c+knl

ac=bc+bkn mod n ? ac=bc mod n ac=bc mod n ? (a-b)c=ln

a-b=l/c*n 由于 gcd(c,n)=1 所以 必有 c|l 所以 a-b= jn ? a=b mod n

6 对任意互素的a和n, (gcd(a, n)=1), 有a mod n=1

证明：令{r1, …, rφ(n)}是模n的缩剩余集，0

?(n)?(n)i

对于解密：

LD1?RD0?LE16?RE15RD1?LD0?F(RD0,K16)?RE16?F(RE15,K16)?LE15?F(RE15,K16)?F(RE15,K16)?LE15

所以有

LD1?RE15RD1?LE15

对于其他各轮也是如此。解密后最后一轮的输出是

RE0||LE0，左右互换即可得到原来的明文。

2 试证明模算术的两个性质

[(amodn)?(bmodn)]?(a?b)modn??ari?1mod n???(n)?i?1(rimodn)，?φ

?(n)?(n)ari??i?1rimodn

i?1?(n)

a?(n)?i?1ri??i?1rimodn，即得a

(n)

mod n = 1

[(amodn)?(bmodn)]modn?(a?b)modn证明：设

a?k1n?rab?kbn?rbra?nrb?n

也可由此证明，费马定理 ap-1 mod p = 1

7. 证明RSA算法的正确性

Med?Mmodn,n?pq.edmod?(n)?1,

[(amodn)?(bmodn)]?(ra?rb)modn?(kan?ra?(kbn?rb))modn?(a?b)modn

RSA

M的正确性等价于证明：

modn?M.

k(p?1)(q?1)?1

[(amodn)?(bmodn)]modn?(ra?rb)modn若gcd(M,n)=1,根据欧拉定理，容易得到

k(p?1)(q?1)?1(a?b)modn?(kan*kbn?kan*rb?kbn*ra?ra*rb)modMn?(ra?rb)modnmodn?M。当 gcd(M,n)?1，假

3 证明十进制整数N和它的各位数之和模9同余

设m是p的倍数，即m=cp。 那么有：

M?(q)modq?1(M?(q))?(p)modq?1

M?(n)modq?1 Mkφ

(n) mod q=1

因此有：(φ(n)均改为kφ(n))

M?(n)?kq?1

M?(n)M?(kq?1)MM?(n)?1?M?kcn

M?(n)?1?Mmodn得证。

8 证明Diffie-Hellman的正确性

证明：DH中，素数q和本原根a是公开的。A选择私有的Xa，B选择私有的Xb，A和B之间交换

YXaa?amodq，Ybb?aXmodq，交换的密钥为：

KXaa?YbmodqKXbb?Yamodq

其中

KXba?(amodq)Xamodq?aXbXamodq??aXaXbmodq??aX

amodq?Xbmodq?YXbamodq?Kb9 对基于CBC的MAC算法，如果知道一个分组X的MAC值为T?MAC(K,X)，证明对分组X||X?T的MAC值依然是T

证明:

在CBC模式下，

MAC(X||X?T)?MAC(MAC(X)?X?T)?MAC(X)

解答题

1 使用下述Playfair矩阵加密消息：Must see you

over Cadogan West, Coming at once

?MFHIJK???UNOPQ???ZVWXY?

??ELARG????DSTBC??Playfair加密的原理：

如果字母对的两个字母相同，那么它们之间填充x。 落在同一行的明文字母用用右边的代换，同一列的字母用下面的代换，对角的字母用其另外的对角替换。

答：UZ TB DL GZ PN NW LG TG TU ER OV LD BD UH FP ER HW QS R

2 用Vigenera密码加密单词explanation，密钥为leg

加密方法：密钥字母决定行，明文字母决定列 答：PBV WET LXO ZR

3 对于系数在Z10上的多项式计算，分别计算：

a.(7x?2)?(x2?5)b.(6x2?x?3)?(5x?2)

Z10是模10的剩余类。Zn中整数模运算的性质是：

答：a.9x2+7x+7 b.7x2+7x+6

4 在使用RSA的公钥体制中，已截获发给某用户的密文为C＝10，该用户的公钥e=5, n=35,那么能否破解出其明文？明文是什么？ 答：能。

C=Me mod n

10=M5 mod 35 n=35=5*7 φ(n)=4*6=24

ed mod φ(n)=1 即5*d mod φ(n)=1 且 d<φ(n) d=5 m=Cd mod n=105 mod 35=5

5 设DH方法中，公用素数q=11,本原根为2 a. 证明2是11的本原根

b. 若用户a的公钥为9，那么A的私钥是多少？ c. 若用户b的公钥为3，那么共享的K是多少？

解：

21mod11?222mod11?423mod11?824mod11?525mod11?1026mod11?9

27mod11?728mod11?329mod11?6210mod11?1可以验证2是11的本原根

b. 若A的公钥为9，则其私钥为6

c. 若B的公钥为3，那么共享密钥

K?98mod11?3

6 A和B之间可通过如下协议实施相互认证并交换密钥：

1.A?B:IDA||Na2.B?KDC:IDB||Nb||E(Kb,[IDA||Na||Tb])3.KDC?A:E(Ka,[IDB||Na||Ks||Tb])||E(Kb,[IDA||Ks||Tb])||Nb4.A?B:E(Kb,[IDA||Ks||Tb])||E(Ks,Nb)

请解释该协议.

答：1、A初始化该认证交换。A产生临时交互号Na,并将其标识和Na以明文的形式发送给B。该临时交互号将和会话密钥等一起被加密后返回给A，以使A确定消息的及时性。

2、B向KDC申请一个会话密钥。B发送给KDC的消息和临时交互号Nb,该临时交互号将和会话密钥等一起加密后返回给B，以使B确信消息的及时性。B发送给KDC的消息中还包括用B和KDC共享的密钥加密后的信息，该信息用于请求KDC给A发证书，它指定了证书的接受方、证书的有效期和收到的A的临时交互号。

3、KDC将B的临时交互号用KDC和B共享的密钥加密后的信息发送给A，我们将会看到该信息可用作A进行后续认证的一张“证明书”。同时KDC将用它和A共享的密钥加密后的信息发送给A，该信息可用来验证B曾收到过A最初发出的消息（IDB），并可说明该消息是及时的消息，而不是重放的消息（Na），同时A可从中得出会话密钥（KS）及其使用时限（Tb）。

4、A将证书和用会话密钥加密后的B的临时交互号发送给B，B可由该证书的解密EK1[Nb]的密钥，从而得出Nb用会话密钥对B的临时交互号加密，可保证该消息是来自A的非重放消息。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《密码学基础复习提要》(2)在线全文阅读。