近段时间一直在RSA,PKI, CA，Certificate里混，偏偏RSA牵扯到了数论的一些知识，想想是否能用代码来完整的实现一下，也算做一个总结

整除： a整除b， 表示为 a|b => b = ka => b%a=0

质数：除1和自身外，不被其它数整除

分析：判断一个质数只有该数与小于它的数取余都不为0， 则可以判断此数为质数

1 #!/usr/bin/env python  2 import math  3 def prime(number):  4     for i in range(2,number):  5         if number%i == 0:  6             break  7     if i == number-1:  8         return True  9     else: 10         return False          11 number = int (raw_input('please input a number:')) 12  13 print prime(number) 14 print prime_fast(number)

分析：如果一个数是合数，n = p*q， 如果 p<=sqrt(n)，那么q>=sqrt(n)， 如果sqrt(n)+1以内没有数可以整除n，可以断定大于(sqrt(n),n)也不会有数可以整除n

15 def prime_fast(number):16     N = int(math.sqrt(number)+1)17     for i in range(2,N): 18         if number % i == 0:19             break20     if i == N-1:21         return True22     else:23         return False

最大公约数：能同时整除a和b的最大值，表示为gcd(a,b)

即 a % gcd(a,b) = 0 && b % gcd(a,b)=0 && 最大的公约数

分析： 欧几里德定理 gcd(a,b) = gcd(b, a mod b)

证明：    设 a = q * b + r                     q为整数， r为余数   设 d 为 a, b 的公约数   则 d|a=m,  d|b= n, (m，n为整数)   因为 r = a - q*b   所以 d|r = d|a -q*d|b = m - q*n =k   仍为整数   因为 d|b, d|r都为整数   所以 d是（r,b）的公约数   由于d是任意假设的，而d即是（a,b）的公约数，又是（b,r）的公约数，可得（a,b）与（b,r）的公约数相同   所以最大公约数也相同表示为 gcd(a,b)=gcd(b,r)=gcd(b,a mod b)

通过这个定理，算gcd(a,b)只需要计算gcd(b, a %b)就可以，那么数学的表示：

r_0=a, r_1=br_0 = q_1 * r_1 + r_2r_1 = q_2 * r_2 + r_3r_2 = q_3 * r_3 + r_4...r_i = q_(i+1) * r_(i+1) + r_(i+2)...r_(n-2) = q_(n-1) * r_(n-1) + r_n  (r_n为最大公约数)r_(n-1) = q_n * r_n + 0

证明1： r_n为a, b的公约数

因为 r_(n-1) = q_n * r_n所以 r_n | r_(n-1)                 ........q_n因为 r_(n-2) = q_(n-1) * r_(n-1) + r_n所以 r_n | r_(n-2)                 ........q_(n-1)*q_n+1可以推断 r_n | r_1,  r_n | r_0 => r_n | a, r_n | br_n 为 a, b 的公约数

证明2： r_n 为a, b的最大公约数

设a, b的最大公约数g(a,b) = g则 g | a,  g | b => g | r_0, g | r_1因为 r_0 = q_1 * r_1 + r_2所以 g | r2  ..............r_0/g-q_1*r_1/g为整数所以 g | r_n 所以 r_n >= g因为g 是最大公约数，所以r_n是最大公约数

证明3： r_(n+1)=0

r_0 = q_1 * r_1 + r_2r_1 = q_2 * r_2 + r_3...r_i = q_(i+1)*r_(i+1)+r_(i+2)...r_(n-2) = q_(n-1) * r_(n-1) + r_nr_2是r_1的余数，所以r_2
    
     
      r_1>r_2>r_i...>r_(n-1)由于都是整数，因此肯定存一个r_(n+1)=0,算法终止
     
    

欧几里德算法

def gcd(a,b):    “a = q * b + r”                   if a

扩展欧几里德算法

分析： a * x + b * y  = gcd(a,b)

def exgcd(a,b):    "ax+by=gcd(a,b)"    if b==0:        return (1,0)    #a*x1 + b*y1 = a    x1=1    y1=0    #a*x2 + b*y2 = b    x2=0    y2=1    while b!=0:        q = a/b        #gcd(a,b)=gcd(b,a%b)        a,b = b, a%b        #x_i = x_(i-2) - a/b*x_(i-1)        x1,x2 = x2, x1-q*x2                #此时的x1是x2, x2其实是x3 下一次的赋值 x3=x1-q*x2        #y_i = y_(i-2)- a/b*y_(i-1)        y1,y2 = y2,y1-q*y2                 #由于y的值取决于前两次的值，而初值又给定，因此y值肯定能算出，b是循环终止，所以可以算出一对（x,y）    return (x1,y1,a)

欧拉函数：

def oula(number):    counter = 0    for i in range(1,number):        if gcd(i,number)==1:  #gcd(a,b)=1, a  and b relatively prime            counter+=1    return counter

RSA加解密的数学表示

加密 m ^ e mod n = c解密 c ^ d mod n = m代入 (m ^ e) ^ d mod n = m 得   m ^ (e*d) mod n = m=>   m ^ (e*d-1) mod n = 1欧拉定理： m ^ φ(n) mod n = 1因此 e*d-1 = k*φ(n)e * d - k*φ(n) = 1a * x + b * y = 1

例子：

Alice发一个信息给Bob, 该信息的数数为 m = 89

Bob首先要生成公钥（n,e）和私钥（n,d）

Bob 选取 p=53, q=59 作为 n = p * q = 3127Bob 任意选取 e=3此时可以计算出 φ(n)=（p-1）(q-1)=52*58=3016, 因为p,q是质数，同样也可以通过代码计算oula(3127)=3016计算私钥：e * d - k * φ(n) = 1         3 * d + 3016*k = 1                因为并不在乎k的值，但代入代码中的（a，b）为正数通过代码计算得出 exgcd(3,3016)     d,k = -1005,1     d=-1005是个负数所以需要寻找另一个解         3 *(3016-1005) + 3016*1 - 3*3016       d,k = 2011,-2  d = 2011         只要给出3016的整数倍，k就是整数，就是另一个解Bob给Alice     (n=3127,e=3)Bob自己保存私钥  (n=3127,d=2011)

Alice对信息进行加密

m ^ e mod n = c89 ^ 3 mod 3127 = 1394把 c=1394传给Bob,这个是用(n,e)加密过的信息c，原始信息为m

Bob用私钥解密

c ^ d mod n = 1394 ^ 2011 mod 3127 = 89L得到原信息 m

RSA的安全性

知道 n, e， 可否算得出d，其中最重要的就是一个参数 φ(n)，虽然我有代码计算 oula(number)，但是这并不是那么容易的事，运行程序随着当number的位数增加，时间成倍的增加，暴力的破解是可以破解，但如果要你花一万年的时间呢，得不尝失了，目前最多也就破了768位，当我们的n是1024位时基本就是安全的，为什么选p,q为质数呢，也在于当p，q为质数时，算φ(n)=(p-1)(q-1)，但如果你不知道p,q，由n来因式分解的话，就等死吧

参考：

http://blog.chinaunix.net/xmlrpc.php?r=blog/article&uid=26403844&id=5065983http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.htmlhttp://www.wikiwand.com/zh/碾转相除法