Explore BrainMass

Public Key Cryptography System

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

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

Similar Posting

Advances in Encryption

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

View Full Posting Details