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


α = 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 August 21, 2018, 10:20 am ad1c9bdddf

Solution Preview

See the attached pdf file for properly formatted copy.


1. Statement of the exercise
Exercise 1.1. Decode the following message:"79311601" knowing that the public key
n = 8191 × 65537 = 536813567
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.