A2 encryption algorithm
Implementation manual

Contents *

1. Summary

This is technical manual how to implement A2 encryption algorithm in software. Because of compatibility all implementation must obey these instructions.

No information about the algorithm security or efficiency is present here, for more information about that consult the Thesis document.

This algorithm is designed to ensure security and confidentiality wherever it is needed. No limitations are made on secrecy level of data that are going to be encrypted with this algorithm; infinite quantity of data can be encrypted. A2 have 2174 bits key. The key is composed of two parts; table of addition constants (2048 bit long) and scenery table (128 bit long). A2 operate in 16 rounds and every round made the data transformation according to the key (part of the key used in that round). The key can be any random array of bits generated by and external source (in this case it must be 2174 bits long) or the generator proposed in this Manual can be used (in this case the key is 128 bits long).

A2 is designed to use only the basic processor operations, no S-Boxes is required and no build-in constants or large data structure are used.

This manual only describe how to implement A2 transformation function, so other sources should be consult in order to chose mode of encryption and how to generate random keys. Basically A2 supports all modes of operation, it can simultaneously encrypt and decrypt data at same time. This is vary important if you want to encrypt your communication channels; then you can use the same module both for encryption of outgoing data and for decryption of incoming data.

2. Terminology and Notation

In this manual the following notation and terminology will be used.

In this document a "word" is a 32-bit quantity and a "byte" is an eight-bit quantity. A sequence of bits can be interpreted in a natural manner as a sequence of bytes, where each consecutive group of eight bits is interpreted as a byte with the high-order (most significant) bit of each byte listed first. Similarly, a sequence of bytes can be interpreted as a sequence of 32-bit words, where each consecutive group of four bytes is interpreted as a word with the low-order (least significant) byte given first.

Let x[I] denote "x sub i". Let the symbol "+" denote addition of words (i.e., modulo-2^32 addition). Let X << s denote the 32-bit value obtained by circularly shifting (rotating) X left by s bit positions. Let ~X denote the bit-wise complement of X, and let X | Y denote the bit-wise OR of X and Y. Let X ^ Y denote the bit-wise XOR of X and Y, and let X & Y denote the bit-wise AND of X and Y.

Block is every peace of data that is currently transforming; sub-block is a quarter of block (Because the block is 128 bits long it is divided on four 32-bits sub-blocks).

About the A2 specific terminology and the names of the data structures consult the Thesis.

A2 algorithm is very simple to implement, it is harder to understand it. It have minimal memory requirements, a fully functional code is not longer than two pages. The implementation of A2 can be done on assembler level, also optimizations for speed are possible, especially on 32-bit machines. The most time consuming operation is rotation, which are done very often, but on Assembler level programming they are no problem to optimize.

Because of its simplicity and efficiency this algorithm can be use for all major cryptographic applications. It can be used in all modes of operation, ECB, OFB, CBC, CFB etc. When an IV is required it can be input separately or produced by two sub-sequential encryption of constant listed in part 2 of this document. A propose CBC mode to be used for file encryption.

3. Data structures and operations used by A2

A2 use only regular data types: 32-bit words, 8-bit word and 16-bit words. All of them are presentable on today processors. A2 use these operations: XOR, AND, NOT, OR, ADDITION (+), SUBSTRACTION (-) and SHIFT ROTATION. These data structures are used:

The key is stored in:

Rext[16][4] (2-bit data), 128 bits

Fext[16][4] (32-bit data), 2048 bits

Operation are done using:

N[4] block of data (32-bit data), 128 bits

R[4] used during key generation (32-bits), 128 bits

Fv[4] used during key generation (32-bits), 128 bits

C[4]={01234567L,89ABCDEFL,FEDCAB98L,76543210L}; constant used during key generation.

All other variables are matter of optimization and are not concerned with the algorithm design.

A2 use 4 functions, they accept 3 arguments and return a single value. Default set of operation is (using C notation):

F(x, y, z)=( ( x & y ) | ( ( ~ x ) & z ) )

G(x, y, z)=( ( ( x & z ) | ( y & ( ~ z ) ) )

H(x, y, z)=( x ^ y ^ z )

I(x, y, z)=( y ^ ( x | ( ~ z ) ) )

They are respectively assumed to be the first, second, third and forth function; and are denoted as f[0], f[1], f[2] and f[3]. Those operations are very important and have a significant impact on the algorithm security. This set is used by the most of algorithms that require operations of this type and is assumed they satisfy the request in general case.

4. A2 Algorithm Description

A2 is a block cipher, it has 16 rounds that are functionally identical; every round uses a unique part of the key to drive the transformation. Because the A2 is a Feistel Network the encryption and decryption are nearly identical processes, only the usage of key is reversed. In every round function of three sub-blocks is XORED with the sub-block that did not participate in its computation. No rearrangement is made on sub-block order.

1. The first step is to supply the algorithm with key, this is done filling the Rext and Fext variables with proper values.
2. Prepare the input data, input data must be divided on 128 bits block before the encryption / decryption process. This is no practical problem because the data is ordinary presented in bytes, so 16 bytes are used to form a block. The first byte goes on the last significant position of the block and the 16 on the most significant position.
3. Now the 16 round of encryption / decryption begin.
   1. Encryption
      1. First on every sub-block the value of Fext[r][i] is added. Where r is the number of round (first, second...); i is the index of sub-block.
      2. rrt = (Rext[r][1]+Rext[r][3])*4 + Rext[r][0]+Rext[r][2]
      3. Now the block is rotated to left for (Fext[r][0]+Fext[r][1]+Fext[r][2]+Fext[3]+11) modulo 128 places
      4. After this the following transformation is done:
         1. N[0]^=F[Rext[r][0]](N[1],N[2],N[3]);
         2. All sub-block are rotated to left for (rrt+5*Rext[r][i])%32 places, i is sub-block index
         3. N[1]^=F[Rext[r][1]](N[0],N[2],N[3]);
         4. All sub-block are rotated to left for (rrt+5*Rext[r][i])%32 places, i is sub-block index
         5. N[2]^=F[Rext[r][2]](N[0],N[1],N[3]);
         6. All sub-block are rotated to left for (rrt+5*Rext[r][i])%32 places, i is sub-block index
         7. N[3]^=F[Rext[r][3]](N[0],N[1],N[2]);
         8. All sub-block are rotated to left for (rrt+5*Rext[r][i])%32 places, i is sub-block index
      5. After all 16 round are run the encryption process is finished.
   2. Decryption
      1. rrt = (Rext[16-r][1]+Rext[16-r][3])*4 + Rext[16-r][0]+Rext[16-r][2]
      2. The following transformations are done
         1. All sub-block are rotated to right for (rrt+5*Rext[16-r][i])%32 places, i is sub-block index
         2. N[3]^=F[Rext[16-r][3]](N[1],N[2],N[3]);
         3. All sub-block are rotated to right for (rrt+5*Rext[16-r][i])%32 places, i is sub-block index
         4. N[2]^=F[Rext[16-r][2]](N[0],N[2],N[3]);
         5. All sub-block are rotated to right for (rrt+5*Rext[16-r][i])%32 places, i is sub-block index
         6. N[1]^=F[Rext[16-r][1]](N[0],N[1],N[3]);
         7. All sub-block are rotated to right for (rrt+5*Rext[16-r][i])%32 places, i is sub-block index
         8. N[0]^=F[Rext[16-r][0]](N[0],N[1],N[2]);
      3. Now the block is rotated to right for (Fext[16-r][0]+Fext[16-r][1]+Fext[16-r][2]+Fext[16-r][3]+11) modulo 128 places
      4. Every sub-block is decreased for the value of Fext[16-r][i] (where r is number of round, i is index of the sub-block.
      5. After all round are executed, the decryption process is finished.

This manual also describes procedure how to generate key. Absolute length of the key is 2172 bits, this is very long key for practical use. Only in extremely case the key should be generated by an external source of randomness, and directly inserted into the proper variables. When you chose the key externally obey to those rules:

1. The key must be random stream of bits
2. The scenery part of the key must be chose very carefully because it made a significant impact on security. Those requests should be satisfied:
   1. In every round et least 2 function operations must be used
   2. In total, all functions should be used equal number of times (or at least nearly equal).

In practice this algorithm should be used with reduced key on 128 bits. In this case the procedure described in this document must be used to create internal key. Internal key generation procedure is very similar with encryption; some additional transformations are added in order to make it as securely as possible.

1. Reset the key, the first step is to initially set all the bits of Rext and Fext to 0.
2. Fill the block with 128 bits key.
3. First the value of sub-blocks is increased by the constant C[I], where I is index of sub-block. The value of Rext is set to value of block (N). Last significant bit of N is last significant bit of Rext. Value of Fv is set to value of N.
4. Now the 16 rounds of transformation are run
   1. Value of R is set to Rext[r] where r is number of round. Now a asymmetric rearrangement of R is done, Using C notation it is:

      for(I=0;I<4;I++)

      for(j=I+1;j<4;j++)

      if(Fv[R[j]]<Fv[R[j]]) SWAP(R[j],R[I]);

   2. First on every sub-block the value of Fext[r][i] is add. Where r is the number of round (first, second...); i is the index of sub-block.
   3. rrt = (R[1]+R[3])*4 + R[0]+R[2]
   4. Now the block is rotated to left for (N[0]+N[1]+N[2]+N[3]+11) modulo 128 places
   5. After this the following transformation is done:
      1. N[0]^=Fv[Rext[r]]=F[Rext[r][0]](N[1],N[2],N[3]); Fv[Rext[r]] is subtracted form N[1],N[2] and N[3]
      2. All sub-block are rotated to left for (rrt+5*R[i])%32 places, i is sub-block index
      3. N[1]^=Fv[Rext[r]]=F[Rext[r][1]](N[0],N[2],N[3]); Fv[Rext[r]] is subtracted form N[0],N[2] and N[3]
      4. All sub-block are rotated to left for (rrt+5*R[i])%32 places, i is sub-block index
      5. N[2]^=Fv[Rext[r]]=F[Rext[r][2]](N[0],N[1],N[3]); Fv[Rext[r]] is subtracted form N[0],N[1]and N[3]
      6. All sub-block are rotated to left for (rrt+5*R[i])%32 places, i is sub-block index
      7. N[3]^=Fv[Rext[r]]=F[Rext[r][3]](N[0],N[1],N[2]); Fv[Rext[r]] is subtracted form N[0],N[1] and N[2]
      8. All sub-block are rotated to left for (rrt+5*R[i])%32 places, i is sub-block index
   6. Value of Rext[r] is set to R and value of Fext[r] is set to value of N
   7. Bits of Rext are XORed with the bits of N
5. After all 16 round are run the encryption process can be done. Now every part of Fext[I] is substituted with the cipher-text produced from it. This makes a complicated link between the Fext table entries force them to depend from all other.

In practical implementations en/decryption and key generation code can be integrated in a compact module. This is very practically solution because these codes are very similar, the second one only have some extra transformations in it.

5. Differences between A2 and Anigma

A2 development is based on Anigma. They are very similar in basic design ideas. A2 is designed to correct weakness in Anigma design. Technically Anigma is simpler, only difference are key depend rotations added in A2 which are absent in Anigma; some changes are made in key generation. All other properties are the same; Anigma can be substituted with A2 wherever it is used. Anigma is not compatible to A2. A2 can not decrypt Anigma cipher-text and vise versa.

6. Using A2 as Message digest function

A2 can be used as a message digest function, Just run it in CBC mode and encrypt the file with key {0123456789ABCDEFFEDCBA9876543210}. The last ciphertext bock is encrypted one more time. This double encrypted bock is the message digest.

7. Using A2 as Random Number Generator

A2 can be used as random number generator too. It use 2048 bit seed, and 128 bit session key to run the process.

1. Reset the internal key values
2. Fill the Fext variable with random array of bits (the seed)
3. Choose a 128 session key and use it to run A2 key generation process
4. Encrypt the key, this ciphertext is the first random block
5. If more then 1 random block is need use this procedure:
   0. Run the key generation process with the ciphertext from the previous iteration
   1. Use the ciphertext from the previous round as plaintext and encrypt it, produced ciphertext is next random block

Using C notation:

char seed[256]; /* the seed used by the implementation */

char block[16]; /* session key */

char rndb[1000][16];

A2("",A2_RESET);

A2(seed,A2_DKI);

for(I=0;I<blocks_needed;I++)

{

A2(block,A2_KEYGEN);

A2(block,A2_ENCRYPT);

memcpy(&rndb[I][0],&block,16);

}

8. Key Generation (technical instructions)

First thing that should be done before use of A2 is to reset its internal values, { A2("",A2_RESET); }. Now you should choose a key you will use to encrypt and decrypt. There is two ways to initiate the key:

1. Directly, Any string 2176 bits long can be use as a key for A2 function. If the string is memorized in { char *key } that the initialization is like { A2(key,A2_DKI); }
2. Generated using 128-bit string. If this approach is used the key will be generated by the A2 function, only the 128-bit string will be required for latter decryption. If the string is memorized in { char *str } the initialization is like { A2(str,A2_KEYGEN); }. This approach is the one that should be used in practice.

When the value of the internal key is needed, use { A2(buff,A2_GETKEY); } this will copy the key into the buff. After this the key can be store modify or whatever you want.

ANEX:

This algorithm can be used with variable key length, up to 2176 bits. If the one you want to use have fewer that 128 bits, the rest should be filled up to 128 bits with 0. If more than 128 but less then 2176-bit key is required then the following procedure should be use:

A2("",A2_RESET);

A2(key_1,A2_KEYGEN);

A2(key_2,A2_KEYGEN);

.

.

.

A2(key_n,A2_KEYGEN);

All values of key_i are 128 bit long, if the wished key length is not dividable with 128 the last key will be filled up to 128 bits with 0. n must be less than 18, if more that 17 keys are use no improvement in security will be made.

More information about this way of key generation is supply in A2 Thesis. This mode is important to cryptographers and cryptoanlysists.

9. Implementation

Here an implementation of A2 module is given. It is written in C and should be possible to compile it with all available compilers (I prefer Borland). Here the interface of the module:

/* Project: ASIGMATIKON, Anigma Function Redesign, A2 */

#include <stdio.h>

#include <mem.h>

#define F(x,y,z) ((x&y)|((~x)&z))

#define G(x,y,z) ((x&z)|(y&(~z)))

#define H(x,y,z) (x^y^z)

#define I(x,y,z) (y^(x|(~z)))

#define ROT32R(a,m) ((a>>m)|(a<<(32-m)))

#define ROT32L(a,m) ((a<<m)|(a>>(32-m)))

#define A2_ENCRYPT 1

#define A2_DECRYPT 0

#define A2_KEYGEN 2

#define A2_DKI 3

#define A2_RESET 4

#define A2_GETKEY 5

int A2(char *buff,int mode);  

A2 have easy to use interface, A2(char *buff, int mode), only two arguments are needed for all operations.

 

A2("",A2_RESET); all internal values are reset on 0, the first argument is not needed;

A2(buff,A2_KEYGEN); key generation procedure is run according to content in the buff

A2(buff,A2_DKI); the content of buff is inserted as a key, the buff must contain exactly 2172 bits.

A2(buff,A2_GETKEY); the content of internal key is stored in buff in this order: Fext[0][0], Fext[0][1]...Fext[15][3], Rext[0][0], Rext[0][1]...Rext[15][3]; Fext[j][k] is the k-th sub-block of the j-th round key (32bit); Rext[j][k] is a k-th sub-block of the j-th round scenery (2bits);

A2(buff,A2_ENCRYPT); encrypt the content of buff according to stored key in Fext and Rext; the output is written in buff

 

A2(buff,A2_DECRYPT); decrypt in the same manner.

 

/* Project: ASIGMATIKON, Anigma Function Redesign, A2 */

int A2(char *buff, int mode)

{

static unsigned long N[4],H[3],Fv[4], Fext[16][4];

static int R[4],Rext[16][4];

static const

RR=16, RT=11, RRT=5, P[4][3]={{1,2,3},{0,2,3},{0,1,3},{0,1,2}};

static const unsigned long

C[4]={0x01234567L,0x89ABCDEFL,0xFEDCBA98L,0x76543210L};

int r,i,j,u,g,rrf;

unsigned long r1,r2,rtf;

r=i=j=u=0; r1=r2=0;

if(mode==3)

{

A2("",4);

memcpy(&Fext[0][0],buff,256);

for(i=0;i<16;i++) for(j=0;j<4;j++) Rext[i][j]^=(buff[256+i]>>(2*j))&0x03;

return 0;

}

if(mode==4)

{

for(i=0;i<4;i++)

{

N[i]=0; R[i]=0; H[i%3]=0; Fv[i]=0;

for(j=0;j<16;j++) { Fext[j][i]=0; Rext[j][i]=0; }

}

return 1;

}

if(mode==5)

{

for(i=0;i<256+16;i++) buff[i]=0;

memcpy(buff,&Fext[0][0],256);

for(i=0;i<16;i++) for(j=0;j<4;j++) buff[256+i]|=(Rext[i][j]<<(2*j));

return 1;

}

memcpy(&N[0],buff,16); memcpy(&Fv[0],buff,16);

if(mode==2)

{

for(i=0;i<4;i++) { N[i]+=C[i]; R[i]=i; }

for(i=0;i<16;i++) for(j=0;j<4;j++) Rext[i][j]^=(buff[i]>>(2*j))&0x03;

}

/***********************************************************************/

for(r=0;r<RR;r++)

{

for(j=0;j<4;j++) R[j]=Rext[(mode)?r:(RR-1-r)][j];

rrf=4*(R[1]+R[3])+R[0]+R[2];

if(mode==2) for(i=0;i<4;i++) for(j=i+1;j<4;j++)

if(Fv[R[j]]<Fv[R[i]]) { u=R[j]; R[j]=R[i]; R[i]=u; }

if(mode)

{

rtf=0;

for(i=0;i<4;i++)

{ r1=Fext[(mode)?r:(RR-1-r)][i]; N[i]+=r1; rtf+=r1; H[i]=N[i]; }

rtf%=128; g=(int)rtf/32; rtf=(rtf+RT)%32; for(i=3;i>=0;i--) N[i]=H[(i-g+4)%4];

r1=N[3]>>(32-rtf);

for(i=0;i<4;i++) { r2=N[i]>>(32-rtf); N[i]<<=rtf; N[i]|=r1; r1=r2; }

}

for(u=0;u<4;u++)

{

if(mode) i=u; else i=3-u;

if(mode) for(j=0;j<4;j++) N[j]=ROT32L(N[j],((rrf+RRT*R[j])%32));

for(j=0;j<3;j++) H[j]=N[P[i][j]];

switch(R[i])

{

case 0: Fv[0]=F(H[0],H[1],H[2]); break;

case 1: Fv[1]=G(H[0],H[1],H[2]); break;

case 2: Fv[2]=H(H[0],H[1],H[2]); break;

case 3: Fv[3]=I(H[0],H[1],H[2]); break;

}

if(mode==2) { for(j=0;j<4;j++) N[j]-=Fv[R[i]]; N[i]+=Fv[R[i]]; }

N[i]^=Fv[R[i]];

if(!mode) for(j=0;j<4;j++) N[j]=ROT32R(N[j],((rrf+R[j]*RRT)%32));

}

if(!mode)

{

rtf=0;

for(i=0;i<4;i++) { r1=Fext[(mode)?r:(RR-1-r)][i]; rtf+=r1; H[i]=N[i]; }

rtf%=128; g=(int)rtf/32; rtf=(rtf+RT)%32; for(i=0;i<4;i++) N[i]=H[(i+g)%4];

r1=N[0];

for(i=3;i>=0;i--) { r2=N[i]; N[i]>>=rtf; N[i]|=(r1<<(32-rtf)); r1=r2; }

for(i=0;i<4;i++) N[i]-=Fext[(mode)?r:(RR-1-r)][i];

}

if(mode==2)

{

for(i=0;i<4;i++) { Rext[r][i]=R[i]; Fext[r][i]=N[i]; }

for(i=0;i<16;i++) for(j=0;j<4;j++)

{ u=(char)(((N[i/4]>>(8*(i%4)))>>(2*j))&0x03); Rext[i][j]^=u; }

}

}

/**********************************************************************/

if(mode!=2) memcpy(buff,&N[0],16);

if(mode==2) for(i=0;i<16;i++) A2((void *)&Fext[i][0],A2_ENCRYPT);

return 0;

}

10. About the author and future information

All questions about this document you can post to me on kbajalc@eon.pmf.ukim.edu.mk. More information about me, my researches and links to cryptography resources can be found on my Home Page http://eon.pmf.ukim.edu.mk/~kbajalc here is also a link to A2 page where all available information is presented.This document and information in it and copyright for them are property and of Kostadin Bajalcaliev. This document is freely available to everybody, Everybody have right to distribute it use information presented in it free of charge since this copyright notice is retained.

© Kostadin Bajalcaliev, 1998

This document is created on: May 5, 1998

A2 algorithm design is finished on May 4, 1998