The Hardware Side of Cryptography

6 March 2008

Hardware Implementation of A5/1 Cipher

Filed under: encryption, logic gate — Tags: , , , , , , , — edipermadi @ 11:39 am

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.

a5_cipher.png

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:

a5_truth_table.png

y1 = m0 + m1 + m2 + m5 + m6 + m7
y2 = m0 + m1 + m3 + m4 + m6 + m7
y3 = m0 + m2 + m3 + m4 + m5 + m7

y1.png
y2.png
y3.png

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

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).

Hot news! : A5/1 Implementation on PIC16F84 microcontroller

RELATED STUFF

References
Pedagogical Implementation Of A5/1 Cipher
A5 Cipher

6 Comments »

  1. Hi , it was very helpful for me . Can you please tell me the importance of implementing a5/1 algorithm on hardware or VLSI ? . It would be of great help to me . Thanks

    Comment by Ranjit — 13 September 2011 @ 8:39 am

    • well, i just did this for the sake of curiosity. if you need performance vlsi helps

      Comment by edipermadi — 13 September 2011 @ 3:35 pm

  2. sorry, it was not accessible to me

    Comment by edipermadi — 22 March 2012 @ 5:25 am

  3. this one is caesar cipher

    Comment by edipermadi — 22 March 2012 @ 5:25 am

  4. Hallo mas permadi, kira-kira butuh berapa lama untuk menghasilkan kunci bit jika algoritma a5-1 di implementasi ke microcontroller arm 7. thanks.

    Comment by sutomo — 12 September 2012 @ 12:49 pm

    • Hehe. Maaf saya belum benchmark d arm7. Jadi ndak tahu

      Comment by edipermadi — 13 September 2012 @ 9:24 am


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: