作业内容一：
任意给定两个素数p和q，p！= q，记 N = p * q ，构造Zn*，
问（编程解决）：
1、是否每个元素都有inverse？是否成群？ 2、这个集合有多少元素？
一个群需要满足以下特性：
1.封闭性
2.结合律
3.存在单位元
4.任意元素存在逆元
实际上，题目中的群的元素为比N小且与N互素的正数，即X<N且gcd(X,N)=1
代码如下：
#任意取两个不等素数p、q，令N=p*q，并构造ZN*
import random
#gcd函数求最大公因子
def gcd(a,b):
if a%b == 0:
return b
else :
return gcd(b,a%b)
#随机抽取两个不等素数p，q
for i in range(100):
tag1=1
tag2=1
while tag1:
p=random.randint(2,30)
for j in range(2,p):
if (p % j) == 0:
break
else:
tag1=0
break
while tag2:
q=random.randint(2,30)
for j in range(2,q):
if (q % j) == 0:
break;
else:
tag2=0
break
if (p!=q):
break
N=p*q
print("p=",p,"q=",q,"N=",N)
#构造ZN*，其中元素比N小且与N互素,即X<N,gcd(X,N)=1，并得到元素个数
ZN=[]
for x in range(1,N):
if (gcd(x, N)==1):
ZN.append(x)
num=len(ZN)
print("一共有",num,"个元素")
#验证封闭性
isclosed=1
for i in range(0,num):
for j in range(0,num):
mark=0;
for k in range(0,num):
if ((ZN[i]*ZN[j])%N==ZN[k]):
mark=1
break
if (mark==0):
isclosed=0
print("ZN*不封闭，不成群！")
if (isclosed==1):
print("ZN*封闭！")
#验证结合律
iscombined=1
for i in range(0,num):
for j in range(0,num):
for k in range(0,num):
if (((((ZN[i]*ZN[j])%N)*ZN[k])%N) != ((ZN[i]*((ZN[j]*ZN[k])%N))%N)):
iscombined=0
if (iscombined==0):
print("ZN*不符合结合律，不成群！")
else:
print("ZN*符合结合律")
#验证是否有单位元
haveunit=0
for i in range(0,num):
for j in range(0,num):
if(((ZN[i]*ZN[j])%N) == ((ZN[j]*ZN[i])%N) == ZN[i]):
haveunit=1
print("ZN*存在单位元,该单位元为:", ZN[j])
break
if (haveunit==1):
break
if (haveunit==0):
print("ZN*不存在单位元，不成群！")
#验证是否每个元素存在逆元,显然1是ZN*的单位元
isinverse=1
count=0
for i in range(0,num):
for j in range(0,num):
if((ZN[i]*ZN[j])%N==1):
count = count+1
break
if (count==num):
print("ZN*任何元素都有逆元")
else:
isinverse=0
print("ZN*不是任何元素都有逆元")
#结论
if (isclosed and iscombined and haveunit and isinverse):
print("ZN*成群！")
else:
print("ZN*不成群！")
实验结果：
第二次实践作业1.PNG
作业内容二：
写一个程序，实现AES的S-box的构造。
1.按字节值的升序逐行初始化S盒，行x列y的字节值是{xy}
2.把S盒中的每个字节映射为它在有限域GF(2^8)中的逆，{00}被映射为它自身{00}
3.把S盒中的每个字节的每个位做变换
bi′=bi⊕b(i+4)mod8⊕b(i+5)mod8⊕b(i+6)mod8⊕b(i+7)mod8⊕ci
其中(c7c6c5c4c3c2c1c0)=(01100011), 即c为{63}
代码如下：
l_t = [0 for i in range(256)] #辅助列表
m_t = [0 for i in range(256)] #辅助列表
Sbox = [0 for i in range(256)] #S盒
inverse = [0 for i in range(256)] #存放逆元
#变换所需的矩阵
matrix = [0xf1, 0xe3, 0xc7, 0x8f, 0x1f, 0x3e, 0x7c, 0xf8]
#求GF(2^8)中的乘法逆元
p = 1
for i in range(256):
l_t[i] = p
m_t[p] = i
if (p & 0x80):#判断p最高位是否为1
p = p ^ (p << 1) ^ (0x11b)#8次不可约多项式16进制表示为11B
else:
p = p ^ (p << 1) ^ 0
#求出逆元后存放在mid_t中
for i in range(256):
if (i):
inverse[i] = l_t[255 - m_t[i]]
else: #00逆元为00
inverse[i] = 0
#位变换
for i in range(256):
t = 0
m = 0
mid = 0
tab = 0
for j in range(8):
m = mid = (matrix[j] & inverse[i])
for k in range(8):
n = mid>>1
if (m != (n << 1)):
t+=1
mid = n
m = mid
if (t % 2 > 0): #奇数
temp = 1
for k in range(j):
temp = temp << 1
tab += temp
t = 0
Sbox[i] = tab ^ 0x63
#输出S盒
print("S盒如下：")
for i in range(0, 256):
print("%02x" % Sbox[i], end=" ")
if ((i+1) % 16 == 0):
print()
实验结果：
第二次实践作业2.PNG
