ComSec作业三--GF(2^8)

ComSec

题目：编程实现AES算法中定义的GF(2^8)的乘法（给定a和b，求a*b）、求乘法逆元(给定a和m，求a'，使得a a' = 1，m按课本给定的值即可. )。

此题本人用python3和C语言两种语言实现两个版本。
计算逆元时：用课本给定的值
$a=x^7+x+1,m=x^8+x^4+x^3+1$
计算结果$a'=x^7$

由于在$GF(2^8)$中运算，数值均为8位无符号整数，故用C语言实现时，未采用GMP库。

python3实现版本

'''
# File : GF_compute.py
# Author : Hongpei Lin
# Date : 20190924
# Purpose : In GF(2^8) : 
# 1. giving a and b, compute the reslut about a*b
# 2. giving a and m, compute the inverse about a', where a*a'=1(mod m)
'''
#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%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'
#giving a=x^7+x+1, m=x^8+x^4+x^3+x+1
#we get a'=128(mod m)
print(inverse(int('10000011',2),int('100011011',2)))    

C语言实现版本

/*
* File : GF_compute.c
* Author : Hongpei Lin
* Date : 20190924
* Purpose : In GF(2^8) :
* 1. giving a and b, compute the reslut about a*b
* 2. giving a and m, compute the inverse about a', where a*a'=1(mod m)
*/
#include<stdio.h>
#include<stdlib.h>
//multilpy in GF(2^8)
int mul(int a, int b);
//compute the max index number which < 2^count
//return count, from 0
int highest_bit(int n);
//division about polymerization
//return quotient and remainder
int * DIV(int a, int b);
//compute the inverse about a', where a*a'=1(mod m)
//the algorithrm likes EGCD
int inverse(int a, int m);
int main()
{
  //giving a=x^7+x+1, m=x^8+x^4+x^3+x+1
  //we get a'=128(mod m)
  printf("%d",inverse(131,283));
    return 0;
}
int mul(int a, int b)
{
    int r=0;
    while(b>0)
    {
        if(b%2==1){r=r^a;}//add operation:XOR
        b=b>>1;
        if((a&128)==0){a=a<<1;}//first bit's value = 0
        else//first bit's value = 1
        {
            a=a<<1;
            a=a%283;
        }
    }
    return r;
}
int highest_bit(int n)
{
    int count=0;
    while (n>0)
    {
        ++count;
        n=n>>1;
    }
    return count-1;
}
int * DIV(int a, int b)
{
    int *result;
    result=(int*)malloc(sizeof(int)*2);
    if(a==b)
    {
        result[0]=1;result[1]=0;return result;
    }
    if(a<b)
    {
        result[0]=0;result[1]=a;return result;
    }
    int a_bit=highest_bit(a);
    int b_bit=highest_bit(b);
    int move,temp;
    result[0]=0;
    while(!(a_bit<b_bit))
    {
        move=a_bit-b_bit;
        temp=b<<move;
        result[0]=result[0]+(1<<move);
        a=a^temp;
        a_bit=highest_bit(a);
    }
    result[1]=a;
    return result;
}
int inverse(int a,int m)
{
  int r0=1,s0=0,r1=0,s1=1;
  int t,*q,r0_temp,s0_temp;
  q=(int*)malloc(sizeof(int)*2);//q[0]=a//m,q[0]=a mod m
  q[1]=m;
  while(q[1]>0)
  {
    t=q[1];
    q=DIV(a,q[1]);
    a=t;
    r0_temp=r0;s0_temp=s0;
    r0=r1;s0=s1;
    r1=r0_temp^mul(q[0],r1);//sub operation:XOR
    s1=s0_temp^mul(q[0],s1);
  }
  free(q);
  return r0;
}