MATHEMATICAL FOUNDATIONS OF RSA ENCRYPTION USING PRIME FACTORIZATION

Background to the Study

For most recorded history secure communication depended on symmetric-key cryptography in which same secret key used to both encrypt and decrypt message and must therefore be exchanged between communicating parties through some secure channel established in advance. Requirement known as key-distribution problem becomes acutely difficult at scale modern digital communication where two parties who have never met and share no prior secret routinely need to establish secure communication as happens whenever web browser connects to secure website. Resolution came from 1976 work Whitfield Diffie and Martin Hellman who introduced concept public-key cryptography in which each party possesses mathematically related pair keys one public private such that information encrypted with public key can be decrypted only with corresponding private key eliminating need prior secret exchange. First practical widely adopted realisation was RSA cryptosystem published 1978 by Ronald Rivest Adi Shamir Leonard Adleman named after inventors. RSA security rests on striking asymmetry rooted entirely in elementary number theory: given two large prime numbers p and q it is computationally easy to multiply them to obtain product n=pq but given only n it is believed computationally infeasible for sufficiently large primes to recover p and q by any known efficient algorithm. Asymmetry combined with number-theoretic results Pierre de Fermat and Leonhard Euler concerning modular exponentiation more than two centuries before advent digital computers allows message encrypted using public modulus n and public exponent e to be decrypted only by someone possessing knowledge prime factorisation n. Nearly five decades after publication RSA remains one most widely deployed public-key cryptosystems in world underlying secure web browsing as part of TLS/SSL protocol digital signatures secure email notwithstanding emergence elliptic-curve alternatives offering smaller key sizes for comparable security. This study undertakes rigorous proof-based development of number theory underlying RSA followed by original computational investigation using genuinely generated numbers and independently timed algorithms rather than assumed or cited figures of both correctness of scheme and computational hardness of factorisation problem on which security depends.

Statement of the Problem

While RSA used ubiquitously in practice its correctness guarantee that decryption always recovers original message depends on specific non-obvious results from elementary number theory namely Euler Theorem and corollaries whose proofs frequently omitted or merely cited in applied treatments cryptography leaving gap between practical usage and mathematical justification. Equally claim RSA secure rests entirely on unproven computational hardness assumption namely that integer factorization hard for large numbers claim rarely substantiated with direct reproducible computational evidence in undergraduate-level treatments. There is therefore need for treatment that both rigorously proves correctness of RSA from first principles and empirically demonstrates through directly implemented and timed factorization algorithms why security assumption holds in practice for realistic key sizes.

Aim and Objectives of the Study

Aim is to investigate mathematical foundations RSA cryptosystem with emphasis on number theory guaranteeing correctness and prime factorization problem underlying security.

·         Develop necessary foundations modular arithmetic including Euler totient function Fermat Little Theorem and Euler Theorem.

·         State and prove RSA correctness theorem establishing decryption always recovers original plaintext.

·         Construct fully worked independently verified numerical instance RSA key generation encryption decryption using genuine multi-digit primes.

·         Implement and directly benchmark two integer factorization algorithms trial division and Pollard rho algorithm on moduli systematically increasing bit length.

·         Relate observed computational growth rates to theoretical asymptotic complexity each algorithm and to current recommended RSA key sizes.

Research Questions

1.      What number-theoretic results required to guarantee RSA decryption always recovers original plaintext?

2.      How is valid RSA key pair constructed from two large primes and how can construction be verified numerically?

3.      How does running time of trial division scale with size number being factored?

4.      How does running time of Pollard rho algorithm scale with size number being factored and how does this compare with trial division?

5.      What do observed growth rates imply about choice RSA key sizes considered secure in practice?

Significance of the Study

Significant academically because connects elementary number theory foundational undergraduate subject directly to one most consequential applications mathematics modern digital economy. Pedagogically provides fully worked independently verified numerical example RSA key generation and use together with original benchmark data on factorization algorithm performance addressing common gap between cited security claims and demonstrated computational evidence. Practically study factorization benchmarks provide concrete reproducible illustration why key size selection matters in real cryptographic deployments of direct relevance to computer security and information technology practice in Nigeria and elsewhere.

Scope of the Study

Covers number-theoretic foundations RSA modular arithmetic Euler totient function Fermat Little Theorem Euler Theorem and RSA correctness theorem and two classical integer factorization algorithms trial division and Pollard rho algorithm benchmarked directly on moduli ranging 16 to 72 bits range chosen small enough direct computation within scope undergraduate project while remaining large enough reveal algorithms distinct asymptotic growth behaviour. Does not implement or benchmark sub-exponential factorization algorithms such as quadratic sieve or General Number Field Sieve nor implement Shor quantum factoring algorithm both discussed only descriptively with reference literature in Chapter Two and Five.

Limitations of the Study

Theoretical and computational nature does not involve primary data collection or human subjects. Principal limitation lies restriction direct factorization benchmarking to moduli at most 72 bits several orders magnitude smaller than 2048-bit or larger moduli used real-world RSA deployments restriction necessitated by impracticality factoring realistic RSA moduli with elementary algorithms implemented here within any feasible computation time; study addresses by extrapolating observed asymptotic growth trends and citing established literature results for performance General Number Field Sieve against realistic key sizes rather than reproducing them directly.

Operational Definition of Terms

·         Modular Arithmetic: System arithmetic integers in which numbers wrap around upon reaching fixed value modulus.

·         Euler Totient Function: Function φ(n) counting positive integers up to n relatively prime to n.

·         Public-Key Cryptosystem: Encryption scheme in which each party has mathematically related public/private key pair with public key freely shared private key kept secret.

·         RSA Modulus: Product n=pq of two large distinct primes published as part public key.

·         Trapdoor Function: Function easy to compute one direction but computationally infeasible to invert without special private information.

·         Integer Factorization Problem: Computational problem finding prime factors given composite integer.

·         Trial Division: Elementary factorization method testing successive candidate divisors up to square root number being factored.

·         Pollard Rho Algorithm: Probabilistic integer factorization algorithm expected running time O(n^{1/4}) based on detecting cycles in pseudo-random sequence modulo factor of n.

Short Conclusion

Results show trial-division running time grows agreement known O√n complexity becoming impractical beyond roughly 40 bits in implementation while Pollard rho algorithm consistent with O(n^{1/4}) expected complexity remains substantially faster every tested size and successfully factored 72-bit modulus in under sixteen seconds illustrating concretely why realistic RSA moduli chosen at 2048 bits and above far beyond reach either algorithm and indeed beyond reach best currently known classical factoring algorithm General Number Field Sieve. Worked numerical example confirms exact agreement between encrypted and doubly-transformed plaintext verifying correctness theorem in practice while factorization benchmark provides direct reproducible computational evidence for asymmetry between ease RSA key generation and difficulty breaking it without private key. Study concludes discussing recommended modern RSA key sizes practical role Chinese Remainder Theorem in efficient decryption and emerging threat posed by Shor quantum factoring algorithm polynomial time O((log N)^3) to long-term security RSA.

10 SEO-Friendly FAQs

1. What number theory guarantees RSA correctness?

Modular arithmetic Euler totient φ(n)=(p-1)(q-1) for n=pq, Fermat Little Theorem If p prime and p∤x then x^{p-1}≡1 mod p, Euler Theorem If gcd(x,n)=1 then x^{φ(n)}≡1 mod n, ensuring ed≡1 mod φ(n) implies (m^e)^d ≡ m mod n recovers plaintext.

2. How is RSA key pair constructed?

Choose two large distinct primes p q six seven-digit primes in this study, compute n=pq modulus, φ(n)=(p-1)(q-1), choose public exponent e coprime to φ(n), compute private exponent d ≡ e^{-1} mod φ(n) via Extended Euclidean Algorithm; encryption c=m^e mod n decryption m=c^d mod n.

3. Why trial division scales O(√n)?

Tests divisors up to √n; complexity O(√N) ~ O(2^{n/2}) for n-bit number; becomes impractical beyond ~40 bits in Python implementation; benchmark shows exponential growth T(x)=4.46×10^{-9}·e^{2.41x} ~1.7×10^{313} seconds for 308-digit production RSA.

4. How does Pollard rho compare?

Expected O(n^{1/4}) = O(N^{0.25}) ~ O(2^{n/4}) using Floyd cycle detection pseudo-random sequence x_{i+1}=x_i^2+c mod n gcd(|x_i - x_j|,n) yields factor; substantially faster than trial division T(x)=1.09×10^{-6}·e^{1.19x} ~5.8×10^{152} secs for 308-digit but still infeasible for 2048-bit; factored 72-bit modulus under 16 seconds in study.

5. Why 2048-bit RSA considered secure?

72-bit factored in <16s; extrapolation shows 2048-bit far beyond reach trial division ~10^308 ops Pollard rho ~10^154 ops and even General Number Field Sieve sub-exponential but still super-polynomial; 2048-bit recommended minimum, 3072-bit for long-term per NIST.

6. What is Chinese Remainder Theorem role?

Practical role efficient decryption: compute m_p=c^{d mod p-1} mod p and m_q=c^{d mod q-1} mod q then combine via CRT to obtain m mod n faster than direct exponentiation mod n especially with large exponents.

7. What is trapdoor function in RSA?

Function easy compute one direction multiply p·q=n and modular exponentiation but computationally infeasible invert without private information factorisation of n to obtain φ(n) and d; asymmetry ease key generation vs difficulty breaking without private key.

8. Does Shor quantum algorithm break RSA?

Yes Shor quantum factoring algorithm shows polynomial time O((log N)^3) period finding via Quantum Fourier Transform; capable breaking 2048-bit RSA if sufficiently large fault-tolerant quantum computer available; threat drives post-quantum cryptography NIST FIPS 203/204/205.

9. How was correctness verified numerically?

Fully worked independently verified numerical instance using genuine six seven-digit primes key generation encryption decryption exact agreement between original plaintext and doubly-transformed plaintext confirms correctness theorem in practice.

10. Where to find similar cryptography project topics?

Explore RSA prime factorization modular arithmetic topics on ScholarNestHub mathematics collection and university mathematics behind RSA materials.