作業(yè)內(nèi)容一：

任意給定兩個素數(shù)p和q，p！= q，記 N = p * q ，構(gòu)造Zn*，
問（編程解決）：
1、是否每個元素都有inverse？是否成群？ 2、這個集合有多少元素？

一個群需要滿足以下特性：
1.封閉性
2.結(jié)合律
3.存在單位元
4.任意元素存在逆元
實際上，題目中的群的元素為比N小且與N互素的正數(shù)，即X<N且gcd(X,N)=1

代碼如下：

#任意取兩個不等素數(shù)p、q，令N=p*q，并構(gòu)造ZN*
import random

#gcd函數(shù)求最大公因子
def gcd(a,b):  
    if a%b == 0:  
        return b  
    else :  
        return gcd(b,a%b)

#隨機抽取兩個不等素數(shù)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)

#構(gòu)造ZN*，其中元素比N小且與N互素,即X<N,gcd(X,N)=1，并得到元素個數(shù)
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*封閉！")
    
#驗證結(jié)合律
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*不符合結(jié)合律，不成群！")
else:
    print("ZN*符合結(jié)合律")
    
#驗證是否有單位元
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*不是任何元素都有逆元")           

#結(jié)論
if (isclosed and iscombined and haveunit and isinverse):
    print("ZN*成群！")
else:
    print("ZN*不成群！")            

實驗結(jié)果：

第二次實踐作業(yè)1.PNG

作業(yè)內(nèi)容二：

寫一個程序，實現(xiàn)AES的S-box的構(gòu)造。

1.按字節(jié)值的升序逐行初始化S盒，行x列y的字節(jié)值是{xy}
2.把S盒中的每個字節(jié)映射為它在有限域GF(2^8)中的逆，{00}被映射為它自身{00}
3.把S盒中的每個字節(jié)的每個位做變換
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): #奇數(shù)
            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()

實驗結(jié)果：

第二次實踐作業(yè)2.PNG