现代密码学（第4版）—习题参考答案.pdf

6 . ( 1 ) 在 I D E A 的模乘运算中，为什么将模乘取为2 1 6 + 1 而不是2 3 ？( 2 ) 在 I D E A 的模加运算中，为什么将模乘取为2 '6而不是21 6 + 1 ?答：( 1 ) 在 ID E A 模乘运算中，必须保证运算构成一个群，因此模数必须为素数，故不能取21 6,( 2 ) 同一群内的分配律和结合律都成立，但 I D E A 算法中要保证模数的加法和模数的乘法，比特异或之间分配律和结合律不成立，因此模加运算不能和模乘运算在同一个群内，即不能选模2 历+ 1 , 而在模加运算中必为一个群.7 . 证明S M 4 算法满足对合性，即加密过程和解密过程一样，只是密钥使用的顺序相反证明：S M 4 算法的加密轮函数分为加密函数G和数据交换E 其中G对数据进行加密处理， E进行数据顺序交换即加密轮函数A = G tE其中，G t = G i (X i ， X i +i ， M +2， X i +3,% ) (i = 0,1,2， …, 31)=(X j ㊉ T (X i +i ,X i +2， X i +3， r k )X i +i ,X i +2， X i +3)E (X i +4， (X i +i ， X i +2， M +3)) = ((X i +i ， X i +2， X i +3),X i +4), (i = 0,1,2， …， 31)因为,⑹)2 = [( X i ㊉ 7(Xi+i，Xi+2，M+3，rkD，Xi+i，Xi+2，Xi+3，rk i)= (Xi-㊉ T(Xi+i，Xi+2，Xi+3，r/Q)㊉ 7(Xi+i，Xi+2，Xi+3，rki),X i+ i，Xi+2，Xi+3，rk i)=何a + 1出 +2因 +3，7母)=I因此，加密函数G 是对合的。

E 变换为：E(Xi+4, (Xi+i，Xi+2，Xj+3)) = (( Xi + i，Xi + 2，Xj+3),Xi+4)E?(Xi+4, (Xi + i，Xi+2，Xi+3)) = I显然，E 是对合运算综上，加密轮函数是对合的根据加密框图，可将SM4的加密过程写为：SM4 = GQEG^E ... G3 0E G31R根据解密框图，可将SM 4的解密过程写为：SM4T = G31E G30E . . . G1E G0R比较SM4与 SM4」 可知，运算相同，只有密钥的使用顺序不同所以，SM4算法是对合的第4章1 . 证明以下关系：(1) (am odn) = (Jbm odn), 则 a 三bm od〃；(2) a = b m o d n f W O b = am odn ；(3) a = b m o d n f b = c m o d n » 则 々三 m od〃解：(1)设am o d 〃 = G， bm od〃 = / ; , 由题意得吃二5 ，且存在整数，% , 使得a = j n+ ra,b = kn + rh^> a — b = (j - k) n , 即〃 |a —/7, 证得々三人m od〃。

2)已知三〃m od/z, 则存在整数Z ， 使得Q = k i + /? n b = (-Z )〃 + a ,证 得 三 am od〃3)已知a 三〃m od〃力三c、 m od〃，则存在整数， 次 ，使得a = j n + b,b = kn + c= > a = (/ + 左 )〃 + c , 证得 a 三 cm od〃2 . 证明以下关系:( 1) [(am o dn) - (bm o d 〃 月 m o dn - ( a - h )m o dn；( 2) [(am o dn)x(bm o dn) ]m o dn = (axh )m o dn解：(1)设4m o d 〃 = c， 0m o d 〃 =以，则存在整数，上 ,使得a = j n + ra,b = kn + rb^ > a - h = (j -k) n + (ra-rb')= > ra-rb= -(j -k) n-h (a-b)= > (〃- 与)m o d n - (a-b) m o d n.即[ (〃 m o d n) - (b m o d 〃 )] m o d n = (a-b) m o d n 0(2)设 々m o d " = 弓,。

m o d 〃 = 5, 则存在整数，攵，使得a = j n-\-ra,b = kn+ rb n a x b = (Jkn + m +行 口 " + 二 %n =- ( jk n + + krJn + S x b )= > (〃7; ) m o d n = (ax b) m o d n.即[ (〃 m o dn)x(hm o dn) ]m o dn = (axb)m o dn3 . 用 F er m a t 定理求 32" m o d 11 o解：因为〃 = 1 1 是素数，且g c d (3,l l )= l ,则由F er m a t 定理可得:3")三 1 m o d 11 n 心"三 1 m o d 11；又根据性质[ (〃 m o d 〃 )x(bm o d /2)] m o dn = (axb)m o dn , 可得:3201 m o d 11 = [ ((3I 0)20)m o d 11)x (3' m o d 11)] m o d 11 = 3m o d 11 4 . 用推广的E u c l i d 算法求6 7 m o d l 19 的逆元。

解：运算步骤如下表所示：循环次数QX1X2X3Y i丫2丫3初值〜10119016 711016 71-15 2211-15 2-121533-12154-77424-77-9161所以 6 77 m o d l 19 = 16 5 .求 g c d (46 5 5 ,12075 )解：由E u c l i d算法，得：12075 = 2x 46 5 5 + 276 546 5 5 = 1x 276 5 + 18 9 0276 5 = 1x 18 9 0 + 8 7518 9 0 = 2x 8 75 + 1408 75 = 6 x 140 + 35140 = 4x 35 + 0所以 g c d (46 5 5 ,12075 ) = 35x = 2 m o d 36 .求解下列同余方程组：( X三l m o d 5x = 1 m o d 7解： 根据中国剩余定理求解该同余方程组， 记4 = 2,% = 1,% = 1，叫= 3,牡= 5 ,m , = 7 ,M =町 x 机,x丐 =105 ,则有M =—— =35 , M m o d 町=35 T m o d 3 = 2,町m o dm2 = 21T m o d 5 = 1,,Mi= — = 15 ,M-' m o d 吗= 15T m o d 7 = l .m ,所以方程组的解为x = + M2M ^ a2 + ) m o d M= (35 x 2x 2 + 21x l x l + 15 x l x l )m o d l 05= 176 m o d l 05 = 71m o d l 05 .7.计算下列L eg en d r e符号：解:⑴圆= (-1)小=-1⑵( - 1)[2 + ：X3)= (― 1 ( |) = (-1)(-1)^=18 .求25的所有本原根。

解： 因为夕(25) = 25(1 — 5 = 20 = 22x5,所以°(25)的所有不同的素因子为1 =2,即对每个g ,只需计算8叱 又 因 为 以24) = 24(l — g)(l— ； ) = 8 ,所以25有8原根 5 ,个本I10 = lmod25, I4 = lmod25；3'° = 24mod25, 34 =6mod25；5'° =0mod25, 5° = 0mod25；7川 =24moe125, 74 =lmod25；910 =lmod25, 94 = Hmod25；lf°=lmod25, ll4 =16mod25；1310 = 24mod25, 134 = llmod25；15'° = 0mod25, 154 =0mod25；1710 = 24mod25, 174 = 21 mod25；W°=lmod25, 194 = 21mod25；2110 = lmod25, 214 =6mod25；2310 = 24mod25, 234 = 16mod25；210 = 24mod25» 24 = 16mod25；410 = 1 mod25, 44 = 6mod25；610 - lmod25, 64 = 21 mod25；8,0=24mod25, 84 = 21mod25；IO10 =0mod25, 104 =0mod25；1210 =24mod25, 124 =Hmod25；1410 = lmod25, 144 = 16mod25；16l0 = lmod25, 164 =llmod25；1810 =24 mod 25, 184 =1 mod 25；2O10 = 0mod25, 204 = 0mod25；2210 = 24mod25, 224 =6 mod 25；24'° = 1 mod 25, 244 = 1 mod 25；满足 g 1 ° w 1 mod 25 且 g4Hlmod 25 的 g 为 25 的本原根，即 2,3,8,12,13 /7,22,239 .证明当且仅当〃是素数时，

证明：(1)若 是域，则 , 均为 Abel 群 显然＜Z ",+” ＞为A b el群，与〃是否为素数无关；但若＜Z “ -{O } ,x “ ＞为A b el群， 其条件之一必须保证对任意XGZ “ - {0}有模乘法逆元，即对任意x e Z “ - {0} ,有yeZ ,-{0} ,使得x x y三l m o d〃，所以g c d(尤 ,〃)=1 ,即〃为素数2)若〃不是素数，则双〃)＜〃-1 ,即至少存在一个x e Z“ 一{0} ,使得g c d (x ,〃)H l ,即x无模乘法逆元，因此不能保证＜ Z 〃 - {0} ,x “ ＞均为A b el群 ,即＜Z “ ,+“ ， x ” ＞不是域10 .设通信双方使用R S A加密体制，接收方的公开钥是(e,〃 ) = (5 ,35 ),接收到的密文是C = 1 0 ,求明文解：因为“ = 3 5 = 5x 7= ＞p = 5,q = 7 ,则奴〃) = (p _ l )(q _ l ) = 4 x 6 = 2 4 ,所以d m e ~[ m o d Q (〃)三 5T m o d 24 = 5 m o d 2 4 ,即明文 M 三 C" m o d n = 1 05 m o d 3 5 = 5。

1 1 .已知cd m o d n的运行时间是O Q o g] 〃 )，用中国剩余定理改进R S A的解密运算如果不考虑中国剩余定理的计算代价，证明改进后的解密运算速度是原解密运算速度的4倍证明：R S A的两个大素因子p ,q的长度近似相等，约为模数〃的比特长度l o g〃的一半，即(l o g/ ? )/ 2,而在中国剩余定理中，需要对模p和模夕进行模指数运算，这与c " m o d〃的运行时间规律相似，所以每一个模指数运算的运行时间仍然是其模长的三次累，即O [ (l o gn / 2 )3] = O (l o g3n )/ 8 »在不考虑中国剩余定理计算代价的情况下，R S A解密运算的总运行时间为两个模指数运算的运行时间之和， 即l o g3 〃)/ 8 + O (l o g3 〃)/ 8 = O (l o g3 〃)/ 4 ,证得改进后的解密运算速度是原解密运算速度的4倍1 2 .设R S A加密体制的公开钥是(e , 〃 ) = (77,2 2 1 )(1 )用重复平方法加密明文1 60 ,得中间结果为:1 6()2 (m o d 2 2 1 )三 1 8 51 604 (m o d 2 2 1 )三 1 9 11 6()8 (m o d 2 2 1 )三 1 61 60 '6(m o d 2 2 1 ) = 3 5I G O '? (m o d 2 2 1 ) = 1 2 01 6()64 (m o d 2 2 1 )三 3 51 6072(m o d 2 2 1 ) = 1 1 81 6076(m o d 2 2 1 ) = 2 1 71 6077 (m o d 2 2 1 ) = 2 3若敌手得到以上中间结果就很容易分解〃，问敌手如何分解〃。

2 )求解密密钥解：(1 )由以上中间结果可得：1 601 6 (m o d 2 2 1 )三 3 5 三 W O ^ Cm o d 2 2 1 )= > 1 6064 - 1 60l 6= 0 (m o d 2 2 1 )n (1 6()3 2 — [6 0s)(1 603 2 + 1 6O8) = 0 (m o d 2 2 1 ) > (1 2 0 - 1 6)(1 2 0 + 1 6) = 0 (m o d 2 2 1 )= > 1 0 4 x 1 3 6 三 0 (m o d 2 2 1 )由 gc d (1 0 4 ,2 2 1 ) = l 3 , gc d (l 3 6,2 2 1 ) = 1 7 ,可知分解为 2 2 1 = 1 3 x 1 7⑵解密密钥 d = e T m o d (9 (〃))= 77T m o d (°(1 3 x l 7)) = 77T m o d (1 2 x l 6),由扩展的E u c i l d算法可得d = 51 3 .在E l G a m a l加密体制中，设素数p = 7 1 ,本原根g = 7,(1 )如果接收方B的公开钥是为 =3 ,发送方A选择的随机整数左=2,求明文M = 3 0所对应的密文。

2 )如果A选择另一个随机整数k， 使得明文M = 3 0加密后的密文是C = ( 5 9 ,)， 求 解：(1 )密文c = ( q ， G) ，其中：G - gk m o d p - 72 m o d 71 = 4 9 , C2 = (y j M )m o d p = (32 x 3 0 )m o d 71 = 5 7所以明文M = 3 0对应的密文为C = (4 9 ,57)⑵ 由G =8卜m o d 〃 n 59 = 7 k m o d 7 1 ,穷举法可得k = 3 所以 G = (y) m o d p = (33 x 3 0 ) m o d 71 = 2 9 1 4 .设背包密码系统的超递增序列为(3 ,4 ,9 / 7,3 5),乘数r = 1 9 , 模数左= 7 3, 试对go o dn i gh t 力 口 密 解： 由 4 = (3 ,4 ,9 ,1 7,3 5), 乘 数1 = 1 9 ， 模 数 左= 73 , 可 得B - t x A m o d k = (57,3 ,2 5,3 1 ,8 )。

明文“ go o d n i gh t ” 的编码为“ 0 0 1 1 1 ” , “ 0 1 1 1 1 ” , “ 0 1 1 1 1 ” , “ 0 0 1 0 0 ” ， “ 0 0 0 0 0 ” , "O H I O ” , "0 1 0 0 1 ” ,“ 0 0 1 1 1 ” , “ 0 1 0 0 0 ” , “ 1 0 1 0 0 ” , 则有：/ (0 0 1 1 1 ) = 2 5 + 3 1 + 8 = 64 ,/ (0 1 1 1 1 )= 3 + 2 5 + 3 1 + 8 = 67,/ (0 1 1 1 1 )= 3 + 2 5 + 3 1 + 8 = 67,/ (0 0 1 0 0 ) = 2 5,/ (0 0 0 0 0 ) = 0 ,/ (0 1 1 1 0 )= 3 + 2 5 + 3 1 = 59 ,/ (0 1 0 0 1 )= 3 + 8 = 1 1 ,/ (0 0 1 1 1 ) = 2 5 + 3 1 + 8 = 64 ,/ (0 1 0 0 0 ) = 3 ,/ (1 0 1 0 0 ) = 57 + 2 5 = 8 2 = 9 m o d 73 .所以明文“ go o d n i gh t ” 相应的密文为(64 ,67,67,2 5,0 ,59 ,1 1 ,64 ,3 ,9 )。

1 5 .设背包密码系统的超递增序列为(3 ,4 ,8 ,1 7,3 5),乘 数 ， = 17 , 模数％ = 6 7 , 试对2 5,2 ,72 ,9 2 解密解： 因 为 " m o d % = 1 7一 | m o d 67 = 4 m o d 6 7 ， 则 4 x (2 5,2 ,72 ,9 2 ) m o d 67 = (3 3 ,8 ,2 0 ,3 3 )所以其对应的明文分组为(0 ()0 0 1 ,0 0 1 0 (),1 0 0 1 0 ,0 0 0 ()1 ), 由课本1 2 0 页表4 - 7可得明文为“ A D R A ” 1 6 .己知〃=网 ， p ,q 都是素数，x , y w Z ： , 其 J a c o b i 符号都是1 , 其中Z ： = Z“ 一{0 },证明：⑴ 肛 (m o d 〃)是模〃的平方剩余，当 且 仅 当 都 是 模 〃 的 平 方 剩 余 或 都 是 模 〃 的 非平方剩余2 ) V y 5 ( m o d 〃)是模〃的平方剩余，当且仅当尤,y都是模”的 平 方 剩 余 或 都 是 模 〃 的非平方剩余。

证明：（ 1 ） ①必要性：若 孙 （ m o d 〃 ） 是模〃的平方剩余，即存在f使得x y =rm o d ”，而n - p q ,显然必有xy = r mo d p , x y - r m o d g ,所以刈 也同时是模p和模q的平方剩余,即（ 现 ） = 1 ,（ 现 ） = 1 n （ £） £ ） = 1 ,（ - ） A = 1 .p q p p q q又由题意得（ 2） = 1 ,（ 2） = 1 , BP（ - ） （ - ） = 1 ,（ - ） （ - ） = 1 » 所以：n n p q p q当（ ±） = 1 时，有（ 2） = l n（ 2） = l n（ 土） = 1, 即x同时是模p和模q的平方剩余，y 也p p q q同时是模p和模夕的平方剩余，即 都 是 模 " 的 平 方 剩 余 ；当（ 土） = 7 时，有 （ 马 =_1 0 （ 马 =_1 = （ 为 =_1, 即x同时是模p和模q的非平方剩p p q q余，y 也同时是模p和模q的非平方剩余，即 都 是 模 〃 的 非 平 方 剩 余 。

② 充 分 性 ：若都是模“的 平 方 剩 余 ，则 演 y 也 是 模 p和 模 9 的 平 方 剩 余 ，即（ 土） =（ 当 =（ 马 =（ » ） = 1, 即孙同时是模p和模q的平方剩余，所以孙是模〃的平方剩p q p q余；若演y 都是模〃的非平方剩余， 则它们对于模p和模q至少有一种情况是非平方剩余， 不妨设 （ 土） = -1 ,= （ 2） =一1 ，则有（ 与 =- 1 ,（ 马 = 一 1, 即尤,y 也都是模p和模q的非平方剩p p q q余所以（ 土） （ 上） =（ ? ） =（ —1 ） （ —1 ） = 1, 同理（ 与 ） = 1, 即孙同时是模p和模q的平方剩p p p q余，所以孙是模〃的平方剩余⑵ 若 x ，5（ m o d 〃 ） 是模〃的平方剩余，则 丁 尸 同 时 是 模p和 模q的平方剩余，所以< 3 5 \4L = 1 = （ 二） 3（ 2） 5 , 由于勒让德符号的偶数次方肯定为1（p | x 情况除外） ，即有< p J p P1 = （ A） （ 2） , 余下证明同（ 1 ） p P提示:目讣1X X |、p人 “V 、y yp人 力= [ £ ( »17.在Rabin密码体制中设p = 53,q = 59 ：(1)确定1在模〃下的4个平方根。

2)求明文消息2347所对应的密文3)对上述密文，确定可能的4个明文解：( 1)已知/ 三lmod3127, 〃 = pq = 53x59 = 3 1 2 5 ,由中国剩余定理可得到等价方程组:x1 = 1 mod 53x2 s i mod 59因为( ±1)2 三 1 mod53,(±iy 三lmod59 ,所以x三土lmod53, x三±lm od59经组合可得到以下四个方程组:x 三 lmod53x = lmod59x = \ mod53x = -lm od59x = -lm od53x = lmod59x = -lm od53x = -lm od59根据中国剩余定理M = 59, mod53 = 9,M2= 53,M；] mod59 = 4 9 ,则有:第一个方程组的解为(59・ 9 ・ l + 53・ 49・ l)mod3127ml；第二个方程组的解为(59・ 9・ l+53・ 49・ (— l))mod3127三1061；第三个方程组的解为(59 • 9 • (— 1) + 53 ・ 49・ 1) mod 3127三2066 ；第四个方程组的解为(59.9・ (— 1) + 53・ 49.(— l))mod3127三3126。

所以，1 mod/?的四个平方根为 1 mod ()61 mod 〃 ,2066mod 〃 ,3126mod n2) 2347 对应的密文为 c 三 23472 mod 3127 三 17623)解密即解尤2三I762m od3127,由中国剩余定理可得到等价方程组：X2 三 1762mod53 = 13x2 三 1762mod59 = 51因为( ±15)2 三 13mod53,(±13)2 三51m od59,所以 x三±15mod53,x三±13mod59 ,经组合可得到以下四个方程组：x = 15mod53 (x = 15mod53 (x = -15mod53 [x = -15mod53x s 13mod59 x = -13mod59 x = 13mod59 x = -13mod59根据中国剩余定理必= 59,M jm od53三9,^2 =53,M jm od59三4 9 ,则有：第一个方程组的解为(59915 + 53・ 4943)mod3127三1075；第二个方程组的解为(59 • 9 • 15 + 53 • 49 • (-13)) mod 3127 三 2347：第三个方程组的解为(59 9 ( - 15) + 53 ・ 49 • 13) mod 3127三780 ；第四个方程组的解为(5 9 9 (— 15) + 53・ 49-(— 13))mod3127三2052。

所以，四个可能的明文为1075,2347,780,205218.椭圆曲线片|(1,6)表示V三V + x + G m o d ll,求其上的所有点解：模11的平方剩余有1,4,9,5,3x = l,4,6时，y2 = 8mod 1 1 ,无解，曲线无与这一x相对应的点;x = 9时，y2 = 7 mod 1 1 ,无解，曲线无与这一 x相对应的点；x = 0时，y2 = 6mod 1 1 ,无解，曲线无与这一 x相对应的点；x = 2时，y2 = 2mod 11,y = 4^c7 ；x = 3 时，y?三 3 modl 1, y = 5或6 ；x = 5,7,10时，y2 = 4mod 11, y = 2或9 ；x = 8时，/ 三9m odll,y = 3或8所以椭圆曲线E ” ( l,6)上的所有点为:{ ( 2 ,4),( 2 ,7 ),( 3,5),( 3,6),( 5,2 ),( 5,9),( 7 ,2 ),( 7 ,9),( 8 ,3),( 8 ,8 ),( 1 0 ,2 ),( 1 ( X 9),1 9.已知点G = ( 2 ,7 )在椭圆曲线E ” ( l,6)上，求2G和3 G。

解：( 1 )求 2G2 = 3x2上। mo d 1 1 = ( 1 3x 4)mo d 1 1 = 8 mo d 1 1 ,2 x 7x2G = ( 82 -2 -2 )mo d 1 1 = 5mo d 1 1 ,y2G = [ 8 x ( 2 -5)-7 1 mo d 1 1 = 8 mo d 1 1 ,所以 2 G = ( 5,2 ) 2 )易知3G = 2 G + G = ( 5,2 ) + ( 2 ,7 )2 - - ~| mo d 1 1 = ( 5x 7 ) mo d 1 1 = 2 mo d 1 1 ,x3G = ( 22 - 5-2 ) mo d 1 1 = 8 mo d 1 1 ,y3G = [ 2 x ( 5— 8 )-2 ] mo d 1 1 = 3 mo d 1 1 ,所以 3G = ( 8 ,3)2 0 .利用椭圆曲线实现E lG a ma l密码体制，设桶圆曲线是E ” ,6 ) ,生成元G = ( 2 ,7 ),接收方A的秘密钥% =7 1 )求A的公开钥“ 。

2 )发送方B欲发送消息匕,= ( 1 0 ,9),选择随机数％ = 3 ,求密文( 3)显示接收方A从密文C,“ 恢复消息Pm的过程解：( 1 )易知公开钥5 = 7 G = 2 x 2 G + 3 G①求2 x 2 G3x 52 + 1A . = - -1----mo d 1 1 = ( 1 0 x 3) mo d 1 1 = 8 mo d 1 1 ,2 x 2x4C = ( 82-5-5)mo d ll = 1 0 mo d ll,y4G = [ 8 x ( 5 — 1 0 ) - 2 ] mo d 1 1 = 2 mo d 1 1 ,所以 2 x 2 G = ( 1 0 ,2 )②由题 1 9可得3G = ( 8 ,3),即2=2乂2 6 + 36 = ( 1 0 ,2 ) + ( 8 ,3)3-22 = -~ ~ — mo d 1 1 = ( 1 x 5) mo d 1 1 = 5 mo d 1 1 ,xlc - ( 52 -1 0 -8 )mo d i 1 - 7 mo d 1 1 ,y7 G = [ 5x ( 1 0 -7 )-2 ] mo d ll = 2 mo d ll,所 以 乙 = ( 7 ,2 )。

⑵密文C,“ = (攵G ,吊 + %) ①求 k G ： k G - 3G = ( 8 ,3)»②求狂3 % 以= 2 2 + 〃 = 3G + 7 G = ( 2 ,7 ) + ( 7 ,2 )2 -72 =----mo d 1 1 = 一 1 mo d 1 1 ,7 -2= ( ( -I )2-2 -7 )mo d l 1 = 3mo d l 1 ,y3l,A = ( ( -1 ) x ( 2 - 3) - 7 ) mo d 1 1 = 5 mo d 1 1 ,所以％5 =( 3,5)③ 求 月 + %： 尺,+ % = ( 1 0 ,9) + ( 3,5)5-92 =-----mo d 1 1 = -lmo d 1 1 ,3-1 0xPm+kPA = ( ( — I p — 1 0 — 3) mo d 1 1 = 1 0 mo d 1 1 ,yp +kP = ( ( -l)x ( 1 0 -1 0 )-9)mo d ll = 2 mo d ll,所以&+ S = ( io ⑵ .综上：Cm = (kG ,与 + 俎 ) ={ ( 8 ,3),( 1 0 ,2 ))。

⑶从密文c, “ 恢复消息pm的过程如下：Pm= (Pm + kPA) -nA(kG )= ( 1 0 ,2 )-7 ( 8 ,3)= ( 1 0 ,2 )-( 3,5)= ( 1 0 ,2 )+ ( 3,6)= ( 1 0 ,9).其中：a )计算 7 ( 8 ,3)①先计算2(8,3 )3X82+1A - ------------2x3三 1 mod 11,“ 2(8 3)=1—8 — 8 = 7 mod 11,% ( 8 ,3)= l( 8 _ 7 )_ 3m9mo d ll,所以 2(8,3) = (7,9)②计算 3(8,3) = 2(8,3)+ (8,3)3 — 9A = -------= 5 mod 11,8 -7七 (8,3)=5?—7 — 8 m lOmodll,%(8.3)= 5 ( 7 — 10)-9m 9m odll,所以 3(8,3) = (10,9)③计算 6(8,3) = 3(8,3)+ 3(8,3)A —3 x102+ 1 吧 三 lOmodll,2x918尤6(8,3)= 1°2—10一1° 三 3 modll,然(8,3)= 1 ° 。

° 一 3) — 9 三 6 mod 11,所以 6(8,3) = (3,6)④计算 7(8,3) = 6(8,3)+ (8,3) 3 — 6 - 3 , 11A = -------= — = 6 mod 11,8 -3 5* 7(8 3)= 6 — 3 — 8三3 mod 11,%(8,3)= 6(3-3 )-6 = 5 mod 11,所以 7(8,3) = (3,5)b)计算(10,2)-7(8,3) = (10,2) -(3,5) = (10,2) + (3,-5) = (10,2) + (3,6)6 — 2 4 ...A.= ----= —— = 1 mod 11,3-10 -7rm= l2-1 0 -3 = 10modll,= l(10-10)-2 = 9modll,所以(10,2)-7(8,3) = (10,9)第5章1.在公钥体制中，每一用户U都有自己的公开钥PK“和秘密钥S K如果任意两个用户A , B按以下方式通信，A发 给B消息（ E p K “ （ m） , A ） ，B收到后，自 动 向A返回消息（EPK、以使A知道B确实收到报文m ,（ 1 ）问用户C怎样通过攻击手段获取报文m ?解：当A发给B消息（ E p " （ m） , A ）时，A的身份“ A ”并没有认证，而B在收到消息后也无法对发送者进行检验， 且身份A , B均明文传输，因此用户C可通过如下手段获得报文m ：当A发给B消息（ 4, （ m） , A ）时，C截取该消息并将身份A替换为自己的身份C,将修改后的消息（ 与小（ m） , C）发给接收者B ；B提取消息后，根据身份“ C”将返回消息、 （ 心心（ m） , 8 ）；C再次劫取B返回的消息（ 七用自己的私钥S / Q解密出消息m,并 用A的公钥对m加密后将消息（ 耳啊（ m） , 8 ）发给A o这样，用户C获得了报文m而没有影响A , B之间的正常通信，实现了攻击。

2 ）若通信格式变为：A 发给 B 消息 EP K< （ESK, 4 ）B向A返回消息E p K ,、（ 4.（ 利） , 帆,8 ）这时的安全性如何？分析这时A、B如何相互认证并传递消息m解：根据消息格式，先对消息m进行了签名，然后再进行加密，传送的消息具有了保密性和认证性，敌手无法获得报文明文，安全性提高A , B之间相互认证传递消息的过程如下：B收 到 消 息EPKII （ 小 、 ⑹ , 也 勾 时 ， 先 用B自 己 的 私 钥 解 密 得 到 消 息（ 线储（ 机） ， 见A ） ,然后根据提取的身份信息A,用A的公钥对消息m的签名口的（ 他） 的正确性进行验证，如果验证通过，则说明消息确实来自Ao反 之A用相同的方法可验证E p K . （ESK“ （ / 〃 ） , / 〃 ,8 ）确实来自B,从而实现了相互认证2 . D i f f i e - He l l m a n 密钥交换协议易受中间人攻击，即攻击者截获通信双方通信的内容后可分别冒充通信双方，以获得通信双方协商的密钥详细分析攻击者如何实施攻击解：虽 然 D i f f i e - He l l m a n 密钥交换算法十分巧妙，但由于没有认证功能，存在中间人攻击。

当 A l i c e 和 B o b 交换数据时，T r u dy 拦截通信信息，并冒充A l i c e 欺 骗 B o b , 冒充B o b 欺骗A l i c e 其过程如下：( 1 ) A l i c e 选取大的随机数为 并计算X = g * ( m o d P ) , A l i c e 将 g 、 P 、 X传送给B o b ,但被T r u dy 拦截；( 2 ) T r u dy 冒充A l i c e 选取大的随机数z , 并计算Z = g / ( m o d P ) , T r u dy 将 Z传送给B o b ；( 3) T r u dy 冒充 B o b , 再将 Z = g 二 ( m o d P ) 传送给 A l i c e ；( 4 ) B o b 选取大的随机数y,并计算丫 = gy ( m o d P ) , B o b 将 Y传送给A l i c e , 但被T r u dy 拦截由 ( 1 ) 、( 3) A l i c e 与 T r u dy 共享了一个秘密密钥 g "” ,由 ( 2 ) 、( 4 ) T r u dy 与 B o b 共享了一个秘密密钥g vL以后在通信过程中， 只要Tru dy 作中间人， Al i c e和 B o b 不会发现通信的异常， 但 Tru dy可以获取所有通信内容。

3. D i f f i e-Hel l m a n 密钥交换过程中，设大素数p= l L a = 2是 p 的本原根，( 1) 用户A 的公开钥〃 = 9, 求其秘密钥乂4 解：X 4 满足％ = qX " mod p 即9 = 2、 " m o d l l , 所以有X/ 6 2 ) 设用户B的公开钥匕 =3 , 求 A 和 B的共享密钥K «解：由 D i f f i e-Hel l m a n 协议可知 K = Y 「m o d p = 36 m o d 11 = 3,4. 线性同余算法X ,,+ | =( a X “ ) m o d 24，问：( 1 ) 该算法产生的数列的最大周期是多少？解：由于模m = 2,因此它没有原根，又由递推式不难得知X n = a " X o m o d 2 4 因此该算法产生的序列的最大周期为a m o d 2 4 的最大阶/,而 / |9(2 )但 /夕( 2若 1= 4,则不难验证，X °= l, a = 3时，数列周期为4 ,因此该算法产生数列的最大周期是42) a的值是多少？解：a必须满足gcd(a,2)= I ,所以a在｛ 1,3,5,… ,15｝中取值。

周期为4的有｛ 3,5,11,13｝ ,即为a的取值( 3 )对种子有何限制？解：种子X 必须满足gcd(Xo,24) = L5 .在Shamir秘密分割门限方案中,设k=3, n=5, q=17, 5个子密钥分别是8、7、10＞ 0、1 1 ,从中任选3个，构造插值多项式并求秘密数据s解：取" 1 ) = 8, " 2 ) = 7, /(4 ) = 0构造插值多项式/(x ) = 8( x -2 ) (x-4) /(l-2 ) (l-4 ) +7( x -l)(x -4 ) / ( 2 -l)( 2 -4 ) +0( x -l)(x -2 ) / ( 4 -l)( 4 -2 )= 8( x -2 ) (x -4 ) 6 + 7( x -l)(x -4 ) 8modl7= 2x2 + 1 Ox+13s = /(0 ) = 136 .在基于中国剩余定理的秘密分割门限方案中， 设攵= 2 ,九=3 ,肛=7 ,= 9 ， m3 = " ，三个子秘钥分别是6、3、4 ,求秘密数据s解： 由题设可得S应满足11 =砥＜5＜町加2 =63因为％ = 2 ,鹿= 3 ,仍= 7 , m 2 = 9 ,砥=11, 3个子密钥分别是6, 3, 4 ,那么M=An1x/n2x/T23= 7 x 9 x ll = 693陷 =竺 =丝2 = 99, N, = M；'(modzn,) = 99-1 mod7 = 1m｝ 7= — = — = 77, N?= M「(mod/n,) = 77-i mod 9 = 2丐 9M3 = — = = 63 , N3 = Af3-1 (mod77^) = 63-1 modi 1 = 7m3 11由Si=6, S2= 3可得s = S ' MN + S2M2N2 (mod 63) = 6x99xl + 3x77x 2( mod 63) = 1056(mod 63) =48由$2 = 3 , % = 4可得s = S2M2N2 -FS3M3N3(mod99) = 3x77x2 + 4x63x7(mod99) = 2226(mod99) =48由4=6, $ = 4可得s = S] M [ N、+ s3 M 3 % (mod 77) = 6x99x1 + 4x63x7(mod 77) = 2358(mod 77) =48即秘密数据s为48第6章1. 6.1.3节介绍的数据认证算法是由CBC模式的DES定义的，其中初始向量取为0 ,试说明使用CFB模式也可获得相同结果。

6.1.3节用CBC模式的DES设计数据认证算法为：1 = 蜃 (2 = 琮 (2 ㊉ 3 =以 (2) = ON= EK(DN © EK(DN T ㊉ …㊉ EK(J)2 ㊉/ 3 1 ))… ) 川=EK(DN 0 °N-I)如果改用CFB模式来实现，由于输出为64位，所以必须取/ = 6 4 ,也就是每次移位寄存 器 左 移 整 个6 4位 为 了 达 到 相 同 的 结 果 ， 可 取C F B模 式 中IV = %R = Dl+ 1(i = 1,…N - 1),PN = 0，则有：1 = 2 ㊉ 蜃(DJ3 ㊉ EK(4 ㊉后((2) = 可=EK(°N-I)= EK(DN ® EK(DN T ㊉ …㊉ EK(D2 ㊉ 以 (1 ) ) … )° N -1 = DN ㊉ EK(PN.2)ON = ㊉ EK[°N-I)比较两式，ON作为消息认证码，结果相同2 .有很多哈希函数是由CBC模式的分组加密技术构造的，其中的密钥取为消息分组例如将 消 息M分 成 分 组M1 , M2,...,MN，H o=初 值 ，迭代关系为” = ㊉( i = l , 2 , . . . , N ),哈希值取为HN, 其中E是分组加密算法。

1 )设E为D E S ,第3章的习题已证明如果对明文分组和加密密钥都逐比特取补，那么得到的密文也是原密文的逐比特取补，即如果Y=DESK ( X ) ,那 么 Y，=DESK，( X ， )利用这一结论证明在上述哈希函数中可对消息进行修改但却保持哈希值不变答：敌 手 主 要 是 通 过 修 改 函 数 的 输 入 值 …, 河川和来构造碰撞 = DESMI ( ” o) © HoH2 = DESM2(% )㊉ %利用y '= 七5 / (万')和/ ㊉y ' = x㊉y两个性质可知，若 敌 手 同 时 对 和a 逐比特取补，则由性质一知DESMK % )也被逐比特求补，由性质二知凡保持不变，所以外, …诙也都不受影响，所以有：”(Mlg…= "(Ml%…M v ) =诙(2)若迭代关系用=EH JMMD © 证明仍可对其进行上述攻击答：改迭代关系为e =EH JK M J㊉M j ，则敌手也可同时对M l和H o逐比特取补，由性质一知 DESHO(MI)也被逐比特求补，由性质二知H ] , …HN都不受影响，故仍可进行上述攻击3 .考虑用公钥加密算法构造哈希函数，设算法是RSA,将消息分组后用公开钥加密第一个分组，加密结果与第二个分组异或后，再对其加密，一直进行下去。

设一消息被分成两个分组B i和B 2 ,其哈希值为H ( B i . B2)=RSA(RSA(BI)®B2)» 证明对任一分组 CI 可选 C2 ,使得 H(CI. C? )= H(BI. B ? )证明用这种攻击法，可攻击上述用公钥加密算法构造的哈希函数证明：对任一分组Cl ，可构造C2 如下：C2 = R S A ( CJ ㊉ R S 力 ( B J ㊉ B2，贝 IJW ( C1 (C2) = R S A ( R S 4 ( G )㊉ C2)=R S A ( R S A ( Ci ) © R S 4 ( G ) ® RSA(B^ © B2)=R S 4 ( R S 4 ( B i )㊉ B2)= H回B2)设哈希函数的输入消息分组为M 1 M 2 …MN，则可任取MI替代MI，并由上述方法构造M 2 替代M 2 ，可得…用 力 = " ( 如 时 2 …MJ，攻击成功4.在图6 - 1 1 中， 假定有8 0 个 3 2 比特长的字用于存储每一个W„ 因此在处理信息分组前，可预先计算出这8 0 个值为节省存储空间，考虑有1 6 个字的循环移位寄存器，其初值存储前 1 6 个 值 ( 即 W o, W. . . . . 设计一个算法计算以后的每一个W i 。

答：%~吗 5 为消息分组的1 6 个字，初始放在移位寄存器中，如上图连接电路CL S i 的输出反馈到移位寄存器右边的输入端，则每个时钟到来时，移位寄存器从左边输出端移出一个 字 %（ i = 0 , …, 7 9 ）5. 对 SHA,计算 W % , W 1 7 , W |8, W , 9答：W1 6 = C L S K %㊉上㊉%㊉吗3）W1 7 = C LS i （ 四㊉电㊉明㊉■4）名8 = C LS 1（W2㊉明㊉叫0㊉叫5）Wi g = CLSI”3 ㊉肌㊉ © 名6）6.设a i a 2 a 3初是3 2比特长的字中的4个字节，每一给④可看作由二进制表示的0 ~ 2 5 5之间的整数，在大端方式中，该字表示整数a122 4+ a22l 6+ a328+ a4,在小端结构中，该字表示整数 3 4 2 2 4 + a 3 2 i6 + a 2 2 8 + a i 1 ）MD5使用小端结构，因消息的摘要值不应依赖于算法所用的结构，因 此 在M D 5中为了对以大端方式存储的两个字X =x 1 x 2 x 3 x 4和Y=y l y 2 y 3 y 4进行模2加法运算，必须要对这两个字进行调整，问如何进行？答：由于MD5使用l it t l e- en d ia n结构，而X , Y使用的是b ig - en d ia n存储结构，因此必须把X , Y转换成l it t l e- en d ia n格式, 设转换成：X = X ；石石率，丫' =丫； ）3 ；亦则有%1 22 4 + x221 6 + X328 + %4 = ^4 22 4 + 焉216 + X； 2 8 + X；=> Xjx4, x2“ 3, “ 3 = %4 = "1（ 2 ） S HA使用大端方式， 问如何对以小端结构存储的两个字X和Y进行模2加法运算。

答：由于S HA使 用b ig - en d ia n结构，而X , Y使用的是l it t l e- en d ia n存储结构，因此必须把X , Y转换成b ig - en d ia n格式，设转换成：X， =月月用4丫 = ViV2 y 3 y； 则有X4224 + X321 6 + X228 + jq = x [ 22 4 + x；2 i6 + % ^28 + x4-% [=%4? %2 = %3，%3 = %2，*4 = %]第7章1 . 在 DSS 数字签名标准中，“ = 83 = 2x41 + 1,q = 41,/z = 2 ,于是 g = 2?三 4mod83 ,若取x = 57 ,则y三g '三457 =77mod83在对消息M = 5 6签名时，选择左= 2 3 ,计算签名并进行验证解：( 1)签名过程：为了简化，用 " 代 替" ( M ) ,则用户对消息M的签名为(r,s)计算r = (gk mod p) mod q = (423 mod 83) mod 41 = 51 mod 41 = 10,k~' modq = 23T mod 41 = 25 ,s = + xr)] mod q = [25 x (56 + 57x10)] mod 41 = 29。

所以签名( r,s) = (10,29)2)验证过程：接收方收到的消息为M',签名为(r',s') = (10,29)计算卬=(s')T mod^ = 29-1 mod 41 = 17 ,w , = (W w)m od7 = (56x17)moc141 =9 ,u2 = (r'w)modq = (10x17)mod41 = 6 ,v = Kg"， ) mod p] mod q = [(49 x 776) mod 83] mod 41 = 10因为丫 = 尸 =1 0 ,所以认为签名有效，即验证通过2 .在DSA签名算法中，参数％泄露会产生什么后果？解：若攻击者得到了一个有效签名( r ,s ) ,并且知道了 DSA签名算法中的参数人，那么在签名方程s = [ k ( 〃(M) + xr)]m odg中只存在一个未知数，即用户的秘密钥x ,所以攻击者可以求得秘密钥x = [(依 - " ( " ) ) 尸"m odq 0因此， 参数人泄漏将导致签名秘密钥的泄漏,攻击者可以伪造任意消息的签名第8章1 、假设你知道一个背包问题的解，试设计一个协议，以零知识证明方式证明你的确知道问题的解解一：设背包向量为A ,证明者P知道一个背包容积x的解8,,即A 5 , = x , P以零知识证明方式向验证者证明自己掌握秘密Bx的协议如下：① P随 机 选 取 一 向 量 计 算A By = y,将 y发给V 。

② V 随机选ee{ O , l } , 将 e 发给P ；③ P 计算 C = 3v+ e B , , 即 e = 0 时，C = ； e = l 时，C = B 、 + B 、,将 发给 V 注：如果e = 0 , P展示y的解，即 B 、, ；如果e = l , P展示被加密的y的解，即纥, + 81④ 若 A C = y + ex , V 接受P的证明协议的完备性、正确性和安全性( 1 ) 完备性：如 果 P和 V 遵守协议，且 P知道x的解B 、 ，则应答使得A C = y + ex , V接受P的证明 2 ) 正确性：假冒的证明者E可按以下方式以的概率骗得V 接受自己的证明：2① E随机选取一向量4 和g e { 0 , 1 } , 计算4?v = y,将 y —次 发 给 V ② V 随机选ee{ 0 , l } , 将 e 发给E ；③ £ 将 与 发 给 丫 V 的验证方程为A8 ) , = y —法 + ex 当々=6时 ・ ， 方程成立， V 接受E的证明， E欺骗成功因々= 6的 概 率 是 所 以 E成功的概率是上2 2另一方面，▲是E成功的最好概率，否则假定E 以大于' 的概率使V相信自己的证明，那2 2么 E 知道一个y , 对这个y , 他可以正确回答V的两个询问e = 0和 e = l, 意味着E 能计算 4G = % A C2 = y + x ,由此可计算x = A(G —G )，因此得秘密纥= (G - G )。

3 ) 安全性：根据以上的讨论知，假冒的证明者E 欺 骗 V成功的概率为上 ，这个概率太大2了• 为减少这个概率，可以将协议重复执行多次，设执行， 次，则欺骗成功的概率将减少到万 解二：⑴ 构造背包问题先选大素数N , g , l < g < N , N是素数，且( N — 1 ) /2也为素数，g为N的本原根P随机选取f个整数S - S2, S ,( 不用超递增序列) ，计算V , = g " m o d NV2 = g ® m o d NIII匕-gs, m o d N式中S-S2, S ,为秘密密钥；N , g , V ,,匕 ，…，V ,为公开 2 )零知识证明协议1 ) P随机选择r ，计 算x = g ' m o d N ,并将x传送给V ；2 ) V随机选择f个二进制比特序列伪，b2, b,,并将其传送给P ；3 ) P计算M y = M + r ,并将其传送给V/ = !4 ) V验证，计算i = l ， 2 ,…,ty' = xZ,Z2-Z ,比较y = y' 是否成立，若成立，说明P了 解 秘 密 密 钥S 2 ,…，S ,;反之，P为假冒。

3 )安全性此类算法的安全威胁主要来自P欺骗V或V假冒P 假如使用的背包和离散对数没有问题，P欺骗v和v假冒p成功的概率都基于伪( I K i K f )的随机性，若每一个伪( 1 K i

当A将42发 给B时，B由gcd(55, 42 + 2) = 11得到〃的一个因子，从而得到”的分解式1 1 x 5 ,从而获得A的秘密3当A将53发 给B时，因53三2m od55,所 以B不能计算出〃的一个因子，没有得到任何新信息，从而不能获得A的 秘 密 3、 设p是素数， 群Z；的元素g是群Z；的生成元， 当且仅当对每一九eZ ； ,存在一整数x ,使得〃三g* mod p1)在Z；中均匀、随机选取一元素〃，证明，如果g不是Z；的生成元，则存在一整数x ,使得h三g ' m o d p成立的概率至多是: 2 ) 给出g 是 Z ； 的生成元的零知识证明3 ) 在(2 ) 中的零知识证明中，证明者能否在多项式时间内完成证明，为什么？解：(1 ) 因为g 不是Z ； 的生成元，记 循 环 群 为 “ ，显然H 是Z ； 的子群， 且设 司 = r , r 是一个大于1 的正整数，所以2 =I M Z ； r 2在 Z ； 中均匀、随机选取一元素h,若hs H ,则可在H上找到一个x , 使得h = g ' m o d p成立而 / z e H 的概率至多是: ，所以/? 三g* m o d p 成立的概率至多是: 。

2 ) ① V在 Z ； 中任意取一个元素h,发送给P ② P知道x, 使得/zmg ' m o d p P在 Z ； 中随机取一个元素4 , 计 算 "三 g “ m o d ”并发送给V③ V随机选ee{0』} , 将 e 发给P ；④P计算力= Z + e x 并发送给V⑤ V验证屋若成立，则接受P的证明⑥P和 V重复以上过程〃次3 ) 以上的证明可以在多项式时间内完成因为，〃是一个有限值，4 三g& m o d/? 可以在多项式时间内完成4、 设n 是两个未知大素数p和q 的乘积，X o ， X i e Z ； 且其中至少一个是模n 的二次剩余又设x 0,x i模n 的 Jac o bi符号都为1 ,考虑下面交互证明系统，其中x 0,X i和n 作为输入，P为证明者，V为验证者：(1 ) P 随 机 选 择 i —R {0,l },V b， V i_ b —R Z],计 算 yb = V b m o d n 及 y - b 三vi- b(xi- b) 1 m o d n , 将y ,以发送给 V2 ) V随机选择c -R {0,1 },将c 发送给P o(3 ) P 计算Z b 三 u i@ C vbm o dn . z. b m v . b ，将z^ Z I 发送给 V。

4) V 检 查 * = y0 m o d n 和za =x[y1 m o d n 是否成立，或z xoyo m o d n 和 好 =x|- cyx mod n是否成立如果不成立，则拒绝并终止以上过程重复log2(v)次1 )证明以上协议证明了x0,xi中至少有一个是模n的二次剩余2 )证明以上协议是完备的解：(1 )对于给定的y ,力和x0,xi，证明者P都能够回答c = 0或c = 1的两个挑战；故说明yo和yoxo都是模九 的二次剩余或者乃和当x i都是模n的二次剩余；根据数论知识可得：X 或均至少有一个是模n的二次剩余2 )若Prover和Verifier都是诚实的，且(1)是正确的，显然，验证者最终会接受证明者的证明第9章可证明安全习题1、解释主义安全的概念，这一概念可用于抵抗如下攻击吗？1） 、被动的多项式时间有界敌手；2） 、被动的多项式时间无界敌手；3） 、主动的多项式时间有界敌手答：语义安全：一个安全的加密方案应使敌手通过密文得不到任何信息，即使是1 比特的信息此概念可用于抵抗被动的多项式时间有界敌手和主动的多项式有界敌手， 但不能抵抗被动的多项式无界敌手。

2. Rabin密码体制是IND-CPA安全的吗？是IND-CCA安全的吗？是IND-CCA2安全的吗？答: Rabin密码体制Rabin密码体制是RSA密码体制的一种修正， 假定模数〃 = pq不能被分解，该类体制对于选择明文攻击是计算安全的因此，Rabin密码体制提供了一个可证明安全的密码体制的例子： 假定分解整数问题是整数上不可行的,那 么 Rabin密码体制是安全的Rabin密码体制：（ 一）密钥生成设〃 = p q , 其 中 p 和乡是素数，且〃三“三3（ mod4） ,即这两个素数形式为4Z + 3 , 计算n = pq.〃为公钥，p ,q 为私钥 二）加密c = nr mod n其中6 是明文分组，c是对应的密文分组 三）解密解密也就是求C模〃的平方根，即 解 / 三 cmod” ，该方程等价于方程组：x2 = c mod px1 =c mod q由于p 三q 三3(m od4),所以可以解出每个方程有两个解：x = y mod p.x = -y mod px = z mod q,x = -z mod q两两组合可得4 个同余方程组：① x = ym odpx = z mod q② x 三ymodpx = -z mod q③、X 三- ym odpx = z mod q④ x = -y mod px = -z mod q由中国剩余定理可解出每一个方程组的解， 共四个，即每一密文对应的明文不唯0为有效确定明文一般在〃? 中加入某些代表性信息，如：发送者身份号、接受者身份号、时间、日期等下面证明，当〃三q 三3(mod4)时，两个方程V 三cmodp , V 三cm odq的平方根都很容易求出。

由p 三3(mod4)得，p + l = 4 Z ,即: ( p + 1)是一个整数因c 是模p 的平方剩余，故 色 三 c

离 散 对 数 问 题 （ D i s c r e t e L o g a r i t hm 问题 ， DL问题） 是已知（ g , g ， ） ， 计 算 x 证明如下关系：D L u C D H u D D H证明：1 ） 、证明定义DDH假设： 设G是阶为大素数q的群， g为G的生成元 则以下两个分布：随机四元组 R = （ g , g X , g >, g Z ） e G 4 （ g , g ' , g ' , g D e G ’（ 称为D i f f i e - H e l l m a n 四元组，简称DH四元组） 是计算上不可区分的，称为DDH假设具体地说，对任一敌手A , A区分R 和的优势是£ 可忽略的设R°H是R 构成的集合，D°H是构成的集合下面构造一个敌手B, B 利用A来攻击C D H 问题设- RZ q Q e G.g e GB 输入四元组T = （ g , ggt ） ,目标是判断T e R 的还是T eT — B, /7G{ 0,1}"A如果用= 1则说明T e D ” ，输出熄= r ；否则夕= 0 则说明TGR . , 终止。

此时B 选中t 的概率是'，故B 获胜的概率是£q q2） 、证 明 "由C D H 问题可知，对任一敌手A , 在已知（ g ,g ' ,g ' ） 情况下，A计算g ”的优势是£ 可忽略的那么下面构造一个敌手C, C利用A 来攻击DL问题则C 已知（ g,g"） ,目标是计算x 设 ,GZ；, 且{g， g " } —Bg ""-A如果：g" = g * 贝 Ux = 6 ；或 g浦= g〃 * ， 则 x = a ；否则终止此时敌手C选中光的概率为士q又因为A 计算源的优势是£ ,所以C获胜的概率为主q4.设r r = （ Enc； Dec） 是单钥加密方案， 将 9 2 2 节中的加密方案修改如下:输 入 公开钥（ 〃 ,e） 和消息加” 0,1产 ） ，选择一个随机数「 一 逐： ，输出密文（ rf mod n, Enck （ w） ） o证 明 如 果 R S A 问题是困难的，则修改后的加密方案是IND-CPA安全的公钥加密方案证明：设 GenRSA是 RSA加密方案的密钥生成算法，它的输入为K , 输出为模数 " （ 为 2 个 K 比特素数的乘积） ，整数 e ,d 满 足 ed三lm od/（ 〃 ） 。

又设H: {0,l『 K f {0,广⑺是一个哈希函数，其中/（K）是一个任意的多项式加密方案□' 如下：密钥产生过程：KeyGen（K）：（ 7 1 , e,d） — GenRSA（K） 、pk = (〃, e), sk = (n, d) o加密过程(其中m e {0,1严 )EpK(m )：k = H (r)；输 出(remod〃，Enek{m})解密过程：r = C： mod n ；输出 Deck (m) □定理：设”是一个随机谕言机，如果与方案GenRSA相关的R SA问题是困难的，则方案口' 是IND-CPA安全的即，设存在一个IND-CPA敌手A以£ 的优势攻破方案F T ,那么一定存在一个敌手B至少以Adi俨(K) > 2式K)的优势解决RSA问题证明：□' 的IND-CPA游戏如下：EXP^'M-.(〃,e, d) < — GenRS A(K) ;pk = , sk = (n,d);{0,1尸} ;k = H⑺;(人,仍) < -A*(pZ),其中瓜| = 网= /(K) ;尸一R{ 」 }，r 一避“ ;C* = (r,- mod n, Enek (mp))B — N (pk,C *)如果，= 。

则返回1 ,否则返回0敌手的优势定义为安全参数K的函数：A d v f （ K ） = P r [ & p f （ K ） = l ] — g下面证明IT方案可归约到R S A假设敌手B已知（ 〃 ,e£） ,以A （ 攻击IT方案）作为子程序，进行以下过程，目标是计算户三©）61 m o d 〃 o1）选取一个随机串A- R{0,1}“K＞， 作为H⑺的猜测值， 将公钥（ 〃 ,e ）发给A o2） H询问：B建立一个表”面 （ 初始为空），元素类型（ % 4 ） , A在任何时 候 都 能 发 出 对 的 询 问，B做如下应答（ 设询问为x ）/ 如果x已经在〃面，则以（ x , / i ）中的/ i应答；/ 如果£三 © m o d 〃以/ ? 应答，将（ x ,百 ） 存入表中，并记下户=% /否则随机选择以/ ? 应答，并将（ x ,〃 ） 存入表中3） 挑战：A输出两个挑战的消息相 和㈣，B随机选择1一 《 {0, 1} ,并令 k = h , c2 = E nck（ i np）将（ © ） 给A作为密文4）在A执行结束后（ 在输出其猜测之后） ，B输出第2）步记下的户=无。

设H表示事件：在模拟中A发出”（ 力询问，即”（ 户 ） 出 现 在 中 断言1：在以上模拟过程中，B的模拟是完备的证明在以上模拟中，A的视图与其在真实攻击中的视图是同分布的，这是因为1） A的，询问中的每一个都是用随机值来回答的而在A对n的真实攻击中，A得到的是”的函数值，由于假定H是随机谕言机，所以A得到的”的函数值是均匀的2） 对A来说， 为左对叼做一次密加密由左的随机性，£ 1“ %（ % ）对A来说是随机的所以两种视图不可区分断言2：在上述模拟攻击中Pr [ H ] N 2£证明：显然有Pr [ E x p f （ K ） = l | [ H ] = ；又由A在真实攻击中的定义，可知A的优势大于等于 £ , 得A在模拟攻击中的优势也为Pr[ 瓯f（ K ） = l ] - gPr [ E ＜ （ K ） = l ]= Pr [E xp' ^K） = 1 HH ] Pr [ ^ H ] + Pr [版 ： '（K） = 11 H ] Pr [ H ]＜Pr[ 国f（ K ） = l | [ H ] Pr [ [ H ] + Pr [ H ]= g p r [ [ H ] + Pr [ H ]= 1 （ l - Pr [ H ] ） + Pr [ H ]= - + - Pr [ H l2 2 1 J又知：Pr [ E ＜ （ K ） = l ]N Pr[ 瓯 f（ K ） = l | [ H ] Pr [「H ]= 1d - Pr [ H ] ）所以£WPr [ E x ^ （ / c ） = l ] - 1| < | p r [ H ]即模拟攻击中Pr [ H ] N 2£。

由以上两个断言， 在上述模拟过程中r以至少2 e的概率出现在Hli s, 若H发生，则B在 第（ 2）步可找到x满足V三 m o d " ,即次 三 户 三（ 3尸m o d 〃所以B成功的概率与H发生的概率相同5 .Cramer-Shoup密码体制也使用哈希函数， 其安全性证明为什么不是随机谕言机模型？答：首先回顾随机谕言机的定义在对方案进行安全性分析时，将其中的哈希函数视为随机谕言机随机谕言机是一个魔盒，对 用 户 ( 包 括 敌 手 ) 来 说 ，魔盒内部的工作原理及状态都是未知的 用户能够与这个魔盒交互，方式是向魔盒输入一个比特串x ,魔盒输出比特串) ( 对用户来说，y是均匀分布的) 这一过程称为用户向随机谕言机询问 由于这种哈希函数工作原理和内部状态是未知的,因此不能用通常的公开哈希函数在安全性的归约证明中，敌手A需要哈希函数值时，只能由敌手B为他产生之所以以这种方式使用哈希函数，是因为B要把欲攻击的困难问题嵌入到哈希函数值中 这种安全性称为随机谕言机模型下的如果不把哈希函数当作随机谕言机，则安全性称为标准模型下的而Gramer-Shoup的证明过程无需把困难问题嵌入到哈希函数中，所以它是标准模型下的证明过程。

6 . ( 1 )在PaiUier方 案1中，设，九 = 5x7 , g = 1 3 ,在对〃 =23加密时,取r= 1 9 ,计算密文，并验证解密过程 2 )在Paillier方 案2中，设〃 = 5x7, g = 1 3 ,计算机=1178的密文，并验证解密过程答：因为在Paillier方 案1中，加密算法为：C T = gmrn modn1解密算法为：" C 7 'm o d后 mod〃 三 “L(g mod/r)所以当〃 = 5x7, g = 1 3 ,加= 2 3 ,厂=19时 ， 其 帝 又 为 ：gmrH mod n2 = 1323 xl935 mod352 = [(1323 mod 352)x(1935 mod352)]mod352= (342 x 734) mod 352 =1128解密过程：解密为:MM Crm odn2) 4 砧 U S L了跖曲^ ^厂而二= [[CT]J modn即[[1128]] , mod 35第10章1 . 下面是X.509三向认证的最初版本A -B： A{tA,rA,B}B->A:B{tB,rB,A,rA}A-> B: A{.}假定协议不使用时间戳， 可在其中将所有时间戳设置为0 , 则攻击者C 如果截获A、B 之前执行协议时的消息，就可假冒A 和 B , 以使A（ B） 相信通信的对方是B（ A） .请提出一种不使用时间戳的、防中间人欺骗的简单方法。

答：方案如下：A- 5： A{tA,rA,B,flagA}8 ^A :B {tB,rB,A,rA,flagB]B:A{rB, flagA}需要交互的用户A 和 B 提前设置一个只有双方知道的口令passwordo 其中的力ag = password ㊉ r □当接收方收到发送方的消息之后进行：力伤㊉「，若得的值为之前商定好的password值，则说明发送方的可信的上述过程即是不使用时间戳的、防止中间人欺骗的一种简单方法2 . 在 PGP中， 若用户有N 个公开钥， 则密钥ID至少有两个重复的概率有多大？解： 在 PGP中， 用公开钥中64个最低有效位表示该密钥的ID ,即公开钥尸 " 的ID是PKA mod264 由于64位已经足够长， 所以不同密钥ID重复的概率非常小密钥ID 的可能取值共有2“ 种， 则当用户有N个公开钥时, ID取值共有（ 2M） “ 种,密钥ID至少有两个重复的概率为1 -7而2” !——（ 2M） % （ 264 -A^） !3 .在PGP中，先对消息签名再对签名加密，请详细说明这一顺序为什么优于先加密再对加密结果签名答： 将签字与明文消息在一起存储比与密文消息在一起存储会带来很多方便，同时也给第三方对签字的验证带来方便。

如果先加密消息再对消息签字， 签字将和密文消息放在一起，这不利于存储消息，也不利于第三方验证签字另外，加密之前需要压缩，对不压缩的消息签字，可便于以后对签字的验证如果对压缩后的消息签字，则为了以后对签字的验证，需存储压缩后的消息或在验证签字时对消息重做压缩并且，zip压缩算法是不确定性的，该算法在不同的实现中会由于在运行速度和压缩率之间产生不同的折中，产生出不同的压缩结果4 .在PGP的消息格式中，消息摘要的前两个8比特位组以明文形式传输 1）说明这种形式对哈希函数的安全性有多大程度的影响答：首先，哈希函数满足如下几个性质（ 1）输入为任意长度，输出为固定长度，便于计算与实现 2）哈希函数具有单向性 3）哈希函数具有抗碰撞性在PGP中，消息摘要有SHA对签名的时间戳链接上本身后求得的160比特哈希函数输出结果公开的消息摘要的前两个8比特位数组（ 哈希结果的前两个8比特位数组内容） ，对哈希函数的安全性没有影响 2）接收方用消息摘要的前两个8比特位组，确定自己在验证发送方的数字签名时是否正确地使用了发送方的公开钥，其可信程度有多大？答：消息摘要是对签名的时间戳链接上消息本身后求得的160比特函数输出， 然后再由发送方使用秘密要进行签名所得。

接收方验证签名时，即为使用对应发送方公钥进行签名验证， 其可信程度与签名算法的安全性相关，如果使用的签名算法具有不可伪造性，那么这种验证方式就是可信安全的5 . 在 表10-2中，公钥环中的每一项都有一个拥有者可信字段，用以表示这一公钥的属主（ 即拥有这一公钥的用户） 的可信程度 这一字段能否充分表达PGP对这一公钥的信任？如果不能，则如何实现PGP对这一公钥的信任？解：PG P是一个网络，每个人在信任链中都作为到另一个人的介绍人PG P把密钥签名作为一种介绍形式当某个人签署了一个密钥时， 他就成为那个密钥的潜在介绍人例如，假 设 Alice签署了 B ob的密钥，而 Bob签署了 Charlie的密钥A lice现在就有了一个到C hrlie的证明路径A lice现在有一种方式知道Charlie的密钥确实是Charlie的，因为上面有B ob的签名，而 且 Alice知 道 Bob的密钥确实是B ob的这是一种在密钥中提供可传递的信任这个设计中有一个明显的问题如果有人作为介绍人， 但是并不真正知道他所介绍的人会怎么样呢？例如，如 果 B ob非常粗心，虽然签署了 D oug的密钥，却宣称是Charlie的。

不 仅 Bob认为这处密钥属于Charlie ( 尽管是Doug但却宣称它属于C harlie),而且因为对受托性没有一种度量，Alice也会相信这就是PGP信任网中所发生的通过信任网( Web of T ru st),用户定义了对一个密钥的信任量，作为介绍人在前面的例子中，Alice给 予 B ob的密钥尽可能多的信任，而且如果他相信B o b 正确地签署了其他人的密钥，他也会相信这个密钥如果Alice知 道 Bob对于密钥验证很松懈， 他就不会再信任Bob作介绍人了 其结果是, Alice不会再相信Bob为 Doug签署的但宣称为Charlie的密钥当然，信任网也不是绝对安全如果有人被欺骗签署了一个错误的密钥，它就会使得其他人错误地相信它 PGP信任网被认为是一个声誉系统， 受到尊敬的人给出好的签名，其他人则给出不好的签名当存在错误的声誉时，系统就可能失效综上所述， 我们可知， PG P的信任字段并不能充分表达用户对这一公钥的信任用户要根据证书链以及信誉系统来计算对特定公钥的信任程度如果使用用户充分信任的第三方机构或个人为特定公钥签字， 可以实现用户对这一公钥的充分信任。