Math Problem Statement

Alice wants to send a plaintext message π‘š = 13 to Bob secretly using RSA public key cryptosystem. Bob selects 𝑝 = 13, and π‘ž = 11 with 𝑒 = 13. You have to perform following tasks: a. Compute and list Bob’s public and private keys. b. Compute the ciphertext that Alice will send to Bob using plaintext message π‘š = 13. c. Recover the actual plaintext from the ciphertext sent by Alice.

Solution

Let's walk through the steps to solve the problem using RSA public key cryptosystem.

a. Compute Bob’s public and private keys

  1. Choose the prime numbers:

    • p=13p = 13
    • q=11q = 11
  2. Compute nn (the product of pp and qq): n=pΓ—q=13Γ—11=143n = p \times q = 13 \times 11 = 143

  3. Compute Ο•(n)\phi(n) (Euler’s totient function): Ο•(n)=(pβˆ’1)(qβˆ’1)=(13βˆ’1)(11βˆ’1)=12Γ—10=120\phi(n) = (p - 1)(q - 1) = (13 - 1)(11 - 1) = 12 \times 10 = 120

  4. Public exponent ee:

    • Given e=13e = 13, and it needs to satisfy gcd⁑(e,Ο•(n))=1\gcd(e, \phi(n)) = 1.
    • Since gcd⁑(13,120)=1\gcd(13, 120) = 1, 13 is valid.
  5. Private key dd:

    • To find dd, we need the modular inverse of ee modulo Ο•(n)\phi(n), i.e., d≑eβˆ’1mod  ϕ(n)d \equiv e^{-1} \mod \phi(n).

    Using the Extended Euclidean Algorithm, we solve for dd: 13d≑1mod  12013d \equiv 1 \mod 120 The solution is d=37d = 37 (since 13Γ—37=481≑1mod  12013 \times 37 = 481 \equiv 1 \mod 120).

    So, Bob's private key is d=37d = 37.

  • Bob's public key: (e,n)=(13,143)(e, n) = (13, 143)
  • Bob's private key: (d,n)=(37,143)(d, n) = (37, 143)

b. Compute the ciphertext that Alice will send to Bob using plaintext m=13m = 13

  1. Plaintext: m=13m = 13

  2. Ciphertext is calculated using the formula c≑memod  nc \equiv m^e \mod n: c≑1313mod  143c \equiv 13^{13} \mod 143 We can compute 1313mod  14313^{13} \mod 143 step by step using modular exponentiation:

    • 132mod  143=169mod  143=2613^2 \mod 143 = 169 \mod 143 = 26
    • 134mod  143=(132)2mod  143=262mod  143=676mod  143=9413^4 \mod 143 = (13^2)^2 \mod 143 = 26^2 \mod 143 = 676 \mod 143 = 94
    • 138mod  143=(134)2mod  143=942mod  143=8836mod  143=11313^8 \mod 143 = (13^4)^2 \mod 143 = 94^2 \mod 143 = 8836 \mod 143 = 113

    Then: 1313=138Γ—134Γ—13mod  143=113Γ—94Γ—13mod  14313^{13} = 13^8 \times 13^4 \times 13 \mod 143 = 113 \times 94 \times 13 \mod 143 First, 113Γ—94=10622mod  143=49113 \times 94 = 10622 \mod 143 = 49. Now compute: 49Γ—13=637mod  143=6549 \times 13 = 637 \mod 143 = 65 So, the ciphertext is c=65c = 65.

c. Recover the actual plaintext from the ciphertext sent by Alice

To decrypt the ciphertext, we use Bob's private key d=37d = 37 and compute: m≑cdmod  nm \equiv c^d \mod n That is: m≑6537mod  143m \equiv 65^{37} \mod 143 We will use modular exponentiation to compute this efficiently:

  • 652mod  143=4225mod  143=8065^2 \mod 143 = 4225 \mod 143 = 80
  • 654mod  143=(652)2mod  143=802mod  143=6400mod  143=10165^4 \mod 143 = (65^2)^2 \mod 143 = 80^2 \mod 143 = 6400 \mod 143 = 101
  • 658mod  143=(654)2mod  143=1012mod  143=10201mod  143=3565^8 \mod 143 = (65^4)^2 \mod 143 = 101^2 \mod 143 = 10201 \mod 143 = 35
  • 6516mod  143=(658)2mod  143=352mod  143=1225mod  143=8365^{16} \mod 143 = (65^8)^2 \mod 143 = 35^2 \mod 143 = 1225 \mod 143 = 83
  • 6532mod  143=(6516)2mod  143=832mod  143=6889mod  143=3165^{32} \mod 143 = (65^{16})^2 \mod 143 = 83^2 \mod 143 = 6889 \mod 143 = 31

Now we can combine these powers of 65: 6537=6532Γ—654Γ—65mod  143=31Γ—101Γ—65mod  14365^{37} = 65^{32} \times 65^4 \times 65 \mod 143 = 31 \times 101 \times 65 \mod 143 First, compute 31Γ—101=3131mod  143=13731 \times 101 = 3131 \mod 143 = 137, and then: 137Γ—65=8905mod  143=13137 \times 65 = 8905 \mod 143 = 13

So, the recovered plaintext is m=13m = 13.

Summary of Results:

  • Public key: (e=13,n=143)(e = 13, n = 143)
  • Private key: (d=37,n=143)(d = 37, n = 143)
  • Ciphertext: 6565
  • Recovered plaintext: 1313

Do you need further details or have any questions?


Here are 5 related questions to extend your understanding:

  1. What would happen if gcd⁑(e,Ο•(n))β‰ 1\gcd(e, \phi(n)) \neq 1?
  2. How would the encryption process differ with larger prime numbers for pp and qq?
  3. Can RSA encryption be applied to larger messages, and if so, how?
  4. How does the Extended Euclidean Algorithm find the modular inverse in RSA?
  5. What are potential weaknesses in the RSA algorithm, and how can they be mitigated?

Tip: In RSA, choosing large prime numbers makes the encryption more secure, as factoring large numbers becomes more difficult.

Ask a new question for Free

By Image

Drop file here or Click Here to upload

Math Problem Analysis

Mathematical Concepts

Number Theory
Modular Arithmetic
RSA Cryptography
Prime Numbers
Euler's Totient Function
Extended Euclidean Algorithm

Formulas

n = p * q
Ο•(n) = (p - 1)(q - 1)
c ≑ m^e mod n
m ≑ c^d mod n
d ≑ e^(-1) mod Ο•(n)

Theorems

Euler's Totient Function
Modular Inversion
RSA Algorithm

Suitable Grade Level

University Level (Cryptography Course)