背包公钥密码体制详解，4步搞懂陷门函数加密原理

网络信息安全第4章讲的是公钥密码体制, 然后4.1小节是关于公钥密码体制的概述, 这里标题写的是公钥密码体制概述, 接着又说一遍公钥密码的基本思想, 它的思想和单向陷门函数的思想是紧密相关的。构造公钥密码体制的一般原理, 大概是这样的。第一点是从一个困难问题P开始。

这个P问题是不可行的, 它是基于计算复杂性来定的, 而且最好是那种计算平均复杂度方面的问题。第二点是取出P里面的一个子问题P1。它应该是属于那种很容易就能被解决掉的情况, 通常情况下它的计算复杂度是多项式级别的时间, 而最理想的状态则是能够达到线性时间这样的程度。

接下来要做的事情, 是把P1这个具体问题给进行一种伪装, 让它在形式上变成P2这个问题, 从而使得外界在看待P2问题的时候, 会发现它看起来跟原来的那个P问题有着非常高的相似度, 就好像P问题具备的难度等级是一样的那样难解。

然后就要把P2问题给完全公开出来, 并且同时把这个已经被公开的P2问题当作是一个加密密钥所对应的加密函数来加以使用, 与此同时还需要对于如何才能够从P2这个地方成功恢复出关于P1问题的具体信息这样的一种操作流程或者关键资料进行严格的保密措施, 而在学术领域里面, 大家习惯将这种被严格保密的关键信息称谓为“陷门”这个词所表达的概念。

(5）让系统的合法用户可以靠着解决那个相对容易的一些问题P1来进行解密操作, 而其他的用户呢, 就非得去求解问题P2不可, 而且求解P2的这个步骤, 从表面上看, 似乎就是在解原本就很困难的那个P问题。

目前市面上已经出现的那些安全性能还比较不错的公钥密码体制, 主要就是基于一些很难解决的数学问题来建立的, 具体包括这几点: 第一点, 是基于数论里面涉及到的大整数分解的问题, 就像大家所知道的RSA算法就是这样；第二点, 是基于离散对数的这个问题, 比如说某些密钥交换的协议就用到了这个原理；第三点, 是基于在椭圆曲线上面开展的离散对数的问题, 典型的应用就是ECC椭圆曲线密码体制；第四点, 是基于线性编码里面的解码问题, 对应的一些密码体制也属于这一类；第五点, 则是基于自动机和语言理论相关的问题。

接着是关于公钥密码体制这方面的一个总体概述, 也就是4.1部分提到的公钥密码体制概述, 这里主要涉及到公钥这个方面的基本原理说明, 以及公钥体制（key）在Diff等语境下的相关内容。