Mengzelev's Blog

问题求解学习笔记-密码算法

Word count: 644 / Reading time: 3 min
2019/04/13 Share

RSA公钥加密系统

每个参与者都有一把公钥($P$)和密钥($S$)

$\mathcal{D}$表示允许信息的集合,要求公钥与密钥指定一种从$\mathcal{D}$到自身的一一对应的函数。
Alice的公钥函数$P_A$和密钥函数$S_A$都是$\mathcal{D}$的排列

系统中任何参与者的公钥与密钥都是匹配对,指定函数互为反函数,对任何消息$M\in \mathcal{D}$,有
$$M=S_A(P_A(M))$$
$$M=P_A(S_A(M))$$

加密过程

  • Bob取得Alice的公钥$P_A$
  • Bob计算出相应与$M$的密文$C=P_A(M)$,并把$C$发送给Alice
  • 当Alice收到密文$C$后,运用自己的密钥$S_A$恢复原始信息$M$

数字签名

  • Alice运用密钥$S_A$和等式$\sigma=S_A)M’$计算出信息$M’$的数字签名$\sigma$
  • Alice把消息/签名对$(M’,\sigma)$发给Bob
  • Bob收到$(M’,\sigma)$时,通过验证等式$M’=P_A(\sigma)$来证实消息的确是来自Alice

任何人都可以把数字签名翻译出来,但只有密钥持有者可以生成数字签名

RSA加密系统

加密
$$P(M)=M^e\bmod n$$
解密
$$S(C)=C^d\bmod n$$

上述加密解密操作可以使用快速幂实现。

运行时间

假定:

  • 公钥$(e,n)$和密钥$(d,n)$满足$\lg~e=O(1), \lg~d\le\beta, \lg~n\le\beta$
  • 应用公钥需要执行$O(1)$次模乘法运算和$O(\beta^2)$次位操作
  • 应用密钥需要执行$O(\beta)$次模乘法运算和$O(\beta^2)$次位操作。

正确性证明

定理31.36(RSA的正确性):RSA加密和解密等式定义了满足再上面两个等式的$\mathbb{Z}_n$的逆变换

RSA加密系统的安全性主要来源于对大整数进行因子分解的困难性

效率提高

  • 无公钥加密系统
  • 抗冲突散列函数$h$
  • 证书

整数的因子分解

Pollard的rho启发式方法

  • 通过随机数寻找$n$的非平凡约数
  • 可能会出现”$\rho$”字型回路,在出现回路之前预计要执行的步数为$\Theta(\sqrt{n})$
  • 一种找出大整数的小素数因子的可供选择的办法

私钥密码学

仿射密码系统(affine cryptosystem):$f(p)=ap+b\bmod 26$, $f^{-1}(p)=a^{-1}p-a^{-1}b\bmod 26$

多字码密码系统(polyalphabetic cryptosystem): $f(\textbf{p})=A\textbf{p}+b$,其中$A$是矩阵,$b$是列向量,$f^{-1}(\textbf{p})=A^{-1}\textbf{p}-A^{-1}\textbf{p}$

公钥密码学

RSA加密系统(CLRS上已讲

CATALOG
  1. 1. RSA公钥加密系统
    1. 1.1. 加密过程
      1. 1.1.1. 数字签名
    2. 1.2. RSA加密系统
      1. 1.2.1. 运行时间
      2. 1.2.2. 正确性证明
      3. 1.2.3. 效率提高
  2. 2. 整数的因子分解
    1. 2.0.1. Pollard的rho启发式方法
  3. 2.1. 私钥密码学
  4. 2.2. 公钥密码学