Exercise 3: Why Doubling RSA Key Size Helps Security So Much More Than It Hurts Speed — Possible Solution (intuition only, per this exercise's own scope note) ==================================================================== THE TWO OPERATIONS GROW AT GENUINELY DIFFERENT RATES ------------------------------ Legitimate encryption and decryption is repeated multiplication under a modulus (this course's own Chapter 7 formalizes this as modular exponentiation). Multiplying larger numbers together does take somewhat longer as the numbers grow, but the slowdown is POLYNOMIAL - roughly proportional to some fixed power of the number of digits. Doubling the digit count makes each individual operation slower by a bounded, predictable, relatively small factor - encryption and decryption remain fast in absolute terms, which is exactly why real systems can afford to use much bigger keys without users noticing any meaningful delay. Factoring the product, with no shortcuts and no prior knowledge of its two prime factors, does NOT slow down at the same predictable polynomial rate. This chapter's own worked demonstration showed that factoring a product from scratch needs a search space related to the SQUARE ROOT of the product itself, not the product's own digit count directly - and real-world factoring algorithms (more sophisticated than the simple trial division this chapter used to illustrate the idea) still scale in a way that grows dramatically faster than polynomially as the number of digits increases. WHY THIS PRODUCES SUCH A LOPSIDED OUTCOME ------------------------------ Because the "legitimate" cost (multiply/exponentiate) and the "attacker" cost (factor from scratch) are governed by fundamentally different growth rates, adding more digits doesn't affect them proportionally. A modest, linear-feeling increase in key size (say, doubling the number of digits) causes only a modest, predictable increase in how long encryption and decryption take - but causes a dramatically larger increase in how hard the factoring problem becomes, because factoring's own difficulty compounds much faster as the numbers involved grow. This exact lopsidedness - a small, controlled cost for the legitimate operation, paired with an enormous, compounding cost for the attack - is precisely why RSA is usable as real-world security at all. If both operations scaled at the same rate, there would be no meaningful security margin to exploit; making the key bigger would just slow everyone down equally. WHAT'S DELIBERATELY LEFT IMPRECISE HERE ------------------------------ This answer intentionally avoids stating an exact growth-rate formula for either operation, since this chapter's own Chapter 7 (fast exponentiation) hasn't been covered yet, and the precise behavior of real factoring algorithms is well beyond this course's own stated scope. The reasoning above captures the genuine shape of the asymmetry - two operations governed by different growth rates - without overstating a level of mathematical precision this chapter never claimed to provide. WHY THIS WORKS AS AN ANSWER ------------------------------ The explanation identifies the correct underlying mechanism (two operations with genuinely different growth rates, not just "one is harder than the other") and is honest about what remains imprecise at this stage of the course, matching the exercise's own explicit statement that a precise answer isn't expected yet.