Public key encryption: definition, features and types of algorithms

The idea of ​​public key encryption was first introduced at Stanford University in 1976 by M. Hellman, R. Merkle and W. Diffie.

Two types of PKC algorithms are: RSA, an abbreviation named after the inventors: Rivest, Shamir and Adelman, and DSA (Digital Signature Algorithm). PKC encryption has evolved to meet the growing secure communication needs of many sectors and industries, especially the military. Unlike symmetric-key cryptography, public-key encryption is a relatively new concept.

Stages of the emergence of cryptosystems

Symmetric cryptography is also well suited for large financial corporations that use secret transmission of information. With the proliferation of unprotected computer networks over the past few decades, there has been an urgent need to use cryptography on a larger scale. The symmetric key turned out to be impractical because of the problems that it encountered while managing the system. This led to public key encryption.

Stages of the creation process:

• 1977 year. Invented by the RSA by a group of programmers R. Rivest, A. Shamir and L. Adleman.
• 1978 year. Created by MacAlice due to decoding problems for Goppa codes.
• 1979 year. Rabin came out, based on the factoring problem and related to RSA.
• 1984 year. Published by Chor-Rivest.
• 1985 year. Elgamal came out based on a discrete logarithm.

Other asymmetric cryptosystems:

1. An elliptical method based on elliptic curves, reminiscent of Elgamal.
2. Merkle / Hellman - based on the LUC backpack problem, like RSA, it forms a Lucas sequence.
3. MNLN is the same as RSA.

The principle of encryption, advantages and disadvantages

To understand the principle of asymmetric encryption, you must always remember that you are dealing not only with one key, but with two. Public key encryption begins with the publication of the public key. Publication can be done, for example, through the server, as well as by mail. The user does not need to transfer it in a safe way, everyone can take possession of the public key. It is often even desirable for it to be distributed globally to ensure that no other public key is distributed under false names.

Using a public key encryption system, everyone is able to secure information for the public key owner. Therefore, the message is decrypted by the recipient with its secret key. That is why it is so important that the key remains secret. Its owner can decrypt all messages encrypted by others, their own public key.

Such cryptosystems are used for public-key data encryption, authentication, and integrity. Well-known examples based on asymmetric methods are OpenPGP or S / MIME, as well as cryptographic protocols such as SSH, SSL / TLS and even https based on asymmetric cryptosystems.

Benefits:

1. Relatively high security.
2. It does not require as many keys as in the symmetric encryption method, thereby less effort to create privacy.
3. No problems with key transfer.
4. Authentication with digital signatures.

The disadvantages of public key encryption systems are:

1. Algorithms work very slowly: approximately 10,000 times slower than symmetric ones.
2. Large key length required.
3. Problems with multiple recipients when a message must be additionally encrypted.
4. Remedies for hybrid procedures.
5. The security risk available for each public key is also a drawback of public key encryption systems.

Asymmetric cryptography

PKC is also known as public key encryption, asymmetric encryption, asymmetric cryptography, asymmetric cipher, asymmetric key encryption, and Diffie-Hellman encryption. PKC is a cryptographic algorithm and cryptosystem component implemented by various Internet standards, including Transport Layer Security (TLS), Pretty Good Privacy (PGP), GNU Privacy Guard (GPG), Secure Socket Layer (SSL), and Hypertext Transfer Protocol (HTTP) .

PKC provides secure communication over an insecure channel that only allows the intended recipient to read the message. For example, A uses the public key B to encrypt a message that can be decrypted using the unique private key B.

PKC maintains email confidentiality and ensures communication security when messages are in transit or stored on mail servers. PKC is also a DSA component used to authenticate a private key, which can be verified by anyone with authorized public key access. In this way, PKC facilitates the confidentiality, data integrity, and authentication that form the key information (IA) parameters.

PKC is slower than secret key cryptography (or symmetric cryptography) methods, due to high computational requirements. This is a clear flaw in public key encryption systems. Unlike symmetric cryptography, PKC uses a fixed buffer size, depending on specific and small amounts of data that can be encrypted and not tied to streams. Because a wide range of possible encryption keys is used, PKC is more reliable and less susceptible to security breach attempts.

Public key method

Different keys are used for encryption and decryption. This is a property that sets a scheme other than symmetric encryption. Each receiver has a unique decryption key, commonly called a private decryption key.

The recipient needs to publish one called the public key of the encryption method. Some confidence in its authenticity is needed in this scheme in order to avoid the substitution of attackers as a recipient. Typically, this type of cryptosystem includes a trusted third party that certifies that a particular public key belongs only to a particular person or object.

The RSA public key encryption algorithm is sophisticated enough to prevent an attacker from extracting plaintext from encrypted text and a shared encryption key.

RSA pair generation

Each person or party who wants to participate in communication using cryptography immediately generates a couple of options, namely the public and private encryption keys. The process is described below:

1. Generate RSA module (n).
2. Two primes p and q are selected.
3. Find the derivative number e. The number e must be greater than 1 and less than (p - 1) (q - 1). For e and (p - 1) (q - 1) there should not be a common factor except 1.
4. Perform encryption using the public key.
5. A pair of numbers (n, e) forms the RSA public key. Although n is part of the public key, the difficulty of factorizing such a number ensures that the attacker cannot find two prime numbers (p & q) used to obtain n in finite time. This understanding is the foundation of RSA.

Creating a private key is as follows. The private key d is calculated from p, q and e. For given n and e, there is a singular d. The number d is the inverse of e modulo (p - 1) (q - 1). This means that d is a number less than (p - 1) (q - 1), but such that when multiplied by e it is 1 modulo (p - 1) (q - 1). This relation is written mathematically as follows:

ed = 1 mod (p - 1) (q - 1).

The advanced Euclidean algorithm takes p, q and e as input and gives d as output. The following is an example of creating an RSA Key pair. For ease of understanding, the primes p & q, taken here, are small values. In practice, these values ​​should be very significant.

Calculation algorithm:

1. Let two primes be equal to p = 7 and q = 13. Thus, the module n = pq = 7 x 13 = 91.
2. Choose e = 5, which is an acceptable choice, since there is no number that is a common factor of 5 and (p - 1) (q - 1) = 6 × 12 = 72, with the exception of 1. A pair of numbers (n, e) = (91, 5) generates a public key and may be available to anyone who needs to send encrypted messages. The input is p = 7, q = 13, and e = 5. The output will be d = 29.
3. Make sure that the calculated d is correct - de = 29 × 5 = 145 = 1 mod 72.
4. Therefore, the public key is (91, 5) and private keys (91, 29).

Encryption and decryption

Further, the encryption and decryption process is relatively simple and easy to calculate. Interestingly, RSA does not directly work with bit strings, as in the case of the symmetric method. It works with numbers modulo n. Therefore, it is necessary to represent plaintext as a series of numbers less than n.

RSA Encryption:

1. Suppose the sender wants to send a text message to someone whose public key is (n, e).
2. The sender then presents the plaintext as a series of numbers less than n.
3. Encrypt the first plaintext P, which is a number modulo n. The encryption process is a simple math step, C = Pe mod n.

In other words, the ciphertext C is equal to the open text P times e times and then reduced modulo n. This means that C is also less than n. Returning to the example of generating plaintext keys P = 10, we get ciphertext: C = 105 mod 91.

RSA Decryption:

1. The decryption process for RSA is also very simple. Suppose the recipient of the key pair (n, e) has received the text C.
2. The receiver raises the value of C for key d. The result modulo n will be plain text P: Plaintext = Cd mod n.
3. Returning again to a numerical example, the ciphertext C = 82 will be decrypted to the number 10 using the private key 29: Plaintext = 8229 mod 91 = 10.

RSA security depends on the strengths of two separate functions. The RSA cryptosystem is the most popular public key cryptosystem based on the practical difficulty of factorizing very large numbers.

Encryption function - it is considered a unidirectional function of converting plaintext to encrypted text and can only be canceled using the secret key d. The difficulty of determining the RSA public and private encryption keys is equivalent to factorization of module n. Thus, an attacker cannot use the knowledge of the RSA public key to determine the RSA private key, unless he can determine n. This is also a one-way function, the transition from p & q to the module n is easy, but the opposite is not possible.

If either of these two functions is not one-way, then the RSA is violated. In fact, if factoring technology is effectively developed, then RSA will no longer be safe. The strength of the RSA encryption is sharply reduced against attacks if the numbers p and q are not prime numbers or the selected public key e is a small number.

Cryptosystem ElGamal

Along with RSA, there are other public key cryptosystems. Many of them are based on different versions of the discrete logarithm problem.

The ElGamal cryptosystem, called a variant of the elliptic curve, is also based on the discrete logarithm problem. It draws the power of protection from the assumption that discrete logarithms cannot be found in a practical time interval for a given number, while the inverse power operation can be calculated efficiently.

For example, a simple version of ElGamal that works with modulo p numbers. In the case of variants of an elliptic curve, the method is based on completely different calculus systems. Each user of the ElGamal cryptosystem generates a key pair as follows:

1. Choosing a large prime p. Usually a prime number between 1024 and 2048 bits is selected.
2. Generator Element Selection g. This number must be between 1 and p - 1.
3. He is a generator of the multiplicative group of integers modulo p. This means that for any integer m co-prime with p there is an integer k such that gk = a mod n. For example, 3 is a generator of group 5 (Z 5 = {1, 2, 3, 4}).

Secret key selection. The private key x is any number greater than 1 and less than (p-1). Calculation of the public key part. The value of y is calculated by the parameters p, g and the private key x as follows:

y = gx mod p.

Getting the public key. The ElGamal public key consists of three parameters (p, g, y). Suppose, for example, that p = 17 and g = 6. It can be argued that 6 is a generator of the group Z 17. The private key x can be any number greater than 1 or less 71, therefore, choose x = 5. Then, the y value is calculated as follows:

y = 65 mod 17 = 7.

Thus, the private key is 62, and the public key is (17, 6, 7).

ECC elliptic curve

Elliptic Cryptography Curve (ECC) is a term used to describe a set of cryptographic tools and protocols whose security is based on special versions of the discrete logarithm problem. He does not use modulo p numbers. ECC is based on sets of numbers associated with mathematical objects called elliptic curves. There are rules for adding and calculating multiples of these numbers, as well as for numbers modulo p.

ECC includes options for many cryptographic schemes that were originally developed for modular numbers, such as ElGamal encryption, public key encryption algorithms, and digital signatures. It is believed that the discrete logarithm problem is much more complicated when applied to points on an elliptic curve.

This causes a transition from numbers modulo “p” to points on the elliptic curve. An equivalent level of security can also be obtained with shorter keys if options with an elliptic curve are used. Shorter keys lead to two benefits of public key encryption:

1. Easy key management.
2. Effective computing.

These advantages make elliptic curve encryption options very attractive for applications where computing resources are limited. You can quickly compare RSA and ElGamal schemes for various aspects.

Secure Sockets Layer Protocol (SSL)

Internet traffic that transmits information through intermediate computers can be intercepted by a third party:

1. Eavesdropping. The information remains intact, but its privacy is compromised. For example, someone might collect credit card numbers, record a private conversation, or intercept sensitive information.
2. Fake The information in transit is changed or replaced, and then sent to the recipient. For example, someone may change the order of goods or change a person’s resume.
3. Personification. Information is passed on to the person who represents as the intended recipient.

Avatar can take two forms:

1. Substitution. A person can pretend to be someone else.
2. Distortion. A person or organization can distort itself. For example, a named site may qualify for a role in an online furniture store when it does receive credit card payments but never sends any goods.

Public key cryptography provides protection against Internet attacks.

Encryption Algorithm and Its Security Benefits

It is not practical to calculate the private key based on the public key. Because of this, public keys can be freely used, which makes it easy and convenient to use content encryption and digital signature verification, and private keys can be kept secret, ensuring that only holders of private keys can decrypt content and create digital signatures.

Because public keys must be shared but too large to be easily remembered, they are stored in digital certificates for secure transport and sharing. Private keys are not shared, they are simply stored in the software or operating system that they use, or on hardware, such as a USB token, hardware that contains drivers that allow it to be used with the software or operating system.

Digital certificates are issued by organizations known as certification authorities (CAs). The main business applications for public key cryptography are:

1. Digital signatures - the content of a digital signature with a user's private key is verified by the user's public key.
2. - .

, , :

1. - , , , .
2. - , , .

(PKI) , , , , , , , .

PKI , -, - , -, HTTPS.

PKI, , . , PKI , .

PKI :

1. A certification policy is a security specification that defines the structure and hierarchy of the PKI ecosystem, as well as policies related to key management, secure storage, processing, revocation.
2. The root certification authority (CA) is responsible for authenticating identities in the system.
3. The intermediate CA is certified by the root CA for the specific purposes defined by the certificate policy.
4. Digital certificates are usually issued and signed by certification authorities.
5. The certificate database stores their records.
6. Revocation services are servers that publish updated Certificate Revocation Lists (CRLs) or Online Certificate Status Protocol (OCSPs) that use CRLs and respond to revocation checks for devices that cannot handle CRLs themselves.

Thus, asymmetric cryptosystems are used for encryption, authentication and integrity. If an attacker does not have a public encryption key certificate, he will never be able to use secret data. Known examples based on asymmetric methods are OpenPGP or S / MIME. But also cryptographic protocols, such as SSH, SSL / TLS or even https, are based on asymmetric cryptosystems.