Multiplication is usually based on addition. When we have to add value exactly amount of times we can just multiply to get the same value. Can we do it here with Galois addition? No! When we add two identical values together we end up with a neutral element of addition! It's not very crypto when you can simply guess the result!
Inside Galois Field the multiplication is defined in a very particular way. The moment we see a "" we stop thinking about the number as a binary value, we think about it as a polynomial. Let's take numbers and and write them in binary.
We use the bit values from those numbers to create two polynomials.
And multiply those polynomials.
Now we have to switch it back from the polynomial to a number. First we take all the constants write them down.
Time to make a classical "modulo two" on every digit. This means that we change every even number to , and every odd number to . This leaves is with a large binary number.
The size of the value is a problem because we only have eight bits to store the solution. To solve it we need to use Galois Modulo and our old friend number .
This will become very interesting in next chapter, but first I need to explain another concept.
What's the neutral element of Galois Multiplication? I will prove you that it's a vector of eight bits that looks exactly like this
Now pay attention! I'm proving it by multiplying two binary values.
Now we change them into polynomials.
And multiply them as above.
When we change it back from polynomial into binary we get again
def Multiply(a, b):
result = 0;
for i in range(31):
bit = (a >> i) & 0x1
if bit == 0x1:
result ^= (b << i);
Do you remember how they taught You addition is school? Remember how ? Forget all of that! From now on ! Why? Because now we are in Galois Field! And they have rules here young lady! Oh, and subtraction. Remember how subtraction used to be reverse of addition? It still is, but it's also the same operation. Easy huh?
From now on when we hear "add" we think "xor"! "Exclusive Or" is a very useful operation that has been used in cryptography for a long time. We will not be using it's full potential though. Just the basics. Xor is a binary operation. This means that if we want to add two numbers together we need to know their binary representations. The result is calculated by compering one by one same significant bits of two numbers and xoring them. This means writing if they are different, and when they are the same.
Explanation time! You see the three red bits? First two are the same so we write in the result. Two orange ones are different that's why the resulting binary value is . If You read the previous chapter You probably expected to see somewhere a modulo. You are right. I chose to use the simplest and not formal definition of xor. The proper one uses "normal" addition and "normal" modulo.
And how will subtraction work? Probably we should go bit by bit and do "normal" subtraction and "normal" modulo two like this:. You don't believe me that's the same as a addition? Let me show You!
Two identical binary values give us and two different ones give us . You have to admit this sounds a lot like my first definition of addition. I trust You're smart enough to deduce the rest.
This is a field right? So the addition and subtraction have to have a neutral element. What is it? Addition requires us to do some xor operations. So maybe we can use the neutral element of a xor? Good thinking! Neutral element of xor is a single binary zero. When we xor any binary value with a binary zero we get that value unchanged.
But overall there are eight of those operations that we have to do if we want to add two values. So we probably need eight of those zeroes. Correct! The neutral element of addition and subtraction is a vector of eight binary zeroes.
def Add(a, b):
def Subtract(a, b):
Because since the dawn of civilization government like to hide stuff from us in 1975 National Bureau of Standards got IBM to write the safest cipher in the world called DES or Data Encryption Standard! IBM is no Microsoft so they did good job. Unfortunately the bureaucracy as usual did its worst. Who needs 128 bits of key? I think 56 bits is enough! - said someone with no idea about cryptography. Because of that in 1997 DESCHAL Project brute forced through all combinations of the key and cracked it for the first time. Now I can brake it on my laptop while playing CoD.
Next time they got someone smarter to manage the whole standard. That smart person made a contest. Everyone could send their ciphers and also everyone could review them. From five finalists (Rijndael, RC6, Mars, Serpent and Twofish) one victorious emerged! Rijndael. It had many key lengths but for the standard they chose only 128 bits, 196 bits and 256 bits. So far even 128 bits is long enough, but it will be broken soon so it's better to use 256 bits when creating something new.
Did you ever read stories about how authorities are listening to your every left click? - They know everything! - Said to me once a man on the street wearing an aluminum foil hat. Because I *know* when information source is solid I started researching. How is it possible that even though everyone know how cryptography works, just by making the key your little "secret", you can safely store your precious files? Well, I found out!
There are just two rules of cryptography!
1. You should never invent your own cipher!
2. You should never implement some one else's ciphers by yourself!
Explanation of first rule is easy. What's the title of your doctorate in abstract mathematics? What? You don't have one? Then get your console and play some Halo 4!
Accepting the second rule requires a little tough love from my side. Do You really think you are better then a team of experts working for thousands of man hours fixing bugs reported by a community of hundreds of testers? Oh. You do? Then go home Mr. Schneier! You are drunk!
But since when did something displayed on a computer screen got a control over my free will? OK, there was this one time with that cat video, but never again! Oh man that cat was soo cute... Ahh! Focus! Let's ignore those two rules and learn something about currently most commonly used cipher in the world Rijndael. Also called Advanced Encryption Standard or AES for short. This pretty much means if someone finally breaks it we all are screwed.