RSA & Modular Arithmetic lab report

1. Title and aim

Public-Key Cryptography & Modular Arithmetic: RSA Key Generation, Square-and-Multiply Exponentiation, Extended Euclidean Algorithm, and Miller-Rabin Primality. To investigate the algorithmic principles of public-key asymmetric cryptography, evaluate the mathematical foundations of the RSA cryptosystem, analyze Euler's Totient Theorem (M^(ed) ≡ M mod n), execute the Extended Euclidean Algorithm to compute modular multiplicative inverses d = e^(-1) mod φ(n), assess strong pseudo-prime generation via the Miller-Rabin test, verify the linear arithmetic scaling law M(B) = k_mod · B + M_0 = 1.5000 · B + 0.0000 operations across exponent bit lengths B ∈ [64, 4096] in Square-and-Multiply modular exponentiation, and evaluate integer factorization complexity under the General Number Field Sieve (GNFS).

2. Abstract

Seven benchmark trials were generated across private key exponent bit lengths B = 64 to B = 4096 bits (total modular exponentiation operations M from 96 to 6144 operations). An ordinary least-squares regression of modular operations against exponent bit length yielded an empirical multiplier of 1.5000 operations/bit and an intercept of 4.5475e-13 operations, demonstrating exact agreement with Rivest, Shamir, and Adleman's Square-and-Multiply invariant M(B) = 1.5B (difference = 0.0000%). The empirical telemetry confirms that by scanning the binary bitstring of the exponent, modular exponentiation executes exactly B squarings and 0.5 B multiplications, reducing operational complexity from exponential O(2^B) to strictly linear O(B).

3. Apparatus and fixed settings

• Square-and-Multiply Binary Exponentiation Unit: Evaluates multi-precision modular powers C = M^e mod n and M = C^d mod n in O(log e) operations via bitwise squarings and conditional multiplications.
• Extended Euclidean Modular Inverter: Solves Bézout's identity e · d + φ(n) · y = 1 to compute the modular multiplicative inverse private key exponent d = e^(-1) mod φ(n).
• Miller-Rabin Probabilistic Primality Tester: Verifies cryptographic strong pseudo-prime candidates using witness bases and quadratic congruence checks with composite error probability < 2^(-80).
• Euler Totient & Key Synthesis Engine: Computes composite modulus n = p · q, Euler's totient φ(n) = (p-1)(q-1), and verifies that public exponent e is coprime to φ(n).
• Montgomery Modular Multiplication Accelerator: Transforms large-integer operands into Montgomery residue space to replace multi-precision division with fast bitwise shifts and additions.
• Cryptographic Telemetry & Operation Logger: Tracks modular squarings, multiplications, calculates Effective Memory Access Time (EMAT), and validates linear regression against M(B) = 1.5B.
• Modular arithmetic: Multi-precision big integer arithmetic modulo composite n = p · q.
• Public exponent: Standard Fermat prime e = 65537 = 2^16 + 1.
• Private exponent d: Evaluated via the Extended Euclidean Algorithm d = e^(-1) mod φ(n).
• Exponent bit lengths tested: B ∈ [64, 128, 256, 512, 1024, 2048, 4096] bits.
• Exponentiation algorithm: Binary Square-and-Multiply modular exponentiation.

4. Theory and graph choice

Modern digital communication, global commerce, and national defense rely on public-key cryptography to establish secure channels over untrusted public networks. In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman created the RSA cryptosystem, realizing Diffie and Hellman's vision of asymmetric trapdoor one-way functions. RSA leverages the profound computational asymmetry between modular exponentiation and prime factorization: multiplying two massive prime numbers p and q to form modulus n = p · q executes in microseconds, whereas factoring n back into p and q requires astronomical computational energy under the best known classical sub-exponential algorithms (the General Number Field Sieve, GNFS). Under RSA, public encryption C = M^e mod n is accessible to all, while decryption M = C^d mod n requires the private exponent d = e^(-1) mod φ(n), calculated via the Extended Euclidean Algorithm. To evaluate modular powers with 2048-bit exponents without performing 10^616 sequential multiplications, cryptographic hardware utilizes the Square-and-Multiply algorithm. By scanning the binary bitstring of the exponent, the algorithm executes exactly B modular squarings and an average of 0.5 B modular multiplications, establishing the deterministic linear scaling law M(B) = 1.5000 · B operations. In this laboratory investigation, students benchmark modular exponentiation across key lengths B ∈ [64, 4096], verify the linear scaling law M(B) = 1.5000 · B + 0.0000 via ordinary least-squares regression, execute the Extended Euclidean Algorithm, analyze Miller-Rabin primality testing bounds, and contrast classical factorization hardness with quantum Shor's algorithm threat models.

The mathematical regression fits the linear model y = mx + b, where x = B represents exponent bit length in bits, y = M represents total modular arithmetic operations (squarings and multiplications), m represents the exponentiation multiplier k_mod, and b represents the baseline arithmetic offset (theoretically M_0 = 0.0000 operations). The gradient has physical units operations/bit.

5. Method

1. Generate large random odd integers p and q across benchmark bit lengths B ∈ [64, 128, 256, 512, 1024, 2048, 4096]. Execute 40 rounds of Miller-Rabin primality testing per candidate to guarantee composite error probability < 2^(-80).
2. Multiply prime factors to compute the composite public modulus n = p · q. Calculate Euler's totient function φ(n) = (p - 1)(q - 1).
3. Select the standard Fermat prime public exponent e = 65537, verifying that gcd(e, φ(n)) = 1. Execute the Extended Euclidean Algorithm to calculate the private decryption exponent d satisfying e · d ≡ 1 (mod φ(n)).
4. Decompose the private key exponent d into its binary representation (b_{B-1} ... b_0)_2. Initialize accumulator acc = 1. For each bit from most significant to least significant, execute a modular squaring acc = acc² mod n (incrementing operation counter by 1); if the bit is 1, execute a modular multiplication acc = (acc · base) mod n (incrementing counter by 1).
5. Encrypt a test plaintext integer M < n into ciphertext C = M^e mod n. Decrypt using C^d mod n and verify that M' matches original message M exactly, confirming Euler's theorem M^(ed) ≡ M mod n.
6. Plot recorded modular operations M(B) against exponent bit length B. Perform ordinary least-squares regression to verify the theoretical slope k_mod = 1.5000 operations/bit, intercept M_0 = 0.0000, and correlation coefficient R² = 1.00000.

6. Observations and calculation table

All benchmark observations use strictly controlled memory buffers. Values are recorded deterministically from the algorithmic comparator register. Residuals are computed relative to the ordinary least-squares regression line.

Download the sample observations (CSV) ↓

7. Worked calculation for one observation

8. Graph, gradient and final calculation

Circular markers represent empirical benchmark observations. The solid line represents the ordinary least-squares asymptotic linear fit.

9. Uncertainty and comparison

Percentage difference = |estimate − theoretical value| / |theoretical value| × 100 = 0.0000%.

For n = 7 benchmark observations, Σresidual² = 9.0897e-25; s² = Σresidual²/(n − 2). Gradient standard error = √[s²/Σ(x − x̄)²] = 1.1857e-16. Intercept standard error = √[s²(1/n + x̄²/Σ(x − x̄)²)] = 2.1196e-13.

Propagating the fit parameters yields a fit standard error of 1.1857e-16 operations/bit, with an ideal coefficient of determination R² = 1.000000.

In public-key cryptography and algorithmic number theory, the modular operation count M(B) = k_mod · B + M_0 = 1.5000·B + 0.0000 operations across exponent bit length B is an exact deterministic arithmetic invariant for binary Square-and-Multiply exponentiation. Unlike continuous physical instrumentation, there is no analog sensor noise, thermal drift, or calibration variance in counting discrete modular squarings or multi-precision multiplications. However, in physical cryptographic hardware and software implementations, wall-clock encryption/decryption latency and security margins are heavily modulated by microarchitectural dynamics: (1) Multi-precision large-integer limb arithmetic: large integers exceeding the native CPU register width (64 bits) are represented as arrays of 64-bit limbs; multi-precision multiplication scales quadratically as O((B/64)²) under classical Comba multiplication, or O((B/64)^1.58) via Karatsuba multiplication; (2) Montgomery residue space transformation: standard multi-precision modular division is replaced in production libraries (OpenSSL) by Montgomery multiplication, eliminating quotient division at the expense of initial domain conversion overhead; (3) Side-channel timing and power analysis vulnerabilities: conditional execution of modular multiplications in naive Square-and-Multiply creates data-dependent timing discrepancies, allowing adversaries to extract private key bits via Simple Power Analysis (SPA); and (4) Constant-time Montgomery ladder mitigation: production cryptographic security modules implement constant-time exponentiation ladders (executing 1 squaring and 1 multiplication on every bit regardless of bit value) to eliminate side-channel leakage. Ordinary least-squares linear regression of observed modular operations against exponent bit length B across instances from B = 64 to B = 4096 bits yields an empirical scaling multiplier k_mod = 1.5000 operations/bit and baseline intercept M_0 = 0.0000 operations with zero residual variance (R² = 1.00000), verifying the binary exponentiation complexity bound Θ(B) with mathematical certitude.

10. Result and discussion

The empirical benchmark observations provide rigorous quantitative verification of Public-Key Asymmetric Cryptography, Modular Arithmetic, and the RSA Cryptosystem. Traditional symmetric key cryptography requires sharing identical secret keys in advance, creating an intractable O(N²) key distribution problem in global networks. In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman solved this dilemma by inventing RSA, founded upon asymmetric one-way trapdoor permutations. Under RSA, encryption C = M^e mod n is publicly accessible, while decryption M = C^d mod n requires the private key exponent d = e^(-1) mod φ(n). According to Euler's Totient Theorem, if gcd(M, n) = 1, then M^φ(n) ≡ 1 mod n. Because e·d ≡ 1 mod φ(n), the exponents satisfy e·d = k·φ(n) + 1, guaranteeing that C^d ≡ (M^e)^d = M^(k·φ(n)+1) ≡ (1)^k · M ≡ M mod n. The Extended Euclidean Algorithm computes the modular inverse private key d in strictly logarithmic O(log(min(e, φ(n)))) steps by solving Bézout's identity e·d + φ(n)·y = 1. To evaluate modular powers with large cryptographic exponents without executing 10^616 operations, the Square-and-Multiply algorithm scans the binary bits of the exponent: every bit position unconditionally executes a modular squaring, and bits with value 1 execute an additional modular multiplication. Across all benchmark trials from B = 64 to B = 4096 bits, the empirical regression slope m = 1.5000 operations/bit and baseline intercept b = 0.0000 confirm this invariant with zero residual variance (R² = 1.00000). Comparative cryptographic security analysis evaluated the integer factorization hardness under the General Number Field Sieve (GNFS), demonstrating why 512-bit RSA is obsolete, 1024-bit is deprecated, 2048-bit represents the robust standard, and post-quantum lattice cryptography is emerging to counter quantum Shor's algorithm.

11. Precautions and limitations

• In production RSA implementations, never use textbook unpadded RSA; always apply Optimal Asymmetric Encryption Padding (OAEP) to prevent chosen-ciphertext attacks (CCA2) and Coppersmith attacks.
• Ensure that private primes p and q are chosen with large difference |p - q| > 2^(B/2 - 100) to prevent Fermat's factorization method from factoring n in seconds.
• In hardware cryptographic engines, implement Montgomery ladder or dummy multiplication branches to ensure constant-time execution, preventing timing and power analysis side-channel attacks.
• Securely zeroize and purge prime factors p and q and totient φ(n) from volatile memory immediately following private key generation to prevent cold boot memory extraction.

The simulated benchmark environment models idealized big-integer modular arithmetic where Square-and-Multiply modular operations scale deterministically (M(B) = 1.5B operations). In physical hardware cryptographic security modules (HSMs) and software libraries (OpenSSL), wall-clock latency is heavily modulated by multi-precision word sizes (e.g. 64-bit limbs vs. AVX-512 vector arithmetic), Montgomery residue space reduction overhead, cache line access patterns during sliding-window exponentiation, and constant-time side-channel countermeasure padding. In the Square-and-Multiply modular exponentiation benchmark across private key exponent bit lengths B in [64, 4096] bits (where the exponent d is an IEEE large integer with uniform Hamming weight W ≈ 0.5 · B, representing realistic cryptographic keys), exponentiation proceeds via binary scanning from the most significant bit to the least significant bit. At each bit position i ∈ [0..B-1], the algorithm unconditionally executes exactly 1 modular squaring operation (acc = acc² mod n) to double the binary weight. Additionally, whenever the current bit b_i = 1, the algorithm executes exactly 1 modular multiplication (acc = acc · base mod n). Across an exponent of bit length B, the cumulative arithmetic operation count is strictly governed by the exact deterministic linear invariant M(B) = B + 0.5 · B = 1.5000 · B + 0.0000 modular operations. Plotting modular operations against exponent bit length B yields an ordinary least-squares regression slope k_mod = 1.5000 operations/bit and baseline intercept M_0 = 0.0000 operations with an ideal coefficient of determination R² = 1.000000.

12. Conclusion

This laboratory investigation quantitatively verified the asymmetric key synthesis mechanics, modular inverse derivation, and Square-and-Multiply scaling of the RSA Cryptosystem. Through systematic benchmarking across exponent bit lengths from B = 64 to 4096 bits, we verified the empirical exponentiation multiplier k_mod = 1.5000 operations/bit and baseline intercept M_0 = 4.5475e-13 operations with an ideal R² = 1.00000. The investigation established the microarchitectural efficiency and theoretical necessity of one-way trapdoor functions, Euler's totient theorem, and constant-time modular arithmetic, proving why RSA and public-key cryptography remain the foundational pillar of Internet security, digital signatures, and global confidential communications.