The University of Sydney
School of Mathematics and Statistics
Assignment 2
MATH1064: Discrete Mathematics for Computation Semester 2, 2023
Lecturers: Christopher Lustri
This individual assignment is due by 11:59pm Thursday 19 October 2023, via
Canvas. Late assignments will receive a penalty of 5% per day until the closing date.
A single PDF copy of your answers must be uploaded in Canvas at https://canvas.
sydney.edu.au/courses/53114. It should include your SID. Please make sure you
review your submission carefully. What you see is exactly how the marker will see your
assignment. Submissions can be overwritten until the due date. To ensure compliance
with our anonymous marking obligations, please do not under any circumstances
include your name in any area of your assignment; only your SID should be present.
The School of Mathematics and Statistics encourages some collaboration between
students when working on problems, but students must write up and submit their
own version of the solutions. If you have technical difficulties with your submission,
see the University of Sydney Canvas Guide, available from the Help section of Canvas.
This assignment is worth 5% of your final assessment for this course. Your answers should be
well written, neat, thoughtful, mathematically concise, and a pleasure to read. Please cite any
resources used and show all working. Present your arguments clearly using words of explanation
and diagrams where relevant. After all, mathematics is about communicating your ideas. This
is a worthwhile skill which takes time and effort to master. The marker will give you feedback
and allocate an overall mark to your assignment using the following criteria:
Copyright © 2023 The University of Sydney 1
In this assignment, you will implement a (very simplified) version of RSA public key cryptog-
raphy. You will create two keys:
• The public key can be made public knowledge. It allows anyone to encode a message that
is intended for your eyes only.
• The private key is information that only you possess. This allows you to decrypt messages
that were encoded using the public key. Without this, the message is incredibly difficult
to decode.
Very Important: You will have to select values for e and d in this assignment. You should
select single-digit values (the primes have been chosen so this is always possible). If you pick
values for either e or d that are larger than this, you will lose marks – you might be right,
but it will be impossible for us to easily check your calculations! In this case, the markers will
be instructed to not continue marking beyond this point.
1. Creating a public key.
(a) Start by selecting two prime numbers, p and q. Typically these prime numbers
would be very large, but we will use smaller primes in order for the mathematics to
be possible using standard computational tools. As such, select one of the following
options:
(p, q) ∈ {(3, 5), (3, 7), (3, 11), (3, 13), (5, 7), (5, 13)}
Calculate the value n = pq.
(b) The Euler totient function ϕ(n) counts the number of positive integers 0 < k < n
such that gcd(k, n) = 1.
(i) Prove that if a positive integer n is the product of two distinct primes p and
q, then ϕ(n) = (p− 1)(q − 1).
(ii) Calculate ϕ(n) for your choice of n in (a).
(c) Select a positive integer e such that e and ϕ(n) are relatively prime.
For the sake of making the calculations easier, you must pick a value of e that is
single-digit.
The ordered pair (e, n) is your public key. You can give this information to anyone and they
can encode a message that you can decode.
2. Creating a private key.
(a) To create the private key, we need one extra positive integer, d. Find a value of d
such that
ed ≡ 1 (modϕ(n)).
Note that e and d are allowed to be the same number (if this condition is satisfied).
For the sake of making the calculations easier, you must pick a value of d that is
single-digit. You might find that your choice for e from Part 1 does not produce a
value of d that is single-digit. In that case, try selecting a different value for e. A
bit of exploration (or coding) should give you a single-digit choice for both e and
d with any of the prime pairs available to you in this assignment.
The ordered pair (d, n) is your private key. You should keep this information to yourself, as it
can be used to decode any message coded using your public key.
2
3. Encoding and decoding a message.
(a) To encode a message using a public key (e, n), we express the message as a number
m. We then calculate the coded message c by finding
c ≡ me (modn), 0 ≤ c < n.
Take the last eight individual digits of your student number, and encode them in
this way. That is, you will choose mi for i = 1, . . . , 8 and produce ci for i = 1, . . . , 8.
Note: Normally, you would not encode individual digits. But this will keep the
numbers in the assignment at a manageable size.
(b) To decode a message c using a private key (d, n), we compute m using the following
equation:
m ≡ cd (modn), 0 ≤ m < n.
Show that your coded values ci from Part (a) decode to recover mi.
Taking the powers of e and d in this step is why we needed to pick small values of e and d. In
practice, there are ways to do this that do not require explicit calculation of large powers, but
we aren’t going to do that here.
4. Encoding and decoding a message for somebody else.
(a) Find a peer whose public key is different to yours (either in person or through the
Ed forum). Exchange public keys with each other.
Note: One person can supply coded messages to multiple people if needed to make
sure everyone has something to decode. We won’t be cross-checking assignments.
(b) Select the last name of a famous scientist or mathematician from history (whose
last name has 5 letters or more). Convert each letter of their last name to a 2-digit
number (ie. A = 1, B = 2, . . . , Z = 26) and encode them using your peer’s public
key. Exchange coded messages with each other.
(c) Use your private key to decode the message that your peer sent to you.
There is a great deal of number theory that makes this method work. If you wish to know
more about it, the textbook contains an explanation of why the message can be encoded and
decoded in this way. We won’t learn about the details in MATH1064, but it is worth reading
about if you are interested in cryptography.