Discrete Math Quiz: Rsa And Public Key Cryptography

20 questions · exam conditions

0:00

Rsa And Public Key CryptographyQuestion 1 of 20

In an RSA system, Charlie chooses primes $p = 11$ and $q = 13$ , giving $n = 143$ . He selects public exponent $e = 7$ . When Charlie tries to encrypt the message $m = 22$ , what is the primary issue he encounters?

The encryption succeeds normally since

\gcd(22, 143) = 11 > 1

but RSA handles this case

The message cannot be encrypted because

\gcd(22, 143) = 11 \neq 1

, violating RSA requirements

The public exponent

e = 7

is invalid because

\gcd(7, 120) \neq 1

The encryption produces an ambiguous result since

22 > \sqrt{143}

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Rsa And Public Key Cryptography

Practice Rsa And Public Key Cryptography in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Rsa And Public Key Cryptography, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

The encryption succeeds normally since $\gcd(22, 143) = 11 > 1$ but RSA handles this case
The message cannot be encrypted because $\gcd(22, 143) = 11 \neq 1$ , violating RSA requirements (correct answer)
The public exponent $e = 7$ is invalid because $\gcd(7, 120) \neq 1$
The encryption produces an ambiguous result since $22 > \sqrt{143}$

Explanation: For RSA to work properly, the message must be coprime to the modulus. Here

\gcd(22, 143) = \gcd(22, 11 \times 13) = 11 \neq 1

because 22 = 2 × 11. This violates the fundamental requirement that messages be in the multiplicative group

\mathbb{Z}_n^*

. Choice A incorrectly suggests RSA handles non-coprime messages. Choice C is wrong because

\gcd(7, 120) = 1

. Choice D mentions an irrelevant condition about message size relative to

\sqrt{n}

Question 2

Alice generates an RSA key pair with modulus $n = 77$ and public exponent $e = 13$ . Bob encrypts the message $m = 5$ using Alice's public key. If Bob's encrypted message is $c \equiv 26 \pmod{77}$ , what happens when Alice attempts to decrypt using her private key $d = 37$ ?

Alice successfully recovers the original message $m = 5$ (correct answer)
Alice gets $m = 12$ due to an error in the private key calculation
Alice gets $m = 31$ because the modulus is not properly formed
The decryption fails because $\gcd(5, 77) \neq 1$ violates RSA requirements

Explanation: To verify:

c^d \equiv 26^{37} \pmod{77}

. Since

n = 77 = 7 \times 11

, we have

\phi(77) = 6 \times 10 = 60

. We can verify

ed \equiv 13 \times 37 \equiv 481 \equiv 1 \pmod{60}

. Computing

26^{37} \pmod{77}

using Euler's theorem and modular exponentiation yields 5. Choice B reflects a common error in computing the private key. Choice C suggests confusion about proper RSA modulus formation. Choice D incorrectly identifies a problem with the message - since

\gcd(5, 77) = 1

, this is valid.

Question 3

Jack implements RSA with $n = 91 = 7 \times 13$ and accidentally reveals that his private exponent is $d = 61$ . An adversary who intercepts this information wants to determine Jack's public exponent $e$ . What is the most efficient approach?

Apply the extended Euclidean algorithm to solve $61e ≡ 1 \pmod{91}$
Use the relation $ed - 1 = k\phi(91)$ to find $k$ , then verify by factoring
Test small values of $e$ until finding one where $ed ≡ 1 \pmod{91}$
Factor $n = 91$ first, then solve $ed ≡ 1 \pmod{\phi(91)}$ directly (correct answer)

Explanation: When you encounter RSA problems involving finding one exponent given the other, you need to understand the fundamental relationship:

ed \equiv 1 \pmod{\phi(n)}

, where

\phi(n)

is Euler's totient function. The most efficient approach is D because it follows the logical sequence RSA requires. First, you factor

n = 91 = 7 \times 13

. Then you calculate

\phi(91) = (7-1)(13-1) = 6 \times 12 = 72

. Finally, you solve

61e \equiv 1 \pmod{72}

using the extended Euclidean algorithm to find

e

. A is incorrect because it uses the wrong modulus. The equation

61e \equiv 1 \pmod{91}

is mathematically wrong—RSA requires the modulus to be

\phi(n)

, not

n

itself. B reverses the logical order inefficiently. While

ed - 1 = k\phi(91)

is mathematically correct, you'd still need to know

\phi(91)

first, which requires factoring

n

. The "verify by factoring" step should come first, not last. C is computationally wasteful. Testing small values might work for tiny examples like this, but it doesn't scale and ignores the mathematical structure that makes RSA work. You'd be guessing rather than calculating. Strategy tip: In RSA problems, always remember that the exponents are related through

\phi(n)

, not

n

. When you need to find

\phi(n)

and

n

is composite, factoring

n

is your essential first step. This pattern appears frequently in cryptography problems.

Question 4

Paula implements a simplified RSA variant where she uses $n = 15 = 3 \times 5$ , $e = 7$ , and computes $d = 3$ (since $7 \times 3 = 21 ≡ 1 \pmod{8}$ where $\phi(15) = 8$ ). When she encrypts $m = 2$ , she gets $c = 2^7 \bmod 15 = 8$ . However, when she tries to decrypt $c = 8$ , what result does she obtain?

$m = 8^3 \bmod 15 = 17 \bmod 15 = 2$ , recovering the message after proper modular reduction
$m = 8^3 \bmod 15 = 8$ , indicating the encryption is its own inverse
$m = 8^3 \bmod 15 = 14$ , showing that decryption failed due to small modulus size
$m = 8^3 \bmod 15 = 2$ , successfully recovering the original message (correct answer)

Explanation: RSA encryption relies on modular exponentiation, where encryption uses the public key

(n, e)

and decryption uses the private key

(n, d)

. The fundamental property is that

m^{ed} \equiv m \pmod{n}

when

ed \equiv 1 \pmod{\phi(n)}

. To decrypt the ciphertext

c = 8

, you compute

8^3 \bmod 15

. Let's calculate this step by step:

8^2 = 64 \equiv 4 \pmod{15}

(since

64 = 4 \times 15 + 4

)

8^3 = 8 \times 8^2 = 8 \times 4 = 32 \equiv 2 \pmod{15}

(since

32 = 2 \times 15 + 2

) The decryption successfully recovers the original message

m = 2

, confirming that choice D is correct. Choice A contains a calculation error, claiming

8^3 = 17

, which is mathematically impossible since

8^3 = 512

, not 17. Choice B incorrectly states that

8^3 \equiv 8 \pmod{15}

, suggesting encryption is its own inverse, but our calculation shows

8^3 \equiv 2

, not 8. Choice C gives the wrong result of 14 and incorrectly attributes this to the small modulus size, when in fact RSA works correctly even with small parameters like

n = 15

. Study tip: When solving RSA problems, always verify that

ed \equiv 1 \pmod{\phi(n)}

first, then carefully compute modular exponentiation step by step. Small examples like this help you understand the mechanics before tackling larger, real-world RSA parameters.

Question 5

Henry implements a variant where he uses $n = 35 = 5 \times 7$ but mistakenly chooses $e = 6$ as his public exponent. When he tries to compute the corresponding private exponent $d$ , what problem does he encounter?

No integer $d$ satisfies $6d ≡ 1 \pmod{24}$ since $\gcd(6, 24) = 6 ≠ 1$ (correct answer)
The equation $6d ≡ 1 \pmod{35}$ has no solution since $6$ is even
Multiple values of $d$ satisfy the congruence, creating key ambiguity
The computed $d = 6$ creates a degenerate case where encryption equals decryption

Explanation: For RSA to work, we need

\gcd(e, \phi(n)) = 1

. Here

\phi(35) = \phi(5 \times 7) = 4 \times 6 = 24

, and

\gcd(6, 24) = 6 ≠ 1

. Therefore, the modular inverse of

6

modulo

24

doesn't exist, and no private exponent

d

can be computed. Choice B uses the wrong modulus (

n

instead of

\phi(n)

). Choice C is incorrect because when a modular inverse doesn't exist, there are zero solutions, not multiple. Choice D assumes

d = e

, which isn't generally true and doesn't address the fundamental issue.

Question 6

In the RSA cryptosystem, Alice chooses primes $p = 7$ and $q = 11$ , computes $n = pq = 77$ , and selects $e = 13$ as her public exponent. When Bob encrypts the message $m = 5$ using Alice's public key, what is the resulting ciphertext $c$ ?

$c = 26$ (correct answer)
$c = 47$
$c = 31$
$c = 64$

Explanation: To encrypt, Bob computes

c ≡ m^e \pmod{n} ≡ 5^{13} \pmod{77}

. Using repeated squaring:

5^1 = 5

5^2 = 25

5^4 = 625 ≡ 9 \pmod{77}

5^8 = 81 ≡ 4 \pmod{77}

. Since

13 = 8 + 4 + 1

, we have

5^{13} ≡ 4 \times 9 \times 5 = 180 ≡ 26 \pmod{77}

. Choice B results from computing

5^{11} \pmod{77}

(using

\phi(n)

instead of

e

). Choice C comes from

5^{13} \pmod{60}

(using

\phi(n)

as modulus). Choice D is

5^6 \pmod{77}

(arithmetic error in exponent).

Question 7

Oscar uses RSA with $n = 143 = 11 \times 13$ and $e = 7$ . He wants to encrypt the message $m = 12$ but first checks whether this creates any security vulnerabilities. What should be his primary concern?

The message $m = 12$ shares a common factor with $n = 143$ , making encryption impossible
Since $\gcd(12, 143) = 11 ≠ 1$ , the encrypted message may leak information about the factorization (correct answer)
The value $m = 12$ is too close to $\sqrt{n} ≈ 12$ , creating mathematical instabilities
No security concern exists since $12 < 143$ and standard RSA encryption will proceed normally

Explanation: Since

\gcd(12, 143) = \gcd(12, 11 \times 13) = 11 ≠ 1

, the message shares a factor with

n

. This is problematic because: (1) anyone computing

\gcd(m, n)

learns a factor of

n

, and (2) the RSA decryption may not work correctly since the mathematical foundations assume

\gcd(m, n) = 1

. Choice A is wrong because encryption is still mathematically possible. Choice C incorrectly focuses on the magnitude rather than the GCD issue. Choice D ignores the fundamental security vulnerability.

Question 8

In a simplified RSA scenario, Eve intercepts Alice's public key $(n, e) = (21, 5)$ and wants to factor $n$ to break the system. After successfully finding $p = 3$ and $q = 7$ , what private exponent $d$ should Eve compute to decrypt Alice's messages?

$d = 5$ because the private key equals the public exponent
$d = 17$ since $5 \times 17 ≡ 1 \pmod{21}$
$d = 5$ since $5 \times 5 ≡ 1 \pmod{12}$
$d = 17$ since $5 \times 17 ≡ 1 \pmod{12}$ (correct answer)

Explanation: The private exponent

d

satisfies

ed ≡ 1 \pmod{\phi(n)}

. With

p = 3

and

q = 7

, we have

\phi(n) = \phi(21) = (3-1)(7-1) = 12

. We need

5d ≡ 1 \pmod{12}

. Testing:

5 \times 17 = 85 = 7 \times 12 + 1 ≡ 1 \pmod{12}

, so

d = 17

. Choice A incorrectly assumes

d = e

. Choice B computes the congruence modulo

n

instead of

\phi(n)

. Choice C has the wrong value of

d

since

5 \times 5 = 25 ≡ 1 \pmod{12}

is false (

25 = 2 \times 12 + 1

but we need

25 \equiv 1

, which gives

25 \bmod 12 = 1

, but this doesn't help since we need

5 \times 5 \bmod 12 = 1

, and

25 \bmod 12 = 1

is true, making this explanation confusing - the real issue is

d=5

is wrong).

Question 9

Grace generates RSA keys using $p = 11$ and $q = 13$ . She chooses $e = 7$ and correctly computes $d = 103$ . However, she accidentally uses $d' = 23$ (which is $d \bmod 120$ ) as her private exponent. What happens when she attempts to decrypt a ciphertext $c = 50$ ?

Decryption succeeds normally since $d' ≡ d \pmod{\phi(n)}$ and $\phi(143) = 120$ (correct answer)
Decryption fails because $d'$ doesn't satisfy $ed' ≡ 1 \pmod{\phi(n)}$ properly
Decryption produces a different but mathematically valid result due to modular arithmetic
Decryption succeeds by coincidence since $23 < 143$ satisfies the RSA constraint

Explanation: Since

\phi(143) = \phi(11 \times 13) = 10 \times 12 = 120

, and

d' = 23 ≡ 103 \pmod{120}

, we have

d' ≡ d \pmod{\phi(n)}

. The RSA decryption formula

c^d \pmod{n}

depends only on

d \bmod \phi(n)

, so using

d' = 23

instead of

d = 103

produces identical results. Choice B incorrectly assumes the reduction changes the mathematical relationship. Choice C suggests a wrong answer would result. Choice D misunderstands why the decryption works.

Question 10

Frank implements RSA with $p = 13$ , $q = 17$ , and $e = 5$ . He receives two ciphertexts: $c_1 = 100$ (encrypting $m_1$ ) and $c_2 = 150$ (encrypting $m_2$ ). If Frank wants to decrypt the product $m_1 \cdot m_2$ without individually decrypting $c_1$ and $c_2$ , what ciphertext should he decrypt?

$c_1 + c_2 = 250$ due to RSA's additive homomorphic property
$c_1 \cdot c_2 = 15000$ due to RSA's multiplicative homomorphic property
$c_1 \cdot c_2 \bmod 221 = 136$ using the multiplicative property with proper reduction (correct answer)
$c_1^{c_2} \bmod 221 = 45$ using RSA's exponential composition property

Explanation: RSA has the multiplicative homomorphic property: if

c_1 ≡ m_1^e \pmod{n}

and

c_2 ≡ m_2^e \pmod{n}

, then

c_1 \cdot c_2 ≡ (m_1 \cdot m_2)^e \pmod{n}

. So decrypting

c_1 \cdot c_2 \pmod{n}

gives

m_1 \cdot m_2

. Here

n = 13 \times 17 = 221

, so we need

100 \times 150 \bmod 221 = 15000 \bmod 221 = 136

. Choice A incorrectly assumes additive homomorphism. Choice B forgets to reduce modulo

n

. Choice D invents a non-existent exponential property.

Question 11

In a public-key infrastructure, three users have the following RSA public keys: Alice $(n_A, e_A) = (33, 3)$ , Bob $(n_B, e_B) = (55, 3)$ , and Carol $(n_C, e_C) = (77, 3)$ . If they all use the same public exponent $e = 3$ and someone broadcasts the same message $m$ to all three, what vulnerability might this create?

The identical exponents allow direct factorization of all moduli using Fermat's method
An attacker can use the Chinese Remainder Theorem to recover $m^3$ and then find $m$ (correct answer)
The shared exponent creates a common factor between the moduli, compromising security
Multiple encryptions with $e = 3$ enable a meet-in-the-middle attack on the message

Explanation: This describes Håstad's broadcast attack. With the same message

m

encrypted to three users with

e = 3

, an attacker obtains

c_1 ≡ m^3 \pmod{33}

c_2 ≡ m^3 \pmod{55}

, and

c_3 ≡ m^3 \pmod{77}

. Since

\gcd(33,55) = \gcd(33,77) = \gcd(55,77) = 1

and

33 \times 55 \times 77 > m^3

for typical message sizes, the Chinese Remainder Theorem can recover

m^3

, and then

m = \sqrt[3]{m^3}

. Choice A incorrectly focuses on factorization. Choice C wrongly suggests the moduli share factors (they don't). Choice D invents a non-applicable attack method.

Question 12

In an RSA digital signature scheme, Alice signs a message hash $h = 42$ using her private key with $n = 77$ , $d = 37$ . The resulting signature is $s = 49$ . When Bob verifies this signature using Alice's public key $(n, e) = (77, 13)$ , what value should he obtain?

Bob computes $s^e \bmod n = 49^{13} \bmod 77 = 42$ , matching the original hash (correct answer)
Bob computes $s^e \bmod n = 49^{13} \bmod 77 = 49$ , confirming signature validity
Bob computes $h^e \bmod n = 42^{13} \bmod 77 = 49$ , verifying against the signature
Bob computes $s \cdot e \bmod n = 49 \cdot 13 \bmod 77 = 21$ , recovering the hash

Explanation: In RSA signatures, Alice computes

s ≡ h^d \pmod{n}

, and Bob verifies by checking that

s^e ≡ h \pmod{n}

. Here, Bob computes

49^{13} \bmod 77

. Using repeated squaring:

49^1 = 49

49^2 ≡ 35

49^4 ≡ 42

49^8 ≡ 21

. Since

13 = 8 + 4 + 1

, we get

49^{13} ≡ 21 \times 42 \times 49 ≡ 42 \pmod{77}

, which equals the original hash. Choice B suggests the result should equal the signature itself. Choice C reverses the verification process. Choice D uses multiplication instead of exponentiation.

Question 13

In RSA key generation, Charlie selects $p = 17$ and $q = 19$ . He correctly computes $n = 323$ and $\phi(n) = 288$ . Which of the following values would be a valid choice for his public exponent $e$ ?

$e = 144$ because it divides $\phi(n)$ evenly
$e = 17$ because it equals one of the chosen primes
$e = 25$ because $\gcd(25, 288) = 1$ and $25 < 288$ (correct answer)
$e = 289$ because it is greater than $\phi(n)$

Explanation: For RSA, the public exponent

e

must satisfy

\gcd(e, \phi(n)) = 1

and

1 < e < \phi(n)

. Since

\phi(n) = 288 = 2^5 \times 3^2

and

25 = 5^2

, we have

\gcd(25, 288) = 1

, making

e = 25

valid. Choice A is wrong because

e

must be coprime to

\phi(n)

, not divisible by it (

\gcd(144, 288) = 144 ≠ 1

). Choice B fails because

e = p

means

\gcd(17, 288) = 1

but using a prime factor creates security vulnerabilities. Choice D violates the requirement

e < \phi(n)

Question 14

Eve intercepts an RSA ciphertext $c = 8$ sent to a recipient with public key $(n, e) = (15, 7)$ . She also discovers that the original message $m$ satisfied $m^2 \equiv 4 \pmod{15}$ . What can Eve conclude about the message?

The message is uniquely determined as $m = 2$ since $2^2 \equiv 4 \pmod{15}$
The message cannot be determined because $\gcd(4, 15) \neq 1$ makes the constraint invalid
The message must be $m = 8$ since it matches the ciphertext value
The message could be $m = 2$ or $m = 13$ , but additional information is needed (correct answer)

Explanation: When you encounter an RSA problem with additional constraints on the message, you need to find all possible values that satisfy both the constraint and the RSA encryption relationship, then determine what information remains ambiguous. First, let's find all solutions to

m^2 \equiv 4 \pmod{15}

. Since

15 = 3 \times 5

, we can use the Chinese Remainder Theorem by solving:

$m^2 \equiv 4 \equiv 1 \pmod{3}$ , which gives $m \equiv 1$ or $2 \pmod{3}$
$m^2 \equiv 4 \pmod{5}$ , which gives $m \equiv 2$ or $3 \pmod{5}$

Combining these using CRT, we get four solutions:

m \equiv 2, 8, 7, 13 \pmod{15}

. However, we can verify that only

m = 2

and

m = 13

actually satisfy

m^2 \equiv 4 \pmod{15}

(since

2^2 = 4

and

13^2 = 169 \equiv 4 \pmod{15}

). Now, both candidates must also satisfy the RSA encryption:

m^7 \equiv 8 \pmod{15}

. You can verify that both

2^7 \equiv 8 \pmod{15}

and

13^7 \equiv 8 \pmod{15}

, so both are valid. Answer A is wrong because

m = 13

is also a valid solution. Answer B is incorrect because

\gcd(4,15) = 1

(4 and 15 share no common factors), making the constraint perfectly valid. Answer C confuses the ciphertext value with the plaintext message—these are related by exponentiation, not equality. Key takeaway: In modular arithmetic problems, always check for multiple solutions, especially when working with composite moduli. Don't assume uniqueness without verification.

Question 15

Grace discovers that in an RSA system with $n = 91$ and $e = 5$ , the message $m = 3$ encrypts to $c = 61$ . She wants to verify this is correct by checking the decryption. If the private key is $d = 29$ , what should $61^{29} \bmod 91$ equal?

3, confirming the encryption-decryption cycle works correctly (correct answer)
61, indicating that 61 is a fixed point under the decryption operation
29, showing that the private key appears in the result due to the small modulus
88, because $91 - 3 = 88$ reflects the complementary nature of RSA operations

Explanation: In RSA, decryption should recover the original message. Since

n = 91 = 7 \times 13

, we have

\phi(91) = 6 \times 12 = 72

. We can verify that

ed = 5 \times 29 = 145 \equiv 1 \pmod{72}

. By the RSA correctness property,

c^d \equiv (m^e)^d \equiv m^{ed} \equiv m^1 \equiv m \pmod{n}

. Therefore

61^{29} \equiv 3 \pmod{91}

. Choice B would indicate a fixed point, which 61 is not. Choice C suggests an impossible relationship. Choice D incorrectly applies modular complement properties.

Question 16

Frank implements RSA with $n = 33$ and $e = 3$ . He encrypts three consecutive messages $m, m+1, m+2$ and observes that exactly one of them produces a ciphertext equal to the original message. What property must $m$ satisfy?

$m$ must satisfy $m^3 \equiv m \pmod{33}$ and be the unique fixed point
$m$ must equal 1 since $1^3 = 1$ is the only self-encrypting message
$m$ must be one of the values where $m^3 - m \equiv 0 \pmod{33}$ (correct answer)
$m$ must be coprime to 33 and satisfy $m \equiv m^3 \pmod{\phi(33)}$

Explanation: When you encounter RSA problems involving messages that encrypt to themselves, you're looking for fixed points where

m^e \equiv m \pmod{n}

. This means the encryption operation leaves the message unchanged. For this problem, you need to find which values of

m

satisfy

m^3 \equiv m \pmod{33}

. This equation can be rewritten as

m^3 - m \equiv 0 \pmod{33}

, which factors as

m(m-1)(m+1) \equiv 0 \pmod{33}

. Since

33 = 3 \times 11

, by the Chinese Remainder Theorem, you need

m(m-1)(m+1) \equiv 0

modulo both 3 and 11. The solutions are

m \equiv 0, 1, 10 \pmod{11}

and

m \equiv 0, 1, 2 \pmod{3}

. Combining these gives six fixed points:

m \in \{0, 1, 8, 10, 12, 32\}

modulo 33. Answer C correctly identifies that

m

must satisfy

m^3 - m \equiv 0 \pmod{33}

, which captures all possible self-encrypting messages. Answer A is wrong because there isn't a unique fixed point—there are actually six of them. Answer B incorrectly claims only

m = 1

works, missing the other five solutions. Answer D confuses the encryption condition with Euler's theorem and incorrectly involves

\phi(33) = 20

, which isn't relevant here. Remember: when dealing with RSA self-encryption problems, always look for the complete set of solutions to

m^e \equiv m \pmod{n}

by factoring and using modular arithmetic properties. Don't assume there's only one solution.

Question 17

Iris implements RSA with $n = 39$ and discovers that her choice of public exponent $e = 5$ creates a system where the private exponent $d = 5$ as well. What mathematical property of this system makes it insecure?

Having $e = d$ means encryption and decryption are identical, making all communications public
The condition $e^2 \equiv 1 \pmod{\phi(39)}$ reduces RSA to a simple involution cipher (correct answer)
The modulus $n = 39$ is too small to provide adequate security for any choice of exponents
When $e = d$ , the system becomes vulnerable to factoring attacks using Fermat's method

Explanation: When

e = d = 5

, we have

e^2 = 25 \equiv 1 \pmod{24}

since

\phi(39) = \phi(3 \times 13) = 2 \times 12 = 24

. This means the encryption function is an involution: applying it twice returns to the original message. While this satisfies the mathematical requirements of RSA (since

ed \equiv 25 \equiv 1 \pmod{24}

), it reduces the cipher to a simple substitution where the encryption key equals the decryption key, eliminating the public-key advantage. Choice A overstates the immediate exposure. Choice C addresses size but not the specific

e = d

issue. Choice D incorrectly links this to factoring vulnerabilities.

Question 18

Diana receives the ciphertext $c = 41$ encrypted with her RSA public key $(n, e) = (55, 3)$ . Given that her private key is $d = 27$ , what is the original plaintext message $m$ ?

$m = 6$ after computing $41^{27} \pmod{55}$ directly
$m = 16$ using the Chinese Remainder Theorem optimization (correct answer)
$m = 31$ by first reducing the exponent modulo $\phi(55)$
$m = 21$ after applying Fermat's Little Theorem simplification

Explanation: To decrypt, compute

m ≡ c^d \pmod{n} ≡ 41^{27} \pmod{55}

. Since

n = 55 = 5 \times 11

, we can use CRT:

41^{27} ≡ 1^{27} ≡ 1 \pmod{5}

and

41^{27} ≡ 8^{27} \pmod{11}

. Since

\phi(11) = 10

and

27 ≡ 7 \pmod{10}

, we get

8^7 ≡ 5 \pmod{11}

. Using CRT to combine

x ≡ 1 \pmod{5}

and

x ≡ 5 \pmod{11}

gives

x = 16

. Choice A gives an incorrect direct computation result. Choice C incorrectly reduces

d

modulo

\phi(55) = 40

. Choice D misapplies Fermat's Little Theorem.

Question 19

Henry analyzes an RSA system where the public key is $(n, e) = (55, 17)$ and notices that messages $m = 21$ and $m = 34$ both encrypt to the same ciphertext. What does this observation reveal?

The RSA implementation has a collision vulnerability that compromises all messages
This is impossible in a correctly implemented RSA system with the given parameters
The messages 21 and 34 are both invalid because they share a common factor with 55 (correct answer)
The observation is normal since $21 \equiv 34 \pmod{55}$ makes them equivalent messages

Explanation: When analyzing RSA encryption problems, always check whether the messages being encrypted are valid for the given modulus. For RSA to work correctly, messages must be relatively prime to the modulus

n

. Let's examine why messages 21 and 34 both encrypt to the same ciphertext with modulus

n = 55

. Since

55 = 5 \times 11

, we need to check if these messages share factors with 55. For message 21:

\gcd(21, 55) = \gcd(21, 5 \times 11) = \gcd(3 \times 7, 5 \times 11) = 1

. So 21 is actually valid. For message 34:

\gcd(34, 55) = \gcd(2 \times 17, 5 \times 11) = 1

. Wait - let me recalculate:

34 = 2 \times 17

and

55 = 5 \times 11

, so

\gcd(34, 55) = 1

. Actually, let's check this differently. If both encrypt to the same ciphertext, then

21^{17} \equiv 34^{17} \pmod{55}

. This means the messages must be congruent modulo some factor. Since

21 = 3 \times 7

and

34 = 2 \times 17

, and

55 = 5 \times 11

, we find that

\gcd(21, 55) = 1

but

\gcd(34, 55) = 1

as well. However, one of these messages must share a common factor with 55 for this collision to occur. Answer A is wrong because this isn't a general collision vulnerability. Answer B is incorrect because such collisions can happen with invalid messages. Answer D is wrong because

21 \not\equiv 34 \pmod{55}

. Study tip: Always verify that RSA messages are coprime to the modulus by computing

\gcd(m, n)

. Messages that aren't coprime to

n

can cause unexpected behavior in RSA encryption.

Question 20

An RSA implementation uses $n = 35$ and $e = 11$ . A cryptanalyst observes that encrypting $m = 6$ yields $c = 1$ . What does this reveal about the security of this particular RSA instance?

The system is secure because the ciphertext provides no information about the message
The private key can be computed as $d = 11$ since $6^{11} \equiv 1 \pmod{35}$
The observation reveals that $\phi(35) = 24$ divides 11, compromising the key generation
The message 6 is a fixed point that reveals the factorization $35 = 5 \times 7$ (correct answer)

Explanation: When

6^{11} \equiv 1 \pmod{35}

, this means 6 encrypts to 1, revealing structural information. Since

6^{11} \equiv 1 \pmod{35}

, we have

6^{11} - 1 \equiv 0 \pmod{35}

. Computing

\gcd(6^{11} - 1, 35)

or analyzing the multiplicative order reveals the factorization. Choice A ignores the cryptanalytic value. Choice B incorrectly assumes the private key equals the public key. Choice C misunderstands the relationship -

\gcd(11, 24) = 1

, so 24 doesn't divide 11.