Can public key be used to decrypt?

Public Key Encryption

Public key encryption uses two different keys. One key is used to encrypt the information and the other is used to decrypt the information. Sometimes this is referred to as asymmetric encryption because two keys are required to make the system and/or process work securely. One key is known as the public key and should be shared by the owner with anyone who will be securely communicating with the key owner. However, the owner’s secret key is not to be shared and considered a private key. If the private key is shared with unauthorized recipients, the encryption mechanisms protecting the information must be considered compromised.

Public key encryption

Public key encryption is also referred to as asymmetric encryption because there is not just one key used in both directions as with the symmetric encryption. In public key encryption there are two keys; whichever one is used to encrypt requires the other be used to decrypt. In this chapter we will stick with the term public key encryption to help establish context and contrast it to shared key encryption.

The keys in public key encryption are nonmatching but they are mathematically related. One key (it does not matter which) is used for encryption. That key is useless for decryption. Only the matching key can be used for decryption. This concept provides us with the critical facility we need for secure key exchange to establish and transport a shared key.

A diagram showing how basic public key encryption works is shown in Fig. 4.

A note about Kerberos before we continue with discussions of public key encryption. While it is true that Kerberos is an alternative for distributing shared keys, Kerberos only applies to a closed environment where all principals requiring keys share direct access to trusted key distribution centers (KDCs) and all principals share a key with that KDC. Microsoft Windows natively support Kerberos so within a closed Windows-only environment Kerberos is an option. No further discussion of Kerberos is contained in this chapter. We recommend public key systems for this function. Public key systems work with paired keys one of which (the private key) is kept strictly private and the other (the public key) is freely distributed; in particular the public key is made broadly accessible to the other party in secure communications.

Communicating parties each must generate a pair of keys. One of the keys, the private key, will never leave the possession of its creator. Each party to the communication passes their public key to the other party. The associated public key encryption algorithms are pure mathematical magic because whatever is encrypted with one half of the key pair can only be decrypted with its mate. Combining this simple fact with the strict rule that private keys remain private and only public keys can be distributed leads to a very interesting and powerful matrix of how public key encryption interrelates to confidentiality and identity. This matrix is shown in Table 1.

Table 1. How Public Key Encryption Interrelates to Confidentiality and Identity

Public KeyPrivate KeyWhat This MeansEncrypt (w/ recipient's)Decrypt (w/ recipient's)Confidentiality (no one but intended recipient can read)Decrypt (w/ sender's)Encrypt (w/ sender's)Signature (identity) (it could only have come from sender)

For Alice to send a confidential message to Bob, Alice must obtain Bob's public key. That's easy since anyone can have Bob's public key at no risk to Bob; it is just for encrypting data. Alice takes Bob's public key and provides it to the standard encryption algorithm and encrypts her message to Bob. Because of the nature of the public-private key pair and the fact that Alice and Bob agree on a public, standard encryption algorithm (like RSA), Bob can use his private key to decrypt Alice's message. Most importantly, only Bob—because no one will ever get their hands on Bob's private key—can decrypt Alice's message. Alice just sent Bob a confidential message. Anyone intercepting it will get just scrambled data because they don't have Bob's private key.

Digital signatures will be described in just a moment but notice something interesting about doing things just the reverse of Alice's confidential message. If Alice encrypts a message with her private key, which only Alice could possess, and if Alice makes sure Bob has her public key, Bob can see that Alice and only Alice could have encrypted that message. In fact, since Alice's public key is in theory accessible to the entire world, anyone can tell that Alice and only Alice encrypted that message. The identity of the sender is established. That is the basic principle of digital signature.

Remember: encrypt with your private key and the whole world using your public key can tell it could be from you and only you (digital signature) or encrypt with a specific person's public key and they and only they, using their private key, can read your message (secret or confidential messages).

Public key encryption is based on the mathematics of factoring large numbers into their prime factors. This problem is thought to be computationally intractable if the numbers are large enough. But a limitation of public key encryption is that it can only be applied to small messages. To achieve our goal of distributing shared keys this is no problem—shared keys are not larger than the message size limitation of public key algorithms. To achieve our goal of digital signatures we will apply a neat trick and remain within this size limitation as we will discuss momentarily.

Public key vs shared key performance

Even when implemented in hardware, shared key algorithms are many orders of magnitude faster than public key encryption. In hardware, RSA is about 1000 times slower than DES.

The first performance hit comes from key generation. We must find two multihundred-bit prime numbers that are near the same length. Then these two primes must be tested for primality, a very expensive operation requiring a series of steps that each have a certain probability of determining the values are relatively prime and must be run several times to make the probability high enough as to be of an acceptably infinitesimal risk of being wrong.

The second reason that public key encryption is so much slower than shared key is that RSA encryption/decryption is based on the mathematics of modular exponentiation. This means we are taking each input value, raising it to a power (a large number of multiplications) and then performing the modulo operation (the remainder after doing integer division). On the other hand, shared key ciphers are based on much faster logical operations on bit arrays. Public key algorithms are called asymmetric for a reason. Because the private key has a much larger exponent than the public key, private key operations take substantially longer than do public key operations. In confidentiality applications (i.e., encryption) where the public key is used for encryption, decryption takes substantially longer than decryption. In integrity applications (i.e., signature) where the private key is used for encryption it is the other way around. This imbalance would be a problem when applied to large messages but is not an issue when applied only to small messages such as the 200-bit key for shared key encryption.

The third reason to be concerned about the computational complexity of public key encryption is the padding issues. The input to RSA encryption operations is interpreted as a number so special padding is required to make the input totally consistent. The total length of the data must be a multiple of the modulus size and the data must be numerically less than the modulus. A 1024-bit RSA key has a 128-byte modulus. Therefore, data must be encrypted in blocks of 128 bytes. Each input number must be padded with zeros until its numerical value is less than that of the modulus. XML encryption specifies the use of PKCS#1 Block 02 padding. This padding places a critical restriction on the size of data that RSA can encrypt. This is why RSA is never used to encrypt the entire plaintext message but only the shared key being exchanged between communicating parties. Once the shared key is established safely between the parties, AES encryption is used on the plaintext message itself.

On the negative side, shared key cryptography fails to solve the problem of scalable key distribution. These algorithms are fast and can handle infinitely large messages but both ends of the communication need access to the same key and we need to get it to them securely. Shared key cryptography also fails to solve the issue of repudiation. We are going to need to be able to prove that a certain identity created and attests to sending a message (or document) and no one else could have. They must not be able to deny having sent this exact document at this moment in time. Shared key cryptography provides no help here. Finally, shared key cryptography fails to solve the issue of data integrity. We know no one intercepted our message and we have some assurance that no blocks of data in the message were substituted thanks to cyclic block chaining, but we do not have assurance that our message sent and received are identical. For these issues, we need public key cryptography.

2.2.2 Public-Key Encryption

Public-key encryption systems are quite different from the popular private-key encryption systems like DES. They rely on a substantially different branch of mathematics that still generates nice, random white noise. Even though these foundations are different, the results are still the same.

The most popular public-key encryption system is the RSA algorithm that was developed by Ron Rivest, Adi Shamir, and Len Adleman when they were at MIT during the late 1970s. Ron Rivest, Adi Shamir, and Len Adleman The system uses two keys. If one key encrypts the data, then only the other key can decrypt it. After the encryption, first key becomes worthless It can't decrypt the data. This is not a bug, but a feature. Each person can create a pair of keys and publicize one of the pair, perhaps by listing it in some electronic phone book. The other key is kept secret. If someone wants to send a message to you, they look up your public key and use it to encrypt the message to you. Only the other key can decrypt this message now and only you have a copy of it.

In a very abstract sense, the RSA algorithm works by arranging the set of all possible messages in a long, long loop in an abstract mathematical space. The circumference of this loop, call it n, is kept a secret. You might think of this as a long necklace of pearls or beads. Each bead represents a possible message. There are billions of billions of billions of them in the loop. You send a message by giving someone a pointer to a bead.

The public key is just a relatively large number, call it k. A message is encrypted by finding its position in the loop and stepping around the loop k steps. The encrypted message is the number at this position. The secret key is the circumference of the loop minus k. A message is decrypted by starting at the number marking the encrypted message and marching along the n − k steps. Because the numbers are arranged in a loop, this will bring you back to where everything began– the original message.

Two properties about this string of pearls or beads make it possible to use it for encryption. The first is that given a bead, it is hard to know its exact position on the string. If there is some special first bead that serves as the reference location like on a rosary, then you would need to count through all of the beads to determine the exact location of one of the beads. This same effect happens in the mathematics. You would need to multiply numbers again and again to determine if a particular number is the one you want.

The second property of the string of beads in this metaphor does not make as much sense, but it can still be easily explained. If you want to move along the string k beads, then you can jump there almost instantaneously. You don't need to count each of the k beads along the way. This allows you to encrypt and decrypt messages using the public-key system.

The two special features are similar but they do not contradict each other. The second says that it is easy to jump an arbitrary number of beads. The first says it's hard to count the number of pearls between the first bead and any particular bead. If you knew the count, then you could use the second feature. But you don't so you have to count by hand.

The combination of these two features makes it possible to encrypt and decrypt messages by jumping over large numbers of beads. But it also makes it impossible for someone to break the system because they can't determine the number of steps in the jump without counting.

This metaphor is not exactly correct, but it captures the spirit of the system. Figure 2.3 illustrates it. Mathematically, the loop is constructed by computing the powers of a number modulo some other number. That is, the first element in the loop is the number. The second is the square of the number, the third is the cube of the number, and so on. In reality, the loop is more than one-dimensional, but the theme is consistent.

3.3 Public-key encryption

A Public-key Encryption (PKE) with plaintext-space Pconsists of the following three algorithms:

pksk←KeyGen1κ: The key generation algorithm takes the security parameter κ as input, outputs a public key and a secret key (pk, sk).

c ← Enc (pk, pw;r): the encryption algorithm takes pk and a plaintext pk∈Pas inputs, with an internal coin flipping r, outputs a ciphertext c.

pw ← Dec(sk,c): the decryption algorithm takes sk and c as inputs, and outputs a plaintext pw or ⊥.

2.6.4 Noninteractive proof (example)

In public key encryption system, the authenticity of public key and private key pair of an entity is ensured by a certificate authority. Harry (verifier) wants to verify that Tom has a private key (i.e., a legitimate user of the system), he can directly check the authenticity of the certificate issued to Tom. The certificate is served as a noninteractive proof.

In a blockchain network, verification of a node's identity uses noninteractive proofs explained as above. Further, zero-knowledge proofs can be used to validate a transaction without revealing identity of sender and recipient. Zcash (Ben-Sasson et al., 2014) is a crypto-currency that provides anonymity of entities involved in its transactions.

Pocket Calculator Encryption at the Client

The security that public key encryption provides is a consequence of the difficulty of factoring large numbers, not the complexity of the method. You can do PKI on any pocket calculator. The “how” is shown in the “Three Magic Numbers” sidebar and explained in material following.

Three Magic Numbers

Start with three magic numbers: Public “normalizer” N=33, public encryption key E=3, and private decryption key D=7.

Encrypt plain-text letter “O” (15th letter of the alphabet) from certificate N and E values.

Write down “O” value E times and multiply:

15×15×15×3375

Divide by N and compute remainder:

3375/33=102.27272…

0.27272…×33=8.99976=9

Send 9, the cipher text for plain-text 15, over the network.

We have to start with three “magic” numbers, and two of them must be prime numbers. Usually, you choose two large primes first (hundreds of digits) and derive a third huge number called N (for “normalizer”) through a very complex process. N is never called a key in the documentation, but N is necessary for both encrypting and decrypting. The security comes from the fact that given a large N and one of the keys, it is next to impossible to derive the second prime key number. In this example, N=33, and the two primes are 3 and 7. There is no obvious relationship between 33 and 3 and 7, although with these small numbers, a code cracker could figure it out in a minute or two.

One of the two primes becomes the public key (it doesn’t matter which), and the other becomes the private key. Never consistently assign the smaller number as the public key. This speeds up client encryption, but is a security risk if people know one factor must be larger than the other. In this example, N=33, the public encryption key E=3, and the private decryption key D=7.

4.2 Protocols with general public key encryption

Kaghazgaran's first protocol used public key encryption [31]. The DO uploads the ciphertexts of his data to CS. CS selects a random integer l and calculates the different of ciphertexts and the integer, then the results will be sent to TP. TP recovers the plaintexts. TP adds 1 to N to the result in order, without knowing the integer, and decrypt them. CS gets the magnitude relation from the l-th result. The protocol is described in Table 7. The processes is shown in Fig. 8.

Table 7. Kaghazgaran's protocols with general public key encryption.

Algorithm 5: Kaghazgaran's first comparison protocolAt DO:
Generates a public/private key pair (pk, sk);
Shares the private key sk to TP;
Uploads Epk(xi)(i = 1, 2, ⋯, n), the ciphertexts of his data xi’s, to CS;
At CS:
Picks a random integer l(1 < l < L) and computes the values of: ci = Epk(xi) − l;
Sends ci’s to TP;
At TP:
Decrypts ci’s to get mi,j = Dsk(ci + j)(j = 1, 2, ⋯, L);
Generates random r and computes Mi, j = mi,j + r;
Sends the n arrays in size of L to CS;
At CS:
Looks at l-th number of each array sent by CS A, and get the sort of the data it kept.

Source: author.

This scheme is similar to Yao's scheme. Although TP can get mi,l = xi,l is not known by TP, it cannot derive which ones are the data owner's original data. The operation Mi,j = mi,j + r makes sure that CS can sort those data without knowing the exact values of DO's original data. This protocol takes full advantage of cloud servers, and makes it possible to sorting over encrypted data without data owner involved. However, it still comes with big computation overhead and communication overhead.

Digital Certificates

As mentioned earlier, public key encryption is more secure than secret key encryption because there is no need to transmit a key across unsecured channels, but public key cryptography is also more complex, and it's more difficult to implement on a large scale. There must be a system that ensures that public keys that are posted to the Internet are not forgeries posted by someone who purports to be another user. If this happens, the data that is encrypted with that public key (and intended to be sent to the user whose name was associated with it) could be intercepted by the unauthorized user who posted the key. That unauthorized person would then be able to decrypt the data and read the message.

We need a mechanism that will provide a way for a trusted third party to confirm that the user who publishes the public key is in fact who he or she claims to be. A digital certificate provides this assurance. To understand how a digital certificate works, think of the way a driver's license or government-issued ID card is used for identity verification. If a store or bank requires that you prove your identity by producing a license or ID card, that entity is relying on the word of a trusted third party (in this case, the Department of Motor Vehicles [DMV]) that you are who you say you are. The store or bank presumes that the DMV has checked you out and would not have issued the official identification document unless your identity was confirmed.

Just as the store or bank accepts your driver's license as proof of your identity, another computer with which you want to exchange data or make transactions will accept the digital certificate issued by a trusted third party. In the case of digital certificates, the trusted third party is a certificate authority (CA). The CA verifies that a particular identity is bound to the public key that is included in the certificate.

Some public CAs, such as VeriSign, issue certificates to persons on the Internet. Some private (internal) CAs are set up by organizations to issue certificates to users within the local network. The CA is a server that runs special software that allows it to issue, manage, and revoke digital certificates. The CA's role is to guarantee to other users, computers, and applications that a particular public key really belongs to the entity with whose name it is associated.

9.5 COMPARISON OF PRIVATE-KEY AND PUBLIC-KEY ENCRYPTION TECHNOLOGIES

Both private-key and public-key encryption systems were developed in academia in the early 1970s and provide very secure modern communications over public networks. Both use computers and many of the same technical concepts and approaches including (1) a mathematical process that generates each key, (2) an error checking scheme that also generates a hash, (3) message digests, (4) key IDs, (5) key certificates, and (6) key rings. However, the manner in which the two encryption systems do this differs significantly. The similarities and differences, advantages and disadvantages, of each are compared in Table 9.1 on pages 354 and 355.

TABLE 9.1.

Private-Key SystemsPublic-Key SystemsKnowledge of KeysBoth sender and receiver must know the (same) key before they can exchange encrypted information.

Sender need only know the recipient's public key to communicate. If recipient's public key is unknown, sender can locate it in a key server or the two parties can establish a one-time session key.

The recipient's private key is not shared, but rather retrieved by a software-based link to recipient's public key.

Communicating parties need not know each other before they communicate.

Need not have communicated before.

Strangers can communicate with one another in private.

A sender need only know the recipent's public key to send a message to that party.

Works well in Internet Age because it allows flexible, secure communications between any two or more persons (without the need for any prior key hand-off or information about one another.)

This means that two total strangers, persons who have never met one another nor had any previous communication, may immediately exchange encrypted information with one another. They need not exchange a key before this occurs.

For this reason, public-key technology is perfect for the Internet Age and the modern communications between very far-flung persons.

Public-key encryption is the current direction of most new encryption systems in the Internet Age.

Keys are created and controlled by the user, not by a central authority. No key hand-off is required.

No centralized authority is needed or required to operate the system.

A key cannot be changed until the sender informs the receiver about the change and communicates the new key to the receiver.

Thus, a key cannot be easily changed.

A person's public key can be changed at any time simply by selecting and publishing a new public key. The encryption system then provides a new corresponding private key to be used by the owner to decrypt all messages sent to the new public key. Directories will make knowledge of the change available to anyone not directly updated by the owner.

Private keys are managed by the key owner, and never needs to be revealed to others.

Since both sender and receiver must know the key, the security of the key is vulnerable during both hand-off and routine use.

Key must be closely guarded by all parties to avoid its discovery or duplication (forgery) by others.

Slow.

Two-key systems take longer and require more resources to encrypt and decrypt information than one-key systems. To reduce this time requirement, session keys are used, including hybrid systems and key exchanges.

Control of key by users. No requirement for centralized control.

Provides an excellent technical solution for modern communications over the open Internet.

Given today's technological environment, encryption provides a very effective, efficient, and affordable means of retaining privacy in communications and protecting users against electronic theft, fraud, and forgery. As such, it meets the privacy needs of modern communicators, whether over the Internet, satellite, optic fiber, wireless, or other paths of modern communications.

Does public key encrypt or decrypt?

Can you decrypt with a public key RSA?

Why can't you decrypt a public key?

Which key is used for decryption?