Public-Key-Cryptography

Public-Key-Cryptography

In public-key cryptography, there are two keys: a private key and a public key. The private key is kept by the receiver. The public key is announced to the public.

Imagine Sender, as shown in Figure, wants to send a message to receiver. Sender uses the public key to encrypt the message.

When the message is received by Receiver, the private key is used to decrypt the message.

In public-key encryption/decryption, the public key that is used for encryption is different from the private key that is used for decryption.

The public key is available to the public; the private key is available only to an individual.

Public-key encryption/decryption has two advantages. First, it removes the restriction of a shared symmetric key between two entities (e.g., Persons) Who need to communicate with each other.

A shared symmetric key is shared by the two parties and cannot be used when one of them wants to communicate with a third party.

In public-key encryption/ decryption. each entity creates a pair of keys; the private one is kept, and the public one is distributed. Each entity is independent. and the pair of keys created can be used to communicate with any other entity.

The second advantage is that the number of keys needed is reduced tremendously.

In this system, for 1 million users to communicate, only 2 million keys are needed, not 500 billion. as was the case in symmetric-key cryptography.

Public-key cryptography also has one disadvantage, the complexity of the algorithm. If we want the method to be effective. the algorithm needs large numbers.

Calculating the ciphertext from plaintext using the long keys takes a lot of time.

That is the main reason that public-key cryptography is not recommended for large amounts of text.

RSA

The most common public-key algorithm is called the RSA method after its inventors (Rivest, Shamir, and Adleman).

The private key here is a pair of numbers (N, d); the public key is also a pair of numbers (N: e). "Note that N is common to the private and public keys.

The sender uses the following algorithm to encrypt the message:

C= Pe mod N

In this algorithm, P is the plaintext, which is represented as a number; C is the number that represents the ciphertext. The two numbers e and N are components of the public key.

Plaintext P is raised to the power e and divided by N. The mod term indicates that the remainder is sent as the ciphertext.

The receiver uses the following algorithm to decrypt the message:

p=Cd mod N

In this algorithm, P and C are the same as before. The two numbers d and N are components of the private key.

For example

Imagine the private key is the pair (109, 77) and the public key is the pair (109, 5). The sender needs to send the character F.

This character can be represented as number 6 (F is the sixth character in the alphabet), The encryption algorithm calculates C = 65 mod 109 = 41.

This number is sent to the receiver as the ciphertext. The receiver uses the decryption algorithm, to calculate P = 4177 mod 109 = 6 (the original number). The number 6 is then interpreted as F.

The reader may question the effectiveness of this algorithm. If an intruder knows the decryption algorithm and N = 109, the only thing missing is d = 77.

Why couldn't the intruder use trial and error to find d? The answer is yes; in this trivial example an intruder could easily guess the value of d.

But a major concept of the RSA algorithm is to use very large numbers for d and e.

In practice, the numbers are so large (on the scale of tens of digits) that the trial-and-error approach of breaking the code takes a long time (years, if not months) even with the fastest computers available today.

Choosing Public and Private Keys

One question that comes to mind is, How do we choose the three numbers N, d, and e for encryption and decryption to work?

The inventors of the RSA used number theory to prove that using the following procedure will guarantee that the algorithms will work.

1. Choose two large prime numbers p and q.

2. Compute N = P x q.

3. Choose e (less than N) such that e and (p – l) (q - 1) are relatively prime (having no common factor other than 1).

4. Choose d such that (e x d) mod [(p - l) (q - 1)] is equal to 1.