RSA and public-key cryptography concepts (intro) - Discrete Math

1. 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?
   Answer: The messages 21 and 34 are both invalid because they share a common factor with 55 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.
2. 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?
   Answer: 3, confirming the encryption-decryption cycle works correctly 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.
3. 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$?
   Answer: Decryption succeeds normally since $d' ≡ d \pmod{\phi(n)}$ and $\phi(143) = 120$ 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.
4. 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$?
   Answer: $c = 26$ 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).
5. 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$?
   Answer: $m = 16$ using the Chinese Remainder Theorem optimization 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.
6. 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?
   Answer: $c_1 \cdot c_2 \bmod 221 = 136$ using the multiplicative property with proper reduction 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.
7. 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?
   Answer: Factor $n = 91$ first, then solve $ed ≡ 1 \pmod{\phi(91)}$ directly 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.
8. 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?
   Answer: No integer $d$ satisfies $6d ≡ 1 \pmod{24}$ since $\gcd(6, 24) = 6 ≠ 1$ 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.
9. 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?
   Answer: $m$ must be one of the values where $m^3 - m \equiv 0 \pmod{33}$ 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.
10. 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?
    Answer: The message cannot be encrypted because $\gcd(22, 143) = 11 \neq 1$, violating RSA requirements 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}$.
11. 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?
    Answer: $d = 17$ since $5 \times 17 ≡ 1 \pmod{12}$ 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).
12. 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?
    Answer: The message 6 is a fixed point that reveals the factorization $35 = 5 \times 7$ 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.
13. 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?
    Answer: Bob computes $s^e \bmod n = 49^{13} \bmod 77 = 42$, matching the original hash 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.
14. 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?
    Answer: Since $\gcd(12, 143) = 11 ≠ 1$, the encrypted message may leak information about the factorization 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.
15. 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?
    Answer: An attacker can use the Chinese Remainder Theorem to recover $m^3$ and then find $m$ 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.
16. 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?
    Answer: $m = 8^3 \bmod 15 = 2$, successfully recovering the original message 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.
17. 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?
    Answer: The message could be $m = 2$ or $m = 13$, but additional information is needed 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.
18. 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$?
    Answer: $e = 25$ because $\gcd(25, 288) = 1$ and $25 < 288$ 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)$.
19. 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?
    Answer: The condition $e^2 \equiv 1 \pmod{\phi(39)}$ reduces RSA to a simple involution cipher 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.
20. 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$?
    Answer: Alice successfully recovers the original message $m = 5$ 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.

Start this quiz