同余运算

符号约定：

a≡b(mod m)表示a,b对模m同余
(a, b)=c表示整数a和b的最大公约数为c
[a, b]=c表示整数a和b的最小公倍数为c

定理1： 整数a,b对模m同余的充要条件是 a-b能被m整除（即m

a-b）。

推论： a≡b(mod m)的充要条件是a=mt+b（t为整数）。

定理2： 同余关系具有反身性、对称性与传递性，即

1）a≡a (mod m);

2）若a≡b (mod m), 则b≡a (mod m);

3）若a≡b (mod m), b≡c (mod m)，则a≡c (mod m).

定理3： 若a≡b(mod m), c≡d (mod m),则

1）a+c≡b+d (mod m);

2）a-c≡b-d (mod m);

3）ac≡bd (mod m).

推论： 若a≡b(mod m),n为自然数，则an≡bn (mod m)。

定理4： 若ca≡cb(mod m), (c,m)=d, 且a,b为整数，则a≡b(mod m/d).

推论： 若ca=cb(mod m), (c,m)=1,且a,b为整数，则a≡b(mod m).

定理5： 若a≡b (mod m),a≡b (mod n),则a≡b(mod [m,n]).

推论： 若a≡b(mod mi), i=1,2,…,n，则a≡b (mod [m1,m2,..,mn]).

同余运算总结：

(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
(a * b) % p = (a % p * b % p) % p
结合律：
- (a + b) % p = (a % p + b % p) % p
- (a * b) % p = (a % p * b % p) % p
交换律
- (a + b) % p = (b + a) % p
- (a * b) % p = (b * a) % p
分配律
- (a+b) % p = ( a % p + b % p ) % p
- ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p
重要定理
- 若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)
- 若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)
- 若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，(a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)

欧拉定理

定义： 若对任意的自然数m，用记号ф(m)表示0,1,2,…,m-1中与m互素的数的个数，则称ф(m)为欧拉函数。

欧拉定理： 若(a,n)=1，则a^ф(n) ≡1 (mod n)

证明：

将1~n中与n互质的φ(n)个数按顺序排布：

x_1,x_2, …,x_{φ(n)}

我们考虑这么一些数：

m_1=a*x_1, m_2=a*x_2, …, m_{φ(n)}=a*x_{φ(n)}

1）这些数中的任意两个都不模n同余，因为如果有mi≡mj (mod n) （这里假定mi更大一些），就有： mi-mj=a(xi-xj)=qn，即n能整除a(xi-xj)。但是a与n互质，a与n的最大公因子是1，而xi-xj<n，因而左式不可能被n整除。也就是说这些数中的任意两个都不模n同余，φ(n)个数有φ(n)种余数。

2）这些数除n的余数都与n互质，因为如果余数与n有公因子r，那么axi=pn+qr=r(……)，axi与n不互质，而这是不可能的。那么这些数除n的余数，都在x1,x2,x3……xφ(n)中，因为这是1~n中与n互质的所有数，而余数又小于n.

由1）和2）可知，数m1,m2,m3……mφ(n)（如果将其次序重新排列）必须相应地同余于x1,x2,x3……xφ(n). 故得出：m1m2m3……mφ(n)≡x1x2x3……xφ(n) (mod n)

即a^[φ(n)]*(x1*x2*x3……xφ(n))≡x1*x2*x3……xφ(n) (mod n)

或者为了方便：K{a^[φ(n)]-1}≡0(mod n) 这里K=x1x2x3……xφ(n)。

可知K{a^[φ(n)]-1}被n整除。但K中的因子x1,x2……都与n互质，所以K与n互质。那么a^[φ(n)]-1必须能被n整除，即a^[φ(n)]-1≡0 （mod n），即a^[φ(n)]≡1(mod n)，得证。

推论（费马小定理）： 若p是素数，a与p互质，则

a^{p-1}≡1\pmod{p}

推论： 若p是素数，则

a^{p}≡a\pmod{p}

定理1： 若p是素数，则

\phi(p^a)=p^a-p^{a-1}

定理2： 若(m,n)=1,则ф(mn)=ф(m)ф(n)。

推论： 若正整数m1,m2,…mk两两互素，则ф(m1m2…mk)=ф(m1)ф(m2)…ф(mk).

定理3： 若m的标准分解式为

m=p_1^{a_1}p_2^{a_2}...p_k^{a_k}

则

\phi(m)=p_1^{a_1-1}p_2^{a_2-1}…p_k^{a_k-1}(p_1-1)(p_2-1)…(p_k-1)

RSA加密算法

公钥密钥产生

随意选择两个大的质数p和q，p不等于q，计算N=pq。
根据欧拉函数，求得r=ф(N) = (p-1)(q-1)
随机选择一个整数 e，条件是1<e<r，且e与r互质
求得 e 关于模 r 的模反元素，命名为d。（所谓”模反元素”就是指有一个整数d，可以使得ed被φ(n)除的余数为1。ed ≡ 1 (mod φ(N))）
将 p 和 q 的记录销毁。

(N,e)是公钥，(N,d)是私钥。

加密消息

假设Bob想给Alice送一个消息m，他知道Alice产生的N和e。他使用起先与Alice约好的格式将m转换为一个小于N的整数n，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将n加密为c：

n^e \equiv c\pmod{N}

计算c并不复杂。Bob算出c后就可以将它传递给Alice。

解密消息

Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n：

c^d ≡ n \pmod{N}

得到n后，她可以将原来的信息m重新复原。

解密原理

我们需要证明

c^d ≡ n \pmod{N}

根据加密规则得

c = n^e - kN

代入最终要证明的规则等同于求证

(n^e - kN)^d ≡ n (mod N)
<=> n^{ed} ≡ n \pmod{N}

由于ed ≡ 1 (mod ф(N))，所以ed=hф(N)+1，代入求证式得

n^{h\phi(N)+1} ≡ n \pmod{N}

接下来分两种情况证明上式：

(1) n与N互质

根据欧拉定理有

n^{\phi(N)} \equiv 1 \pmod{N}

于是

(n^{\phi(N)})^h*n \equiv n \pmod{N}

原式得证

(2) n与N不互质

则n=kp或n=kq。

以n=kp为例，又N=pq，且n<N，则k<q且k与q互质，n=kp与q互质。

于是根据欧拉定理有

(kp)^{q-1} ≡ 1 \pmod{q}

进一步得到

[(kp)^{q-1}]^{h(p-1)} × kp ≡ kp \pmod{q}

即

(kp)^{ed} ≡ kp \pmod{q}

可以改写成

(kp)^{ed} = tq + kp

由于等式左边必然能被p整除，所以等式右边的t必然也能被p整除，假设t=sp。则

(kp)^{ed} = spq + kp

即

n^{e·d} = sN + n

原式得证。

RSA算法的可靠性

密钥生成过程中一共产生了6个数，p,q,N,ф(N),e,d.

其中公钥用到了(N, e), 密钥用到了(N, d), 只有公钥是对外部已知的，有无可能在已知N和e的情况下推导出d？

ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
n=pq。只有将n因数分解，才能算出p和q。

结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。

可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。

RSA加密算法的缺点

　　虽然RSA加密算法作为目前最优秀的公钥方案之一，在发表三十多年的时间里，经历了各种攻击的考验，逐渐为人们接受。但是，也不是说RSA没有任何缺点。由于没有从理论上证明破译RSA的难度与大数分解难度的等价性。所以，RSA的重大缺陷是无法从理论上把握它的保密性能如何。在实践上，RSA也有一些缺点：

产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密；
分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢。

RSA加密原理