本文大纲

简介
DH
RSA

Leopold

文章

分类

标签

github.com/SayNop

gitee.com/WhenTimeGoesBy

fur999immer@gmail.com

非对称加密算法

2024-05-03

CryptographyCryptographyDHRSA

简介

非对称加密算法的加密与解密使用不同的密钥，即公钥和私钥。通常来说，发送方使用公钥加密数据后发送，接受方使用私钥解密数据得到明文

DH

DH（Diffie-Hellman 密钥交换）算法用于安全的发放收发双方约定的密钥

DH算法是第一个密钥协商算法，仅用于密钥分配，不能用于加解密消息

消息传递流程

收发双方构建本地密钥。构建密钥时，使用本方的私钥及对方的公钥构建本地密钥
发送方使用本地密钥加密消息发送
接受方使用本地密钥对收到的消息解密

API 使用流程

通过调用生成甲方密钥对
通过甲方公钥生成乙方密钥对
构建甲方本地密钥：通过甲方私钥与乙方公钥构建
构建乙方本地密钥：通过乙方私钥与甲方公钥构建
甲方加密
乙方解密

代码

Java API

// 初始化甲方密钥 - 直接构建
public static Map<String, Object> initKey() throws Exception {
    // 1.实例化DH算法的密钥对生成器
    KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("DH");
    keyPairGenerator.initialize(512);  // 初始化生成器 - 密钥长度需64的整数倍，默认1024

    // 2.生成密钥对
    KeyPair keyPair = keyPairGenerator.generateKeyPair();
    DHPublicKey publicKey = (DHPublicKey) keyPair.getPublic();  // 甲方公钥
    DHPrivateKey privateKey = (DHPrivateKey) keyPair.getPrivate(); // 甲方私钥
    
    // 3.hash表存储密钥并返回
    Map<String, Object> KeyMap = new HashMap<String, Object>(2);
    keyMap.put("DHPublicKey", publicKey);
    keyMap.put("DHPrivateKey", privateKey);
    return keyMap;
}

// 初始化乙方密钥 - 根据甲方公钥构建自己的密钥对
public static Map<String, Object> initKey(byte[] publicKey) throws Exception {
    // 1.根据传入的公钥转换成可生成本地密钥对的公钥
    X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(publickey);  // 公钥转换材料。X509为数字证书文档，根据RFC 5280编码
    KeyFactory keyFactory = KeyFactory.getInstance("DH");  // 实例化
    PublicKey pubKey = keyFactory.generatePublic(x509KeySpec);  // 产生转换后的公钥
        
    // 2.根据转化后的公钥构建密钥对
    DHParameterSpec dhParamSpec = ((DHPublicKey) pubKey).getParams();
    // 密钥对生成器
    KeyPairGenerator KeyPairGenerator = KeyPairGenerator.getInstance(keyFactory.getAlgorithm())
    // 生成密钥对
    KeyPair keyPair = keyPairGenerator.generateKeyPair();
    DHPublicKey publicKey = (DHPublicKey) keyPair.getPublic();  // 已方公钥
    DHPrivateKey privateKey = (DHPrivateKey) keyPair.getPrivate(); // 已方私钥
    
    // 3.hash表存储密钥对并返回
    Map<String, Object> KeyMap = new HashMap<String, Object>(2);
    keyMap.put("DHPublicKey", publicKey);
    keyMap.put("DHPrivateKey", privateKey);
    return keyMap;
}

// 构建本地密钥 - 本方的私钥及对方的公钥
public static byte[] getSecretKey(byte[] publicKey, byte[] privateKey) throws Exception { 
    // 公钥转换为可用公钥
    X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(publickey);  // 公钥转换材料。X509为数字证书文档，根据RFC 5280编码
    KeyFactory keyFactory = KeyFactory.getInstance("DH");  // 实例化
    PublicKey pubKey = keyFactory.generatePublic(x509KeySpec);  // 产生转换后的公钥
        
    // 私钥转换为可用私钥
    PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(privateKey);
    PrivateKey priKey = KeyFactory.generatory.generatePrivate(pkcs8KeySpec);
        
    // 构建本地密钥
    KeyAgreement keyAgree = KeyAgreement.getInstance(keyFactory.getAlgorithm());
    keyAgree.init(priKey);
    KeyAgree.doPhase(pubKey, true);
    // 生成本地密钥
    SecretKey secretKey = keyAgree.generateSecret("AES");
    return secretKey.getEncoded();
}

// 加密 - 消息加解密使用AES进行，DH只在密钥交换中使用
public static byte[] encrypt(byte[] data, byte[] key) throws Exception {
    // 转换成可用本地密钥
    SecretKey secretKey = new SecretKeySpec(key, "AES");
    // 加密
    Cipher cipher = Cipher.getInstance(secretKey.getAlgorithm());
    cipher,init(Cipher.ENCRYPT_MODE, secretKey);
    return cipher.doFinal(data);
}

// 解密 - 消息加解密使用AES进行，DH只在密钥交换中使用
public static byte[] decrypt(byte[] data, byte[] key) throws Exception {
    // 转换成可用本地密钥
    SecretKey secretKey = new SecretKeySpec(key, "AES");
    // 解密
    Cipher cipher = Cipher.getInstance(secretKey.getAlgorithm());
    cipher,init(Cipher.DECRYPT_MODE, secretKey);
    return cipher.doFinal(data);
}

RSA

RSA算法由三位学者提出，以三位学者首字母命名，基于因数分解，可用与加密与数字签名。
相对于DES算法，RSA算法效率低，速度慢

消息传递流程

发送方构建密钥对，公布公钥至消息接受方
发送方使用私钥加密数据，将加密内容发送至接受方
接受方通过公钥解密，得到消息内容。即“私钥加密，公钥解密”
消息的互相发送，即接受方需要向发送方发送消息
- 如果保持之前情况，则采用“公钥加密，私钥解密”（容易被窃听）
- 接受方同样生成密钥对，并告知发送方自己的公钥，以保证“私钥加密，公钥解密”
- 即：私钥加密的数据需要公钥解密，公钥加密的数据需要私钥解密

工作模式与密钥长度

密钥长度支持512-65536，必须是64的整数倍

ECB：密钥长度1024
None：密钥长度2024

涉及到数学内容

互质：若N个整数的最大公因数为1，则这N个数互质
- 判断1：两个质数一定互质
- 判断2：一个质数与另一个不是它倍数的数一定互质
- 判断3：两个相邻的数一定互质
- 判断4：两个相邻的奇数一定互质
- 判断5：较大的数为质数时，两数互质
- 判断6：较小的数为质数，较大的数不是其倍数，两数互质（与判断2类似）
- 判断7：2与任何奇数互质
- 判断8：1与任何数互质
- 判断9：通过辗转相除法
欧拉函数：小于等于指定数字 n 的正整数中，与 n 互质的数的个数。例如：n=8，则与 n 互质的数为1、3、5、7，最终结果为4，记为 $φ (n) = 4$ 。质数的欧拉函数为自身减1，即 $φ (p) = p - 1$ ( $p$ 为质数)
- 若 $n = p \cdot q$ ，其中p与q为质数，则有 $φ (n) = φ (p \cdot q) = φ (p - 1) φ (q - 1) = (p - 1) (q - 1)$
同余：若 a 与 b 对 m 求模的值相等，则a与b关于模m同余，记为 $a \equiv b (m o d m)$ 。例如 $26 \equiv 14 (m o d 12)$
- $(a - b) m o d m = 0$ ，则 $a \equiv b (m o d m)$
模反元素：若 a 与 n 互质，则存在 b ，使 $a \cdot b - 1$ 可以被n整除（ $a \cdot b$ 除以 n 的余数为1, $a \cdot b m o d n = 1$ ），则b为a的模反元素 - 参考百度百科模反元素open in new window
- 根据定义可知 $a x = k n + 1$ （k为任意常数），求解出 x 得到一组模反元素
- 例如：3 与 11 互质，4 为 3 的模反元素， $(3 \times 4) - 1$ 可以被11整除。-18，-7，15，26等也为3的模反元素（除以11等于0），即 $b + k \cdot n$ 都为模反元素。
- 此时记为 $a \cdot b \equiv 1 (m o d n)$ ，或记为 $a^{- 1} \equiv b (m o d n)$
- 模逆元的存在，在模数n下的除法可以用和对应模逆元的乘法来达成，此概念和实数除法的概念相同 - 参考wiki百科模反元素open in new window
欧拉定理：若 m 与 n 互质，则 $m^{φ (n)} \equiv 1 (m o d n)$
- 引申： $m^{φ (n)} = m \cdot m^{φ (n) - 1}$ 。根据模反元素定义 $m^{φ (n) - 1}$ 就是 m 在模 n 时的模反元素

实现流程

寻找一对数字a，b，使得对a求幂还是对b求幂，对n取余后值为对方的逆运算。即 $x^{a} m o d n = y$ ， $y^{b} m o d n = x$

公私钥产生
- 取余对象：任意两质数 p 与 q （加密中会使用较大质数），且 $p \neq q$ ，得到 $n = p \cdot q$ 。例如，取 p = 3，q = 11， $n = p \cdot q = 33$ (二进制为100001，6位二进制，即6位加密，实际中会常用1024位)
- 公钥范围：计算n的互质个数 $φ (n) = (p - 1) \cdot (q - 1) = 2 \cdot 10 = 20$
- 选公钥：选择小于 $φ (n)$ 的整数 e , $1 < e < φ (n)$ ，且需要互质（取模反的条件）。这里取 e = 7。其中，取 e = 19 时，后续生成的公私钥相同
- 算私钥：求 e 模 $φ (n)$ 的模反元素，命名为d（模反元素定义，需要 e 与 $φ (n)$ 互质）。这里取 k = 1 时, d 的值，3
- (n, e) 为公钥，（n，d）为私钥。本例中公钥 (33, 7) ，私钥 (33, 3)
- 如果需要猜测私钥，需要知道公钥范围 $φ (n)$ 。而 $φ (n)$ 需要两个质数因子p和q，即对n进行质因数分解
加密
- 将待加密文本进行编码，得到字节码。例如：加密数字 3
- 待加密数字 m 必须小于 n（本例中必须小于33），使用事先约定好的方法将待加密文本转换成数组（每两位16进制组成一个数字，举例中直接用ascii码数组）。数组中数字依次使用 $m^{e} \equiv c (m o d n)$ 得到密文c。 $m^{e} \equiv c (m o d n)$ 可用 $m^{e} m o d n = c$ ，得到 $3^{7} m o d 33 = 2187 m o d 33 = 9$ ，密文9
解密
- 根据流程目标，与加密同理
- 计算 $9^{3} m o d 33 = 719 m o d 33 = 3$ , 明文为3

原理

明确流程
- 明文 m 使用公钥 e 经过 $c = m^{e} (m o d n)$ 加密得到密文 c
- 密文 c 使用私钥 d 经过 $m^{'} = c^{d} (m o d n)$ 解密得到明文 m′
- 将加密公式代入解密公式可知，只需 证明 $(m^{e})^{d} \equiv m (m o d n)$ 即可证明该算法
根据公私钥生成过程可知，e 与 d 是模 $φ (n)$ 的模反元素，即存在整数 k ，使得
$\begin{matrix} (1) & e \times d = 1 + k \times φ (n) \end{matrix}$
将式(1) 代入 $(m^{e})^{d} = m^{e \times d}$ 得到式(2)
$\begin{aligned} m^{e \times d} & = m^{1 + k \times φ (n)} \\ (2) & = m \times m^{k \times φ (n)} \end{aligned}$
将 m 与 n 代入欧拉定理（欧拉定理要求 m 与 n 互质，实际计算中明文 m 与模数 n 不互质也能正常输出），得到式(3)
$\begin{aligned} m^{k \times φ (n)} & \equiv 1^{k} (m o d n) \\ (3) & \equiv 1 (m o d n) \end{aligned}$
将式(3) 两边同乘 m 得到
$\begin{matrix} (4) & m \times m^{k \times φ (n)} \equiv m (m o d n) \end{matrix}$
将式(2) 代入式(4) 得到待证明式，即证明完成
$m^{e \times d} \equiv m (m o d n)$

代码

Python实现。代码出自GPT：使用python编写rsa算法的实现流程

import random
from math import gcd  # 用于计算最大公约数
from sympy import mod_inverse  # 计算模反元素

def is_prime(n):
    """检查一个数是否为素数"""
    if n <= 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def generate_prime(bits=8):
    """生成一个指定位数的素数"""
    while True:
        num = random.getrandbits(bits)
        if is_prime(num):
            return num

def generate_keys(bits=8):
    """生成 RSA 密钥对"""
    # 生成两个大素数 p 和 q
    p = generate_prime(bits)
    q = generate_prime(bits)
    # 计算 n 和 φ(n)
    n = p * q
    phi_n = (p - 1) * (q - 1)

    # 选择公钥指数 e (通常选择 65537)
    e = 65537  # 公钥指数
    d = mod_inverse(e, phi_n)  # 私钥指数 - 求模反元素
    
    return (e, n), (d, n)

def encrypt(message, public_key):
    """加密"""
    e, n = public_key
    encrypted_message = [pow(ord(char), e, n) for char in message]
    return encrypted_message

def decrypt(encrypted_message, private_key):
    """解密"""
    d, n = private_key
    decrypted_message = ''.join([chr(pow(char, d, n)) for char in encrypted_message])
    return decrypted_message

# 测试 RSA 加密解密
public_key, private_key = generate_keys(bits=8)
message = "Hello RSA"
print("原始消息:", message)

# 加密
encrypted_message = encrypt(message, public_key)
print("加密后的消息:", encrypted_message)

# 解密
decrypted_message = decrypt(encrypted_message, private_key)
print("解密后的消息:", decrypted_message)

代码中的公钥指数补充：关于公钥指数e常用65537，可以加快加密过程
- 65537 是一个费马素数（Fermat prime），形式为 $2^{2^{k}} + 1$ ，k = 4时， $2^{16} + 1 = 65537$ 。费马素数的二进制较为特殊，如65537的二进制为10000000000000001，在计算乘法和模运算可以通过快速指数算法（如快速幂算法）进行优化，从而显著提高计算效率
- 快速幂算法：将较大的幂运算拆成多个较小的幂运算的乘积，循环查看指定位数是否为1后进行连乘，详细内容可查看快速幂open in new window。以对65537求幂为例 $a^{65537} = a^{65536} \times a^{1} = a^{2^{16}} \times a^{2^{0}}$
```
def binpow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a
        a = a * a
        b >>= 1
    return res
```

非对称加密算法

# 简介

# DH

# 消息传递流程

# API 使用流程

# 代码

# RSA

# 消息传递流程

# 工作模式与密钥长度

# 涉及到数学内容

# 实现流程

# 原理

# 代码

简介

DH

消息传递流程

API 使用流程

代码

RSA

消息传递流程

工作模式与密钥长度

涉及到数学内容

实现流程

原理

代码