The Multiplicative_Inverse_Repo is a modular inverse program developed in C++ that is responsible for locating the multiplicative inverse of an input byte by utilizing the Extended Euclidean Algorithm. Unlike long division, when implementing the Extended Euclidean Algorithm is an important task to monitor the auxiliary. The multiplicative inverse is used as a component of the Advanced Encryption Standard, also known as the Rijndael algorithm, which utilizes base 2 finite field with 256 elements, which is also known as the Galois field GF(2^8). By using GF(2^8), the irreducible polynomial (a polynomial that cannot be factored) x8+x4+x3+x+1 with a degree of 8 that is provided by the norm is a modulo that corresponds to the multiplication of two polynomials. Input values were processed through the multiplicative inverse transformation finding a value that congruent to: 1 mod x8+x4+x3+x+1. For a visual reprsentation of what the program is trying to accomplish navigate to the ./img/Multi_Inverse_Ex.jpg or Image. Do note the remainder column in the image. In the code I have split this column into the dividend and divisor to assist with readability of the long division operations.
This project was developed using the Linux operating system and includes three source files. A makefile was created to generate the executable from the program's source files. To determine if make is installed on the host machine enter the following in the terminal:
make --version
The above command should output something similar to below:
GNU Make 3.81
Copyright (C) 2006 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.
There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE.
If not, install make using the commands below:
sudo apt-get update
sudo apt-get install make
In the terminal, navigate to the Multiplicative_Inverse_Repo directory. To display the multiplicative inverse of all values from 0 -> 255 enter the following
below:
make
./bin/mi_demo
To locate the multiplicative inverse of a desired value from 0 -> 255 enter the following below:
make
./bin/mi_demo [INPUT_VALUE]
If a value is entered out of bounds the following error will be displayed.
ERROR: Input value is out of range.
Please enter a value (0 - 255).