# Asymmetric encryption schemes

## Security challenge

Public-key encryption scheme (asymmetric cryptography) - a cryptographic scheme that allows to encrypt the plaintext by any person using the recipient’s public key, and allows to restore the original text only person who has the corresponding personal private key.

In 1976 an asymmetric-key cryptosystem was published by Whitfield Diffie and Martin Hellman who, influenced by Ralph Merkle's work on public-key distribution, disclosed a method of public-key agreement. This method of key exchange, which uses exponentiation in a finite field, came to be known as Diffie–Hellman key exchange. This was the first published practical method for establishing a shared secret-key over an authenticated (but not private) communications channel without using a prior shared secret. Merkle's "public-key-agreement technique" became known as Merkle's Puzzles, and was invented in 1974 and published in 1978. The public key algorithms receive this title because the encryption key is not required to keep secret. Anyone can use it to encrypt message, but only the holder of the corresponding private key will be able to read this encrypted message.

## Theoretical issues

Public-key encryption algorithms based on using one-way functions. These functions have the property that for a given value of the argument x is relatively easy to calculate the value of the function y = f (x), however, is to find x, which corresponds to the predetermined value y, is extremely difficult, precisely due to the large amount of computation. For example, a power function is one-way function:

у = f(x) = Ax mod(N),

where x and N - very large numbers, and A - of random number of the interval [2, N - 2].

For a given value of x is relatively easy to calculate the value of y, but calculating of value x = f -1(y) will require a very large amount of computation.

But if you use one-way function, it will be impossible to decrypt the message. Therefore, one-way functions with a trap (trapdoor function) are used in public-key cryptography. A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor".

### General public-key encryption scheme

Assume:

K - key space;
m – the plaintext;
с – ciphertext;
e – encryption key;
d – decryption key;
Ee — encryption function for an arbitrary key e ϵ K;
Dd – decryption function for an arbitrary key d ϵ K.

Then the encryption and decryption will occur by the following formulas, respectively:

E e (m) = c,
D d (c) = m.

Ee is a one-way function, and d - a trapdoor. By this means, if you know the e, it is impossible to determine the appropriate decryption key d. The Figure 1 shows the transmission of information from person A to person B. The sender А encrypts the message with the public key e and sends the resulting ciphertext с to the recipient В using the insecure channel. The recipient В, in turn, decrypts the ciphertext с using a secret key d, and receives the original text m.

Figure 1: General public-key encryption scheme

In order to ensure the protection of information to the public-key cryptosystems are presented two important and obvious requirements.

1. Transformation of the original text should be irreversible and conditionally exclude its recovery on the basis of the public key.
2. Determination of the private key based on the public key should also be impossible at the current level of technology.

## Public-key cryptosystems

The most well-known public-key cryptosystems are:

RSA. Used factoring problem (computation of prime factors) of a large integer. The algorithm is based on the multiplication of two prime numbers larger capacity.

ElGamal encryption system. Based on the discrete logarithm problem in a finite field.

Knapsack Merkle-Hellman’s cryptosystem. Based on the question of packing knapsack.

### RSA cryptosystem

In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, thefactoring problem. RSA stands for Ron Rivest, Adi Shamir and Leonard Adleman, who first publicly described the algorithm in 1977.

The first stage of the RSA algorithm is the creating key pair by the recipient of cryptograms: public and private keys. This step consists of the following operations:

1) Choose two sufficiently large prime numbers p and q, calculate their product n = p·q, called modules;
2) Choose an integer e, such that e < φ (n) and the GCD (e, φ (n)) = 1 (greatest common denominator), where φ (n) = (p – 1)·(q – 1)and is called the Euler function;
3) Calculate the number d, satisfying the condition e·d = 1 (mod φ (n)).

Pair (e, n) is a public key, which is published in the public certified reference book and available to all subscribers of the RSA cryptosystem.

Pair (d, n) is called the private key, which is kept in secret.

Encrypting the open message M is performed by the formula:

M e mod(n) = C,

where C - the resulting ciphertext.

Decrypting the ciphertext C is performed by the formula:

C d mod(n) = M
.

Reliability of RSA cryptosystem is based on the not easily soluble - almost unresolvable - problem decomposition n into cofactors, because of at this time effective ways of finding the cofactors does not exist.

The Figure 2 shows the transmission of information from person В to person А.

Figure 2:RSA scheme

The sender В creates a ciphertext C, raising a message M to the power e and taking this value modulo n: C = M e mod(n), where e and n – a public key of person A.

Then the person В sends the encrypted text C to person A. To decrypt the received text, A raising the received ciphertext C to the power d and takes that value modulo n: M = C d (mod n), where d and n - a private key of person A. The value of d is calculated using the Extended Euclidean algorithm.

Currently, RSA Laboratories recommends keys of 1024 bits for routine tasks, and for important tasks recommends keys of 2048 bits.

### El Gamal encryption system

El Gamal encryption system is based on the difficulty of calculating discrete logarithms in a finite field. It was described by Taher Elgamal in 1985.

The first stage of the algorithm El Gamal is key generation. This stage includes the following steps:

1) Generate a random prime number p, which length is n bits.
2) Choose an arbitrary integer a, which is a primitive root modulo p.
3) Choose a random number x from the interval (1, p), which co-primes to p-1.
4) Calculate y = a x (mod p).

The public key is a triple (a, p ,y), the private key - number x.

The second stage of the algorithm includes encryption.

The message M is encrypted in the following manner:

1) Select a random secret number k, which co-primes to p - 1.
2) Calculate
γ = ak(mod p),
δ = M · yk(mod p),

where M - the original message.

A pair of numbers (γ,δ) is the ciphertext.

It is easy to notice that the length of ciphertext in ElGamal encryption twice as long than the original message M.

The final stage of El Gamal encryption is decryption.

If we know the private key x and that M = (δ · γ p-1-x)(mod p) , the original message M can be computed from the ciphertext (γ,δ) according to the formula:

M = γ -x · δ (mod p)

The Figure 3 shows a scheme of the El Gamal encryption algorithm.

Figure 3: El Gamal Scheme

In view of the fact that the number k is arbitrary, then this scheme is called probabilistic encryption scheme. The probabilistic nature of encryption is an advantage for the ElGamal encryption scheme, because probabilistic encryption schemes have been greater stability in comparison to schemes with certain encryption process.

The disadvantage of scheme El Gamal encryption is doubling the length of ciphertext in comparison with the initial text. For probabilistic encryption scheme the message M and the key don’t uniquely determine the ciphertext. It is necessary to use different values of the random variable k for encrypting different messages M and M '. If you use the same k, then for the following ciphertexts (γ,δ) and (γ',δ') there is a relation δ · (δ') -1 = M · (M') -1(mod p). From this expression we can easily calculate M, if we know M '.

### Knapsack Merkle-Hellman’s cryptosystem

In 1978 Merkle and Hellman proposed to use the question of packing knapsack (rucksack) for asymmetric encryption. It is stated as follows: given a set of items with different weights. The question: is it possible to put some of these items in the knapsack so that its weight became equal to a certain value? More formally, the problem is formulated as follows: given a set of values M1, M2, ..., Мn, and the total value of S ; it is required to calculate values bi, such that

S = b1М1 + b2М2 + ... + bnМn,

where n - the number of items;

bi - binary multiplier. The value bi = 1 means that the object i put in a backpack, bi = 0 - do not put.

For example, the weight of the items has the values 1, 5, 6, 11, 14, 20, 32 and 43. It is possible to pack the backpack so that the weight of rucksack was equal to 22, using weight items 5, 6 and 11. It is impossible to pack the backpack so the weight of the rucksack became equal to 24.

The algorithm proposed by Merkle and Hellman, is the idea of encrypting messages based on solving series of stacking backpack. Items from the heap are selected using the plaintext block length (in bits) is equal to the number of items in the heap. At the same plaintext bits correspond to the values b, a text is received by total weight. Example cryptogram obtained by the problem of packing a knapsack, is shown in the following table.

The Merkle-Hellman system is based on the question of packing knapsack. Items from the heap are selected using the block of plaintext, which length (in bits) is equal to the number of items in the heap. At the same time bits of plaintext correspond to the values b, and the text is the received total weight. Example cryptogram, obtained by the question of packing a knapsack, is shown on the Figure 4.

Figure 4: Example encrypting based on the problem of packing a knapsack

The essence of this approach for encryption is that in fact there are two different tasks of packing a backpack - one of them is easily solved and is characterized by a linear increase in the complexity, and the other, as commonly cited, is not.

Easy packing knapsack can be converted to difficult. If so, you can use the public key as difficult packing knapsack that is easy to use for encryption, but it is impossible to decrypt. And as a private key you can apply an easy packing knapsack, which provides an easy way to decrypt the message.

As the private key (Easy packing knapsack) is used superincreasing sequence.

Solution for superincreasing knapsack is easy to find. As the current selected full weight, which we want to obtain, and compared with the weight of the heaviest item in the knapsack. If the current weight is less than the weight of the item, it is not put in a knapsack, otherwise it is placed in a knapsack. Reduce the current weight on the weight of the putting item and move on to the next item by weight in the sequence. Steps are repeated as long as the process is completed. If current weight is reduced to zero, then the solution is found. Otherwise, is not.

The public key is not superincreasing (normal) sequence. It is formed on the basis of the private key and, as is commonly believed, cannot easily solve the question of packing a knapsack. In order to obtain it all of the private key value multiplied by the number n modulo m. The modulus m must be greater than the sum of all the numbers in the sequence. The factor n has to be relatively prime to the modulus m.

For encrypting, at first the message is divided into blocks, which size is equal to the number of elements in a sequence in a knapsack. Then, assuming that the 1 indicates that the element of sequence in a knapsack, and a 0 – that the element is absent, we calculate the total weight of knapsack - one knapsack for each message block.

To decrypt the message, at first the recipient must determine the inverse number of n -1, such that (n * n -1)mod m = 1.

To calculate the inverse numbers modulo it is usually used extended Euclidean algorithm. After determining the inverse number, each value of cryptogram multiplied by the n -1 modulo m, and with a private key are determined the bits of the plaintext.

## Application in modern technologies

The RSA algorithm is used for software protection and in digital signature scheme. It is also used in an open system PGP encryption and in other encryption systems, (e.g., DarkCryptTC format and xdc) in combination with symmetric algorithms.

Because of the low speed of encryption (about 30 kbit / s at 512 bit key to data processing machine 2GHz), messages are typically encrypted using more efficient symmetric algorithms with a random key (session key), and using the RSA encrypt only the key, thus is realized a hybrid cryptosystem. Such a mechanism has the potential vulnerability due to the need to use cryptographically strong random number generator for generating a random session key for symmetric encryption and effectively resist the attacks on symmetric encryption algorithm (for the time being are widely used AES, IDEA, Serpent, Twofish).

RSA cryptosystem has standard RFC 2437 - PKCS # 1: RSA Cryptography Specifications Version 2.0.

El Gamal scheme used in the standards Electronic Signature: DSS, GOST R 34.10-94.