• 基础知识
  • 1.素数
  • 2.模运算
  • 3.互质
  • 4.欧拉函数
  • 5.欧拉定理
  • 6.模反元素
• RSA

面试时被问到了RSA的原理和一些基本的攻击手段，之前接触过，但是太久没用的话，只记得大概，大部分都不记得了，所以现在重新回顾一下做个记录。

基础知识

密码学和数论之间存在强相关性，了解RSA之前需要对数论有一些基础的了解。

1.素数

如果一个自然数（大于1）的因数有且仅有 1和它本身，那么这个数被成为素数。

2.模运算

模运算也称为求余运算,即求 一个数除以另一个数的余数
如果两个整数a，b 除以 正整数m 得到的余数相同，则称a和b关于m同余，写作：

$a \equiv b \space mod \space m$

3.互质

若两个正整数a，b 除了1以外，没有其他共因素，则称a和b互质。

4.欧拉函数

给定一个正整数n，求小于等于n的正整数中，与n互质的个数，记为φ(n)

1. 如果n为质数， φ(n) = n-1
2. 如果n为质数p的k次方，φ(n)=p^k - p^(k-1)
3. 如果n可以分解为素数的乘积(例如n=abc)，则φ(n)=φ(a)φ(b)φ(c)

5.欧拉定理

如果a和n互质，那么存在以下公式成立:

a^φ(n) $ \equiv 1 \space mod \space n$

6.模反元素

如果a和n互质，一定可以找到正整数b，使得以下公式成立:

ab $\equiv 1 \space mod \space n$

RSA

对于RSA加密，步骤如下：

1. 首先你需要生成一个大数n，n=p*q且p，q均为质数。
2. 计算φ(n)，$ φ(n)= φ(p)φ(q)=(p-1)(q-1)$
3. 随机选择一个数e，满足 1 < e < φ(n) 且 e与φ(n) 互质
4. 输入明文m，得到密文c，公式：m^e $\equiv c \space mod \space n$
5. 需要求得e关于φ(n)的模反元素d，即 $ed \equiv 1 \space mod \space φ(n)$
6. 解密时，使如公式：$ c^d = (m^e)^d =$ m^ed = m^φ(n)+1 = m

因此，在进行传输时，将（n，e）作为公钥，（n，d）作为私钥。
可以看出,RSA的安全性基于n=p*q的分解难度。如果n=p * q被成功分解，在知道n，p，q，e的情况下，可以得到φ(n)，进而可以求出d，使得RSA被攻破。