公钥密码学实验报告：RSA与ElGamal加密算法解析

"实验05-RSA_ElGamal-2018级信安3-4班1" 实验报告中涉及了公钥密码学的重要算法，主要包括RSA和ElGamal密码系统，这些是现代加密技术的基础。RSA是一种非对称加密算法，它的安全性基于大整数因子分解的困难性。ElGamal则是一种基于离散对数问题的公钥密码体制。 1. RSA算法： - **选择素数**：RSA的核心是选取两个大素数p和q，这两个数必须保密，因为它们的乘积n=p*q构成了公共密钥的一部分。 - **计算欧拉函数**：φ(n) = (p-1)*(q-1)，这个值也必须保密，因为它与解密密钥d的计算有关。 - **选取公钥e**：e是一个介于1和φ(n)之间的数，且与φ(n)互质，通常选择一个较小的素数如65537以提高效率。 - **计算私钥d**：通过求解ed ≡ 1 mod φ(n)，得到d，d是私钥，与e互为模φ(n)的逆元。 - **加密和解密**：加密过程是C=M^e mod n，解密过程是M=C^d mod n。加密和解密使用不同的密钥，保证了安全性。 2. 求逆算法（扩展欧几里得算法）： - **扩展欧几里得算法**用于找到两个整数a和b的最大公约数，并同时计算出a和b的模逆元。在RSA中，这个算法用来求解d，使得ed ≡ 1 mod φ(n)。 - 实验中给出了算法的伪代码，通过迭代求解商q和余数r，最终得到a关于模p的逆S=a^-1 mod p。 3. ElGamal密码： - ElGamal加密过程涉及到选择一个随机数k，计算两个部分：C1=g^k mod p（公钥中的g是群生成元，p是素数），C2=M*a^k mod p，其中M是明文，C1和C2一起构成密文。 - 解密时，使用私钥x计算k^-1 mod p，然后解出M=(C2*C1^(-x)) mod p。 4. 实验要求： - 学习者需要掌握三种公钥密码体制的原理，包括RSA、ElGamal和椭圆曲线密码，理解其安全性和应用。 - 实现这些密码系统的具体方案，包括加解密过程。 - 理解公钥密码实现中的优化算法，以提高效率。 5. 实验环境： - 使用Windows操作系统，结合高级编程语言环境进行实验，这可能包括使用Python、Java等语言实现加密和解密算法。 通过这个实验，学生不仅能够理论学习公钥密码学的基本概念，还能通过实践加深理解，提升在实际环境中应用这些算法的能力。同时，实验也强调了密码安全性和算法优化的重要性，这对于信息安全专业人员来说至关重要。