文章目录

• 3. Key Types
• • 公钥质数E
  • 生成随机大质数p和q
  • 求最小公倍数L
  • 求私钥质数D
  • PyCryptodome generate()
• 4. Data Conversion Primitives
• 5. Cryptographic Primitives
• • 5.1. Encryption and Decryption Primitives
  • • 5.1.1. RSAEP
    • 5.1.2 RSADP
  • 5.2. Signature and Verification Primitives
  • • 5.2.1. RSASP1
    • 5.2.2. RSAVP1
• 6. Overview of Schemes
• OpenSSL接口
• 参考资料

也可以参考NIST.SP.800-56B和FIPS 186-4, Digital Signature Standard (DSS) | CSRC (nist.gov)。

PKCS， The Public-Key Cryptography Standards，涉及多个标准，其中PKCS #1为RSA的标准，可以在RFC官网搜索PKCS查阅。

简介：

• 命名取自三位发明者的姓氏字母Ron Rivest、Adi Shamir、Leonard Adleman；
• 官网：https://rsa.com/
• 1983年申请专利，现已过期，所以可以商用；
• 公钥密码基于数学困难问题保证机密性，RSA的基础是，大整数质因数分解十分困难；
• RSA的实现通常会用到Base64，主要是为了防止产生乱码；
• RSA的密钥长度、密文和签名长度与模量n一致，比如2048 bits（256 bytes），参考FIPS记为nlen，RSA的安全强度与模量n的位数相关联；
  • 2017年根据ECRYPT报告，建议长度不少于2048 bits；
  • FIPS 186-4签名标准中为1024, 2048 和3072 bits；
• 签名和解密（基于私钥）比验签和加密（基于公钥）慢；
• …

文章与PKCS一致。

3. Key Types

RSA Public Key：

• n, the RSA modulus(模量), a positive integer
• e, the RSA public exponent, a positive integer

RSA Private Key：

• n, the RSA modulus, a positive integer, the same as in the corresponding RSA public key.
• d, the RSA private exponent, a positive integer

其中，私钥在RFC 8017中还有第二种表示法，参数很多，感兴趣的可查看原文档。

密钥生成步骤参考FIPS 186-4

• B.3.1 Criteria for IFC Key Pairs
• B.3.3 Generation of Random Primes that are Probably Prime

IFC: Integer Factorization Cryptography

术语：

• LCM, Least Common Multiple, 最小公倍数。
• GCM, Greatest Common , 最大公约数。

公钥质数E

根据FIPS 186-4 B.3.1 1(b)，E使用满足以下条件的默认值即可：

2^16 < e < 2^256
65537 == 2^16 + 1  # default

若E采用随机值，则性能不可控。

生成随机大质数p和q

需要使用伪随机数生成器生成这两个大质数，利用费马素性检测（Fermat Primality Test）判断是否为质数。

需要满足：

• (p-1)和(q-1)分别与e互素（ relatively prime to e）
• len§ = len(q) = nlen/2
• 2^(nlen-1)/2 <= p <= 2^nlen/2 - 1 == 2^len§ - 1， q一致
• p和q差值 > 2^nlen/2-100

N = p x q，生成N后丢弃p和q。

求最小公倍数L

L = LCM(p-1, q-1)

GCD(E, L) == 1，保证一定存在私钥中的D；

求私钥质数D

2^nlen/2 < D < L，若不满足需要重新生成p和q。

E x D mod L == 1,保证可以解密还原明文。

即：D = E^-1mod L

等价于：1==(ED) mod L

PyCryptodome generate()

\Crypto\PublicKey\RSA.py

def generate(bits, randfunc, e=65537):# ...d = n = Integer(1)e = Integer(e)while n.size_in_bits() != bits and d < (1 << (bits // 2)):# Generate the prime factors of n: p and q.# By construciton, their product is always# 2^{bits-1} < p*q < 2^bits.size_q = bits // 2size_p = bits - size_qmin_p = min_q = (Integer(1) << (2 * size_q - 1)).sqrt()if size_q != size_p:min_p = (Integer(1) << (2 * size_p - 1)).sqrt()def filter_p(candidate):return candidate > min_p and (candidate - 1).gcd(e) == 1p = generate_probable_prime(exact_bits=size_p,randfunc=randfunc,prime_filter=filter_p)min_distance = Integer(1) << (bits // 2 - 100)def filter_q(candidate):return (candidate > min_q and(candidate - 1).gcd(e) == 1 andabs(candidate - p) > min_distance)q = generate_probable_prime(exact_bits=size_q,randfunc=randfunc,prime_filter=filter_q)n = p * qlcm = (p - 1).lcm(q - 1)d = e.inverse(lcm)

4. Data Conversion Primitives

• I2OSP - 将数大端存储
• OS2IP - I2OSP逆过程

5. Cryptographic Primitives

源码参考PyCryptodome

5.1. Encryption and Decryption Primitives

公钥加密，私钥解密。

5.1.1. RSAEP

RSA Encryption Primitive

def RSAEP ((n, e), m):#  an integer between 0 and n - 1return  c = m**e % n# pycryptodome \Crypto\PublicKey\RSA.py
def _encrypt(self, plaintext):if not 0 <= plaintext < self._n:raise ValueError("Plaintext too large")return int(pow(Integer(plaintext), self._e, self._n))

5.1.2 RSADP

RSA Decryption Primitive

# def RSADP (K, c):# K: one of the 2 forms of private key
def RSADP((n,d), c):return  m = c**d % ndef RSADP((p, q, dP, dQ, qInv, r_i, d_i, t_i), c):m_1 = c**dP % p m_2 = c**dQ % qif u > 2:m_i = c**(d_i) % r_i # i = 3, ..., uh = (m_1 - m_2) * qInv % pm = m_2 + q * hif u > 2:R = r_1for i in range(3, u+1):R = R * r_(r-1)h = (m_i - m) * t_i % r_im = m + R * h.return m# pycryptodome \Crypto\PublicKey\RSA.py
def _decrypt(self, ciphertext):if not 0 <= ciphertext < self._n:raise ValueError("Ciphertext too large")if not self.has_private():raise TypeError("This is not a private key")# Blinded RSA decryption (to prevent timing attacks):# Step 1: Generate random secret blinding factor r,# such that 0 < r < n-1r = Integer.random_range(min_inclusive=1, max_exclusive=self._n)# Step 2: Compute c' = c * r**e mod ncp = Integer(ciphertext) * pow(r, self._e, self._n) % self._n# Step 3: Compute m' = c'**d mod n       (normal RSA decryption)m1 = pow(cp, self._dp, self._p)m2 = pow(cp, self._dq, self._q)h = ((m2 - m1) * self._u) % self._qmp = h * self._p + m1# Step 4: Compute m = m**(r-1) mod nresult = (r.inverse(self._n) * mp) % self._n# Verify no faults occurredif ciphertext != pow(result, self._e, self._n):raise ValueError("Fault detected in RSA decryption")return result

5.2. Signature and Verification Primitives

私钥签名（加密），公钥验证（解密）。

其实和5.1加解密是一样的。

5.2.1. RSASP1

RSA Signature Primitive, version 1

# def RSASP1 (K, m):# K one of the 2 forms of private key# m message representative, an integer between 0 and n - 1
def RSASP1((n,d), m)return s = (m**d) % ndef RSASP1((p, q, dP, dQ, qInv, r_i, d_i, t_i), m):s_1 = m**dP % ps_2 = m**dQ % qif( u > 2):s_i = m**(d_i) % r_i # i = 3, ..., uh = (s_1 - s_2) * qInv % ps = s_2 + q * hif ( u > 2 ):R = r_1for i in range(3, u+1):R = R * r_(i-1)h = (s_i - s) * t_i mod r_is = s + R * hreturn s

5.2.2. RSAVP1

RSA Verification Primitive, version 1

def RSAVP1 ((n, e), s):#  an integer between 0 and n - 1return m = s**e % n

6. Overview of Schemes

这一部分仅涉及RSA对数据的处理，实际应用中还要有密钥管理，如密钥获取和验证。

Two types of scheme（方案） :

• encryption schemes
  • RSAES-OAEP (Section 7.1)
  • RSAES-PKCS1-v1_5 (Section 7.2)
• signature schemes
  • RSASSA-PSS (Section 8.1)
  • RSASSA-PKCS1-v1_5 (Section 8.2)

一对密钥仅能用于一种应用方案。

OpenSSL接口

OpenSSL 3.0以前：

https://www.openssl.org/docs/man3.0/man3/RSA_new.html
https://www.openssl.org/docs/man3.0/man3/RSA_generate_key.html

OpenSSL 3.0以后：

https://www.openssl.org/docs/man3.0/man7/EVP_PKEY-RSA.html

参考资料

RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2

NIST.SP.800-56Br2-Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography (nist.gov)

FIPS 186-4, Digital Signature Standard (DSS) | CSRC (nist.gov)