计算机安全学第二次实践性作业2018-03-26

一.任意给定两个素数p和q，p！= q，记 N = p * q ，构造Zn*，问（编程解决）：
1、是否每个元素都有inverse？是否成群？ 2、这个集合有多少元素？
群表示一个拥有满足封闭性、结合律、有单位元、有逆元的二元运算的代数结构。
群的定义：如果一个非空集合G上定义了一个二元运算o，满足：
1）结合律，推广（广义结合律：对于任意有限多个元素....）
2）存在幺元（单位元）
3）存在逆元
4）交换律（满足的话，称G为交换群或Abel群）

from __future__ import division
import random

p = 0 
q = 0

for j in range(100000):
    while(1):
        i = random.randint(1, 30)
        for num in range(2, i):
            if (i % num == 0):
                break
        else:
            p = i
            break
    while(1):
        k = random.randint(1, 30)
        for m in range(2, k):
            if (k % m == 0):
                break
        else:
            q = k
            break
    if (q != p): break

print ("random prime p: ", p, ", q: ", q)
#mod N
N = p * q
print ("  N : ", N )

#是否满足封闭性
for i in range(1, N):
    for j in range(1, N):
        modNum = (i * j) % N
        #print (modNum)
        if ( modNum >= N and modNum < 0):
            print ("It's not sealed. Not a Group!")
print ("It's sealed!")

#是否满足结合律
for i in range(1, N):
    for j in range(1, N):
        for k in range(1, N):
            if (((((i*j) % N) * k) % N ) != ((((j*k) % N) * i) % N )):
                print("It's can not be combined. Not a Group!")
print ("It can be combined arbitratily!")

#单位元
print ("Obviously, the E is 1 in the mod n* multiply exp")

#是否对每个数都存在逆元
inversenum = [199 for i in range(N)]
for i in range(1, N):
    for j in range(1, N):
        modNum = (i * j) % N
        if (modNum == 1): #has inverse
            inversenum[i] = 1

ifInverse = 1
#print (len(inversenum))
for i in range(1, len(inversenum)):
    #print (inversenum[i])
    if (inversenum[i] != 1):
        ifInverse = 0
        print ("Not everyone has a inverse..., It's not a Group!")
        break
if (ifInverse):
    print ("Everyone in this set has a inverse! Also it's a Group!")

二.写一个程序，实现AES的S-box的构造。（本题难在求乘法逆元）
       参考《密码编码学与网络安全——原理与实践》第七版 第6.3节 AES TRANSFORMATION FUNCTIONS
初始化S-box，使第xx行第yy列的元素为{xyxy}。
（代码实现时这一步和第二步合在一个initialize()函数中完成）
对S-box中的每个元素求乘法逆元
（求乘法逆元用到扩展欧几里得算法，所以必须要实现GF(2828)中的乘法运算）
对S-box中的公式运用一下公式得到最终的S-box。
b′i=bi⊕b(i+4)mod8⊕b(i+5)mod8⊕b(i+6)mod8⊕b(i+7)mod8⊕ci
bi′=bi⊕b(i+4)mod8⊕b(i+5)mod8⊕b(i+6)mod8⊕b(i+7)mod8⊕ci
其中(c7c6c5c4c3c2c1c0=(01100011)(c7c6c5c4c3c2c1c0=(01100011), 即c=0x63c=0x63。
       找到一个用c++实现的参考网站为：https://blog.csdn.net/snowlyw/article/details/78756055

       再者，有个人用了一个小聪明：（已有GF的指数表）利用指数表可以轻易地构造出乘法逆元表。具体方法如下：
若 x = 3^m, y = 3^n, x 与 y 互为乘法逆元，则有x * y = 3^m * 3^n = 1 = 3^255（任意乘法逆元的255次方必定为1，有点类似费尔马小定理），则m+n=255（虽然我也不是很懂，但是就是想装一下=。=）

Sbox  = [0 for i in range(256)]　#sbox array
l_t   = [0 for i in range(256)]  #log table
m_t   = [0 for i in range(256)]  #pow table - decrease dimension
mid_t = [0 for i in range(256)]  #inverse table


b     = [0xf1, 0xe3, 0xc7, 0x8f, 0x1f, 0x3e, 0x7c, 0xf8]  #b vector
#initialize
p = 1
'''
Step1. the inverse of multiply operation in GF(2^8)
'''
for i in range(256):
#2 mapping table
    l_t[i] = p
    m_t[p] = i
    if (p & 0x80): #whether the b7 is 1 or not
        p = p ^ (p << 1) ^ (0x11b) #generator p - 1
    else :
        p = p ^ (p << 1) ^ 0
    #print (p)
for i in range(256):
    if (i):
          mid_t[i] = l_t[255 - m_t[i]] #255-m_t[i] is the location of inverse in table
    else:
        mid_t[i] = 0 #{00} to {00}

'''
Step2. the operation of matrix
'''
for i in range(256):
    t = 0
    tab = 0
    for j in range(8):
        m = mid = (b[j] & mid_t[i])#press b vector
        #matrix multiplication
        for k in range(8):
            n = mid>>1
            if (m != (n << 1)):
                t+=1 #locate t
            mid = n
            m = mid
        if (t % 2 > 0):
            temp = 1
            for k in range(j):
                temp = temp << 1 # carry
            tab += temp          # sum 
        t = 0
    Sbox[i] = tab ^ 0x63 #plus 0x63



print("Here is the Sbox!")#print 
for i in range(0, 257):
       if (i == 0):
            continue
       else :
                print ("%x" % Sbox[i - 1], end = "")
       if (i % 16 == 0):
             print()

辛苦老师了