公钥体制的基本原理是单向陷门函数。

要求

公钥密钥对参数生成需满足的要求：

• 公开密钥(public-key), 可以被任何人知道, 用于加密或验证签名；
• 私钥(private-key), 只能被消息的接收者或签名者知道,用于解密或签名；
• 由私钥及公开参数容易计算出公开密钥；
• 由公钥及公开参数推导私钥是困难的；

公钥密码体制的要求：

• 产生一对密钥在计算上是可行的；
• 已知公钥和明文，产生密文是容易的；
• 接收方利用私钥来解密密文在计算上是可行的；
• 对于攻击者，利用公钥来推断私钥在计算上是不可行的；
• 已知公钥和密文，在不知道私钥的情况下，恢复明文在计算上是不可行的。

RSA

密钥生成

1. 选一对不相等且足够大的质数$p,q$
2. 计算$n=p\times q$
3. 计算$n$的欧拉函数\varphi (n)=(p-1)\times(q-1)$
4. 选一个与$\varphi (n)$互质的整数$e$，$1<e<\varphi(n)$且$gcd(\varphi(n),e)=1$
5. 计算$e$在模$\varphi (n)$逆元$d$，$d\times e \equiv 1 \mod\varphi(n)$
6. 以$\{e,n\}$为公开钥（𝑃𝐾）,$\{d,n\}$为秘密钥（𝑆𝐾）

例：$29\times d \mod 264 = 1$，求$d$：
用辗转相除法可以转换为下列式子：
（1）$29 \times d - 264 \times k = 1$
（2）$29 \times d - 3 \times k = 1$
（3）$2 \times d - 3 \times k = 1$
（4）$2 \times d - 1 \times k = 1$
此时$k$的系数以及化为$1$;
令$d=1$，带入（4）式中，得$k=1$；
令$k=1$，带入（3）式中，得$d=2$；
令$d=2$，带入（2）式中，得$k=19$；
令$k=19$，带入（1）式中，得$d=173$；
解得：$d=173$

加密

加密时首先将明文比特串分组，使得每个分组对应的十进制数小于$n$，即分组长度小于$\log_2n$。然后对每个明文分组$m$，作加密运算：
$$C \equiv m^e \mod n$$

解密

对密文分组的解密运算为：
$$M \equiv c^d \mod n$$

ElGamal

密钥生成

1. 对于Bob,首先要随机选择一个大素数$p$，且要求$p-1$有大素数因子。再选择一个模$p$的本原元$g$。将$p$和$g$公开。
   我们为了方便计算取$p = 37$,则$37$的一个本原元$g = 2$.
2. 随机选择一个整数$x$作为密钥，$2\le x \leq p-2$。
   我们选择$x = 5$,
3. 计算$y\equiv g^x\pmod p$
   $\beta=2^5\pmod {37} = 32$

以$(y,g,p)$作为公开密钥，$x$作为秘密密钥。

K是否需要保密？K能否重复使用？

需要，$K$泄露，则由$y$和$C_2$可以解出$M$
攻击者若已知$k$，可以计算$y^k$,然后用$C_2/y^k$就得到明文；
若是$k$重复使用，则$C_2/C_2’=M/M’$,知道其中的一个明文，另一个可求。

加密

假设Alice 想发送消息 $M = 29$
1. 首先选取随机数$k$ , $0 \le k \le p-1$
假设$k = 7$，计算密文对$C = \{C1, C2\}$
则：$C_1 = g^k \mod p = 2^7 \mod 37 = 17$
$C_2 = M \times y^k \mod p = 29\times 32^7 \mod 37 = 33$
2. 将密文$C = \{17,33\}$发送给Bob

解密

Bob收到密文$C = \{17,33\}$后恢复明文如下：
$M = C_2 (C_1^x) ^{-1} \mod p$
$= 33 \times(17^5) ^{-1} \mod 37$
$= 33\times 2 \mod 37$
$= 29$

EDCH体制

假定椭圆曲线𝐸定义在$Z_q$域（$q$为素数）上。设$P$为$E$上的一个点。A和B分别选$a$和$b$予以保密，但将$aP, bP\in E$公开。A、B间通信用的密钥为$abP$，这是第三者无法得知的。
两用户A和B之间的密钥交换如下进行：
1. A选一小于$n$的整数$n_A$，作为秘密钥，并由$P_A=n_AG$产生$E_p(a,b)$上的一点作为公开钥。
2. B类似地选取自己的秘密钥$n_B$和公开钥$P_B$。
3. A、B分别由$K=n_AP_B$和$K=n_BP_A$产生出双方共享的秘密钥。
这是因为$K=n_AP_B=N_A(n_BG)=n_B(n_AG)=n_BP_A$。
攻击者若想获取$K$，则必须由$P_A$和$G$求出$n_A$，或由$P_B$和$G$求出$n_B$，即需要求椭圆曲线上的离散对数，因此是不可行的。

例$p=211$，$E_p(0,-4)$，即椭圆曲线为$y^2\equiv x^3-4$，$G=(2,2)$是$E_{211}(0,-4)$的阶为$241$的一个生成元，即$241G=O$。
A的秘密钥取为$n_A=121$，公开钥为$P_A=121(2,2)=(115,48)$。
B的秘密钥取为$n_B=203$，公开钥为$P_B=203(2,2)=(130,203)$。
由此得到的共享密钥为$121(130,203)=203(115,48)=(161,169)$，即共享密钥是一对数。