ComSec作业四：求AES中的S-Box

ComSec

题目：根据课本描述，编程实现：1、输出AES算法中的S-Box。2、实现具体的字节代换功能，输入一个8比特数，输出其对应的S-Box的值。
第二小题中，本人利用课本例值0x95，结果返回2A。

'''
# File : AES_S-Box.py
# Author : Hongpei Lin
# Date : 20190925
# Purpose : In algorithm AES
# build S-Box in SubBytes
'''
#multilpy in GF(2^8)
def mul(a,b):
    r=0
    while b:
        if b%2:
            r=r^a #add operation : XOR
        b=b>>1
        if a&int('10000000',2)==0: #first bit's value = 0
            a=a<<1
        else: #first bit's value = 1
            a=a<<1
            a=a^283
    return r
#compute the max index number which < 2^count
#return count, from 0
def highest_bit(n):
    count = 0
    while n:
        count+=1
        n=n>>1
    return count-1
#division about polymerization
#return quotient and remainder
def div(a,b):
    if a==b:
        return 1,0
    if a<b:
        return 0,a
    a_bit = highest_bit(a)
    b_bit = highest_bit(b)
    result = 0
    while not a_bit<b_bit:
        move=a_bit-b_bit
        temp=b<<move
        result=result+(1<<move)
        a=a^temp
        a_bit=highest_bit(a)
    return result,a
#compute the inverse about a', where a*a'=1(mod m)
#the algorithrm likes EGCD
def inverse(a,m):
    r0,s0,r1,s1=1,0,0,1
    while m>0:
        t=m
        q,m=div(a,m)#q=a//m,m=a mod m
        a=t#a=m
        r0,r1=r1,r0^mul(q,r1)#sub operation:XOR
        s0,s1=s1,s0^mul(q,s1)
    return r0 #a'
T=[]
T_v=143
#build the matrix  to multiply b0-b7 in step 3
for i in range(8):
    T.append(T_v)
    if T_v&int('00000001',2):
        T_v=(T_v>>1)^int('10000000',2)
    else:
        T_v=T_v>>1
S0=[[0]*16 for i in range(16)]#inital S_Box in step 1
S1=[[0]*16 for i in range(16)]#S_Box
for i in range(16):
    for j in range(16):
        S0[i][j]=(i<<4)+j
        S1[i][j]=inverse(S0[i][j],283)
        #In order to multiply matrix T,let every bit in a byte reverse.
        Bit=list('{:08b}'.format(S1[i][j]))
        Bit.reverse()
        Bit_s=""
        for k in Bit:
            Bit_s=Bit_s+str(k)
        Bit=int(Bit_s,2)
        #T */& b0-b7
        T_result=[]
        for l in T:
            And=l&Bit
            And_list=list('{:08b}'.format(And))
            And_reslut=int(And_list[0],2)
            for m in And_list[1:]:
                And_reslut=And_reslut^int(m,2)
            T_result.append(And_reslut)
        T_result_s=""
        for n in T_result:
            T_result_s=T_result_s+str(n)
        #get the reslut +/XOR c/63's reverse bits
        S_temp=int(T_result_s,2)^int('11000110',2)
        S_temp=list('{:08b}'.format(S_temp))
        S_temp.reverse()#reverse again, get the final answer
        S_temp_s=""
        for o in S_temp:
            S_temp_s=S_temp_s+str(o)
        S1[i][j]=hex(int(S_temp_s,2))
'''
#print the S-Box
for i in range(16):
    for j in range(16):
        print(S1[i][j][2:],end=',')
    print("")
'''
def SubByte(S_BOX,n):
    high_four=(n&int('11110000',2))>>4
    low_four=(n&int('00001111',2))
    return S_BOX[high_four][low_four]
print(SubByte(S1,int('95',16)))