单向陷门函数

概述

单向陷门函数（One-Way Trapdoor Function）是公钥密码学的数学基础：正向计算容易、逆向计算困难，但掌握"陷门"（私钥）后逆向计算变得容易。

关键内容

定义

一个函数 f 是单向陷门函数，如果： 1. 正向容易：给定 x，计算 f(x) 很快 2. 逆向困难：给定 f(x)，找到 x 在计算上不可行 3. 陷门：如果掌握某个秘密信息（陷门/私钥），逆向计算变得容易

在密码学中的角色

• 公钥加密：公钥对应 f，私钥对应陷门
• 数字签名：私钥对应 f^{-1}（用陷门逆向计算），公钥对应 f（正向验证）

候选函数

• 大整数分解：给定 n = p × q，求 p 和 q（RSA 基础）
• 离散对数：给定 g^a mod p，求 a（Diffie-Hellman 基础）
• 椭圆曲线离散对数：椭圆曲线上的离散对数（ECC 基础）

与 P vs NP 的关系

如果 P = NP，则单向函数不存在——所有"困难"问题都有快速算法。因此，公钥密码学的存在性依赖于 P ≠ NP 的假设。

来源

• raw/books/计算机科学/11-diffie-hellman-new-directions.md

相关

• 公钥密码学 — 数学基础
• Diffie-Hellman 论文 — 论文中引入
• 计算复杂度理论 — 计算困难性假设
• P vs NP — 如果 P=NP，单向函数不存在