RSA 概念

RSA简介及证明 #

RSA(Rivest–Shamir–Adleman)是一种公钥密码系统，被广泛应用于安全数据传输。RSA名称来自其发明者的姓名首字母缩写：Ron Rivest，Adi Shamir和Leonard Adleman。该系统通过使用两个大质数生成公钥和私钥来工作。公钥可以自由分发，而私钥必须保密

当某人想要向公钥所有者发送消息时，他们使用公钥加密消息。只有私钥的所有者才能解密消息，确保通信保持机密性

RSA被认为是非常安全的加密方法，因为它依赖于目前认为分解两个大质数乘积的因子在常规时间是不可行的事实

算法步骤 #

RSA加密算法主要步骤如下：

  1. 选择2个大质数 p 和 q，计算出模数 N = p * q，N 作为公私密钥共同的模，N可以公开，p 和 q 不公开私密保留
  2. 计算欧拉函数 φ(N) = (p - 1) * (q - 1)，φ(N) 不公开私密保留
  3. 选择一个e(1 < e < φ(N))，且 e 和 φ(N) 互质，e 可以公开
  4. 取 e 的模逆元为 d，ed ≡ 1 (mod φ(n)) ，d 不公开私密保留

公钥（可以公开）：e和N
私钥（不可以公开）：d

加密：c = m^e (mod N)，得到的 c 即为密文
解密：m = c^d (mod N)，得到的 m 即为明文

算法证明 #

RSA算法可以抽象为两个映射：加密映射 E(x) 和 解密映射 D(x)，满足

D(E(x)) = x

解密性证明如下：

D(E(x)) ≡ (E(x))^d (mod N)
        ≡ x^ed
        ≡ x^(φ(N)k)x      (根据ed的取值关系，ed = kφ(N) + 1)
        ≡ (1^k)x          (根据欧拉定理，a^φ(N) ≡ 1 (mod N))
        ≡ x

因为 p 和 q都是大素数，x 和 n = pq 不互质的概率很低，所以直接忽略了不互质的情况

Q&A #

  1. 解密性证明方法主要用到了什么定理

  2. e 的取值

  3. 算法是对数字进行加密，实际使用场景主要是文本，数字和文本怎么对应的

  4. p、q 为 大质数，构造这2个大质数复杂吗

  5. RSA算法中哪些部分是可以公开的，哪些部分是不可以公开的

  6. RSA 算法的安全性体现在哪

  7. 常说的1024/2048长度的RSA密钥，这个长度指的是什么的长度

  8. RSA 算法限制只能使用p、q两个质数吗？

Edit Edit this page