CnRSA算法实现说明与帮助

博主： samool
发布时间：2024 年 12 月 31 日
95 次浏览
暂无评论
12218字数
分类：搞软件 Delphi

                 CnPack For Delphi/C++Builder
                 中国人自己的免费第三方开发包
             (C)Copyright 2001-2024 CnPack 开发组

                    CnRSA算法实现说明与帮助
                       Revision 1.0.1.0
                   =========================
                    作者：刘啸 2024.11.02

======================================================================

CnRSA 介绍
CnRSA 是 CnPack 开放源码组件包中的一部分，是以纯 Delphi 代码实现的工程可用的 RSA 算法，支持从 Delphi 5 到最新版的所有版本的 Delphi，并兼容 OpenSSL。为了给用户一个完整的使用说明以及使用户在发现问题时能通过阅读 CnRSA 的代码解决问题，这里将 RSA 的算法说明以及 CnRSA 相关实现机制整理如下文。

======================================================================

RSA 算法说明
RSA 加密算法是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在 1977 年共同提出的一种非对称加密算法，目前在公开密钥加密和电子商业中被广泛使用。RSA 即为该三人姓名的首字母。
所谓非对称加密算法，是指加密与解密时使用的密钥不相同，能够避免对称加密算法所面临的密钥传递时的泄露危险。

2.1 如何以最简单的方式理解 RSA 加解密

先以通俗的算法描述来了解 RSA 算法。

选俩素数，算它们的积（叫做积一）。
算俩素数各减一的积（叫做积二）。
找一个和积二互素的数 E，一般就选 65537（有时候 3 也行）
再求个正数 D，要求 D 能满足（D * 65537） mod 积二 = 1
好了，我们得到了一对简单的 RSA 公私钥。其中公钥是积一和 65537，私钥是积一和 D。
得到了公私钥如何加解密呢？也很简单：
加密：原文数字的 65537 次方除以积一，余数就是密文
解密：密文数字的 D 次方除以积一，余数就是明文

2.1.1 不能实际使用的 RSA 例子一

如果上面仍不好理解，我们可以拿一个数字非常小因而并不能投入实际使用的简单例子来说明：

素数：5、11
积一：5 * 11 = 55
积二：(5 - 1) * (11 - 1) = 40
E：3
D：D * 3 mod 40 = 1，求得D = 27
我们得到公钥 55 和 3，私钥 55 和 27，假如我们的明文是 2，那么
加密：2 的 27 次方除以 55 = 134217728 mod 55 = 18，密文为 18
解密：18 的 3 次方除以 55 = 5832 mod 55 = 2，解出了明文 2。

2.1.2 不能实际使用的 RSA 例子二

上面的例子实在太简陋了，我们换一个数字稍微大一点的来看：

素数：1504629263、146270947
积一：220083547182922061
E：65537
求得 D = 122005207634220149
得到公钥 220083547182922061 和 65537，私钥 220083547182922061 和 122005207634220149。假如明文是 12345678987654321
加密得到密文：99815494076289543
解密得到明文：12345678987654321

2.2 为什么以上两个例子不能投入实际使用？

上面两个例子以最简单的方式说明了 RSA 算法的机制，但为什么这两个例子无法在实际应用中使用？答案很简单，积一的素数因子分解太容易了，55 = 5 * 11 一眼就能看出来，220083547182922061 = 1504629263 * 146270947 用计算机来计算也不难，因此我们根据公钥能够迅速猜到私钥，密文就能被直接解密了。
只有当两个素数非常大时，RSA 算法才有实际应用的意义。它所基于的数学原理就一句话：两个大素数相乘十分容易，但是想要对其乘积进行素数因子分解却极其困难。
为了演示，CnPack 组件包中的 CnRSA.pas 单元里也提供了 CnInt64RSA 实现类，它能够实现 Int64 范围内的 RSA 加解密。如上面所说，它的加解密强度相当弱，只能作为教学演示使用。

======================================================================

RSA 算法的工程实现
RSA 算法要在实际应用中使用，爱思考的读者们一定已经看出了至少有以下几个点：

3.1 RSA 算法投入实际使用所面临的必须解决的问题

要加大运算强度与破解难度，Int64 明显不够，需要非常的大整数运算支持。
很大的素数如何准确快速地寻找？我们熟知的筛法对于大素数寻找太慢了。
加解密的过程都需要进行大整数的高次幂求余运算，直接算极易溢出，一般机器跑不动。
生成公私钥时的 D 怎么求？
所幸的是，以上的第一个工程问题与后三个数学问题目前全都解决了，下面分别阐述。

3.2 大整数运算

大整数运算有不少开源库可以参考，如 GMP 库、JDK 中的 BigInteger 等。CnPack 组件包中参考 OpenSSL 中的 BN_ 大数库，在 CnBigNumber.pas 单元中实现了 TCnBigNumber 类，实现了大整数的常规四则运算、乘方开方、比较、位运算等功能。
一个 TCnBigNumber 代表一个没有明显上限的大整数，它内部用一个名为 Neg 的变量标记其正负，另用一可变长度的 UInt32 数组表示该大数的数值。该数组中，越靠近内存高位越代表大数的高位，UInt32 内部则依赖于 CPU 的大小端。在 x86 这种小端 CPU 上，一个 TCnBigNumber 的大数值，严格等于该数组经字节倒序后所表达的数。
UInt32 数组中的每个 UInt32 数组元素代表大数中的运算最小单元，类似于十进制里的每一位。两个大数相加减较易理解，对应数组元素加减即可，但要注意进位和借位的变化。乘法则按竖式乘法那样每个元素与对方相乘再相加，数值较大时可用 Karatsuba 算法加速。除法最为复杂，要模拟竖式除法里的试除并轮减求余数，并且 UInt32 的数组元素间的整除和求余运算其实涉及到 64 位的借位除法，在 32 位平台下涉及 DIV 等汇编指令（或使用系统封装的 _lludiv 汇编方法），因而效率较已经实现了 128 位借位除法的 64 位平台下略低。
另外，在复杂的运算中，经常需要临时生成大数对象作为中间运算的结果存储，而频繁创建及释放 TCnBigNumber 对象对运行效率影响较大，因而 CnBigNumber.pas 单元中也提供了大数池 TCnBigNumberPool 的机制，供运算过程中快速获取及回收大数对象，提升运行效率。
在 64 位系统上，一个 TCnBigNumber 的大数数值表示元素也可用 UInt64 代替，这样运算的拆分粒度较 UInt32 更大，更能有效利用 64 位 CPU 的运算能力，但该机制尚未经完整的严格测试因而默认未开放。如需要使用，可在头部找到 {$IFDEF CPU64BITS} 行，取消 {$DEFINE BN_DATA_USE_64} 的注释即可。

3.2 寻找大素数

RSA 每一对公私钥都离不开两个大素数，而大素数的寻找不能用常规的筛法，其时间复杂度太高无法忍受。譬如较为典型的埃拉托斯特尼筛法，其时间复杂度为 O(nlog(logn))，n 一大就跑不动了。
有不少数学家在大素数搜索这个领域进行了深入研究，目前效率较高的确定性大素数判定算法有 AKS 等，其时间复杂度在 O(log^12(n)) 到 O(log^6(n))，但仍然不够。
著名数学家费马提出的费马小定理衍生了一种素数判定算法，如果某个数不符合费马小定理，那么它一定是合数，但满足费马小定理的数偏偏还有不少卡迈克尔数不是素数，因而基于费马小定理的素数判定算法只能说是一种不确定的概率性算法，而且失败的概率不太可控。
后来数学家 Miller 和 Rabin 基于费马判定，终于研究出了目前较为通用的概率性的米勒-拉宾（Miller-Rabin）素性测试算法，该算法对一个大数进行多轮独立判定，每一轮判定通过的话，该大数便有一定概率是素数。如果某数通过了许多轮判定，那么它是合数的概率就会非常小，工程上可以近似认为它就是素数。
米勒-拉宾素性测试算法的时间复杂度是多项式级的，约 O(klog^3(n))，并且误判的概率可以通过判定的轮数来控制，是目前工程上通用的快速大素数发掘算法。CnBigNumber.pas 中也提供了该算法的实现 BigNumberIsProbablyPrime 函数，允许自定义轮数来针对一个大数做米勒-拉宾素性测试，默认是 50 轮。寻找指定长度的素数时，则先随机填充长度并就近取为一个奇数大数进行米勒-拉宾素性测试，如果没通过，则加 2 继续做，一般用不了多久就能找到一个大素数。
当然，RSA 算法里能够充当私钥的两个大素数还有一些其他安全要求，譬如两个素数的积要满足目标位数、两个素数的差的位数要大于积的位数的三分之一、其积的 NAF 形式要满足一定条件等，CnRSA.pas 中的 CnRSAGenerateKeys 方法里有其对应实现与约束。

3.2 蒙哥马利快速幂求余

RSA 加解密过程中要用到大数的求幂再求余操作，该操作不仅慢而且容易溢出，因而同样需要优化。目前典型的快速幂求余算法是蒙哥马利（Montgomery）快速幂求余算法，该算法可将大数的幂求余转换成积求余，再将积求余转换成和求余，不过后者在大数库中可以直接计算，再转的话反倒更慢了。
CnBigNumber.pas 中的 BigNumberPowerMod 是该算法的优化实现，加入了滑动窗口机制以提速，另还有 BigNumberPowerPowerMod 算法供简化幂幂求余的计算。

3.3 扩展欧几里得辗转相除法求 D

RSA 算法中求 D 实际上是解一个不定方程。解该方程可以用扩展欧几里德辗转相除法。CnBigNumber.pas 中分别实现了 BigNumberExtendedEuclideanGcd 与 BigNumberExtendedEuclideanGcd2 两个函数，可以分别用来求解二元一次不定方程 A * X + B * Y = 1 和 A * X - B * Y = 1 的一组可能的整数解。其中 A 和 B 是传入的已知系数，X 和 Y 则是解出的结果，调用者需自行保证 A 和 B 互素，否则结果不准确。如果解出的 X 小于 0，可用再加上 B 以满足实际使用的要求。

3.4 能实际使用的 RSA 例子

这里举一个用 CnRSA 生成并实现的 1024Bit 的 RSA 例子：

素数1：11795690727769166502699638182754409621456989841069533832409296669283539752710514527118625192440783910929318385366251930645685151242541471612896690908882923456354611372214569998798084210665759517540352249124683826216519450941427190839581034113979818949296421808888128229002101509923237360815392588526618623329
素数2：

41796933860949200670641741619002242706200884209800427754253948967485500817792149989487462921560747234453728927850855387841283613487237843749810167266874818386701456382226980435208447566858623992216821707365826319661759609660952845848248344717132880325137049426056929895980579645903534795006345618720672323903

私钥：

493023705192779595210145354685109032381675423245360416178769886612163990284348875671828035231858207098648425646220707837436431132668213677174682529367508918477166322056877775736729813634753876786035741510262055711504159365918297754773269440589944916358958356251028578635995752304389582201751807633999913547105822151847389558292350264276539573157158412151534508675407677679382724637583925191636337580097289205994468084262989724899881442817872960905702688082976843140262209457214252940923560528088923892710365238269097437794268515595342764640130947923874793568727740340900389930404581924472824917092620371109040133087
135809648745674199800551659186875709318192569324938456036671388116779781140475613050696728871335828810471947574518553467342720772053332644369356908352100927800605514626742366684089648985278724043186341173455618837599899126187085606099178070570369036956654640972272440455248658259473963219070530894252108568670123741636034469281039220462078765731342191652521431688864354969945295611074934753899645904014933858251338620621806232860404238483976297099160836127912880292330477076462999501920642080564286548567282027098415191128055260860093628449927525319005051929366532495686583229065742627467952309370633927463816745537

公钥：

输入明文 123456789098765432160987654321234567890

计算得到密文：

370761033836692845867876908686801249690501348545326198396750376307045398113322358066839178778435264575616327278764502560461230964491703721106607773979135199442894855382213278795836052552935514091663273554569294373201200736874888350373001927444818995774668351437275863963782001163681323154102543656763841655066052620792911166395441572020624608625297270763670162863103600728965900763109571233491420275859860131675836838619509708151209660156607343765129188413561502687349711359681330652057612549647531874481003031800795322394905021006554579157421282649620031479766125003843382414751938227385246262073569289334870480359

解密后的明文 123456789098765432160987654321234567890

======================================================================

RSA 的具体使用
非对称加密算法主要有两大应用场合：加密解密、签名验签。不光 RSA 如此，ECC 也如此。
以上的说明中，RSA 运算的明文均是以数字的方式参与运算的，但原始被处理的数据如何转换成数字及如何还原，这部分还涉及到填充与对齐。注意 RSA 加密时无法处理长度超过两个素数乘积（上文的积一、正式名称为 Modulus）位长度的数据，这一点和那些能够分组无限长加密的对称加密算法不同。虽然 RSA 理论上也可以将超长数据分成一块块后，像分组加密算法一样逐块加密，但因为 RSA 的计算效率远低于分组对称加密，因而这种分块机制可行性较弱，并没有通用规范规定如何做。填充对齐的规则由 RFC 文档规范说明。
另外，RSA 的公私钥也涉及到传递、保存、加载，目前 CnPack 组件包内实现了 PEM 格式的兼容处理，该格式使用 BER/DER 方式的编码将公私钥等关键信息存储在树状结构中，并将树状结构输出成二进制再 Base64 编码。而且 PEM 格式还支持用指定密码进行对称加密，以避免私钥文件丢失导致泄密。

4.1 填充与对齐

RSA 加解密使用的是 PKCS1 对齐填充方式，该方式会将一段数据填充至指定字节长度，如果原有数据长度太长则出错，填充失败。PKCS1 又分三种填充类型，分别是 Private 00、Private FF、Public Random三种。RSA 私钥加密数据时使用 Private FF 类型的 PKCS1 填充，公钥加密数据时使用 Public Random 类型的 PKCS1 填充。目的都是在原始数据前面加上“0、填充类型、填充内容、0”四部分数据凑成等于 RSA 两个素数乘积位长度的固定长度，而且第一个字节 0 确保该数值确定小于 Modulus。注意公钥加密数据时填充使用了随机内容，因此相同公钥针对相同数据加密，每次结果会不同。

4.2 加密与解密

CnRSA.pas 单元使用 TCnRSAPrivateKey 与 TCnRSAPublicKey 两个类来容纳一对 RSA 公私钥，公私钥可以通过 CnRSAGenerateKeys 函数生成，或通过 CnRSALoadKeysFromPem 从 OpenSSL 生成的密钥文件中载入（支持部分算法的密码加密的 PEM 格式），也可以通过 CnRSASaveKeysToPem 函数保存至 PEM 格式的密钥文件（支持部分指定对称加密算法的密码加密）。
CnRSAEncryptData 与 CnRSAEncryptFile 函数能够分别使用公私钥对文件或数据加密，CnRSADecryptData 与 CnRSADecryptFile 函数能够分别使用公私钥解密数据或文件。这批函数内部均实现了 RFC 规定的填充与对齐的添加与去除，兼容 OpenSSL。

4.3 签名与验签

RSA 算法一般用私钥签名、公钥验证签名。RSA 针对文件的签名也分两种：指定 Hash 算法的与不指定 Hash 算法的。不指定 Hash 算法时，RSA 签名的机制是直接将原始文件来个 Private FF 类型的 PKCS1 填充，然后私钥加密，保存成签名文件。指定 Hash 算法时，先用指定的 Hash 算法算出原始文件的 Hash 值，再以 BER 格式拼上一些说明信息如使用了哪种 Hash 算法等，再来个 Private FF 类型的 PKCS1 填充，然后同样私钥加密，保存成签名文件。
验证签名时则用公钥将签名文件解密并去除 PKCS1 对齐内容，如果知道是无 Hash 算法的签名，直接比对原始文件与解密文件即可，对不上就是验签失败。如果知道是有 Hash 算法的，则按 BER 格式解开解密文件中的 Hash 算法与 Hash 值，然后按指定 Hash 算法计算原始文件的 Hash 值和解密文件中的 Hash 值对比，相同则验签成功。
无 Hash 算法的 RSA 签名除对齐方式不同外，本质上类似于私钥加密，因而同样有无法处理过长数据的问题。对于过长数据，指定 Hash 算法的 RSA 签名几乎是唯一的选择。Hash 算法能针对任意长的数据生成长度较短且固定的摘要值供 RSA 私钥加密。如果有恶意用户更改了原始数据，按 Hash 算法的特性无法生成同样的摘要，而如果用新摘要重新生成新签名，又需 RSA 私钥重新加密，因而只要 RSA 私钥保密了，这类 Hash 后再 RSA 的签名验证机制便没有明显漏洞，是目前与椭圆曲线签名同样流行的数据防篡改机制。
该签名与验证签名的功能同样兼容 OpenSSL。

======================================================================

例子与帮助
CnRSA 的详细例子可见 cnvcl/Example/VCL/RSA 目录。例子的第二个 Tab “Big Number RSA”是 CnRSA 的核心内容，公私钥的生成、保存、加载以及文件的加密解密验证签名均在其中演示。CnRSA.pas 源码中也有对各类以及各方法的详细说明可供参考。

======================================================================

联系我们
开发网站：https://www.cnpack.org
开发论坛：https://bbs.cnpack.org
管理员信箱：master@cnpack.org
源码：https://github.com/cnpack

最后修改：2024 年 12 月 31 日

一分也是爱

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址 *

CnRSA算法实现说明与帮助

samool • 2024 年 12 月 31 日

<hr><pre><code>                 CnPack For Delphi/C++Builder
                 中国人自己的免费第三方开发包
             (C)Copyright 2001-2024 CnPack 开发组</code></pre><hr><pre><code>                    CnRSA算法实现说明与帮助
                       Revision 1.0.1.0
                   =========================
                    作者：刘啸 2024.11.02

</code></pre><p>======================================================================</p><ol><li><h1>CnRSA 介绍</h1><p>CnRSA 是 CnPack 开放源码组件包中的一部分，是以纯 Delphi 代码实现的工程可用的 RSA 算法，支持从 Delphi 5 到最新版的所有版本的 Delphi，并兼容 OpenSSL。为了给用户一个完整的使用说明以及使用户在发现问题时能通过阅读 CnRSA 的代码解决问题，这里将 RSA 的算法说明以及 CnRSA 相关实现机制整理如下文。</p></li></ol><p>======================================================================</p><ol start="2"><li><h1>RSA 算法说明</h1><p>RSA 加密算法是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在 1977 年共同提出的一种非对称加密算法，目前在公开密钥加密和电子商业中被广泛使用。RSA 即为该三人姓名的首字母。<br> 所谓非对称加密算法，是指加密与解密时使用的密钥不相同，能够避免对称加密算法所面临的密钥传递时的泄露危险。</p></li></ol><hr><h2>2.1 如何以最简单的方式理解 RSA 加解密</h2><pre><code>先以通俗的算法描述来了解 RSA 算法。
</code></pre><ul><li>选俩素数，算它们的积（叫做积一）。</li><li>算俩素数各减一的积（叫做积二）。</li><li>找一个和积二互素的数 E，一般就选 65537（有时候 3 也行）</li><li><p>再求个正数 D，要求 D 能满足 （D * 65537） mod 积二 = 1</p><p>好了，我们得到了一对简单的 RSA 公私钥。其中公钥是积一和 65537，私钥是积一和 D。<br>得到了公私钥如何加解密呢？也很简单：</p></li><li>加密：原文数字的 65537 次方除以积一，余数就是密文</li><li>解密：密文数字的 D 次方除以积一，余数就是明文</li></ul><h2>2.1.1 不能实际使用的 RSA 例子一</h2><pre><code>如果上面仍不好理解，我们可以拿一个数字非常小因而并不能投入实际使用的简单例子来说明：
</code></pre><ul><li>素数：5、11</li><li>积一：5 * 11 = 55</li><li>积二：(5 - 1) * (11 - 1) = 40</li><li>E：3</li><li><p>D：D * 3 mod 40 = 1，求得D = 27</p><p>我们得到公钥 55 和 3，私钥 55 和 27，假如我们的明文是 2，那么</p></li><li>加密：2 的 27 次方除以 55 = 134217728 mod 55 = 18，密文为 18</li><li>解密：18 的 3 次方除以 55 = 5832 mod 55 = 2，解出了明文 2。</li></ul><h2>2.1.2 不能实际使用的 RSA 例子二</h2><pre><code>上面的例子实在太简陋了，我们换一个数字稍微大一点的来看：
</code></pre><ul><li>素数：1504629263、146270947</li><li>积一：220083547182922061</li><li>E：65537</li><li><p>求得 D = 122005207634220149</p><p>得到公钥 220083547182922061 和 65537，私钥 220083547182922061 和 122005207634220149。假如明文是 12345678987654321</p></li><li>加密得到密文：99815494076289543</li><li>解密得到明文：12345678987654321</li></ul><hr><h2>2.2 为什么以上两个例子不能投入实际使用？</h2><pre><code>上面两个例子以最简单的方式说明了 RSA 算法的机制，但为什么这两个例子无法在实际应用中使用？答案很简单，积一的素数因子分解太容易了，55 = 5 * 11 一眼就能看出来，220083547182922061 = 1504629263 * 146270947 用计算机来计算也不难，因此我们根据公钥能够迅速猜到私钥，密文就能被直接解密了。
只有当两个素数非常大时，RSA 算法才有实际应用的意义。它所基于的数学原理就一句话：两个大素数相乘十分容易，但是想要对其乘积进行素数因子分解却极其困难。
为了演示，CnPack 组件包中的 CnRSA.pas 单元里也提供了 CnInt64RSA 实现类，它能够实现 Int64 范围内的 RSA 加解密。如上面所说，它的加解密强度相当弱，只能作为教学演示使用。
</code></pre><p>======================================================================</p><ol start="3"><li><h1>RSA 算法的工程实现</h1><p>RSA 算法要在实际应用中使用，爱思考的读者们一定已经看出了至少有以下几个点：</p></li></ol><hr><h2>3.1 RSA 算法投入实际使用所面临的必须解决的问题</h2><ul><li>要加大运算强度与破解难度，Int64 明显不够，需要非常的大整数运算支持。</li><li>很大的素数如何准确快速地寻找？我们熟知的筛法对于大素数寻找太慢了。</li><li>加解密的过程都需要进行大整数的高次幂求余运算，直接算极易溢出，一般机器跑不动。</li><li><p>生成公私钥时的 D 怎么求？</p><p>所幸的是，以上的第一个工程问题与后三个数学问题目前全都解决了，下面分别阐述。</p></li></ul><hr><h2>3.2 大整数运算</h2><pre><code>大整数运算有不少开源库可以参考，如 GMP 库、JDK 中的 BigInteger 等。CnPack 组件包中参考 OpenSSL 中的 BN_ 大数库，在 CnBigNumber.pas 单元中实现了 TCnBigNumber 类，实现了大整数的常规四则运算、乘方开方、比较、位运算等功能。
一个 TCnBigNumber 代表一个没有明显上限的大整数，它内部用一个名为 Neg 的变量标记其正负，另用一可变长度的 UInt32 数组表示该大数的数值。该数组中，越靠近内存高位越代表大数的高位，UInt32 内部则依赖于 CPU 的大小端。在 x86 这种小端 CPU 上，一个 TCnBigNumber 的大数值，严格等于该数组经字节倒序后所表达的数。
UInt32 数组中的每个 UInt32 数组元素代表大数中的运算最小单元，类似于十进制里的每一位。两个大数相加减较易理解，对应数组元素加减即可，但要注意进位和借位的变化。乘法则按竖式乘法那样每个元素与对方相乘再相加，数值较大时可用 Karatsuba 算法加速。除法最为复杂，要模拟竖式除法里的试除并轮减求余数，并且 UInt32 的数组元素间的整除和求余运算其实涉及到 64 位的借位除法，在 32 位平台下涉及 DIV 等汇编指令（或使用系统封装的 _lludiv 汇编方法），因而效率较已经实现了 128 位借位除法的 64 位平台下略低。
另外，在复杂的运算中，经常需要临时生成大数对象作为中间运算的结果存储，而频繁创建及释放 TCnBigNumber 对象对运行效率影响较大，因而 CnBigNumber.pas 单元中也提供了大数池 TCnBigNumberPool 的机制，供运算过程中快速获取及回收大数对象，提升运行效率。
在 64 位系统上，一个 TCnBigNumber 的大数数值表示元素也可用 UInt64 代替，这样运算的拆分粒度较 UInt32 更大，更能有效利用 64 位 CPU 的运算能力，但该机制尚未经完整的严格测试因而默认未开放。如需要使用，可在头部找到 {$IFDEF CPU64BITS} 行，取消 {$DEFINE BN_DATA_USE_64} 的注释即可。
</code></pre><hr><h2>3.2 寻找大素数</h2><pre><code>RSA 每一对公私钥都离不开两个大素数，而大素数的寻找不能用常规的筛法，其时间复杂度太高无法忍受。譬如较为典型的埃拉托斯特尼筛法，其时间复杂度为 O(nlog(logn))，n 一大就跑不动了。
有不少数学家在大素数搜索这个领域进行了深入研究，目前效率较高的确定性大素数判定算法有 AKS 等，其时间复杂度在 O(log^12(n)) 到 O(log^6(n))，但仍然不够。
著名数学家费马提出的费马小定理衍生了一种素数判定算法，如果某个数不符合费马小定理，那么它一定是合数，但满足费马小定理的数偏偏还有不少卡迈克尔数不是素数，因而基于费马小定理的素数判定算法只能说是一种不确定的概率性算法，而且失败的概率不太可控。
后来数学家 Miller 和 Rabin 基于费马判定，终于研究出了目前较为通用的概率性的米勒-拉宾（Miller-Rabin）素性测试算法，该算法对一个大数进行多轮独立判定，每一轮判定通过的话，该大数便有一定概率是素数。如果某数通过了许多轮判定，那么它是合数的概率就会非常小，工程上可以近似认为它就是素数。
米勒-拉宾素性测试算法的时间复杂度是多项式级的，约 O(klog^3(n))，并且误判的概率可以通过判定的轮数来控制，是目前工程上通用的快速大素数发掘算法。CnBigNumber.pas 中也提供了该算法的实现 BigNumberIsProbablyPrime 函数，允许自定义轮数来针对一个大数做米勒-拉宾素性测试，默认是 50 轮。寻找指定长度的素数时，则先随机填充长度并就近取为一个奇数大数进行米勒-拉宾素性测试，如果没通过，则加 2 继续做，一般用不了多久就能找到一个大素数。
当然，RSA 算法里能够充当私钥的两个大素数还有一些其他安全要求，譬如两个素数的积要满足目标位数、两个素数的差的位数要大于积的位数的三分之一、其积的 NAF 形式要满足一定条件等，CnRSA.pas 中的 CnRSAGenerateKeys 方法里有其对应实现与约束。
</code></pre><hr><h2>3.2 蒙哥马利快速幂求余</h2><pre><code>RSA 加解密过程中要用到大数的求幂再求余操作，该操作不仅慢而且容易溢出，因而同样需要优化。目前典型的快速幂求余算法是蒙哥马利（Montgomery）快速幂求余算法，该算法可将大数的幂求余转换成积求余，再将积求余转换成和求余，不过后者在大数库中可以直接计算，再转的话反倒更慢了。
CnBigNumber.pas 中的 BigNumberPowerMod 是该算法的优化实现，加入了滑动窗口机制以提速，另还有 BigNumberPowerPowerMod 算法供简化幂幂求余的计算。
</code></pre><hr><h2>3.3 扩展欧几里得辗转相除法求 D</h2><pre><code>RSA 算法中求 D 实际上是解一个不定方程。解该方程可以用扩展欧几里德辗转相除法。CnBigNumber.pas 中分别实现了 BigNumberExtendedEuclideanGcd 与 BigNumberExtendedEuclideanGcd2 两个函数，可以分别用来求解二元一次不定方程 A * X + B * Y = 1 和 A * X - B * Y = 1 的一组可能的整数解。其中 A 和 B 是传入的已知系数，X 和 Y 则是解出的结果，调用者需自行保证 A 和 B 互素，否则结果不准确。如果解出的 X 小于 0，可用再加上 B 以满足实际使用的要求。
</code></pre><hr><h2>3.4 能实际使用的 RSA 例子</h2><pre><code>这里举一个用 CnRSA 生成并实现的 1024Bit 的 RSA 例子：
</code></pre><ul><li>素数1：11795690727769166502699638182754409621456989841069533832409296669283539752710514527118625192440783910929318385366251930645685151242541471612896690908882923456354611372214569998798084210665759517540352249124683826216519450941427190839581034113979818949296421808888128229002101509923237360815392588526618623329</li><li>素数2：</li></ul><p>41796933860949200670641741619002242706200884209800427754253948967485500817792149989487462921560747234453728927850855387841283613487237843749810167266874818386701456382226980435208447566858623992216821707365826319661759609660952845848248344717132880325137049426056929895980579645903534795006345618720672323903</p><ul><li>私钥：</li></ul><p>493023705192779595210145354685109032381675423245360416178769886612163990284348875671828035231858207098648425646220707837436431132668213677174682529367508918477166322056877775736729813634753876786035741510262055711504159365918297754773269440589944916358958356251028578635995752304389582201751807633999913547105822151847389558292350264276539573157158412151534508675407677679382724637583925191636337580097289205994468084262989724899881442817872960905702688082976843140262209457214252940923560528088923892710365238269097437794268515595342764640130947923874793568727740340900389930404581924472824917092620371109040133087<br>135809648745674199800551659186875709318192569324938456036671388116779781140475613050696728871335828810471947574518553467342720772053332644369356908352100927800605514626742366684089648985278724043186341173455618837599899126187085606099178070570369036956654640972272440455248658259473963219070530894252108568670123741636034469281039220462078765731342191652521431688864354969945295611074934753899645904014933858251338620621806232860404238483976297099160836127912880292330477076462999501920642080564286548567282027098415191128055260860093628449927525319005051929366532495686583229065742627467952309370633927463816745537</p><ul><li>公钥：</li></ul><p>493023705192779595210145354685109032381675423245360416178769886612163990284348875671828035231858207098648425646220707837436431132668213677174682529367508918477166322056877775736729813634753876786035741510262055711504159365918297754773269440589944916358958356251028578635995752304389582201751807633999913547105822151847389558292350264276539573157158412151534508675407677679382724637583925191636337580097289205994468084262989724899881442817872960905702688082976843140262209457214252940923560528088923892710365238269097437794268515595342764640130947923874793568727740340900389930404581924472824917092620371109040133087<br>65537</p><pre><code>输入明文 123456789098765432160987654321234567890

计算得到密文：</code></pre><p>370761033836692845867876908686801249690501348545326198396750376307045398113322358066839178778435264575616327278764502560461230964491703721106607773979135199442894855382213278795836052552935514091663273554569294373201200736874888350373001927444818995774668351437275863963782001163681323154102543656763841655066052620792911166395441572020624608625297270763670162863103600728965900763109571233491420275859860131675836838619509708151209660156607343765129188413561502687349711359681330652057612549647531874481003031800795322394905021006554579157421282649620031479766125003843382414751938227385246262073569289334870480359</p><pre><code>解密后的明文 123456789098765432160987654321234567890
</code></pre><p>======================================================================</p><ol start="4"><li><h1>RSA 的具体使用</h1><p>非对称加密算法主要有两大应用场合：加密解密、签名验签。不光 RSA 如此，ECC 也如此。<br> 以上的说明中，RSA 运算的明文均是以数字的方式参与运算的，但原始被处理的数据如何转换成数字及如何还原，这部分还涉及到填充与对齐。注意 RSA 加密时无法处理长度超过两个素数乘积（上文的积一、正式名称为 Modulus）位长度的数据，这一点和那些能够分组无限长加密的对称加密算法不同。虽然 RSA 理论上也可以将超长数据分成一块块后，像分组加密算法一样逐块加密，但因为 RSA 的计算效率远低于分组对称加密，因而这种分块机制可行性较弱，并没有通用规范规定如何做。填充对齐的规则由 RFC 文档规范说明。<br> 另外，RSA 的公私钥也涉及到传递、保存、加载，目前 CnPack 组件包内实现了 PEM 格式的兼容处理，该格式使用 BER/DER 方式的编码将公私钥等关键信息存储在树状结构中，并将树状结构输出成二进制再 Base64 编码。而且 PEM 格式还支持用指定密码进行对称加密，以避免私钥文件丢失导致泄密。</p></li></ol><hr><h2>4.1 填充与对齐</h2><pre><code>RSA 加解密使用的是 PKCS1 对齐填充方式，该方式会将一段数据填充至指定字节长度，如果原有数据长度太长则出错，填充失败。PKCS1 又分三种填充类型，分别是 Private 00、Private FF、Public Random三种。RSA 私钥加密数据时使用 Private FF 类型的 PKCS1 填充，公钥加密数据时使用 Public Random 类型的 PKCS1 填充。目的都是在原始数据前面加上“0、填充类型、填充内容、0”四部分数据凑成等于 RSA 两个素数乘积位长度的固定长度，而且第一个字节 0 确保该数值确定小于 Modulus。注意公钥加密数据时填充使用了随机内容，因此相同公钥针对相同数据加密，每次结果会不同。
</code></pre><hr><h2>4.2 加密与解密</h2><pre><code>CnRSA.pas 单元使用 TCnRSAPrivateKey 与 TCnRSAPublicKey 两个类来容纳一对 RSA 公私钥，公私钥可以通过 CnRSAGenerateKeys 函数生成，或通过 CnRSALoadKeysFromPem 从 OpenSSL 生成的密钥文件中载入（支持部分算法的密码加密的 PEM 格式），也可以通过 CnRSASaveKeysToPem 函数保存至 PEM 格式的密钥文件（支持部分指定对称加密算法的密码加密）。
CnRSAEncryptData 与 CnRSAEncryptFile 函数能够分别使用公私钥对文件或数据加密，CnRSADecryptData 与 CnRSADecryptFile 函数能够分别使用公私钥解密数据或文件。这批函数内部均实现了 RFC 规定的填充与对齐的添加与去除，兼容 OpenSSL。
</code></pre><hr><h2>4.3 签名与验签</h2><pre><code>RSA 算法一般用私钥签名、公钥验证签名。RSA 针对文件的签名也分两种：指定 Hash 算法的与不指定 Hash 算法的。不指定 Hash 算法时，RSA 签名的机制是直接将原始文件来个 Private FF 类型的 PKCS1 填充，然后私钥加密，保存成签名文件。指定 Hash 算法时，先用指定的 Hash 算法算出原始文件的 Hash 值，再以 BER 格式拼上一些说明信息如使用了哪种 Hash 算法等，再来个 Private FF 类型的 PKCS1 填充，然后同样私钥加密，保存成签名文件。
验证签名时则用公钥将签名文件解密并去除 PKCS1 对齐内容，如果知道是无 Hash 算法的签名，直接比对原始文件与解密文件即可，对不上就是验签失败。如果知道是有 Hash 算法的，则按 BER 格式解开解密文件中的 Hash 算法与 Hash 值，然后按指定 Hash 算法计算原始文件的 Hash 值和解密文件中的 Hash 值对比，相同则验签成功。
无 Hash 算法的 RSA 签名除对齐方式不同外，本质上类似于私钥加密，因而同样有无法处理过长数据的问题。对于过长数据，指定 Hash 算法的 RSA 签名几乎是唯一的选择。Hash 算法能针对任意长的数据生成长度较短且固定的摘要值供 RSA 私钥加密。如果有恶意用户更改了原始数据，按 Hash 算法的特性无法生成同样的摘要，而如果用新摘要重新生成新签名，又需 RSA 私钥重新加密，因而只要 RSA 私钥保密了，这类 Hash 后再 RSA 的签名验证机制便没有明显漏洞，是目前与椭圆曲线签名同样流行的数据防篡改机制。
该签名与验证签名的功能同样兼容 OpenSSL。
</code></pre><p>======================================================================</p><ol start="4"><li><h1>例子与帮助</h1><p>CnRSA 的详细例子可见 cnvcl/Example/VCL/RSA 目录。例子的第二个 Tab “Big Number RSA”是 CnRSA 的核心内容，公私钥的生成、保存、加载以及文件的加密解密验证签名均在其中演示。CnRSA.pas 源码中也有对各类以及各方法的详细说明可供参考。</p></li></ol><p>======================================================================</p><ol start="5"><li><h1>联系我们</h1><p>开发网站：<span class="external-link"><a class="no-external-link" href="https://www.cnpack.org" target="_blank"><i data-feather="external-link"></i>https://www.cnpack.org</a></span><br> 开发论坛：<span class="external-link"><a class="no-external-link" href="https://bbs.cnpack.org" target="_blank"><i data-feather="external-link"></i>https://bbs.cnpack.org</a></span><br> 管理员信箱：<a href="mailto:master@cnpack.org">master@cnpack.org</a><br> 源码：<span class="external-link"><a class="no-external-link" href="https://github.com/cnpack" target="_blank"><i data-feather="external-link"></i>https://github.com/cnpack</a></span></p></li></ol>

CnRSA算法实现说明与帮助

CnRSA 介绍

RSA 算法说明

2.1 如何以最简单的方式理解 RSA 加解密

2.1.1 不能实际使用的 RSA 例子一

2.1.2 不能实际使用的 RSA 例子二

2.2 为什么以上两个例子不能投入实际使用？

RSA 算法的工程实现

3.1 RSA 算法投入实际使用所面临的必须解决的问题

3.2 大整数运算

3.2 寻找大素数

3.2 蒙哥马利快速幂求余

3.3 扩展欧几里得辗转相除法求 D

3.4 能实际使用的 RSA 例子

RSA 的具体使用

4.1 填充与对齐

4.2 加密与解密

4.3 签名与验签

例子与帮助

联系我们

相关文章

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

设置WebBrowser的Referrer值

《Stanley博士的家》高智商游戏

TVB经典台庆剧·《寻秦记》OST原声音乐专集下载

开创Web安全新时代趋势进入"云安全"

今天是我的大喜日子

《Google Adsense的秘密》第八章：内容建设

山寨版鸟巢

SQL在结果集中进行查询

傻猫讲故事之“沙河浮起来的男尸”

delphi 字符串与内存流和文件的快速转换函数

CnRSA算法实现说明与帮助

CnRSA 介绍

RSA 算法说明

2.1 如何以最简单的方式理解 RSA 加解密

2.1.1 不能实际使用的 RSA 例子一

2.1.2 不能实际使用的 RSA 例子二

2.2 为什么以上两个例子不能投入实际使用？

RSA 算法的工程实现

3.1 RSA 算法投入实际使用所面临的必须解决的问题

3.2 大整数运算

3.2 寻找大素数

3.2 蒙哥马利快速幂求余

3.3 扩展欧几里得辗转相除法求 D

3.4 能实际使用的 RSA 例子

RSA 的具体使用

4.1 填充与对齐

4.2 加密与解密

4.3 签名与验签

例子与帮助

联系我们

相关文章

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

CnRSA算法实现说明与帮助

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款