9.3 Prime Numbers, Factorization, and the Mathematical Boundaries of RSA

The security fortress delivers a lock based on large integers. The task within the tower isn't to admire prime numbers per se, but to identify which computational problems provide the foundation for its strength.

Prime numbers are fundamental building blocks of integer factorization and appear in discussions of public-key cryptography and hash tables. However, simply using primes does not automatically yield security or uniform distribution; the actual security and behavior of the algorithm depend entirely on the full construction.

Prime Numbers and the Fundamental Theorem of Arithmetic

An integer greater than 1 that has no positive divisors other than 1 and itself is called a prime number. An integer greater than 1 that is not prime is called a composite number.

The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be expressed as a product of prime numbers, and this factorization is unique up to the order of the factors.

360 = 2³ · 3² · 5

Prime factorization enables a clear understanding of gcd, lcm, and simplification operations in terms of prime exponents. However, factoring large integers into their prime components can be computationally challenging in practice.

Trial Division and Sieve Methods

Determine whether n is prime; if it has a nontrivial factor, at least one is no greater than √n. Thus, we can test divisors up to the square root.

To avoid floating-point square root boundaries, use:

d≤n/d

And first handle 2, then only test odd numbers.

To find all primes in a given range, the Eratosthenes sieve marks multiples starting from small primes, with typical time complexity O(N log log N) and space complexity O(N). Segment sieving reduces memory usage for large intervals.

Trial division works well for small numbers but is not suitable for cryptographic-scale values.

Primality Testing Does Not Equal Factorization

Primality testing answers the question "Is n a prime number?" whereas factorization requires producing the actual factors of a composite number. The former has deterministic polynomial-time algorithms, and in practice, efficient probabilistic tests are widely used. In contrast, no known classical polynomial-time algorithm exists for the general factorization of large integers.

The Miller–Rabin test expresses an odd number n as:

n - 1 = 2^s * d, where d is odd

It then checks the strong pseudoprime condition for a chosen base. Finding a witness proves that n is composite; passing multiple independent random bases yields a "probable prime" conclusion, with the error probability decreasing as the number of rounds increases.

For fixed machine integer ranges, a known set of deterministic bases can be used to achieve a definitive judgment. The specific combination of bases depends on the numerical upper bound and cannot be simply extended from 64-bit rules to arbitrary large integers.

Cryptographic key generation should use established standards and mature libraries (including candidate generation, random source selection, additional validation, and parameter length specifications) rather than manually combining Miller–Rabin tests.

RSA's Mathematical Backbone

Teaching model:

1. Select two distinct large primes p,q;
2. Compute n=pq;
3. Calculate λ(n)=lcm(p-1,q-1) or the corresponding standardized parameters;
4. Choose e such that gcd(e,λ(n))=1;
5. Compute d≡e⁻¹ (mod λ(n)).

The public key contains (n,e), while the private key includes d and commonly used CRT parameters. Basic operations:

c ≡ m^e (mod n)
m ≡ c^d (mod n)

Correctness stems from exponentiation modulo congruence, and each equation can be proven separately modulo p and modulo q, then combined using the Chinese Remainder Theorem (CRT).

Textbook RSA Cannot Be Used Directly

Raw m^e mod n is deterministic and does not provide semantic security required by modern encryption, making it vulnerable to structural and chosen-ciphertext attacks. Standard cryptographic schemes define encoding for basic RSA operations as follows:

• Encryption uses schemes like RSAES-OAEP;
• Signing uses schemes like RSASSA-PSS;
• In practice, large data volumes typically employ hybrid encryption, where RSA is used only to encrypt a randomly generated symmetric key.

Encryption and signing are not simply the same interface flipped, private-key encryption and public-key decryption. They have distinct security objectives and encoding mechanisms.

The security of RSA should not be stated as being "equivalent to the difficulty of integer factorization." Efficient factorization of n would reveal the private key, but the precise equivalence between RSA inversion and integer factorization has not been universally established as a general principle. Security assessments depend on the RSA problem, the specific encoding scheme, key length, implementation details, and the attack model.

Quantum Shor's algorithm poses a threat to RSA on sufficiently large, fault-tolerant quantum computers; migration strategies are discussed in Chapter 8 of the Cryptography section.

Hash Table Capacity: Primes Are Not Magic

Slot mapping typically follows one of two patterns:

index = floorMod(hash, m)
index = mixedHash & (m - 1), when m is a power of two

Prime moduli help avoid certain input step sizes sharing factors with the table length, which can lead to short cycles, especially in linear probing or simple polynomial hashing. However, the actual distribution of keys depends jointly on the hash function, key distribution, bit extraction method, and collision resolution strategy.

A capacity that is a power of two enables fast indexing via masking and easy doubling when resizing. It performs well if the high and low bits are properly mixed; however, if only the low bits are used and the keys have strong low-order patterns, clustering can occur.

Therefore, it's incorrect to broadly claim that "primes always result in fewer collisions." Instead, one should:

• Follow the capacity strategy appropriate to the specific implementation;
• Use well-designed hash mixing;
• Implement anti-hash flooding defenses for keys under attacker control;
• Conduct stress testing with realistic load factors and actual key distributions.

The goals of cryptographic hashing and hash table lookup are fundamentally different, and their evaluation criteria should not be conflated.

The Minimum Boundary of Cryptographic Implementation

• Do not implement RSA padding, prime generation, or constant-time operations from scratch;
• Use well-maintained standard libraries with explicit algorithm identifiers;
• Select key lengths and signature/enryption schemes according to current best practices;
• Clearly distinguish between encryption, signing, and key exchange operations;
• Design key rotation, revocation, and algorithm migration strategies;
• Validate implementation through test vectors and interoperability testing.

A mathematical explanation of why an algorithm works cannot alone prove the security of its implementation.

Completion Checklist

1. Use the sieve method to list all prime numbers below 100;
2. Explain what "witnesses" and "probable primes" mean in the context of the Miller–Rabin test;
3. Manually compute a small RSA example using small primes, and clearly demonstrate why it is insecure;
4. Explain why OAEP/PSS is not merely optional padding, why it is essential;
5. Construct key pairs with shared low bits and compare direct masking with indexing after bit mixing;
6. Clarify the difference between "if you can factor, you can break RSA" and "RSA inversion has been proven equivalent to factoring."

References

• RFC 8017: PKCS #1 v2.2
• NIST FIPS 186-5: Digital Signature Standard
• GNU MP: Prime Testing Algorithm