1.公钥密码体制

公钥密码体制为密码学的发展提供了新的理论和技术基础,它的出现是迄今为止整个密码学发展史上最伟大的一次革命,甚至可以说没有公钥密码体制,就没有现代密码学。

2.公钥密码体制的提出

对称密码体制,即解密密钥与加密密钥相同或解密密钥可由加密密钥推算出来,可以在定程度上解决保密通信的问题。但随着计算机和网络的飞速发展，保密通信的需求越来越泛.对称密码体制的局限性就逐渐显现出来，主要表现在:

  1. 密钥分发问题
    使用对称密码体制进行保密通信时,通信双方要事先通过安全的信道传递密钥，而安全信道是不易实现的。所以发送方如何安全、高效地发送密钥到接收方(通常称为初始密钥分发)是对称密码体制难以解决的问题。
  2. 密钥管理问题
    在n个用户的通信网络中,使用对称密码体制实现两两保密通信,则每个用户需要和其他n-1个用户分别共享一个钥,而系统中的总密钥量将达到 n(n-1)/2。当n较大时，这样大的密钥量,使得密钥产生、保存、传递、使用和销毁等各个管理环节都会变得很复杂,存在全隐患。
  3. 数字签名问题
    对称密码体制中通信双方拥有同样的密钥,所以任何一方都可以生成消息的认证标签，发送方可以否认发送过某消息,即无法实现信息安全的不可否认性目标，或者说不能实现数签名功能。

正是对称密码体制存在的这些局限性以及实际应用需求促使一种新的密码体制被提出。1976 年,Whitefield Diffie 和 Martin Hellman 在论文《密码学的新方向》(New DirectionsiCryptography)中提出一个设想:

用户A有一对密:加密密钥 $P_k$和解密密钥$S_k$公开$P_k$，保密$S_k$。若B要给A发送加密信息,他需要在公开的目录中查出A的公开(加密)密钥$ P_k$，用它用加密消息;A 收到密文后,用自己秘密保存的解密密钥 $S_k$解密密文,由于别人不知道 $S_k$即截获了密文,也无法恢复明文。在这种思想中,加密密钥和解密密钥是不同的，加密密钥是公开的且从加密密钥推出解密密钥是不可行的。基于这种思想建立的密码体制，被称为公钥密码体制,也叫非对称密码体制。这个设想提出之后,立刻引起密码学家的高度重视和浓厚兴趣,多种公钥密码算法相继被提出,可惜许多是不安全的,而那些被视为安全的算法又有许多不实用。直到 1978 年,美国麻省理工学院的 Rivest、Shamir 和 Adleman 3 位密码学家提出了RSA 公钥密码体制，很好地解决了对称密码体制所面临的问题。

3.公钥加密体制的思想

公钥密码体制，通常要使用一些计算上困难的问题。更重要的是,与只使用单一密钥的传统加密技术不同,它在加密/解密时,分别使用了两个不同的密钥:一个可对外界公开,称为公钥或公开密钥,用于加密消息;另一个只有所有者知道,称为私钥或私有密钥,用于解密消息。公钥和私钥之间具有紧密关系，但由公开密钥推导私有密钥,在计算上是不可行的。

通常情况下,公钥加密体制满足以下要求。

  1. 接收方 A容易产生一对密钥(公钥 $P_k$和私钥$ S_k$)。
  2. 发送方 B在知道接收方 A公钥 $P_k$和待加密消息M 的情况下很容易通过加密函数计算产生对应的密文 C;同理,接收方收到密文 C后,容易用私钥和解密函数解出明文。
  3. 敌对方T即使知道公钥 $P_k$,要确定私钥 $ S_k$在计算上是不可行的。
  4. 敌对方T即使知道公钥 $P_k$和密文 C,要想恢复原来的消息 M 在计算上也是不可行的。
  5. 加密、解密次序可交换,即 $E_{P_k}[D_{S_k}(M)]=D_{S_k}[E_{P_k}(M)]$。（E=解密，D=加密）

最后一条不是对所有的算法都作这个要求,但非常有用。
公钥加密体制与陷门单向函数有关,要满足上述对公钥加密体制的要求,最终可归结为设计一个陷门单向函数。

陷门单向函数是满足下列条件的函数 f:

  1. 正向计算容易，即如果知道密钥 P和消息M,容易计算$C=f_{P_k}(M)$;
  2. 在不知道密钥$S_k$的情况下,反向计算不可行,即如果只知道加密后的消息 C而不知道密钥$S_k$,则计算 $M=f^{-1}©$不可行;
  3. 在知道密钥 $S_k$的情况下,反向计算容易,即如果同时知道加密消息 C和密钥$S_k$,则计算 $M=f^{-1}_{S_k}©$是容易的,这里的密钥 $S_k$相当于陷门,它和 $P_k$配对使用。

对于以上的条件,若仅满足(1)、(2)的函数称为单向函数。

在现实世界中,这样的例子很普遍,如将挤出的牙膏弄回管子里要比把牙膏挤出来困难得多;把盘子打碎成数片碎片很容易，但要把所有这些碎片再拼成为一个完整的盘子则很难。数学上有很多函数感觉像单向函数,能够有效地计算它们,但至今未找到有效的求逆算法。如将许多大素数相乘要比将其乘积因式分解容易得多。

第(3)条称为陷门性,其中的密钥 $S_k$:称为陷门信息。也就是说,对于陷门单向函数而言，若不知道某种附加的信息，它是一个单向函数,有了附加信息,函数的反向就容易计算出来。在现实生活中,这样的例子也不少,比如将一个手表拆分为数百个细小的零件很简单,但是若要想将这些零件重新组合起来成为一个可工作的手表却很难,这就需要知道陷门(手表的结构图及装配指令)才能完成重新组合。

公钥加密体制中的公钥用于陷门单向函数的正向(加密)计算,私钥用于反向(解密)计算。

4.公钥密码体制的分类

自 1976 年公钥密码体制的思想提出以来,国际上已经出现了许多种公钥加密体制,例如基于大整数因子分解问题的公钥加密、基于有限域乘法群上的离散对数问题的公钥加密、基于椭圆曲线上的离散对数问题的公钥加密、基于背包问题的公钥加密、基于格的短向量问题的公钥加密、基于代数编码中的线性解码问题的公钥加密等。目前应用最广的公钥加密体制主要有 3 个;RSA公钥加密体制,EIGamal公钥加密体和椭圆曲线公钥加密体制。

应老师实验要求，本博客还有介绍RSA 公钥加密体制和MH 背包公钥加密体制,如需查看，点击直达 🤗