Operations in Galois Field

In the field of cryptography, galois field has some interesting applications. An important feature of this field is it is a finite field. In simple terms, whatever be the number of operations performed on a set of inputs the output will be in a fixed range. This itself is very useful for us as with the increasing complexity of encoding of data, it is very important for it to not occupy large amount of space yet retain its complexity.

Algebraically, galois field , named in the honor of Évariste Galois, is a finite field consisting of finite numbers which is called its order. You can find information on what constitutes a galois fields and its applications all around the internet. One interesting stuff is elliptical curves over finite field. This has separate field in cryptography called the elliptical curve cryptography. Do check it out if interested. But I suggest understanding galois field before jumping into it as it gets too gibberish and alien if not without a proper foundation.

What I am going to write as a part of this blog is two operations of this field namely addition and multiplication and their implementations as a code.

Addition in Galois Field :

Let us first consider a galois field. An example of such a field will be modulo of a prime number. It is quite often used in cryptography due its difficulty in discrete logarithm problem.                                                                                        ( link : http://en.wikipedia.org/wiki/Discrete_logarithm).

Let us consider the galois filed to be 2m usually represented as GF(2m). The elements of this field can be represented as polynomials.

F = a02m-1+a12m-2+…+am-12+am       with all a’s belonging to {0,1}.

Any number belonging to this field can be represented as above. So basically a’s are series of binary bits. So to represent a number belonging to this field say GF(28), we create a variable of 8 bits. It can represent all the values belonging to this field.

Say we want to add two elements of this field, algebraically it is the sum of the two elements(polynomials) and them coefficient arithmetic mod 2 applied on the polynomial. This could also be expressed as xor of the respective binary bits of the two elements. How ? Just try to add the two elements in their binary form. We see that sum of two 1’s or two 0’s is 0 else it is 1. That is exactly the function of xor. Hence for addition of two elements of the field we can just get it done by applying XOR ( ^ ) on them.

Computationally, Ele1 + Ele2 in GF(2m) = Ele1 ^ Ele2.

Next comes multiplication.

Multiplication is performed more tediously. For the multiplication of two polynomials(elements) f(x) and g(x) we apply mod of a irreducible polynomial of this field n(x) of atleast degree m over their product.

What is a irreducible polynomial? If a polynomial can only be divide by itself and constants then it is called an irreducible polynomial.

This is done to ensure that the product is in the range of the field. This is called as reduction modulo.

So the result of their product can be written as = ( f(p) * g(p) ) modulo ( n(p) )  for GF(pm). We can see that the product depends on the n(p) we choose.

Let me show this using a small example.

Consider the field GF(28). Let us take the product of 24 and 61 in this field with our acting irreducible polynomial as n(p) = 28 + 26 + 23 + 22 + 1.

So product = (24 * 61) mod (n(p))                                                                                             =  ( ( 24 + 23) * ( 25 + 24 + 23 + 22 + 1) ) mod (n(p))                                                 =  ( 29 + 28 + 27 + 26 + 24 + 28 + 27 + 26 + 25 + 23) mod(n(p))                                 =  ( 29 + 2.28 + 2.27 + 2.26 + 25 + 2.24 + 23) mod(n(p))                                           =  ( 29 + 25 + 24 + 23 ) mod(n(p))

Now we divide 29 + 25 + 24 + 23 with 28 + 26 + 23 + 22 + 1. We get the remainder 27 + 25 + 2 which is nothing but 162.

Now let’s see how we can convert this into a working code which calculates the product given two polynomials and the irreducible polynomial. Let us see if we can simplify the above steps.

Now given f(x) = x4 + x3 and g(x) = x5 + x4 + x3 + x2 + 1 ( in this case x=2 ).

f(x) * g(x) can be represented as f(x) * (x5 + x4 + x3 + x2 + 1) mod n(x)                                                            =  ( f(x) * x5 ) mod n(x) + ( f(x) * x4 ) mod n(x) + …

We can start calculating f(x) * x mod n(x) for every iteration ( it becomes f(x) * x after 1st iteration, f(x) *x2 after 2nd iteration  and so on ) and use that value into our result whenever it is required. ( we don’t need all products .. just the ones specified by g(x) i.e. in the above case, we need f(x) , f(x)*x2, f(x)*x3, f(x)*x4, f(x)*x5. So every iteration we just need to calculate the updated f(x) * x.

Another observations is x8 modn(x) =  x8 mod ( x8 + x6 + x3 + x2 + 1) which is nothing but (x6 + x3 + x2 + 1). We can utilize this in our calculation.

Calculating f(x) * x :

Say f(x) = a7a6a5a4a3a2a1a0. If a7 is 0 then f(x) * x will not be above the range and hence the remainder is nothing but f(x). The problem is when a7 is 1. Then f(x) * x would become 1a6a5a4a3a2a1a00. This modulus n(x) would be               (x8 + a6x7+ a5x6+ a4x5+ a3x4+ a2x3+ a1x2+ a0x1) mod n(x) )                                i.e. (a6x7+ a5x6+ a4x5+ a3x4+ a2x3+ a1x2+ a0x1) mod n(x) ) + (x8 mod n(x))

The first part is within the range of our field so it remains the same and the second part we know will be n(x) – x8 ( calculated earlier).

So our result is a6a5a4a3a2a1a00 ^ ( x6 + x3 + x2 + 1).

So here’s a program which does the above :

uint8_t r = 0, t;
while (a && b) {
    if (a & 1)
    r = r ^ b;
    t = b & 0x80;
    b = b << 1;
    if (t)
        b = b ^ 0x4d;
    a = a >> 1;
} 

What does the above algorithm do ?

At every iteration, it checks if the most significant bit of b is 1 before multiplying it with x ( i.e. XOR with 0x80 = x^8). If it is 1, then it xors with n(x) – x^8. In our case, x6 + x3 + x2 + 1 is represented as 0x4d ( hexadecimal format ). If we need this result it stores it in our r variable ( a & 1 –> indicates the coefficient is 1 and that we need that multiplication) else continues with the calculation until a is zero.

Let us run this on our example 24 * 61 mod (x6 + x3 + x2 + 1). Let a = 24 and b = 61.

a) We don’t need this value. Hence continue. 00111101(61) doesn’t have x7 coefficient. Multiplies it with x. The changed polynomial is 01111010. Convert 00011000(24) into 00001100.

b) We don’t need this value. Hence continue. 01111010 doesn’t have x7 coefficient. Multiplies it with x. The changed polynomial is 11110100. Convert 00001100 into 00000110.

c) We don’t need this value. Hence continue. 1111010 has x7 coefficient. Multiplies it with x. The changed polynomial is 11101000 ^ 01001101 which is 10100101. Convert 00000110 into 00000011. We don’t need this multiplication. Hence continue.

d) We need this value. Hence result is 00000000 ^ 10100101 = 10100101 . 10100101 has x7 coefficient. Multiplies it with x. The changed polynomial is 01001010 ^ 01001101 which is 00000111. Convert 00000011 into 00000001.

e) We need this value. Hence the result is 10100101 ^ 00000111 = 10100010. 00000111 doesn’t have x7 coefficient. Multiplies it with x. The changed polynomial is 00001110. Convert 0000001 into 00000000.

f) a is zero therefore end and return the result.

Therefore our result is 10100010. This is nothing but 27 + 25 + 2 = 162.
Tada!! The above algorithm works as galois field multiplier. This algorithm is called as Peasant algorithm.

The complexity for the above algorithm is O(logn). We can further improve this and reduce the time taken for calculation which will be discussed in the future blogs. That’s it for today. Hope you all have a wonderful week !!

Tips for OPW aspirants …

With summer approaching, the OPW (http://gnome.org/opw/) comes up with new projects and organisations giving  wonderful opportunities to women to explore open source world. First timers can be quite confused how to proceed and what to do. Here is a small guide I hope will be useful to all.

Contribution_-_FLOSS_Outreach_Program_for_Women (1)

Start Early

The key to success is starting early. This is very important as things in open source projects can be quite alien to you and might require a lot of time to understand. Even solving bugs sometimes can be difficult if one is an amateur in that area/language. Starting early will help you to take your time and not cramp things in the last minute. This will also increase the possibility of your acceptance. Make sure you start with couple of organisations you are interested in and finally narrow it down to one when you are confident. You can also apply for more than one organisation too.

Ask Questions 

It is very important to ask questions whenever in doubt even though it may seem quite silly to you or the person answering. Nobody expects you to know everything when you enter. The people in these organisations are very friendly and will patiently answer your doubts. This will also help mentors to understand to your progress. It will build a good relationship with your mentors as they are the people who will be guiding you all along your project. But remember, don’t ask to ask. Do not ask questions like : ” Hey, I am having some problem with the code. Can somebody help me”. Ask the right questions. Be specific of what your problem is.

Choose your domain

Choose the project which is interesting to you. If you feel it is a burden, then it is not what you want to do. Go through the prerequisites and see what match with your skill list.There are many interesting projects which come up every year from coding to documentation. You can come up with your own proposal too. If you find a project interesting, you can try even if you don’t have the required skills. It might be difficult initially but it is worth learning. Trust me!! Where better than internships to learn new things. But you don’t want to miss out the fun element.

Solve bugs or build applications

Solve bugs which are generally put up in the issues page, which every organisation has. Or build an application useful for the project. These are just to understand that you have sufficient knowledge of the domain and the project. Add your past work and experience to your application.

Be ethical

It is VERY important to behave properly. Many people around the world would be working in these organisations along with you. A sense of proper behavior is expected of everyone. NO slang, foul language is allowed. There is a lot of info about ethics of opensource in the internet which you can . Be respectful to your peers and mentors.

Mentors are humans too

Mentors are just like you, contributing along with various other activities in their life. Be patient if your mentor doesn’t reply immediately. They will surely get back to you.

Be determined and work hard

Finally it is your determination and hard work which will decide your acceptance. Be focused and spend quality amount of time on your application. You will definitely get through it.

These are useful if you are applying for GSOC too. If your organisation is participating in both OPW and GSOC you can apply for both. You can later discuss with your mentor on which to choose. So all the best for all the aspirants. Hope you have a wonderful summer ahead !!

Ciphers ??

Hey there .

Its been a long weekend and finally I am here with my second blog in which , as I promised , I will be talking about ciphers . Yayy 😀 … okay, not so cool yet !!

Almost everyone knows what’s a cipher. Lots of sci-fi movies and books have been written on this topic. For example, the very famous Da Vinci Code by Dan Brown where Robert Langdon ( played by the awesome Tom Hanks in the movie 😀 ) goes after solving a cryptic message.                                                                                                                                                                                                                                                                             cipher3                                                      The very famous Jefferson’s cipher

Let’s get to the boring stuff behind ciphers. Just Kidding !! It starts to get even more interesting now.

What’s a cipher ?

If we go by the definition of Wikipedia, it is an algorithm for performing encryption and decryption. In simpler words, it follows a series of steps to encode the data and also decode it. Encoding and decoding is something we all might be familiar with. Remember the secret messages we passed to our hands filled with weird symbols  or the coded language we came up with ? Yep. Exactly that !! The method in which we coded or decoded the messages is nothing but a cipher.

We have a series of steps to encode the data into something cryptic and decode it with a similar method. In the case of the secret messages, it used to be some symbols representing the letters of the alphabet. Something like this, I guess :

coded_language_by_ophelia11-d4cjff4

Well, ours was more filled with hearts, bows, and smileys ;). Anyways, this is a perfect example of a simple cipher. Now if we have a message which needs to be sent secretly, we transform the message as per our coded language and send it. Simple!! ( Not so simple actually. Why? That’s a completely different discussion for another post.)

Another simple example could be a substitution cipher. For example, when we encrypt a message by replacing all the letters by their second successive letter. A will be replaced by C, B by D, and so on [Encoding]

So a message like ” Hi what’s up ?” can be “Jk yjcv’u wr?”. Totally meaningless if you try to read it plainly. But the “real” message is hidden in the crypt message or the “cipher text”. Now, if the person on the other end wants to decode it he just needs to substitute all the letters with their second predecessor. [Decoding]

Where does cipher come in this ?

The job of a cipher is to encode or decode the data correctly and safely. Why correctly ? Of course, the other person shouldn’t end up getting the wrong message now , right? It could be disastrous if a country planned to send the information to some secret base about a missile destination and it ended up in the wrong place ?? Scary. Yeah, I watch a lot of sci-fi 😛

Why safety? Now, you don’t want the person who is passing you secret message to your friend to know what it means. Attacks are an important way to understand the vulnerabilities of the cipher which we will see later.

Cryptography :

This whole process comes under something known as CRYPTOGRAPHY. It forms a major branch of Mathematics. This OLYMPUS DIGITAL CAMERAhas a long history dating back to Greeks and Egyptians. ( Hey, there were always spies , weren’t they? )  Most of them are called classical as they relied mostly on using pen and paper. Later on came complex machines and today we are using computers to encrypt data. The cryptography has had quite a mark in the history of the world. Breaking the German naval codes, which were thought to be unbreakable, in World War II played an important role in shaping the war.                                                                                                                                                                      Modern cryptography has reached new heights and electronics are being used to perform encryption and decryption on large data at a great speed. New and complex algorithms are being designed that turns data into digital gibberish using long keys efficiently. Attempts are being made to reduce the possibility of attacks on the algorithms by avoiding weaknesses in the method. AES, Blowfish, Twofish, variants of DES called triple DES are all examples of modern symmetric ciphers. The general function of all these ciphers is to break down message into chunks and encrypt each chunk with the help of a key, known to only the end persons, and decrypt using the same key. Asymmetric ciphers are slightly different relying on two keys one public and other private for the function.

On the whole, cryptography and ciphers offer a great opportunity for exploration and inventions. Work is going on to come up with newer algorithms with less vulnerabilities and greater accuracy.

That’s it for this post. If you find this interesting, I encourage you to explore and learn more about this. I am working on three algorithms called CAST128, Camellia and Twofish. I remind you I am still exploring the field of cryptography and if there is any naivety in the post, please excuse me as I am trying my best to share whatever I am learning in a proper manner. I will come up with next blog in a few days which will focus on basics of some modern ciphers, mainly symmetric ciphers. I end with this final picture :

code_talkers

Hope you all have a good week. Take care !! Until next time, Byee 😀

Disclaimer : I do not own any of the pictures included in this post. 😛  

Blogging for the first time …

“I was nervous. Like an ice-cube, I just froze up. Then I melted in some strange guy’s drink.”
Jarod Kintz, The Titanic would never have sunk if it were made out of a sink.

My feeling when I first heard that I was supposed to publish a blog every week as a part of my internship. I hated the idea of writing and postponed it for weeks , much to the dismay of my mom who found it difficult to understand that I couldn’t come up with a few sentences about my activities (^_^;). ( I can read a thousand page book on politics of china easily than write a blog !! )

So, here I am to share my experiences and knowledge while hopefully learn something along the way. Let me tell you where this all started. Last month, I got selected for the OPW – Outreach Program for Women internship as a part of which I will be working for the next two months with Ffmpeg on Symmetric block ciphers and optimization. I was very happy when I first got to know that I was selected as it has always been my dream to contribute to open source and hopefully be a full-time part of it.

Looking at others’ work contribution and the level of expertise , I was initially quite scared to even make an attempt. My first attempt had gone wrong terribly with my OS crashing 6 times or so !! . But this time I made up my mind that I will succeed and started going through the organisations a month ahead of the application deadline. I consider myself to be very lucky that I came across Ffmpeg as it had the very project I was most comfortable in. 😀 I am well versed with c, c++ and very much interested in cryptography and security. I got to meet the sweetest mentor ever, Giorgio , who was very patient and understanding right from the first day. Then I sent a patch as a qualification task, completed my application and finally got selected !

My work for the three months is mostly to add twofish, camellia and cast 128 algorithms to the library of ffmpeg. I am almost done with cast 128 and camellia. I am planning to publish few blogs on the basics of ciphers in the next couple of days. Although I am just an amateur in the field of cryptology, I hope I will be able to share and learn along the way. That’s it for this one. I am glad that you have kept up with my blabber which I guess was quite boring !! ( I felt the same while writing 😉 ) . Nevertheless, I will try to learn to blog better too. ( I am thinking to take up a course on blogging , what say ? 😛 ) Finally, a very happy and a prosperous new year to all of you.