RSA加密算法数学原理

RSA加密

符号说明

MOD

此符号有两个含义由于网上资料对此符号的混用，故特此说明

同余符号给定正整数m，如果两个整数a和b满足a-b能被m整除，即m|(a-b)，那么就称整数a与b对模m同余，记作a≡b(mod m)
取余符号 a mod b = c 表示整数a除以整数b所得余数为c

gcd()

g c d (a, b) = a 与 b 的 最 大 公 因 数

RSA加解密方法

欲加密明文m

选择两个大质数p和q
计算n=p*q，安全要求n至少为1024位长
计算φ(n)=(p-1)(q-1)
选择公钥e，满足1≤e＜φ(n)，gcd(e，φ(n))=1 （gcd最大公约数）
选择私钥d，满足于e*d≡1(mod φ(n) )

加密传递e、n给对方，加密明文m为c方法如下

c = m^{e} mod n

解密已知d、n时，将密文c解密为明文方法如下

m = c^{d} mod n

数学原理

欧拉函数 φ(n)的计算

定义：φ(n) 表示在小于等于 n 的正整数之中，与 n 构成互质关系的数的个数。

如果 n = p * q，p 与 q 均为质数，则

φ (n) = φ (p q) = φ (p - 1) φ (q - 1) = (p - 1) (q - 1)

明白了对于任意数n的φ(n)的计算方法即可得出上述结论

对于任意数n的φ(n)的计算

再说一遍：φ(n) 表示在小于等于 n 的正整数之中，与 n 构成互质关系的数的个数。

1~N共有N个数，去掉其中N的因数，剩下的就是与 n 构成互质关系的数。由此即可求出φ(n) 。

先对N进行质因数分解：

N = p_{1}^{c_{1}} p_{2}^{c_{2}} p_{3}^{c_{3}} \dots p_{m}^{c_{m}}

1~N中，任一质数p的倍数的个数为[N/p]取整，另一质数q的倍数的个数为[N/q]取整。

1~N中除去p与q的倍数。剩下的，与 n 构成互质关系的数的，个数为

N - \frac{N}{p} - \frac{N}{q} + \frac{N}{p q} = N \cdot (1 - \frac{1}{p}) (1 - \frac{1}{q})

PS：因为pq的倍数被多去了一次，所以要加上[N/pq]取整。使用了容斥原理。

由质因数分解的定义可得，N的全部因数为

p_{1} p_{2} p_{3} \dots p_{m}

有

\begin{aligned} φ (N) = N - \sum_{i = 1}^{m} \frac{N}{p_{i}} + \sum_{1 \leq i < j \leq m} \frac{N}{p_{i} p_{j}} - \sum_{1 \leq i < j < k \leq m} \frac{N}{p_{i} p_{j} p_{k}} + \dots + (- 1)^{m + 1} \frac{N}{p_{1} p_{2} \dots p_{m}} \end{aligned}

化简得

φ (N) = N \cdot \prod_{i = 1}^{m} (1 - \frac{1}{p_{i}})

上述方法的python实现：


xxxxxxxxxx
def phi(n):
    res = n
    i = 2
    while i * i <= n:
        if n % i == 0:
            res //= i
            res *= (i - 1)
            while n % i == 0:
                n //= i
        i += 1
    if n > 1:
        res //= n
        res *= (n - 1)
    return res

python按欧拉函数定义计算任意数的欧拉函数


xxxxxxxxxx
import fractions

def phi(n):
    amount = 0
    for k in range(1, n + 1):
        if fractions.gcd(n, k) == 1:
            amount += 1
    return amount

公钥私钥的生成

公钥的选择条件 gcd(e，φ(n))=1 保证了私钥d的存在，既e的逆元存在模φ(n)

为什么呢，需要理解模的逆元这个概念

模的逆元

定义：模m意义下，e与m互质时，存在k, 有de=km+1既de≡1(mod m )，则称d为e的逆元

逆元存在的充要条件

模m意义下，e的逆元存的冲要条件就是

g c d (e ， m) = 1

证明则需要使用辗转相除法的知识，见下文

辗转相除法

也叫欧几里得算法，对于e、φ(n)有s、d，有下式

\gcd (Φ (n), e) = s \cdot Φ (n) + d \cdot e

当 gcd(e，φ(n))=1时，上式为

1 = s \cdot Φ (n) + d \cdot e

可写成下式，后文的证明需要使用此式

d \cdot e = 1 + s \cdot Φ (n)

证明解密是加密的逆过程

当我们知道d、n可对密文c进行如下操作得到明文m。证明解密是加密的逆过程即证明下式成立

m = c^{d} mod n

证：

考虑到

c = m^{d} mod n = (c^{d} mod n)^{e} mod n

对于c可进行如下代换

c = (m^{e} + k_{1} n)

将上式带入后有

右 式 = c^{d} mod n = (m^{d} + k_{1} n)^{d} mod n

右 式 = (\sum_{i + j = d} m^{i e} (k_{1} n)^{j}) mod n

= (m^{e d}) mod n

对于ed有下式

d \cdot e = 1 + s \cdot Φ (n)

带入右式有

右 式 = (m^{e d}) mod n = m m^{s \cdot Φ (n)} mod n

其中，由快速幂取模（后文有解释）有

m^{s \cdot Φ (n)} mod n = \prod_{i = 1. . s} (m^{Φ (n)} mod n) mod n

欧拉定理（后文有解释）得出

m^{φ (n)} mod n = 1

带入后右式有

右 式 = m \cdot 1 mod n = m mod n

由于0≤m<n则右式有

右 式 = m mod n = m

证毕

证明加密是解密的逆过程同理可证

快速幂取模

公式：

(a \times b) mod m = ((a mod m) \times (b mod m)) mod m

证明：

这里，a、b和m都是整数，我们假设a和b的模除以m的结果分别为A和B，那么根据取模的定义我们有：

a = k m + A (A < m)

b = n m + B (B < m)

我们把这两个表达式带入到等式左边得到：

(a \times b) mod m = (k m + A) (n m + B) mod m = (k n m ² + (k B + n A) m + (A B)) mod m = A B mod m

然后，再看一下等式的右边：

((a mod m) \times (b mod m)) mod m = (A B) mod m

证毕

欧拉定理

对任何两个互质的正整数a, m（即 gcd(a,m) = 1），m＞2，有m

a^{φ (m)} \equiv 1 (mod m)

1 = a^{φ (m)} mod m

证明：

欧拉定理是数论中的一个重要定理，由著名数学家欧拉提出。欧拉定理可以表示为：如果a和n是互质的正整数，那么 a^(φ(n)) ≡ 1 (mod n)，其中φ(n) 是欧拉φ函数，表示小于n并且与n互质的正整数数量。

证明：

首先，我们考虑一个集合S，这个集合包含了所有小于n并且与n互质的正整数。记φ(n)=m。

然后，我们考虑另一个集合T，它是由a乘以集合S的每个元素并且对n取模得到的。根据a和n互质，我们知道这样得到的集合T的元素是不重复的，并且与集合S一一对应。记作

S = {x_{1}, x_{2}, . . ., x_{m}}

T = {y_{1}, y_{2}, . . ., y_{m}}

y_{i} \equiv a x_{i} (mod n)

我们考虑集合S的元素的乘积与集合T的元素的乘积，并且都对n取模，由于S和T是一一对应的，它们的乘积应该相等，即有：

x_{1} x_{2} . . . x_{m} \equiv y_{1} y_{2} . . . y_{m} (mod n) \equiv a x_{1} a x_{2} . . . a x_{m} (mod n)

x_{1} x_{2} . . . x_{m} \equiv a^{m} x_{1} x_{2} . . . x_{m} (mod n)

因为等式左边和n互质，我们可以得到：

1 \equiv a^{m} (mod n)

因为m=φ(n)

证毕

本文基于 VoxCeleb1 语音数据集，探索了通过语音特征提取与聚类分析来识别说话人身份的可行性。文章首先介绍了语音数据的聚类任务及其意义，并对比了两种常见的语音特征——MFCC 和 Fbank，指出 MFCC 更具代表性。随后，探讨了降维方法 PCA 和 t-SNE 的应用场景与效果，认为 t-SNE 在保留语音结构方面更优。接着，对三种主流聚类方法（KMeans、DBSCAN、层次聚类）进行了评估，发现 KMeans 在 MFCC + t-SNE 组合下聚类效果最佳，并提供了相应的数据支持。此外，文章还分析了每个说话人语音在聚类中的表现差异，揭示语音聚类并非绝对精准，而是受特征、样本量、噪声等因素影响。最后提出了未来改进的方向，如使用深度学习特征、优化降维参数、增加样本量等，以为进一步提升语音聚类的效果和实用性。