一、任意给定两个素数p和q，p！= q，记 N = p * q ，构造Zn*，
问（编程解决）：
1、是否每个元素都有inverse？是否成群？ 2、这个集合有多少元素？
解决这道题在理解上有两个关键点：
1、是要理解好“群”这个概念。大学阶段，我首先接触到“群”这个概念是在《离散数学》课上。
“群”的定义如下：
设G是一个非空集合，*是它的一个（二元）代数运算，如果满足以下条件：
- 封闭性：群内任意两个元素或两个以上的元素（相同的或不同的）的结合（积）都是该集合的一个元素。即假设对于群G操作（运算）是·，对于G里的任意元素a,b，那么a·b和b·a都必须是G的元素。
- 结合律：虽然群元素不一定要求满足交换律，但必须满足结合律，即对G中任意元素a,b,c都有 (a·b)·c=a·(b·c)；
- 单位元素：集合G内存在一个单位元素e，它和集合中任何一个元素的积都等于该元素本身，即对于G中每个元素a都有 e·a=a·e=a；
- 逆元素：对任意a∈G，存在元素b∈G，使得a·b=e，则b叫做a的右逆元，若b·a=e，则b称为a的左逆元。如果b·a=a·b=e，则b称为a的逆元；
元素的集合如果满足上述四个条件就称为“群”。
2、题干中，Zn集合里面的元素是小于N且与N互素的数，集合的运算符是模N乘法，即{Zn，（a*b）mod N}。
在编程过程的难点，由于没有学过Python，所以这次作业写起来比较费力，需要0、零基础学习Python，因此用时较长。
# -*- coding: utf-8 -*-
from __future__ import division
from random import choice
######求素数2-100之间的素数
list=[]
i = 2
for i in range(2,100):
j = 2
for j in range(2,i):
if (i%j==0):
break
else:
list.append(i)
#任选两个素数 p,q , N=p*q ,p != q
p = choice(list)
q = choice(list)
print ("随机生成的两个素数分别为 p: ", p, ", q: ", q)
p != q
N=p*q
print(" N : ", N, "生成的集合元素总数即为", N)
#集合Zn*本身的性质 x < N , gcd(x,N)=1
for x in range(1,N):
for i in range(1,x+1):
if ((x%i == 0)and (N%i == 0)):
hcf = i
#集合Zn* 的单位元显然为1e = 1
#集合Zn* 的运算符为模N 乘法,
#下面根据群的判定条件判断是否成群
b = 0 #用来判断是否符合群
#是否封闭
for i in range(1, N):
for j in range(1, N):
modNum = (i * j) % N
if ( modNum >= N and modNum < 0):
b = 1
if (b == 1):
print("这个集合并不是封闭的，不成群")
else:
print("这个集合是封闭的")
#是否符合结合律
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 )):
b = 1
if (b == 1):
print("这个集合并不符合结合律，不成群")
else:
print("这个集合符合结合律")
#模N乘法单位元为1
for i in range(1, N):
for j in range(1, N):
if(i * j == j * i == i):
b = 1
c = j#存下单位元
if (b == 1):
print("这个集合存在单位元,该单位元为", c)
else:
print("这个集合不存在单位元，不成群")
#下面验证是否每个元素是否都有逆元
inversenum = [100 for i in range(N)]
for i in range(1, N):
for j in range(1, N):
modNum = (i * j) % N
if (modNum == 1):
inversenum[i] = c
ifInverse = 1
for i in range(1, len(inversenum)):
if (inversenum[i] != 1):
ifInverse = 0
print("这个集合中存在一个元素不含逆元，该元素为", i)
print("所以这个集合不成群")
break
if (ifInverse):
print("这个集合中每个元素都存在逆元")
print("经检测该集合符合所有群的定义要求，故该集合成群")
二、写一个程序，实现AES的S-box的构造。
初始化S-box，使第x行第y列的元素为{xy}。
对S-box中的每个元素求乘法逆元
（求乘法逆元用到扩展欧几里得算法，所以必须要实现GF(28)中的乘法运算）对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), 即c=0x63。
sbox [16][16];
#初始化 sbox[i][j] <- {ij}
def initialize(i,j):
i = 000
j = 000
for i in range(0xF):
for j in range(0xF):
sbox[i][j] = inverse((i << 4) + j)
# 找到非零最高位并返回
def msb(num):
i = 0
for i in range(8):
if (num >> (i + 1) != 0
#a/b #一个字节的多项式除法,返回商(a/b)
def divide(a,b,r):
a_msb = msb(a)
b_msb = msb(b)
if a < b
r = a
bit = a_msb - b_msb
temp = b;
temp = temp << bit
a = a ^ temp
if (1 << bit) or divide(a, b, r)
return
#GF(2^8)乘法,返回a * b
def multiply(a,b):
res = 0;
if(b & 0x01)
res = a
i = 1
for i in range(8):
if b & (0x01 << i)
temp = a
j = 0
for j in range(i):
if !(temp & 0x80) = 1
temp <<= 1
else:
temp <<= 1
temp = temp ^ 0x1B
res = res ^ temp;
return res;
#扩展欧几里得算法求b在GF(2^8)的乘法逆元
def inverse(b):
if b == 0
return 0;
r0 = 0x11B
r1 = b
r2 = q
w0 = 0
w1 = 1
w2 = 0
q = divide(r0, r1 , r2)
w2 = w0 ^ multiply(q, w1)
while 1
if r2 == 0
break
r0 = r1
r1 = r2
q = divide(r0, r1, r2)
w0 = w1
w1 = w2
w2 = w0 ^ multiply(q, w1)
return w1
#映射
def map(a):
c = 0x63
res = 0x0
temp = 0x0
i = 0
for i in range(8):
temp = temp ^ ((a >> i) & 0x1) ^ ((a >> ((i + 4) % 8)) & 0x1)#优先级>> 高于 &
temp = temp ^ ((a >> ((i + 5) % 8)) & 0x1) ^ ((a >> ((i + 6) % 8)) & 0x1)
temp = temp ^ ((a >> ((i + 7) % 8)) & 0x1) ^ ((c >> i) & 0x1)
res = res or (temp << i)
temp = 0x0
return res;
if __name__ == '__main__':
initialize(i,j)
i = 0
j = 0
for i in range(0xF):
for j in range(0xF):
sbox[i][j] = map(sbox[i][j])
print("%02X ",sbox[i][j])
