Cryptography, Information Theory, and Error-Correction. Aiden A. Bruen

is an open‐source (free) alternative standard for digitally signing and encrypting e‐mail. The most common implementation of OpenPGP is GPG, which stands for GNU Privacy Guard.

      PGP and GPG are very similar in their uses and operation, but differ in the algorithms that they use. They both use algorithms such as RSA or Elliptic Curve cryptography (ECC) for asymmetric encryption but PGP uses patented symmetric encryption algorithms, while GPG uses public domain (free) algorithms.

      Both programs may be used for encrypting/decrypting e‐mail and signing/authenticating messages.

      Before using PGP or GPG, a user generates their own public key and private key pair. Then, the public key must be published so that others may access it. This may be done by putting it out on a website, sending out mass emails announcing the public key, or placing it on a key server and associating it to an e‐mail address.

      Encrypting/decrypting

      To send an encrypted message, the user decides on a symmetric algorithm and then the computer will generate a random key for use with this message. The message is encrypted using this key, and the key is encrypted using the intended recipient's public key. Both the message and the encrypted key are sent by e‐mail to the intended recipient. If the e‐mail is intercepted in this form, the eavesdropper shouldn't be able to read the contents, because they don't possess the proper private key to decode the session key, nor do they possess the session key to decode the message.

Upon receipt of an encrypted e‐mail, the user's computer will use his/her private key to decrypt the enclosed session key, and then will use the session key to decode the message. In many modern e‐mail programs that support PGP or GPG, this is done without the user knowing. That way, the user isn't inconvenienced by the added security, but will still enjoy the benefits of encrypted e‐mail.

      Note that symmetric encryption is used for the actual message and asymmetric encryption is used for the key exchange. This is because symmetric cryptography is about 4000 times faster than asymmetric. That means that sending a large e‐mail with large attachments would take quite some time to encrypt if you only used RSA.

      Signing/authenticating

      Just as the encryption algorithm for PGP and GPG are very similar to TLS, so is the authentication mechanism. A hash of the e‐mail message is encrypted with the user's private key, and then appended to the end of the message. Then when the e‐mail is received, the user's computer may decrypt this message with the sender's public key and check that the hash corresponds to the hash of the current message. This procedure may serve two purposes. It authenticates the original message sender (the person in possession of the private key used to encrypt the message hash), and it almost guarantees that the message wasn't altered since its signing since, with a strong enough hashing algorithm, it is highly unlikely that two messages hash to the same value.

      For more information on the encryption of e‐mail, see “Trustworthy Email” by Rose et al., [RNGC19].

3.11 Problems

      Notation In some of the problems/solutions below, we used the notation introduced in this chapter. Recall that just means the remainder when is divided by . For example, . Later on, in Chapter 19 we will also use the equivalent or mod notation.

      Some of these problems need background material and may be skipped on a first reading.

      1 3.1 An essential property. In a cryptographic system suppose messages are encrypted, resulting in cipher texts . If , must ? (See Solution 3.1.)

      2 3.2 In the RSA algorithm suppose that , and . Must (See Solution 3.2.)Repeated squaring

      3 3.3 Using the repeated squaring method, find the remainder when is divided by 97. (See Solution 3.3.)

      4 3.4 Using the repeated squaring method, find the remainder when is divided by 167. (See Solution 3.4.)RSA encryption

      5 3.5 Using the RSA algorithm, given the cipher text with , can there be more than one decryption index such that ? (See Solution 3.5.)

      6 3.6 In the RSA algorithm, we assume that are large primes which must be unequal. Why is it that must be unequal? (See Solution 3.6.)

      7 3.7 Show that for security reasons in the RSA algorithm, and should not be chosen too close together. (See Solution 3.7.)

      8 3.8 In the RSA algorithm, why must we choose to be relatively prime to ? (See Solution 3.8.)

      9 3.9 In the RSA algorithm, show that must be odd. (See Solution 3.9.)

      10 3.10 In the RSA algorithm, the restriction is sometimes made – even in textbooks – that . Is this restriction necessary? (See Solution 3.10.)

      11 3.11 Suppose an eavesdropper Eve knows and also .⁴ Show that Eve can then find and . (See Solution 3.11.)Calculations using RSA (The Euclidean Algorithm of Chapter 19 can be used)

      12 3.12 Find an RSA decryption exponent given that , and , using both methods as described in the text. (See Solution 3.12.)

      13 3.13 Repeat the previous problem with , and . (See Solution 3.13.)

      14 3.14 Find an RSA decryption exponent , given that and . (See Solution 3.14.)

      15 3.15 Let so and . Let . Suppose . Find the cipher text . (See Solution 3.15.)

      16 3.16 Let be as in the previous question. Suppose . What is ? (See Solution 3.16.)

      17 3.17 Find all possible values of for . What is a compact formula for this quantity in general? (See Solution 3.17.)Sending text messages with RSA

      18 3.18 Suppose Alice wishes to send a text message to Bob using the RSA algorithm. Bob's public key is the pair . Note that . Alice encodes the 26 letters of the English alphabet by putting . Alice transmits the message in blocks. Each block corresponds to two letters which are encoded into their numerical equivalents. For example the pair becomes the block which then gets enciphered to , since the block corresponds to the decimal number 405. Now suppose Bob receives the cipher text 0300. What was the message transmitted by Alice? (See Solution 3.18.)

      19 3.19 In the above problem, why can't we put more than 2 letters in a block? (See Solution 3.19.)

      20 3.20 Are the text messages that are sent in this way secure? (See Solution 3.20.)Elementary attacks, pitfalls and incorrect implementations of RSASmall message, small exponent

      21 3.21 Show that if the message is a small integer and the enciphering index is a small integer, then RSA is not secure. (See Solution 3.21.)

      22 3.22 For , decrypt assuming that is “small.” (See Solution 3.22.)

      23 3.23 Can you think of a real‐world example of enciphering a small integer where the attack of Problem 3.22 might cause difficulties? (See Solution 3.23.)

      24 3.24