下载掌阅APP，畅读海量书库
立即打开
引用百度百科里对密码学的定义：密码学是研究编制密码和破译密码的技术科学。定义里提到的编制密码和破译密码，可以被看成制定一套信息转换的规则，通过这套规则可以将人们想要保护的信息转换为加密的信息，只有获得授权的人才可以获知信息的内容。随着计算机科学的蓬勃发展和计算机时代的到来，密码学也发展到了新的阶段。当一个算力远超人类的机器出现之后，密码学研究的理论基础、工具和手段都有了全新的变化。
现代密码学的发展经历了几个重要的阶段。1949年，香农发表了论文 Communication Theory of Secrecy Systems （《保密系统的通信理论》 ［3］ ），为密码学奠定了理论基础。1976年，Diffie和Hellman发表了论文 New Directions in Cryptography ［4］ ，开创性地提出了基于公钥密码的密码设计思想。至此，公钥密码体制诞生了。此后，学界提出了许多种公钥密码体制，1977年由Rivest、Shamir和Adleman首先提出第一个实用的公钥密码体制，即著名的RSA，1985年由Tather ElGamal（塔希尔·盖莫尔）提出ElGamal 密码体制及基于椭圆曲线的ElGamal密码体制等。这些密码体制都得到了广泛的应用，并且为我们提供了各种各样的安全服务。
密码学的研究内容主要包括密码编码学和密码分析学两个领域。
密码编码学主要研究与密码的编码和译码相关的协议及算法。这些协议和算法可以被理解为一套规则和机制，通过它们能够实现信息的保护和隐藏。这里提到的密码编码，就是我们常说的加密；密码译码，就是我们常说的解密。加密和解密过程中的一个重要参数，被称为密钥。密码编码学的研究主要是为了实现两类安全目标：信息保密和身份认证。信息保密指的是保证我们想要保护的信息只能由掌握密钥的人正确读取和理解，身份认证指的是能够保证和鉴别信息传递双方身份的真实性。
密码分析学研究密码机制的分析和破译方法，主要包括穷举攻击、统计分析攻击和数学分析攻击等内容。穷举攻击指的是通过遍历所有可能的密钥进行破解的方法；统计分析攻击指的是通过分析明文和密文的统计规律来进行破译的方法；数学分析攻击指的是针对加密算法的数学基础（各种数学困难问题），通过数学求解的方法来破译密码的一种方法。针对每一种攻击，均会产生相应的抵御攻击的方法。
可以说，密码编码学和密码分析学相互之间是典型的矛与盾的关系，既相互对立，又相互依存；而恰恰是这种对立统一的关系，在相互不断的攻防过程中，推动了密码学的发展。
密码系统可以被抽象描述为五元组〈 M， C，K，Enc，Dec〉，主要包含以下几个要素。
· 明文：未经加密的信息，一般用 m 表示。 M =｛ m ｝表示所有明文组成的明文空间。
· 密文：加密后的信息，一般用 c 表示。 C =｛ c ｝表示所有密文组成的密文空间。
· 密钥：明文与密文转换过程中的重要参数，一般用 k 表示。 K =｛ k ｝表示密钥空间。
· 加密转换：将明文转换为密文的算法、函数、协议或者映射，一般用Enc表示。加密转换以明文和密钥作为输入，输出为加密后的密文，可以表示为Enc（ k ， m ）= c 。
· 解密转换：将密文转换为明文的算法、函数、协议或者映射，一般用Dec表示。解密转换以密文和密钥作为输入，输出为解密后的明文，可以表示为Dec（ k，c ）= m 。
此外，在进行密码学理论算法讨论的时候，会涉及很多“ a 传输消息给 b ”之类的描述。由于密码学中的算法理论往往比较复杂，因此为了便于描述和理解，我们习惯上会引入人物角色进行替代，其中最广泛应用的就是密码学讨论中著名的“人物”：爱丽丝（Alice）和鲍伯（Bob）。在密码学语境下，“ a 传输消息给 b ”一般被描述成如下过程：
Alice想给Bob发送消息 m ，为了实现信息的安全传递，Alice和Bob事先通过密钥机制形成了密钥 k 并共享。然后Alice用密钥通过加密转换Enc（ k ， m ）= c ，将明文加密为密文消息 c ，并把密文 c 发送给Bob。接收到密文后，Bob基于密钥，通过解密转换 Dec（ k，c ）= m ，得到Alice想要传递的明文 m 。
根据密钥的管理策略，密码体制可以被分为对称密码体制和非对称密码体制。上述过程简单描述如下：在对称密码体制中 ， 通常只有一个密钥 ， 即 k Alice = k Bob = k ，并且这个密钥仅有Alice和Bob知道。在通信过程中，Alice和Bob通过该密钥对信息进行加密和解密。这里的加密算法和解密算法往往是互逆的，即Dec（ k ，Enc（ k ， m ））= m 。在非对称密码体制中，在密钥生成阶段会为Alice和Bob生成各自的密钥对（pk，sk）。其中，可以公开的那个密钥pk被称为公钥，不公开的那个密钥sk被称为私钥。
前面我们提到密码编码学的研究，主要是为了实现信息保密和身份认证这两类安全目标：为了实现信息保密，一般使用公钥加密、私钥解密，此时只有私钥的拥有者才能正确解密；为了实现身份认证，一般使用私钥签名（类似加密）、公钥验证（类似解密），此时知道公钥的任何人都可以验证（解密），但只能验证私钥拥有者签名的内容。这就是数字签名技术。
以上，我们简单介绍了密码学的一些基本概念。在讨论密码学和密码系统的时候，人们最朴素的需求是通过密码体制实现安全目标。接下来，就让我们看看密码体制的安全性都受哪些因素的影响。
让我们再回顾一下Alice和Bob通信的过程，看看要做到安全的通信，密码体制都需要做哪些事情。在整个过程中，通信双方希望传输的是加密后的密文，密文对于其他人来说应该是不可识别的，从而达到安全通信的效果；同时通信双方各自能够将密文转换为明文。实现这些目标的关键，在于Alice和Bob通信过程中的加密转换Enc（ k ， m ）= c 和解密转换Dec（ k，c ）= m 。其中，Alice和Bob知道密钥 k ，加/解密转换负责明文和密文的转换，同时不掌握密钥 k 的攻击者不能从密文获得明文的有效信息。
可以看出，密码体制的安全性主要包括两个方面：加/解密转换（Enc和Dec）的安全性，即密码体制抗破解的安全性；密钥（ k ）的安全性，即密钥管理的安全性。19世纪，奥古斯特·柯克霍夫提出了著名的柯克霍夫原则（Kerckhoffs's principle） ［5］ ，对于密码体制在这两个方面的安全性要求给出了描述：即使密码体制的一切运转细节被所有人知道，但只要密钥未被泄露，这个体系也应该是安全的。该原则已经成为密码系统设计的一项重要原则。
让我们来拆解一下柯克霍夫原则的含义。
“密码体制的一切运转细节被所有人知道”，是指加/解密转换（Enc和Dec）对所有人是公开的；具体来说就是，加/解密算法本身是所有人都知道的。这对密码体制设计者提出了要求，要在算法本身公开的情况下，体系仍是安全的。达成这一目标取决于两个方面。一方面是柯克霍夫原则的另一个要求，即“密钥未被泄露”，具体来说就是密钥 k （除了非对称加密中的公钥）是需要保密的。这就是密钥管理的研究内容，包括密钥的产生、存储、分配、保护、更新、撤销、销毁等。
另一方面，在密钥未被泄露的前提下，确保即使有人知道加/解密算法的内容，也无法破解加密的信息数据。
你肯定想知道如何做到这一点。
要讨论这个内容，需要从密码体制的无条件安全性和有条件安全性说起。
无条件安全性，也叫理论安全性，是指假定攻击者拥有无限的计算资源，仍然无法破译该密码体制。香农基于信息论证明了“一次一密”的加密体系可以实现无条件安全性。一次一密（one timepad）指使用与明文长度等长的随机密钥进行加密，并且密钥本身只使用一次。但很可惜这样的方式并不具备实用性，因为一次一密的密钥必须跟明文一样长（即|k|=|m|），而且密钥不能重复使用。可以说，香农证明了绝对安全是可以达到的。同时我们也可以看出，绝对安全的密码体制在实际应用中是有局限性的。我们需要考虑兼顾实用因素下的安全性评估方式，即有条件安全性。
有条件安全性，是指假定攻击者的计算资源有限或者存在某些条件的限制时的系统安全性。有条件安全性关注现实世界密码系统的实际安全性。可以看到，加入实用因素后，若想构造一种安全且高效的密码算法，挑战很大，需要从安全强度、运算效率、系统开销等方面综合考虑。当然，这样的难题总会被科学家和工程师解决。即使这不是理论上最完美的解决方式，也总能很好地解决现实世界的问题。
简单来说，目前业界主流的安全性设计思路和目标是，实现密钥管理简单，且算法破解过程的消耗远大于破解后的收益的密码体制。这里所说的“消耗远大于收益”，可以是破解所需要消耗的资源（一般指计算资源）远大于攻击者所拥有的资源，也可以是破解所需要的时间远大于信息本身存在的时间等，目的就是让破解“入不敷出”。用相对形式化一些的方式来描述的话，一个成功的密码体制需要满足以下原则：
（1）∀ k ∈ K ， m ∈ M ，Enc（ k ， m ）是容易计算的。
（2）∀ k ∈ K ， c ∈ C ，Dec（ k ， c ）是容易计算的。
（3）对于用密钥 k 加密后的密文 c ∈ C ，在不知道密钥 k 的情况下，Dec（ k，c ）= m 是难以计算的。
在计算机时代，密码体制实现这样的安全目标主要基于计算复杂性理论，这种安全性可以被称为计算安全性。计算复杂性理论在图灵机的理论框架下刻画了算法破解的计算困难程度。而计算安全性，就是基于计算复杂性理论来建立这样一个密码体制的：虽然破解算法理论上可行，但限于现有的计算能力和工具，攻击者是不可能完成破解所需要的计算量的，或者不可能在可接受的时间内完成破解。要实现这样的目的，一般会基于数学困难问题设计密码机制，如基于分解大整数困难性的RSA密码体制及其变体、基于离散对数困难问题的公钥密码ElGamal密码体制及基于椭圆曲线的ElGamal密码体制等。
这些数学困难问题的理论基础是数论，密码学也成为数论这门学科的一个重要应用。接下来，让我们简单认识一下数论。
数论是最古老的数学分支之一，是一门优美的纯数学学科。数论的纯粹性吸引着一代又一代的数学家。被誉为“数学王子”的德国数学家高斯称赞“数学是科学的皇后，而数论是数学的女王”。前文提到的大数学家希尔伯特也说过：“数学中没有一个领域能够像数论那样，以它的美——一种不可抗拒的力量，吸引着优秀的数学家。”
数论主要研究整数的性质和相互关系，产生了很多著名的悬而未解的问题，如哥德巴赫猜想、孪生质数猜想等。对这些问题严谨的数学证明的探索虽然仍未完成，但其研究推动了整个数学学科的发展，催生了大量的新思想和新方法。
数论的产生最早可以追溯到公元前的希腊时代。公元前300年左右，欧几里得发表了他的经典著作《几何原本》。《几何原本》是古希腊数学发展的顶峰和不朽杰作。欧几里得基于5个公理和5个公设，通过严密的公理化逻辑推导，构建了整个欧氏几何大厦。其内容和公理化推导的形式，对几何学本身以及整个数学的发展都产生了不可估量的影响。在这套13卷本的伟大著作中，第7卷到第10卷讨论了与数论相关的问题。在欧几里得时代大约2000年后，数论取得了再一次的重大突破。18世纪末，数学家高斯完成了他的经典著作《算术研究》（该书于1801年出版）。这本著作汇集了费马、欧拉、拉格朗日等数学家的研究成果。在《算术研究》中，高斯将这些研究成果进行了系统化，并将符号进行了标准化，同时高斯还提出了很多新的概念和研究方法。至此，数论真正走向成熟，成为一门独立的学科。随着数学研究和数学工具的不断深化，新的数论研究工具和成果不断出现。计算机科学和应用数学的发展，使得数论得到了广泛的应用，特别是在现代密码学领域，数论已经成为支撑密码学发展的重要数学基础。
我们通过著名的RSA算法来说明数论在密码学中的应用。RSA是1977年由Ron Rivest（罗纳德·李维斯特）、Adi Shamir（阿迪·萨莫尔）和 Leonard Adleman（伦纳德·阿德曼）一起提出的密码算法，RSA就是他们三人姓氏开头字母的组合。RSA采用了一种非对称的密钥体制，在这种体制下，使用不同的加密密钥（一般为公钥，用于加密信息）与解密密钥（一般为私钥，用于解密信息），并且在计算上由已知公钥推导出私钥是不可行的。
数论是如何支撑实现RSA这种密码机制的呢？
首先把RSA中用到的数论基本概念做一个简要介绍。（这里仅做概念的简要介绍，以便大家理解RSA。不感兴趣的读者可以略过解释和公式，直接阅读后面RSA如何运转的内容。）
整除： 设 a ， b ∈ Z ，其中 Z 表示整数集合，如果 a ≠0，并且∃ q ∈ Z ，使得 b = aq ，则称 b 可被 a 整除。
质数： 又称为素数，指在大于1的自然数中，只能被1和自身整除的数。
互质关系： 如果两个正整数，除了1之外没有其他公因子，就称这两个数为互质关系（该关系也被称为互素关系）。
模运算： 如果 a - b 能够被 m 整除，记作 a ≡ b mod m 。这也被称为模 m 的同余式。
逆元： 如果两个正整数 a 和 n 为互质关系，则一定存在整数 b ，使得 ab ≡1（mod n ）， b 就被称为 a 模 n 的逆元。
欧拉函数： 记为 φ （ n ），表示对于正整数 n ，在小于或等于 n 的正整数之中，与 n 构成互质关系的正整数个数。例如，取 n =10，在小于或等于10的正整数之中，与10形成互质关系的正整数是1、3、7、9，因此 φ （10）=4。
欧拉定理： 如果两个正整数 a 和 n 为互质关系，则 a φ （ n ） ≡1（mod n ）成立，其中 φ （ n ）为 n 的欧拉函数。
接下来，我们结合Alice和Bob 的通信过程，看看RSA是如何运转的。
密钥生成阶段如下。
步骤1： 随机选择两个不相等的质数 p 和 q 。例如，随机选择 p =97， q =71。
步骤2： 计算 p 和 q 的乘积 n 。这里 n =97×71=6887。
步骤3： 计算 n 的欧拉函数 φ （ n ）。这里 φ （6887）=6720。
步骤4： 随机选择一个整数 e ，满足1＜ e ＜ φ （ n ），且 e 与 φ （ n ）互质。这里选择 e =37。
步骤5： 计算 e 模 φ （ n ）的逆元 d ，即 ed ≡1（mod φ （ n ））。这里计算得到 d =1453。
至此，密钥生成阶段形成了公钥（ n，e ），在这里即（6887，37）；以及私钥（ n，d ），在此即（6887，1453）。
需要强调的是，在密钥生成阶段生成的 p 、 q 、 n 、 φ （ n ）、 e 和 d 中，只有用于公钥（ n，e ）的两个数字是公开的，即（6887，37）。其他数字均只有Alice和Bob 知道。
加/解密阶段如下。
步骤1： 假设Alice要给Bob发送的消息是一个字符“@”，在计算机世界里，这个字符对应的ASCII码为64。所以这里的明文 m =64，且 m ＜ n 。
步骤2：
Alice通过公钥pk
Bob
及加密转换Enc（
m
，pk
Bob
）得到密文
c
。加密转换的具体内容是数学公式
≡
c
（mod
n
）。这里pk
Bob
=
e
=37，
m
=64，计算64
37
mod 6887=1682，即加密后的密文
c
=1682。
步骤3：
Bob接收到密文
c
后，用自己掌握的私钥sk
Bob
及解密转换Dec（
c，
sk
Bob
）解密出明文
m
。解密转换的具体内容是数学公式
≡
m
（mod
n
）。这里sk
Bob
=
d
=1453，
c
=1682，计算1682
1453
mod6887=64，即
m
=64。Bob对照ASCII码，就知道Alice发送了字符“@”。
至此，我们通过简单的例子，了解了RSA的运转流程以及涉及的数论知识。但是你可能还有疑问：这个运算过程看起来好像并不十分复杂，用计算机来计算的话似乎也没有什么困难，如何能实现安全目标呢？上述过程中的哪些因素和哪些步骤实现了应用中的安全目标呢？再具体一点儿，上述过程是怎样保证只有Alice和Bob知道发送的消息“@”呢？
安全性说明：让我们回顾一下上面这个例子中Alice和Bob 的通信过程。在密钥生成阶段，通信双方通过计算获得了
p
、
q
、
n
、
φ
（
n
）、
e
和
d
。Alice想要给Bob传递的明文消息是
m
，同时为了安全传输，在RSA中，基于数论知识将加/解密转换设计为数学公式
≡
c
（mod
n
）和
≡
m
（mod
n
）。所以，真正在网络中传递的是基于加密转换后获得的密文
c
。
在上述信息中，按照柯克霍夫原则，加/解密转换（也就是数学公式）是所有人都可以知道的。根据现实世界网络通信过程不能完全保证安全的假设，加密后传输的密文 c 是可能被攻击者获取的。根据非对称密钥机制，公钥信息，即（ n，e ）也是公开的。需要确保不被泄露的信息，包括私钥信息 d 以及在密钥生成阶段随机选择的质数 p 和 q 。
这里的安全性关键是，如果私钥信息 d 是未被泄露的，攻击者能否基于公开的信息 n 和 e ，推导、计算得到 d 呢？
通过前面介绍的数论知识可知， d 是 e 模 φ （ n ）的逆元，根据公式 ed ≡1（mod φ （ n ）），当我们知道 φ （ n ）时，就能够计算出 d 。接下来看看欧拉函数 φ （ n ）如何计算。
回顾密钥生成阶段，我们通过随机选择的两个质数 p 和 q ，得到了乘积 n 。根据欧拉函数的性质，如果 n 可以被分解为两个质数的乘积，那么 φ （ n ）=（ p -1）（ q -1）。（欧拉函数有更为丰富的内容，这里为了便于理解，直接给出两个质数时的欧拉函数计算公式，未涉及具体的数学推导和说明。）所以，如果知道 p 和 q ，就可以得到 φ （ n ）。
但是我们知道， p 、 q 和私钥 d 都是非公开的信息，因此对于想要破解密文的攻击者而言，只有通过对 n 进行因式分解，得到 p 和 q ，从而计算 φ （ n ），才能最终计算得到私钥 d 。
至此，我们终于到达了RSA安全性的核心：在当前的计算机理论框架和算力下，大整数的因数分解（即对 n 进行因式分解，得到 p 和 q ），是一件非常困难的事情。因此，只要 p 、 q 和私钥 d 未被泄露，攻击者就很难通过公开信息破解密文。
大整数的因数分解为何如此困难呢？
前面我们介绍了，计算机世界的理论基础源于图灵机这个计算模型。基于图灵机计算模型，图灵也给出了计算的极限，明确了图灵机可以解决的问题、不能解决的问题，这些都划定了现代计算机可以解决的问题的理论边界。冯·诺依曼结构奠定了计算机的工程结构基础，也从工程上给出了计算能力的工程边界。而大整数因式分解困难的原因如下：由于计算机的理论和工程能力边界的限制，即使这个问题的求解是通过计算机来完成的，但要具备求解问题所需要的资源（算力、时间、空间等等）也是困难的，或者说是不可承受的。
在计算机世界中，这样一类问题叫作计算困难问题。
计算困难问题，简单来说是指计算机难以高效得到答案的一类问题。在密码体制设计中，计算困难问题是非常重要的设计基础。参考阿基米德的名言“给我一个支点，我就能撬动地球”，我们可以说“给密码设计者提供一个计算困难问题，就可以构建出一个公钥密码体制”。当然，上面提到的“计算机难以高效得到答案”这样的描述还不够严谨科学，为了更好地研究这个问题，我们需要更为理论化的工具。那么在计算机世界里，如何严谨科学地评估和刻画计算机解决问题的难易程度呢？这就是计算复杂性理论的研究内容。
在1.3节中已经介绍过，图灵机给出了一个可实现的通用计算模型，并将计算归结为一些内容简单、含义明确的基本操作。图灵证明了由图灵机这个计算模型按照一定的规则，通过确定性的机械操作可以完成各种计算问题。这些可以在图灵机模型下进行计算的问题被称为可计算问题；换句话说就是，可计算问题都是可以通过计算机来解决的。计算机科学家和工程师为了求解各类问题而设计出相应的算法，理论上这些算法都可以被看成最终转换成机械操作步骤的各种组合。
让我们回顾一下图灵机的构成：纸带、读/写头、状态寄存器和指令表。这个计算模型下的机械操作步骤可以对应成读/写头在纸带、状态寄存器和指令表之间的来回移动和读/写操作。简单来说，为了计算某一个问题而需要读/写头完成的操作数量，就可以被理解为解决这个问题所需的计算资源。而在求解过程中纸带、寄存器、指令表等部件存放的信息规模可以被理解为解决这个问题所需的存储资源数量。
计算复杂性理论主要研究的就是求解计算问题时所需的资源，包括如何衡量、评估以及如何优化、节省这些资源。这些资源主要包括算法步骤的数量或者规模，即时间复杂度；以及所需的存储资源的数量，即空间复杂度。在计算机世界中，时间复杂度和空间复杂度用来刻画和衡量计算机求解问题的难易程度。下面我们简要介绍一下计算复杂性理论中是如何描述一个算法的时间复杂度的。
假设一个需要求解的问题的规模为 n （比如，有 n 个数字的大整数），那么求解这个问题的算法的时间复杂度就被描述为一个以 n 为参数的函数关系，表示为 O （ n ）。这样就可以通过这个函数关系来研究算法的时间复杂度。常见的时间复杂度从小到大如下所示：
O （1）＜ O （log n ）＜ O （ n ）＜ O （ n log n ）＜ O （ n k ）＜ O （ k n ）＜ O （ n ！）
这些复杂度代表什么意思呢？
如果某种算法求解问题所需要的时间与问题规模无关，该算法就被称为具有常数复杂度，表示为 O （1）。这种复杂度算法的运行时间不会随着问题规模的增加而增加，是时间复杂度最低、算法效率最高的一类算法。
如果某种算法求解问题所需要的时间与问题规模成指数关系，该算法就被称为具有指数复杂度，表示为 O （ k n ）。其中， k 表示常数。这种复杂度算法的运行时间随着问题规模的增加，呈现指数增加的趋势。这表示这种算法的运行效率比较低。
按照类似的定义， O （log n ）表示算法具有对数复杂度， O （ n ）表示算法具有线性复杂度， O （ n log n ）表示算法具有对数线性复杂度， O （ n k ）表示算法具有多项式复杂度， O （ k n ）表示算法具有指数复杂度， O （ n ！）表示算法具有阶乘复杂度。
其中，对于复杂度为
O
（
k
n
）、
O
（
n
！）的算法，当这类算法所解决问题的规模比较大的时候，算法的复杂度将会迅速增加。从算法设计的角度来说，我们要尽量避免设计出这些复杂度的算法，因为该算法的执行效率不高。但是从另一个方面去看，如果解决某类问题的算法复杂度是
O
（
k
n
）、
O
（
n
！），就代表当问题规模较大时，这类问题通过计算机仍“难以高效得到答案”，那么这类问题就可以被称为计算困难问题。比如大整数分解问题，目前最优的算法复杂度为
。这是指数复杂度级别的算法。因此，大整数分解可以作为密码体制设计的一个基础，事实上RSA密码体制的安全核心就基于此。
至此，我们介绍了什么样的问题被称为计算困难问题，并介绍了这类问题基于计算复杂性理论是如何衡量和评估算法复杂度的。
关于计算复杂性理论，再多说一点儿。
在计算复杂性理论中，通过计算机能够在多项式时间复杂度内解决的问题，被称为P问题（Polynomial problem）。在多项式时间复杂度内不能解决，但通过计算机能够在多项式时间复杂度内验证答案是否正确的问题，被称为NP问题（Non-deterministic Polynomial problem）。NP问题的一个特点是，问题的求解比较困难，但是验证某个答案是否正确相对容易。大整数分解就是一个NP问题。
如果一个问题同时满足：（1）它是一个NP问题，（2）所有NP问题都可以被归约到它。那么这个问题被称为NP完全问题，也被称为NPC问题（Non-deterministic Polynomial Complete problem）。其中，第2个条件提到的“归约”的含义是：如果可以用问题B的解法解决问题A，或者说问题A可以被转变成问题B，就称问题A可以被归约为问题B。因此NP完全问题的一个意义在于，如果可以在多项式时间复杂度内求解一个NP完全问题，那么就可以在多项式时间复杂度内求解其他任何的NP问题。
如果一个问题满足NP完全问题定义的第二条但不一定满足第一条，该问题被称为NP困难问题，也被称为NP-Hard问题。
为什么要提到上面这些概念呢？这跟计算机界的一个著名难题相关。
将时间拉回到2000年。美国克雷数学研究所（Clay Mathematics Institute）于2000年5月24日公布了7个数学难题，即“千禧年世纪难题”。根据克雷数学研究所制定的规则，答题没有时间限制，但是所有数学难题的解答必须发表在数学专业期刊上并经过各方验证。只要通过验证，研究者每解决一个数学难题，将获得100万美元奖金。在1.3节中曾提到，1900年希尔伯特应邀参加在巴黎举办的第二届国际数学家大会。在该大会上，希尔伯特提出了著名的23个数学问题。“千禧年世纪难题”与希尔伯特提出的23个数学问题遥相呼应。这7个数学难题中排名榜首的问题，就是著名的“P=NP？”问题。
这个问题的解答，会直接影响计算机科学领域的理论基础和发展前景。
举个例子，如果证明了P=NP，那么大整数分解这个NP问题，将会找到一个P问题量级的解答。也就是说，大整数分解将不再是计算困难问题，不会有“计算机难以高效得到答案”的特点。如此一来，基于此构建的密码体制将不再安全。但如果证明了P≠NP，就说明计算困难问题仍将是密码体制设计的一个坚实基础，基于此构建的密码体制，在图灵机和冯·诺依曼结构框架下仍是足够安全的。
这个难题的意义，不仅仅是其本身的难度，更重要的是，无论证明这个问题成立与否，或者证明其不可被证明，都会给计算机科学和数学界带来巨大的影响。