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.
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 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 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
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
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).
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
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
Congruence of the ring of integers
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:
Fermat's theorem (Pierre de Fermat)
Linear congruence solving
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 divisible by d, then the comparison (№ 2) has d solutions.
Let a = a1d, b = b1d, m = m1d. Then cdividing (№ 2) by d, we obtain the congruence , which is equivalent to the comparison (№ 2). Since (a1, m1) = 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.
The number a is called a quadratic residue modulo p if the congruence x2 a(mod p), (2, p) = 1 has a solution. Otherwise, the number is called a quadratic non-residue mod p.
Theorem. Euler's criterion
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 x2 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).
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:
Legendre symbol's properties
Multiplicative order. Primitive roots
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.
Let us prove the necessity.
Let us prove the sufficiency.
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 .
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 to indicate index is modulo p. In other words, comparison is fullfilled. Note that is satisfied if and only if j = j1 (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
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
Description of the method .
Then find x0 from the table.
In this case, the congruence is fulfilled:
Then find x1.
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.
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.
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 :
Number theory application
Move to bibliography for this section.
Душа И.Ф., Лагутина Е.А., 2013