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

© BrainMass Inc. brainmass.com March 5, 2021, 1:32 am ad1c9bdddfhttps://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), deﬁned 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 ﬁnds 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.