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

======================================================================
1. CnRSA 介绍
======================================================================

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

======================================================================
2. 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 加解密。如上面所说，它的加解密强度相当弱，只能作为教学演示
使用。

======================================================================
3. RSA 算法的工程实现
======================================================================

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

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

  * 要加大运算强度与破解难度，Int64 明显不够，需要非常的大整数运算支持。
  * 很大的素数如何准确快速地寻找？我们熟知的筛法对于大素数寻找太慢了。
  * 加解密的过程都需要进行大整数的高次幂求余运算，直接算极易溢出，一般机器跑不动。
  * 生成公私钥时的 D 怎么求？

    所幸的是，以上的第一个工程问题与后三个数学问题目前全都解决了，下面分别阐述。

--------------
3.2 大整数运算
--------------

    大整数运算有不少开源库可以参考，如 GMP 库等。CnPack 组件包中参考 OpenSSL 中的
BN_ 大数库，在 CnBigNumber.pas 单元中实现了 TCnBigNumber 类，实现了大整数的常规四
则运算、乘方开方、比较等功能。

--------------
3.2 寻找大素数
--------------

    大素数的寻找不能用常规的筛法，其时间复杂度太高无法忍受。
    有不少数学家在大素数搜索这个领域进行了深入研究，目前效率较高的确定性大素数判定
算法有 AKS 等，但仍然不够。
    著名数学家费马提出的费马小定理衍生了一种素数判定算法，如果某个数不符合费马小定
理，那么它一定是合数，但满足费马小定理的数偏偏还有不少卡迈克尔数不是素数，因而基于
费马小定理的素数判定算法只能说是一种不确定的概率性算法，而且失败的概率不太可控。
    后来数学家 Miller 和 Rabin 基于费马判定研究出了目前较为通用的概率性的米勒-拉宾
（Miller-Rabin）素性测试算法，该算法对一个大数进行多轮独立判定，每一轮判定通过的话，
该大数便有一定概率是素数。如果某数通过了许多轮判定，那么它是合数的概率就会非常小，
工程里可以近似认为它就是素数。
    米勒-拉宾素性测试算法的时间复杂度是多项式级的，并且误判的概率可以通过判定的轮数
来控制，是目前工程上通用的快速大素数发掘算法。CnBigNumber.pas 中也提供了该算法的实
现 BigNumberIsProbablyPrime 函数，允许自定义轮数来针对一个大数做米勒-拉宾素性测试，
默认是 50 轮。

----------------------
3.2 蒙哥马利快速幂求余
----------------------

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

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

    RSA 算法中求 D 实际上是解一个不定方程。解该方程可以用扩展欧几里德辗转相除法。
CnBigNumber.pas 中分别实现了 BigNumberExtendedEuclideanGcd 与
BigNumberExtendedEuclideanGcd2 两个函数，可以分别用来求解二元一次不定方程
A * X + B * Y = 1 和 A * X - B * Y = 1 的整数解。

-------------------------
3.4 能实际使用的 RSA 例子
-------------------------

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

  * 质数1：1179569072776916650269963818275440962145698984106953383240929666928353
  9752710514527118625192440783910929318385366251930645685151242541471612896690908
  8829234563546113722145699987980842106657595175403522491246838262165194509414271
  90839581034113979818949296421808888128229002101509923237360815392588526618623329

  * 质数2：4179693386094920067064174161900224270620088420980042775425394896748550
  0817792149989487462921560747234453728927850855387841283613487237843749810167266
  8748183867014563822269804352084475668586239922168217073658263196617596096609528
  45848248344717132880325137049426056929895980579645903534795006345618720672323903

  * 私钥：49302370519277959521014535468510903238167542324536041617876988661216399
  0284348875671828035231858207098648425646220707837436431132668213677174682529367
  5089184771663220568777757367298136347538767860357415102620557115041593659182977
  5477326944058994491635895835625102857863599575230438958220175180763399991354710
  5822151847389558292350264276539573157158412151534508675407677679382724637583925
  1916363375800972892059944680842629897248998814428178729609057026880829768431402
  6220945721425294092356052808892389271036523826909743779426851559534276464013094
  7923874793568727740340900389930404581924472824917092620371109040133087
  和
  1358096487456741998005516591868757093181925693249384560366713881167797811404756
  1305069672887133582881047194757451855346734272077205333264436935690835210092780
  0605514626742366684089648985278724043186341173455618837599899126187085606099178
  0705703690369566546409722724404552486582594739632190705308942521085686701237416
  3603446928103922046207876573134219165252143168886435496994529561107493475389964
  5904014933858251338620621806232860404238483976297099160836127912880292330477076
  4629995019206420805642865485672820270984151911280552608600936284499275253190050
  51929366532495686583229065742627467952309370633927463816745537

  * 公钥：49302370519277959521014535468510903238167542324536041617876988661216399
  0284348875671828035231858207098648425646220707837436431132668213677174682529367
  5089184771663220568777757367298136347538767860357415102620557115041593659182977
  5477326944058994491635895835625102857863599575230438958220175180763399991354710
  5822151847389558292350264276539573157158412151534508675407677679382724637583925
  1916363375800972892059944680842629897248998814428178729609057026880829768431402
  6220945721425294092356052808892389271036523826909743779426851559534276464013094
  7923874793568727740340900389930404581924472824917092620371109040133087
  和
  65537

    输入明文 123456789098765432160987654321234567890
    计算得到密文：370761033836692845867876908686801249690501348545326198396750376
    30704539811332235806683917877843526457561632727876450256046123096449170372110
    66077739791351994428948553822132787958360525529355140916632735545692943732012
    00736874888350373001927444818995774668351437275863963782001163681323154102543
    65676384165506605262079291116639544157202062460862529727076367016286310360072
    89659007631095712334914202758598601316758368386195097081512096601566073437651
    29188413561502687349711359681330652057612549647531874481003031800795322394905
    02100655457915742128264962003147976612500384338241475193822738524626207356928
    9334870480359
    解密后的明文 123456789098765432160987654321234567890

======================================================================
4. RSA 的具体使用
======================================================================

    非对称加密算法主要有两大应用场合：加密解密、签名验签。不光 RSA 如此，ECC 也如此。
    以上的说明中，RSA 运算的明文均是以数字的方式参与运算的，但原始被处理的数据如何
转换成数字，这部分还涉及到填充与对齐。注意 RSA 加密时无法处理长度超过两个素数乘积位
长度（称为 Modulus）的数据，这一点和那些能够分组无限长加密的对称加密算法不同。填充
对齐的规则由 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 两个素数乘积位长度的固定长度。注意公
钥加密数据时填充使用了随机内容，因此相同公钥针对相同数据加密，每次结果会不同。
    
--------------
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 值对比，相同则验签成功。
    该签名与验证签名的功能同样兼容 OpenSSL。

======================================================================
4. 例子与帮助
======================================================================

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

======================================================================
5. 联系我们
======================================================================

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