常见公钥算法加解密公式

相关基础数学知识请看：
https://blog.csdn.net/weixin_43790779/article/details/105621372

RSA （大整数分解）

1. 密钥生成：
   • 大素数：p、q (至少为1024位 )；
   • $n=p×q ，φ(n)=(p-1)(q-1)$ ，其中 $φ(n)$ 是n的欧拉函数值；
   • 选择一整数e，满足1<e<φ(n)，且gcd(φ(n), e)=1；
   • 计算d，满足 d·e ≡1 mod φ(n)；
   • 公钥{e, n}，私钥{d, n}。
2. 加密：

   $$

   $$

   $$

   $$

3. 密钥生成：
   • p，一个较大的素数；
   • g，$Z^ * _ p $ 中的生成元；
   • $\alpha \in Z_{p-1} ,\beta=g^{\alpha} mod p$ ；
   • p,g,β为公钥；α为私钥；
4. 加密：
   随机生成一个秘密数k，$k\in Z_{p-1}$ 。

$E(x,k)=(r,s),其中 r=g^k mod p s=x\beta^k mod p$

3. 解密：

$D(r,s)=s(r^\alpha)^{-1} mod p=xg^{ak}g^{-ak}mod p=x$

椭圆曲线上ElGamal秘密（椭圆曲线，离散对数问题）

1. 密钥生成：
   在椭圆曲线$E_p(a,b)$ 上选取一个阶为n(n为一个大素数)的生成元P。随机选取整数x(1<x<n)，计算Q=xP。公钥为Q，私钥为x。
2. 加密：
   为了加密$P_m$，随机选取一个整数k，1<k<n，计算

$C_1=kP, C_2=P_m+kQ$

则密文$c=(C_1,C_2)$。

3. 解密：
   为了解密一个密文$c=(C_1,C_2)$，计算

$C_2-xC_1=P_m+kQ-xkP=P_m+kxP-xkP=P_m$

攻击者要想从$c=(C_1,C_2)$，计算出$P_m$，就必须知道k。而要从P和kP中计算出k将面临求解椭圆曲线上的离散对数问题。