Universal Finite Field Multiplication on Logic Gates

Today i spent 3 hours sitting in the front of computer just to draw and test this circuit. This circuit is about implementing 8-bit universal finite field multiplication on discrete logic gates. This picture generalized my previous post about “How to implement AES (Rijndael) finite field multiplication on logic gates”. Here, the circuit works general, you way also implement part of “official” rijndael cipher (especially mix column) using this circuit. But you may also alter mix column process of “Official Rijndael Cipher” and create your own “unofficial” Rijndael Cipher. This is Nice and Fun! if any of you could draw me the PCB layout of this, i’ll appreciate much.

To open full-sized picture, just click on the picture (warning : large picture!)

You can freely use and redistribute this picture under the term of GNU Public License v3.0.

PROOFING AND BENCHMARK

Lets proof the circuit. The way is simple, just compare theoretical result and practical result. For the picture, lets define “1″ as RED and “0″ as BLUE and then color the wire bit by bit. Note that most significant bit located leftmost and least significant bit located rightmost.

Now, we are going to calculate (0xc5 x 0×67) mod (0×1b).

A = 0xc5 = 11000101
B = 0×67 = 01100111
N = 0×1b = 00011011

0xc5 = 11000101 = (0×80 + 0×40 + 0×04 + 0×01)
0xc5 x 0×67 = (0×67 x 0×80) + (0×67 x 0×40) + (0×67 x 0×04) + (0×67 x 0×01)

0×67 x 0×01 = 01100111 = 0×67
0×67 x 0×02 = 11001110 = 0xce
0×67 x 0×04 = 10011100 ^ 00011011 = 10000111 = 0×87
0×67 x 0×08 = 00001110 ^ 00011011 = 00010101 = 0×15
0×67 x 0×10 = 00101010 = 0×2a
0×67 x 0×20 = 01010100 = 0×54
0×67 x 0×40 = 10101000 = 0xa8
0×67 x 0×80 = 01010000 ^ 00011011 = 01001011 = 0×4b

0xc5 x 0×67 = (0×67 x 0×80) + (0×67 x 0×40) + (0×67 x 0×04) + (0×67 x 0×01)
0xc5 x 0×67 = 01001011 ^ 10101000 ^ 10000111 ^ 01100111 = 00000011 = 0×03

And now have a look at this picture below. I shows us 0×03 too. Isn’t it nice ha . If you want to see full-sized picture, just click on it.

You can freely use and redistribute this picture under the term of GNU Public License v3.0.

RELATED STUFF

Download
Download picture source

References:
 Rijndael
 Advanced Encryption Standard
 Finite Field

Links:
 Finite Field in Hardware (pdf)
 Finite Field
 Abstract Math
AES (Rijndael) Simulator

AES finite field multiplication on Logic Gates

Have you ever think about doing AES (Rijndael) finite field multiplication in hardware instead of software. If that so, you got the same question as me. I was wondering how to do AES (Rijndael) finite field multiplication on Logic Gates. After long path way through google. Finally, i found an idea on how to solve this problem. It was just circular left shift by one and conditional XOR by certain constant. Sounds nice and fun.

My previous was about implementing finite field mltiplication bt two, but here i expanded it into full 8 bit by 8 bit finite field multiplication for AES (Rijndael). Hopefully, if you are the one that questioning about how to implement galois field or finite field multiplication of AES (Rijndael) algorithm on hardware (especially logic gates), you will find this picture satisfy and answer your question. All of this picture is only to show you how to do C = (A x B) mod N. where N here is x⁸ + x⁴ + x³ + x¹ + 1 or simply 0×1b. Just for that simple equation, we gone through this complicated path .

If you mad enough, you can expand this picture to universal finite field multiplication, not only for AES, but for any finite field multiplication. Thats gonna be cool. If you got it, you can easily implement RSA encryption using logic gates. Isn’t that mad enough .

You can freely use and redistribute this picture under the term of GNU Public License v3.0.

Note : I just expanded this picture from my previous post about galois field.

PROOFING AND BENCHMARK

To proof that my circuit work well, lets compare theoretical and real result. If they are the same, means the circuit is OK. For picture, lets define “1″ as RED and “0″ as BLUE.

For theoretical part, Lets do this :

(0×8c x 0×57) mod 0×1b = … ?
0×8c = 10001100 = (0×80 + 0×08 + 0×04)
0×57 = 01010111

(0×8c x 0×57) = (0×57 x 0×04) + (0×57 x 0×0 + (0×57 x 0×80)

Lets go further step by Step

(0×57 x 0×01) = 0×57
(0×57 x 0×02) = 10101110 = 0xae
(0×57 x 0×04) = 01011100 ^ 00011011 = 01000111 = 0×47
(0×57 x 0×0 = 10001110 = 0×8e
(0×57 x 0×10) = 00011100 ^ 00011011 = 00000111 = 0×07
(0×57 x 0×20) = 00001110 = 0×0e
(0×57 x 0×40) = 00011100 = 0×1b
(0×57 x 0×80) = 00111000 = 0×38

Previously, we stated that:
(0×8c x 0×57) = (0×57 x 0×80) + (0×57 x 0×0 + (0×57 x 0×04)

Hence:

(0×8c x 0×57) = 0×47 ^ 0×8e ^ 0×38 = 0xf1

Testing Screenshot:

Finally, check the picture. It is shows 0xf1 as well. Nice!!! now i can proof that my circuit work properly .

RELATED STUFF

Download
Download picture source

References:
 Rijndael
 Advanced Encryption Standard
 Finite Field

Links:
 Finite Field in Hardware (pdf)
 Finite Field
 Abstract Math
AES (Rijndael) Simulator

faster GOST cipher implementation on PIC16F877

Previously, i’ve coded GOST cipher on PIC16F84. You knew that each of ciphering and deciphering proces takes 5800 cycles. In order to enhance process throughput. I ported the code into PIC16F877. Here i concatenated SBOX1 to SBOX2, and so on. However, this posting is dedicated to anyone who is searching for implementation of cipher function especially GOST cipher in microcontroller such PIC16F877.

So here we need to allocate 4 x 256 bytes of program just for SBOX lookup table. After concatenating the SBOX, the throughput of ciphering and deciphering process was increasing. Each of them just takes approximately 4200 cycles. Which is a little bit faster than previous faster. To gain more speed, you can modify the algorithm or just replace with higher microcontroller that has better instruction on addition.

Later on, you also can try to port this code into another platform such AVR or ever 8051 . If you find better result, please let me know.

RELATED STUFF

Download
 Source Code v1.0
 PIC16F877 Datasheet
 Mid Range Reference Manual
 Original GOST cipher translation
 GOST Specification
 An Analysis of GOST cipher

References:
 GOST
Gosstandart

Links:
 Encryption
 PIC16F877
 PIC16F877 Programmer
 PIC16F877 Development Board

Official Website
- Microchip

GOST cipher implementation on PIC16F84

GOST was a Soviet Union (Now Russian) standard of cryptography. GOST stands for “Gosudarstvennyi Standard Soyuza SSR” or Government Standard of the Union of Soviet Socialist Republics, which is equal to FIPS in USA.

GOST cipher is a 64-bit block cipher with 256 key and 32 rounds. It uses feistel structure, SBOX based substitution, Circular left shift by 11, 32 bit addition, 32 bit bitwise XOR and 32-bit register to register swapping with simple key scheduling. If code size matter, GOST can be implemented on microcontroller such PIC16F84 with less than 256 lines of code and less than 64 bytes of RAM. But if speed matter, you can modify the code to go faster but with larger code size. Again, it depends on your purposes.

I got the specification of GOST from here. But it contains missing thing such SBOX. Here i just took DES SBOX to fill the missing chain, of course to make the cipher works. Although this way sounds funny and speculative, the most important thing is that actually GOST cipher works on any SBOX table including DES. Here, i cannot guarantee that my code fully compatible with original GOST cipher. But, since nobody know the real SBOX table for GOST cipher, lets make just our life easier and assume that it is true. Dont confuse yourself .

For more confidential things, you can modify SBOX table and create your own customizable GOST cipher and have fun.

If you use microcontroller with larger program memory space , you can cut unnecessary steps by combining 2 4-bit SBOX become a 8-bit SBOX. By doing that, we can speed up the code and neglect code size. Later on, i will port the code to PIC16F877.

Below is the screenshot that i took from MPLAB 5.20.

RELATED STUFFS

Downloads:
Source Code v1.0
PIC16F84 Datasheet
Mid-Range Reference Manual
 Original GOST cipher translation
 GOST Specification
 An Analysis of GOST cipher

References:
 GOST
Gosstandart

Links:
 Encryption
 PIC16F84
 PIC16F84 Programmer
 PIC16F84 Development Board

Official Website:
- Microchip

Cheap AES Galois Field (GF) Implementation

If you learned Advanced Encryption Standard (AES) algorithm, you will find that the algoritm uses galois field on several processes such mix column and key scheduling. I’ve implemented Finite Field multiplication of AES using Discrete Logic Gate. The picture below will illustrate you how miltiplication by two over finite fields was done.

It was just basic things. Hopefully i’ll be able to implement complete finite field multiplication calculator or even universal finite field multiplication calculator using discrete logic gates.

Refernces:
Advanced Encryption Standard
Finite Field Arithmatic

Links
AES (Rijndael) Simulator

An AES implementation on PIC16F877

Yup, previously i’ve implemented AES (Rijndael) 128 bit using PIC16F84. But you knew that the performance was not so good. Since program size and speed are trade off and limitation of PIC16F84 memory space, i decided to decrease the the performance to fit PIC16F84 memory limit. Here, i ported the code into PIC16F877 which has larger memory . Of course to speed up the application.

By using PIC16F877, i felt much more flexible to rock the microcontroller. As a benchmark, porting the code from PIC16F84 into PIC16F877 will speed up the encryption process by 56% as well as speeding up decryption by 37%.

Speed Benchmark:
PIC16F877 - Encryption : 4559 cycles
PIC16F84 - Encryption : 12225 cycles

PIC16F877 - Decryption : 10428 cycles
PIC16F84 - Decryption : 28504 cycles

I will keep modify both of codes rock the microcontroller and speed up the whole process. If necessary, i will also port the code into higher microcontroller platform such PIC18x.

RELATED STUFF

Downloads:

 Source Code V1.0
 Source Code V1.1
 Source Code V1.2
 Source Code V1.3
 PIC16F877 Datasheet
 Mid Range Reference Manual
 AES Publication (fips-197) 
 Practical Implementation of Rijndael S-Box Using Combinational Logic

References:
 Advanced Encryption Standard
 Vincent Rijmen
 Joan Daemen

Links:
 Encryption
 PIC16F877
 PIC16F877 Programmer
 PIC16F877 Development Board
 Rijndael
 Rijndael (pdf)
 AES SBOX
AES (Rijndael) Simulator

Official Website
- Microchip
- Advanced Encryption Standard