建立一个公开密钥密码系统，有两个最基本的条件。第一，加密和解密变换必须是计算上容易的；第二，密码分析必须是计算上困难的。

Diffie和Hellman建立了陷门单向函数的概念，指出了解决这个问题的一种方法。陷门单向函数是一个函数族y=f（x，k），其中k是参数。对于每个k，f（x，k）和x一一对应。给定x和k，求f（x，k）是计算上容易的问题。反之，若给定y和k，求x是计算上困难的问题。所以y=f（x，k）是单向函数，即正方向容易计算反方向不容易计算的函数。此外，还存在一个“陷门信息”d（k）及函数g（y，k′），使得当y=f（x，k）时，x=g（y，d（k））；且给定y和k′时，求g（y，k′）是计算上容易的问题，即陷门信息d（k）使计算函数f（x，k）的逆变得“容易”起来。仅仅具备单向性的单向函数可以用来存储口令文件等，陷门单向函数则适合于建立公开密钥密码系统。

一个密码系统的保密性依赖于它所依赖的问题的计算复杂性，但是以计算上困难的问题为基础，却不一定得到一个保密性很强的密码系统。计算复杂性理论是公开密钥密码系统的基础，但是在公开密钥密码学中应用计算复杂性理论要十分当心，因为计算复杂性理论的分析与公开密钥密码学的要求不完全相同。

（1）计算复杂性理论通常分析问题的一个孤立的事例，但在密码分析时往往需要解决许多统计上相关的问题，例如，破译由同一个加密密钥生成的几段密文。(www.daowen.com)

（2）计算复杂性理论通常做的是最坏情形的度量，一个多项式时间内不可解的困难问题完全有可能对其中大多数事例是多项式时间可解的。然而，一个对大多数事例是信息容易破解的密码系统却是毫无用处的。

（3）计算复杂性理论对问题的难易分类时，通常只考虑是否存在确定的多项式时间算法。但是，一个可以通过某个概率多项式时间算法以很高的概率攻破的公开密钥密码系统，即使不存在确定的多项式时间算法去攻破它，也同样是没有用途的。

数字证书是由权威机构，又称证书授权（Certificate Authority，CA）中心发行的。证书一方面可以用来向系统中的其他实体证明自己的身份，另一方面由于每份证书都携带着证书持有者的公钥，所以证书也可以向接收者证实某人或某个机构对公开密钥的拥有，起着公钥分发的作用。在公开密钥密码系统中，每个用户都公开他的加密算法和加密密钥——公开密钥，把它们放在一个公开文件中，用户将相应的解密密钥保密。