AES (06) Galois Multiplication

Open LockMultiplication is usually based on addition. When we have to add value x exactly y amount of times we can just multiply x \cdot y 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! x \oplus x = 0 It's not very crypto when you can simply guess the result!

Multiplication

Inside Galois Field the multiplication is defined in a very particular way. The moment we see a "\cdot" we stop thinking about the number as a binary value, we think about it as a polynomial. Let's take numbers 83 and 202 and write them in binary.

 83 = 01010011b
 202 = 11001010b

We use the bit values from those numbers to create two polynomials.

 0x^7 +  1x^6 + 0x^5 + 1x^4 + 0x^3 + 0x^2 + 1x^1 + 1x^0
 1x^7 +  1x^6 + 0x^5 + 0x^4 + 1x^3 + 0x^2 + 1x^1 + 0x^0

And multiply those polynomials.

 (x^6 + x^4 + x^1 + x^0) \cdot (x^7 + x^6 + x^3 + x^1)
 =
 \begin{align*} (x^{13} + x^{12} + x^{9} + x^{7}) + (x^{11} + x^{10} + x^{7} + x^{5}) + (x^{8} + x^{7} + x^{4} + x^{1}) + (x^{7} + x^{6} + x^{3} + x^{1}) \end{align*}
 =
 \begin{align*} 1x^{13} + 1x^{12} + 1x^{11} + 1x^{10} + 1x^{9} + 1x^{8} + 4x^{7} + 1x^{6} + 1x^{5} +  1x^{4} + 1x^{3} + 1x^{1} + 0x^{0}\end{align*}

Now we have to switch it back from the polynomial to a number. First we take all the constants write them down.

 1111114111110

Time to make a classical "modulo two" on every digit. This means that we change every even number to 0, and every odd number to 1. This leaves is with a large binary number.

 1111110111110b

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

 1111110111110b \;\%\; 283
 =
 1111110111110b \;\%\;  100011011b
 =
 00000001b

This will become very interesting in next chapter, but first I need to explain another concept.

Neutral Element

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

 00000001b .

Now pay attention! I'm proving it by multiplying two binary values.

 a_{7}a_{6}a_{5}a_{4}a_{3}a_{2}a_{1}a_{0} \quad a_{x} \in \{0,1\}
 00000001b

Now we change them into polynomials.

 a_{7}x^7 +  a_{6}x^6 + a_{5}x^5 + a_{4}x^4 + a_{3}x^3 + a_{2}x^2 + a_{1}x^1 + a_{0}x^0
 0x^7 +  0x^6 + 0x^5 + 0x^4 + 0x^3 + 0x^2 + 0x^1 + 1x^0

And multiply them as above.

 (a_{7}x^7 +  a_{6}x^6 + a_{5}x^5 + a_{4}x^4 + a_{3}x^3 + a_{2}x^2 + a_{1}x^1 + a_{0}x^0)
 \cdot
 (0x^7 +  0x^6 + 0x^5 + 0x^4 + 0x^3 + 0x^2 + 0x^1 + 1x^0)
 =
 (a_{7}x^7 +  a_{6}x^6 + a_{5}x^5 + a_{4}x^4 + a_{3}x^3 + a_{2}x^2 + a_{1}x^1 + a_{0}x^0)

When we change it back from polynomial into binary we get again

 a_{7}a_{6}a_{5}a_{4}a_{3}a_{2}a_{1}a_{0} \quad a_{x} \in \{0,1\}

AES (05) Galois Modulo

Open LockRemember the value 283 I wrote few chapters ago? Now we are going to use it. Imagine that we have an operation that ends up giving us 27226. That's way bigger than 2^8-1. We need to make the result much smaller. Fortunately there is a method to do that. Inside our field we can define something called a modulo. Fortunately for us computers can perform it very easily. Let's start from writing that value in binary.

27226 = 00000000000000000110101001011010b

Now we move from left to right bit by bit. Yes, I know that the first bits can be omitted, but in software we will probably use here a thirty-two bit unsigned integer variable so just starting every time at position thirty-one makes everything much easier. To get the value of thirty-first bit all we have to do is shift the number right by thirty-one positions. Logical isn't it?

(27226 \gg 31) = 0

We got a binary zero. That's great, because we don't have to do anything in this case. Let's continue checking bits by decreasing length of the shift until we hit binary value 1.

(27226 \gg 16) = 0
(27226 \gg 15) = 0
(27226 \gg 14) = 1

Got it! What do we do now? We take the value 283 save it as a thirty-two bit unsigned integer variable and left shift it six times. Why exactly six times? Because we want to move the most significant bit that's not a zero to position fourteen.

 00000000000000000\color{red}{100011011}000000b

Cool things happen when we subtract those two values. Just remember that in this world subtraction is done by using the bit by bit xor operation. Lets try it now.

 00000000000000000\color{red}{1}10101001011010b
\; - \;
 00000000000000000\underline{\color{red}{1}00011011}000000b
\; = \;
 00000000000000000\color{red}{0}10110010011010b

See what happened to 1 on position fourteen? It disappeared! This means that we can continue.

(27226 \gg 14) = 0
(27226 \gg 13) = 1

Got another 1 this time on position thirteen! This can mean only one. We shift our 283 left five times and subtract it from previous result!

 000000000000000000\color{red}{1}0110010011010b
\; - \;
 000000000000000000\underline{\color{red}{1}00011011}00000b
\; = \;
 000000000000000000\color{red}{0}0111111111010b

This is how we got rid of our uninvited guest on position thirteen. We can continue and find next problem.

(27226 \gg 13) = 0
(27226 \gg 12) = 0
(27226 \gg 11) = 1

At this moment everyone smart enough probably guessed the algorithm. But just in case I'm wrong about that I'm going to show explicitly every operation we need to make.

 00000000000000000000\color{red}{1}11111111010b
 00000000000000000000\underline{\color{red}{1}00011011}000b
 \Downarrow
 00000000000000000000\color{red}{0}\color{orange}{1}1100100010b
 000000000000000000000\underline{\color{orange}{1}00011011}00b
 \Downarrow
 000000000000000000000\color{orange}{0}\color{blue}{1}101001110b
 0000000000000000000000\underline{\color{blue}{1}00011011}0b
 \Downarrow
 0000000000000000000000\color{blue}{0}\color{green}{1}01111000b
 00000000000000000000000\underline{\color{green}{1}00011011}b
 \Downarrow
 00000000000000000000000\color{green}{0}01100011b

And we are done! We just change the binary value to decimal using windows calculator set to programmer mode and we can summarize that in Galois finite field:

27226 \;\%\; 283 = 99

AES (04) Galois Addition

Open LockDo you remember how they taught You addition is school? Remember how 1+1=2? Forget all of that! From now on 1+1=0! 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?

Addition

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 1 if they are different, and 0 when they are the same.

 174 = 10\color{red}{1}0111\color{orange}{0}b
 +
 113 = 01\color{red}{1}1000\color{orange}{1}b
 =
 223 = 11\color{red}{0}1111\color{orange}{1}b

Explanation time! You see the three red bits? First two are the same so we write 0 in the result. Two orange ones are different that's why the resulting binary value is 1. 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.

\forall x,y \in \{0,1\} \quad x \oplus y = (x + y) \% 2

Subtraction

And how will subtraction work? Probably we should go bit by bit and do "normal" subtraction and "normal" modulo two like this:(x - y) \% 2. You don't believe me that's the same as a addition? Let me show You!

 (0 - 0) \% 2 = 0 \% 2 = 0
 (0 - 1) \% 2 = -1 \% 2 = 1
 (1 - 0) \% 2 = 1 \% 2 = 1
 (1 - 1) \% 2 = 0 \% 2 = 0

Two identical binary values give us 0 and two different ones give us 1. You have to admit this sounds a lot like my first definition of addition. I trust You're smart enough to deduce the rest.

Neutral Element

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.

 0 \oplus 0 = 0
 0 \oplus 1 = 1

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.

 0 = 00000000b

AES (03) Galois Finite Field

Open LockCongratulations You are now learning now about Galois Finite Field! As everything in math it has a kick-ass name! But it's pretty easy if you just read a blog post about it. Preferably a blog post from someone who understands discrete math, and does not like to write to many complicated definitions. If you need more info read a book! Damn, You are lazy!

This is a field: (K,+,\cdot,1,0) Looks simple right?

  • "K" is a set of all numbers that we can use.
  • "+" is an operation that behaves just like addition.
  • "\cdot" is an operation that behaves just like multiplication.
  • "1" is an element of "K" that's neutral to "\cdot"
  • "0" is an element of "K" that's neutral to "+"

The word "neutral" means that for every element of K:
\forall x \in K \quad x + 0 = x
\forall x \in K \quad x \cdot 1 = x

Imagine now that "K" are all Real numbers, "+" is addition, "\cdot" is multiplication, "1" is number one and "0" is number zero. Boom! We got a field which You have been using on math through all high school!

When a Field is a Finite Field? That's easy. When "K" is a finite set.

For our purpose let's define "K" as a set containing first 2^8 natural numbers. This gives us a total of 256 elements. We can write them as decimals or hexadecimals but sometimes the most useful is the binary representation. Memorize this:

K=(0, 1, 2,\ldots, 255)
K=(0x00, 0x01, 0x02,\ldots, 0xFF)
K=(00000000b, 00000001b,\ldots, 11111111b)

Having a finite "K" created a problem with "+" and "\cdot" operations. For example if "\cdot" is a normal multiplication we get 250 \cdot 20 = 250 * 20 = 5000. That's way outside of "K"! Fortunately we can easily fix this by changing the definition a little. Let's define "\cdot" as multiplication modulo 17. This gives us 250 \cdot 20 = (250 * 20) \% 17 = 5000 \% 17 = 2. And now the result popped right back into "K". We are awesome!

But why did I use 17? Because why not! I can use any number from "K" for it to work. If I work a little harder, and instead of normal addition and multiplication use definitions created by Galois, I can even use a number outside of "K". I just have to remember in that case that I need to chose a prime number.

OK so from now on lets use 283!

AES (02) History and Prehistory!

Open LockBecause 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.

AES (01) Problems with secrecy!

Open LockDid 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.