RSA

RSA.py

#!/usr/bin/python
# encoding:utf-8

"""
    密码学实验 - RSA
======================
author： `13
time  ： 2017.10.9

details：
        1、编写程序构造一RSA密钥；
        2、编写程序实现快速指数算法；
        3、编写程序生成大素数；
        4、实现RSA密码体制。

"""

import math 
import random
 
global UP_LIMIT
UP_LIMIT = 1000

def isPrime(n):
    """判断质数""" 
    if n <= 1: 
        return False
    for i in range(2, int(math.sqrt(n)) + 1): 
        if n % i == 0: 
            return False
    return True

def euler(n):
    """欧拉函数"""
    __result = 0
    for i in xrange(1,n+1):
        if gcd(n, i) == 1:
            __result += 1
    return __result
    
def gcd(a, b):
    """通过辗转相除法取最大公因数"""
    if a < b:
        a, b = b, a
    y = a % b
    if y == 0:
        return b
    else:
        a, b = b, y
        return gcd(a, b)

# 1、编写程序构造一RSA密钥
def RSA_SecretKey(p, q):
    """RSA密钥生成"""
    if not(isPrime(p) and isPrime(q)):
        return False
    __n = p * q
    __Phi_n = (p - 1) * (q - 1)
    
    __find_e = False 
    while not __find_e:
        __e = random.randint(1, UP_LIMIT)
        if gcd(__e, __Phi_n) == 1:
            __find_e = True
    __e = 37
    
    for i in range(1, __Phi_n):
        if i * __e % __Phi_n == 1:
            __d = i
    
    return {
        "public_key":[__e, __n],
        "private_key":[__d, __n]
    }
    
# 2、编写程序实现快速指数算法；
def fastIndex(x, c, n):
    """快速指数算法 x^c(mod n)"""
    __bin_c = int(bin(c)[2:])
    __x_square_result = [x % n]
    
    for i in range(len(str(__bin_c))+1):
        if i > 0:
            __x_square_result.append(__x_square_result[i-1] * __x_square_result[i-1] % n)
    __x_square_result = __x_square_result[:-1]
    
    result = 1
    for i in range(len(str(__bin_c))):
        __temp = (__x_square_result[i] * int(str(__bin_c)[i])) % n
        if __temp!= 0:
            result = result * __temp
    return result % n

#Miller_Rabin

# cal (a*b) % c 
def mult_mod(a, b, c):
    return a*b % c

# cal x^n % c
def pow_mod(x, n, c):
    if(n == 1):
        return x % c
    x %= c
    tmp = x
    ret = 1
    while(n):
        if(n&1):
            ret = mult_mod(ret, tmp, c);
        tmp = mult_mod(tmp, tmp, c);
        n >>= 1
    return ret

# n - 1 = x *2^t            a^(n-1) = 1(mod n) check n is prime?
def check (a, n, x, t):
    ret = pow_mod(a, x, n)
    last = ret
    for i in range(0, t) :
        ret = mult_mod(ret, ret, n);
        if (ret == 1 and last != 1 and last != n-1): return True
        last = ret
    if (ret != 1): return True
    return False

# 3、编写程序生成大素数
def Miller_Rabin(n):
    if(n<2) : return False
    if(n==2) : return True
    if(not(n&1)) : return False
    x = n - 1
    t = 0
    S = 20
    while((x&1)==0):
        x >>= 1
        t += 1
    for i in range(0, S):
        a = random.randint(0, n)
        if (check(a, n, x, t)):
            return False
    return True


# 4、实现RSA密码体制
def RSA_Demo(p, q, s):
    [e,n] = RSA_SecretKey(p, q)['public_key']   # 公钥
    [d,n] = RSA_SecretKey(p, q)['private_key']  # 私钥
    print "公钥 e ->",e
    print "私钥 d ->",d
    print "输入的明文 c -> ",s
    m = s ** e % (p * q)
    print "生成的明文 m -> ",m
    c = m ** d % (p * q)
    print "解密的明文 c -> ",c
    
RSA_Demo(7,11,2)