More mathematical background for asymmetric cryptography

From CryptoWiki
Revision as of 06:54, 27 November 2013 by 13-03-DushaIF (Talk | contribs)

Jump to: navigation, search

Asymmetric cryptography (cryptographic public key systems ) 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 one (private, called also secret) key is used to decrypt messages and to create digital signatures. Private and public keys of the recipient are connected 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.

Contents

Asymmetric cryptography main problems. Solution methods for their

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 this 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 "share" 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 [one-way function with a secret | one-way function] Fk: X → Y with a secret k, publishes an algorithm for computing the values ​​of the function Fk, and keeps k in secret. Any user A who wants to send a secret message x ∈ X to user B, computes y = Fk(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 Fk, since, if it were not so, it would be possible to calculate k by knowing Fk and effectively find the invent function to Fk, 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 the use of asymmetric cryptography systems

The benefits of asymmetric ciphers 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 comparisom 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 is 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 : Asim2.png

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

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: Asim3.png

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.

Asim4.png

Euler function. Congruence in the ring of integers

Euler function

Euler function Asim5.png 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 Asim6.png 0 , then it is said that a is comparable to the number b modulo m ( is denoted by Asim7.png ), 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

3 ) Asim8.png

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:

Asim9.JPG

Euler's theorem

 Let m be a positive integer. Then Asim10.png should be Asim11.png

Fermat's theorem

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

Linear congruence solving

Linear congruence has the form Asim13.png. Transporting the free term in the right-hand side of the comparison and changing notation of the coefficients, we obtain Asim14.png (№ 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 Asim14.png 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 = a1d, b = b1d, m = m1d. Then cdividing (№ 2) by d, we obtain the congruence Asim15.png, which is equivalent to the comparison (№ 2). Since (a1, m1) = 1, the latter comparison, according to to the previous theorem, has a unique solution - Asim16.png, i.e. Asim17.png. Consider the sequence of classes

Asim18.png    

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.

Congruences

Definition

The number a is called a quadratic residue modulo p if the congruence x2 Con.png 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 Asim19.png and belonging to a quadratic non-residue modulo p is denoted as Asim20.png.

Theorem. Euler's criterion

If (a, p) = 1 , then the congruence x2 Con.pnga(mod p) has 2 solutions or none depending on the value of the number Asim21.png.

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

Proof

If we involute a to the power (p-1), then acording to Fermat's theorem Asim22.png => Asim23.png. Since the product Asim24.png 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.

Asim25.png, hence a Con.png0(mod p). Therefore, there is only one of the congruentions. But every quadratic residue satisfies a comparison x2 Con.png a(mod p) for some x and, therefore, also satisfy the congruention Asim22.png, 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 Asim21.png Con.png -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   Legendre symbol is defined as follows:

Asim26.png

According to Euler's criterion, Asim27.png.

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 x2 Con.png a (mod p).

Legendre symbol's properties

Asim28.JPG


______________________

Indexes.

______________________


Primitive roots

Definition (Vinogradov)   Index, to which a belongs modulo m is the smallest j, such that aj Con.png 1(mod m).

Definition (Buchstab)   Index of a modulo m is the smallest j, such that aj Con.png 1(mod m).

Definition (Ayerlend)   A number a has the order of j modulo m, if j is the smallest number such that aj Con.png 1(mod m).

Denoted by Asim29.png.

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. Asim30.png

Claim 1

Asim31.png

Proof.

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

Proved.

Claim 2

Let us consider the sequence {Asim35.png}, where Asim36.png.

Then Asim37.png, with Asim38.png.

Proof.

Let Asim39.png. 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 Asim40.png, which contradicts the initial conditions.

Proved.

Claim 3

If Asim36.png, then Asim41.png if and only then j is comparable to j1 modulo Delta.png. Special case is Asim42.png.

Proof.

Let us prove the necessity.

Asim43.PNG, where Asim44.png Asim45.png. Given that Asim46.png, we obtain Asim47.png, i.e. Asim48.png.

Let us prove the sufficiency.

Asim49.png Asim50.png

Proved.

Conclusion

Asim51.png

Proof

Asim52.png

Proved.

Gauss theorem

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

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 gj = a(mod p), 0 <= j <= p-2 .

Definition.

 Any j, such that a = gj(mod p), 0 <= j <= p-2, is called
 an index of a modulo p. It is denoted such ind a or Asim57.png to indicate
 index is modulo p. In other words, comparison Asim56.pngis fullfilled.
 Note that Asim58.png is satisfied if and only if j = j1 (mod(p-1)). This follows from assertion (№ 3).

Index properties :

Asim59.png

Indexes application for comparisons solution.

Let a comparison Asim60.png. When taking the index of this expression, we obtain Asim61.png, and after the transfer of asquanted to the right side we obtain a comparison Asim62.png, 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 : Asim63.png. 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 Asim64.png. Then we can identify the following two problems :

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

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

Additive groups notations change with the change of designation operation : Asim67.png => Asim66.png

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 Asim68.png.

The complexity of the method : Asim69.png.

Description of the method .

Step 1.

Asim70.png, then build a table : Asim71.png.

Step 2.

Asim72.png find Asim73.png using tables, built in step 1.

Let Asim74.png, Asim75.png.

Asim76.png

Asim77.png Asim78.png

In this case, the congruence is fullfilled:

Asim79.png

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

Step 3 .

Asim81.png

Asim82.png

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 is 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 Asim83.png, where f(x, y) = 0 ia a nonzero polynomial .

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

 Elliptic curve is a flat cubic curve, which is given by : Asim85.png

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

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 Asim88.png.

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 Asim92.png and Asim93.png.

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 Q1(x1, y1) and Q2(x2, y2) of the elliptic curve E several cases are considered.

For the points Q1 and Q2, the coordinates of which satisfy the condition: x1 not equal to x2,as their sum the point Q3(x3, y3) is, the coordinates of which are determined by comparing :

Asim94.png

where

Asim95.png

If the equalities x1 = x2 and y1 = y2 are fullfilled Asim96.png, then the coordinates are defined as follows:

Asim97.png

where

Asim98.png

If the conditions x1 = x2 and y1 = y2 are fullfilled Asim99.png, then the sum of points is denoted as a zero without specifying its exact coordinates.

Number theory application

RSA cryptosystem

Claim

If e,d:Asim89.png, then relation is fullfilled:

Asim90.png

Proof

Asim91.png

Glossary

Bibliography

  • Фомичев В. М. Методы дискретной математики и криптологии. – М.: Диалог-МИФИ, 2010. – 424 с.
  • Виноградов И.М. Основы теории чисел, 180 с.
  • Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография. НПО "Профессионал" – 2004, 480 с.
  • Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. – М.: Гелиос АРВ, 2001.
  • Wenbo Mao, Modern Cryptography: Theory and Practice - Издательский дом "Вильямс", 2005, 768 p.
  • Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Алгоритмические основы эллиптической криптографии. — Москва: МЭИ, 2000, 100 с.

Вернуться к оглавлению

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