ComSec作业5--Project for RSA

ComSec

实现RSA加解密和签名功能。要求如下：
1、安全参数：1024 bits-2048bits
2、有简单的交互界面、或命令行操作
3、语言: Python、 C/C++、Java
4、平台：不限
5、加解密可以针对简单的字符文本；签名（验证签名）针对任意选择的文件。

本题用两个程序实现，第一个程序生成大素数$p$和$q$.
第二个程序实现加解密及签名（验证签名）功能。

'''
# File : Get_PUPR.py
# Author : Hongpei Lin
# Date : 20191023
# Purpose : Generate primes p and q, and write e and n to a public file;
#           write Phi_n to another file that is private
#           In this project, I let e=65537
'''
import random
import time
#Algorithm GCD to compute greatest common divisor
def gcd(a,b):
    while b!=0:
        y=b
        b=a%b
        a=y
    return a
#A quickly multiply algorithm with modding n
def Qmul(a,b,n):
    r=0
    while b:
        if b&1:
            r=(r+a)%n
        b=b>>1
        a=(a<<1)%n
    return r
#A quidckly exponential algorithm with modding n
def QPow(a,x,n):
    result=1
    while x:
        if x&1:
            result=(result*a)%n
        x=x>>1
        a=(a*a)%n
    return result
#Find the number = (n-1)/2^k
def Find_q(n):
    while not n&1:
        n=n>>1
    return n
#Miller Rabin algorithm
def Miller_Rabin(a,n):
    q=Find_q(n-1)
    aq=QPow(a,q,n)
    #final condition,q=n-1
    while q<n:
        if aq==1 or aq==-1:
            return True
        #make aq = aq(q*2^j)
        aq=QPow(aq,2,n)
        q=q<<1
    return False
#A quickly algorithm to make a odd number
def Build_Random_Odd(nbit):
    #hightest bit = 1
    number=1
    #every bit value = 0 or 1
    while nbit-2:
        number=(number<<1)|random.randint(0,1)
        nbit=nbit-1
    #lowest bit = 1, make it is odd
    number=(number<<1)|1
    return number
#A algorithm to test whether a number is a prime
def Judge_Prime(n):
    #using Miller Rabin to test is in 10 times
    t=10
    while t:
        t-=1
        a=random.randint(2,n-1)
        if not Miller_Rabin(a,n):
            return False
    return True
#A algrothm to build prime p and q, and gcd(e,Phi(n))=1
#because Phi(n)=(p-1)*(q-1), if gcd(e,Phi(n))!=1, e must be the factor or exist a common divisor but not = 1, with p-1 or q-1
def Build_Prime(e):
    while True:
        i=0
        p_flag=False
        p_bit=random.randint(512,1024)
        p=Build_Random_Odd(p_bit)
        #if it is not a prime, maybe it plus 2 will be
        #try 100 times, meaning plus 200
        while i<100:
            if Judge_Prime(p):
                p_flag=True
                break
            else:
                p=p+2
                i+=1
                continue
        #if (p-1) don't coprime e, make another p again
        if p_flag and gcd(e,p-1)==1:
            break
        else:
            continue
    while True:
        j=0
        q_flag=False
        q_bit=random.randint(512,1024)
        q=Build_Random_Odd(q_bit)
        while j<100:
            if Judge_Prime(q):
                q_flag=True
                break
            else:
                q=q+2
                j+=1
                continue
        if q_flag and gcd(e,q)==1:
            break
        else:
            continue
    return p,q
starttime = time.time()
e=65537
p,q=Build_Prime(e)
n=p*q
Phi_n=(p-1)*(q-1)
#write e and n to a public file
fpu=open("publicfile.txt","w+")
fpu.write(str(e)+'\n')
fpu.write(str(n))
fpu.close()
#write  Phi(n) to a private file
fpr=open("privatefile.txt","w+")
fpr.write(str(Phi_n))
fpr.close()
endtime = time.time()
#running time
print(endtime - starttime)

'''
# File : SHA3.py
# Author : Hongpei Lin
# Date : 20191204
# Purpose : Hash Function,input data n(any bits), output hash value l(any bits you want)
'''
import hashlib
import numpy as np
import codecs
#Padding Function
#Input data bits n and block unit length(n:string type;r:int type),and len(n)%8=0
#Output data bits n' that is r|n'(string type)
def Padding(n,r):
    mod=len(n)%r
    pad_count=r-mod
    if pad_count==8:
        n=n+"01100001"
    else:
        n=n+"011"+"0"*(pad_count-4)+"1"
    return n
#Block Function, block the data n, get blocks of n
#Input n:string type,r:int type
#output: list type, which value is string type
def Block(n,r):
    BlockList=[]
    index=0
    length_n=len(n)
    while index<length_n:
        s=n[index:index+r]
        news=""
        si=0
        while si<r:
            news+=s[si:si+64][::-1]
            si=si+64
        BlockList.append(news)
        index+=r
    return BlockList
#n=1600bit, build a matrix 5*5*64;
#in this matrix, I let it be a 25*64 matrix; sign row=index/5;colunm=index%5 in mind
def Build_Matrix(n):
    n_list=[]
    index=0
    while index<len(n):
        n_list.append(n[index:index+64])
        index+=64
    return n_list
#0 step in f Function
#theta function,input 25*64matrix, oupput 25*64, both are string in list.
def theta(M):
    T=["" for i in range(25)]
    for j in range(64):#all lanes compute in the same time
        sigma0=[0,0,0,0,0]#sigma(a[(x-1),y',z])
        sigma1=[0,0,0,0,0]#sigma(a[(x+1),y',(z-1)]
        for i in range(5):
            sigma0[i]=int(M[(i-1)%25][j])^int(M[(i-6)%25][j])^int(M[(i-11)%25][j])^int(M[(i-16)%25][j])^int(M[(i-21)%25][j])
            sigma1[i]=int(M[(i+1)%25][(j+1)%64])^int(M[(i+6)%25][(j+1)%64])^int(M[(i+11)%25][(j+1)%64])^int(M[(i+16)%25][(j+1)%64])^int(M[(i+21)%25][(j+1)%64])
        for i in range(25):
            T[i]=T[i]+str(int(M[i][j])^int(sigma0[i%5])^int(sigma1[i%5]))
    return T
T_Table=[0,1,62,28,27,36,44,6,55,20,3,10,43,25,39,41,45,15,21,8,18,2,61,56,14]
#1 step in f Function
#rho function:shift in every lane
#input a 25*64 matrix and T table, output a new matrix 25*64
def rho(M,table):
    for i in range(25):
        s=M[i]
        M[i]=s[table[i]:]+s[:table[i]]
    return M
#2 step in f Function
#pi function:lane confusion
#input a 25*64 matrix and T table, output a new matrix 25*64
def pi(M):
    v_Matrix=np.array([[0, 1], [2, 3]])
    New_Matrix=[""for i in range(25)]
    for i in range(25):
        x,y=i%5,i//5#x=colunm;y=row
        Initial_Matrix=np.array([[x],[y]])
        N_Matrix=v_Matrix.dot(Initial_Matrix)
        index=int(N_Matrix[0][0]%5+(N_Matrix[1][0]%5)*5)
        New_Matrix[index]=New_Matrix[index]+M[i]
    return New_Matrix
#3 step in f Function
#chi function:bits transformation
#input a 25*64 matrix output a new matrix 25*64
def chi(M):
    T=["" for i in range(25)]
    for j in range(64):
        for i in range(25):
            row=i//5
            x_1,x_2=i+1,i+2#x_1=x+1,x_2=x+2 in a same row
            if  not x_1<(row+1)*5:
                x_1=x_1-5
            if  not x_2<(row+1)*5:
                x_2=x_2-5
            T[i]=T[i]+str(int(M[i][j])^(int(M[x_1][j])^1)&int(M[x_2][j]))
    return T
#4 step in f function
#iota function:transformation of first lane in every round
#input a 25*64 matrix and RC and ordinal round, output a new matrix 25*64
RC=[1,int('8082',16),int('800000000000808A',16),int('8000000080008000',16),
    int('808b',16),int('0000000080000001',16),int('8000000080008081',16),int('8000000000008009',16),
    int('8a',16),int('88',16),int('0000000080008009',16),int('000000008000000A',16),
    int('000000008000808B',16),int('800000000000008B',16),int('8000000000008089',16),int('8000000000008003',16),
    int('8000000000008002',16),int('8000000000000080',16),int('000000000000800A',16),int('800000008000000A',16),
    int('8000000080008081',16),int('8000000000008080',16),int('0000000080000001',16),int('8000000080008008',16)]
def iota(M,Rc,i):
    M[0]=bin(int(M[0],2)^Rc[i])[2:]
    pad_count=64-len(M[0])#padding, let string len=64
    zero="0"*pad_count
    M[0]=zero+M[0]
    return M
#f function, input 1600bits string,output 1600bits string
def f(s):
    s_Matrix=Build_Matrix(s)
    for i in range(24):#24 rounds
        s_Matrix=iota(chi(pi(rho(theta(s_Matrix),T_Table))),RC,i)
    news=""
    for i in s_Matrix:
        news+=i
    return news
def absorbing(s,r):
    s=Padding(s,r)#padding
    P_list=Block(s,r)#block
    c="0"*(1600-r)
    news="0"*1600#initial s
    for i in range(len(P_list)):
        P_list[i]=P_list[i]+c
        news=bin(int(P_list[i],2)^int(news,2))[2:]
        pad_count=1600-len(news)#padding , let string len=1600
        zero="0"*pad_count
        news=zero+news
        news=f(news)
    return news
def squeezing(s,r,l):
    b=s[:r]
    i64,i8=0,0
    templist=[]
    while i64<len(b):
        temp_b=b[i64:i64+64]
        i8state=i8+64
        while i8state>i8:
            templist.append(b[i8state-8:i8state])
            i8state-=8
        i8+=64
        i64+=64
    news=""
    for i in templist:
        news+=i
    if not l>r:
        return news[:l]
    BlockCount=l//r+1
    while BlockCount:
        b=f(b)
        templist=[]
        i64,i8=0,0
        while i64<len(b):
            temp_b=b[i64:i64+64]
            i8state=i8+64
            while i8state>i8:
                templist.append(b[i8state-8:i8state])
                i8state-=8
            i8+=64
            i64+=64
        for i in templist:
            news+=i
        BlockCount-=1
    return news[:l]
def HashSHA3(s,l):
    s=absorbing(s,1600-l-l)
    s=squeezing(s,1600-l-l,l)
    s=hex(int(s,2))[2:]
    while len(s)<l//4:
        s="0"+s
    return s
def MakeSHA3(filename,l):
    fr=codecs.open(filename,"r",encoding='utf-8')
    msg=fr.read()
    fr.close()
    msgstream=""
    for i in msg:
        temp=bin(ord(i))[2:]
        while len(temp)%8!=0:
            temp="0"+temp
        msgstream+=temp
    hashvalue=HashSHA3(msgstream,l)
    fw=codecs.open("HashFile.txt","w",encoding='utf-8')
    fw.write(hashvalue)
    fw.close()
    return True

'''
# File : RSA.py
# Author : Hongpei Lin
# Date : 20191023
# Purpose : RSA
'''
import re
import codecs
import SHA3
def egcd(a,b):
    r0,r1,s0,s1,t=1,0,0,1,b
    while b:
        q,a,b=a//b,b,a%b
        r0,r1=r1,r0-q*r1
        s0,s1=s1,s0-q*s1
    if r0<0:
        r0=r0%t
    return r0
def QPow(a,x,n):
    result=1
    while x:
        if x&1:
            result=(result*a)%n
        x=x>>1
        a=(a*a)%n
    return result
#Get public key in a public flie
def Get_PuKey(puf):
    fpu=open(puf,"r")
    l=[]
    for line in fpu.readlines():
        l.append(int(line))
    fpu.close()
    e,n=l[0],l[1]
    return e,n
#Get private key in a private file
def Get_PrKey(puf,prf):
    e,n=Get_PuKey(puf)
    fpr=open(prf,"r")
    Phi_n=int(fpr.read())
    fpr.close()
    d=egcd(e,Phi_n)
    return d,n
#make a string become bitstream
def Str_to_Byte(s):
    news=""
    for i in s:
        news=news+"{:08b}".format(ord(i))
    return news
#block the plain, every block has 1024 bits
#input a bitstream,output a list
def BlockPlain(n):
    nlist=[]
    nlength=len(n)
    if not nlength>1024:
        nlist.append(n)
        return nlist
    i=0
    while i>nlength:
        nlist.append(n[i:i+1024])
        i+=1024
    nlist.append(n[i:])
    return nlist
#RSA encrypt and decrypt, accordings using public key or private key
def RSA_Encrypt(s,e,n):
    news=Str_to_Byte(s)
    Clist=BlockPlain(news)
    Cstring=""
    for i in Clist:
        value=int(i,2)
        encryption=QPow(value,e,n)
        encryption=bin(encryption)[2:]
        while len(encryption)%8!=0:
            encryption="0"+encryption
        Cstring=Cstring+encryption
    Crylist=re.findall(r'.{8}',Cstring)
    s1=""
    for i in Crylist:
        s1+=chr(int(i,2))
    return s1
#encrypt plaintext
def EncryptText(puf):
    PlainTextFile=input("Please input the filename you wanna encrypt\n")
    fo=codecs.open(PlainTextFile,"r",encoding='utf-8')
    PlainText=fo.read()
    fo.close()
    e,n=Get_PuKey(puf)
    Encrypttext=RSA_Encrypt(PlainText,e,n)
    fw=codecs.open("EncryptText.txt","w",encoding='utf-8')
    fw.write(Encrypttext)
    fw.close()
    return True
#decrypt
def DecryptText(puf,prf):
    d,n=Get_PrKey(puf,prf)
    EncryptFile=input("Please input the filename you wanna decrypt\n")
    fo=codecs.open(EncryptFile,"r",encoding='utf-8')
    EncryptFileText=fo.read()
    fo.close()
    Decrypttext=RSA_Encrypt(EncryptFileText,d,n)
    fw=codecs.open("DecryptText.txt","w+",encoding='utf-8')
    fw.write(RSA_Encrypt(EncryptFileText,d,n))
    fw.close()
    return True
#Digital signatrue
def SignaTrue(puf,prf):
    d,n=Get_PrKey(puf,prf)
    message=input("Please input the filename of the message!\n")
    fr=codecs.open(message,"r",encoding='utf-8')
    Mstring=fr.read()
    fr.close()
    msgstream=""
    for i in Mstring:
        temp=bin(ord(i))[2:]
        while len(temp)%8!=0:
            temp="0"+temp
        msgstream+=temp
    Hmessage=SHA3.HashSHA3(msgstream,256)
    Sign=RSA_Encrypt(Hmessage,d,n)
    fw=codecs.open("Signatrue.txt","w+",encoding='utf-8')
    fw.write(Sign)
    fw.close()
    return True
#Authentication
def JudgeSign(puf):
    e,n=Get_PuKey(puf)
    sign=input("Please input the filename of the signatrue!\n")
    message=input("Please input the filename of the message!\n")
    fr=codecs.open(message,"r",encoding='utf-8')
    Mstring=fr.read()
    fr.close()
    msgstream=""
    for i in Mstring:
        temp=bin(ord(i))[2:]
        while len(temp)%8!=0:
            temp="0"+temp
        msgstream+=temp
    Hmessage=SHA3.HashSHA3(msgstream, 256)
    fs=codecs.open(sign,"r",encoding='utf-8')
    sign=fs.read()
    fs.close()
    Auth=RSA_Encrypt(sign,e,n)
    if Auth==Hmessage:
        return True
    else:
        return False
def __main__():
    select="Please select the functions\n"
    encrypt="0:Encrypt\n"
    decrypt="1:Decrypt\n"
    Sign="2:Signature\n"
    Authentication="3:Authentication\n"
    out="Other:Exit\n"
    pukeyfile="publicfile.txt"
    prkeyfile="privatefile.txt"
    while True:
        project=input(select+encrypt+decrypt+Sign+Authentication+out)
        if project=="0":
            if EncryptText(pukeyfile):
                print("Encrypt Successfully!")
                continue
            else:
                print("Encrypt Failed!")
                continue
        elif project=="1":
            if DecryptText(pukeyfile,prkeyfile):
                print("DecryptText Successfully!")
                continue
            else:
                print("Encrypt Failed!")
                continue
        elif project=="2":
            if SignaTrue(pukeyfile,prkeyfile):
                print("Signatrue Successfully!")
                continue
            else:
                print("Signatrue Failed!")
                continue
        elif project=="3":
            if JudgeSign(pukeyfile):
                print("Authentication Successfully!")
                continue
            else:
                print("Authentication Failed!")
                continue
        else:
            break
if __name__=="__main__":
    __main__()