实验二、RSA公开密钥密码系统实验.pdf

实验二RSA 公开密钥密码系统 1．实验目的 （1）熟悉可视化计算工具Raptor 。 （2 ）掌握Raptor 中的赋值、输入、输出、调用、循环等符号的使用。 （3 ）掌握构建RSA 公钥密码系统的简单程序的方法。 2．实验准备 （1）认真阅读“附录A ：Raptor 可视化程序设计概述”的内容。 （2 ）认真阅读本教材第2.3 节内容。 （3 ）了解初等数论中的“费马定理”、“欧拉定理”。 1）欧拉定理(Euler Theorem) 在数论中，欧拉定理（也称费马——欧拉定理）是一个关于同余性质的定理。欧拉定理 表明，若 、为正整数，且 、互质，则 ( ) ( ) = 1 其中，欧拉函数()表示不大于n 且与n 互质的正整数的个数。 − 1 , 为质数 ( ) = { ( ) ( ) ( ) ( ) = − 1 − 1 ， = 且 、均为质数 2）费马小定理(Fermat Theory) 若为质数，且、 的最大公约数(, ) = 1，则(−1) ( ) = 1。 即：若a 为整数，为质数，且、互质(即两者只有一个公约数1)，则(−1) 除以 的 余数恒等于1。 ( ) 证明这个定理非常简单，由于是质数，所以有 = − 1，代入欧拉定理即可证明。 3 ）举例 给出一个简单的例子帮助理解欧拉定理，令 = 3、 = 7，、互质。在比7 小的正整 数集合中与7 互质的数有1、2 、3、4、5、6，所以(7) = 6 。 计算() ( ) = 36 ( 7) = 729 7 = 1与定理结果相符。 3．热身实验 1）质数判定 给定判断输入的数值是否为质数的程序，如图2.1 所示。请回答以下问题： 图2.1 质数判定的程序示例 问题1：给定数值n=1，n=2，n>2，分别写出程序的运算过程。 问题2：思考程序跳出循环的必要条件。 2 ）输出给定区间内质数 给定一程序如下图2.2 所示，请回答以下问题： (a) main 函数 (b) Prime 子图 图2.2 输出给定区间质数的程序示例 问题：给定区间如[3,11]，模拟程序运行过程。 3 ）欧拉函数 给定欧拉函数求解程序如图2.3 所示，请回答以下问题： (a) main 函数 (b) AreRP 子图 图2.3 欧拉函数计算的程序示例 问题1：模拟程序运行，介绍该程序的功能。 问题2：模拟程序运行，介绍该程序子程序的功能。 问题3 ：在x 为质数，或者x = pq且p、q 均为质数的情况下，分别输入x 值，模拟程 序运行过程，验证欧拉函数。（例x = 11；x = 3 × 11） 4．进阶实验 1）RSA 公开密钥密码系统的构建 给定构建RSA 公开密钥密码系统的程序如图2.4 所示，模拟程序的运算过程，并了解程 序功能。 注：考虑到 Raptor 存在数据溢出的问题，这里假设输入的两个质数 p、q 的值都不大。 对于密码学中的大数运算问题，具体可参考国外著名密码学C 语言函数库——Miracl。 (a) main 函数