Share
Explore BrainMass

Public Key Cryptography System

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

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