```
Questions
(1) Encode the letters $\mathrm{A}$ to $\mathrm{Z}$ as the numbers 11 to 36 , respectively. Set $p=541$, $q=607$ and $a=227$.
(a) Use RSA with public key $(a, p q)$ to encrypt the message consisting of the first two letters of your surname, as recorded in the UOW database.
The two letters yield a single, 4-digit block for encryption, not two 2-digit blocks. For example, if the first two letters of your family name is PA, then the 4-digit block that you need to encrypt is 2611.)
(3 marks)
(b) Compute the private decryption key.
(1 marks)
(c) Decrypt the encrypted message.
(2 marks)
(2) Apply Fermat's factorisation algorithm to the number $n=10595$, gaining a speedup by panning relative to the two moduli 3 and 5 . Be sure to make clear which potential squares in the $a^{2}-n$ sequence need to be examined and which do not. Write down the resulting non-trivial factorisation of $n$. (Just find two non-trivial factors, not all prime factors.)
(5 marks)
(3) Use Pollard's method to find two non-trivial factors of $n=889093$.
(4 marks) (If you cannot find a factor before $k=17$, stop the algorithm.)
```

Sign in to unlock the answer

Answer from Sia

Posted 5 months ago

Solution by Steps

step 1

Convert the first two letters of the surname "Daniel" to numbers using the given encoding: A=11, ..., Z=36

step 2

The letters D and A correspond to the numbers 14 and 11, respectively. Combine them into a 4-digit number for encryption: 1411

step 3

Calculate $n = p \times q = 541 \times 607$

step 4

Use the public key $(a, n)$ to encrypt the message. The encryption function is $c = m^a \mod n$, where $m$ is the message and $c$ is the ciphertext

step 5

Compute $c = 1411^{227} \mod n$ using a modular exponentiation algorithm

Answer

[The encrypted message is the value of $c$ computed in step 5.]

Key Concept

RSA Encryption

Explanation

RSA encryption involves encoding messages as numbers and then using modular exponentiation with a public key to encrypt the message.

Solution by Steps

step 1

Calculate $n = p \times q$ as before

step 2

Compute Euler's totient function $\phi(n) = (p-1)(q-1)$

step 3

Find the private decryption key $d$ such that $d \times a \equiv 1 \mod \phi(n)$. This can be done using the Extended Euclidean Algorithm

Answer

[The private decryption key $d$ is the value computed in step 3.]

Key Concept

RSA Decryption Key

Explanation

The private decryption key in RSA is calculated using the Extended Euclidean Algorithm to find the multiplicative inverse of the public exponent $e$ modulo Euler's totient function $\phi(n)$.

Solution by Steps

step 1

Use the private key $d$ found in the previous solution to decrypt the ciphertext $c$

step 2

The decryption function is $m = c^d \mod n$, where $m$ is the decrypted message

step 3

Compute $m = c^d \mod n$ using a modular exponentiation algorithm

Answer

[The decrypted message is the value of $m$ computed in step 3.]

Key Concept

RSA Decryption

Explanation

RSA decryption involves using the private key to perform modular exponentiation on the ciphertext to retrieve the original message.

Solution by Steps

step 1

Start Fermat's factorization algorithm with $n = 10595$

step 2

Find the smallest integer $a$ such that $a^2 > n$ and $a \equiv 0 \mod 3$ and $a \equiv 0 \mod 5$ to speed up the process

step 3

Check if $a^2 - n$ is a perfect square. If not, increment $a$ by the least common multiple of 3 and 5 (which is 15) and check again

step 4

Once $a^2 - n$ is a perfect square, write $n$ as a difference of two squares $n = a^2 - b^2 = (a+b)(a-b)$ to find the factors

Answer

[The non-trivial factorisation of $n$ is $n = (a+b)(a-b)$ found in step 4.]

Key Concept

Fermat's Factorization

Explanation

Fermat's factorization method is based on representing an odd integer as the difference of two squares, which can then be factored into a product of two non-trivial factors.

Solution by Steps

step 1

Apply Pollard's rho algorithm to $n = 889093$ with a maximum of $k = 17$ iterations

step 2

Choose a random starting value for $x$ and define the function $f(x) = x^2 + 1 \mod n$

step 3

Iterate the function $f$ to generate a sequence of values

step 4

Use the sequence to find the greatest common divisor (gcd) of $|x_i - x_{2i}|$ and $n$ at each iteration. If the gcd is not 1 or $n$, it is a non-trivial factor

step 5

Stop the algorithm if a factor is found or after $k = 17$ iterations

Answer

[The non-trivial factors of $n$ are the gcds found in step 4 that are not 1 or $n$.]

Key Concept

Pollard's Rho Algorithm

Explanation

Pollard's rho algorithm is a probabilistic factorization method that uses a pseudo-random sequence to find a non-trivial factor of a composite number.

Not the question you are looking for? Ask here!

Enter question by text

Enter question by image

Upgrade to Asksia Pro

Join a AskSia's Pro Plan, and get 24/7 AI tutoring for your reviews, assignments, quizzes and exam preps.

Unlimited chat query usages

Strong algorithms that better know you

Early access to new release features

Study Other Question