The Implementation of Vigenere Cipher on PIC16F84

Today, i was reading the “CRYPTOLOGIA History” book. I found nice classical cipher named “vigenere”. This cipher was invented by Blaise de Vigenère. Although this cipher is insecure, lets just code it for the sake of curiosity.

This post is dedicated to provide an example to anyone who is looking for the implementation of Vigenère cipher in hardware, especially on PIC16F84 the PICmicro Microcontroller from microchip. Hopefully this piece will benefit to anyone, at least to satisfy myself .

This cipher mechanism is based on substitution table. The substitution table consisted of columns and rows labelled “A” to “Z”. To get cipher test, first you select the column of plain text and then you select the row of key. The intersection of row of column is called cipher text then. To decode cipher text, you select the row of key and you find the intersection which is equal to cipher text, the label of column is called plain text then. Simple right .

Above is the substitution table of vigenere cipher. I also took the screenshot of testing the algoritm on MPLAB 8. The picture is below:

Enciphering / Encoding Screenshot

Deciphering / Decoding Screenshot

Cheers 

BENCHMARK

Test Vector

Encryption:

Plain Text : I AM TRYING TO HIDE THIS MESSAGE FOR YOU
Key: HOPEFULLY NOBODY COULD READ THIS TEXT
Cipher Text: POBXWSTYEGCIWGCVVCDPVWSDZLNGKCLN

Decryption:

Cipher Text: POBXWSTYEGCIWGCVVCDPVWSDZLNGKCLN
Key: HOPEFULLY NOBODY COULD READ THIS TEXT
Plain Text: I AM TRYING TO HIDE THIS MESSAGE FOR YOU

Speed Test:

Encryption : 870 cycles / 32 characters
Decryption : 902 cycles / 32 characters

RELATED STUFF

Download
Download source code v1.0
PIC16F84 Datasheet
Mid-Range Reference Manual

References:
 Vigenère Cipher

Links:
Vigenere cipher
 Encryption
 PIC16F84
 PIC16F84 Programmer
 PIC16F84 Development Board

Official Website:
- Microchip

Simulator
Vigenere Cipher Simulator

The Implementation of Rijndael Mix Column on Combinational Logic

In Rijndael cipher, there is a process named “Mix Column”. The process is actually matrix multiplication over GF(2⁸). Mathematically speaking it is defined as:

But wait, how to do this in reality.  I meant, how to implement mix-column in combinational logic. I was wondering that question also. Finally i spent several hours to draw mix-column process on logic gates. It was a tedious job, but no matters, jut to satisfy ourself. The picture is below, just click it to see full-sized one (warning extra large picture)

Since the basic process of mix column is multiplication over GF(2⁸). You can understand the concept of this application by extending my previous post about finite field multiplication of Rijndael cipher. Hopefully this piece benefit you anyway ;p .

RELATED STUFF

AES (Rijndael) Simulator

Hardware Implementation of Rijndael SBOX using Logic Gates

Have you ever questioning about how Rijndael’s (AES) SBOX was done is hardware? Or perhaps you were questioning where Rijndael’s SBOX comes from, is it drop from from the sky? Or it just because of Mr. Rijmen and Mr. Daemen found it while jogging in the morning? Just kidding .

All of that were not true, actually both of two crypto geniuses which is Mr. Rijmen and Mr. Daemen both has strong reason behind the design of Rijndael’s SBOX design. There should be a strong reason behind the scene, yeah for sure.

When i was reading the Offical Rijndael specification (fips-197), something is bothering me, a big question mark exists in my mind. I was just like a dummyhead student who is trying to digest cryptic lecture and pretending to be understand . I can not just swallow the specification and pretending to be convinced. I can’t fool myself, i have to convince my self really .

After sitting several hours in the front of my old computer, finally uncle Google gave me some hints. Aha! a miracle just happened, my broken brain is working. An idea just drop from the sky and i caught it immediately,and it got it !

Ok, lets start the story!

After uncle Google gave me some hints, I found that there are several ways to implement Rijndael’s (AES) SBOX in such hardware sense. It just a lookup table that maps 8 bit combinations of input into unique 8 bit combinations of output.

The easieast wasy to do this is by ROM/EEPROM to emulate lookup table. Even kindergarten kids can do this . But wait, since ROM/EEPROM has fixed parameter such access time, this way is gonna be slow. If, however, your application is not critical in term of speed, you may use this concept. Just to save your time. Beside that, ROM/EEPROM is a bit expensive you have to consider the cost too. I named this trivially as “ROM/EEPROM Lookup Table Emulation”.

Second way of this, which is a bit harder is by decomposing minterm of maxterm. You have to list, when each bit of SBOX output reach “1″ and “0″,If you divide 8 bits of input into two nibbles, you will get “high nibble” and “low nibble” while each nibble takes 4 bits. Furthermore, you can decode each combination of 4 bits of low and high nibbles into 16 combinations each. Here, you have 32 outputs, first sixteenth bits came from decoding high nibble and second sixteenth bits came from decoding low nibble. For example, if SBOX results “1″ when its input reach 0×56 0r “01010110″ for bit say 7, you can gate y₅ of first decoder, which is connected to high nibble and y₆ of second decoder which is connected to low nibble. This is true since y₅ will active when its input reach “0×05″ or “0101″ and y₆ will active when its input reach “0×06″ or “0110″. Here we have to consider “what active mean”, whether logic “1″ or logic zero, so we can choose proper gate. For example 74LS154 uses “active low”, means its output pin will produce “0″ when ever active. We will talk about this implementation later on. It might sounds too intuitive and funny to you, but it works then. Lets just call it “minterm/maxterm decomposition”.

The third one, is about boolean algebra. This way sounds horrible and disgusting to you, lets just swallow it first. I believe that it might bennefit us, at least to satisfy our madness ;p . To do this, you map each bit of output as a function of 8 bits of input, so you have 8 boolean algebraic equations. Since the equation is sum of bit products, we will name it “Sum Of Product Decomposition”. This job is tedious, or probabably will get you sick. But hope not so. Lets sacrifice our brain and deal with those complicated equation just to satisty ourself. However, this equation might be important if you want to design such an ASIC (Application Specific Integrated Circuit) for Rijndael cipher. Lets name this “Sum Of Product decomposition”.

The last one, which named “analytical implementation” was derived theoretically using abstract math. Although it sound more horrible than “Sum Of Product decomposition”, but believe me, this way will result the most efficient Rijndael’s SBOX implementation in logic gates. Furthermore, you can also hack the circuit to reduce circuit cost by combining SBOX and Inverse SBOX of Rijndael algorithm. Hmmm… sound nice and more practical huh . Besides it results simpler circuit, it also results cheaper circuit. Every engineer are looking for fast, simple and cheap circuit, no one could deny this. However, to proceeed this method, we need to understand abstract math at least in simple way.

Am i talking too much? sorry then. Lets get ourself dirty . Next, i will explain you those 4 ways of implementing Rijndael’s SBOX and even inverse of Rijndael’s SBOX. Hopefully you get the the point, dont blame me if i confuse you .

1. ROM Lookup Table

This way of implemention is wasy to do. All you have to do is to allocate 2×256 bytes or 512 Bytes of ROM/EEPROM and fill the first 256 bytes of it with the value of Rijndael’s SBOX and the other 256 bytes by the inverse of Rijndael’s SBOX. Sounds easy huh!. But you have to guarantee when you connect SBOX input to address of ROM/EEPROM and you conncet connect SBOX output from ROM/EEPROM, you get exactly like what the specification said. Simply treat addresses as input port and data busses as output port of SBOX. Below are the table of SBOX and inverse SBOX of rijndael algorithm:

Rijndael SBOX

Rijndael Inverse SBOX

I’ll draw you some pictures also, hopefully it will helps you.

If you use 256 bytes of ROM/EEPROM use configuration below:

If you use 512 bytes of ROM/EEPROM and cascaded SBOX and inverse SBOX, use configuration below:

Please note that:
x₁..x₇ : the input lookup table (SBOX or inverse SBOX)
y₁..y₇ : the output lookup table (SBOX or inverse SBOX)
a₁..a₇ : the ROM/EEPROM address bits
d₁..d₇ : the ROM/EEPROM data bits

2. Minterm/Maxterm decomposition

Deriving each minterms of each bit of SBOX/Inverse SBOX probably too much if it shown here, I’ll just show one of them, to keep this explanation clear and understandable. Lets have a look to 7th bit of SBOX table. First, we have to convert hexadecimal notation and then we extract them. Below is a portion of Rijndael SBOX shown in binary.

0×00 01100011
0×01 01111100
0×02 01110111
0×03 01111011
0×04 11110010
…. ……..
…. ……..
…. ……..
…. ……..
0xfc 10110000
0xfd 01010100
0xfe 10111011
0xff 00010110

If we list them, we will find that probability of “0″ occurence and probability of “1″ occurence on each bit is always the same, means 50%-50% for each of them. you can proof this if you want to, please let me know if there are mistaken here. Sounds logically true, because each of input combination will be mapped uniquely to output combination and no collision at all. In addition, SBOX and inverse of SBOX are reciprocal, this is also proof that there are no collision on both SBOX and Inverse of SBOX. Hopefully you understand what i’m saying. I don’t know the best way to express this. Just let it flow .

For example, If “0″ occur on minterm 0×51,0×43,0xa5 and 0xf7 (else will be “1″). Since 74LS54 is an active low 4 to 16 decoder, and we use active low gating, therefore we use OR gate to combine activation signals from both decoder and finally we use AND gate to combine active low signals for OR gates. The picture is depicted below.

note that i will not implement SBOX or Inverse of SBOX on this way, because its innefective. I wrote this implementation here just to demonstrate you that SBOX can be implemented using minterm/maxterm decomposition. So, no more drama guys, story just ended here :p .

3. Sum Of Product Decomposition

Going further from previous method, now we are going to expand each output bit as a function of 8 bit input. After function decoposed, we can express them as a sum of product. To speed up this step, we will not discuss how equation was derived from truth table i’ll just show you the result. If you learned Fundamental of Digital Design, i’m sure you can solve karnaugh map deriving equation problem while brushing teeth . In addition, this way of implementation is fast but not cost effective, because you have to such specific circuit for each SBOX and Inverse SBOX implementation. I’ll skip this method and go further to next step.

4. Analytical Implementation

The last way that i found so far to implement SBOX is about decomposition of polynomial boolean function. I really appreciate to Mr. Edwin NC Mui’s paper of Practical Implementation of AES SBOX. This paper inspired me to write analytical implementation of Rijndael SBOX.

From official explanation of AES (fips-197), we showed that SBOX table is defined by:

And Inverse SBOX is defined by :

While {a} is the value of original number that we would find for, {b} is the multiplicative inverse of {a} and {b’} is the result of SBOX substitution. In addition, s(a) is operation of finding SBOX substitution of {a} and s^-1(a) is operation of finding the inverse SBOX of {a}.

Since matrix multiplication is easlily implemented on Logic gates, now the problem is about finding the multiplicative inverse of GF(2⁸).

Based on paped authored by Edwin NC Mui, which entitled “Practical Implementation of Rijndael S-Box Using Combinational Logic“, we can define several module needed to find the implementation of AES SBOX/Inverse SBOX. The module are:

• Affine Transformation Module
• Inverse Affine Transformation Module
• Isomorphic Mapping Module
• Inverse Isomorphic Mapping Module
• GF(2⁴) Squarer Module
• GF(2⁴) Lambda Multiplication Module
• GF(2⁴) Multiplicative Inverse Generator Module
• GF(2⁴) Multiplication Module

First, since affine transformation is defined by:

If translate the equation above into combinational logic circuit, we will find that the schematic of Affine Transformation Module is drawn as follow:

Second, the Inverse affine transformation of Rijndael algorithm is defined by:

Again, if transform equation above into combinational logic, we will find that the circuit of Inverse Affine Transformation Module is defined as follow:

Third, Isomorphic Mapping is defined by:

Forth, Inverse Isomorphic Mapping is defined by:

Fifth, The squaring function of GF(2⁴) is defined by:

Sixth, GF(2⁴) Lambda Multiplication is defined by:

Seventh, GF(2⁴) Multiplicative Inverse is defined by:

(coming soon)

Eighth, GF(2⁴) Multiplication Module is defined by:

(coming soon)

RELATED STUFF

 Practical Implementation of Rijndael S-Box Using Combinational Logic

Link:
AES (Rijndael) Simulator

Hardware Implementation of A5/1 Cipher

Have you ever heard about A5/1 stream cipher. A5 is one of three famous and “secret” GSM algorithm (instead of A3 and A8). This cipher was pretty famous because it was used to encrypt all GSM conversation on the earth. I dont know exactly, perhaps all GSM provider were migrating to A5/2 or even the newest one, which is A5/3 (a.k.a kasumi cipher).

Many crypto geniuses, crypto nerds and crypto nutters said that A5/1 cipher was not designed perfectly to encrypt GSM conversation. It was such a “dummy” cryptosystem to fool human being, so intelligent guys could work behind . Others people said that A5/2 is even weaker than A5/1 and other said that A5/3 (kasumi) is pretty secure than its two predecessors. Nice scenario ha..

I do totally blind about this, lets just assume that everyting is true. Even in fact, i even don’t give a damn to those issues . For now on, lets have fun with A5/1 cipher. Our job here is about implementing A5/1 cipher in hardware, if you are questioning this issues lets check it out .

A5/1 cipher is a kind of stream cipher that employs LFSR (Linear Feedback Shift Register). Below, i picked a picture from Wikipedia. As you can see, A5/1 cipher uses 3 shift registers with different length and different taps. Taps are used to determine next Least Significant Bit of Shift Register, when it is going to be shifted. For example, register R1 which has 19 bits length, it taps and XORs its 13rd, 16th, 17th and 18th bit to produce next Least Significant Bit. R2 and R3 also have their own way to tap inputs and produce next least significant bit.

When clock occurs, each bit will shifted 1 unit to the left. The most left bit (least significant bit) will be filled by value that produced by each taps output. Lets just see the picture, it is easier to understand than describing word by word literally.

Notice that all those three register have such a “clocking rule”. It is said that a register will be clocked if its middle bit equal to majority bit of all middle bit from each registers. Majority bit will be “1″ if and only if 2 or more middle bits are “1″, else will be zero. From the picture, you can see that middle bit is colored orange.

Middle bit of R1 = bit 8, lets define this bit as x₁
Middle bit of R2 = bit 10, let define this bit as x₂
Middle bit of R3 = bit 10, lets define this bit as x₃

Lets define y₁ as clocking condition of R1
Lets define y₂ as clocking condition of R2
Lets define y₃ as clocking condition of R3

if y₁ =”1″ then R1 is clocked, and so on for R2 and R3.

From truth table, we can derive karnaugh-map table then retrieve boolean equation as follows:

y₁ = m₀ + m₁ + m₂ + m₅ + m₆ + m₇
y₂ = m₀ + m₁ + m₃ + m₄ + m₆ + m₇
y₃ = m₀ + m₂ + m₃ + m₄ + m₅ + m₇

Finally, we get ourself to destinantion. Lets draw everything clearly .

Clocking Control (Just click it to see full-sized one)

The complete picture of A5/1 cipher is depicted below (click it to see the full-sized one).

RELATED STUFF

References
 Pedagogical Implementation Of A5/1 Cipher
A5 Cipher

Link
GSM Encryption
GSM Security
GSM Algorithm
A5 cipher
COMP128