软件开发者如何创建属于你自己的简易RSA算法

介绍

密码学的一个关键发展是公钥（或非对称）密码系统的引入。这些系统依赖于密钥对：其中一个是公钥（每个人都知道），另一个是私钥（只有特定用户知道）。公钥用于加密消息（任何人都可以这样做，因为它是公开的），而私钥用于解密消息。这与对称加密形成对比，在对称加密中，只有一个密钥可以执行这两种操作（并且是 20 世纪 70 年代之前唯一可用的方法）。这意味着需要一个安全通道来交换/确定密钥，以便只有某些特权方才能进行密码学操作。实时密码学和我们所知的互联网是由公钥密码学实现的。根据所使用的方法，密钥可以是数字（例如，RSA），或者，在椭圆曲线密码学（ECC）的情况下，可以是一个数字和一个椭圆曲线上的点。加密和解密的算法也是公开的，因此整个系统的安全性取决于永远不泄露私钥（这被称为 克尔克霍夫原则）。非对称密码学在许多应用和协议中起着 фундаментальную роль，提供数据和电子通信的保密性、真实性和不可否认性。互联网标准，如 TLS、SSH 和 PGP 都依赖于这种密码学原语。

RSA（以 Rivest、Shamir 和 Adleman 命名）是最早的公钥密码系统之一，也是使用最广泛、最容易理解和实现的系统之一 (1)。我们今天将讨论 RSA 的工作原理、如何实现其基本结构，以及该系统的一些陷阱和弱点（这些陷阱和弱点导致它在与 ECC 的竞争中失利）。

我们将在下面使用一些数学和密码学概念；你可能想要先回顾我们的数学 速成工具包。

RSA 的工作原理

非严格的数学思想

RSA 依赖于四个关键步骤：密钥生成、密钥分发、加密和解密。我们不会按顺序描述它们中的每一个，而是将概述整个过程，然后再深入细节。基本思想如下：给定一个数字 $n$（公共），存在两个数字 $e$（公钥，用于加密）和 $d$（私钥，用于解密），它们是乘法逆元（也就是说，$d \times e = 1$，所以 $e = d^{-1}$）。给定一条消息 $M$，表示为 $0$ 和 $n-1$ 之间的数字，加密 $E(M)$ 通过取 $M$ 的 $e$ 次幂来完成，

$E(M) = M^e$

解密通过类似的方式完成，即取加密消息的 $d$ 次幂，

${E(M)}^d = (M^{e})^d = M^{d \times e} = M$ 当然，如果你从高中数学的角度思考，会发现几个问题，首先也是最明显的是，知道了 конечно, если вы думаете с точки зрения школьной математики, возникает несколько проблем, начиная с очевидного факта, что зная $e$ 允许你计算 позволяют вам вычислять $d$，并且加密的消息可能会变成一个非常大的数字（并占用大量空间）。这就是数论和模运算发挥作用的地方。

步骤

现在让我们更详细地了解每个步骤，以及我们如何获得一些非常难以破解的东西，除非你知道密钥。

1. 密钥生成：

• 选择大的随机素数 $p$ 和 $q$ 并保持秘密（2）。
• 计算 $n = p \times q$。 $n$ 作为公钥参数的一部分发布。
• 计算 Euler函数 $\phi(n) = (p-1) \times (q-1)$ 的值并保持秘密（3）。
• 选择一个整数 $1 < e < \phi(n)$，它与 $\phi(n)$ 互质（也就是说，它们的唯一公约数是 1）。$65537 = 2^{16} + 1$ 是一个典型的选择，因为它提供了相当快的加密和安全性。另一个流行的选择是 $3$，但众所周知，这在许多设置中会导致不安全的加密。
• 计算 $d = e^{-1} \mod \phi(n)$，也就是说，$d$ 是 $e$ 模 $\phi(n)$ 的乘法逆元（4）。这可以通过取 $e$ 的幂来完成，也可以使用 扩展欧几里得算法 以更快的方式完成。

2. 密钥分发：如果两个人 Alice 和 Bob 想要通信，每个人都会向对方发送他们的公共参数 $(e_A, n_A)$ 和 $(e_B, n_B)$。当然，会出现一个显而易见的问题，Bob 和 Alice 如何知道他们得到的是彼此的公共参数，而不是其他人的（臭名昭著的中间人攻击）？
3. 加密：

• 使用商定的填充方案将消息 $P$ 转换为整数 $1 < m < n$。
• 计算 $E(m)$，即 $E(m) \equiv m^e \pmod{n}$。

4. 解密：

• 通过执行 $E(m)^d \equiv m \pmod{n}$ 来计算消息 $m$。
• 反转加密的第一步，将 $m$ 转换为 $P$。

计算示例

让我们选择一个玩具模型来说明如何进行计算（当然，没有真正的模型使用这些简单的数字，因为它很容易被破解，即使是通过暴力尝试）。

1. 我们选择两个随机素数 17 和 19。
2. $n = 17 \times 19 = 323$
3. 我们计算 $\phi(323) = 288$ 或 $\lambda(323) = 144 = lcm(16, 18)$。
4. 我们选择 $e = 5$（记住，小的 $e$ 不是一个好的选择）。我们不能选择 $3$，因为 $3$ 与 $\phi(n) = 288 = 2^5 \times 3^2$ 不互质。
5. $d = 5^{11} \equiv 29 \pmod{144}$。（我们使用 Carmichael 的Euler函数，因为它更快）。让我们检查一下我们是否做对了：$5 \times 29 = 145 \equiv 1 \pmod{144}$，因为 $145 = 1 \times 144 + 1$。一个更快的替代方法是使用扩展欧几里得算法。
6. 我们的消息是 11。因此 $E(11) = 11^5 \equiv 197 \pmod{323}$。
7. 我们现在尝试解密 $197^{29} \equiv 11 \pmod{323}$

幕后的数学原理

这个技巧之所以有效，是因为我们有两个数字 $d$ 和 $e$，使得 $d \times e \equiv 1 \pmod{\phi(n)}$。换句话说，$d \times e = k\phi(n) + 1$。如果我们执行加密，然后进行解密，我们得到

${(m^e)}^d = m^{e \times d} = m^{1 + k\phi(n)} = m \times (m^{\phi(n)})^k \equiv m \pmod{n}$ 最后一步是Euler定理的结果，因为 Последний шаг является следствием теоремы Эйлера, так как $a^{\phi(n)} \equiv 1 \pmod{n}$，给定，给定 a и и $n$ 互质。

安全问题

RSA 存在几个问题，尤其是在未正确实施时。生成随机素数时，这些素数必须是真正随机的（因此，始终使用适用于密码学应用程序的伪随机生成器）。许多攻击依赖于获得公共参数 $n$ 的因式分解。如果我们能找到 $p$ 或 $q$，那么我们就能得到另一个，并且我们可以计算 $\lambda(n)$ 或 $\phi(n)$，$e$ 的乘法逆元，它不是别的，正是私钥。例如，如果 $p$ 和 $q$ 的长度非常相似，我们知道 $p \approx q \approx \sqrt{n}$，并且费马因式分解 как два квадрата $n=a^2-b^2$ 是可能的。很容易看出 это возможно. Легко видеть, что $a^2-b^2=(a+b)\times (a-b)$ 因此我们同时拥有两个数字。如果我们知道许多不同的 итак, у нас есть оба числа. Если мы знаем много разных $n$，我们可以尝试通过查找最小公约数来破解因式分解。例如，假设我们知道 для примера, скажем, мы знаем, что для двух человек $n_1$ и и $n_2$，他们共享一个公因子，他们 разделяют общий фактор $p$。那么我们有 Тогда у нас есть $p=gcd(n_1,n_2)$，并且 благодаря 欧几里得算法，gcd 可以非常快地找到（在多项式时间内）。这样，我们就破坏了两个帐户的安全性。

即使不知道因式分解，其他方法也有效。在低指数 $e$（如 $3$）的情况下，可能会发生 $M^3$ 不超过模数 $n$，因此可以通过取立方根轻松破解。另一方面，如果私钥很小，你可以使用 Wiener 的 或 Boneh-Durfree 的攻击 并获取密钥。以下 链接 上收集了几种策略。你可以构建你自己的因式分解方法，也可以尝试使用开源工具，如 SageMath，看看执行复合数的因式分解有多么容易。

实现一些关键函数

为了能够使用 RSA 执行操作，我们需要首先实现一些算术运算并定义字段元素。我们将展示如何在 Rust 中实现其中一些。

use::std::ops::{Add, Sub, Mul, Div};
pub struct FieldPoint {
    num: u128,
    prime: u128,
}

第一行导入标准库（特别是加法、减法、乘法和除法的运算），这将允许我们使用我们需要在模运算中使用的表达式来覆盖这些运算符。

在第二行中，我们定义了一个名为 FieldPoint 的公共结构，它有两个字段：num（范围从 0 到素数的数字）和 prime（这将给出我们的大小，并且我们将执行所有模素数运算）。对于实际应用，我们需要用适当的变量替换无符号整数 u128，这些变量允许我们存储大整数。

我们现在可以在 FieldPoint 上实例化一些方法，例如如何创建一个方法，或者如何乘除字段元素。

impl FieldPoint {
    pub fn new(num: u128, prime: u128) -> FieldPoint {
        if num > prime {
            panic!("Not a valid input for a field point, num should be nonnegative and less than prime, obtained {}", num);
        } else {
            FieldPoint {num:num, prime:prime}
        }
    }
}

方法是按照关键字 impl 和 struct 的名称定义的。我们有一个 FieldPoint 的构造函数，它接受两个无符号 u128 整数。

为了定义加法，我们可以用这种方式为 FieldPoint 实现 Add 特性

impl Add for FieldPoint {
    type Output = Self;
    fn add(self, other: Self) -> Self {
        if self.prime == other.prime {
            FieldPoint {num: (self.num + other.num).rem_euclid(self.prime), prime: self.prime}
        } else {
            panic!("Cannot add these field points, different prime values {},{}",self.prime,other.prime);
        }
    }
}

加法只是简单地添加 num 字段，如果结果超过模数 prime，我们取总和与模数之间的欧几里得除法的余数。

乘法的工作方式类似

impl Mul for FieldPoint {
    type Output = Self;
    fn mul(self, other: Self) -> Self {
        if self.prime == other.prime {
            FieldPoint {num: (self.num*other.num).rem_euclid(self.prime), prime: self.prime}
        } else {
            panic!("Cannot multiply these field points, different prime values, {},{}",self.prime,other.prime);
        }
    }
}

我们需要定义 FieldElement 的幂。我们可以通过平方和取余数以相当有效的方式执行此操作：

pub fn power(&self,index: u128) -> Self {
        if index == 0 {
            FieldPoint {num: 1u128, prime: self.prime}
        } else {
            let mut aux=index.rem_euclid(self.prime-1u128);
            let mut acc: u128 = 1;
            let mut base: u128 =self.num;
            while aux >0{
                if aux%2 == 0 {
                    base = (base*base).rem_euclid(self.prime);
                    aux=aux/2u128;
                } else {
                    acc = (acc*base).rem_euclid(self.prime);
                    aux=aux-1u128;
                }
            }
            FieldPoint {num: acc, prime: self.prime}
        }

    }

幂函数接受一个 FieldElement 和一个 u128 类型的 index。如果索引为 $0$，则结果是微不足道的，我们输出一个 FieldElement，其中 num 等于 $1$。在任何其他情况下，我们首先减少 index（如果 index 超过 prime，我们可以取 index 除以 prime-1 的余数 - 当模数为质数时，这有效，因为Euler定理表明 $a^{p-1} \equiv 1 \pmod{p}$-。一个更好的版本是用 $\phi(n)$ 减少 index），并将其存储在 aux 中。我们还定义一个变量来计算结果 acc 和 base，我们将在其中重复地平方并取 num 的余数。

我们现在专注于平方和结果的更新：

while aux >0{
    if aux%2 == 0 {
        base = (base*base).rem_euclid(self.prime);
        aux=aux/2u128;
    } else {
        acc = (acc*base).rem_euclid(self.prime);
        aux=aux-1u128;
    }
}

我们将减少存储在 aux 中的索引：如果它是偶数（第一个条件 - 这可以通过检查 aux 的最后一位来更快地检查 -），我们将 aux 除以 2 并将 base 更新为它的平方的余数。如果它是奇数，那么我们继续更新 acc 中的结果并将 aux 减 1 （这意味着在下一步中它将是偶数）。

为了让我们自己信服，让我们举一个简短的数值例子，同时我们遵循这些指示。让我们将 prime 设为 11，将 num 设为 4，将 index 设为 39。

1. 我们将 aux 设置为 39 和 10（这也是 $\phi(11)$）的余数相等。我们得到 aux=9。
2. 由于 $9>0$，我们进入 while 循环。$9$ 是奇数，所以 acc=9 和 aux=8。
3. aux 是偶数，所以 base=4*4=16；我们必须通过取除以 11 的余数来减少这个数，所以 base=5 和 aux=4。
4. aux 是偶数，所以 base=5*5=25，我们得到 base=3 和 aux=2。
5. aux 再次是偶数，base=9 和 aux=1。
6. aux 是奇数，我们得到 acc=9*4=36->3 和 aux=0。
7. 由于 aux=0，我们跳出 while 循环，该函数返回 FieldPoint（num=3,prime=11）。

我们需要的另一个函数是最大公约数。该算法的一个非常简单的形式如下所示

pub fn gcd(a: u128,b: u128) -> u128 {
    let mut r0: u128=b;
    let mut r1: u128=a;
    if a>b {
        r0 = b;
        r1 = a;
    }
    let mut r2: u128 = 1;
    while r2 >0 {
        r2=r1.rem_euclid(r0);
        r1=r0;
        r0=r2;
    }
    r1
}

我们取两个数 $a$ 和 $b$，然后输出它们的最大公约数。如果 $a$ 小于 $b$，我们将被除数初始化为 $b$，将除数初始化为 $a$（这使我们用较小的数截断较大的数）；否则，我们反转选择。接下来，我们开始通过 $r0$ 减少 $r1$，然后更改角色（因为 $r2$ 小于 $r0$）。一个数值示例有助于说明这些要点：

1. 取 a=12, b=8（我们可以立即看到正确的答案是 4，但这有助于我们了解这个算法是如何找到它的）。
2. $r0=8$，$r1=12$，$r2=1$，所以我们立即进入 while 循环。
3. $r2=4$，因为 12 除以 8 的余数是 4。
4. $r1=8$ 和 $r0=4$。
5. 由于 $r2$ 不为零，我们将其保存在循环中。
6. $r2=0$（因为 8 可以被 4 整除），$r1=4$ 和 $r0=0$。
7. 现在 $r2=0$，所以我们退出循环，该函数输出 gcd=4。

借助前面的函数，可以轻松计算 Carmichael 的Euler函数：

pub fn lambda(p: u128,q: u128) -> u128 {
    let greatest_div: u128=gcd(p-1,q-1);
    (p-1)*(q-1)/greatest_div
}

可以借助扩展欧几里得算法轻松计算逆元：

pub fn inversion(a:i128,b:i128) -> i128 {
    let mut t=0i128;
    let mut r=b;
    let mut t1=1i128;
    let mut r1=a;
    while r1 != 0i128 {
        let q=r.div_euclid(r1);
        (t,t1)=(t1,t-q*t1);
        (r,r1)=(r1,r-q*r1);
    }
    if r != 1i128 {
        return 0i128;
    }
    if t<0{
        t=t+b;
    }
    t
}

让我们看看它在一个简单的例子中的工作方式：a=3, b=5；3（模 5）的倒数是 2。该算法从以下步骤开始：

1. t=0, t1=1, r=5, r1=3。
2. 因为 $r1=3 \neq 0$ 我们循环执行：q=1, t=1, t1=0-1*1=-1, r=3, r1=2。
3. $r1 \neq 0$, q=1, t=-1, t1=1-1*(-1)=2, r=2, r1=1。
4. $r1 \neq 0$, q=2, t=2, t1=-1-2*2=-5, r=1 和 r1=0。
5. $r1=0$，所以这个函数输出 t=2，这是正确的答案。

我们可以使用 米勒-拉宾素性测试 来测试素性。给定一个奇数 $n$，我们可以将其写为 $n = 2^r \times d + 1$，其中 $r>0$，而 $d$ 是一个奇数。如果 $d$ 是素数，那么：

$a^d \equiv 1 \pmod{n}$

$a^{2r \times d} \equiv -1 \pmod{n}$ 如果如果 n 是质数，那么它满足费马小定理，并且 n 是质数，那么它满足费马小定理，并且 1 的唯一平方根是 единственными квадратными корнями 1 являются -1 и и 1. 如果没有满足上述任一条件， Если ни одно из условий не выполнено, n 不是质数（如果通过了该测试，那么可以是可以 бить составным числом（в зависимости от выбора a，称为证人）。检查几个，可以 нам убедиться, что проверка прошла и для более составного числа. Проверка несколькиха позволяет нам убедиться, что проверка прошла и для более составного числа.a$ 允许我们确保测试通过了一个合数。分解很容易做到：

pub fn decompose(n: u128) -> (u128,u128) {
        let mut d: u128=n-1;
        let mut r: u128=0;
        while d%2 == 0 {
            d /= 2;
            r += 1;
        }
        (d,r)
    }

由于 $n-1$ 是偶数，我们可以重复取 2 的因子，直到 $d$ 不能再被 2 整除。可以通过查看 $n-1$ 的最后一位来更快地检查该条件。

米勒-拉宾测试的核心是（如果可能是素数，则产生真）：

fn miller_rabin(a: u128, n: u128, d: u128, r: u128) -> bool {
        let n_minus_one: u128 = n - 1u128;
        let field=FieldPoint::new(a,n);
        let mut x = field.power(d);
        let mut count: u128 =1;
        if x.num == 1 || x.num == n_minus_one {
            return true;
        }
        while count < r {
            x = x.power(2u128);
            if x.num == n_minus_one {
                return true;
            }
            count += 1u128;
        }
        false
    }

如果你有一个合数并尝试了几个证人，它很可能会至少在一个证人处失败（并在第一个地方停止），这样我们就可以丢弃这个数。

总结

我们介绍了 RSA 的基础知识，并讨论了它的数学基础。我们还给出了一些它可能遭受的攻击，尤其是在实现不正确时。最后，我们给出了一些构建 RSA 的基本函数（例如模幂运算、计算逆元和通过 Rabin-Miller 测试检测素性）。即使你可以从头开始构建你自己的 RSA，也是不可取的，因为它可能容易受到几种攻击（当然，除非它实现得非常好）。

笔记

(1) 即使你可以非常快速地编写代码，也不能保证你的实现对现实生活有用。有几件事需要检查，并且应该尝试遵循标准。此外，你应该了解密码学并理解一些底层数学)。

(2) 出于安全原因，$p$ 和 $q$ 应该有不同的位数（除非你希望你的系统容易受到 费马因式分解）的攻击），并且选择应该是真正随机的（小心不适用于密码应用程序的伪随机生成器，它们是灾难的配方的一部分）。

(3) 如果你想要更好的东西，请计算 Carmichael 的Euler函数 $\lambda(n) = lcm(q-1, p-1)$，其中 $lcm$ 代表 $q-1$ 和 $p-1$ 的最小公倍数。每当出现 $\phi$ 时，你都可以用 $\lambda$ 替换它。

(4) 这与说 $d \times e - 1$ 可以被 $\phi(n)$ 整除或 $d \times e = k\phi(n) + 1$ 对于某个整数 $k$ 相同。Euler定理 指出，如果 $a$ 和 $n$ 互质，则 $a^{\phi(m)} \equiv 1 \pmod{m}$。

如果我们取 $m = \phi(n)$ 和 $a = e$，我们看到 $e \times e^{\phi(\phi(n))-1} \equiv 1 \pmod{\phi(n)}$，$d = e^{\phi(\phi(n))-1}$，这意味着可以通过执行 $e$ 的幂来计算 $d$。

• 原文链接： blog.lambdaclass.com/how...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～