This is a description of the Twofish encryption algorithm. Really it is the description of Twofish 128, 192 and 256 which are versions of Twofish with different key lengths. I am writing this to improve my understanding and also because I have found other descriptions of this algorithm I have found online to be confusing (there may be errors in what I have written). If you are trying to understand the Twofish algorithm I hope you will find this repo useful but this should not be used for encryption purposes. This code has support for all three versions of Twofish by changing the value of N when generating the keys.
I am just some guy in a room, I have no training in cryptography and this code has not been checked by anyone with real training in cryptography. Just going through the code for this write up I found at least one major error in the implementation so please do not use this code for any real encryption purposes. I hope you will find this document informative and that the code may be helpful to you in understanding the Twofish algorithm but please do not attempt to use this code for real world encryption.
The code in this repo can be divided into two sections, a subkey generation section and a encryption/decryption section.
In this section we are going to first generate three important vectors, Me, Mo and S. The M vectors we are then going to use to generate the subkeys, Kj and the S vector will be used in the encryption and decryption of the input text.
The process for generating these vectors changes slightly depending on whether we are working with Twofish 128, 192 or 256. The length of these vectors will be determined by the value of σ which is defined below
σ = N/64
where N is the length of the key. We are now going to convert the key M into 2σ words of 32 bits each. This will be the vector Mi. These will then be used to generate the vectors Me and Mo using the logic shown below
Me = (M0, M2, ..., M2σ-2) Mo = (M1, M3, ..., M2σ-1)
The third word vector, S is generated using a matrix multiplication in the GF(28) field. First a 8 element vector is created from the vector m, which is the key split into bytes (8 bit words). Now the words of the S vector will be generated using the logic shown below (in an png image because I can't get matrix mutliplication to look right in markdown)
The 4, 8 bit words generated by this function are combined into a single 32 bit word which is added to the S vector until σ 32 bit words have been generated. This multiplication is done within the finite field GF(28). This means that any mathematical function must take place within the finite field GF(28), the process for which is described in the following sub-sub-sub-section.
The field GF(28) is a finite field containing 28 elements, also known as a Galois field or Galois ring field. This field is the ring of integers 28 long. Within this ring you can perform the operations of addition, subtraction and multiplication but the input and the results must always be contained within the field.
Addition in this field is performed using a XOR operation, doubling is done using a bitwise shift to the left and halving is done using a bitwise shift to the right. Knowing this we can use Russian peasant multiplication in order to perform multiplication within GF(28)
Russian peasant multiplication is an algorithm for performing multiplication whereupon you can multiply two numbers A and B. In this algorithm we will first initialise p as zero before starting the first round of the multiplication process.
With each round we first check if B is odd, if it is we add A to p (using XOR since we are working in GF(28)). Next we double A, using a rightwise bitshift, and check if it is outside GF(28). If A is outside GF(28) we will bring the value of A back inside the field by XORing A with the primitive polynomial, which is valued at 283 for GF(28). Next we will half B using a bitshift to the left, if this results in B being equal to zero we end the algorithm and return p as the result. Otherwise we go back to the start of the loop and perform another round.
Now we need to introduce the function h which will be used to generate the subkeys from the vectors Me and Mo and which will also be used in combination with the S vector in the encryption step of the algorithm. The structure of the function h is shown below
In this diagram the fact that the round 3, 4 and 5 are the only rounds which will always be used is demonstrated using the switches connecting round 2 and 1 to the rest of the blocks. When σ is greater than 3, i.e. key length is 192 or 256, then round 2 is used and if σ is equal to 4, i.e. key length is 256, then all rounds are used. The blocks q0 and q1 are permutation blocks which work on 8 bit words. They follow the logic show below where x is the input to the block and y is the output.
a0, b0 = [x/16], x % 16
a1 = a0 ⨁ b0
b1 = a0 ⨁ ROR4(b0, 1) ⨁ 8a0 % 16
a2, b2 = t0[a1], t1[b1]
a3 = a2 ⨁ b2
b3 = a2 ⨁ ROR4(b2, 1) ⨁ 8a2 % 16
a4, b4 = t2[a3], t3[b3]
y = 16b4 + a4
The logic is the same for both q0 and q1 but the substitution boxes, ti, are different in q0 and q1.
Finally using the intermediary vectors and the function h we may generate the subkeys Kj by using the logic chain shown below
ρ = 224 + 216 + 28 + 20
Ai = h(2iρ, Me)
Bi = ROL(h(2i + 1, M0), 8)
K2i = (Ai + Bi) % 232
K2i + 1 = ROL(Ai + 2Bi) % 232, 9)
In this way the 40 subkeys are generated which will be used in combination with the S vector in order to perform both encryption and decryption.
The general shape of the encryption function is shown below.
In this diagram you can see the subkeys K0-3 being used as an initial whitening step as the 128 bit input is broken into 4, 32 bit blocks. Then the left hand side words are put through h blocks with the S vector resulting in two 32 bit words which are crossed with one another in a PHT block which uses modulo addition to combine them. The results are then modulo added to the subkeys K2r+8 and K2r + 9 where r is the round number. The results from this are XORed with segments from the right hand side of the word after a ROL by one bit is applied to word R3. Once the XOR is done a ROR by one bit is applied to R2 and the left and right sides are swapped around so that the next round may begin. The encryption function is applied 16 times before a final swap to undo the swap of the final round and the output is whitened using the subkeys K4-7. The resulting 4, 32 bit words are then recombined and returned as the encrypted block.
In order to perform decryption the process is run in reverse. The diagram for this is shown below.
In this diagram the algorithm has been reversed as has the order of the keys being used with the swapping happening at the start of the round rather than the end of the round and ROR of e2 happening before e2 is XORed with the modified e0 and the ROL of e3 happening after e3 is XORed with the modified e1.
- https://en.wikipedia.org/wiki/Twofish
- https://www.schneier.com/academic/archives/1998/12/the_twofish_encrypti.html
- https://www.schneier.com/academic/paperfiles/paper-twofish-paper.pdf
- https://en.wikipedia.org/wiki/Finite_field
- http://www.cs.cas.cz/portal/AlgoMath/NumberTheory/Arithmetics/Multiplication/PeasantMultiplication.htm
- https://sites.math.washington.edu/~morrow/336_12/papers/juan.pdf