Q18Information Security Systems

Invented by Rivest, Shamir, and Adleman in 1977, RSA is the absolute foundation of global Asymmetric (Public Key) Cryptography. It completely eradicates the key-distribution nightmare of symmetric systems. Its security is mathematically anchored in the catastrophic computational difficulty of factoring massive semi-prime numbers.

The server executes a rigid mathematical sequence to generate the Key Pair:

• Step 1 (Prime Selection): Violently generate two massive, distinct prime numbers, $p$ and $q$ (in reality, these are 2048 bits long). Example: Let $p=11$ and $q=3$.
• Step 2 (The Modulus): Mathematically calculate $n=p\times q$. This $n$ will be released to the public. Example: $n=11\times 3=33$.
• Step 3 (Euler's Totient): Calculate $\varphi (n)=(p-1)\times (q-1)$. Example: $\varphi (33)=10\times 2=20$.
• Step 4 (Public Exponent $e$): Select an integer $e$ such that $1<e<\varphi (n)$, and $e$ is strictly coprime to $\varphi (n)$ (they share no common factors except 1). Example: Let $e=3$. (3 and 20 are coprime).
• Step 5 (Private Exponent $d$): Mathematically calculate the modular multiplicative inverse of $e$ modulo $\varphi (n)$. Meaning, $(d\times e)\equiv 1(\mathrm{mod}\varphi (n))$. Example: $(d\times 3)\equiv 1(\mathrm{mod}20)$. By trial or Extended Euclidean algorithm, $d=7$, because $(7\times 3)=21$, and $21(\mathrm{mod}20)=1$.

The keys are now violently locked. - Public Key: $(e,n)\Rightarrow (3,33)$. - Private Key: $(d,n)\Rightarrow (7,33)$.

Encryption (By the Sender using Public Key)

Let the plaintext message $M=4$. The mathematical encryption formula is: $$C=M^e(\mathrm{mod}n)$$

Execution: $C=4^3(\mathrm{mod}33)=64(\mathrm{mod}33)=31$. The Ciphertext $C=31$ is blasted across the public internet.

Decryption (By the Receiver using Private Key)

The receiver mathematically unlocks $C$ using their highly guarded Private Key ($d=7$). The formula is: $$M=C^d(\mathrm{mod}n)$$

Execution: $M=31^7(\mathrm{mod}33)$. $31^7=27512614111$. $27512614111(\mathrm{mod}33)=4$. The absolute original plaintext $M=4$ is flawlessly recovered.

A hacker intercepts $C=31$, and knows the Public Key $(e=3,n=33)$. To decrypt the message, the hacker MUST mathematically calculate the Private Key $d$. To calculate $d$, the hacker MUST know $\varphi (n)$. To know $\varphi (n)$, the hacker MUST know the original prime numbers $p$ and $q$.

Therefore, the hacker must mathematically factor $n$ back into $p\times q$. For $n=33$, a human can instantly see $11\times 3$. However, if $n$ is a 4096-bit number (a number with 1200 digits), no supercomputer on Earth possesses the physical time or mathematical algorithms to execute the factorization before the universe ends. The security of RSA relies entirely on the catastrophic asymmetry of multiplication (easy) versus factorization (impossible).