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.

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

Stages of emergence of cryptosystems

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

Steps in the creation process:

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

Other asymmetric cryptosystems:

1. An elliptic curve method similar to Elgamal.
2. Merkle / Hellman - based on the knapsack problem, LUC, like RSA, forms a Lucas sequence.
3. MNLN - same as RSA.

Encryption principle, 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 pass it through a secure path, anyone can get hold of the public key. It is often even desirable that it be distributed globally to ensure that no other public key is distributed under false names.

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

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

Benefits:

1. Relatively high security.
2. Does not require as many keys as symmetric encryption method, thus less effort to create secrecy.
3. No issue with handover of keys.
4. Ability to authenticate with digital signatures.

The disadvantages of public key encryption systems are:

1. Algorithms are very slow: about 10,000 times slower than symmetrical ones.
2. Large required key length.
3. Problems with multiple recipients when the message needs to be further encrypted.
4. Hybrid procedure protections.
5. The security risk available for each public key is also a disadvantage of public key encryption systems.

Asymmetric cryptography

PKC also known aspublic 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 B's public key to encrypt a message that can be decrypted using B's unique private key.

PKC maintains email privacy and secure communications while messages are in transit or stored on email servers. The PKC is also a component of the DSA used to authenticate the secret key, which can be verified by anyone with authorized access to the public keys. Thus, PKC facilitates confidentiality, data integrity, and authentication, which form key information (IA) parameters.

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

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 referred to as a private 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 to avoid spoofing attackers as the recipient. Typically, this type of cryptosystem involves a trusted third party that certifies that a particular public key only belongs to a particular person or entity.

The RSA public key encryption algorithm is sophisticated enough to prevent an attacker from inferring plaintext from the ciphertext and the shared encryption key.

Generate an RSA pair

Each person or party wishing to participate in communication using cryptography generates a pair of options at once, namely a public and private encryption key. The process is described below:

1. Generate RSA module (n).
2. Select two primes p and q.
3. Find the derived number e. The number e must be greater than 1 and less than (p - 1) (q - 1). e and (p - 1) (q - 1) must have no common factor other than 1.
4. Perform encryption using the public key.
5. Pair of numbers (n, e) forms an RSA public key. Although n is part of the public key, the difficulty in factoring such a number ensures that an attacker cannot find, in finite time, the two primes (p & q) used to obtain n. This understanding is the basis of RSA.

Creating a secret key is as follows. The private key d is calculated from p, q and e. Given n and e, there is a single number 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 ratio is written mathematically as follows:

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

The extended Euclidean algorithm takes p, q and e as input and gives d as output. Below 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. So the modulus n=pq=7 x 13=91.
2. Choose e=5, which is a valid choice since there is no number that is a common factor of 5 and (p - 1) (q - 1)=6 × 12=72 except for 1. The pair of numbers (n, e)=(91, 5) forms a public key and can be accessed by anyone who needs to send encrypted messages. Input p=7, q=13 and e=5. Output will be d=29.
3. Make sure thatcalculated d is correct - de=29 × 5=145=1 mod 72.
4. Hence the public key is (91, 5) and the private keys are (91, 29).

Encryption and decryption

Next, the encryption and decryption process is relatively simple and easy to calculate. Interestingly, RSA does not deal directly with bitstrings, as is the case with the symmetric method. It works with numbers modulo n. Therefore, it is necessary to represent the 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 plaintext P multiplied by it e times and then reduced modulo n. This means that C is also less than n. Returning to the example of generating keys with plaintext P=10, we get the ciphertext: C=105 mod 91.

RSA decoding:

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

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

Encryption function - considered a one-way function of converting plaintext to ciphertext and can only be overridden with the secret key d. The difficulty of determining the public and private key of an RSA encryption is equivalent to factoring the modulo n. Thus, an attacker cannot use knowledge of the RSA public key to determine the RSA private key unless he can determine n. It is also a one-way function, going from p & q values to modulo n is easy, but the reverse is not possible.

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

ElGamal cryptosystem

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 the elliptic curve variant, is also based on the discrete logarithm problem. It derives the strength of the defense from the assumption that discrete logarithms cannot be found in practice.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 the elliptic curve, the method is based on completely different systems of calculation. Each user of the ElGamal cryptosystem generates a key pair as follows:

1. Choose a large prime number p. Usually a prime number between 1024 and 2048 bits is chosen.
2. Select generator element g. This number must be between 1 and p - 1.
3. It is the generator of the multiplicative group of integers mod p. This means that for any integer m co-prime with p, there exists an integer k such that g k=a mod n. For example, 3 is the generator of group 5 (Z 5={1, 2, 3, 4}).

N	3	3 mod 5
1	3	3
2	9	4
3	27	2
4	81	1

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

y=gx mod p.

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

y=65 mod 17=7.

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

Elliptic Curve ECC

Elliptic Curve Cryptography (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. It does not use modulo p numbers. ECC is based on sets of numbers associated with mathematical entities called elliptic curves. There are rules for adding and calculating multiples of these numbers, as for numbers modulo p.

ECC includes variants of 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 difficult when applied to points on an elliptic curve.

This causes a transition from numbers modulo "p" to points on an elliptic curve. Also, an equivalent level of security can be obtained with shorter keys if the elliptic curve variants are used. Shorter keys result in two benefits of encrypting information with the public key:

1. Easy key management.
2. Efficient calculation.

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

RSA	ElGamal
More efficient for encryption.	More efficient for decryption.
Less efficient for decryption.	More efficient for decryption.
Long keys are required for a certain level of security in RSA.	The same level of security requires very short keys.
The method is widely used.	New method and not yet very popular on the market.

Secure Sockets Layer (SSL)

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

1. Eavesdropping. The information remains intact, but its confidentiality is compromised. For example, someone might collect credit card numbers, record a confidential conversation, or intercept sensitive information.
2. Fake. The information in transit is modified or replaced and then sent to the recipient. For example, someone might change an order for goods or change a person's resume.
3. Incarnation. The information passes to the person who presents as the intendedrecipient.

An impersonation 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 can claim to be an online furniture store when it actually receives credit card payments but never ships any items.

Public key cryptography provides protection against Internet attacks.

Encryption algorithm and its security benefits

It is not practical to calculate a private key from a public key. Because of this, public keys can be freely applied, making it easy and convenient to use content encryption and digital signature verification, while private keys can be kept secret, ensuring that only owners of private keys can decrypt content and create digital signatures.

Because public keys need to be shared but are 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 is being used, 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 Certificate Authorities (CAs). Key Business Applications for Public Key Cryptographyare:

1. Digital signatures - Digital signature content with the user's private key is verified with the user's public key.
2. Encryption - content is encrypted with the public key and can only be decrypted with the user's private key.

Assuming the user's private key has not been compromised, data and message encryption provides the following security benefits:

1. Privacy - Since the content is encrypted with the user's public key, it can only be decrypted with the private key, ensuring that only the intended recipient can decrypt and view the content.
2. Integrity - Part of the decryption process involves checking that the content of the original encrypted message and the new decrypted match, so even the slightest change to the original content will cause the process to fail.

Open Tool Infrastructure

Public Key Infrastructure (PKI) is a background cybersecurity measure that is described as a set of rules, policies and procedures required to create, manage, distribute, use, store and revoke digital certificates.

PKI is based on asymmetric cryptography, widely used today to provide electronic communications for online shopping, internet banking and email, and to secure communications between millions of users and the websites they connect tousing

Although it is easy to encrypt messages without PKI, the user cannot easily verify who they are communicating with. In other words, the PKI infrastructure helps him to authenticate or verify the identity he is communicating with.

A typical PKI ecosystem includes the following key components:

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. An intermediate CA is certified by a root CA for the specific purposes defined by the certificate policy.
4. Digital certificates are usually issued and signed by certification authorities.
5. The database of certificates stores their records.
6. Revocation Service are servers that publish updated Certificate Revocation Lists (CRLs) or Online Certificate Status Protocol (OCSP) that use CRLs and respond to revocation checks for devices that themselves cannot process CRLs.

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 the secret data. Well-known examples based on asymmetric methods are OpenPGP or S/MIME. But also cryptographic protocols like SSH, SSL/TLS or even https are based onasymmetric cryptosystems.