RSA加密算法笔记

阮一峰RSA算法原理一
阮一峰RSA算法原理二

  • 历史 1977年三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法。一直公开被破解的秘钥长度为768位,超过768位的可认为是安全的,1024长度的非常安全,2048位的极其安全
  • 数学原理
    • 互质关系
      如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互质关系(coprime)。
    • 欧拉函数
      任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?计算这个值的方法就叫做欧拉函数,以φ(n)表示。
    • 欧拉定理
      如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:
      aφ(n)≡1(mod n)
      也就是说,a的φ(n)次方被n除的余数为1
    • 模反元素 如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。
      ab ≡ 1(mod n)
      这时,b就叫做a的”模反元素”。
  • RSA密钥生成步骤
    • 随机选择两个不相等的指数p和q 【RSA加密算法笔记】实际应用中,这两个质数越大,就越难破解。
    • 计算p和q的乘积n。 n需要转换为二进制,二进制的位数就是密钥长度,一般密钥长为1024,重要场合用2048位
    • 计算n的欧拉函数φ(n) 根据公式:φ(n) = (p-1)(q-1)
    • 随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质 实际应用中,常常选择65537。
    • 计算e对于φ(n)的模反元素d。 ed ≡ 1 (mod φ(n))
    • 将n和e封装成公钥,n和d封装成私钥。 实际应用中,公钥和私钥的数据都采用ASN.1格式表达
  • RSA算法的可靠性 一共出现p q n φ(n) e d 这几个关键数字
    d是最重要的是因为它和n组成了私钥
    (1)ed≡1 (mod φ(n))。只有知道e和φ(n),才能算出d。
    (2)φ(n)=(p-1)(q-1)。只有知道p和q,才能算出φ(n)。
    (3)n=pq。只有将n因数分解,才能算出p和q。
    所以,对n的因式分解的难度基本上等于RSA破解的难度。事实上人类已经分解的最大整数是232个十进制位,768个二进制位。比它更大的因数分解,还没有被报道过,因此目前被破解的最长RSA密钥就是768位。
  • 加密和解密
    • 加密要用公钥 (n,e) 所谓加密就是算出下式的c
      me ≡ c (mod n)
    • 解密要用私钥(n,d) 公式:cd ≡ m (mod n) m即为加密前的明文
      你可能会问,公钥(n,e) 只能加密小于n的整数m,那么如果要加密大于n的整数,该怎么办?有两种解决方法:一种是把长信息分割成若干段短消息,每段分别加密;另一种是先选择一种”对称性加密算法”(比如DES),用这种算法的密钥加密信息,再用RSA公钥加密DES密钥。
  • 私钥解密的证明 一系列数学公式【头晕】

    推荐阅读