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 x1
Middle bit of R2 = bit 10, let define this bit as x2
Middle bit of R3 = bit 10, lets define this bit as x3
Lets define y1 as clocking condition of R1
Lets define y2 as clocking condition of R2
Lets define y3 as clocking condition of R3
if y1 =”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:
y1 = m0 + m1 + m2 + m5 + m6 + m7
y2 = m0 + m1 + m3 + m4 + m6 + m7
y3 = m0 + m2 + m3 + m4 + m5 + m7
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
