[关闭]
@Lin-- 2020-01-02T10:31:05.000000Z 字数 10674 阅读 291

ComSec作业5--Project for RSA

ComSec


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

本题用两个程序实现,第一个程序生成大素数.
第二个程序实现加解密及签名(验证签名)功能。

  1. '''
  2. # File : Get_PUPR.py
  3. # Author : Hongpei Lin
  4. # Date : 20191023
  5. # Purpose : Generate primes p and q, and write e and n to a public file;
  6. # write Phi_n to another file that is private
  7. # In this project, I let e=65537
  8. '''
  9. import random
  10. import time
  11. #Algorithm GCD to compute greatest common divisor
  12. def gcd(a,b):
  13. while b!=0:
  14. y=b
  15. b=a%b
  16. a=y
  17. return a
  18. #A quickly multiply algorithm with modding n
  19. def Qmul(a,b,n):
  20. r=0
  21. while b:
  22. if b&1:
  23. r=(r+a)%n
  24. b=b>>1
  25. a=(a<<1)%n
  26. return r
  27. #A quidckly exponential algorithm with modding n
  28. def QPow(a,x,n):
  29. result=1
  30. while x:
  31. if x&1:
  32. result=(result*a)%n
  33. x=x>>1
  34. a=(a*a)%n
  35. return result
  36. #Find the number = (n-1)/2^k
  37. def Find_q(n):
  38. while not n&1:
  39. n=n>>1
  40. return n
  41. #Miller Rabin algorithm
  42. def Miller_Rabin(a,n):
  43. q=Find_q(n-1)
  44. aq=QPow(a,q,n)
  45. #final condition,q=n-1
  46. while q<n:
  47. if aq==1 or aq==-1:
  48. return True
  49. #make aq = aq(q*2^j)
  50. aq=QPow(aq,2,n)
  51. q=q<<1
  52. return False
  53. #A quickly algorithm to make a odd number
  54. def Build_Random_Odd(nbit):
  55. #hightest bit = 1
  56. number=1
  57. #every bit value = 0 or 1
  58. while nbit-2:
  59. number=(number<<1)|random.randint(0,1)
  60. nbit=nbit-1
  61. #lowest bit = 1, make it is odd
  62. number=(number<<1)|1
  63. return number
  64. #A algorithm to test whether a number is a prime
  65. def Judge_Prime(n):
  66. #using Miller Rabin to test is in 10 times
  67. t=10
  68. while t:
  69. t-=1
  70. a=random.randint(2,n-1)
  71. if not Miller_Rabin(a,n):
  72. return False
  73. return True
  74. #A algrothm to build prime p and q, and gcd(e,Phi(n))=1
  75. #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
  76. def Build_Prime(e):
  77. while True:
  78. i=0
  79. p_flag=False
  80. p_bit=random.randint(512,1024)
  81. p=Build_Random_Odd(p_bit)
  82. #if it is not a prime, maybe it plus 2 will be
  83. #try 100 times, meaning plus 200
  84. while i<100:
  85. if Judge_Prime(p):
  86. p_flag=True
  87. break
  88. else:
  89. p=p+2
  90. i+=1
  91. continue
  92. #if (p-1) don't coprime e, make another p again
  93. if p_flag and gcd(e,p-1)==1:
  94. break
  95. else:
  96. continue
  97. while True:
  98. j=0
  99. q_flag=False
  100. q_bit=random.randint(512,1024)
  101. q=Build_Random_Odd(q_bit)
  102. while j<100:
  103. if Judge_Prime(q):
  104. q_flag=True
  105. break
  106. else:
  107. q=q+2
  108. j+=1
  109. continue
  110. if q_flag and gcd(e,q)==1:
  111. break
  112. else:
  113. continue
  114. return p,q
  115. starttime = time.time()
  116. e=65537
  117. p,q=Build_Prime(e)
  118. n=p*q
  119. Phi_n=(p-1)*(q-1)
  120. #write e and n to a public file
  121. fpu=open("publicfile.txt","w+")
  122. fpu.write(str(e)+'\n')
  123. fpu.write(str(n))
  124. fpu.close()
  125. #write Phi(n) to a private file
  126. fpr=open("privatefile.txt","w+")
  127. fpr.write(str(Phi_n))
  128. fpr.close()
  129. endtime = time.time()
  130. #running time
  131. print(endtime - starttime)
  1. '''
  2. # File : SHA3.py
  3. # Author : Hongpei Lin
  4. # Date : 20191204
  5. # Purpose : Hash Function,input data n(any bits), output hash value l(any bits you want)
  6. '''
  7. import hashlib
  8. import numpy as np
  9. import codecs
  10. #Padding Function
  11. #Input data bits n and block unit length(n:string type;r:int type),and len(n)%8=0
  12. #Output data bits n' that is r|n'(string type)
  13. def Padding(n,r):
  14. mod=len(n)%r
  15. pad_count=r-mod
  16. if pad_count==8:
  17. n=n+"01100001"
  18. else:
  19. n=n+"011"+"0"*(pad_count-4)+"1"
  20. return n
  21. #Block Function, block the data n, get blocks of n
  22. #Input n:string type,r:int type
  23. #output: list type, which value is string type
  24. def Block(n,r):
  25. BlockList=[]
  26. index=0
  27. length_n=len(n)
  28. while index<length_n:
  29. s=n[index:index+r]
  30. news=""
  31. si=0
  32. while si<r:
  33. news+=s[si:si+64][::-1]
  34. si=si+64
  35. BlockList.append(news)
  36. index+=r
  37. return BlockList
  38. #n=1600bit, build a matrix 5*5*64;
  39. #in this matrix, I let it be a 25*64 matrix; sign row=index/5;colunm=index%5 in mind
  40. def Build_Matrix(n):
  41. n_list=[]
  42. index=0
  43. while index<len(n):
  44. n_list.append(n[index:index+64])
  45. index+=64
  46. return n_list
  47. #0 step in f Function
  48. #theta function,input 25*64matrix, oupput 25*64, both are string in list.
  49. def theta(M):
  50. T=["" for i in range(25)]
  51. for j in range(64):#all lanes compute in the same time
  52. sigma0=[0,0,0,0,0]#sigma(a[(x-1),y',z])
  53. sigma1=[0,0,0,0,0]#sigma(a[(x+1),y',(z-1)]
  54. for i in range(5):
  55. 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])
  56. 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])
  57. for i in range(25):
  58. T[i]=T[i]+str(int(M[i][j])^int(sigma0[i%5])^int(sigma1[i%5]))
  59. return T
  60. 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]
  61. #1 step in f Function
  62. #rho function:shift in every lane
  63. #input a 25*64 matrix and T table, output a new matrix 25*64
  64. def rho(M,table):
  65. for i in range(25):
  66. s=M[i]
  67. M[i]=s[table[i]:]+s[:table[i]]
  68. return M
  69. #2 step in f Function
  70. #pi function:lane confusion
  71. #input a 25*64 matrix and T table, output a new matrix 25*64
  72. def pi(M):
  73. v_Matrix=np.array([[0, 1], [2, 3]])
  74. New_Matrix=[""for i in range(25)]
  75. for i in range(25):
  76. x,y=i%5,i//5#x=colunm;y=row
  77. Initial_Matrix=np.array([[x],[y]])
  78. N_Matrix=v_Matrix.dot(Initial_Matrix)
  79. index=int(N_Matrix[0][0]%5+(N_Matrix[1][0]%5)*5)
  80. New_Matrix[index]=New_Matrix[index]+M[i]
  81. return New_Matrix
  82. #3 step in f Function
  83. #chi function:bits transformation
  84. #input a 25*64 matrix output a new matrix 25*64
  85. def chi(M):
  86. T=["" for i in range(25)]
  87. for j in range(64):
  88. for i in range(25):
  89. row=i//5
  90. x_1,x_2=i+1,i+2#x_1=x+1,x_2=x+2 in a same row
  91. if not x_1<(row+1)*5:
  92. x_1=x_1-5
  93. if not x_2<(row+1)*5:
  94. x_2=x_2-5
  95. T[i]=T[i]+str(int(M[i][j])^(int(M[x_1][j])^1)&int(M[x_2][j]))
  96. return T
  97. #4 step in f function
  98. #iota function:transformation of first lane in every round
  99. #input a 25*64 matrix and RC and ordinal round, output a new matrix 25*64
  100. RC=[1,int('8082',16),int('800000000000808A',16),int('8000000080008000',16),
  101. int('808b',16),int('0000000080000001',16),int('8000000080008081',16),int('8000000000008009',16),
  102. int('8a',16),int('88',16),int('0000000080008009',16),int('000000008000000A',16),
  103. int('000000008000808B',16),int('800000000000008B',16),int('8000000000008089',16),int('8000000000008003',16),
  104. int('8000000000008002',16),int('8000000000000080',16),int('000000000000800A',16),int('800000008000000A',16),
  105. int('8000000080008081',16),int('8000000000008080',16),int('0000000080000001',16),int('8000000080008008',16)]
  106. def iota(M,Rc,i):
  107. M[0]=bin(int(M[0],2)^Rc[i])[2:]
  108. pad_count=64-len(M[0])#padding, let string len=64
  109. zero="0"*pad_count
  110. M[0]=zero+M[0]
  111. return M
  112. #f function, input 1600bits string,output 1600bits string
  113. def f(s):
  114. s_Matrix=Build_Matrix(s)
  115. for i in range(24):#24 rounds
  116. s_Matrix=iota(chi(pi(rho(theta(s_Matrix),T_Table))),RC,i)
  117. news=""
  118. for i in s_Matrix:
  119. news+=i
  120. return news
  121. def absorbing(s,r):
  122. s=Padding(s,r)#padding
  123. P_list=Block(s,r)#block
  124. c="0"*(1600-r)
  125. news="0"*1600#initial s
  126. for i in range(len(P_list)):
  127. P_list[i]=P_list[i]+c
  128. news=bin(int(P_list[i],2)^int(news,2))[2:]
  129. pad_count=1600-len(news)#padding , let string len=1600
  130. zero="0"*pad_count
  131. news=zero+news
  132. news=f(news)
  133. return news
  134. def squeezing(s,r,l):
  135. b=s[:r]
  136. i64,i8=0,0
  137. templist=[]
  138. while i64<len(b):
  139. temp_b=b[i64:i64+64]
  140. i8state=i8+64
  141. while i8state>i8:
  142. templist.append(b[i8state-8:i8state])
  143. i8state-=8
  144. i8+=64
  145. i64+=64
  146. news=""
  147. for i in templist:
  148. news+=i
  149. if not l>r:
  150. return news[:l]
  151. BlockCount=l//r+1
  152. while BlockCount:
  153. b=f(b)
  154. templist=[]
  155. i64,i8=0,0
  156. while i64<len(b):
  157. temp_b=b[i64:i64+64]
  158. i8state=i8+64
  159. while i8state>i8:
  160. templist.append(b[i8state-8:i8state])
  161. i8state-=8
  162. i8+=64
  163. i64+=64
  164. for i in templist:
  165. news+=i
  166. BlockCount-=1
  167. return news[:l]
  168. def HashSHA3(s,l):
  169. s=absorbing(s,1600-l-l)
  170. s=squeezing(s,1600-l-l,l)
  171. s=hex(int(s,2))[2:]
  172. while len(s)<l//4:
  173. s="0"+s
  174. return s
  175. def MakeSHA3(filename,l):
  176. fr=codecs.open(filename,"r",encoding='utf-8')
  177. msg=fr.read()
  178. fr.close()
  179. msgstream=""
  180. for i in msg:
  181. temp=bin(ord(i))[2:]
  182. while len(temp)%8!=0:
  183. temp="0"+temp
  184. msgstream+=temp
  185. hashvalue=HashSHA3(msgstream,l)
  186. fw=codecs.open("HashFile.txt","w",encoding='utf-8')
  187. fw.write(hashvalue)
  188. fw.close()
  189. return True
  1. '''
  2. # File : RSA.py
  3. # Author : Hongpei Lin
  4. # Date : 20191023
  5. # Purpose : RSA
  6. '''
  7. import re
  8. import codecs
  9. import SHA3
  10. def egcd(a,b):
  11. r0,r1,s0,s1,t=1,0,0,1,b
  12. while b:
  13. q,a,b=a//b,b,a%b
  14. r0,r1=r1,r0-q*r1
  15. s0,s1=s1,s0-q*s1
  16. if r0<0:
  17. r0=r0%t
  18. return r0
  19. def QPow(a,x,n):
  20. result=1
  21. while x:
  22. if x&1:
  23. result=(result*a)%n
  24. x=x>>1
  25. a=(a*a)%n
  26. return result
  27. #Get public key in a public flie
  28. def Get_PuKey(puf):
  29. fpu=open(puf,"r")
  30. l=[]
  31. for line in fpu.readlines():
  32. l.append(int(line))
  33. fpu.close()
  34. e,n=l[0],l[1]
  35. return e,n
  36. #Get private key in a private file
  37. def Get_PrKey(puf,prf):
  38. e,n=Get_PuKey(puf)
  39. fpr=open(prf,"r")
  40. Phi_n=int(fpr.read())
  41. fpr.close()
  42. d=egcd(e,Phi_n)
  43. return d,n
  44. #make a string become bitstream
  45. def Str_to_Byte(s):
  46. news=""
  47. for i in s:
  48. news=news+"{:08b}".format(ord(i))
  49. return news
  50. #block the plain, every block has 1024 bits
  51. #input a bitstream,output a list
  52. def BlockPlain(n):
  53. nlist=[]
  54. nlength=len(n)
  55. if not nlength>1024:
  56. nlist.append(n)
  57. return nlist
  58. i=0
  59. while i>nlength:
  60. nlist.append(n[i:i+1024])
  61. i+=1024
  62. nlist.append(n[i:])
  63. return nlist
  64. #RSA encrypt and decrypt, accordings using public key or private key
  65. def RSA_Encrypt(s,e,n):
  66. news=Str_to_Byte(s)
  67. Clist=BlockPlain(news)
  68. Cstring=""
  69. for i in Clist:
  70. value=int(i,2)
  71. encryption=QPow(value,e,n)
  72. encryption=bin(encryption)[2:]
  73. while len(encryption)%8!=0:
  74. encryption="0"+encryption
  75. Cstring=Cstring+encryption
  76. Crylist=re.findall(r'.{8}',Cstring)
  77. s1=""
  78. for i in Crylist:
  79. s1+=chr(int(i,2))
  80. return s1
  81. #encrypt plaintext
  82. def EncryptText(puf):
  83. PlainTextFile=input("Please input the filename you wanna encrypt\n")
  84. fo=codecs.open(PlainTextFile,"r",encoding='utf-8')
  85. PlainText=fo.read()
  86. fo.close()
  87. e,n=Get_PuKey(puf)
  88. Encrypttext=RSA_Encrypt(PlainText,e,n)
  89. fw=codecs.open("EncryptText.txt","w",encoding='utf-8')
  90. fw.write(Encrypttext)
  91. fw.close()
  92. return True
  93. #decrypt
  94. def DecryptText(puf,prf):
  95. d,n=Get_PrKey(puf,prf)
  96. EncryptFile=input("Please input the filename you wanna decrypt\n")
  97. fo=codecs.open(EncryptFile,"r",encoding='utf-8')
  98. EncryptFileText=fo.read()
  99. fo.close()
  100. Decrypttext=RSA_Encrypt(EncryptFileText,d,n)
  101. fw=codecs.open("DecryptText.txt","w+",encoding='utf-8')
  102. fw.write(RSA_Encrypt(EncryptFileText,d,n))
  103. fw.close()
  104. return True
  105. #Digital signatrue
  106. def SignaTrue(puf,prf):
  107. d,n=Get_PrKey(puf,prf)
  108. message=input("Please input the filename of the message!\n")
  109. fr=codecs.open(message,"r",encoding='utf-8')
  110. Mstring=fr.read()
  111. fr.close()
  112. msgstream=""
  113. for i in Mstring:
  114. temp=bin(ord(i))[2:]
  115. while len(temp)%8!=0:
  116. temp="0"+temp
  117. msgstream+=temp
  118. Hmessage=SHA3.HashSHA3(msgstream,256)
  119. Sign=RSA_Encrypt(Hmessage,d,n)
  120. fw=codecs.open("Signatrue.txt","w+",encoding='utf-8')
  121. fw.write(Sign)
  122. fw.close()
  123. return True
  124. #Authentication
  125. def JudgeSign(puf):
  126. e,n=Get_PuKey(puf)
  127. sign=input("Please input the filename of the signatrue!\n")
  128. message=input("Please input the filename of the message!\n")
  129. fr=codecs.open(message,"r",encoding='utf-8')
  130. Mstring=fr.read()
  131. fr.close()
  132. msgstream=""
  133. for i in Mstring:
  134. temp=bin(ord(i))[2:]
  135. while len(temp)%8!=0:
  136. temp="0"+temp
  137. msgstream+=temp
  138. Hmessage=SHA3.HashSHA3(msgstream, 256)
  139. fs=codecs.open(sign,"r",encoding='utf-8')
  140. sign=fs.read()
  141. fs.close()
  142. Auth=RSA_Encrypt(sign,e,n)
  143. if Auth==Hmessage:
  144. return True
  145. else:
  146. return False
  147. def __main__():
  148. select="Please select the functions\n"
  149. encrypt="0:Encrypt\n"
  150. decrypt="1:Decrypt\n"
  151. Sign="2:Signature\n"
  152. Authentication="3:Authentication\n"
  153. out="Other:Exit\n"
  154. pukeyfile="publicfile.txt"
  155. prkeyfile="privatefile.txt"
  156. while True:
  157. project=input(select+encrypt+decrypt+Sign+Authentication+out)
  158. if project=="0":
  159. if EncryptText(pukeyfile):
  160. print("Encrypt Successfully!")
  161. continue
  162. else:
  163. print("Encrypt Failed!")
  164. continue
  165. elif project=="1":
  166. if DecryptText(pukeyfile,prkeyfile):
  167. print("DecryptText Successfully!")
  168. continue
  169. else:
  170. print("Encrypt Failed!")
  171. continue
  172. elif project=="2":
  173. if SignaTrue(pukeyfile,prkeyfile):
  174. print("Signatrue Successfully!")
  175. continue
  176. else:
  177. print("Signatrue Failed!")
  178. continue
  179. elif project=="3":
  180. if JudgeSign(pukeyfile):
  181. print("Authentication Successfully!")
  182. continue
  183. else:
  184. print("Authentication Failed!")
  185. continue
  186. else:
  187. break
  188. if __name__=="__main__":
  189. __main__()
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注