RSA_simply_python.

RSA_Simply.py

#coding=utf-8
import random

# 解密模块
def RSA_Decrypy(d,n,c):
    result_m = pow(c,d,n)
    return result_m 


# 加密模块
def RSA_Encrypt(e,n):
    m = int(raw_input('输入明文以加密: '))
    
    c = pow(m,e,n)
    return c

# 扩展的欧几里得算法,求e对euler_n的模反元素d
# def extended_euclid(a,b):
#     X1 = 1; X2 = 0; X3 = b
#     Y1 = 0; Y2 = 1; Y3 = a
#     while Y3 != 1:
#         if Y3 == 0:
#             return 0  #无逆元
#         Q = X3/Y3
#         T1 = X1 - Q*Y1; T2 = X2 - Q*Y2; T3 = X3 - Q*Y3
#         X1 = Y1; X2 = Y2; X3 = Y3
#         Y1 = T1; Y2 = T2; Y3 = T3
#     return Y2%b

# http://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95
def extended_euclid(a,b):
    if(b == 0):
        return 1,0,a
    else:
        x,y,q = extended_euclid(b,a%b)
        x,y = y,(x - a/b*y)
        return x,y,q


# 判断给定的两个数是否互质,如果互质会返回元组(1,0)
def gcd(a,b):
    if a < b:  # 确保a大于b
        a,b = b,a
    while b != 0:
        temp = a % b
        a = b
        b = temp
    return (a,b)

# 产生e,e满足小于euler_n并且与euler_n互质
def product_e(euler_n):
    tepflag = 1
    counter = 0
    while tepflag:
        e = random.randrange(euler_n)
        counter += 1
        if gcd(e,euler_n) ==(1,0):
            print "获取与euler_n互质的数e一共循环的次数为:",counter
            tepflag = 0
        return e

# AKS 素性检验  费马小定理 n为素数的充要条件是:(x-a)**n % n == (x**n-a) % n
def _aks_(a,n):
    flag = 0
    a1 = pow(17-a,n,n)  #pow(x,y,z) = (x**y)%z
    a2 = pow(17,n,n) - (a % n)
    if a1 == a2:
        return 1
    else:
        return 0

# 获取一个大的随机素数
def get_big_number():
    flag = 0
    while not flag:
        n = random.randrange(2**512,2**516)#在512-516个二进制为之间选取
        if(n%2==0 or n%3==0 or n%5==0 or n%7==0 or n%13==0):
            continue  #如果可以被这些数整除就一定不是素数,就直接进入下一个循环,省去素性检查的时间
        flag = _aks_(2,n)  #_aks_是素性检查函数,是素数返回1,不是返回0
    return n

def rsa():
    # 产生两个大的质数p和q
    p = get_big_number()
    q = get_big_number()
    print 'p=',p
    print '---------------'
    print 'q=',q

    # 计算n
    n = p * q
    print '---;--------------'
    print 'n=',n
    # 计算n的欧拉函数,因为p,q都是质数所以n的欧拉函数就是 (p-1) * (q-1)
    euler_n = (p-1) * (q-1)
    print '-----------------'
    print 'euler_n=',euler_n

    # 计算e,e满足小于euler_n并且与euler_n互质
    e = product_e(euler_n)
    print '-----------------'
    print 'e=',e

    # 计算d(用于私钥需保密),d是e对euler_n的模反函数,采用的计算方法是扩展的欧几里得算法
    d ,d1,d2= extended_euclid(e,euler_n)
    print '---------------------'
    if (d < d1):
        d,d1 = d1,d
    print 'd=',d
    #print 'd1=',d1
    #print 'd2=',d2

    # 自此密钥生成所需的参数全部得到,其中公钥用到了(n,e)私钥用到了(n,d)
    # 加密过程
    c = RSA_Encrypt(e,n)

    # 解密过程
    result_m = RSA_Decrypy(d,n,c)
    print 'result_m=',result_m


if __name__ == "__main__":
    rsa()