RSA的数学基础

概要

RSA是一种非对称加密算法，非常普遍，主要涉及的数学知识

• 互质
• 欧拉函数
• 欧拉定理

互质

概念：两个正整数，除了1以外没有其他公因子（公约数）。
(补充：公因子同时能被两个数整数的整数，是这两个数的公因子，求最大公约数可以用辗转相除法
)

注意区分质数（素数prime）概念：质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

举例： 7和20，20是不是质数，但是和7是互质数。

互质相关结论：

• 任意两个质数构成互质关系，比如，13和97
• 质数和非本身倍数的数都互质，比如，13和33
• 两个数之中，大的数是质数，那么互质，比如，33和97
• 1和任意自然数互质
• p是大于1的整数，p和p-1互质，比如，23和24
• p是大于1的奇数，p和p-2互质，比如，9和7

欧拉函数

假设需要求解下面问题：
给定正整数n，小于等于n的所有正整数中，求解有多少个与n互质？
欧拉函数就能解这个问题。
(欧拉函数用希腊字母 \phi表示，棒棒糖造型的那个符号，但是这里打不出来，后续用O代替。)

结合前面互质所得到的相关结论。

• 【结论1】1和任意数互质
  O(1) = 1

• 【结论2】n是质数，n与小于它的每个数都互质
  O(n) = n - 1

• 【结论3】n是质数的k次方，n=p^k，p为质数
  O(n) = p^k - p^(k-1)
  这个公式理解起来意识是，p如果是质数，那么p的k次方，一定和p的整数倍不是互质，有共同的质因子p，其余都是和p互质。p^k 是总数，需要排除1p，2p，3p，...，p^(k-1)p，有p^(k-1)个。
  可以看出结论2是k=1的特例。

• 【结论4】如果n可以分解为两个质数乘积 n = p1 × p2，
  φ(n) = φ(p1p2) = φ(p1)φ(p2)
  证明方式是【todo: 中国剩余定理】

• 【结论5】任意一个正整数都可以写成一系列质数的乘积，得到欧拉函数通项公式：

  
  image
  

  (其中p1, p2……pn为x的所有质因数，x是不为0的整数)

【证明方式todo：剩余定理和拉格朗日定理】
理解这个公式的要领，这其实是一个概率公式，比如，x = 12，p1 = 2，p2 = 3，n = 2，第一个质因素p1 = 2，小于等于12的数字中，有多少和12有公约数p1呢，答案是有12 / p1 = 6个 。意思是，小于等于12的数字中，有 1/p1概率的数字和12不互质，那么有x*(1-1/p1)个数字与x互质。

欧拉定理

【定理】如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立（同余性质）：

image

费马小定理

【定理】
a是不能被质数p整除的正整数，则有a^(p-1) ≡ 1 (mod p)

模反元素

【定义】如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1，b就叫做a的"模反元素"。

举例：
3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {...,-18,-7,4,15,26,...}，即如果b是a的模反元素，则 b+kn 都是a的模反元素

a的 φ(n)-1 次方，就是a的模反元素

扩展欧几里得算法

todo

RSA 生成公私钥过程

• 第一步：选择随意两个不想等的质数p和q

• 第二步：计算乘积： n = p * q
  其中n的二进制长度就是密钥的长度。
  比如： p和q是61和53，n = 3233
  那么n = 110010100001，12位长度。
  通常RSA长度是1024位，或者 2048位

• 第三步： 计算n的欧拉函数
  O(n) = O(p) * O(q) = (p-1)(q-1) = 3120

• 第四步： 选择一个整数e ， 1< e< O(n)， 且和 O(n) 互质
  比如选择 e = 17，
  实际应用中，常用的e是3和65537

• 第五步：计算e对于O(n)的模反元素d
  ed = 1(mod O(n))
  这个式子等价于
  ed - 1 = k * O(n)

  所以：
  ed - kO(n) = 1
  这个式子等价于对于：
  ex + O(n)*y = 1 这个二元一次方程求解。
  17 * x + 3120 * y = 1

  【求解方式是： 扩展欧几里得算法】
  可以算出一组整数解为： x = 2753，y = -15
  所以d = 2753。

• 到这里所有的解就完成了
  公钥：（n，e）-->（3233， 17）
  私钥： （n，d）--> （3233， 2753）

RSA 不可破解原因

1 已经知道了 n和e，可以破解d么？
ed = 1 （ mod O(n)）
那么 ed = k* O(n) + 1。
d = （ k*O(n) + 1 ）/ e

2 上面式子需要求O(n)，可解就能破解d
O（n） = (p-1)(q-1)， n = p*q
所以只要知道了p和q，就能知道O(n)

3 但是：大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。所以认为n足够大，当前的计算机算力，n = p*q分解不出来。
因此目前被破解的最长RSA密钥就是768位。

RSA加密解密有效性证明

• 加密 ：c = m^e % n
• 解密 ：m = c^d % n

注意：
1 m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。
2 公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种"对称性加密算法"（比如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥。

• 证明
  c = m^e % n
  那么： c = m^e - kn
  两边取 d次方mod n
  c ^ d % n = （m^e - kn）^ d % n
  kn作为任意乘因子，%n都等于0
  （m^e - kn）^ d % n = m^ed % n
  ed = k* O(n) + 1
  所以
  c ^ d % n = m^(k*O(n)+1)%n

1 假设 m 和 n 互质，欧拉定理
m ^ O(n) = 1 （mod n）
所以
m^(kO(n)+1)%n = (m^(kO(n)) * m) % n（取模的乘法结合律）
=( ([m^{O(n)%n*....*m}O(n)%n] %n%n...%n ) * (m %n ) ) %n
= (m % n ) %n
= m % n
= m
解密完成
2 假设m与n不互质
n = p * q，那么 m = h * p 或者 h * q
假设m = h * p，且 m和 q 一定 互质
所以：
m ^ (O(q)) = 1 (mod n)
m ^ (q-1) = 1 (mod n)
所以：
m ^ (q-1) = k * n + 1

前面得到了式子：
c ^ d % n = m^(k*O(n)+1)%n
= { m * [m ^ ((p-1)(q-1))] ^ k }%n (带入：m ^ (q-1) = k * n + 1)
= m * [kn + 1]^（k(q-1)) %n
= m%n (m小于n)
= n