|
|
import random
|
|
|
import string
|
|
|
from DES import des_encrypt, des_decrypt, S, P, E
|
|
|
|
|
|
def generate_random_8bit_plaintext():
|
|
|
"""生成8位随机明文"""
|
|
|
return ''.join(random.choice(string.ascii_letters + string.digits) for _ in range(8))
|
|
|
|
|
|
"""定义S盒线性分布掩码表"""
|
|
|
S_i_mask = [
|
|
|
[[0 for _ in range(16)] for _ in range(64)]
|
|
|
for _ in range(8)
|
|
|
]
|
|
|
|
|
|
def self_xor(num, wide):
|
|
|
"""计算异或结果"""
|
|
|
count = 0
|
|
|
for i in range(wide):
|
|
|
count += num & 1
|
|
|
num >>= 1
|
|
|
return count % 2
|
|
|
|
|
|
def get_S_i_mask(plaintexts, ciphertexts):
|
|
|
"""根据大量明密文对计算S盒线性分布掩码表"""
|
|
|
for i in range(8):
|
|
|
for alpha in range(64):
|
|
|
for beta in range(16):
|
|
|
for x, (plain, cipher) in enumerate(zip(plaintexts, ciphertexts)):
|
|
|
# 获取明文和密文的6位输入和4位输出
|
|
|
s_out = S[i][(plain & 0x20) >> 4 | (plain & 1)]
|
|
|
if self_xor(plain & alpha, 6) == self_xor(s_out & beta, 4):
|
|
|
S_i_mask[i][alpha][beta] += 1 # 统计匹配的次数
|
|
|
|
|
|
def print_S_i_mask(num):
|
|
|
"""打印第num个S盒的线性分布表"""
|
|
|
print(f"\t\t\t\tS{num + 1} 线性分布表")
|
|
|
print("α\\β\t", end="")
|
|
|
for i in range(16):
|
|
|
print(f"{i}\t", end="")
|
|
|
print("\n")
|
|
|
|
|
|
for alpha_index, alpha in enumerate(S_i_mask[num]):
|
|
|
print(f"{alpha_index}\t", end="")
|
|
|
for NS in alpha:
|
|
|
print(f"{NS}\t", end="")
|
|
|
print()
|
|
|
|
|
|
def int2bit6(num):
|
|
|
"""6位整数转二进制字符串"""
|
|
|
return bin(num)[2:].zfill(6)
|
|
|
|
|
|
def int2bit4(num):
|
|
|
"""4位整数转二进制字符串"""
|
|
|
return bin(num)[2:].zfill(4)
|
|
|
|
|
|
def get_best_linear(num):
|
|
|
"""获取S盒的最佳线性逼近，并返回 (alpha, beta)"""
|
|
|
max_bias = [0, 0, 0] # alpha, beta, NS
|
|
|
for alpha in range(1, 64): # 输入6位alpha
|
|
|
for beta in range(16): # 输出4位beta
|
|
|
if abs(S_i_mask[num][alpha][beta]) > abs(max_bias[-1]):
|
|
|
max_bias = [alpha, beta, S_i_mask[num][alpha][beta]]
|
|
|
# 记录所有最大偏差的组合
|
|
|
maxs = []
|
|
|
for alpha in range(1, 64):
|
|
|
try:
|
|
|
beta_index = S_i_mask[num][alpha].index(max_bias[-1])
|
|
|
maxs.append([alpha, beta_index, max_bias[-1]])
|
|
|
except ValueError:
|
|
|
pass
|
|
|
# 输出最佳线性逼近
|
|
|
print(f"在第 {num + 1} 个S盒中：")
|
|
|
for item in maxs:
|
|
|
a = int2bit6(item[0])
|
|
|
b = int2bit4(item[1])
|
|
|
alpha_loca = [num * 6 + i for i in range(6) if a[i] == '1']
|
|
|
beta_loca = [num * 4 + i for i in range(4) if b[i] == '1']
|
|
|
|
|
|
R_local = [32 - E[i] for i in alpha_loca]
|
|
|
K_local = [47 - i for i in alpha_loca]
|
|
|
F_local = [31 - P.index(i + 1) for i in beta_loca]
|
|
|
|
|
|
print(f"\tα={item[0]}, β={item[1]}, NS={item[-1]}, "
|
|
|
f"逼近式：P_low{R_local}⊕C_low{R_local}⊕P_h{F_local}⊕C_h{F_local}=K1{K_local}⊕K3{K_local}")
|
|
|
# 返回最佳线性逼近的第一个结果 (alpha, beta)
|
|
|
if maxs:
|
|
|
return maxs[0][:2]
|
|
|
return None
|
|
|
|
|
|
def linear_attack():
|
|
|
key = '123ghyi9'
|
|
|
plaintexts = []
|
|
|
ciphertexts = []
|
|
|
|
|
|
print("生成1000个明密文对...")
|
|
|
for i in range(10000):
|
|
|
plaintext = generate_random_8bit_plaintext()
|
|
|
ciphertext = des_encrypt(plaintext, key)
|
|
|
plaintexts.append(int(plaintext.encode().hex(), 16))
|
|
|
ciphertexts.append(int(ciphertext, 16))
|
|
|
|
|
|
print("计算S盒线性分布掩码...")
|
|
|
get_S_i_mask(plaintexts, ciphertexts)
|
|
|
|
|
|
print("最佳线性逼近式如下：")
|
|
|
for i in range(8):
|
|
|
get_best_linear(i)
|
|
|
|
|
|
# 推测密钥比特
|
|
|
guessed_key_bits = []
|
|
|
for i in range(8):
|
|
|
alpha, beta = get_best_linear(i)
|
|
|
a = int2bit6(alpha)
|
|
|
b = int2bit4(beta)
|
|
|
alpha_loca = [i * 6 + j for j in range(6) if a[j] == '1']
|
|
|
beta_loca = [i * 4 + j for j in range(4) if b[j] == '1']
|
|
|
|
|
|
possible_key_bits = []
|
|
|
for j in range(2 ** len(alpha_loca)):
|
|
|
key_guess = int2bit6(j)
|
|
|
count = 0
|
|
|
for x, (plain, cipher) in enumerate(zip(plaintexts, ciphertexts)):
|
|
|
s_input = [(plain >> loc) & 1 for loc in alpha_loca]
|
|
|
s_output = [(cipher >> loc) & 1 for loc in beta_loca]
|
|
|
f_result = [int(key_guess[k]) ^ s_input[k] for k in range(len(alpha_loca))]
|
|
|
if self_xor(sum(s_input), len(alpha_loca)) == self_xor(sum(s_output), len(beta_loca)) ^ self_xor(sum(f_result), len(alpha_loca)):
|
|
|
count += 1
|
|
|
possible_key_bits.append((j, count))
|
|
|
|
|
|
# 选择出现次数最多的密钥比特作为推测结果
|
|
|
max_count = max([item[1] for item in possible_key_bits])
|
|
|
max_count_keys = [item[0] for item in possible_key_bits if item[1] == max_count]
|
|
|
guessed_key_bits.extend(int2bit6(random.choice(max_count_keys)))
|
|
|
|
|
|
print("推测的密钥比特:", ''.join(guessed_key_bits))
|
|
|
|
|
|
# 对比推测密钥与真实密钥
|
|
|
correct_bits = sum([int(a) == int(b) for a, b in zip(guessed_key_bits, bin(int(key.encode().hex(), 16))[2:].zfill(64))])
|
|
|
print(f"推测密钥与真实密钥的一致性比例: {correct_bits / 64:.2%}")
|
|
|
|
|
|
if __name__ == '__main__':
|
|
|
linear_attack() |
