扫码获取 VIP 码
添加管理员微信获取 VIP 码
在计算机网络通信中，信息的保密性始终是核心需求。在公钥密码体制诞生之前，人们依赖的是对称加密算法，也就是加密方和解密方使用完全相同的密钥。这种模式存在一个根本性难题：密钥如何安全地分发给通信双方？如果双方事先没有安全的信道交换密钥，那么整个加密体系就无从建立。这个问题被称为密钥分发难题，它困扰了密码学界数十年之久。
一九七六年，斯坦福大学的迪菲和赫尔曼发表了一篇划时代的论文，首次提出了公钥密码体制的概念。他们设想了一种全新的加密模式：加密密钥可以公开传播，而解密密钥由接收方秘密保存，两者在数学上相关联但从公开密钥推导出私有密钥在计算上不可行。这个设想为密码学打开了一扇全新的大门，但它只是一个概念框架，迪菲和赫尔曼并未给出具体的算法实现。
两年后的一九七八年，麻省理工学院的三位研究者罗纳德·李维斯特、阿迪·萨莫尔和伦纳德·阿德曼实现了这个构想。他们发表了一种以三人姓氏首字母命名的算法，这就是RSA非对称加密算法。RSA是人类历史上第一个既能用于数据加密又能用于数字签名的公钥密码算法，四十多年来历经无数密码分析者的攻击考验，至今仍然是全球应用最广泛的公钥密码体制，被嵌入到HTTPS协议、电子邮件加密、数字证书和软件授权等几乎每一个需要安全通信的现代系统中。
RSA算法的核心思想建立在数论中的一个基本事实之上：将两个大素数相乘得到乘积是极其简单的计算，但反过来，给定一个大的合数，要将其分解为两个素数因子却极其困难。这种正向计算容易而逆向计算困难的性质在密码学中被称为单向陷门函数。RSA利用大整数分解的困难性构造了这样一个陷门：任何人都可以用公钥加密消息，但只有掌握私钥中素数因子的人才能解密。这个精妙的设计将数论中最古老的问题之一转化为了保护数字世界安全的基石。
在软考的高级和中级多个科目中，RSA算法都是信息安全知识领域的核心考点。无论是系统架构设计师、系统分析师、网络规划设计师这些高级科目，还是信息安全工程师、软件设计师、网络工程师这些中级科目，RSA的密钥生成计算、加密解密过程和安全特性分析都是必考内容。本文将从数学原理讲起，深入到密钥生成的每一步计算推导，再结合历年真题进行逐题分析，帮助考生彻底攻克这个高频考点。
理解RSA算法的工作原理，必须首先建立扎实的数学基础。RSA的安全性依赖于三个核心数学概念：模运算、欧拉函数和欧拉定理。这三个概念构成了RSA密钥生成和加密解密过程的全部数学支撑，缺一不可。
模运算也称为同余运算，是数论中最基础的工具之一。当我们说两个整数a和b在模n下同余，意味着n能够整除a与b的差值。模运算最常用的性质包括加法和乘法的同余保持性：如果a和b模n同余且c和d模n同余，那么它们的和与积在模n下也分别同余。在RSA算法中，所有的加密和解密操作都是在模n的意义下进行的，模运算的同余性质保证了加密和解密的互逆性。模指数运算还有一个重要特性：可以在计算过程中随时取模而不影响最终结果，这确保了所有中间结果都保持在n以下的可控范围内。
欧拉函数用希腊字母φ表示，读作欧拉函数φ(n)，是RSA算法中最重要的数论函数，它定义为小于n且与n互素的正整数的个数。欧拉函数具有几个关键性质，这些性质直接决定了RSA密钥生成的计算公式。
第一个性质是关于素数的：如果p是一个素数，那么φ(p)等于p减去1，这是因为从一到p-1的所有整数都与p互素。例如当p等于7时，小于7且与7互素的数有1、2、3、4、5、6共六个，所以φ(7)等于6。第二个性质是积性：如果m和n互素，那么φ(m乘以n)等于φ(m)乘以φ(n)。结合这两个性质可以推导出第三个也是最关键的性质：如果n是两个不同素数p和q的乘积，那么φ(n)等于φ(p)乘以φ(q)等于(p减1)乘以(q减1)。这个公式正是RSA密钥生成中计算模数n的欧拉函数值的核心公式，也是考试计算题中出现频率最高的公式之一。
欧拉定理则建立了欧拉函数与模幂运算之间的深刻联系。欧拉定理的表述非常简洁：如果正整数a与n互素，那么a的φ(n)次方在模n下一定等于1。欧拉定理是数论中最重要的定理之一，它推广了费马小定理，后者只是欧拉定理在n为素数时的特例。在RSA算法中，欧拉定理是证明加密和解密互逆性的关键：正是因为这个定理，才能保证用公钥加密后用私钥解密一定能恢复出原始明文。
在RSA密钥生成的第五步中，需要求解私钥指数d，它满足条件e乘以d在模φ(n)下等于1。这意味着d是e在模φ(n)下的乘法逆元。计算模逆元的标准工具是扩展欧几里得算法，它不仅能计算两个整数的最大公约数，还能同时求出满足贝祖等式的系数。
扩展欧几里得算法的输入是两个整数a和b，输出是最大公约数g以及满足a乘x加b乘y等于g的整数x和y。当a和b互素时，g等于1，此时x就是a在模b下的乘法逆元。在RSA密钥生成场景中，我们将e和φ(n)作为输入，由于选择e时已经确保了e与φ(n)的最大公约数为1，算法输出的x经过模φ(n)规范化后就是私钥指数d。
这部分计算在考试中通常以两种形式出现：一种是给定素数p、q和公钥指数e，要求计算私钥指数d；另一种是直接给出加密或解密过程，要求完成模幂运算。前一种题型考查的是扩展欧几里得算法的应用能力，后一种题型考查的是大数模幂运算的技巧掌握程度。无论哪种形式，扎实掌握欧拉函数的计算和模逆元的求解方法都是解题的前提条件。
RSA算法的实际运行过程可以分为三个主要阶段：密钥生成阶段、加密阶段和解密阶段。其中密钥生成是整个算法的核心，也是考试计算题最集中考查的部分。下面我们按照标准的六步流程，详细推导每一步的数学依据和操作要点。
第一步，选择两个大素数p和q。在实际应用中p和q通常需要数百位甚至上千位十进制长度，以保证乘积n无法被有效分解。考试场景中p和q通常简化为较小的素数，比如三、五、七、十一、十三等，以便手工计算。这一步的关键约束是p和q必须是不相同的素数，如果p等于q，n就是完全平方数，分解极其容易，安全性彻底崩溃。
第二步，计算模数n等于p乘以q。这个n就是RSA算法的工作模数，它将同时出现在公钥和私钥中，也是所有加密和解密运算的模数。n的二进制长度被称为RSA的密钥长度，常见的有1024位、2048位和4096位。密钥长度直接决定了算法的安全强度，业界目前建议至少使用2048位的RSA密钥。
第三步，计算n的欧拉函数值φ(n)等于(p减1)乘以(q减1)。这里需要特别注意的是，φ(n)不是(p减1)乘以(q减1)以外任何形式，而是精确的这个乘积关系。很多考生在这里犯的错误是混淆了n的欧拉函数与一般合数的欧拉函数计算方法。对于两个素数乘积这种特殊形式，φ(n)的计算公式有且仅有(p减1)乘以(q减1)这一种正确形式。
第四步，选择一个公开指数e，它必须满足两个条件：e大于1且小于φ(n)，同时e与φ(n)互素。在实际应用中，e通常选择为65537这个固定的素数，因为它的二进制表示中只有两个1位，这使得模幂运算可以非常高效地执行。在考试的计算题中，e通常被给定为3、5、7或11等较小的值。e的选择不是随意的，它必须与φ(n)互素，否则就无法找到对应的私钥指数d，整个密钥生成过程就会宣告失败。
第五步，计算私钥指数d，它满足条件e乘以d在模φ(n)下等于1。这个步骤是RSA密钥生成中最具有计算量的环节，需要运用扩展欧几里得算法。具体来说，我们需要找到整数d和k，使得e乘d加k乘φ(n)等于1成立，其中的d经过模φ(n)规范化后就是私钥指数。这个等式来自贝祖定理，由于e和φ(n)互素，这样的d和k一定存在且d在模φ(n)下是唯一的。
第六步，销毁p、q和φ(n)，只保留公钥由e和n组成以及私钥由d和n组成。公钥可以公开发布给任何人，私钥必须由密钥所有者秘密保存。如果p、q或φ(n)中的任何一个泄露出去，攻击者就可以重构出私钥，RSA的安全性就不复存在了。
加密过程使用接收方的公钥对明文消息M进行变换。加密公式为密文C等于M的e次方模n。这里有一个重要的约束条件：明文M必须小于模数n。如果M大于或等于n，就需要将消息分块，逐块加密。在实际应用中，RSA通常不直接加密消息本身，而是用于加密对称密钥，再由对称密钥加密实际的消息内容，这种混合加密体制兼顾了RSA的安全性和对称加密的高效性。
模幂运算的直接计算方式是对底数连续做e次乘法再取模，但当e很大时这种方
本篇完！