Lecture
Symmetric encryption has drawbacks that limit its applicability in a number of specific cases. In particular, it is often impossible to organize a secret channel for the exchange of encryption keys between the participants of the interaction. Another disadvantage of symmetric ciphers is the need to store a large number of keys: in order for the N participants to interact confidentially in pairs, there must be N * (N-1) / 2 keys in the system. These disadvantages can be eliminated using asymmetric encryption algorithms. For example, for an asymmetric system, it is sufficient to have 2 * N public / private key pairs so that a secret channel can be established between each pair of participants.
The main idea of asymmetric encryption is the existence of two keys at once for the exchange of information - open, known to anyone, and private, which is known only to the recipient of information. It is obvious that the public and private keys are generated simultaneously and there is a certain mathematical connection between them. The main task of an asymmetric algorithm designer is that using a known public key it would be impossible (very time-consuming) to obtain a secret encryption key. To this end, asymmetric algorithms are based on computationally difficult problems of factorization, discrete logarithmization, projection of points on an elliptic curve, etc. What unites all these tasks is that they use the operation of obtaining the remainder from integer division.
For any positive integer n and any a when dividing a by n, we get some integer quotient q and a remainder r satisfying the relation
|
a = qn + r , 0 ≤ r < n ; q = int ( a / n ), |
where int ( x ) denotes the largest integer not exceeding x .
If a is integer and n is positive, then a mod n is defined as the remainder of dividing a by n . Thus, for any integer a you can write
|
a = int ( a / n ) * n + ( a mod n ). |
They say that two integers a and b are comparable modulo n if ( a mod n ) = ( b mod n ). This is written in the form: a º b mod n .
Comparison operations modulo have the following properties:
|
1. a º b mod n , n | ( a - b ) ( n | x means that n divides x totally). 2. From ( a mod n ) = ( b mod n ) it follows a º b mod n . 3. From a º b mod n it follows b º a mod n . 4. From a º b mod n and b º c mod n it follows a º c mod n . |
Arithmetic operations in residue classes have the following properties:
|
1. [( a mod n ) + ( b mod n )] mod n = ( a + b ) mod n . 2. [( a mod n ) - ( b mod n )] mod n = ( a - b ) mod n . 3. [( a mod n ) * ( b mod n )] mod n = ( a * b ) mod n . |
Let Z n denote the set of all non-negative integers that are less than n:
|
Z n = {0, 1, 2, ..., (n - 1)}. |
This set is also called the set of residues (residues) modulo n . For arithmetic operations modulo n in this set the following properties are true:
|
Property |
Expression |
|
Commutative laws |
( w + x ) mod n = ( x + w ) mod n , |
|
Associative laws |
[( w + x ) + y ] mod n = [ w + ( x + y )] mod n , |
|
Distribution law |
[( w + x ) * y ] mod n = [( w * y ) + ( x * y )] mod n |
|
Identities |
(0 + w ) mod n = w mod n , (1 * w ) mod n = w mod n |
|
Additive reverse (- w ) |
For any w є Z n, there exists z such that w + z ≡ 0 mod n |
There is one feature of arithmetic in residue classes, which makes it different from ordinary arithmetic. We note first that, as in ordinary arithmetic, the following property holds
|
if ( a + b ) º ( a + c ) mod n , then b º c mod n . |
This property is consistent with the existence of an additive inverse. Adding to both sides of this equality the additive inverse of the element a , we get:
|
((- a ) + a + b ) º ((- a ) + a + c ) mod n , b º c mod n . |
However, the following statement:
if ( a * b ) º ( a * c ) mod n , then b º c mod n
|
it is executed only under the condition that a and n are coprime (denoted below by ( a , n ) = 1) |
If p is simple, then all elements of Z p will be coprime with p . This gives us the opportunity to add another property to those that have been given above:
|
Property |
Expression |
|
Multiplicative inverse ( w -1 ) |
For any w є Z p, there exists z such that w * z ≡ 1 mod p |
To find the multiplicative inverse, you can use the advanced Euclidean algorithm, which allows you to find in integers the solution of the equation ax + by = 1 for given a and b . Obviously, if a solution exists, then x will be a quantity multiplicatively inverse of a modulo b .
Euclidean algorithm
1. Determine the matrix E :
2. Calculate the r- remainder of dividing the number a by b :
a = bq + r, 0 £ r < b
3. If r = 0, then the first column of the matrix E is a solution to the equation.
4. If r r 0, replace the matrix E :
5. Swap the columns of the matrix E.
6. Replace a pair of numbers a , b on b , r and go to step 2
Comments
To leave a comment
Cryptography and cryptanalysis, Steganography and Stegoanalysis
Terms: Cryptography and cryptanalysis, Steganography and Stegoanalysis