标签：Applied ... 加密 Cryptography bmod RSA varphi 非对称 mathbb

非对称加密(RSA)

• 非对称加密(RSA)
  • 非对称加密系统（Asymmetric Cryptosystems）
  • 数字签名（Digital Signature）
  • RSA加密系统
    • 陷门函数（"Trap door" one-way function）
    • RSA的正确性
      • 欧拉定理(Euler's Theorem)
      • 欧拉函数(Totient function) $\varphi (n) $
      • 费马小定理（Fermat's little theorem）
    • RSA的安全性

非对称加密系统（Asymmetric Cryptosystems）

非对称加密系统（公钥用于加密，私钥用于解密）：

\[D_{kRB}(E_{kUB}(m))=m \]

RSA加密算法是首个非对称加密算法，由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。

本节主要从以下几方面进行学习：

• RSA
• Using RSA in practice
• Applications

数字签名（Digital Signature）

非对称加密系统的应用之一

Alice利用她的私钥(\(k_{RA}\))加密签名，Bob用Alice的公钥(\(k_{UA}\))进行解密，证实该消息确实是由Alice本人发送的。

\[E_{kUA} (D_{kRA}(m)) = m \]

RSA加密系统

陷门函数（"Trap door" one-way function）

在理论计算机科学和密码学中，陷门函数是一种在一个方向上很容易计算，但在没有特殊信息的情况下很难在相反方向上计算（寻找它的逆）的函数，称为“陷门”。陷门函数是单向函数的一种特殊情况，广泛用于公钥密码学中。Diffie & Hellman (1976)创造了这个术语。已经提出了几个函数类，很快就发现陷门函数比最初想象的更难找到。

RSA是第一个具有该属性的加密系统。

RSA Cryptosystems names after Rivest, Shamir and Adleman is the most famous asymmetric cryptosystem used worldwide.
It works as follows:

• The public key is a pair of 2 numbers: \(k_U = (e; n)\) where \(n = p · q\) the product of 2 large prime numbers and \(e\) is a secret number.
• The secret key is a pair of 2 numbers: \(k_R = (d; n)\) where \(n\) is the modulus as before and \(d\) is a secret number.
• To perform encryption fo some message \(m\):
  \[E_{k_U} (m) = m^e \bmod n \]

• To perform decryption on a ciphertext \(c\) using the secret key \(k_R\):
  \[D_{k_R}(c) = c^d \bmod n \]

如何选择\(e, d, n\)的值？

RSA的正确性

RSA正确即需证明一条消息能够加密解密后复原，则需要满足：

\[D_{k_R}(c) = c^d \bmod n = (m^e \bmod n)^d \bmod n = m^{ed} \bmod n = m \]

即我们的目标是选择合适的 \(e,d,n\) ，使其满足：

\[\forall m \in \mathbb{Z}, m^{ed - 1} \equiv 1 \bmod n \]

如何选择合适的 \(e,d,n\)，首先需要知道欧拉定理(Euler's Theorem)

欧拉定理(Euler's Theorem)

\[if \ \ gcd(a, n) = 1 \\ a^{\varphi(n)} \equiv 1 \bmod n \]

欧拉函数(Totient function) $\varphi (n) $

在数论中，对正整数n，欧拉函数 \(\varphi (n)\) 是小于等于 \(n\) 的正整数中与 \(n\) 互质的数的数目。
如果 \(n\) 是一个质数，则 \(\varphi (n) = n - 1\) .
如果 \(n = pq\) ，并且 \(p, q\) 均为质数，则：

\[\varphi (n) = pq - 1 - (q - 1) - (p - 1) = pq - (p + q) + 1 = (p - 1)(q -1) = \varphi(p)\varphi(q) \]

---

证明欧拉定理

\[a^{\varphi (n)}\equiv 1\pmod n \]

即 \(a^{\varphi (n)}\) 与 \(1\) 在模 \(n\) 下同余；\(\varphi(n)\) 为欧拉函数。

费马小定理（Fermat's little theorem）

假如 \(a\) 是一个整数，\(n\) 是一个质数，那么 \(a^{n}-a\) 是 \(n\) 的倍数，可以表示为:

\[a^{n}\equiv a{\pmod {n}} \]

如果 \(a\) 不是 \(n\) 的倍数，这个定理也可以写成更加常用的一种形式:

\[a^{{n-1}}\equiv 1{\pmod {n}} \]

费马小定理的证明：
考虑在 \(gcd(a, n) = 1\) 时的一组数：

\[\lbrace a \bmod n, 2a \bmod n, ... , (n - 1)a \bmod n \rbrace = \lbrace r_1, r_2, ... , r_{n - 1} \rbrace \]

则 \(\lbrace r_1, r_2, ... , r_{n - 1} \rbrace\) 为集合 \(\lbrace 1, 2, ... n - 1 \rbrace\) 的重新排列，即 \(1,2,...,n-1\) 在余数中恰好出现一次。这是因为对于任意两个相异的 \(k*a(k = 1, 2,...n-1)\)，它们的差不是 \(n\) 的倍数，所以不会有相同的余数，且任一 \(k*a\) 也不是 \(n\) 的倍数，所以余数不为 \(0\)，因此：

\[1\cdot2\cdot3...(n-1) \equiv (1\cdot a)\cdot (2\cdot a)\cdot \dots \cdot ((n-1)\cdot a) \pmod n \\ (n-1)! \equiv (n-1)! a^{n-1}\pmod n\\ a^{n-1} = 1 \pmod n \]

---

至此，费马小定理为：\(a^{n-1} \equiv 1 \bmod n\)
但是我们还需要证明：\(a^{\varphi (n)}\equiv 1\bmod n\)

• Case1 : \(n\) 是一个质数，则 \(\varphi(n) = n - 1\)，利用费马小定理即可证明
• Case2 : \(n\) 不是质数，且 \(a\) 与 \(n\) 互质
  定义集合 \(\mathbb{R}\) 是与 \(n\) 互质的数 \(x(x < n)\) 的集合
  \[\mathbb{R} = \lbrace x_1, x_2, ..., x_r \rbrace \\ \mathbb{S} = \lbrace ax_1 \bmod n, ax_2 \bmod n, ... ,ax_r \bmod n \rbrace \]
  由欧拉函数的定义可知，\(\mathbb{R}\) 数组的大小就是 \(\varphi(n)\) 的值，即 \(|R| = \varphi(n)\)。
  由于 \(a\) 与 \(n\) 互质，所以不存在 \(i \neq j\) 使得 \(ax_i \bmod n = ax_j \bmod n\)，即 \(\mathbb{S}\) 数组内的元素各异，且 \(\mathbb{S}\) 数组与 \(\mathbb{R}\) 数组大小相同，数组元素最大为 \(n-1\)（因为对 \(n\) 取模），则 \(\mathbb{R}\) 数组元素也包含 \(1\) 到 \(n-1\) 的数，所以 \(\mathbb{S}\) 数组与 \(\mathbb{R}\) 数组具有相同的元素，则 \(\mathbb{S}\) 数组是 \(\mathbb{R}\) 数组的重新排列。则：
  \[\prod(R) = x_1 \cdot x_2\ ...\ x_r = ax_1 \bmod n \cdot ax_2 \bmod n\ ...\ ax_r \bmod n \\ x_1 \cdot x_2\ ...\ x_r = a^{\varphi(n)}(x_1 \cdot x_2\ ...\ x_r) \bmod n \\ a^{\varphi(n)} \equiv 1 \bmod n \]

证毕

---

再回到RSA...

RSA加密算法我们需要选择两个大的质数 \(p\) 和 \(q\)，\(p \neq q\)，计算 \(n = pq\)

• 公钥：\(k_U=(e;n)\)
• 私钥：\(k_R=(d;n)\)
• 加密函数：\(E_{k_U}(m) = m^e \bmod n\)
• 解密函数：\(D_{k_R}(m) = c^d \bmod n\)
• 可逆性（Invertibility）： \(m^{ed-1} \equiv 1 \bmod n\)

由欧拉定理：\(a^{\varphi(n)} = 1 \bmod n\)，\(a\) 与 \(n\) 互质，则我们需要找出一组 \(e\) 和 \(d\)，使得 \(k*\varphi(n) = ed - 1\)，又因为 \(n = pq\)，则 \(\varphi(n) = \varphi(p) \varphi(q) = (p-1)(q-1)\)，即上式为：

\[ed - 1 = k(p-1)(q-1) \]

由于我们希望私钥更加保密且难以被攻击者猜测，所以我们应该随机选择 \(d\) 的值（私钥中包含 \(d\) ）。而 \(e\) 则是可以公开的，实际上，\(e\) 常常被赋予一个较小的值

随机选择一个 \(d\) 使得其与 \(\varphi(n)\) 互质，则

\[de = 1 \bmod \varphi(n) \]

Q：已知 \(d\) 和 \(\varphi(n)\) 的前提下，计算 \(e\) 困难吗？
A：不困难，可利用扩展欧几里得算法（Extended Euclidean algorithm）。

Q：已知 \(e\) 和 \(n\) 的前提下，计算 \(d\) 困难吗？
A：是的，否则RSA将不具有安全性。

至此，我们说明了RSA的正确性。

RSA的安全性

给定 \(e\) 和 \(n\) 的条件下，很难找到 \(d\) 的值
对于攻击者来说，在知道 \(p\) 和 \(q\) 的前提下，很容易计算出 \(n = pq\)，而 \(n\) 的因子 \(d = e^{-1} \bmod \varphi(n)\)，其中 \(\varphi(n) = \varphi(p)\varphi(q) = (p-1)(q-1)\)

所以我们的安全性主要依靠以下两条原则：

1. 表明所有破解 RSA 的方法都可以轻松地因数分解 \(n\)
2. 证明对大数因数分解是困难的

---

通过 \(\varphi(n)\) 计算 \(p\) 和 \(q\) 比对 \(n\) 直接进行因数分解更容易吗？

\[\varphi(n) = (p-1)(q-1) = pq - (p + q) + 1 = n - (p + q) + 1 \\ p + q = n - \varphi(n) + 1 \]

我们的目标是证明在知道 \(\varphi(n)\) 的前提下，我们可以很容易找到 \(p\) 和 \(q\)

\[(p - q)^2 = p^2 -2pq + q^2 = (p + q)^2 - 4pq \\ p - q = \sqrt{(p+q)^2-4n} = \sqrt{(n-\varphi(n)+1)^2-4n} \]

则联立方程组：

\[\begin{cases} p+q=n - \varphi(n) + 1 \\ p-q=\sqrt{(n-\varphi(n)+1)^2-4n} \\ \end{cases} \]

解方程组即可求出 \(p\) 与 \(q\)。所以在知道 \(\varphi(n)\) 的前提下，很容易计算出 \(p\) 和 \(q\)。

还需说明没有比因数分解 \(n\) 更容易的方法计算出 \(d\)

\[ed = 1 \bmod \varphi(n) \\ k * \varphi(n) = ed - 1 \]

我们已知 \(e\)（公钥内包含），假设知道一种方法能够轻松地计算出 \(d\)，则我们很容易得到 \(\varphi(n)\)，则轻松地完成了对大数 \(n\) 的因数分解，很容易破解了RSA。

---

标签：Applied,...,加密,Cryptography,bmod,RSA,varphi,非对称,mathbb
From： https://www.cnblogs.com/I-am-Sino/p/16909068.html