密码学基础课程设计指导书.doc

《现代密码学基础》 课程设计指导书 杨柳 编 湖南科技大学计算机科学与工程学院 2014年12月 一、概述 本课程在简要复习数学基础知识之后，探讨了密码学研究的基本问题：通过不安全的通信媒介如何进行安全通信。也可以理解为关心任何希望限制不诚实者达到目的的问题，把度量和评价一个密码体制（协议）的安全性作为一个重点。就目前来说，密码学的研究领域已从消息加密扩大到了数字签名、消息认证、身份识别、抗欺骗协议等。无疑，在整个教学过程中非常重视密码学的基础，当然包括数学基础。并针对实际的密码体制（协议）强调设计与分析（攻击），对现代密码学的主要研究问题都进行了介绍。 对于密码学这样的课程，同学们一定要从理论、技术、应用三个方面进行学习与思考。密码体制（协议）无疑是我们的学习重点，密码体制（协议）也可以单纯地理解为计算机算法，从而有设计、分析、证明、实现的问题。实现密码体制（协议）就是我们经常讲的八个字：模型、算法、程序、测试。 二、课程设计步骤 课程设计步骤要求如下： 1. 模型 从数学的角度看，解决任何问题都要建立一个数学模型，对于密码学来说更是如此。我们还可以认为，数据结构中的存储结构也是模型。于是这一部分的任务就是建立起问题的逻辑结构和存储结构，为算法设计和编码实现打下基础。 2. 算法 这一部分对同学们的要求是能看懂书上的常用算法，并对其中的参数可以进行调整和设置，能实现和应用它们。 3. 程序 编码实现得到程序。 4. 测试 5. 提交课程设计报告 三、课程设计报告编写要求 课程设计报告开头标明课程设计题目、设计者的班级、姓名、学号和完成日期，内容包括：模型、算法、程序、测试四个部分。 四、设计要求 可以只做第7题，不做第7题的要做第1题-第6题。 五、课程设计题目 题目1 大整数运算包的设计与实现 1．问题描述 大整数运算是现代密码学算法实现的基础，重要性不言而喻。大整数我们指的是二进制位512、1024和2048的数，一般的语言不支持。 2．基本要求 以类库头文件的形式实现。 3．实现提示 在选择了大整数的存储结构之后，主要实现以下运算： ① 模加； ② 模减； ③ 模乘； ④ 模整除； ⑤ 模取余。这五种运算模拟手算实现。 ⑥ 幂模：利用“平方-乘法”算法实现。 ⑦ GCD：利用欧几里得算法实现。 ⑧ 乘法逆: 利用扩展的欧几里得算法实现。 ⑨ 素数判定与生成：概率性素数产生方法产生的数仅仅是伪素数，其缺点在于，尽管其产生合数的可能性很小，但是这种可能性仍然存在:其优点是产生的伪素数没有规律性，而且产生的速度也比较快。此类方法是生成大素数的主要方法，其中较著名的算法有:Miller Rabin算法、Solovay-Strassen算法等。本文讨论Miller Rabin算法。 Miller Rabin素性测试法是在实际中应用非常广的一种素性测试方案，可以用来判定某随机数是否为素数。其定义如下: 设n2是一个奇数，设n-1=2sm，其中s是非负整数，m0是奇数，设0bn，如果 bm≡－1(mod n)， 或者存在一个r,0≤rs，使得 b 2^r m≡－1(modn) 则称n通过以b为基的Miller-Rabin测试。 可以利用Miller-Rabin素性测试算法来随机生成大素数，随即生成一个奇数n2，随即均匀的选取序列b1,b2...,bk∈{1,2,...,n-1}，对n进行k次Miller-Rabin素性测试，如果每次输出都为“n可能是素数”，则n是合数的概率小于 1/4k当k足够大时，1/4k是一个十分小的数。 同学们在具体实现时，为了提高速度最好以空间换时间，在主程序运行前先构造一个大素数表。 题目2 MD5的实现 1．问题描述 MD5以512比特一块的方式处理输入的消息文本，每个块又划分为十六个32比特的子块。算法的输出由四个32比特的块组成，将它们级联成一个128比特的Hash值。 ①首先填充消息使填充后的长度恰好为一个比512的倍数小64的数。填充方法是附一个“1”在消息后面，再补多个“0”。然后，在其后附上64比特的消息长度（填充前）的二进制表示。算法中使用了四个32比特的变量A、B、C、D，先把这四个变量初始化为： AB=89ABCDEF，C=FEDCBA98，D称它们为链接变量。 ① 接着进行算法的主循环，循环的次数是消息中512比特的块的数目。 将上面四个变量复制到另外的变量中：A到AA，B到BB，C到CC，D到DD。 主循环有四轮， 每一轮由16次操作组成。F、G、H、I函数，FF、GG、HH、II四种操作详见教材各密码学参考书。所有这些步骤进行完之后，将A、B、C、D分别加上AA、BB、CC、DD，然后用下一块数据