密码学 课后习题.doc

_第三章：3-1 使用密钥字为common的代换密码方案，列出字母代换表解：去除后来重复的字母后，真正的密钥字为comn 明文密文COMNABDEFGHIJ明文密文KLPQRSTUVWXYZ3-2 解密下面的一段恺撒密码密文（明文单词间留空，以便阅读）：EHVWWLPHRIWKHBHDULVVSULQJZKHQIORZHUVEORRP解：将密文字母在英文字母表上前移3个位置，即可得到这段恺撒密码密文对应的明文如下： best time of the year is spring when flowers bloom3-3 利用仿射密码算法加密下面的明文，假设k1=7，k2=3（要求首先列出明文字母-密文字母代换表，然后给出对应的密文，并以字母t的加密为例给出计算过程）：解：因为k1=7，k2=3，因此仿射密码的加密公式为字母t（19）被加密为完整的明文字母-密文字母代换表如下表所示： 明文密文DKRYFMTAHOVCJ明文密文QXELSZGNUBIPW3-4 解密3-3题所得仿射密码密文，并以密文字母F的解密为例说明计算过程。解：因为k1=7，k2=3，因此，根据仿射密码的解密公式，有密文字母F（5）解密为： 密文ABCDEFGHIJKLM明文 hwlapetixmbqf密文NOPQRSTUVWXYZ明文ujyncrgvkzods3-5 使用密钥字student 对明文cryptography进行维吉尼亚密码加密和解密，要求仿照表3-7（P51）给出其加密和解密过程，并说明相同明文字符的加密结果。解：去除密钥字student中后来重复的字母后，真正的密钥为studen。因此，应将明文、密文按照6位长度进行分组，每组使用同样的密钥studen加密、解密。 3-6 选择希尔密码的加密密钥矩阵k为：试以明文love为例解：将明文字符love变换为数字，分别为11、14、21、4。 因为加密密钥矩阵k为2阶矩阵，所以应将明文分成和两组分别进行加密。 （1）确定解密密钥矩阵k-1 （见表2-2（P21）（2）加密因此，明文字符love的加密密文为ZQFS。（3）解密 因此，密文字符ZQFS的解密明文为love，即解密后恢复了原来的明文。3-7 使用每行5个字符的格子和密钥字money，将下面的明文置乱为密文（多余的空格内依次填入字母a、b、c）：cryptography is the science and study of secret writing提示：将密钥字money变换为数字（字母表上最靠前的密钥字母用0表示，然后依次递增），即是读出列的顺序。解：置乱密码的格纸表如下表所示： 列行012340crypt1ograp2hyist3hesci4encea5ndstu6dyofs7ecret8writi9ngabc根据密钥字money，得到读出列的顺序为1、3、2、0、4。按照此顺序读出各列，得到置乱密文如下：RGYENDYCRG PASCETFETB YRISCSORIA COHHENDEWN TPTIAUSTIC3-9 用频数法破译下面的一段仿射密码密文（不含空格）：FMXVE DKAPH FERBN DKRXR SREFM ORUDS DKDVS HVUFE DKAPR KDLYE VLRHH RH解：（1）密文字母频数统计该段仿射密码密文一共有57个密文字符，密文字母出现的频数如下表所示：字母ABCDEFGHIJKLMNOPQRSTUVWXYZ频数21075405005221120830240210从上表可见频数比较高的密文字母：R：8 ； D：7； E、H、K：5 ； F、V：4而明文字母频数比较高的几个英文字母依次为e、t、a、o、i、n、s、h、r。（2）假设与推论、证实 第一次假设：频数最高的密文字母R（17）对应频数最高的明文字母e（4）, 频数次高的密文字母D（3）对应频数次高的明文字母t（19）。第二次假设：频数最高的密文字母R（17）对应频数最高的明文字母e（4）, 频数第三高的密文字母E（4）对应频数次高的明文字母t（19）。第三次假设：频数最高的密文字母R（17）对应频数最高的明文字母e（4）, 频数并列第三的密文字母H（7）对应频数次高的明文字母t（19）。第四次假设：频数最高的密文字母R（17）对应频数最高的明文字母e（4）, 频数并列第三的密文字母K（10）对应频数次高的明文字母t（19）。根据仿射密码的加密公式，列出密文和明文的关系方程组如下： -得：解得：由于，因此存在乘法逆元，且，说明第四次假设正确。将代入式，得：因此，破译得到该仿射密码的加密密钥为，。将它们代入仿射密码的解密公式，得到： 将密文字母代入式，得到对应的明文字母，如下表所示： 密ABCDEFGHIJKLMNOPQRSTUVWXYZ明hqzirajsbktcludmvenwfoxgpy例如，密文字母U（20）代入式，得到明文字母为 对照题上表，将密文变换为明文，得到如下的一段具有明确意义的明文： algorithms are quite general definitions of arithmetic processes第四章： 4-5 分别使用（4-14）式和表4-1的S盒查找表，求16进制数5c和e2的字节代换结果。已知5c-1=51，e2-1=d6。解 由于5c-1=51=（01010001）而根据表4-1的S盒查找表，可以直接得到5c的字节代换结果为4a，可见二者结果相同。同理，由于e2-1=d6=（11010110），根据（4-14）式，有而根据表4-1的S盒查找表，可以直接得到e2的字节代换结果为98，可见二者结果也相同。4-6 AES的中间态如题4-6图所示。求AES对其执行行移位运算ShiftRows后的结果。e55f18ae C30698311A5275d 627C41c0b4eCbfE1e7b8De02d47305e58f1Cae65235dA98711641Cb4c0bfeC27E1e7b8De02d47解 AES对其执行行移位运算ShiftRows后的结果如题4-6图2所示。4-7 分别用多项式乘法、移位相加法和表操作法计算下列字节乘法运算：（1） （2）解 （1），。 多项式乘法计算字节乘法运算 移位相加法计算字节乘法运算由于，且因此，有 表操作法计算字节乘法运算查表4-2的对数表，有：，。因此，查表4-3的反对数表，有：。因此，。4-9 利用的已知结果，证明域上的元素。解4-10 利用表操作法，计算域上的元素和的乘法逆元。解：，根据表4-2，有，因此，根据表4-3，得到4-11 分别用移位相加法和表操作法计算AES的下列字运算：（1）（2）解（1） 移位相加法计算 表操作法计算（2） 移位相加法计算 表操作法计算4-12 假设128比特种子密钥k为：k=ab 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c试仿照表4-6列表给出轮密钥字的密钥扩展过程及结果。解 轮密钥字的密钥扩展过程及结果如题4-12表所示。0ab7e1516128aed2a62abf71588309cf4f3c409cf4f3ccf4f3c098a84eb01010000008b84eb01ab7e151620fafe17520fafe1728aed2a608542cb1608542cb1abf71588a3a339397a3a3393909cf4f3caa6c76058aa6c76056c7605aa50386bac0200000052386bac20fafe1772c295bb972c295bb08542cb17a96b90a4-20 画出题4-20图所示4级序列产生器的全状态图，从最小的非0状态开始写出一个周期的输出序列，并说明它是否是m序列产生器。题4-20图 4级序列产生器解：该4级序列产生器的全状态图如题4-20图2所示。由图可见，从最小的非0状态开始，一个周期的输出序列为100011110101100，其周期为15，因此它是m序列产生器。0000000110001100111011110111101101011010110101100011100101000010题4-20图2 4级序列产生器的全状态图4-23 检验周期序列“100011110101100”的平衡特性、游程特性和自相关特性。其中，自相关特性直接通过（4-57）式和（4-58）式的计算来进行检验。解：（1）平衡特性检验。该序列的周期为15 ，且一个周期中有8个“1”、7个“0”，因此符合戈龙提出的随机性公设中的平衡特性。如用频数法检验，将、代入（4-59）式，有显然，它远远小于1自由度的分布表中5%显著性水平值3.84，所以通过频数检验。（2） 游程特性检验。该序列的一个周期中，有两个长度为1的“1”游程，有1个长度为2的“1”游程，有1个长度为4的“1”游程，“1”游程的总数为4。除了长度为4的“1”游程外，长度为1的“1”游程数为“1”游程总数的1/2，长度为2的“1”游程数为“1”游程总数的1/4，因此基本符合游程特性。同样，该序列的一个周期中，有两个长度为1的“0”游程，有1个长度为2的“0”游程，有1个长度为3的“0”游程，“0”游程的总数为4。除了长度为3的“0”游程外，长度为1的“0”游程数为“0”游程总数的1/2，长度为2的“0”游程数为“0”游程总数的1/4，因此也基本符合游程特性。（3）自相关特性检验。检验结果见题4-23表。从该表可见： 该序列的自相关函数值符合（4-58）式的特性，即时，；时，。因此该序列具有很好的自相关特性。 自相关函数具有周期性，其周期与要检验序列的周期相同。题4-23表 自相关特性检验序列相同位数A不同位数D01000111101011001501100011110101100178-1/15200111101011001078-1/15301111010110010078-1/15411110101100100078-1/15511101011001000178-1/15611010110010001178-1/15710101100100011178-1/15801011001000111178-1/15910110010001111078-1/151001100100011110178-1/151111001000111101078-1/151210010001111010178-1/151300100011110101178-1/151401000111101011078-1/15151000111101011001501第5章： 5-5在RSA体制中：（1）若,，求、和。（2）若，求。该计算结果说明了什么问题？解 （1），（2）由于，因此,。该结果说明， 、太小是不安全的，攻击者容易通过因式分解从分解出、，并进而根据和计算出私钥。5-6使用快速计算法计算下列模指数，要求列表给出计算过程。（1）1613 mod 4661 （2）432159 mod 4661解（1）b=13=（1101），a=16，n=4661，计算过程如下表所示31211001 因此，。（2）b=59=（111011），a=4321，n=4661，计算过程如下表所示。514131201101 因此，。5-7假设Alice和Bob采用RSA密码体制进行保密通信。已知Alice的公钥为（eA，nA）=(13，115)，私钥为（dA，nA）=（62，115）；Bob的公钥为（eB，nB）=(7，119)，私钥为（dB，nB）=（55，119）。（1）若Alice想将明文加密后传送给Bob，试计算密文。（2）若Bob要解密密文，试计算明文。解（1）（2）5-8 假设Alice和Bob采用RSA密码体制进行保密通信。已知Alice的公钥为（eA，nA）=(13，115)，私钥为（dA，nA）=（62，115）；Bob的公钥为（eB，nB）=(1223，2867)，私钥为（dB，nB）=（167，2867）。字符代换规则为：字母az分别用0126表示，空格用00表示。（1) 若Alice想将明文“rsa algorithm”秘密地发送给Bob，帮Alice计算密文。（2）Bob收到Alice发来的密文后，帮Bob计算明文，并将明文替换回英文字符。（3）若Bob想将明文“rs”秘密地发送给Alice，帮Bob计算密文。解（1）由于Bob的模数nB=2867，因此Alice可以一次加密两个字符。将明文“rsa algorithm”替换为数字，并按两个字符分组为：1819 0100 0112 0715 1809 2008 1300。各组明文加密如下：因此，Alice加密后的密文为：2756 2001 0542 0669 2347 0408 1815。（2）Bob收到Alice发来的密文后，分组解密得到各组明文：因此，Bob解密后的明文为：1819 0100 0112 0715 1809 2008 1300。替换回英文字符后，明文为：rsa algorithm。（3）由于Alice的模数nA=115，因此Bob只能一次加密一个字符。将明文“rs”替换为数字，为：18 19。各组明文加密如下：因此，Bob加密后的密文为：48 99。5-9 假设Alice采用EIGamal密码体制，并选择素数，私钥， 且已知的一个生成元。（1） 计算Alice的公钥y。（2） 若Bob想秘密发送消息给Alice，且他选择的随机数，试给出Bob和Alice的加密和解密过程。（3）若Bob发送上述密文时，不慎将密文交换了位置，会出现什么问题？解（1）Alice的公钥。（2）Bob和Alice的加密和解密过程Bob加密：Alice解密：（3）若Bob发送上述密文时，不慎将密文交换了位置，Alice将无法正确解密。此时，Alice的解密结果为：5-10 说明实数域上的椭圆曲线能否构成一个阿贝尔群。解 由于、，因此，不满足（5-37）式关于的要求，所以实数域上的椭圆曲线不能构成一个阿贝尔群。5-11找出素域上的椭圆曲线即上的所有点。解 对于、的所有可能值010，列一张方表如题5-11表所示，逐对验证、值是否素域上椭圆曲线即上的点（注意，数值运算时要进行mod 11运算）。若是，对应表格内划；若不是，对应表格内不做记号。题5-11表 寻找素域上椭圆曲线即上的所有点012345678910012345678910根据题5-11表，得到素域上椭圆曲线即上的所有点（不含无穷远点）为：（2,4）,（2,7）,（3,5）,（3,6）,（5,2）,（5,9）,（7,2）,（7,9）, （8,3）, （8,8）, （10,2）,（10,9）。5-13 由不可约多项式定义的有限域有一个生成元，非0元素与生成元的关系参见表5-4。已知上的椭圆曲线为，其上的两个点分别为和。计算：（1） （2）（3） （4）解 ，。（1）由于，因此Q与R为互逆点。根据互逆点规则和（5-61）式，有因此，有。（2）。因为，所以P、R是非互逆点。根据（5-65）式，有将代入（5-63）、（5-64）式，得到因此，有（3） 。根据倍点规则，有将代入（5-67）和（5-68）式，得到 因此，有（4）。首先计算。根据倍点规则，有将代入（5-67）和（5-68）式，得到 因此，有再计算。因为，所以P、W是非互逆点。根据（5-65）式，有将代入（5-63）、（5-64）式，得到因此，有5-15 由不可约多项式定义的有限域有一个生成元，非0元素与生成元的关系参见表5-4。已知上的椭圆曲线为，以其上阶的点构造椭圆曲线的子群。假设Alice和Bob使用基于上述参数的椭圆曲线密码体制进行保密通信。（1） 若Bob选择私钥，计算Bob的公钥。（2） 若Alice要秘密发送消息m=（01101011）给Bob，给出Alice的加密过程。假设她随机选择整数，满足。（3） 给出Bob的解密过程。（4） 该题的参数选择是否有问题？为什么？解 ，。（1）计算Bob的公钥：根据（5-80）式，Bob的公钥为：假设：则有：现在，首先计算。根据倍点规则，有将代入（5-67）和（5-68）式，得到 因此，有然后，计算Bob的公钥。由于，因此不是互逆点。根据（5-65）式，有 将代入（5-63）、（5-64）式，得到因此，有（2）Alice要秘密发送消息m=（01101011）给Bob的加密过程