[代码仓库]RSA算法

本篇代码是在完成应用密码学RSA实验时所写，部分内容可供参考。关于RSA原理不做赘述

import random
import sys
import math
def Fast(a,k0,n):#快速幂超实用！！！！！！！！！！！！！！！！
    k=bin(k0)[2:]
    ans = 1
    for i in range(len(k)):
        ans = ans**2%n
        if(k[i]=='1'):
            ans = ans * a % n
    return ans
#后方与前方是因为不同情况对于补零要求不同，有时候需要保护位数补零，有时候则是为了占位补全分组补零
def fill(s,n):#后方补零#
    if len(s)==n:#
        return s
    count=n-len(s)
    zero='0'
    for i in range(count):
        s=s+zero
    return s
def fill_r(s,n):#前方补零
    if len(s)==n:
        return s
    count=n-len(s)
    zero='0'
    for i in range(count):
        s=zero+s
    return s
def getPQ():#随机生成大素数获得一对pq
    min = 1000000000
    max = 9999999999
    flag=False
    p=0
    while(not flag):
        flag=True
        p = random.randint(min,max)
        while(p%2==0):
            p+=1
        for i in range(100):
            if(not MR(p)):
                flag = False
                break
    flag=False
    q=0
    while(not flag):
        flag=True
        q = random.randint(min,max)
        while(q%2==0):
            q+=1
        for i in range(100):
            if(not MR(q)):
                flag = False
                break
    return (p,q)

def MR(n):#Miller-Rabin素性检验
    m = n-1
    a = random.randint(2,n-1)
    k=0
    while(m%2==0):
        k+=1
        m=m//2 
    b = Fast(a,m,n)
    for i in range(k):
        if(b==n-1):
            return True
        else:
            b=b*b%n
    return False

def getRev(b,a):#求乘法逆元，
    a0=a
    k=a//b
    y=a%b
    while(y!=1):#此处参考实验报告中关于求解乘法逆元的讲解
        a1=b
        b1=y
        k1=a1//b1
        y1=a1%b1
        a=0-k1*a
        k=-1-k1*k
        b=b
        y=y1
    k=-k
    return k%a0
##################中文与十六进制互相转换
def ChtoHex(t):#中文转16进制
    data=bytearray(t.encode())
    s=''
    for char in data:
        s+=hex(char)[2:].rjust(2,'0')
    return s

def HextoCh(s):#16进制转中文
    
    a=bytearray.fromhex(s)
    b=b''
    
    for char in a:
        b+=bytes.fromhex(fill(str(hex(char))[2:],2))
    c=b.decode()
    return c

def rsajiami(m0,e0,n0):#每一个密文分组按照n0在十六进制下的位数+1这么多补位，在十六进制下补位
    m = int(m0,2)
    e = int(e0,16)
    n = int(n0,16)
    fill_num=len(n0)+1
    c0 = Fast(m,e,n)
    c=hex(c0)[2:]
    c=fill_r(c,fill_num)
    return c

def rsajiemi(c0,d0,n0):
    c = int(c0,16)
    d = int(d0,16)
    n = int(n0,16)
    m0 = Fast(c,d,n)
    m=hex(m0)[2:]
    return m

def getKey(p,q):#根据PQ获取一对密钥
    fai = (p-1)*(q-1)
    e = random.randint(2,fai)
    while(math.gcd(e,fai)!=1):
        e = random.randint(2,fai)
    d=getRev(e,fai)
    return (e,d)
def main():
#设计python对命令行参数的提取
    argv = sys.argv[1:]
    mingwen = 'rsa_m.txt'
    miwen   = 'rsa_c.txt'
    miyue_q = 'miyue_q.txt'
    miyue_p = 'miyue_p.txt'
    miyue_n = 'miyue_n.txt'
    miyue_e = 'miyue_e.txt'
    miyue_d = 'miyue_d.txt'
    i = 0
    while(i<len(argv)):#处理命令行参数
        opt = argv[i]
        arg = argv[i+1]
        if opt=='-p':
            mingwen = arg
        elif opt=='-n':
            miyue_n = arg
        elif opt=='-e':
            miyue_e = arg
        elif opt=='-d':
            miyue_d = arg
        elif opt=='-c':
            miwen   = arg
        i+=2
    print('Welcome to use this programm, please input option to do what you want
')
    print('1:  get new key
2:  use existed key(please be sure that key is right)
')
    x = input()
    eflag=1
    if x=='1':#获取一对新的密钥
        while(eflag):
            try:
                mi_p,mi_q = getPQ()
                mi_n = mi_p*mi_q
                mi_e,mi_d = getKey(mi_p,mi_q)
            except:
                print('bad luck
')
            else:
                eflag=0
        a = open(miyue_q,'w')
        a.write(hex(mi_q)[2:])
        a.close()
        a = open(miyue_p,'w')
        a.write(hex(mi_p)[2:])
        a.close()
        a = open(miyue_n,'w')
        a.write(hex(mi_n)[2:])
        a.close()
        a = open(miyue_e,'w')
        a.write(hex(mi_e)[2:])
        a.close()
        a = open(miyue_d,'w')
        a.write(hex(mi_d)[2:])
        a.close()
    print('1:  jiami
2:  jiemi
')
    x = input()
    if x=='1':
        a = open(mingwen,'r')
        m0=a.read()
        m0=ChtoHex(m0)
        a.close()
        #fragment----------------------------------分组时按二进制的长度分组，每个分组64位，第一个1表示分组开始，最后一个1表示分组结束，最后一个分组用0补全64位
#######1与0的添加思想可供参考，即通过位置确定一个边界，然后使用另外一个值保护边界

        m0=bin(int(m0,16))[2:]
        long= len(m0)
        m=[]
        head=0
        while(long>62):
            last = '1'
            last += m0[head:head+62]
            last += '1'
            m.append(last)
            long-=62
            head+=62
        if long>0:
            last = '1'
            last += m0[head:]
            last +='1'#填充1和若干0
            last = fill(last,64)
            m.append(last)
        ########------------------------------------
        a = open(miyue_e,'r')
        e0=a.read()
        a.close()
        a = open(miyue_n,'r')
        n0=a.read()
        a.close()
        #jiami---------------------------------------
        c=''
        for i in m:
            c+=rsajiami(i,e0,n0)
        #jiami----------------------------------
        a = open(miwen,'w')
        a.write(c)
        a.close()
        print('result is : '+c+'
')
        print('finish
')
    elif x=='2':
        a = open(miyue_n,'r')
        n0=a.read()
        a.close()
        a = open(miwen,'r')
        c0=a.read()
        #refragment---------------------
        fill_num=len(n0)+1
        head = 0
        c=[]
        while(head<len(c0)):
            c.append(c0[head:head+fill_num])
            head+=fill_num
        #----------------------------------
        a.close()
        a = open(miyue_d,'r')
        d0=a.read()
        a.close()
        #jiemi-----------------先直接解密，然后转换为2进制，去掉头尾，将剩下的二进制拼起来一起构成明文，用16进制转换出来
        m=''
        for i in c:
            hex_m=rsajiemi(i,d0,n0)
            bin_m=bin(int(hex_m,16))[3:]
            t=-1
            while(bin_m[t]!='1'):
                t-=1
            m+= bin_m[:t]
        m=hex(int(m,2))[2:]
        m=HextoCh(m)
        #jiemi-----------------------s----------
        a = open(mingwen,'w')
        a.write(m)
        a.close()
        print('result is : '+m+'
')
        print('finish
')
main()