《应用密码学》——第四章 公钥密码体制

笔记 评论

概述

对称密码体制的缺点：

  1. 密钥管理的困难：n个用户彼此间进行保密通信就需要n(n-1)/2个密钥；当用户数量增加时，密钥的数量急剧增大，密钥管理量大。密钥的产生、分发、保存、撤销、更新等安全性问题解决困难复杂代价高。
  2. 系统的可拓展性和开放性差：每进来一个新用户都需要对已有的n个老用户进行通知，并添加一个新密钥。不能解决陌生人间的密钥传递问题，也就不能支持陌生人间的保密通信。
  3. 不能数字签名，抗抵赖性差：一旦发送方的消息产生更改，不能确认是否是发送方的行为。

对称密码体制的优点：

​ 加解密处理速度快、效率高；算法安全性高

==》公钥密码体制弥补了对称密钥密码体制的缺点

image-20220419171918297

Alice使用自己的私钥对信息m进行加密发送出去，收者Bob使用Alice的公钥进行解密。若m’和m一致则确定是Alice发送的，不一致则不是Alice发送的。(鉴别) -> 抗抵赖性

因为人手一份公钥和私钥。公钥公开给发送方加密信息，私钥保存主人解密收到信息，机密性高，只有n的密钥管理，也可以用来公开信道上密钥的分发和协商。

当前状况：

image-20220419173702953

公钥密码的基本思想

img

\begin{aligned} 公&钥密码的加密变换E_{KU_B}(m)与解密变换D_{KR_B}(c)应满足下列要求：\\ &(1)D_{KR_B}(c)是E_{KU_B}(m)的逆变换，即对任意的明文M，均有：D_{KR_B}(c)=D_{KR_B}(E_{KU_B}(m))=m\\ &(2)已知加密和解密秘钥时，加解密是容易的\\ &(3)如果不知道私钥{KR}_B，那么即使知道公钥{KU}_B、具体加解密算法以及密文，确定明文计算上都是不可行的 \end{aligned}

像这种不知道解密密钥，对密文进行逆变换得到正确明文在计算上是不可行。具有这种性质的函数称为单向陷门函数

目前人们主要基于如下数学上的困难问题来设计单向陷门函数和公钥密码体制：

  • 大整数分解问题(RSA)

    • 大素数 n=p·q
    • p,q求n简单，但n求p,q难 (概率算法)

  • 有限域上离散对数问题(EIGamal)

    • y=gxmodpy=g^x\;\; mod\;p

    • 通过x求y容易，但通过y求x不容易(与y对应的x太多，不知道是哪一个)

  • 椭圆曲线上的离散对数问题(ECC)

    • <F , + , * > 域

    • 椭圆曲线上的点<x , y>构成的域<F , +> -> 乘相当于x个相加

      \begin{aligned} P &= xG\;\; (mod\;p)\\ 公钥 &=密钥*公共信息\;\;(取模) \end{aligned}

单向陷门函数也存在天敌：量子计算机(速度极快)，如果量子计算机一旦问世并推广，信息加密的安全性问题面临大危机 --> 应对：格Grid函数(量子计算机尚未由应对算法，线性代数离散向量空间：由n维组成的在横纵交线上的点)

RSA公钥密码体制

古典密码技术 -> 近代密码 ：1949年，香农奠基性论文《保密系统的通信理论》发表

近代密码 -> 现代密码 ：1976年，迪菲和赫尔曼发表了《密码学新方向》，首次提出了公钥密码体制的概念和设计思想；1978年，美国的里维斯特R、沙米尔S、阿德勒曼A提出了一个较完整地公钥密码体制——RSA体制，是密码学史上地里程碑

RSA公钥密码体制的安全性建立在大整数因子分解的困难性之上，算法的数学基础是初等数论中的欧拉定理

  1. 密钥生成

    （1）选择两个随机的大素数 p 和 q ，并计算

    n=pq\quad 和\quad \phi(n)=(p-1)(q-1)\\ 其中,\phi(n)欧拉公式: 比n小的数中和n互素的数字个数;p,q为互异的素数(计算完就销毁)

    • ϕ(n)=(n−1)−(q−1)−(p−1)=pq−q−p−1=(p−1)(q−1)\begin{aligned} \phi(n)&=(n-1)-(q-1)-(p-1)\\ &=pq-q-p-1\\ &=(p-1)(q-1) \end{aligned}

    （2）选择一个随机数e，1<e<\phi(n) 满足gcd(e,\phi(n))=1，并计算

    d=e^{-1}\;\;mod\;(\phi(n))\\ 其中，d,e为互素的乘法逆元。ed\equiv1\;mod\;\phi(n)，即ed=k\phi(n)+1

    （3）公钥为（e, n），私钥为 d

  2. 加密

    对明文m<n，其对应的密文为

    c=memodnc = m^e\;\;mod\;n

    • 快速计算a^m mod n

      \begin{aligned} a^{10} \;幂换成二进&制\;a^{1010}\\ &=a^{b_32^3+b_22^2+b_12^1+b_02^0}\\ &=(((1\times a^{b_3})^2 \times a^{b_2})^2 \times a^{b_1})^2 \times a^{b_0}\\ 2^{100}\;mod\;n&=(2^{20}\;mod\;n)^5 \end{aligned} 
      1

  3. 解密

疑问：公私密钥该有谁生成？

  • 由他人(可信度高，KGC)生成所有人的公私密钥

    -> 成为黑客的攻击目标；信息越多，自身价值越大（忧）

  • 由自己生成自己的公私密钥

    -> 由于密钥生成都用到\phi(n)，会导致知道公钥即可推出私钥，而可以伪造任何人的签名（不可取，忧忧忧）

所以RSA的一个缺陷就是由谁生成密钥都不安全

EurekaStudy Notes & Supplement

Strong is beautiful!