ZipCrypto算法回顾

ZipCrypto,也称为 PKZIP Stream Cipher,是一种弱加密手段,在1994年就已经被攻破,该加密方式不能经受已知明文攻击(Known Plaintext Attack,KPA)。

明文攻击主要利用大于 12 字节的一段已知明文数据进行攻击,从而获取整个加密文档的数据。也就是说,如果手里有一个未知密码的压缩包和压缩包内某个文件的一部分明文(不一定非要从头开始,能确定偏移就行),那么就可以通过这种攻击来解开整个压缩包。比如压缩包里有一个常见的 license 文件,或者是某个常用的 dll 库,或者是带有固定头部的文件(比如 xml、exe、png 等容易推导出原始内容的文件),那么就可以运用这种攻击。

Biham和Kocher文中回顾了PKZIP Stream Cipher加密解密过程。

原始论文链接: A Known Plaintext Attack on the PKZIP Stream Cipher

本站链接: A Known Plaintext Attack on the PKZIP Stream Cipher

首先,文件压缩后形成压缩包,PKZIP在压缩包中每个文件头部加上12字节的文件头,用于随机化,也用于在解密时识别错误的密钥,然后该文件头和文件内容一起进行加密。

加密过程如下:

  • 首先初始化,key为用户输入的二进制的密钥序列。key0,key1,key2为三个全局变量,在加/解密每个字节时都会用到。小写L表示第L个字节

Update_keys()函数定义如下,输入为一个字节。

  • 然后就是加文件头,开始加密。Pi代表明文第i字节

解密过程如下:

  • 首先初始化,和加密过程初始化完全相同
  • 然后解密,Ci代表加密的内容。解密后P1-P12是文件头,仅留作校验,解密后不再需要

附上一段代码,实现PKZIP解密,加密类似。

总结:PKZIP Stream Cipher是一种按照文件顺序、逐个字节进行加密/解密的算法。实际使用中,还需要注意到每遇到一个压缩包内的文件,就会从头进行一遍加密/解密过程。实现一个已知密钥zip archive的解密还需要了解ZIP格式等问题,这里就不再赘述了。

参考链接


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

密码算法库是操作系统的基础组件,在系统安全领域的作用不言而喻。操作系统默认已经内置了大量的密码学库,比如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实现例子