# 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 October 17, 2018, 12:58 pm 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.

Advances in Encryption

What are some of the advances in encryption in the last few years?

View Full Posting Details