RSA非对称加密算法
1. 创建资源
开始实验之前，您需要先创建实验相关资源。
在实验室页面，单击创建资源。
（可选）在实验室页面左侧导航栏中，单击云产品资源列表，可查看本次实验资源相关信息（例如IP地址、子用户信息等）。
说明：资源创建过程需要3～5分钟（视资源不同开通时间有所差异，ACK等资源开通时间较长）。完成实验资源的创建后，您可以在云产品资源列表查看已创建的资源信息，例如：子用户名称、子用户密码、AK ID、AK Secret、资源中的项目名称等。
实验环境一旦开始创建则进入计时阶段，建议学员先基本了解实验具体的步骤、目的，真正开始做实验时再进行创建。
资源创建成功，可在左侧的资源卡片中查看相关资源信息以及RAM子账号信息
2. 实验原理
实验原理
非对称密钥加密也称为公开密钥加密，或者叫做公钥加密算法。使用公开密钥密码的每一个用户都分别拥有两个密钥:加密密钥和解密密钥，它们两者并不相同，并且由加密密钥得到解密密钥在计算机上是不可行的。每一个用户的加密密钥都是公开的。因此，加密密钥也称为公开密钥(公钥)。所有用户的公开密钥都将记录在作用类似于电话号码薄的密钥本上，而它可以被所有用户访问，这样每一个用户都可以得到其他所有用户的公开密钥。同时，每一个用户的解密密钥将由用户保存并严格保密。因此，解密密钥也称为私有密钥(私钥)。
非对称密码算法解决了对称密码体制中密钥管理的难题，并提供了对信息发送人的身份进行验证的手段，是现代密码学最重要的发明。公钥加密算法一般是将对密钥的求解转化为对数学上的困难问题的求解，例如RSA 算法的安全性是建立在 “大数分解和素性检测”这个数论难题的基础上。
RSA加密算法于1977 年由美国麻省理工学院的Ronal Rivest，Adi Shamir和Len Adleman三位年轻教授提出，并以三人的姓氏Rivest，Shamir和dleman命名为RSA算法。这三位科学家荣获2002年度图灵奖，以表彰他们在算法方面的突出贡献。该算法利用了数论领域的一个事实，那就是虽然把两个大质数相乘生成一个合数是件十分容易的事情，但要把一个合数分解为两个质数的乘积却十分困难。合数分解问题目前仍然是数学领域尚未解决的一大难题，至今没有任何高效的分解方法。它无须收发双方同时参与加密过程，既可以用于保密也可以用于签名，因而非常适合于电子邮件系统的加密，互联网和信用卡安全系统。
RSA参数生成
生成两个大素数𝑝和𝑞
𝑛 = 𝑝𝑞, 且 𝜙(𝑛) = (𝑝−1)(𝑞−1)
选择一个随机数 𝑒 (1<𝑒<𝜙(𝑛))，使得 𝑔𝑐𝑑(𝑒,𝜙(𝑛)) = 1
𝑑𝑒 ≡ 1 𝑚𝑜𝑑 𝜙(𝑛)
公钥 𝑃𝐾 = {𝑒, 𝑛}，私钥 𝑆𝐾 = {𝑑, 𝑛}
RSA加密解密过程
加密：对于明文分组𝑀，密文分组C：
解密：对于密文分组𝐶，明文分组M：
(注意:明文M的二进制值必须比 𝑛 小)
3. 实验内容
实验内容
编写代码实现RSA加密解密程序。每个同学选取自己学号的后五位(或一个相近的素数)作为𝑒，然后随机选取满足条件的𝑝、𝑞和𝑑，要求𝑝和𝑞的二进制长度不小于128bit
以一段自选的明文作为输入，每个英文字母对应一个数字，规则如下：每个字母或数字与一个两位的十进制数字对应，(如：数字为00-09，𝑎=10，𝐴=36)，明文的一个分组块由4个十进制数字组成，即两个字母。去掉空格和其他标点符号。
分别用公钥加密私钥解密和私钥加密公钥解密。
将𝑝, 𝑞, 𝑛, 𝑒, 𝑑, 𝜙(𝑛)的值以及两种不同方式加密后的密文、解密后的明文输出到文件或屏幕。
独立完成实验报告(包含实验思路，实验结果截图等)，提供源代码，不得抄袭。可以使用开源运算库(例如:GMP)，推荐用Python。
# -*- coding: utf-8 -*- # Created by Zheng Yuntao import sys def is_prime(n, k=128): """ Test if a number is prime Args: n -- int -- the number to test k -- int -- the number of tests to do return True if n is prime """ # Test if n is not even. # But care, 2 is prime ! # WRITE YOUR CODE HERE! def generate_prime_candidate(length): """ Generate an odd integer randomly Args: length -- int -- the length of the number to generate, in bits return a integer """ # WRITE YOUR CODE HERE! def generate_prime_number(length): """ Generate a prime Args: length -- int -- length of the prime to generate, in length bits return a prime """ # keep generating while the primality test fail # WRITE YOUR CODE HERE! class RSA(object): def __init__(self, e): # decide the parameter e by your student ID self.e = e def _egcd(self, a, b): """ extended gcd """ # WRITE YOUR CODE HERE! def _modinv(self, a, m): ''' calulcate solution of a*x mod m = 1 http://stackoverflow.com/a/9758173 ''' # WRITE YOUR CODE HERE! def generate_key(self): ''' randomly generate the public and private key the class doesn't store the keys ''' # WRITE YOUR CODE HERE! def encrypt(self, key, plain_text): ''' using the key (public/private) to encrypt the plain text ''' # WRITE YOUR CODE HERE! def decrypt(self, key, cipher_text): ''' using the key (public/private) to decrypt the cipher text ''' # WRITE YOUR CODE HERE! if __name__ == '__main__': num_e="your student ID" rsa = RSA(num_e) ''' call generate key and encrypt/decrypt the plaintext ''' # WRITE YOUR CODE HERE!
实验链接：https://developer.aliyun.com/adc/scenario/be4a144866a943edbf01a5cb8edb00d3
