文章页面

RSA加密算法

des 自古以来，人类就试图保护信息的安全——从古埃及的象形文字，到凯撒的简单移位密码，再到二战中的恩尼格码机，每一次密码的创新都影响着战争、政治乃至文明的发展
进入信息时代,电子通信无处不在,我们需要一种全新的方法来保证信息在公开网络中仍然安全传输.1977年,三位数学家——Ron Rivest、Adi Shamir 和 Leonard Adleman——提出了 RSA算法,它不仅是非对称加密的奠基石,也标志着密码学从秘密传输走向公钥时代的历史性飞跃
今天，我们将从数学的视角，追溯 RSA 的诞生逻辑：质数、欧拉函数、公钥与私钥。你将看到，正是这些古老而简单的数学概念，支撑起现代数字世界的安全与信任

算法推理

我实现的是纯RSA不包含密钥填充，密钥填充在以后做密码学库再完整实现

算法思想

大质数的乘积难以分解(质因数分解困难)
模指数运算的逆运算关系

算法步骤

选择两个大质数 𝑝,q
- 用来生成密钥
计算 n = p * q
- n作为模数
计算欧拉函数 ϕ(n)=(p−1)(q−1)

Note

小于 n 的正整数中,有多少个和 n 互质(gcd = 1)
ϕ(n)=#{k∈[1,n−1]∣gcd(k,n)=1}
各位具体想学习的话可以问AI
选择公钥指数(e)
- 1 < e < ϕ(n),并且gcd(e,ϕ(n)) = 1
- 常用的是65537
计算私钥d
- 使得 𝑑 × 𝑒 ≡ 1 ( mod 𝜑(𝑛))
- 也就是 𝑑 = 𝑒^(−1) mod 𝜑(𝑛)
加密/解密
- 加密 => c = m^e mod n
- 解密 => m = c^d mod n

简略代码实现

package main

import (
    "crypto/rand"
    "fmt"
    "math/big"
)

// 简单生成RSA密钥
func generateRSAKey() (n, e, d *big.Int) {
    // 选择两个质数
    p, _ := rand.Prime(rand.Reader, 64) // 用小位数方便演示
    q, _ := rand.Prime(rand.Reader, 64)
    n = new(big.Int).Mul(p, q)

    // 计算φ(n)
    p1 := new(big.Int).Sub(p, big.NewInt(1))
    q1 := new(big.Int).Sub(q, big.NewInt(1))
    phi := new(big.Int).Mul(p1, q1)

    // 选择公钥 e
    e = big.NewInt(65537)

    // 计算私钥 d
    d = new(big.Int).ModInverse(e, phi)

    return
}

func encrypt(m, e, n *big.Int) *big.Int {
    c := new(big.Int).Exp(m, e, n)
    return c
}

func decrypt(c, d, n *big.Int) *big.Int {
    m := new(big.Int).Exp(c, d, n)
    return m
}

func main() {
    n, e, d := generateRSAKey()
    fmt.Println("n =", n)
    fmt.Println("e =", e)
    fmt.Println("d =", d)

    // 测试加解密
    message := big.NewInt(42)
    cipher := encrypt(message, e, n)
    fmt.Println("密文:", cipher)
    plain := decrypt(cipher, d, n)
    fmt.Println("解密后:", plain)
}

RC4加密算法 S-DES密码