《01信息安全基础综合实验讲义(模指数运算)》由会员分享，可在线阅读，更多相关《01信息安全基础综合实验讲义(模指数运算)（5页珍藏版）》请在金锄头文库上搜索。
1、 1第一部分第一部分 数论基础实验数论基础实验 1.1 模指数运算的实现模指数运算的实现 模指数运算（Modular Exponentiation）在密码学中占有重要地位。公钥密码体制（例如RSA、ELGammal） 、单向散列函数以及它们的应用都需要用到模指数运算。 一、实验目的一、实验目的 熟悉模指数运算算法，通过编程实现一种模指数运算算法，加深对模指数运算的理解。 二、实验原理二、实验原理 在模指数算法中，运算 ae mod m 最后都转化为一系列的模乘法运算，其转换方法构成模指数算法的核心。实现模指数运算的最直接的方法是利用模运算的性质，将模指数运算ae mod m 转换为( mod
2、) ( mod ) . ( mod )mod amamamm，即进行 e-1 次 a 模 m 的乘法运算。这种方法虽然简单， 但是运算效率很低。 减少模指数运算中模乘法的次数是一种提高模指数运算速度的有效方法。 以下介绍两种常用的模指数运算算法， 这两种算法都是通过减少模乘法次数提高模指数运算的速度。 1. 二进制算法 设 e = (en-1 en-2 e0)2，且 en-1 0，是指数 e 的二进制表示。求 ae mod m 的二进制算法描述如下： (1) 置1neat，且 i n 2； (2) 置 t t t mod m； (3) 若 ei = 1，置 t t a mod m； (4) 置
3、 i i - 1；若 i 0 转到步骤(2)； (5) 输出t。 二进制算法的模乘法次数为101=inie，其中10=inie是指数e的二进制表示中 1 的个数。 2. M-ary 乘方算法 M-ary 算法是对二进制算法的推广，它将指数 e 用大于 2 的基表示，并在二进制步骤(3) 中用乘以 a 的幂的乘法代替乘以 a 的乘法。 设 e = (en-1 en-2 e0)M为指数 e 对某一确定的基 M的表示。求 ae mod m 的 M-ary 算法描述如下： (1) 计算并作为一张表格存储 a2 mod m，a3 mod m，aM-1 mod m； 2(2) 置1neat，且 i n 2
4、； (3) 置 t tM mod m； (4)若 ei 0，置 mod ?eitt am； (5) 置 i i - 1；若 i 0 转到步骤(3)； (6) 输出t。 显然，M-ary 乘方算法所需模乘法的次数依赖指数 e 的位数，也就依赖基 M 的选择。所以 M 的选择应该尽量满足以下两个条件。第一：使步骤(3)中的乘方最大可能地通过求平方计算；第二：使 a 的方幂的预计算中的乘法次数最少。 三、实验环境三、实验环境 操作系统：Windows 2000/XP/2003 或以上版本。应用软件：VC+ 6.0 或以上版本。 四、实验内容和任务四、实验内容和任务 本实验要求学生在掌握常用的模指数运
5、算算法的基础上， 运用高级程序设计语言编程实现模指数运算函数，并通过具体运算测试函数的功能。表 1-1 给出模指数运算函数的接口定义，作为编程实现的参考。 表 1- 1 模指数运算函数接口 函数 long modExpFun (long a, int e, long m) 功能 计算 ae mod m 的值 输入 a (底数)，e (指数)，m (模数) 输出 幂剩余； -1，表示输入参数不全为正整数； -2，表示输入模数为 0。 出错处理 输入参数 a，m 或 e 为负整数，r = -1 输入参数 m 为 0，r = -2 以二进制算法为例，模指数运算函数 modExpFun(a,e,m)的
6、程序流程图如图 1- 1 所示。 3图 1- 1 二进制算法流程图 模指数运算的界面实例如图 1- 2 所示。在空白框中输入模指数运算 ae mod m 的三个参数：底数a、指数e和模数m。点击“计算”按钮，执行模指数运算操作。点击“清空”按钮，清空所有参数的输入，以便重新输入参数值。 参数均有效参数有效性检查参数有特殊值特殊处理根据二进制算法 初始化r; tmpbase = r;k=将e的二进制表示中 除了最高位，其余各位 设置为0的数k=1k!=0r = (r * r) % m(e&k)!=0r = (r * tmpbase) % mk=1返回 rNYNYYYNN输入a, e, m 4图 1- 2 模指数运算实例 【举例 1】输入 a = 2, e = 1234, m = 789, 模指数运算结果为 r = 481，如图 1-3 所示。 图 1- 3 举例 1 的模指数运算结果 【举例 2】输入 a = 1234, e = 667, m = 18577, 模指数运算结果为 r = 4445，如图 1-4 所示。 5图 1- 4 举例 2 的模指数运算结果 五、实验报告要求五、实验报告要求 1. 写出模指数运算器的设计思路 2. 写出实现 modExpFun 函数的程序。 3. 写出自己的测试实例，验证模指数运算器的功能
