S_Box的构造

实现思路

参考:这里，这里，还有这里

• 根据拓展欧几里算法得出对应位置的逆元
• 进行仿射变化
• 将得出的答案进行输出

问题：设计除法函数的时候，会出现溢出的情况。

下面贴出代码:

import sys


def max_index(num):
    for i in range(8):
        if not (num>>(i+1)):
            return i
#进行乘法运算
def gf_multiply(a, b):
    if(b > a):
        a ,b = b ,a
    res = 0
    if(b & 0x01):
        res = a
    for i in range(8):
        if(b & (0x01 << i)):
            temp = a
            for j in range(0,i):
                #判断最高位是否为1
                if not(temp & 0x80):
                    temp <<= 1
                else:
                    temp <<= 1
                    temp = temp ^ 0x1B
            res ^= temp
    return res
#进行除法晕眩
def gf_divide(m,b):
    m_msb = max_index(m)
    b_msb = max_index(b)
    #递归的终点，当除数大于被除数
    if( m_msb < b_msb ):
        global r
        r = m
        return 0
    #获取商的值
    d = m_msb - b_msb
    tem = b
    tem = tem << d
    #求解得到下一次的被除数
    m = m ^ tem
    #将除法得到的每一轮结果进行相加(其中r为余数)
    return ( 1 << d ) | gf_divide( m, b),r

#求逆元，辗转相除，ax+by=1
def get_inverse(num):
    if (num == 0):
        return 0
    a = num
    b = 0x11B

    w0 = 0
    x = 1

    q,r = gf_divide(b,a)

    value = w0 ^ gf_multiply(q,x)
    while(1):
        if(r == 0 | r ==1 ):
            break
        b = a
        a = r
        q,r = gf_divide(b, a)

        w0 = x
        x = value
        value = w0 ^ gf_multiply(q,x)
    return x

#仿射变化
def map(num):
    c = 0x63
    temp = 0x0
    res = 0x0
    for i in range(0,8):
        temp = temp ^ ((num >> i) & 0x01) ^ ((num >> ((i + 4) % 8)) & 0x01)
        temp = temp ^ ((num >> ((i + 5) % 8)) & 0x01) ^ ((num >> ((i + 6) % 8)) & 0x01)
        temp = temp ^ ((num >> ((i + 7) % 8)) & 0x01) ^ ((c >> i) & 0x01)
        res = res | (temp << i)
    return res

if __name__=="__main__":
    sbox = [[0 for i in range(16)] for j in range(16)]
    for i in range(0, 16):
        for j in range(0, 16):
            tem = get_inverse( (i << 4) + j)
            sbox[i][j] = map(tem)
    print (sbox)