ProtoQuant.com

Abstract. A commutative subgroup of the group of 2×2 real matrices is used for encryption and decryption purposes. The process is entirely analogous to that using Chebyshev polynomials, only a lot faster, more economical and apparently safer to attacks.

 

I. Introduction

There are two fundamental actions of the 2×2 matrices usually taken into consideration: the action in 1D domain and the action in the 2D domain, no matter if real or complex. The first one of these actions is the so-called projective or homographic action. If the variable of the 1D domain is represented by z (being real or complex) and the matrix is represented by the 2×2 table

(1)

where the entries can, again, be real or complex, then the homographic action gives the following correspondence of the z-domain into itself:

(2)

On the other hand there is an action in the 2D domain (real or complex) of the matrix (1) – the linear action. If the domain is represented by the pair of numbers (x, y) then the linear action gives the following correspondence of the domain into itself:

(3)

The main difference between the two actions of the 2×2 matrices stays in the number of entries of the matrix necessary to completely characterize the action. In the case of homographic action three of the entries are sufficient to characterize the action, while in the case of linear action we need all four entries to completely characterize the action.

As known these two actions, or better the correspondences they induce by equations (2) and (3), are closely related to algebraic properties of the 2×2 matrices. Especially the composition of correspondences is related to the matrix multiplication.

We take into consideration just the homographic action (2) for z real. It gives a 1-to-1 correspondence except for the point

(4)

where the denominator is zero. Formally the correspondence has a group property due to the group property of multiplication of matrices, because it can be easily verified that

(5)

where ‘o’ represents the composition of functions and ‘•’ represents the matrix multiplication. In other words, the composition of two functions (2) corresponds to their matrix multiplication.

As in general the matrices do not commute in multiplication (they do not form an Abelian group) the composition of functions they define through homographic action has the same property:

(6)

This means that in general the group of matrices cannot be used for encryption without special precaution.

However there are rich classes of commutative matrices (Abelian subgroups) that can be easily made to fill the need for encryption exactly like, for instance, Chebyshev polynomials only a lot easier and, we think, by a faster algorithm.

 

II. Describing an Abelian Subgroup

Choose two numbers (a, b) and build the 2×2 matrix

(7)

This matrix has the important property

(8)

Thus, if we construct the 2-parameter family of matrices

(9)

where m and n are numbers, we have a double infinity of matrices which commute among them – an Abelian group – because we have:

(10)

One can see that the coefficients of matrices e and h are symmetric bilinear forms in m and n.

 

III. The Cryptosystem Based on 2×2 Matrices

Thus, a public key encryption can be made based on the same principles as those related to Chebyshev polynomials. There are, of course, problems of detail like, for instance, the choice of m, n or a, b, but these can be fixed on a case by case basis. In principle, the following scenario, described in terms of universally known characters, Alice and Bob, seems to work very well:

In order to receive the messages, Alice has to do the following:

1. Select a real number x, and four other real numbers: a, b, m_p, n_p

2. Calculate A_mpnp(x) according to equation (2), using equation (9)

3. Set the public key [a, b, x, A_mpnp(x)] in a public place and hold the pair (m_p, n_p) as private key

In order to encrypt and communicate a message, Bob has to do the following:

1. Represent the message as a real number M

2. Obtain the public key [a, b, x, A_mpnp(x)]

3. Select a pair of real numbers (m_b, n_b) and calculate A_mbnb(x)

4. Calculate A_mbnb[A_mpnp(x)] and scramble the message into

X = M×A_mbnb[A_mpnp(x)]

5. Send the cipher message as the pair C ≡ [A_mbnb(x), X]

In order to decrypt the cipher Alice has to do the following:

1. Obtain the cipher C

2. Calculate U ≡ A_mpnp[A_mbnb(x)]

3. Unscramble the cipher by M ≡ X/A_mpnp[A_mbnb(x)]