Public Key Cryptography System

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 ...