想象你住在一个热闹的村庄里，家家户户门口挂着一个带细缝的信箱。任何人都能把写好的信塞进某个信箱——这是再自然不过的事；但想打开信箱取出信，却必须用到只有主人贴身保管的那把钥匙。这个每天发生在村庄里的场景，就是非对称加密的缩影：信箱人人可用，钥匙唯我独有。 RSA 和 ECC 就是两把大名鼎鼎的“信箱锁”。RSA 像一把“合金锁”：铁匠把两块特种金属熔铸成一块合金，铸锁容易，要把这块合金重新分离成两块金属，却难如登天。ECC 则像一把“跳格子锁”：在村口的椭圆棋盘上，从起点按规则跳若干次到达终点很容易，但旁人只看到起终点，想数出到底跳了多少次，同样难如登天。这两把锁守护着现代互联网的全部秘密——你每一次网购、转账、登录，背后都有它们在默默站岗。这篇文章就带你拆开这两把锁，看看内部的齿轮如何咬合。

岗位关联

学会 RSA 与 ECC，就是握住了互联网隐私地基的图纸。无论做 AI 系统还是后端服务，为数据选对锁、配好钥匙，是工程师守护用户信任的第一道防线。

目录
  1. 可视化演示
  2. 非对称密码基础
  3. RSA密钥生成
  4. RSA加解密运算
  5. RSA安全性分析
  6. ECC曲线基础
  7. ECC密钥交换
  8. 曲线离散对数
  9. RSA与ECC对比
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

非对称加密使用公钥加密私钥解密，RSA基于大数分解难题，ECC基于椭圆曲线离散对数。本文详解RSA的密钥生成、... 切换模式查看不同维度。

本节配有交互动效（进入视口后自动加载，约 3KB）。

非对称加密的：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现

非对称密码基础

从前村庄里只有一把共用的挂锁，寄信人和收信人得各配一把相同钥匙，钥匙在送信途中一旦被劫，秘密就全部泄露。于是锁匠发明了“个人信箱”：每个人把信箱挂在门口，投递口敞开，谁都能塞信；但信箱的打开方式只有主人知晓。这就是非对称——“锁”和“钥匙”不再相同，锁负责锁住，钥匙负责开启，二者各司其职。

在密码学中，密钥总是成对出现：公钥对外公开，像门牌号一样人人可查；私钥绝对保密，像贴身钱包一样不离身。加密时使用收件人的公钥，解密时只用收件人自己的私钥。即使加密过程被全程围观，没有私钥谁也读不懂密文。这个模型顺带解决了对称加密最头疼的“密钥分发”问题——寄信人不再需要想方设法把共享钥匙安全送到对方手里。

数学上，非对称加密的本质是一个“单向门”：正向运算轻松，逆向运算只有掌握私钥的人能完成。整个通信模型可以浓缩为一个公式：

从此，村庄里再也不用费力传递钥匙了。投信永远是公开、顺手的动作，开信永远是主人独享的权利。方向不对称，安全却成立——这正是非对称加密名字的由来，也是 RSA 与 ECC 共同的立身之本。

c=EKpub(m),m=DKpriv(c)\displaystyle c = E_{K_{pub}}(m), \quad m = D_{K_{priv}}(c)
这个公式是说：用公钥把明文变成密文是人人可做的，但把密文还原成明文，只有私钥持有者能完成。
  1. 明文 m你想寄出的原始消息，比如“今晚村口见”。
    m\displaystyle m
  2. 加密算法 E把信塞进信箱的机械动作，规则公开、人人可做。
    EKpub(m)\displaystyle E_{K_{pub}}(m)
  3. 公钥 K_pub收件人公开的信箱型号，所有人都能拿到。
    Kpub\displaystyle K_{pub}
  4. 密文 c塞进信箱后被锁芯搅乱的信纸，旁人看到的乱码。
    c\displaystyle c
  5. 解密算法 D 与私钥 K_priv用贴身钥匙反向还原信的机械动作，只有主人能完成。
    DKpriv(c)\displaystyle D_{K_{priv}}(c)

RSA密钥生成

铁匠阿贵打造的“合金锁”大有讲究。第一步，他去矿石堆里挑两块成色上好的特种金属——这两块金属必须极度特殊，不能是路边随手捡的普通铁。然后他把两块金属投进熔炉，铸成一块合金 n。合金的成分配方挂在门外当公钥，而还原合金需要的“私密扳手”则藏在怀里。

在 RSA 中，“金属”就是两个大素数 p 和 q，“合金”就是它们的乘积 n。与此同时，还需要一个中间量 φ(n)，它统计着与 n 互质且小于 n 的正整数个数，是设计钥匙的核心参数。由于 n = p × q 且 p、q 是素数，φ(n) 可以直接由 p、q 算出——这正是只有铸锁者知道的“配方”。为保障安全，p、q 必须是随机生成的强素数，且彼此不能太接近，否则攻击者可以用费马分解法快速拆锁。

RSA 密钥生成的三个关键步骤可以写成：

铸锁的门道全在于“只进不出”：p、q 一旦熔进合金 n，铁匠就把矿石残渣全部销毁。旁人只看到合金块 n，想按配方反推两块金属，就要面对“大数分解”这个无底洞。锁由配方定义，安全由拆分难度守护。

n=p×q,φ(n)=(p−1)(q−1),e⋅d≡1(modφ(n))\displaystyle n = p \times q, \quad \varphi(n) = (p-1)(q-1), \quad e \cdot d \equiv 1 \pmod{\varphi(n)}
这段公式说明：先让两个素数相乘得到模数 n，再用欧拉函数算出配方 φ(n)，最后选一个公开指数 e，并解出满足条件的私钥指数 d。
  1. 大素数 p、q随机挑选的两块“特种金属”，真实场景中各 1024 位比特。
    p, q\displaystyle p, \ q
  2. 模数 n两块金属熔铸成的合金块，长度约 2048 位，公钥和私钥都包含它。
    n=p×q\displaystyle n = p \times q
  3. 欧拉函数 φ(n)合金的“成分配方”，只对掌握 p、q 的人可见。
    φ(n)=(p−1)(q−1)\displaystyle \varphi(n) = (p-1)(q-1)
  4. 公开指数 e通常固定选 65537，是锁上的“通用扣”，公钥 = (n, e)。
    e\displaystyle e
  5. 私钥指数 d满足 e·d ≡ 1 (mod φ(n)) 的“私密扳手”，私钥 = (n, d)。
    d≡e−1(modφ(n))\displaystyle d \equiv e^{-1} \pmod{\varphi(n)}

RSA加解密运算

合金锁铸好了。现在你要给阿强寄信：把信纸叠好，塞进阿强家信箱的投递口。锁芯“咔嚓”一声，信纸被搅成一张写满乱码的纸——这个过程就是加密。阿强收到后，用私密扳手反向转动锁芯，乱码又变回清晰的信纸。

RSA 的加密不是物理搅动，而是模幂运算：先把明文消息转换成一个小于 n 的整数 m，然后计算 m 的 e 次方并对 n 取余数。因为取了余数，结果永远落在 0 到 n−1 之间，密文长度与模数严格一致。这个运算在计算机里用快速幂算法完成，即使 e 是 65537 这样的大数，也只需几十次乘法，速度飞快。

\begin{aligned}

\displaystyle c = m^{e} \bmod n, \quad m = c^{d} \bmod n

\end{aligned}

1. 加密运算 m^e：把明文做 e 次自乘，相当于让信纸连续通过 65537 道锁芯齿轮。

me\displaystyle m^{e}

2. 模 n：对 n 取余数，把指数爆炸的结果“折叠”回 n 的范围，保证密文不超长。

 mod  n\displaystyle \bmod \ n

3. 密文 c：加密后的乱码纸，外人即使截获也读不懂。

c\displaystyle c

4. 解密运算 c^d：密文做 d 次自乘，d 是只有私钥才有的巨大指数。

cd\displaystyle c^{d}

5. 还原原理：欧拉定理保证 m^{e·d} ≡ m (mod n)，因为 e·d ≡ 1 (mod φ(n))，指数循环后回到起点——锁芯转一圈，信纸恢复原样。

me⋅d≡m(modn)\displaystyle m^{e \cdot d} \equiv m \pmod{n}

这就是“单向门”的具象体现：塞信纸进去人人可做，要还原必须让锁芯按私钥 d 的齿数反向转满一圈。发信者与收信者各做各的事，方向不同，却精确咬合。为了防止攻击者利用密文规律做手脚，工程上还会在加密前用 OAEP 等填充方案对消息进行随机化处理，让同样的明文每次加密都产生不同的密文。

RSA安全性分析

既然锁的原理公开、铸锁工具也在市面上，为什么没人能仿造钥匙？阿贵笑着说：“因为拆锁不是力气活，是运气活——你得把合金 n 重新还原成两块金属 p、q。熔铸只要一炷香，还原却要几百年。”

RSA 的安全根基是“大数分解难题”：已知 n = p × q，求 p、q。对当前计算机而言，没有多项式时间的分解算法。最好的通用方法是数域筛法，它的运行时间是一个“亚指数”复杂度——比纯指数稍好，但依旧随 n 的位数急剧膨胀。历史上 RSA 密钥长度也从 512 位、1024 位一路演进到今天的 2048 位起步，因为摩尔定律每前进一步，拆锁的算力就增强一分，锁的尺寸必须跟着升级。

数域筛法的时间复杂度近似为：

除大数分解外，RSA 的工程实现还面临多种攻击：多个用户共用同一个模数会引发共模攻击；没有填充保护的教科书 RSA 会被选择密文攻击击穿；实现时若私钥运算时序不稳定，还可能泄露侧信道信息。因此参数选择要求严格——p、q 必须是随机强素数、长度要足够、填充必须规范。锁的安全等级，取决于“拆锁”的时间成本：2048 位 RSA 的拆锁成本超过 2¹¹² 次运算，相当于让全世界所有计算机联机算上亿年。

Ln=e1.923(ln⁡n)1/3(ln⁡ln⁡n)2/3\displaystyle L_n = e^{1.923(\ln n)^{1/3}(\ln \ln n)^{2/3}}
这个公式描述了拆锁的难度：n 每增大一点，分解时间就呈亚指数级飙升，所以 2048 位的大数分解至今是不现实的。
  1. ln n模数 n 的自然对数，把 2048 位的大数“压缩”成一个可比较的指标。
    ln⁡n\displaystyle \ln n
  2. 主项 (ln n)^{1/3}决定难度主体增长，是难度曲线的核心驱动力。
    (ln⁡n)1/3\displaystyle (\ln n)^{1/3}
  3. 二阶项 (ln ln n)^{2/3}一个缓释的“减速带”，让曲线更加平缓。
    (ln⁡ln⁡n)2/3\displaystyle (\ln \ln n)^{2/3}
  4. 常数 1.923数域筛法的经验常数。
    1.923\displaystyle 1.923
  5. e^{…} 结构整体说明分解时间是 n 的“亚指数”函数——n 每加长一点，难度就飞速爬升。
    e1.923(ln⁡n)1/3(ln⁡ln⁡n)2/3\displaystyle e^{1.923(\ln n)^{1/3}(\ln \ln n)^{2/3}}

ECC曲线基础

阿贵的新作品是“跳格子锁”。村口空地上画着一块形状奇特的椭圆棋盘——一条椭圆曲线，棋盘格子的走法有一套全村公认的规则：从点 A 出发，连一条直线经过点 B，与曲线相交后再翻折到第三点 C，这个组合动作记为 A + B = C。它不像算术加法那样直来直去，更像一种有美感的“跳格子”。

椭圆曲线的方程是 y² = x³ + ax + b。曲线上所有点构成一个数学“群”：任意两点可以用上述规则相加得到第三点，并且满足结合律、交换律，还有一个特殊的“无穷远点”充当零元素。群的阶 n 是一个大素数，基点 G 经过反复标量乘法生成一个循环子群——跳格子的活动范围被限制在这个子群内，外人无法越界。

点加法的坐标公式是：

棋盘和规则全部公开，任何人都能验证某次跳跃是否合法。但“合法”并不等于“可控”——恰恰是这种看似简单的跳格子，隐藏了反向推导的深渊。下一节你会看到，阿强和小花正是利用这个棋盘完成了不可能的秘密握手。

λ=y2−y1x2−x1,x3=λ2−x1−x2,y3=λ(x1−x3)−y1\displaystyle \lambda = \frac{y_2 - y_1}{x_2 - x_1}, \quad x_3 = \lambda^2 - x_1 - x_2, \quad y_3 = \lambda(x_1 - x_3) - y_1
这个公式告诉我们如何计算两个点的“和”：先算连线的斜率 λ，再用 λ 组合出结果点的横纵坐标。
  1. 点 P、Q棋盘上两个已知格点，各有一对坐标 (x, y)。
    P=(x1,y1), Q=(x2,y2)\displaystyle P = (x_1, y_1), \ Q = (x_2, y_2)
  2. 斜率 λ连接 P、Q 两点的直线斜率，决定下一步跳跃的方向。
    λ=y2−y1x2−x1\displaystyle \lambda = \frac{y_2 - y_1}{x_2 - x_1}
  3. 横坐标 x_3结果点的横坐标，等于 λ² 减去两个原点的横坐标。
    x3=λ2−x1−x2\displaystyle x_3 = \lambda^2 - x_1 - x_2
  4. 纵坐标 y_3结果点的纵坐标，由斜率和横坐标差值组合而成。
    y3=λ(x1−x3)−y1\displaystyle y_3 = \lambda(x_1 - x_3) - y_1
  5. 标量乘法 kP同一个点自己加自己 k 次，即 kP = P + P + … + P，是 ECC 最核心的运算。
    kP=P+P+⋯+P⏟k 次\displaystyle kP = \underbrace{P + P + \cdots + P}_{k \ \text{次}}

ECC密钥交换

阿强和小花想约定一个只有他俩知道的“秘密房间号”，但又不能直接传话——万一信差偷看怎么办？他们用跳格子棋盘玩了个聪明把戏：各自偷偷选一个跳跃次数作为私钥，然后只公布“自己从起点跳了那么多次后到达的位置”作为公钥。

这就是 ECDH 密钥交换协议。双方先约定好公共参数：一条椭圆曲线、一个基点 G。阿强随机选私钥 d_A，计算公钥 Q_A = d_A × G 并公布；小花同样选 d_B 并公布 Q_B。因为标量乘法是单向的，旁人看到 Q_A 也算不出 d_A。在实际的 TLS 握手中，双方还会为每次会话生成临时密钥对，即使长期私钥日后泄露，历史会话也无法被回溯解密——这就是前向保密。

共享密钥的计算是优雅的一步：

整个过程中，两人没有传递过一个秘密数字，却神奇地共享了同一个坐标。这就像两人各自闭嘴，却通过公开的“脚印”确定了同一间密室——跳格子锁的优雅就在于此。TLS 1.3、比特币协议里的密钥协商，正是这个把戏的工程化应用。

QA=dA×G,S=dA×QB=dA×dB×G=dB×QA\displaystyle Q_A = d_A \times G, \quad S = d_A \times Q_B = d_A \times d_B \times G = d_B \times Q_A
这个公式说明：阿强用自己的私钥去乘小花的公钥，小花用自己的私钥去乘阿强的公钥，两人殊途同归，得到同一个点 S。
  1. 公共基点 G双方约定的起点，写在棋谱第一页，全员公开。
    G\displaystyle G
  2. 私钥 d_A、d_B各自的跳跃次数，是随机数，牢牢保密。
    dA, dB\displaystyle d_A, \ d_B
  3. 公钥 Q_A、Q_B各自的落地位置，是曲线上的点，对外公开。
    QA=dA×G,QB=dB×G\displaystyle Q_A = d_A \times G, \quad Q_B = d_B \times G
  4. 共享密钥 S阿强算 d_A × Q_B，小花算 d_B × Q_A，结果相同。
    S=dA×QB=dB×QA\displaystyle S = d_A \times Q_B = d_B \times Q_A
  5. 安全性旁人只知道 Q_A、Q_B、G，要得到 S 必须先算出 d_A 或 d_B，这正是离散对数难题。
    S=dAdBG\displaystyle S = d_A d_B G

曲线离散对数

为什么旁人偷看脚印也无法复制密室？假设棋谱上只有两行记录：起点是 P，终点是 Q。棋手从 P 出发按规则跳了若干次到达 Q，任何会跳格子的村民都能验证 Q 是合法位置，但你要问“他到底跳了几次”，所有人都会摇头——没有人愿意从 1 数到几亿。

这个谜题在密码学中叫“椭圆曲线离散对数问题”（ECDLP）：给定基点 P 和曲线上一点 Q，求整数 k，使得 Q = kP。如果 k 的取值范围是 2²⁵⁶ 量级，暴力枚举就是天文数字。目前已知最快的通用攻击算法是 Pollard 的 rho 算法，需要约 O(√n) 次运算——n 是群的阶，256 位时破解需要 2¹²⁸ 次，远超宇宙诞生以来的总运算量。

ECDLP 的定义与攻击复杂度可以写成：

对比 RSA 的“亚指数”分解复杂度，ECDLP 是目前已知难度更陡的单向门：同样的防护等级，ECC 需要的“铜料”只有 RSA 的一个零头。不过量子计算的 Shor 算法理论上能同时瓦解大数分解与离散对数，因此抗量子密码（如格密码）已成为下一代密码学的焦点。棋盘上的每一次跳动，都在指数级的深渊上架起一道独木桥。

Q=kP,k∈[0,n−1],攻击复杂度 O(n)\displaystyle Q = kP, \quad k \in [0, n-1], \quad \text{攻击复杂度 } O(\sqrt{n})
这里的核心是：正向算出 Q 很容易，反向求出 k 极难。k 就是私钥，Q 就是公钥。
  1. 基点 P公开的起点格。
    P\displaystyle P
  2. 公钥点 QkP 的结果，公开的终点格。
    Q=kP\displaystyle Q = kP
  3. 离散对数 k未知的跳跃次数，也就是私钥。
    k\displaystyle k
  4. 取值区间k 在 0 到 n−1 之间，n 是群的阶，约 256 位。
    k∈[0,n−1]\displaystyle k \in [0, n-1]
  5. 攻击复杂度 O(√n)破解所需的运算量随 n 开平方增长——n 是 256 位时，√n 是 128 位，即 2¹²⁸ 次。
    O(n)\displaystyle O(\sqrt{n})

RSA与ECC对比

两把锁各有拥趸。合金锁（RSA）通行百年，各家各户都认得，但用料厚重；跳格子锁（ECC）轻巧灵便，同样强度的锁只用四分之一铜料。如今新建的银行金库——TLS 1.3、区块链钱包——纷纷换上了跳格子锁。

密码学界用“安全强度”统一衡量两把锁：即破解所需运算量对应的比特数。NIST 给出的公认等价关系是 RSA-3072 与 ECC-256 大致相当，都提供约 128 位安全强度；RSA-2048 则约等于 ECC-224 的 112 位强度。同样防护等级下，ECC 的密钥长度只有 RSA 的约十分之一，运算更快、带宽占用更低，在移动设备和低功耗场景优势明显。

等价关系可以浓缩为：

实际应用中，RSA 仍是数字证书、SSH、代码签名的主力——因为老系统兼容性好、生态成熟；而 ECC 凭借短密钥高强度，成为区块链（secp256k1 曲线）、移动端 App、TLS 1.3 的默认选择。设计系统的原则很简单：兼容性优先选 RSA，性能与带宽敏感场景选 ECC。锁的江湖没有常胜将军，只有匹配场景的智慧，懂得两把锁的齿合原理，你就拥有了在安全架构舞台上自由配锁的底气。

RSA-3072≈ECC-256≈2128\displaystyle \text{RSA-3072} \approx \text{ECC-256} \approx 2^{128}
这个公式是说：一把 3072 位的 RSA 锁和一把 256 位的 ECC 锁，拆锁难度大致相同，都需要 2¹²⁸ 次运算。
  1. RSA-3072模数为 3072 位的 RSA 锁。
    RSA-3072\displaystyle \text{RSA-3072}
  2. ECC-256曲线阶为 256 位的 ECC 锁。
    ECC-256\displaystyle \text{ECC-256}
  3. 安全强度 2¹²⁸两者都约需 2¹²⁸ 次运算才能破解，即 128 位安全强度。
    2128\displaystyle 2^{128}
  4. 等价关系同样强度下，ECC 的密钥长度短得多，这正是它的核心优势。
    RSA-3072≈ECC-256\displaystyle \text{RSA-3072} \approx \text{ECC-256}

AI 应用场景

HTTPS/TLS——浏览器与服务器的“秘密握手”

阶段：数据加密传输（安全通信基础设施）

解决的问题：HTTP 明文传输时，账号密码在网络上裸露，中间人可随意窃听篡改。TLS 协议用 ECDHE（基于 ECC 的临时密钥交换）协商会话密钥，再用 ECDSA 或 RSA 签名验证服务器身份，双锁合璧。

具体案例：你访问网上银行时，地址栏出现小锁图标。TLS 1.3 握手第一步，浏览器与服务器通过“临时跳格子”协商出一次性共享密钥，再用证书链上的 RSA 或 ECC 公钥验证服务器身份。整个过程在几百毫秒内完成，你的登录密码从此不再裸奔。

区块链钱包的数字签名

阶段：身份认证与交易确权

解决的问题：如何证明一笔交易确实由账户主人发出，且发出后不可抵赖？区块链用 ECDSA 算法（secp256k1 曲线）实现数字签名——私钥签名、公钥验签，这是非对称加密的“反向使用”。

具体案例：比特币转账时，钱包用私钥对交易哈希签名生成一段签名数据，全网节点用对应公钥验证签名。任何人无法伪造签名，但所有人都能验证签名的真实性——这正是“公钥加密、私钥解密”的镜像应用：私钥“加密”（签名）、公钥“解密”（验签）。

SSH与数字证书——运维人员的入场券

阶段：服务器身份认证与远程登录

解决的问题：密码登录云服务器容易被暴力破解，SSH 密钥对让运维人员用非对称加密完成免密安全登录，RSA 4096 或 Ed25519 是目前主流选择。

具体案例：DevOps 工程师生成一对密钥，公钥上传到服务器的 authorized_keys 文件，私钥保存在本地。登录时服务器用公钥加密一个随机挑战，工程师的私钥能正确解密，身份即被确认——合金锁在这里充当了门卫。

Python 演示

python83 行
import random  def mod_inv(a, m):    # 用扩展欧几里得算法求 a 在模 m 下的逆元    x0, x1 = 1, 0    b = m    while b:        q = a // b        a, b = b, a - q * b        x0, x1 = x1, x0 - q * x1    return x0 % m  def gen_rsa(p, q):    # 输入两个大素数，输出 (公钥, 私钥)    n = p * q    phi = (p - 1) * (q - 1)    e = 65537    d = mod_inv(e, phi)    return (e, n), (d, n)  def rsa_encrypt(m, pub):    return pow(m, pub[0], pub[1])  def rsa_decrypt(c, priv):    return pow(c, priv[0], priv[1])  def ecc_add(P, Q, p, a):    # 椭圆曲线 y^2 = x^3 + a*x + b (mod p) 上的点加法    if P is None:        return Q    if Q is None:        return P    x1, y1 = P    x2, y2 = Q    if x1 == x2 and (y1 + y2) % p == 0:        return None    if P == Q:        lam = (3 * x1 * x1 + a) * mod_inv(2 * y1 % p, p) % p    else:        lam = (y2 - y1) * mod_inv((x2 - x1) % p, p) % p    x3 = (lam * lam - x1 - x2) % p    y3 = (lam * (x1 - x3) - y1) % p    return (x3, y3)  def ecc_mul(k, P, p, a):    # 标量乘法 kP = P + P + ... + P，用二进制展开加速    R = None    while k:        if k & 1:            R = ecc_add(R, P, p, a)        P = ecc_add(P, P, p, a)        k >>= 1    return R  def main():    # 用小的素数演示 RSA（真实场景要选 2048 位大素数）    p, q = 61, 53    pub, priv = gen_rsa(p, q)    msg = 42    ct = rsa_encrypt(msg, pub)    pt = rsa_decrypt(ct, priv)    print("RSA: msg={}, ct={}, pt={}".format(msg, ct, pt))     # 椭圆曲线 y^2 = x^3 + 2x + 2 (mod 17)，基点 G=(5,1)    p_curve, a, G = 17, 2, (5, 1)    dA, dB = 7, 11    QA = ecc_mul(dA, G, p_curve, a)    QB = ecc_mul(dB, G, p_curve, a)    SA = ecc_mul(dA, QB, p_curve, a)    SB = ecc_mul(dB, QA, p_curve, a)    print("ECDH 双方共享密钥一致:", SA == SB)    print("QA={}, QB={}, 共享点={}".format(QA, QB, SA))  if __name__ == "__main__":    main()
目的：用极小的素数完整演示 RSA 密钥生成、加解密闭环，以及 ECDH 密钥交换中双方如何得到一致的共享点。
  1. def gen_rsa(p, q):输入两个大素数，输出公私钥对，对应“合金锁”的铸锁配方。
  2. e = 65537工程上通用的公开指数，兼顾安全与速度。
  3. d = mod_inv(e, phi)用扩展欧几里得算法求私钥指数，是私钥“扳手”的诞生处。
  4. pow(m, pub[0], pub[1])Python 内置模幂运算，一行完成 RSA 加密。
  5. def ecc_add(P, Q, p, a):椭圆曲线点加法，对应“跳格子”的走法规则。
  6. def ecc_mul(k, P, p, a):标量乘法 kP，用二进制展开把 k 次跳跃压缩成几十次运算。
  7. SA = ecc_mul(dA, QB, p_curve, a)用自己的私钥乘对方公钥，得到共享密钥点。
  8. print("ECDH 双方共享密钥一致:", SA == SB)验证阿强和小花殊途同归，到达同一个密室。

常见误区

误区既然公钥和私钥是一对，那我拿到公钥，是不是花点时间就能算出私钥？反正数学公式都公开。

正解不能。公钥到私钥的反推依赖“单向门”——RSA 是 2048 位大数分解，ECC 是 2²⁵⁶ 量级的离散对数。这就像你看到一块合金，知道它是两种金属熔成的，但没有任何工具能把它无损分离。公钥公开的前提，正是这个反推在计算上不可行。

为何常见：数学课上习惯“知一求一”，直觉上觉得知道公式就能反解，忽略了计算复杂性的差距可以让“理论上可解”变成“实际上无解”。

误区ECC-256 的密钥才 256 位，RSA-2048 有 2048 位，所以 ECC 比 RSA 弱得多。

正解两种算法的安全根基不同，不能按位数直接比大小。NIST 的对照是 RSA-2048 ≈ ECC-224 ≈ 112 位安全强度，RSA-3072 ≈ ECC-256 ≈ 128 位。这就像比较一把铜锁和一把指纹锁，不能看体积，要看破解难度。

为何常见：人们习惯用数字大小衡量强度，但密码学的“位”代表的是破解运算量的对数，不同算法之间的换算需要查权威对照表。

误区ECC 叫“椭圆曲线”，那它肯定跟椭圆形有关，大概是在椭圆上取点做运算吧。

正解椭圆曲线方程 y² = x³ + ax + b 的图像是两条平滑分支，看起来像“腰果”或“S 形”，跟椭圆没有几何关系。“椭圆”之名来自计算曲线弧长时用到的椭圆积分，是历史命名遗留。

为何常见：名字带“椭圆”容易望文生义，加上教材里通常不解释命名的历史渊源。

误区用了 RSA 或 ECC，数据就万无一失了，算法本身永远不会被攻破。

正解安全性建立在“计算不可行性”之上，而不是数学上的绝对不可解。参数选错（小素数、弱随机数）、实现有漏洞（侧信道、填充缺失）、或者未来量子计算机成熟，都可能拆掉这把锁。密码学强调“可证明安全”和“安全参数”的动态演进，没有一劳永逸的锁。

为何常见：非对称加密的数学之美容易让人产生“完美保护”的错觉，忽略了工程实现和时代变迁的影响。

面试题

Q1. 在非对称加密中，以下哪一项必须严格保密？

单选题 · easy

  • A.公钥
  • B.私钥← 正确答案
  • C.密文
  • D.加密算法

答案：B。公钥、加密算法都公开，密文可以被截获，唯一的秘密就是私钥。就像村庄信箱的钥匙只配一把，只有主人持有。

Q2. RSA 的安全根基是下列哪个难题？

单选题 · easy

  • A.椭圆曲线离散对数
  • B.大数分解难题← 正确答案
  • C.哈希碰撞
  • D.格基约减

答案：B。RSA 的合金锁 n = p × q，安全依赖于把 n 分解回 p、q 的难度，这是大数分解难题。椭圆曲线离散对数是 ECC 的根基，哈希碰撞是哈希函数的问题。

Q3. RSA 密钥生成中，当 n = p × q 时，欧拉函数 φ(n) 等于多少？

单选题 · mid

  • A.(p+1)(q+1)
  • B.(p-1)(q-1)← 正确答案
  • C.p × q
  • D.(p-1) + (q-1)

答案：B。因为 p、q 是素数，φ(n) = φ(p)φ(q) = (p-1)(q-1)。这个“配方”是计算私钥指数 d 的关键，只有掌握 p、q 的人能算出来。

Q4. RSA 解密的核心运算是下列哪一个？

单选题 · mid

  • A.m = c^e mod n
  • B.c = m^d mod n
  • C.m = c^d mod n← 正确答案
  • D.d = e × φ(n)

答案：C。解密是用私钥指数 d 对密文 c 做模幂：m = c^d mod n。A 是加密公式，B 把方向搞反了，D 是错的等式。

Q5. ECC 的安全性基于下列哪个难题？

单选题 · mid

  • A.大数分解
  • B.椭圆曲线离散对数← 正确答案
  • C.背包问题
  • D.哈希单向性

答案：B。ECC 的安全基点是：已知 P 和 Q = kP，求 k 极难，这就是椭圆曲线离散对数问题（ECDLP）。大数分解属于 RSA，背包问题是被淘汰的公钥方案，哈希单向性与 ECC 无关。

Q6. 下列哪组 RSA 与 ECC 密钥长度大致提供相同的安全强度？

单选题 · mid

  • A.RSA-1024 与 ECC-224
  • B.RSA-2048 与 ECC-224← 正确答案
  • C.RSA-3072 与 ECC-192
  • D.RSA-4096 与 ECC-256

答案：B。NIST 对照表显示 RSA-2048 ≈ ECC-224 ≈ 112 位安全强度；RSA-3072 ≈ ECC-256 ≈ 128 位；RSA-1024 只约等于 ECC-160。密钥长度必须换算成统一的安全强度再比较。

Q7. 关于 ECDH 密钥交换，下列说法正确的有？

多选题 · mid

  • A.阿强的共享密钥是 d_A × Q_B← 正确答案
  • B.小花的共享密钥是 d_B × Q_A← 正确答案
  • C.双方最终得到同一个点 S = d_A × d_B × G← 正确答案
  • D.共享密钥可以直接用 Q_A × Q_B 计算

答案：ABC。ECDH 的精华是双方用自己的私钥乘对方的公钥，殊途同归：d_A × Q_B = d_A × d_B × G = d_B × Q_A。D 错误，曲线上的点之间没有定义“乘法”运算。

Q8. 以下哪些属于 RSA 在实际使用中需要防范的攻击或风险？

多选题 · hard

  • A.共模攻击← 正确答案
  • B.选择密文攻击← 正确答案
  • C.量子 Shor 算法← 正确答案
  • D.生日攻击

答案：ABC。共模攻击发生在多用户共用模数 n 时；选择密文攻击针对无填充的教科书 RSA；Shor 算法是量子计算机对 RSA 的根本威胁。生日攻击是针对哈希函数碰撞的攻击，与 RSA 无直接关系。

Q9. ECC 相比 RSA 的优势有哪些？

多选题 · hard

  • A.相同安全强度下密钥更短← 正确答案
  • B.相同安全强度下运算更快← 正确答案
  • C.密钥更短所以带宽占用更低← 正确答案
  • D.加密过程中无需使用随机数

答案：ABC。ECC 用 256 位就能达到 RSA 3072 位的安全强度，运算和带宽都更优。D 错误——ECC 的私钥生成和签名都依赖高质量随机数，弱随机数会直接泄漏私钥。

Q10. Pollard rho 算法破解 ECC 约需 O(√n) 次运算。当曲线阶 n ≈ 2²⁵⁶ 时，破解约需 2¹²⁸ 次运算，这对应多少位安全强度？

单选题 · extreme

  • A.128 位← 正确答案
  • B.256 位
  • C.112 位
  • D.512 位

答案：A。安全强度定义为破解所需运算量的比特数。2¹²⁸ 次运算就是 128 位安全强度，这正是 ECC-256 的强度等级。256 位是密钥或曲线阶的长度，不是安全强度；112 位对应 RSA-2048 / ECC-224 的强度。