Zn*的构造并验证是否为群
1.生成素数
使用random伪随机函数随机生成在区间(0,1000]的数，判定是否为素数，不是则继续生成，只能生成素数为止
def GenPrime():
flag = False
while flag is False:
result = random.random() * 1000
int(result) # 随机生成在区间[0,1000)的数
for num in range(2, int(math.sqrt(result))):
if (result % num == 0):
break
elif (num == int(math.sqrt(result))):
flag = True
break
return result
2.对Zn*所需的变量进行取值,并构造Zn*的集合
p = GenPrime()
q = GenPrime()
while p ==q:
q = GenPrime()
N = p * q
# 列表G存储Zn*的集合
G = []
for num in range(2, N - 1):
if (math.gcd(num, N) == 1):
G.append(num)
break
构造完成后明显可知二元关系是模N的乘法运算，单位元为1
3.首先验证封闭性
# 首先验证封闭性,利用list.index来寻找匹配项，若不存在则会抛出异常：
for i in G:
for j in G:
G.index(i * j % N)
print('满足封闭性')
4.验证是否存在逆元
# 验证是否存在逆元，存在逆元就是相乘得单位元，由此遍历一般，看看有无例外
length = len(G)
counter = 0
for i in G:
for j in G:
num = i * j % N
if num == 1:
counter = counter + 1
break
if counter == length:
print('存在逆元')
5.结合律
对于模N的乘法运算结合律必定满足
aes中sbox的构造
1.初始化存储sbox的列表
# initialize a list of sbox
sbox = [None] * 256
sbox[0] = 0x63
2.求乘法逆元
首先用生成元3不断乘3来生成一个用来存储3^n的正表，而0 < n < 256，在这个正表里面可以遍历整个GF(2^8)，而对应的下标 i 的值的逆元则为下标 (256 - i) 的值
# 使用生成元为3生成的表
table = [None] * 256
x = 1
table[0] = x
while i < 255:
# x对应A，carry是查看最高位是否有进位，有则要与1b异或
carry = 0x1b if x & 0x80 else 0
x ^= (x << 1)
x ^= carry
x = x & 0xff
table[i] = x
i += 1
# 此处省略了生成逆元表的步骤，直接使用了已有的正表来表示逆元
i = 0
# 因为对于生成元来说3，在GF（2^8）中，遍历255次后就完全遍历整个域，并且3^255=3^0
# 而我们上面则生成了关于3^n的在GF(2^8)的表，而可以知道正表中下标为254的数乘3得1，以此类推，下标为253得数*3*3得1
# 通过逆向思维可以知道数 x 在正表中的下标 i 与其逆元下标 y 的和为255
while i < 255:
# temp代表是table[i]的逆元
temp = table[255 - i]
sbox[table[i]] = temp ^ shift(temp, 4) ^ shift(temp, 3) ^ shift(
temp, 2) ^ shift(temp, 1) ^ 0x63
i += 1
3.通过矩阵乘法进行字节替换
来自书上的公式
b'i = bi xor b(i+4)mod8 xor b(i+5)mod8 xor b(i+6)mod8 xor b(i+7)mod8 xor ci
上面的规律可知道是循环移位,分别是向左移4，3，2，1位的循环移位，
可由下面函数进行计算
# 用于移位操作，方便后续的公式的计算，s表示向左循环移动s位
def shift(b, s):
# 取低八位
b = b << s | b >> (8 - s)
return b & 0xff
4.完整代码
通过整合上述代码，可得
# 用于移位操作，方便后续的公式的计算
def shift(b, s):
# 取低八位
b = b << s | b >> (8 - s)
return b & 0xff
def initialize_sbox():
# initialize a list of sbox
sbox = [None] * 256
# 使用生成元为3生成的表
table = [None] * 256
sbox[0] = 0x63
x = 1
table[0] = x
i = 1
# 假定生成元是3，可以遍历整个GF(2^8)
# 生成了整个3^n次方的表，0 <n <= 255
while i < 256:
# x对应A，carry是查看最高位是否有进位，有则要与1b异或
carry = 0x1b if x & 0x80 else 0
x ^= (x << 1)
x ^= carry
x = x & 0xff
table[i] = x
i += 1
i = 0
# 因为对于生成元来说3，在GF（2^8）中，遍历255次后就完全遍历整个域，并且3^255=3^0
# 而我们上面则生成了关于3^n的在GF(2^8)的表，而可以知道正表中下标为254的数乘3得1，以此类推，下标为253得数*3*3得1
# 通过逆向思维可以知道数 x 在正表中的下标 i 与其逆元下标 y 的和为255
while i < 255:
# temp代表是table[i]的逆元
temp = table[255 - i]
sbox[table[i]] = temp ^ shift(temp, 4) ^ shift(temp, 3) ^ shift(
temp, 2) ^ shift(temp, 1) ^ 0x63
i += 1
return sbox
print(initialize_sbox())
