大数因式分解-邮件加密.doc

一、实验名称
大数的因式分解邮件加密
二、实验目的
熟悉使用maple数学工具，并练习使用maple数学工具进行数学运算如计算随即数产生rand、计算两个数的最大公约数gcd、计算因式分解ifactor、计算数n的欧拉函数值 phi（n）、比数n大的下一个素数 nextprime（n）、作图函数 implicitplot（方程表达式）：例如做椭圆曲线的图等，应用Maple验证RSA算法，学习实验资料中的另外密码学Maple实例如大数的因式分解。
三、实验内容与要求
大数的因式分解
邮件加密
1. 大数的因式分解
找到一個整數k，使得k可以被B以下的所有整數整除。
例如k可以為B!或是1,2,…,B的最小公倍數。
2. 找一個2到n-2之間的整數a。例如a可以為2或3或隨機選定的整數。
3. 使用重複平方法（repeat squaring method）計算ak mod n。
4. 使用輾轉相除法計算ak-1與n的最大公因數d。
如果d不是1或n，則分解成功，d將是n的一個因數；否則，選擇另一組k與a從步驟一開始再試一次。

邮件加密

设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则：
　　   C1 = P^e1 mod n
　　   C2 = P^e2 mod n
　　   密码分析者知道n、e1、e2、C1和C2，就能得到P。
　　   因为e1和e2互质，故用Euclidean算法能找到r和s，满足：
　　   r * e1 + s * e2 = 1
　　   假设r为负数，需再用Euclidean算法计算C1^(-1)，则
　　   ( C1^(-1) )^(-r) * C2^s = P mod n
    加密：将字符串AIIS转化成十进制，然后十六进制，在通过上述的RSA将十六进制加密。
    解密：将加密的十六进制解密，转化成十进制，再转化成字符。

五、思考与心得体会
初步了解了DES,RSA算法的应用，和大数分解的过程。进一步掌握了工具的使用。