使用openssl生成RSA密钥

openssl genrsa -aes256 -out rsakey.pem 4096

生成的rsakey.pem文件编码的是PEM（Privacy Enhanced Mail）格式的数据。文件的内容使用了ASN.1进行编码，它相当于python的pickle，是一个数据结构的二进制打包，-----BEGIN FOO-----和-----END FOO-----中的FOO是文件的主体，它可能是公钥，密钥或证书。文件的主体是一个DER格式的对象（Distinguished Encoding Rules），使用Base64编码。

使用如下代码读取PEM公钥文件内容：

from Crypto.PublicKey import RSA
with open("public.pem", "rb") as f:
    kobj = RSA.importKey(f.read())
    print(kobj.key.n,kobj.key.e)

使用以下命令来获得十六进制私钥内容：

openssl rsa -in rsakey.pem -noout -text

这些参数与RSA算法中 $p,q,N,e,d$ 的关系如下

N           -> modulus (1024 bit)
e           -> public exponent
d           -> private exponent
p           -> prime1
q           -> prime2
d(mod p-1)  -> exponent1
d(mod q-1)  -> exponent2
q^-1(mod p) -> coefficient

其中后3项是为了使用中国剩余定理来加速解密的

RSA

欧拉统计函数：若 $p,q$ 是素数， $n=pq$ ，则 $\varphi(n)=(p-1)(q-1)$ ， $\varphi(n)$ 也是 $\mathbb Z/n\mathbb Z$ 的所有单位元构成的乘法群的阶，即 $\varphi(n)=|\mathbb Z/n\mathbb Z^\times|$

RSA算法步骤：

  1. 密钥生成：随机生成大素数 $p,q$ ，计算$\varphi(n)=(p-1)(q-1)$，随机生成小整数 $e$ （一般固定为0x10001=65537），使用扩展欧几里得算法得到大整数 $d$ 满足 $ed=1 \mod \varphi( n)$
  2. 加密：给定明文 $m$ ，加密得到密文 $c=m^e\mod n$
  3. 解密：给定密文 $c$ ，解密得到明文 $m = c^d \mod n$

算法解密过程使用了费马-欧拉定理（ $a\bot n \Rightarrow a^{\varphi(n)}=1 \mod n$ ）：

$\begin{align*} c^d\mod n &=m^{ed}\mod n\\ & =m^{1+k\varphi(n)} \mod n\\ &=m \mod n \end{align*}$

RSA算法的使用过程：A使用RSA生成私钥 $d,p,q,\varphi(n)$ ，并把公钥e,n公开；B在获得A的公钥e,n后只能用它来加密，并且B使用A的公钥加密的所有密文只有A可以用自己的私钥解密，其他人包括B都无法解密。注意公钥只用于加密，私钥只用于解密

Cramer-Shoup

算法步骤：

  1. 密钥生成：已知一个素数阶的群， $|G|=n$ ，生成元为 $g_1,g_2$，随机生成私钥 $(x_1,x_2,y_1,y_2,z)$，计算公钥 $c=g_1^{x_1}g_2^{x_2},d=g_1^{y_1}g_2^{y_2},h=g_1^z$。
  2. 加密：给定明文 $m$ ，随机生成$k$，计算$u_1=g_1^k$，$u_2=g_2^k$，$e=h^km$，计算哈希$\alpha=H(u_1,u_2,e)$，$v=c^kd^{k\alpha}$，得到密文 $(u_1,u_2,e,v)$
  3. 解密：计算哈希$\alpha=H(u_1,u_2,e)$，验证$v=u_1^{x_1}u_2^{x_2}(u_1^{y_1}u_1^{y_1})^\alpha$，如果验证通过，则得到明文 $m=\frac{e}{u_1^z}$

计算图如下：
$$\overset{\underline{ \overset{\underline{ x_1 \ x_2 }}{\overset{\downarrow}{c}} } \overset{\underline{ y_1 \ y_2 }}{\overset{\downarrow}{d}} \overset{\underline{ \overset{\underline{ \overset{\underline{ z }}{\overset{\downarrow}{h}} \ m }}{\overset{\downarrow}{e}} \ u_1 \ u_2 }}{\overset{\downarrow}{\alpha}} }{\overset{\downarrow}{v}}$$

Schnorr签名

算法步骤：

  1. 密钥生成：已知一个素数阶的群， $|G|=n$ ，生成元为 $g$ ，随机生成签名私钥 $x$ ，生成签名公钥 $y=g^x\mod n$ ，并公开公钥y, g, n
  2. 签名生成：已知需要添加签名的明文m，随机生成 $k$ ，得到 $r=g^k \mod n$ ，使用hash函数得到 $e=H(r||m)$ （||表示拼接），使用私钥得到 $s=k-xe$ ，则 $(s,e)$ 就是一个签名
  3. 验证签名：已知明文m，签名公钥y, g, n，签名(s,e)，得到 $g^sy^e=r^\prime$ ，计算 $e^\prime=H(r^\prime||m)$ ，若 $e=e^\prime$ 则校验成功，否则失败。

签名的使用过程：网站使用密钥为消息颁发证书并公开公钥，只有网站颁发的证书能通过验证并保证没有被篡改。注意公钥只用于验证签名，私钥只用于生成签名

证书

证书由一个机构的签名公钥，签名算法，本机构信息，颁发证书的父机构信息，过期时间及其他信息构成。不同机构之间互相颁发证书，直至根机构（root CA），构成一个信任链

标签: none

评论已关闭