Explore BrainMass
Share

Explore BrainMass

    Public Key Cryptography System

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Exercise 3 . (3 marks) Decode the following message: "79311601" knowing that the public key is

    n = 8191 x 65537 = 536813567

    and

    α = 7582663

    (I used the correspondence A<-> 01, B <-> 02, ... , Z <-> 26, 0 <-> 30, 9 <-> 39 and worked in base 41 to encode this message.)

    © BrainMass Inc. brainmass.com October 10, 2019, 7:50 am ad1c9bdddf
    https://brainmass.com/math/number-theory/public-key-cryptography-system-597257

    Solution Preview

    See the attached pdf file for properly formatted copy.

    PUBLIC KEY CRYPTOGRAPHY SYSTEM
    WWW.BRAINMASS.COM

    1. Statement of the exercise
    Exercise 1.1. Decode the following message:"79311601" knowing that the public key
    is
    n = 8191 × 65537 = 536813567
    and
    a = 7582663
    (I used the correspondence A ↔ 01, B ↔ 02,...,Z ↔ 26, 0 ↔ 30,...,9 ↔ 39 and
    worked in base 41 to encode this message)

    2. RSA in brief
    We are dealing here with RSA cryptography system. In brief the RSA cryptography
    system is as follows: there is the "receiver" and the "sender". It is setup by the receiver
    of the messages:
    (1) The receiver chooses two large primes p and q and calculates n = pq. In our
    case p = 8191, q = 65537 and n = 8191×65537 = 536813567. The number n is
    the "public key".
    (2) The receiver calculates the Euler function ϕ(n), defined as the number of integers
    in {1,2,...,n−1} that are relatively prime to n. In the case of a number of the
    form n = pq with p,q primes we have ϕ(n) = (p− 1)(q − 1).
    (3) Choosing the encryption key. The receiver chooses a ∈ {1,2,...n − 1}
    relatively prime to ϕ(n). The number a is the "encryption key". This number
    is used by the sender to encode the message.
    (4) Constructing the decryption key. To construct the decryption key the re-
    ceiver finds the number d ∈ {1,2,...,n−1} such that ad ≡ 1 (mod ϕ(n)). This
    number d is the "decryption key" and can be constructed by going backwards
    in the Euclid's algorithm.
    (5) Encrypting a message. Now the sender wants to send a message that consists
    of a number m ∈ {1,...,n− 1} that is relatively ...

    Solution Summary

    After a brief explanation of the public key cryptography system we give a detailed explanation of how to decode a given message. We calculate the Euler function, use Euclid's algorithm to find the decryption key and explain how to perform the multiplications modulo the public key number.

    $2.19