# More mathematical background for asymmetric cryptography

*Asymmetric cryptography* (*cryptographic public key system* ) is a cryptographic scheme, which functions are to enable the encryption and/or digital signing, where one key is used to encrypt a message or verify a digital signature, and the other key (private, called also secret) is used to decrypt messages and to create digital signatures. Private and public keys of the recipient are linked by one-way function so that the calculation of the public key of the secret is possible in polynomial time and the calculation of the private key with the known publuc key is a computation complex problem. This section of cryptography typically includes also key exchange algorithms as they are based on the same mathematical principles.

## Asymmetric cryptography main problems. Solution methods.

### Ideas and principles of an asymmetric cryptography

Appliance of different symmetric cryptography algorithms causes problems which are not possible to be resolved algorithmically, but using these algorithms with such deficiencies is unacceptable. The enumeration of problems associated with using symmetric ciphers is going forward.

** The key distribution problem**

Before using a symmetric encryption algorithm parties need to share a secret key that can only distributed through a secure data channel. In some cases such exchange is not possible, for example when creating a secure channel between the users is impossible .

** The trust problem**

Even if the secret keys are distributed in advance, there is another problem: it is impossible to differentiate the two correspondents having the same keys. Upon condition of absence of trust between the parties scheme becomes useless. It may also be a problem if the correspondent "shares" the secret with someone, without informing you.

** The complexity of key management in a large network. **
The problem is related to a fact that the number of pairs of keys needed to be generated, transmitted, stored and destroyed in the network increases in quadratic dependence. For a network of 10 subscribers 45 keys are needed, for 100 - 4950, for 1000 - 499500 , etc.

** Ideas of an asymmetric cryptography **

The idea is to replace the private key by pair of mathematically related keys, one public key, and one private, accessible only to those who has generated the pair.

Advantages:

There is no need for advanced distribution of keys

The secrecy of the key is provided only by the one side

A problem of trust to the other side does not rise

### The principles of construction

Some party T wants to receive encrypted messages. He selects trapdoor one-way function F_{k}: X → Y with a secret k, publishes an algorithm for computing the values of the function F_{k}, and keeps k in secret. Any user A who wants to send a secret message x ∈ X to user B, computes y = F_{k}(x) and sends y by an insecure channel. User B is the only who calcute the value x by knowing y (basing on the definition of one-way function with a secret), since only the T knows the secret k. In addition, it is computationally difficult to recover k knowing the public key F_{k}, since, if it were not so, it would be possible to calculate k by knowing Fk and effectively find the invent function to F_{k}, that is impossible by the definition.

The one-way function with a secret is based on a mathematical problem for which there should not be an algorithm that allows iterating over all the solutions of the problem P in polynomial time relative to the size of the problem. It can be also said this way: there should not be a well-known polynomial-time algorithm that solves this problem - because for neither task has been proved that the suitable algorithm does not exist in principle.

Such mathematical problems based on public-key cryptographic algorithms can be noticed:

1. factorization problem;

2. discrete logarithm problem;

3. knapsack problem;

4. problem solving systems of nonlinear equations over a finite field;

5. the problem of computing short vectors of integer arrays;

6. the problem of decoding a linear code that has no apparent algebraic, combinatorial or other structure.

The majority of the most commonly used algorithms are based on the first two issues. We list the best-known system of asymmetric cryptography: RSA, Merkle, DSA, ElGamal, ECC, Schnorr scheme, GOST 34.10, ECDSA, ECDH, NTRU. The algorithms are based primarily on the results of the number theory.

### The advantages and disadvantages of using asymmetric cryptography systems

The benefits of asymmetric cipher before symmetrical:

- Do not have to distribute the secret key with a reliable channel.

- The secret encryption key is known only to the one party (in symmetric cryptography such key is known to both parties and should be kept secret by both of them).

- A pair secret key and public key, can be the same for a long time (for symmetric encryption key must be updated after each transfer).

- The number of keys in an asymmetric cryptosystem is much less than the symmetric in large networks.

Disadvantages asymmetric encryption algorithm in comparison with symmetric ones:

- Algorithm is more difficult to be modified.

- Although the messages are securely encrypted, the recipient and the sender by the fact of sending encrypted messages "give themselves away".

- The keys are longer.

- Encryption and decryption using a pair of keys are much slower than the encryption-decryption process of the same text with a symmetric cipher.

- More computational resources are required, so asymmetric cryptosystems are used in conjunction with other algorithms in practice.

## Mathematical background for asymmetric cryptography

This section covers all aspects of the mathematical theory on which asymmetric cryptographic algorithms are based.

### Number theory foundation

#### The divisibility theory

** Basic concept **

Number theory attends to the study of properties of integers.

For integers a and b, it is said that a divides b, a is a divisor of b, or b is a multiple of a, and this is written as a|b, if there exists an integer q such that aq=b.

** The greatest common divisor **

Any integer that divides both integers a, b, c, ... , l, is called their common divisor. The largest of the common divisors is called the greatest common divisor and is denoted by (a, b, ..., l). If (a, b, ..., l) = 1 , the numbers a, b, ... , l are said to be relatively primary. If each of these numbers is prime to every other, then they are said to be relatively primary in pairs.

** Modulo operation theorem **

For any two integers a, b such q, r exist, where r> b, so that a = qb + r. In terms of quantifiers that statement looks like this :

Common divisor - any integer that divides both integers a, b, ..., t. The greatest common divisor (GCD) - the largest of the common factors. It is denoted as GCD(a, b, ..., t) or simply (a, b, ..., t).

** Theorem **

For any r integer numbers there is the greatest common divisor.

#### Euclid's algorithm (Euclid)

For finding the greatest common divisor and its most significant properties the Euclidean algorithm is applied. It consists of the following [Vinogradov]. Let a and b be positive integers. According to the Modulus operation theorem we find a series of equations:

This series of equalities ends when rn +1 = 0. Last is inevitable, since the series b, r2, r3 is a decreasing number of integers that can not contain more than b positive.

#### Prime numbers. The fundamental theorem of algebra

Definition

The number p>1 is called prime if it has no positive divisors other than 1 and p.

**Fundamental theorem of algebra**

Any positive integer m can be represented as a product of powers of prime numbers.

#### Euler function (Leonhard Euler). Congruence in the ring of integers

**Euler function**

Euler function is defined for all positive integers a and represents the quantity of such numbers 0,1, ..., a- 1 which are relatively prime to a.

** Congruence of the ring of integers **

Definition.

Let m, a, b - integers , m 0 , then it is said that a is comparable to the number b modulo m ( is denoted by ), if

1 ) m divides the difference between a and b: m | (a-b)

2 ) a and b are divided into m with the equal modulo: a = mq ¬ ¬ a + r, b = mq ¬ ¬ b + r

Comparability - a binary relation , and an [ [ equivalence relation ]] .

** Primitive residue classes **

Since the comparison is an equivalence relation, all the numbers are divided into classes called the residue classes. All the numbers giving the same remainder relatively module m are comparable, and therefore included into the general class of residues modulo m. Taking from each such class one sample (i.e. making transversal [ Discrete Mathematics ] ), we obtain a reduced residue system modulo m. Usually reduced residue system is constructed by the least nonnegative residue : 0,1, ..., m- 1.

** Reduced residue system modulo m**
Since the properties of the reduced system of residues modulo m (numbers 0,1, ..., m- 1) the number of ones, relatively prime to m is,
number of properties of the reduced system as well as the number of classes that contain these numbers relatively prime to the modulus is. .

Example . Reduced residue system modulo 42 is 1, 5 , 11, 13, 17 , 19 , 23, 25, 29 , 31, 37, 41.

Euler's function properties:

** Euler's theorem **

Let m be a positive integer. Then should be

** Fermat's theorem (Pierre de Fermat) **

If the p is a prime , (r, p) = 1 , p does not divide r, then .

#### Linear congruence solving

Linear congruence has the form . Transporting the free term in the right-hand side of the comparison and changing notation of the coefficients, we obtain (№ 2)

While solving such congruences two cases are considered: (a, m) = 1 and (a, m) = d> 1.

If (a, m) = 1 , the congruence (№ 2) has a unique solution .

Proof. The congruence can not have more than m solutions in accordance with the amount of numbers in the reduced residue system. If x runs through a reduced residue system, then the linear form ax-b also runs through a reduced residue system. At that the linear form will once take the value that is congruent to zero, since zero is one of the deductions reduced residue system .

If (a, m) = d> 1, and the number b is not divisible by d, then the congruence of has no solutions. The proof is by contradiction with the use of the properties of divisibility.

If (a, m) = d> 1 , and the number b is divisible by d, then the comparison (№ 2) has d solutions.

Proof.

Let a = a_{1}d, b = b_{1}d, m = m_{1}d. Then cdividing (№ 2) by d, we obtain the congruence , which is equivalent to the comparison (№ 2). Since (a_{1}, m_{1}) = 1, the latter comparison, according to to the previous theorem, has a unique solution - , i.e. . Consider the sequence of classes

It is easily seen that these classes are solutions of the congruence (№ 2), substituting them into the congruence, besides they are different (this is proved by contradiction and using the properties of comparability), and there are no other solutions.

#### Congruencies

Definition

The number a is called a quadratic residue modulo p if the congruence x^{2}a(mod p), (2, p) = 1 has a solution. Otherwise, the number is called a quadratic non-residue mod p.

When this number belongs to a quadratic residue modulo p it is denoted as and belonging to a quadratic non-residue modulo p is denoted as .

** Theorem. Euler's criterion**

If (a, p) = 1 , then the congruence x^{2} a(mod p) has 2 solutions or none depending on the value of the number .

If 1(mod p), then the original congruention has two solutions, and none if -1(mod p).

Proof

If we involute a to the power (p-1), then acording to Fermat's theorem => . Since the product is congruent to zero modulo p, then one of the factors is divisible by p.

We can show that both of them can not simultaneously be divisible by p.

, hence a 0(mod p). Therefore, there is only one of the congruentions. But every quadratic residue satisfies a comparison x^{2} a(mod p) for some x and, therefore, also satisfy the congruention , which can be obtained by termwise involution a to power ^{(p-1)/2}, it can not have more than (p-1)/2 solutions. Therefore the quadratic non-residues satisfy congruence -1 (mod p).

Proved

** Euler's theorem **

The product of two quadratic residues or two non-residues is quadratic residues, the product of a quadratic residues and a non-residues is non-residue .

** The Legendre symbol (Adrien-Marie Legendre)**

Legendre symbol is defined as follows:

According to Euler's criterion, .

Next the most important properties of the Legendre symbol are presented. This properties allow quickly calculating this character, and hence solvaion the problem of solving a comparison x^{2} a (mod p).

**Legendre symbol's properties**

#### Multiplicative order. Primitive roots

Definition (Vinogradov)
Index, to which a belongs modulo m is the smallest j, such that a^{j} 1(mod m).

Definition (Buchstab)
Index of a modulo m is the smallest j, such that a^{j} 1(mod m).

Definition (Ayerlend)
A number a has the order of j modulo m, if j is the smallest number such that a^{j} 1(mod m).

Definition

A primitive root modulo m is a number called a, which order is equal to the value of the Euler function of this module, i.e.

** Claim 1**

Proof.

Let . Then 1(mod m). Here is a contradiction. The case is considered the same way.

Proved.

**Claim 2 **

Let us consider the sequence {}, where .

Then , with .

Proof.

Let . Since (a, m) = 1, the ring of residues modulo m there is an element inverse to a, i.e. a^{(-1)}. Then a congruention can be multiplied on the right by a^{(-k)}.

Thus we obtain , which contradicts the initial conditions.

Proved.

** Claim 3 **

If , then if and only then j is comparable to j1 modulo . Special case is .

Proof.

Let us prove the necessity.

, where . Given that , we obtain , i.e. .

Let us prove the sufficiency.

Proved.

** Conclusion**

Proof

Proved.

** Gauss theorem **

Primitive roots exist only for m = 2,4,, the number of these roots is exactly . If a is a primitive root modulo m, then all primitives are of the form

#### Indices (discrete logarithms) and their properties

Let g be a primitive root modulo p. For any a such that (a, p) = 1 it is satisfied g^{j} = a(mod p), 0 <= j <= p-2 .

Definition.

Any j, such that a = g^{j}(mod p), 0 <= j <= p-2, is called an index of a modulo p. It is denoted such ind a or to indicate index is modulo p. In other words, comparison is fullfilled. Note that is satisfied if and only if j = j_{1}(mod(p-1)). This follows from assertion (№ 3).

Index properties :

Indexes application for comparisons solution.

Let a comparison . When taking the index of this expression, we obtain , and after the transfer of asquanted to the right side we obtain a comparison , which is a comparison of the first degree ind x. According to the rules above solutions of comparisons are:

1. (n, p-1) = 1, then the comparison has one solution

2. (n, p-1) = d> 1

a. d does not divide (ind a - ind b), then there are no solutions

b. d | (ind b - ind a)

We obtain a linear comparison to a simple module : . After finding ind x, we can bring it into the index table (or a table of discrete logarithms) and then use it to solve comparisons of higher degrees. We draw the reader's attention that, in contrast to the tables of logarithms in the field of integers in the residue ring of some modulo composes an index table for this module , which is very different from the corresponding tables for other modules.

#### Discrete logarithm problem

Let us formulate the discrete logarithm problem (DLP). Suppose we have a finite group G with multiplicative operator *. Denote a*a*a*...*a = b as . Then we can identify the following two problems :

1) Consider the . The point is to know whether there is such that

2) It is necessary to find such n, that , if it is know to exist.

Additive groups notations change with the change of designation operation : (n times) =>

** Discrete logarithm problem solution algorithms **.

Since this problem is one of the most important in cryptography and also has a variety of applications, at least in the number theory, there are many algorithms for solving this problem. Among them there are algorithms with exponential complexity (Shanks' algorithm , Pohlig-Hellman algorithm , Pollard's p-method), algorithms with subexponential complexity (Adelman algorithm , the algorithm COS) and also algorithms for solving the problem in an derived finite field (ElGamal algorithm, Coppersmith Algorithm). For example, let the Pohlig-Hellman algorithm be considered.

** Pohlig-Hellman method of the discrete logarithm discovering**

This method is effective if decomposition is known .

The complexity of the method : .

Description of the method .

Step 1.

Step 2.

find using tables, built in step 1.

Then find x_{0} from the table.

In this case, the congruence is fulfilled:

Then find x_{1}.

In general terms, this step can be represented as follows:

Step 3 .

Next, the resulting comparison is solved by means of rules for solving linear comparisons.

### Elliptic Curve Cryptography

#### Elliptic curves application

Asymmetric cryptography bases on the complexity of solving some mathematical problems. Early public-key cryptosystems such as the algorithm RSA are safe due to the fact that it is difficult to decompose a composite number into prime factors. When using algorithms on elliptic curves it is assumed that there are no subexponential algorithms for solving the discrete logarithm problem in groups of their points. the complexity of the problem is determined by the degree of the elliptic curve. It is assumed that achieving the same security level as RSA has requires groups of lower orders, which reduces the cost of storing and transmitting information. For example, at the RSA Conference 2005 National Security Agency announced the creation of "Suite B", in which exclusively elliptical cryptography algorithms are used, and to protect information classified up to "Top Secret" only 384-bit keys are used.

#### Definitions

A flat elliptic curve is the set of points , where f(x, y) = 0 ia a nonzero polynomial .

Cubic curve is a plane algebraic curve, where , for which the maximum value of i + j = 3 .

Elliptic curve is a flat cubic curve, which is given by :

If the characteristic of F is not equal to 2, then y can be replaced by . Then the equation 3 takes the form .

#### Hasse's Theorem

Hasse's theorem on elliptic curves, called also the boundary Hasse, gives an estimate of the number of points on an elliptic curve over a finite field. Restriction is given both above and below. Statement of the theorem : The number of points on an elliptic curve close to the number of elements of finite fields, namely |EC(Fq)|= q+1-t, where .

#### Elliptic curve superposition

Below the rules for adding points on an elliptic curve are presented, as it is defined in ISO 34.10.

Elliptic curve E is a set of numbers satisfying the identical equation and .

Pairs (x, y) which satisfy the identical equation (1) are identified as "points of elliptic curve E";

x and y are identified respectively as x- and y- coordinates of the point.

Elliptic curve point is denoted Q (x, y) or Q.

Two elliptic curve points are equal if equal their respective x and y coordinates .

On the set of all points of the elliptic curve E the superposition operation is denoted by "+" sign.

For any two points Q_{1}(x_{1}, y_{1}) and Q_{2}(x_{2}, y_{2}) of the elliptic curve E several cases are considered.

For the points Q_{1} and Q_{2}, the coordinates of which satisfy the condition: x_{1} not equal to x_{2},as their sum the point Q_{3}(x_{3}, y_{3}) is, the coordinates of which are determined by comparing :

where

If the equalities x_{1} = x_{2} and y_{1} = y_{2} are fulfilled , then the coordinates are defined as follows:

where

If the conditions x_{1} = x_{2} and y_{1} = y_{2} are fulfilled , then the sum of points is denoted as a zero without specifying its exact coordinates.

## Number theory application

#### RSA cryptosystem

**Claim**

If e,d:, then relation is fulfilled:

**Proof**

## Glossary

## Bibliography

Move to bibliography for this section.

*Душа И.Ф., Лагутина Е.А., 2013*