| 变量 | 意义 | 类型 |
|---|---|---|
| x | 明文 | 整形 |
| piS | S盒 | 整形字典 |
| piP | P盒 | 整形字典 |
| primitiveKey | 主秘钥 | 整形 |
| nr | 轮数 | 整形 |
| m | S盒个数 | 整形 |
| l | S盒大小 | 整形 |
In [1]:
m, l = 4, 4 # m S-Boxes, l bits in each
piS = {0: 14, 1: 4, 2: 13, 3: 1,
4: 2, 5: 15, 6: 11, 7: 8,
8: 3, 9: 10, 10: 6, 11: 12,
12: 5, 13: 9, 14: 0, 15: 7}
piP = {1: 1, 2: 5, 3: 9, 4: 13,
5: 2, 6: 6, 7: 10, 8: 14,
9: 3, 10: 7, 11: 11, 12: 15,
13: 4, 14: 8, 15: 12, 16: 16}
nr = 4
primitiveKeyStr = '0011 1010 1001 0100 1101 0110 0011 1111'\
.replace(' ','')
primitiveKey = int(primitiveKeyStr, 2)
K = {}
K[1] = (primitiveKey >> 16) & 0xFFFF
K[2] = (primitiveKey >> 12) & 0xFFFF
K[3] = (primitiveKey >> 8) & 0xFFFF
K[4] = (primitiveKey >> 4) & 0xFFFF
K[5] = primitiveKey & 0xFFFF
piSInv = dict((v,k) for k,v in piS.items())
piPInv = dict((v,k) for k,v in piP.items())
In [2]:
# subsitution for each bits according to sBoxDict
def subsitutionFunc(ur, sBoxDict):
currentUrBinStrMTimesLBits = \
bin(ur).replace('0b', '').zfill(m * l)
for i in range(1, m + 1):
# S box subsitution by each
# get the bits ready for subsitution
# i to m from left to right
currentSboxInput = \
int(currentUrBinStrMTimesLBits\
[l * (i - 1): l * i], 2) # dec int now
currentSboxOutput = \
sBoxDict[currentSboxInput] # dec int now
# give it to vr in format available
# vr should be int
if i == 1:
vrStrInProgress = \
bin(currentSboxOutput).replace('0b', '').zfill(l)
# 4-bit bin str notation
else:
vrStrInProgress += \
bin(currentSboxOutput).replace('0b', '').zfill(l)
# 8,12,finally 16-bit bin str
vr = int(vrStrInProgress, 2)
return vr # return a int
In [3]:
def permutationFunc(vr, pBoxDict):
currentVrBinStrMTimesLBits = \
bin(vr).replace('0b','').zfill(m * l)
wr = [None] * (m * l)
for i in range(1, m * l + 1): # 1 - 16
wr[pBoxDict[i] - 1] = \
currentVrBinStrMTimesLBits[i-1:i]
wr = int(''.join(wr), 2) # wr is a int now
return wr # return a int
In [4]:
def spnFromTextEncryption(x, piS=piS, piP=piP, K=K):
nr = len(K) - 1
w, u, v = {}, {}, {}
# keys and values in u, v, w are int
w[0] = x
for r in range(1, nr): # 1 to nr -1
## xor round key
u[r] = w[r - 1] ^ K[r]
## subsitution
v[r] = subsitutionFunc(u[r], piS)
## permutation
w[r] = permutationFunc(v[r], piP)
u[nr] = w[nr - 1] ^ K[nr]
v[nr] = subsitutionFunc(u[nr], piS)
y = v[nr] ^ K[nr + 1]
return y
In [5]:
def spnFromTextDecryption(y,
piSInv=piSInv,
piPInv=piPInv,
K=K):
nr = len(K) - 1
w, u, v = {}, {}, {}
# keys and values in u, v, w are int
v[nr] = y ^ K[nr + 1]
u[nr] = subsitutionFunc(v[nr], piSInv)
w[nr - 1] = u[nr] ^ K[nr]
for r in range(nr - 1, 0, -1):
## permutation Inverse
v[r] = permutationFunc(w[r], piPInv)
## subsitution Inverse
u[r] = subsitutionFunc(v[r], piSInv)
## xor round key
w[r - 1] = u[r] ^ K[r]
x = w[0]
return x
In [6]:
PLAINTEXT = int('0010 0110 1011 0111'.replace(' ' ,''), 2)
CIPHERTEXT = int('1011 1100 1101 0110'.replace(' ', ''), 2)
if spnFromTextEncryption(PLAINTEXT, piS, piP, K) \
== CIPHERTEXT:
print('SPN From Text ENCRYPTION Correctly Implemented!')
else:
print('WARNING!','SPN From Text Implementation INCORRECT')
if spnFromTextDecryption(CIPHERTEXT, piSInv, piPInv, K) \
== PLAINTEXT:
print('SPN From Text DECRYPTION Correctly Implemented!')
else:
print('WARNING!','SPN From Text Implementation INCORRECT')
In [7]:
def splitBits(toSplit, index):
if index == 4:
shift = 0
elif index == 3:
shift = 4
elif index == 2:
shift = 8
elif index == 1:
shift = 12
else :
raise ValueError("index supposed to be 1, 2, 3 or 4")
return ((toSplit >> shift) & 0b1111)
In [8]:
import random
def pcPairGenRand():
plain = random.randint(2**0-1, 2**16-1)
cipher = spnFromTextEncryption(x=plain)
return (plain, cipher)
In [9]:
def zxor(x, u4_2, u4_4):
x5 = (x >> (16 - 5)) & 0b1
x7 = (x >> (16 - 7)) & 0b1
x8 = (x >> (16 - 8)) & 0b1
u4__6 = (u4_2 >> 2) & 0b1
u4__8 = (u4_2 >> 0) & 0b1
u4__14 = (u4_4 >> 2) & 0b1
u4__16 = (u4_4 >> 0) & 0b1
z = x5 ^ x7 ^ x8 ^ u4__6 ^ u4__8 ^ u4__14 ^ u4__16
return z
In [10]:
import copy
def linearAttack(pairs, piSInv=piSInv):
pairsCount = len(pairs)
Count = [[0 for l2 in range(16)] for l1 in range(16)]
for (x, y) in pairs:
for (l1, l2) in \
[(l1, l2) for l1 in range(16) for l2 in range(16)]:
v4_2 = l1 ^ splitBits(y, 2)
v4_4 = l2 ^ splitBits(y, 4)
u4_2 = piSInv[v4_2]
u4_4 = piSInv[v4_4]
z = zxor(x, u4_2, u4_4)
if z == 0: Count[l1][l2] += 1
max = -1
for (l1, l2) in \
[(l1, l2) for l1 in range(16) for l2 in range(16)]:
Count[l1][l2] = \
abs(Count[l1][l2] - int( pairsCount / 2 ))
if Count[l1][l2] > max:
max = Count[l1][l2]
maxkey = copy.copy((l1, l2))
return maxkey
In [11]:
def xorPlainPairsGen(count=100):
pairs = []
while True:
plain1 = random.randint(2**0-1, 2**16-1)
plain2 = 0b0000101100000000 ^ plain1
cipher1 = spnFromTextEncryption(x=plain1)
cipher2 = spnFromTextEncryption(x=plain2)
pairs.append((plain1, plain2, cipher1, cipher2))
if len(pairs) == count:
return pairs
差分攻击函数
由于同名符号过多，采取约定进行命名：
| 教材表示 | 程序变量表示 |
|---|---|
| $v4_{<2>}$ | v4_2 |
| $(v4_{<2>})*$ | vv4_2 |
| $(v4_{<2>})'$ | vvv4_2 |
In [12]:
def differentialAttack(pairs, piSInv=piSInv):
# if True:
pairsCount = len(pairs)
Count = [[0 for l2 in range(16)] for l1 in range(16)]
for (x, y, xx, yy) in [(x, y, xx, yy) \
for x, y in pairs for xx, yy in pairs \
if (x, y) != (xx, yy)]:
if splitBits(y, 1) != splitBits(yy, 1) \
or splitBits(y, 3) != splitBits(yy, 3):
print('Failure')
else:
for (l1, l2) in \
[(l1, l2) for l1 in range(16) \
for l2 in range(16)]:
v4_2 = l1 ^ splitBits(y, 2)
v4_4 = l2 ^ splitBits(y, 4)
u4_2 = piSInv[v4_2]
u4_4 = piSInv[v4_4]
vv4_2 = l1 ^ splitBits(yy, 2)
vv4_4 = l2 ^ splitBits(yy, 4)
uu4_2 = piSInv[vv4_2]
uu4_4 = piSInv[vv4_4]
uuu4_2 = u4_2 ^ uu4_2
uuu4_4 = u4_4 ^ uu4_4
print(v4_2, v4_4, u4_2, u4_4)
print(vv4_2, vv4_4, uu4_2, uu4_4)
print(uuu4_2, uuu4_4)
if uuu4_2 == 0b0110 \
and uuu4_4 == 0b0110 :
Count[l1][l2] += 1
max = -1
for (l1, l2) in \
[(l1, l2) for l1 in range(16) \
for l2 in range(16)]:
if Count[l1][l2] > max:
max = Count[l1][l2]
maxkey = copy.copy((l1, l2))
# return maxkey
print(maxkey)
In [13]:
%%time
# generate 8000 pairs
pairs = []
for i in range(8000):
pairs.append(pcPairGenRand())
# lin attack
partialKey = linearAttack(pairs)
In [14]:
%%time
def bruteForce(partialKey=partialKey, pairs=pairs):
print("start brute force")
for bits20 in range(2 ** 20):
for bits4 in range(2 ** 4):
primitiveKeyLocal = \
(bits20 << 12)| (partialKey[0] << 8) \
| (bits4 << 4)|(partialKey[1] << 0)
Kl = {}
Kl[1] = (primitiveKey >> 16) & 0xFFFF
Kl[2] = (primitiveKey >> 12) & 0xFFFF
Kl[3] = (primitiveKey >> 8) & 0xFFFF
Kl[4] = (primitiveKey >> 4) & 0xFFFF
Kl[5] = primitiveKey & 0xFFFF
neq = False
paircount = len(pairs)
for index in range(paircount):
(plain, cipher) = pairs[index]
if spnFromTextEncryption\
(x=plain, K=Kl) != cipher:
break
elif index == paircount:
print(primitiveKeyLocal)
print("""done""")
In [15]:
import random
def shuffleDictRand(d):
k, v = list(d.keys()), list(d.values())
random.shuffle(v) # shuffle values
return dict(zip(k, v))
In [16]:
def genPiSRand(size=16):
k, v = \
list(range(size)), list(range(size))
# 0-size-1
random.shuffle(v)
return dict(zip(k, v))
def genPiPRand(size=16):
k, v = \
list(range(1, size + 1)), list(range(1, size + 1))
# 0-size-1
random.shuffle(v)
return dict(zip(k, v))
In [17]:
import random
def genKeyRand(keysize=2048):
return random.randint(0, 2 ** keysize - 1)
In [18]:
m, l = 16, 4 # m S-Boxes, l bits in each
nr = 32
piS = genPiSRand(l ** 2)
piP = genPiPRand(m * l)
primitiveKeyLen = (nr + 1) * (m * l)
primitiveKey = genKeyRand(primitiveKeyLen)
scheduledKeys = []
for r in range(1, (nr + 1) + 1):
cKey = int(bin(primitiveKey).replace('0b', '')\
.zfill(primitiveKeyLen)\
[(r - 1) * m * l: r * m * l - 1], 2)
scheduledKeys.append(cKey)
# K is a dict from 1 to nr + 1
K = {}
for r in range(len(scheduledKeys)):
K[r + 1] = scheduledKeys[r]
piSInv = dict((v,k) for k,v in piS.items())
piPInv = dict((v,k) for k,v in piP.items())
In [19]:
def spnReinforceEncryption(x, piS, piP, K):
nr = len(K) - 1
w, u, v = {}, {}, {}
# keys and values in u, v, w are int
w[0] = x
for r in range(1, nr): # 1 to nr -1
## xor round key
u[r] = w[r - 1] ^ K[r]
## subsitution
v[r] = subsitutionFunc(u[r], piS)
## permutation
w[r] = permutationFunc(v[r], piP)
u[nr] = w[nr - 1] ^ K[nr]
v[nr] = subsitutionFunc(u[nr], piS)
y = v[nr] ^ K[nr + 1]
return y
In [20]:
def spnReinforceDecryption(y, piSInv, piPInv, K):
nr = len(K) - 1
w, u, v = {}, {}, {}
# keys and values in u, v, w are int
v[nr] = y ^ K[nr + 1]
u[nr] = subsitutionFunc(v[nr], piSInv)
w[nr - 1] = u[nr] ^ K[nr]
for r in range(nr - 1, 0, -1):
## permutation Inverse
v[r] = permutationFunc(w[r], piPInv)
## subsitution Inverse
u[r] = subsitutionFunc(v[r], piSInv)
## xor round key
w[r - 1] = u[r] ^ K[r]
x = w[0]
return x
文件加密采取迭代式方法分块读取文件，并分别进行加密或解密。
加解密使用前面实现的 增强SPN 加解密模块。
加密时生成密钥，并存储在文件中。解密时从文件读取密钥，并进行解密。
分组密码工作模式
采取电子密码本（Electric Codebook) 模式
需要加密的消息按照块密码的块大小被分为数个块，并对每个块进行独立加密。
字节填充
遵循 ISO/IEC 10118-1 & ISO/IEC 9797-1 标准。
采取 zero padding，填充 \x00。
All the bytes that are required to be padded are padded with zero. The zero padding scheme has not been standardized for encryption, although it is specified for hashes and MACs as Padding Method 1 in ISO/IEC 10118-1 and ISO/IEC 9797-1.
| 变量 | 解释 |
|---|---|
| path2original | 加密源文件路径 |
| path2encrypted | 加密后文件路径 |
| path2decrypted | 解密后文件路径 |
| path2key | 密钥读取或写入路径 |
| BLOCKSIZE | 密码分块大小 |
| ENDIAN | 加解密时均使用大端，不论文件实际存储所采用的方式 |
In [21]:
path2original = \
'~/Course_Project_of_Cryptography_HUST_2017/code/classicPrime.py'
path2encrypted = \
'~/Course_Project_of_Cryptography_HUST_2017/code/encrypted.py'
path2decrypted = \
'~/Course_Project_of_Cryptography_HUST_2017/code/decrypted.py'
path2key = \
'~/Course_Project_of_Cryptography_HUST_2017/code/key'
BLOCKSIZE = 8 # bytes
ENDIAN = 'big' # big endian default
In [23]:
import pickle
with open(path2key, 'wb') as fkey:
pickle.dump(primitiveKey, fkey)
fkey.close()
In [24]:
path2read = path2original
path2write = path2encrypted
from functools import partial
with open(path2read, 'rb') as fin:
with open(path2write, 'wb') as fout:
byteBlocks = iter(partial(fin.read, BLOCKSIZE), b'')
for index, value in enumerate(byteBlocks):
# convert to 64-bit int
# pad if not BLOCKSIZE
padTime = 0
while len(value) != BLOCKSIZE:
####### ZERO PADDING ######
value += b'\x00'
padTime += 1
byteBlockInt = int.from_bytes(
value, byteorder = ENDIAN)
# encryption
cipherText = spnReinforceEncryption(
byteBlockInt, piS, piP, K)
# convert to bytes
byteBlock2Write = cipherText.to_bytes(BLOCKSIZE
, byteorder = ENDIAN)
fout.write(byteBlock2Write)
# write a byte block to indicate padding info
fout.write((padTime).to_bytes(BLOCKSIZE, ENDIAN))
fout.close()
fin.close()
In [25]:
import pickle
with open(path2key, 'rb') as fkey:
primitiveKey = pickle.load(fkey)
fkey.close()
In [26]:
path2read = path2encrypted
path2write = path2decrypted
from functools import partial
# read last block for padding info
with open(path2read, 'rb') as fp:
padTime = 0
for lastBlock \
in reversed(list(iter(partial(fp.read, 8), b''))):
padTime = \
int.from_bytes(lastBlock, byteorder = ENDIAN)
break
fp.close()
import os
fileSize = os.stat(path2read).st_size
blockCount = int(fileSize / BLOCKSIZE)
with open(path2read, 'rb') as fin:
with open(path2write, 'wb') as fout:
byteBlocks = iter(partial(fin.read, BLOCKSIZE), b'')
for index, value in enumerate(byteBlocks):
# if reaches last block of padding info
if index + 1 == blockCount:
break
# convert to 64-bit int
byteBlockInt = int.from_bytes(
value, byteorder = ENDIAN)
# decryption
cipherText = spnReinforceDecryption(
byteBlockInt, piSInv, piPInv, K)
# convert to bytes
byteBlock2Write = cipherText.to_bytes(BLOCKSIZE
, byteorder = ENDIAN)
# unpad if reaches last - 1 block
if index + 2 == blockCount:
byteBlock2Write = \
byteBlock2Write[0: BLOCKSIZE - padTime]
fout.write(byteBlock2Write)
fout.close()
fin.close()
In [27]:
!hexdump classicPrime.py
In [28]:
!hexdump encrypted.py
In [29]:
!hexdump decrypted.py
In [30]:
!diff classicPrime.py decrypted.py
diff 程序没有任何输出，古人云：
No news is good news. （没有消息就是好消息）
说明我们的加解密正确。
运行提供的随机性检测程序，没有得到*，检测合格。
程序输出见附录。