{"id":7551,"date":"2024-01-17T17:03:22","date_gmt":"2024-01-17T17:03:22","guid":{"rendered":"https:\/\/www.writemyessays.app\/blog\/questions\/perform-encryption-and-decryption-using-the-rsa-p-3-q-11-e-7-m-5-what-is-the-public-key-pu-what-is-the-private-key-pr-what-is-the-cipertext-c-how-does-the-decryption-to-covert-the-ciphe\/"},"modified":"2024-01-17T17:03:22","modified_gmt":"2024-01-17T17:03:22","slug":"perform-encryption-and-decryption-using-the-rsa-p-3-q-11-e-7-m-5-what-is-the-public-key-pu-what-is-the-private-key-pr-what-is-the-cipertext-c-how-does-the-decryption-to-covert-the-ciphe","status":"publish","type":"questions","link":"https:\/\/www.writemyessays.app\/blog\/questions\/perform-encryption-and-decryption-using-the-rsa-p-3-q-11-e-7-m-5-what-is-the-public-key-pu-what-is-the-private-key-pr-what-is-the-cipertext-c-how-does-the-decryption-to-covert-the-ciphe\/","title":{"rendered":"Perform encryption and decryption using the RSA p = 3; q = 11, e = 7; M = 5 What is the public key PU? What is the private key PR? What is the cipertext C? How does the decryption to covert the ciphertext back to the plaintext M?"},"content":{"rendered":"

The pioneering paper by Diffie and Hellman introduced a new approach to cryptography and, in effect, challenged cryptologists to come up with a cryptographic algorithm that met the requirements for public-key systems. A number of algorithms have been proposed for public-key cryptography. Some of these, though initially promising, turned out to be breakable.<\/p>\n

One of the first successful responses to the challenge was developed in 1977 by Ron Rivest, Adi Shamir, and Len Adleman at MIT and first published in 1978. The Rivest-Shamir-Adleman (RSA) scheme has since that time reigned supreme as the most widely accepted and implemented general-purpose approach to public-key encryption.<\/p>\n

The <\/span>RSA<\/b> <\/span>scheme is a cipher in which the plaintext and ciphertext are integers between 0 and n – 1 for some n. A typical size for n is 1024 bits, or 309 decimal digits. That is, n is less than 21024<\/sup>. We examine RSA in this section in some detail, beginning with an explanation of the algorithm. Then we examine some of the computational and cryptanalytical implications of RSA.<\/p>\n

Description of the Algorithm
<\/b><\/p>\n

RSA makes use of an expression with exponentials. Plaintext is encrypted in blocks, with each block having a binary value less than some number n. That is, the block size must be less than or equal to log2<\/sub>(n)  +  1; in practice, the block size is i bits, where  encryption and decryption are of the following form, for some plaintext block M and ciphertext block C.<\/p>\n

<\/p>\n

C = Me<\/sup><\/i> <\/span>mod <\/span>n<\/i><\/p>\n

M = C <\/span>d<\/sup><\/i> <\/span><\/sup>mod <\/span>n = (Me<\/sup>)d<\/sup><\/i> <\/span>mod <\/span>n = Med<\/sup><\/i> <\/span>mod <\/span>n<\/i><\/p>\n


<\/i><\/p>\n

(mod means to find the remainder. For example 10 mod 5 = 0 because 10 divided by 5 and remainder is 0, while 10 mod 3 = 1 because 10 divided by 3 and the remainder is 1)<\/p>\n

Both sender and receiver must know the value of n. The sender knows the value of e, and only the receiver knows the value of d. Thus, this is a public-key encryption algorithm with a public key of PU  =   {e, n} and a private key of PR   =  {d, n}.For this algorithm to be satisfactory for public-key encryption, the following requirements must be met.<\/p>\n

    \n
  1. It is possible to find values of <\/span>e, d<\/i>, and <\/span>n<\/i> <\/span>such that <\/span>Med<\/sup><\/i> <\/span>mod <\/span>n<\/i>  <\/span>=  M<\/i> <\/span>for all M <  n.<\/li>\n
  2. It is relatively easy to calculate <\/span>Me<\/sup><\/i> <\/span>mod <\/span>n<\/i> <\/span>and <\/span>Cd<\/sup><\/i> <\/span>mod <\/span>n<\/i> <\/span>for all values of M  <  n.<\/li>\n
  3. It is infeasible to determine <\/span>d<\/i> <\/span>given <\/span>e<\/i> <\/span>and <\/span>n<\/i>.<\/li>\n<\/ol>\n

    <\/i><\/p>\n

    For now, we focus on the first requirement and consider the other questions later. We need to find a relationship of the form<\/p>\n

    <\/p>\n

     <\/span>Med<\/sup><\/i> <\/span>mod <\/span><\/span>n = M<\/i><\/p>\n


    <\/i><\/p>\n

    The preceding relationship holds if <\/span>e<\/i> <\/span>and <\/span>d<\/i> <\/span>are multiplicative inverses modulo <\/span>\u03d5(n)<\/i>. For two prime numbers p, q, <\/span>\u03d5(pq)<\/i>   =   (p  –  1)(q  –  1). The relationship between e and d can be expressed as<\/p>\n

    ed<\/i> <\/span>mod <\/span>\u03d5(n)<\/i> <\/span>= 1<\/p>\n

    This is equivalent to saying<\/p>\n

    ed<\/i> <\/span>\u2261 1 mod <\/span>\u03d5(n)<\/i><\/p>\n

    d \u2261 e-1<\/sup><\/i> <\/span>mod <\/span>\u03d5(n)<\/i><\/p>\n

     <\/p>\n

    Figure 4 summarizes the RSA algorithm.<\/p>\n

    An RSA example<\/b><\/p>\n

    For this example, the keys were generated as follows.<\/p>\n

      \n
    1. Select two prime numbers, p  =  17 and q  =  11.<\/li>\n
    2. Calculate n  =  pq  =  17  *  11  =  187.<\/li>\n
    3. Calculate <\/span>\u03d5(n)<\/i>  =  (p  –  1)(q  –  1)  =  16  *  10  =  160.<\/li>\n
    4. Select e such that <\/span>e<\/i> <\/span>is relatively prime to <\/span>\u03d5(n)<\/i>  =   160 and less than <\/span>\u03d5(n)<\/i>; we choose <\/span>e<\/i>  =   7. (the greatest common divider (gcd) between <\/span>e<\/i> <\/span>and <\/span>\u03d5(n)<\/i>  is 1)<\/li>\n
    5. Determine <\/span>d<\/i> <\/span>such that <\/span>de<\/i>  \u2261  1 (mod 160) and d  <  160. The correct value is d  =   23, because 23  *  7  =   161  =   (1  *  160)  +  1;<\/li>\n<\/ol>\n

      The resulting keys are public key PU  =   {7, 187} and private key PR  =   {23, 187}.<\/p>\n

      The example shows the use of these keys for a plaintext input of M  =   88. For encryption, we need to calculate C  =   887<\/sup> <\/span>mod 187. Exploiting the properties of  modular arithmetic, we can do this as follows.<\/p>\n

      887<\/sup> <\/span>mod 187 = [(884<\/sup> <\/span>mod 187) * (882<\/sup> <\/span>mod 187) * (881<\/sup> <\/span>mod 187)] mod 187<\/p>\n

      881<\/sup> <\/span>mod 187 = 88<\/p>\n

      882<\/sup> <\/span>mod 187 = 7744 mod 187 = 77<\/p>\n

      884<\/sup> <\/span>mod 187 = 59,969,536 mod 187 = 132<\/p>\n

      887<\/sup> <\/span>mod 187 = (88 * 77 * 132) mod 187 = 894,432 mod 187 = 11<\/p>\n

       <\/p>\n

      For decryption, we calculate M   =   1123<\/sup> <\/span>mod 187:<\/p>\n

       <\/p>\n

      1123<\/sup> <\/span>mod 187 = [(111<\/sup> <\/span>mod 187) * (112<\/sup> <\/span>mod 187) * (114<\/sup> <\/span>mod 187)<\/p>\n

             * (118<\/sup> <\/span>mod 187) * (118<\/sup> <\/span>mod 187)] mod 187<\/p>\n

      111<\/sup> <\/span>mod 187 = 11<\/p>\n

      112<\/sup> <\/span>mod 187 = 121<\/p>\n

      114<\/sup> <\/span>mod 187 = 14,641 mod 187 = 55<\/p>\n

      118<\/sup> <\/span>mod 187 = 214,358,881 mod 187 = 33<\/p>\n

      1123<\/sup> <\/span>mod 187 = (11 * 121 * 55 * 33 * 33) mod 187<\/p>\n

            = 79,720,245 mod 187 = 88<\/p>\n

      The Security of RSA<\/b><\/p>\n

      Five possible approaches to attacking the RSA algorithm are<\/p>\n