Which of the following numbers are prime? For the ones that aren’t prime, factor them as a product of primes.
101
119
127
The number blablabla
The number
The number
For any positive integer
Calculate
Calculate
For any positive integer
We perform divisions with remainder, starting with dividing
Again, we perform divisions with remainder, starting with
dividing
Find integers
Starting from the Euclidean algorithm work from question 2(b), we
have
Here, we first have to run the Euclidean algorithm on
Given our work in part (b), there is just one more thing to do.
We already know that
Compute the following values of the Euler phi function.
Since
Since
Since
Since
Notice that
Here, we can use the same approach that worked for calculating
There are
Modular arithmetic is good for much more than RSA. If an equation
is true in the integers, we can “reduce it mod
Prove that each of the following equations has no integer solution by
showing each one has no solutions mod
Here, we take the equation and reduce it modulo
For this one, we take the equation and reduce it modulo
For this equation, reducing modulo
Since
In RSA, Nick is not supposed to reveal
Suppose you have a magic machine that takes
Once you know both
What this means is that an efficient way for calculating
If we have the values of
So, if we know
As suggested in the hint, let’s see what the quadratic formula
says about the roots of the polynomial
Like any cryptosystem, the security of RSA can be compromised if
used incorrectly. Suppose Nick and Bahaa have the same value of
Explain how Nick and Bahaa can work out each other’s private keys, and therefore read each other’s encrypted messages.
Suppose Shefaza comes along and sends the same message
Explain how Diana can use this information to recover Shefaza’s
plaintext
Hint: Running the Extended Euclidean algorithm on
Because Nick and Bahaa have both chosen the same value of
As mentioned in the hint for the question, since
At this point, Diana should take the ciphertexts
So, if Diana calculates the unique integer
Remark: There’s a minor point to mention here: we
only talked about what it means to raise numbers to positive exponents
mod