DES+AES+RSA学习

DES

在这给网站上有很多知识点！：
https://www.cxyxiaowu.com/1478.html

大佬总结的通俗易懂！

脚本

import random
#global variable
zeroNum=0#记录补0个数
keysRecord=[]#记录每组子秘钥
#主要变换函数

# F函数
def F_func(rightPart,presentKey):
	"F函数"
	#扩展置换E
	E_box=[
	32,1,2,3,4,5,
	4,5,6,7,8,9,
	8,9,10,11,12,13,
	12,13,14,15,16,17,
	16,17,18,19,20,21,
	20,21,22,23,24,25,
	24,25,26,27,28,29,
	28,29,30,31,32,1
	]

	#S-盒替代
	S_box1=[
	[14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7],
	[0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8],
	[4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0],
	[15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13]
	]

	S_box2=[
	[15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10],
	[3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5],
	[0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15],
	[13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9]
	]
	S_box3=[
	[10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8],
	[13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1],
	[13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7],
	[1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12]
	]
	S_box4=[
	[7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15],
	[13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9],
	[10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4],
	[3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14]
	]
	S_box5=[
	[2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9],
	[14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6],
	[4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14],
	[11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3]
	]
	S_box6=[
	[12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11],
	[10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8],
	[9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6],
	[4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13]
	]
	S_box7=[
	[4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1],
	[13,0,11,7,4,9,1,10,10,3,5,12,2,15,8,6],
	[1,4,11,13,12,3,7,14,14,15,6,8,0,5,9,2],
	[6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12]
	]
	S_box8=[
	[13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7],
	[1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2],
	[7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8],
	[2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11]
	]
	Sbox_List=[S_box1,S_box2,S_box3,S_box4,S_box5,S_box6,S_box7,S_box8]

	# P-盒置换
	P_box=[
	16,7,20,21,
	29,12,28,17,
	1,15,23,26,
	5,18,31,10,
	2,8,24,14,
	32,27,3,9,
	19,13,30,6,
	22,11,4,25
	]
	after_E=""
	for x in range(0,48):
		after_E+=rightPart[E_box[x]-1]
	xor_1=int(after_E,2)
	xor_2=int(presentKey,2)
	rst_xor=str(bin(xor_1^xor_2).split("0b")[1])
	while rst_xor.__len__()<48:
		rst_xor="0"+rst_xor
	dataBySbox=[
	rst_xor[0:6],rst_xor[6:12],
	rst_xor[12:18],rst_xor[18:24],
	rst_xor[24:30],rst_xor[30:36],
	rst_xor[36:42],rst_xor[42:48]
	]
	Line=""
	Column=""
	for x in range(0,8):
		Line=dataBySbox[x][0]+dataBySbox[x][5]
		Line=int(Line,2)
		Column=dataBySbox[x][1:5]
		Column=int(Column,2)
		dataBySbox[x]=(Sbox_List[x])[Line][Column]#十进制值
	for x in range(0,8):
		dataBySbox[x]=str(bin(dataBySbox[x]).split("0b")[1])
		while dataBySbox[x].__len__()<4:
			dataBySbox[x]="0"+dataBySbox[x]
	#到目前为止Sbox压缩完成 数据在dataBySbox里
	after_Sbox=""
	for x in range(0,8):
		after_Sbox+=dataBySbox[x]
	after_P=""
	for x in range(0,32):
		after_P+=after_Sbox[P_box[x]-1]
	return after_P

	#初始置换
def init_Ip(m):
	"初始IP置换"
	ipTable=[
	58,50,42,34,26,18,10,2,
	60,52,44,36,28,20,12,4,
	62,54,46,38,30,22,14,6,
	64,56,48,40,32,24,16,8,
	57,49,41,33,25,17,9,1,
	59,51,43,35,27,19,11,3,
	61,53,45,37,29,21,13,5,
	63,55,47,39,31,23,15,7
	]
	fin=""
	if m.__len__()!=64:
		print("输入信息m长度有误。errorPos:init_Ip()")
		return 
	else:
		for x in range(0,64):
			fin+=m[ipTable[x]-1]

	return fin


 # 逆置换
def inv_Ip(m):
	invIpTable=[
	40,8,48,16,56,24,64,32,
	39,7,47,15,55,23,63,31,
	38,6,46,14,54,22,62,30,
	37,5,45,13,53,21,61,29,
	36,4,44,12,52,20,60,28,
	35,3,43,11,51,19,59,27,
	34,2,42,10,50,18,58,26,
	33,1,41,9,49,17,57,25
	]
	fin=""
	for x in range (0,64):
		fin+=m[invIpTable[x]-1]
	return fin


#生成子密钥
def PC1(initKey):
	# 密钥第一次置换矩阵
	dealtKey=""
	PC1_Table=[
	57,49,41,33,25,17,9,
	1,58,50,42,34,26,18,
	10,2,59,51,43,35,27,
	19,11,3,60,52,44,36,
	63,55,47,39,31,33,15,
	7,62,54,46,38,30,22,
	14,6,61,53,45,37,29,
	21,13,5,28,20,12,4
	]
	for x in range(0,56):
		dealtKey+=initKey[PC1_Table[x]-1]
	return dealtKey

# 密钥第二次置换矩阵
def PC2(key):
	dealtKey=""
	PC2_Table=[
	14,17,11,24,1,5,
	3,28,15,6,21,10,
	23,19,12,4,26,8,
	16,7,27,20,13,2,
	41,52,31,37,47,55,
	30,40,51,45,33,48,
	44,49,39,56,34,53,
	46,42,50,36,29,32
	]
	for x in range(0,48):
		dealtKey+=key[PC2_Table[x]-1]
	return dealtKey

#  以上是DES 加密算法的流程

#tools
def stringToAscii(string):
	"返回字符串用二进制ascii码的表示值"
	Rst=""
	for x in range(0,string.__len__()):
		Rst+=complete8bits(bin(ord(string[x])).split("0b")[1])
	return Rst

def AsciiToString(m):
	Message=""
	for x in range(0,m.__len__()//8):
		Message+=chr(int(m[x*8:(x+1)*8],2))
	return Message

def ivInit(ivString):
	IV=""
	randomWord=[]
	for i in range(0,ivString.__len__()):
		randomWord.append(stringToAscii(ivString[i]))
	IV="".join(randomWord)
	
	return randomWord

def complete8bits(string):
	"补全为8位二进制数"
	while string.__len__()<8:
		string="0"+string
	return string

#KeyMode  工作模式
def keyMode_ECB(seed):
	"ECB模式  固定秘钥加密 返回所有子秘钥的组"
	global keysRecord
	singlePart=[]
	# 16 轮  生成16个子密钥
	for  x in range(1,17):
		if x==1:
			keyNow=keyGenernate(seed,x).split(",")[0]#本轮秘钥48bit
			keyNow_=keyGenernate(seed,x).split(",")[1]#本轮秘钥在PC2之前的值56bit
		else:	
			keyNow=keyGenernate(keyNow_,x).split(",")[0]
			keyNow_=keyGenernate(keyNow_,x).split(",")[1]
		singlePart.append(keyNow)
	keysRecord.append(singlePart)
	#singlePart 里放着生成的子密钥
	return singlePart

def keyMode_OFB(IV,O):
	"OFB模式 O(OUTPUT)用来更新IV值"
	for x in range(1,IV.__len__()):
		IV[x-1]=IV[x]
		if x==IV.__len__()-1:
			IV[x]=O

def keyMode_CFB(IV,C):
	"CFB模式  C(CIPHERTEXT)用来更新IV值"
	for x in range(1,IV.__len__()):
		IV[x-1]=IV[x]
		if x==IV.__len__()-1:
			IV[x]=C
	

#  生成子密钥  调用PC1 PC2置换
def keyGenernate(KeySeed,roundTime):
	"子秘钥生成算法  每次调用时传入当前参与到F函数中的秘钥以及目前进行到的轮次"
	# 第一次传入的时候不是2进制ascii码，以后传入的都是二进制值不必调用stringToAscii()
	bitToShift=[1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1]
	if roundTime==1:
		seed=stringToAscii(KeySeed)
		seed=PC1(seed)
	else :
		seed=KeySeed
	key_L=seed[0:28]
	key_R=seed[28:56]
	key_L=key_L[bitToShift[roundTime-1]:]+key_L[:bitToShift[roundTime-1]]
	key_R=key_R[bitToShift[roundTime-1]:]+key_R[:bitToShift[roundTime-1]]
	key=key_L+key_R
	key=PC2(key)
	return key+","+key_L+key_R



# 加密算法 16轮Feistel体制
#core Function
def desEncoded_ECB(M,keySeed):
	"输入message  秘钥给出密文  K暂定为模式函数名（指定密码工作模式）"
	global zeroNum
	global keysRecord
	block_M=[]#加密前存放明文分组，加密后用密文替代该位置的明文分组
	M_ascii=stringToAscii(M)
	block_num=M_ascii.__len__()//64#取整

	if keySeed.__len__()!=8:
		print("秘钥长度有误，加密终止")
		return
	if M_ascii.__len__()/64>block_num:#有余数的话取整除法与带小数除法值不等
		block_num+=1#确定分组数

	for x in range(0,block_num):
		#每64bit分一组 进行分组工作
		block_M.append(M_ascii[64*x:64*(x+1)])
	if block_M[block_num-1].__len__()<64:
		#开始补0
		zeroNum=0#指示补了多少个0
		while block_M[block_num-1].__len__()<56:
			block_M[block_num-1]+="0"
			zeroNum+=1
		zeroNum=bin(zeroNum).split("0b")[1]
		while zeroNum.__len__()<8:
			zeroNum="0"+zeroNum
		block_M[block_num-1]+=zeroNum
		zeroNum=int(zeroNum,2)
	#以上不足64位补0 最后8位指示补了多少个0
	else:
		#不需要补0的话就加一个64bit的“0”字串跟在后面
		block_M.append("0000000000000000000000000000000000000000000000000000000000000000")
		zeroNum=0
	#encode core operation
	
	for block_pos in range(0,block_num):
		binMesToDeal=init_Ip(block_M[block_pos])#每一轮中待处理的二进制字符串 
		keyNowPart=keyMode_ECB(keySeed)#每一分组都要实现自己的秘钥 目前分组所用的所有秘钥
		#16轮Feistel体制
		for roundTime in range(1,17):
			L=binMesToDeal[0:32]
			R=binMesToDeal[32:64]
			keyNow=keyNowPart[roundTime-1]
			newL=R
			#调用F函数
			rst_F=F_func(R,keyNow)
			rst_F=int(rst_F,2)
			L=int(L,2)
			rst_xor_LF=L^rst_F
			rst_xor_LF=bin(rst_xor_LF).split("0b")[1]
			while rst_xor_LF.__len__()<32:
				rst_xor_LF="0"+rst_xor_LF
			#将异或结果补全到32位二进制字符串
			newR=rst_xor_LF
			binMesToDeal=newL+newR
		
		#16轮结束
		L=binMesToDeal[0:32]
		R=binMesToDeal[32:64]
		binMesToDeal=R+L
		#最后逆置换
		block_M[block_pos]=inv_Ip(binMesToDeal)
		#一整个分组加密结束
	C=""
	for x in range(0,block_M.__len__()):
		C+=block_M[x]
	return C


# 解密算法
def desDecoded_ECB(C,keySeed):
	"输入密文字符串  秘钥还原message K为模式函数名"
	global zeroNum
	if C.__len__()/64!=C.__len__()//64:
		print("密文输入长度有误！")
		return
	#确定分组数
	block_C=[]
	block_num=C.__len__()//64
	#构造分组
	for x in range(0,block_num):
		block_C.append(C[x*64:(x+1)*64])
	for block_pos in range(0,block_num):
		binCToDeal=init_Ip(block_C[block_pos])
		keyNowPart=keyMode_ECB(keySeed)#每一分组都要实现自己的秘钥 目前分组所用的所有秘钥
		if block_C[block_pos]=="0000000000000000000000000000000000000000000000000000000000000000":
			break
		for roundTime in range(1,17):
			L=binCToDeal[0:32]
			R=binCToDeal[32:64]
			keyNow=keyNowPart[16-roundTime]
			newL=R
			rst_F=F_func(R,keyNow)
			rst_F=int(rst_F,2)
			L=int(L,2)
			rst_xor_LF=L^rst_F
			rst_xor_LF=bin(rst_xor_LF).split("0b")[1]
			while rst_xor_LF.__len__()<32:
				rst_xor_LF="0"+rst_xor_LF
			#将异或结果补全到32位二进制字符串
			newR=rst_xor_LF
			binCToDeal=newL+newR
			
		#16轮结束
		L=binCToDeal[0:32]
		R=binCToDeal[32:64]
		binCToDeal=R+L
		block_C[block_pos]=inv_Ip(binCToDeal)
	if block_C[block_C.__len__()-1]=="0000000000000000000000000000000000000000000000000000000000000000":
		del block_C[block_C.__len__()-1]
		zeroNum=0
	else:
		binLenth=(block_C[block_C.__len__()-1])[56:64]
		zeroNum=int(binLenth,2)
	if zeroNum!=0:
		block_C[block_C.__len__()-1]=(block_C[block_C.__len__()-1])[0:56-zeroNum]
	block=""
	for x in range(0,block_C.__len__()):
		block+=block_C[x]
	block_C=block
	codedM=""
	for x in range(0,block_C.__len__()):
		codedM+=block_C[x]
	return AsciiToString(codedM)

def desEncoded_Flush(M,Key,ivString,Mode):
	#输入秘钥加密IV IV取出高8位加密一个字节
	IV=ivInit(ivString)
	M_ascii=stringToAscii(M)
	C=""
	for x in range(0,M.__len__()):
		ivS="".join(IV)
		encodedIV=desEncoded_ECB(ivS,Key)
		rst_xor=int(encodedIV[0:8],2)^int(M_ascii[x*8:(x+1)*8],2)
		rst_xor=bin(rst_xor).split("0b")[1]
		while rst_xor.__len__()<8:
			rst_xor="0"+rst_xor
		C+=rst_xor
		if Mode=="CFB":	
			keyMode_CFB(IV,rst_xor)
		elif Mode=="OFB":
			keyMode_OFB(IV,encodedIV[0:8])
	return C
def desDecoded_Flush(C,Key,ivString,Mode):
	IV=ivInit(ivString)
	M=""
	cList=[]
	for x in range(0,C.__len__()//8):
		cList.append(C[x*8:(x+1)*8])
	for x in range(0,cList.__len__()):
		ivS="".join(IV)
		encodedIV=desEncoded_ECB(ivS,Key)
		rst_xor=int(encodedIV[0:8],2)^int(cList[x],2)
		rst_xor=bin(rst_xor).split("0b")[1]
		while rst_xor.__len__()<8:
			rst_xor="0"+rst_xor
		M+=rst_xor
		if Mode=="CFB":	
			keyMode_CFB(IV,cList[x])
		elif Mode=="OFB":
			keyMode_OFB(IV,encodedIV[0:8])
	return AsciiToString(M)

#消息第一个字符的ascii10进制值作为随机数种子

#思路：每组加密前算出所有的子秘钥 zeroNum,keysRecord作为全局变量 加密解密时需要引用
#独立成模块做包导入其他文件

大概总结一下！

1，DES 先ip置换！ 64 变成64 再 L: 32 R :32

2，密钥再 通过pc1 和pc2 置换 56变成 48 生成 16个子密钥

3，再进行迭代的过程中！ 子密钥通过F函数！ Ri-1 通过E扩展置换成48位！ 和子密钥异或 ，再通过 S盒 变成32位 再通过P盒 ，再异或！ 生成Ri！Ri = L i-1 Ri = Ri-1 通过一系列操作！

Li = Ri-1 ！

4，最后经过16轮后！ 64位 再通过逆置换 得到密文！

AES

主要是搞懂AES加密器！

AES 3个特性！

1.密钥

就是AES支持三种长度的密钥：

128位，192位，256位

平时大家所说的AES128，AES192，AES256，实际上就是指的AES算法对不同长度密钥的使用。

2.填充

假如一段明文长度是192bit，如果按每128bit一个明文块来拆分的话，第二个明文块只有64bit，不足128bit。这时候怎么办呢？就需要对明文块进行填充（Padding）。

具体按照多少位来分 。 嗯？ 这个我也不是很清楚！但是填充就是这个意思！

NoPadding：

不做任何填充，但是要求明文必须是16字节的整数倍。

PKCS5Padding（默认）：

如果明文块少于16个字节（128bit），在明文块末尾补足相应数量的字符，且每个字节的值等于缺少的字符数。
比如明文：{1,2,3,4,5,a,b,c,d,e},缺少6个字节，则补全为{1,2,3,4,5,a,b,c,d,e,6,6,6,6,6,6}

ISO10126Padding：

如果明文块少于16个字节（128bit），在明文块末尾补足相应数量的字节，最后一个字符值等于缺少的字符数，其他字符填充随机数。

比如明文：{1,2,3,4,5,a,b,c,d,e},缺少6个字节，则可能补全为{1,2,3,4,5,a,b,c,d,e,5,c,3,G,$,6}

3.模式

AES的工作模式，体现在把明文块加密成密文块的处理过程中。AES加密算法提供了五种不同的工作模式：



ECB、CBC、CTR、CFB、OFB

一开始我对这个模式的感觉很模糊！

我一开始以为他是。。。。。。

他是在加密算法之上的东西！就是你加完密后 通过这种模式会更安全！

AES加密器

轮

初始轮（Initial Round） 1次

普通轮（Rounds） N次

最终轮（Final Round） 1次

除去初始轮，各种Key长度对应的轮数如下：

AES128：10轮

AES192：12轮

AES256：14轮

初始轮只有一个步骤：

加轮密钥（AddRoundKey）

普通轮有四个步骤：

字节代替（SubBytes）

行移位（ShiftRows）

列混淆（MixColumns）

加轮密钥（AddRoundKey）

最终轮有三个步骤：

字节代替（SubBytes）

行移位（ShiftRows）

加轮密钥（AddRoundKey）

每一步https://www.cxyxiaowu.com/3239.html里面有具体的解析！

需要补充一点，加密的每一轮所用到的密钥并不是相同的。这里涉及到一个概念：扩展密钥（KeyExpansions）。

扩展密钥（KeyExpansions）

AES源代码中用长度 4 * 4 *（10+1） 字节的数组W来存储所有轮的密钥。W{0-15}的值等同于原始密钥的值，用于为初始轮做处理。

后续每一个元素W[i]都是由W[i-4]和W[i-1]计算而来，直到数组W的所有元素都赋值完成。

W数组当中，W{0-15}用于初始轮的处理，W{16-31}用于第1轮的处理，W{32-47}用于第2轮的处理 ……一直到W{160-175}用于最终轮（第10轮）的处理。

RSA

补补数学了！

数学知识

互质关系：如果两个正整数，除了数字 1 之外没有其他公因子，我们称这两个数是互质关系。

同余定理：给定一个正整数 m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数 a 与 b 对模 m 同余，记作 a ≡ b(mod m)。

（1）选择两个不相等的质数p和q

例如：选择两个不等质数分别为 61 和 53 （实际应用中选择的质数都相当大）。

（2）计算p和q的乘积n

n = p*q = 61 * 53 = 3233。

（3）计算 n 的欧拉函数 φ(n)

φ(3233) = φ(61 * 53) = φ(61) * φ(53)。

由于 61 为质数，因此 φ(61) = 61 – 1 = 60。同理 φ(53) = 53 – 1 = 52。则 φ(3233) = 60 * 52 = 3120。

https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0

这里百度百科也讲了讲！

（4）随机选择一个整数 e ，条件是1< e < φ(n)，且 e 与 φ(n) 互质

随机选择一个质数e，保证1< e < 3120，这里选择e = 17。

（5）计算e对于φ(n)的模反元素d
e * d ≡ 1 (mod φ(n))。其中e = 17，φ(n) = 3120。

设e*d是φ(n)的k的整数倍，余数为1。则上式可以转化为：
17 * d = 3120k + 1。继续转化得到：
17 * d + 3120y = 1。其中y = -k。

其中，对于d的求解转化为二元一次方程求解。此方程可以使用扩展欧几里得方法进行求解。通过辗转相除法计算出一组解为(2753,-15)。

解得d = 2753。

关于扩展欧几里得方法进行求解：可以看这个！

https://blog.csdn.net/u014634338/article/details/40210435

（6）将n和e封装成公钥，n和d封装成私钥

加密公钥为(3233,17)，私钥为(3233,2753)。

RSA 算法分析

那么 RSA 算法是如何保证安全性的呢？

在 RSA 算法中 n 与 e 是公开的，那么破解 RSA 加密的步骤即为通过 n 与 e 计算出私钥 d 的值。

（1）ed ≡ 1 (mod φ(n))。只有知道 e 和 φ(n)，才能算出 d 。
（2）φ(n) = (p-1)(q-1)。只有知道 p 和 q ，才能算出 φ(n)。

由此得出密码破解的实质问题是：从p * q的值n，去求出 (p-1) 和 (q-1)。换句话说，只要求出 p 和 q 的值，我们就能求出 d 的值而得到私钥。但是，当 p 和 q 是是很大的质数时，从它们的积 p * q 去分解因子 p 和 q ，这是一个公认的数学难题。

比如当p * q大到1024位时，迄今为止还没有人能够利用任何计算工具去完成分解因子的任务。

虽然理论上 RSA 是可以破解的，但是随着密钥长度增加，破解的代价是不可接受的。

因此，只要密钥长度足够长，用 RSA 加密的信息实际上是不能被解破的。目前被破解的最长 RSA 密钥就是 768 位。

关键在于 PQ!