商用密码技术最佳实践白皮书

密码算法库是操作系统的基础组件,在系统安全领域的作用不言而喻。操作系统默认已经内置了大量的密码学库,比如OpenSSL,libgcrypt,gnulib,nettle 是被默认集成到基础操作系统的,它们有一些重复的功能,但也各有侧重的领域,是操作系统不可或缺的安全基石。

本小节会介绍一些支持国密算法的、非常主流的密码算法库,提供给开发者和用户更多的选择。

OpenSSL

官网:https://www.openssl.org

OpenSSL 是一个通用的、强大的、商业级的、功能齐全的工具包,用于通用加密和安全通信。

OpenSSL 的重要性众所周知,这里重点强调一下版本问题。

🟢 1.1.1 稳定版

目前主流发行版使用的仍然是 1.1.1 版本,这个版本在国密的支持上有一些固有的缺陷:

  • 不支持 SM2 的签名验签,因为基于可辨别用户ID的Za值计算在这个版本中未实现
  • 国外主流的发行版的包默认没有编译国密 SM2、SM4 模块,CentOS上就是如此

由于技术上和兼容性的原因,这个版本目前很难升级到最新的社区版本,因此在主流的发行版本中基本是无缘使用国密的。

🟢 3.0.x 稳定版

社区最新的稳定版本是 3.0,这个版本对国密的支持已经比较完善,并且支持了国密的指令集优化。用户如果自行编译可以完整使能国密的能力。

🟢 龙蜥社区 1.1.1 版本

从目前情况来看,对于一个操作系统发行版,要完全从 1.1.1 切换到 3.0 还需要较长的时间,因此龙蜥社区在 1.1.1 版本的基础上,在保证兼容性和稳定性的前提下,补全了国密能力上的缺陷,并且做为操作系统默认库在 Anolis OS 8.8 中集成发布,详细信息可参考Anolis OS 国密开发指南

libgcrypt

官网:https://www.gnupg.org/software/libgcrypt/index.html

不像 OpenSSL 还包括了安全协议,libgcrypt 是一个纯粹的密码算法库,就国密算法的性能来说,libgcrypt 的国密算法优化是做的比较充分的,Linux 内核国密算法的部分优化也是先在 libgcrypt 实现后才移植到内核的。

Libgcrypt 是一个通用密码库,最初基于 GnuPG 的代码。 它为几乎所有的密码提供支持:

  • 对称密码算法 (AES、Arcfour、Blowfish、Camellia、CAST5、ChaCha20 DES、GOST28147、Salsa20、SEED、Serpent、Twofish、SM4)
  • 模式 (ECB、CFB、CBC、OFB、CTR、CCM) ,GCM,OCB,POLY1305,AESWRAP)
  • 哈希算法 (MD2, MD4, MD5, GOST R 34.11, RIPE-MD160, SHA-1, SHA2-224, SHA2-256, SHA2-384, SHA2-512, SHA3-224 , SHA3-256, SHA3-384, SHA3-512, SHAKE-128, SHAKE-256, TIGER-192, Whirlpool, SM3)
  • MAC (HMAC 用于所有哈希算法, CMAC 用于所有密码算法, GMAC-AES, GMAC-CAMELLIA, GMAC-TWOFISH、GMAC-SERPENT、GMAC-SEED、Poly1305、Poly1305-AES、Poly1305-CAMELLIA、Poly1305-TWOFISH、Poly1305-SERPENT、Poly1305-SEED)
  • 公钥算法 (RSA、Elgamal、DSA、ECDSA、EdDSA、ECDH、SM2)
  • 大整数函数、随机数和大量的支持函数

libgcrypt 是很多基础组件依赖的密码库,比如 gpg,systemd,qemu,postgresql,还有许多桌面环境的库,音视频组件,蓝牙都依赖于 libgcrypt 提供的密码安全机制,还有部分会选择依赖libgcrypt,比如 curl,cryptsetup 等会选择依赖 OpenSSL,libgcrypt 算法库,用户需要自行构建来选择不同的密码库。

libgcrypt 从 1.9.0 版本开始陆续支持了国密算法和国密的指令集优化。

GmSSL

项目地址:https://github.com/guanzhi/GmSSL

GmSSL 是一个开源密码工具包,为 GM/T 系列标准中规定的中国国家密码算法和协议提供一级支持。 作为 OpenSSL 项目的一个分支,GmSSL 提供了与 OpenSSL 的 API 级兼容性并保持了所有的功能。 现有项目(例如 Apache Web 服务器)可以轻松地移植到 GmSSL,只需进行少量修改和简单的重建。

自2014年底首次发布以来,GmSSL已入选开源中国六大推荐密码项目之一,并获得2015年中国Linux软件大奖。

该密码库的特点:

  • 支持中国GM/T密码标准。
  • 支持中国厂商的硬件密码模块。
  • 具有商业友好的开源许可证。
  • 由北京大学密码学研究组维护。

GmSSL 将支持以下所有 GM/T 加密算法:

  • SM3 (GM/T 0004-2012):具有 256 位摘要长度的密码哈希函数。
  • SM4(GM/T 0002-2012):密钥长度为128位,块大小为128位的块密码,也称为SMS4。
  • SM2(GM/T 0003-2012):椭圆曲线密码方案,包括数字签名方案、公钥加密、(认证)密钥交换协议和一种推荐的256位素数域曲线sm2p256v1。
  • SM9(GM/T 0044-2016):基于配对的密码方案,包括基于身份的数字签名、加密、(认证)密钥交换协议和一条256位推荐BN曲线。
  • ZUC(GM/T 0001-2012):流密码,采用128-EEA3加密算法和128-EIA3完整性算法。
  • SM1和SSF33:密钥长度为128位,块大小为128位的块密码,没有公开说明,只随芯片提供。

GmSSL 支持许多有用的加密算法和方案:

  • 公钥方案:Paillier、ECIES(椭圆曲线集成加密方案)
  • 基于配对的密码学:BF-IBE、BB1-IBE
  • 块密码和模式:Serpent、Speck
  • 块密码模式:FPE(格式保护加密)
  • 基于SM3/SM4的OTP(一次性密码)(GM/T 0021-2012)
  • 编码:Base58

ECDSA、RSA、AES、SHA-1 等 OpenSSL 算法在 GmSSL 中仍然可用。

nettle

官网:http://www.lysator.liu.se/~nisse/nettle

Nettle 是一个相对低层的加密库,旨在轻松适应各种工具包和应用程序。它开始于2001年的lsh的低级加密函数的集合。自2009年6月以来,Nettle 成为 GNU 软件包。

Nettle 的定位跟 libgcrypt 有点类似,是很多基础组件选择依赖的一个密码学库。

从提供的 API 上来看,Nettle 没有对算法做更高层次的抽象,每个不同的算法都有一套更易理解的接口,开发者也会更容易上手。

Nettle 从 3.8 版本开始支持了 SM3 算法,最新的开发分支已经合入了 SM4 算法,会在下一个 release 版本发布。

gnulib

官网:https://www.gnu.org/software/gnulib

从名字可以看出,gnulib 并不是一个纯密码算法的库,它的定位是 GNU 的公共代码库,旨在 GNU 包的源代码级别之间共享。

之所以在这里提 gnulib,是因为这个库里面实现了常用的哈希算法,也包括SM3算法,gnulib 里的 哈希算法主要是为 coreutils 包里的 sha*sum, md5sum 系列工具提供支持的,当然开发者也可以基于 gnulib 构建自己的程序。

gnulib 是在 2017 年 10 月支持了 SM3 算法,由阿里巴巴张佳贡献。

coreutils

coreutils 支持了大量的计算哈希的工具,比如 cksum,md5sum,b2sum,sha*sum 等,这些工具是紧密依赖于 gnulib 库的。

2017 年 10 月,在 gnulib 库支持了 SM3 之后,我们便向 coreutils 社区提交了 sm3sum 工具的支持,coreutils 社区却迟迟不愿接收,因为 SM3 算法的IV向量没有明确的来历说明,社区对算法的安全性有质疑,虽然彼时 SM3 已经是 ISO 的国际标准算法。社区人员认为 SM3 在 gnulib 中作为库提供给开发者是没有问题的,因为开发者具备也应该具备判断一个算法是否安全的能力,但是在 coreutils 中提供一个 sm3sum 的工具提供给终端用户会引起用户的误导,用户可能误认为算法安全性是得到保证的,尤其是在 SM3 算法安全性被质疑的前提下。

直到四年后的 2021 年 9 月,在包括Linux 内核,libgcrypt,OpenSSL 等主流的密码算法社区都支持了SM3算法后,在龙蜥的几次推动下,coreutils 社区终于不再质疑 SM3 的安全性问题,但是社区也不愿意再多引入一个工具,应该把这个哈希算法整合为一个工具,因为类似 *sum 的工具太多了。

因此,社区提出一个 cksum -a [algo] 的方案,通过给 cksum 工具添加一个算法参数,整合了目前 coreutils 中支持的所有哈希算法,为了兼容考虑,之前的 *sum 工具也继续保留了,SM3 是唯一仅在 cksum 工具中支持的算法,当然这并不是优点,使用习惯上也会有一些差异,用户需要通过 cksum -a sm3 来计算 SM3 哈希,除这个区别外,其它用法跟 md5sum 类似。

coreutils 从 9.0 版本开始支持 SM3 的哈希计算。

RustCrypto

这是一个纯 Rust 编写的密码算法库,供 Rust 开发者使用。

该项目维护着数十个流行的 crate,都提供密码算法的纯 Rust 实现,主要包括以下算法:

  • 非对称加密:椭圆曲线、rsa
  • 加密编码格式:const-oid、der、pem-rfc7468、pkcs8
  • 数字签名:dsa、ecdsa、ed25519、rsa
  • 椭圆曲线:k256、p256、p384
  • 哈希函数:blake2、sha2、sha3、sm3
  • 密钥派生函数:hkdf、pbkdf2
  • 消息认证码:hmac
  • 密码哈希:argon2、pbkdf2、scrypt
  • Sponge 函数:ascon、keccak
  • 对称加密:aes-gcm、aes-gcm-siv、chacha20poly1305、sm4
  • Traits:aead、密码、摘要、密码哈希、签名

该算法库目前支持 SM3 和 SM4 算法。

Intel IPP

项目地址:https://github.com/intel/ipp-crypto

Intel Integrated Performance Primitives (Intel IPP) Cryptography 是一个安全、快速且轻量级的密码学库,针对各种 Intel CPU 进行了高度优化。

该库提供了一套全面的常用于加密操作的函数,包括:

  • 对称密码学原语函数:

    • AES(ECB、CBC、CTR、OFB、CFB、XTS、GCM、CCM、SIV)
    • SM4(ECB、CBC、CTR、OFB、CFB、CCM)
    • TDES(ECB、CBC、CTR、OFB、CFB)
    • RC4
  • 单向哈希原语:

    • SHA-1、SHA-224、SHA-256、SHA-384、SHA-512
    • MD5
    • SM3
  • 数据认证原语函数:

    • HMAC
    • AES-CMAC
  • 公钥加密函数:

    • RSA、RSA-OAEP、RSA-PKCS_v15、RSA-PSS
    • DLP、DLP-DSA、DLP-DH
    • ECC(NIST 曲线)、ECDSA、ECDH、EC-SM2
  • 多缓冲区 RSA、ECDSA、SM3、x25519

  • 有限域算术函数

  • 大整数算术函数

  • PRNG/TRNG 和质数生成

使用英特尔 IPP 密码库的原因:

  • 安全性(秘密处理功能的恒定时间执行)
  • 专为小尺寸设计
  • 针对不同的 Intel CPU 和指令集架构进行了优化(包括硬件加密指令 SSE 和 AVX 的支持)
  • 可配置的 CPU 分配以获得最佳性能
  • 内核模式兼容性
  • 线程安全设计

参考链接


Java—bouncycastle支持国密SM2的公钥加密算法

java代码是依赖 BouncyCastle 类库,经修改此类库中的 SM2Engine 类的原码而来,用于支持 SM2 公钥加密算法,符合《GB/T 35276-2017: 信息安全技术 SM2密码算法使用规范》。

SM4 国标《GB/T 32907-2016 信息安全技术 SM4分组密码算法》。

可以使用 gmssl 工具进行交互测试(http://gmssl.org)

引入jar:

加解密工具类:

工具类:

测试例子:

参考链接


OpenSSL通过OCSP手动验证证书

这篇文章主要用来说明如何借助ocsp服务器来验证证书。ocsp(The Online Certificate Status Protocol)是一种验证证书状态的一种方式,也是CRL(certificate revocation list)证书吊销的一种替代方式。

与传统的CRL比较有以下特点:

  • 由于相对于传统的CRL,一个ocsp响应包含的信息更少,故ocsp能够更有效利用网络和客户资源
  • 用OCSP,客户无需自己解析CRL证书吊销列表,但是客户需要存储状态信息,而由于客户侧需要维护存储缓存,故导致存储信息很复杂。在实际使用中,这点带来的影响却很小,由于第三库提供的相关接口已经帮我们完成此类工作
  • OCSP通过专用网络、专用证书、在特定的时间公开其服务。OCSP不强制加密,故可能带来信息泄露的风险。

此文章中用到的openssl的版本为:OpenSSL 1.0.1g 7 Apr 2014

1、获取证书用于ocsp验证

首先,我们将从一个网站上获取一个证书,这里我们用Wikipedia作为样例来进行。我们获取证书通过如下命令:

过该命令可以获取wikipedia.org的客户端证书

保存这个输出到wikipedia.pem文件中

 现在,检查整个证书中是否包含ocsp网址

若执行正确则输出 http://ocsp.digicert.com ,否则你就不能通过ocsp验证这个证书

2、获取证书链

由于这个证书认证是一级一级逐层进行,故需要获得与这个证书相关的证书链。利用openssl s_client -showcerts 选项,能够查看到在该信任链上的所有相关证书

如你所见,输出能够看到两个证书,number 1 和number 0,其中number 0就是我们刚刚获取的那个证书。如果你的网站有更多证书在认证链中,那么你将看到更多证书。为了发送证书,需要保存证书链中所有证书到一个文件chain.pem,按照刚刚命令输出的证书顺序,根证书总是在文件结尾。

3、发送ocsp认证请求

现在我们有ocsp认证请求的所有信息,使用下面命令发送ocsp认证请求。

其结果如下 

如果你需要更简略的输出,去掉-text 选项,该选项一般用于调试

4、吊销证书

如果你有一个吊销的证书,你也可以测试该证书按照上述步骤,所得的响应如下:

5、其他错误

如果证书和ocsp服务不匹配,验证将错误,使用-text选项可以查看具体错误。

参考链接


RSA算法原理

如果你问我,哪一种算法最重要?

我可能会回答"公钥加密算法"

因为它是计算机通信安全的基石,保证了加密数据不会被破解。你可以想象一下,信用卡交易被破解的后果。

进入正题之前,我先简单介绍一下,什么是"公钥加密算法"。

一、一点历史

1976年以前,所有的加密方法都是同一种模式:

  (1)甲方选择某一种加密规则,对信息进行加密;

  (2)乙方使用同一种规则,对信息进行解密。

由于加密和解密使用同样规则(简称"密钥"),这被称为"对称加密算法"(Symmetric-Key  Algorithm)。

这种加密模式有一个最大弱点:甲方必须把加密规则告诉乙方,否则无法解密。保存和传递密钥,就成了最头疼的问题。

1976年,两位美国计算机学家Whitfield Diffie 和 Martin Hellman,提出了一种崭新构思,可以在不直接传递密钥的情况下,完成解密。这被称为"Diffie-Hellman密钥交换算法"。这个算法启发了其他科学家。人们认识到,加密和解密可以使用不同的规则,只要这两种规则之间存在某种对应关系即可,这样就避免了直接传递密钥。

这种新的加密模式被称为"非对称加密算法"。

  (1)乙方生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的。

  (2)甲方获取乙方的公钥,然后用它对信息加密。

  (3)乙方得到加密后的信息,用私钥解密。

如果公钥加密的信息只有私钥解得开,那么只要私钥不泄漏,通信就是安全的。

1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法。从那时直到现在,RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说,只要有计算机网络的地方,就有RSA算法。

这种算法非常可靠,密钥越长,它就越难破解。根据已经披露的文献,目前被破解的最长RSA密钥是768个二进制位。也就是说,长度超过768位的密钥,还无法破解(至少没人公开宣布)。因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全。

下面,我就进入正题,解释RSA算法的原理。文章共分成两部分,今天是第一部分,介绍要用到的四个数学概念。你可以看到,RSA算法并不难,只需要一点数论知识就可以理解。

二、互质关系

如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互质关系(coprime)。比如,15和32没有公因子,所以它们是互质关系。这说明,不是质数也可以构成互质关系。

关于互质关系,不难得到以下结论:

  1. 任意两个质数构成互质关系,比如13和61。

  2. 一个数是质数,另一个数只要不是前者的倍数,两者就构成互质关系,比如3和10。

  3. 如果两个数之中,较大的那个数是质数,则两者构成互质关系,比如97和57。

  4. 1和任意一个自然数是都是互质关系,比如1和99。

  5. p是大于1的整数,则p和p-1构成互质关系,比如57和56。

  6. p是大于1的奇数,则p和p-2构成互质关系,比如17和15。

三、欧拉函数

请思考以下问题:

  任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?)

计算这个值的方法就叫做欧拉函数,以$φ(n)$表示。在1到8之中,与8形成互质关系的是1、3、5、7,所以 $φ(n) = 4$。

$φ(n)$ 的计算方法并不复杂,但是为了得到最后那个公式,需要一步步讨论。

第一种情况

如果$n=1$,则 $\phi(1) = 1$ 。因为$1$与任何数(包括自身)都构成互质关系。

第二种情况

如果$n$是质数,则 $\Phi(n)=n-1$ 。因为质数与小于它的每一个数,都构成互质关系。比如5与1、2、3、4都构成互质关系。

第三种情况

如果$n$是质数的某一个次方,即 $n = p^k$ ($p$为质数,$k$为大于等于$1$的整数),则

$\varPhi(p^k) {=} p^k - p^{k-1}$

比如 $φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4$。

这是因为只有当一个数不包含质数p,才可能与n互质。而包含质数p的数一共有p^(k-1)个,即1×p、2×p、3×p、...、p^(k-1)×p,把它们去除,剩下的就是与n互质的数。

上面的式子还可以写成下面的形式:

$\varPhi(p^k) {=} p^k - p^{k-1} = p^k(1- \frac{1}{p})$

可以看出,上面的第二种情况是 k=1 时的特例。

第四种情况

如果n可以分解成两个互质的整数之积,

  $n = p_1 * p_2$

  $φ(n) = φ(p_1p_2) = φ(p_1)φ(p_2)$

即积的欧拉函数等于各个因子的欧拉函数之积。比如,φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。

这一条的证明要用到"中国剩余定理",这里就不展开了,只简单说一下思路:如果a与$p_1$互质(a<$p_1$),b与$p_2$互质(b<$p_2$),c与$p_1p_2$互质(c<$p_1p_2$),则c与数对 (a,b) 是一一对应关系。由于a的值有$φ(p_1)$种可能,b的值有$φ(p_2)$种可能,则数对 (a,b) 有$φ(p_1)φ(p_2)$种可能,而c的值有$φ(p_1p_2)$种可能,所以$φ(p_1p_2)$就等于$φ(p_1)φ(p_2)$。

第五种情况

因为任意一个大于1的正整数,都可以写成一系列质数的积。

$n {=} p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$

根据第4条的结论,得到

$\varPhi(n) {=} \varPhi(p_1^{k_1}) \varPhi(p_2^{k_2}) \cdots \varPhi(p_r^{k_r})$

再根据第3条的结论,得到

$\varPhi(n) {=}  p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r} (1- \frac{1}{p_1}) (1- \frac{1}{p_2}) \cdots (1- \frac{1}{p_r})$

也就等于

$\varPhi(n) {=} n(1- \frac{1}{p_1}) (1- \frac{1}{p_2}) \cdots (1- \frac{1}{p_r})$

这就是欧拉函数的通用计算公式。比如,1323的欧拉函数,计算过程如下:

$\varPhi(1323) {=} \varPhi(3^3 * 7^2) {=} 1323 (1- \frac{1}{3}) (1- \frac{1}{7}) = 756$

四、欧拉定理

欧拉函数的用处,在于欧拉定理。"欧拉定理"指的是:

如果两个正整数a和n互质,则n的欧拉函数 $φ(n)$ 可以让下面的等式成立:

$a^{\varPhi(n)} \equiv 1 \pmod{n}$

也就是说,a的φ(n)次方被n除的余数为1。或者说,a的φ(n)次方减去1,可以被n整除。比如,3和7互质,而7的欧拉函数φ(7)等于6,所以3的6次方(729)减去1,可以被7整除(728/7=104)。

欧拉定理的证明比较复杂,这里就省略了。我们只要记住它的结论就行了。

欧拉定理可以大大简化某些运算。比如,7和10互质,根据欧拉定理,

$7^{\varPhi(10)} \equiv 1 \pmod{10}$

已知 φ(10) 等于4,所以马上得到7的4倍数次方的个位数肯定是1。

$7^{4k} \equiv 1 \pmod{10}$

因此,7的任意次方的个位数(例如7的222次方),心算就可以算出来。

欧拉定理有一个特殊情况。

假设正整数a与质数p互质,因为质数p的φ(p)等于p-1,则欧拉定理可以写成

$a^{p-1} \equiv 1 \pmod{p}$

这就是著名的费马小定理。它是欧拉定理的特例。

欧拉定理是RSA算法的核心。理解了这个定理,就可以理解RSA。

五、模反元素

还剩下最后一个概念:

如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。

$ab \equiv 1 \pmod{n}$

这时,b就叫做a的"模反元素"

比如,3和11互质,那么3的模反元素就是4,因为 (3 × 4)-1 可以被11整除。显然,模反元素不止一个, 4加减11的整数倍都是3的模反元素 {...,-18,-7,4,15,26,...},即如果b是a的模反元素,则 b+kn 都是a的模反元素。

欧拉定理可以用来证明模反元素必然存在。

$a^{\varPhi(n)} {=} a* a^{\varPhi(n)-1} \equiv 1 \pmod{n}$

可以看到,a的 $φ(n)-1$ 次方,就是a的模反元素。

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

好了,需要用到的数学工具,全部介绍完了。RSA算法涉及的数学知识,就是上面这些,下一次我就来介绍公钥和私钥到底是怎么生成的。

有了这些知识,我们就可以看懂RSA算法。这是目前地球上最重要的加密算法。

六、密钥生成的步骤

我们通过一个例子,来理解RSA算法。假设爱丽丝要与鲍勃进行加密通信,她该怎么生成公钥和私钥呢?

第一步,随机选择两个不相等的质数p和q。

爱丽丝选择了61和53。(实际应用中,这两个质数越大,就越难破解。)

第二步,计算p和q的乘积n。

爱丽丝就把61和53相乘。

  $n = 61*53 = 3233$

n的长度就是密钥长度。3233写成二进制是110010100001,一共有12位,所以这个密钥就是12位。实际应用中,RSA密钥一般是1024位,重要场合则为2048位。

第三步,计算n的欧拉函数φ(n)。

根据公式:

  $\varPhi(n) = (p-1)(q-1)$

爱丽丝算出φ(3233)等于60×52,即3120。

第四步,随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。

爱丽丝就在1到3120之间,随机选择了17。(实际应用中,常常选择65537)

第五步,计算e对于φ(n)的模反元素d。

所谓"模反元素"就是指有一个整数d,可以使得ed被φ(n)除的余数为1。

  $ed \equiv 1 \pmod{\varPhi(n)}$

这个式子等价于

  $ed - 1 = k\varPhi(n)$

于是,找到模反元素d,实质上就是对下面这个二元一次方程求解。

  $ex + \varPhi(n)y = 1$

已知 e=17, φ(n)=3120,

  $17x + 3120y = 1$

这个方程可以用"扩展欧几里得算法"求解,此处省略具体过程。总之,爱丽丝算出一组整数解为 (x,y)=(2753,-15),即 d=2753。

至此所有计算完成。

第六步,将n和e封装成公钥,n和d封装成私钥。

在爱丽丝的例子中,n=3233,e=17,d=2753,所以公钥就是 (3233,17),私钥就是(3233, 2753)。

实际应用中,公钥和私钥的数据都采用ASN.1格式表达(实例)。

七、RSA算法的可靠性

回顾上面的密钥生成步骤,一共出现六个数字:

  p
  q
  n
  φ(n)
  e
  d

这六个数字之中,公钥用到了两个(n和e),其余四个数字都是不公开的。其中最关键的是d,因为n和d组成了私钥,一旦d泄漏,就等于私钥泄漏。

那么,有无可能在已知n和e的情况下,推导出d?

  (1)ed≡1 (mod φ(n))。只有知道e和φ(n),才能算出d。

  (2)φ(n)=(p-1)(q-1)。只有知道p和q,才能算出φ(n)。

  (3)n=pq。只有将n因数分解,才能算出p和q。

结论:如果n可以被因数分解,d就可以算出,也就意味着私钥被破解。

可是,大整数的因数分解,是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。维基百科这样写道:

  "对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。

  假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。

  只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。"

举例来说,你可以对3233进行因数分解(61×53),但是你没法对下面这个整数进行因数分解。

  12301866845301177551304949
  58384962720772853569595334
  79219732245215172640050726
  36575187452021997864693899
  56474942774063845925192557
  32630345373154826850791702
  61221429134616704292143116
  02221240479274737794080665
  351419597459856902143413

它等于这样两个质数的乘积:

  33478071698956898786044169
  84821269081770479498371376
  85689124313889828837938780
  02287614711652531743087737
  814467999489
    ×
  36746043666799590428244633
  79962795263227915816434308
  76426760322838157396665112
  79233373417143396810270092
  798736308917

事实上,这大概是人类已经分解的最大整数(232个十进制位,768个二进制位)。比它更大的因数分解,还没有被报道过,因此目前被破解的最长RSA密钥就是768位。

八、加密和解密

有了公钥和密钥,就能进行加密和解密了。

(1)加密要用公钥 (n,e)

假设鲍勃要向爱丽丝发送加密信息m,他就要用爱丽丝的公钥 (n,e) 对m进行加密。这里需要注意,m必须是整数(字符串可以取ascii值或unicode值),且m必须小于n。

所谓"加密",就是算出下式的c:

  $m^e \equiv c \pmod{n}$

爱丽丝的公钥是 (3233, 17),鲍勃的m假设是65,那么可以算出下面的等式:

  $65^{17} \equiv 2790 \pmod{3233}$

于是,c等于2790,鲍勃就把2790发给了爱丽丝。

(2)解密要用私钥(n,d)

爱丽丝拿到鲍勃发来的2790以后,就用自己的私钥(3233, 2753) 进行解密。可以证明,下面的等式一定成立:

  $c^d \equiv m \pmod{n}$

也就是说,c的d次方除以n的余数为m。现在,c等于2790,私钥是(3233, 2753),那么,爱丽丝算出

  $2790^{2753} \equiv 65 \pmod{3233}$

因此,爱丽丝知道了鲍勃加密前的原文就是65。

至此,"加密--解密"的整个过程全部完成。

我们可以看到,如果不知道d,就没有办法从c求出m。而前面已经说过,要知道d就必须分解n,这是极难做到的,所以RSA算法保证了通信安全。

你可能会问,公钥(n,e) 只能加密小于n的整数m,那么如果要加密大于n的整数,该怎么办?有两种解决方法:一种是把长信息分割成若干段短消息,每段分别加密;另一种是先选择一种"对称性加密算法"(比如DES),用这种算法的密钥加密信息,再用RSA公钥加密DES密钥。

九、私钥解密的证明

最后,我们来证明,为什么用私钥解密,一定可以正确地得到m。也就是证明下面这个式子:

  $c^d \equiv m \pmod{n}$

因为,根据加密规则

  $m^e \equiv c \pmod{n}$

于是,c可以写成下面的形式:

  $c = m^e - kn$

将c代入要我们要证明的那个解密规则:

  $(m^e - kn)^d \equiv m \pmod{n}$

它等同于求证

  $m^{ed} \equiv m \pmod{n}$

由于

  $ed \equiv 1 \pmod{\varPhi(n)}$

所以

  $ed = h\varPhi(n)+1$

将ed代入:

  $m^{h\varPhi(n)+1} \equiv m \pmod{n}$

接下来,分成两种情况证明上面这个式子。

(1)m与n互质。

根据欧拉定理,此时

  $m^{\varPhi(n)} \equiv 1 \pmod{n}$

得到

  $(m^{\varPhi(n)})^h × m \equiv m \pmod{n}$

原式得到证明。

(2)m与n不是互质关系。

此时,由于n等于质数p和q的乘积,所以m必然等于kp或kq。

以 m = kp为例,考虑到这时k与q必然互质,则根据欧拉定理,下面的式子成立:

  $(kp)^{q-1} \equiv 1 \pmod{q}$

进一步得到

  $[(kp)^{q-1}]^{h(p-1)} * kp \equiv kp \pmod{q}$

  $(kp)^{ed} \equiv kp \pmod{q}$

将它改写成下面的等式

  $(kp)^{ed} = tq + kp$

这时t必然能被p整除,即 t=t'p

  $(kp)^{ed} = t'pq + kp$

因为 m=kp,n=pq,所以

  $m^{ed} \equiv m \pmod{n}$

原式得到证明。

参考链接


SM2的非对称加解密Java工具类(bcprov-jdk15on/bcprov-jdk16)

bcprov-jdk15on实现例子

Maven依赖:

Java实现如下:

bcprov-jdk16实现例子