Q11Information System Security

Invented by Rivest, Shamir, and Adleman, RSA is the absolute foundation of Asymmetric Cryptography. It completely eradicates the key-distribution problem of symmetric ciphers. Its security is mathematically anchored in the horrific computational difficulty of Integer Factorization.

• Step 1: Violently generate two massive, distinct prime numbers, $p$ and $q$. (Example: $p=3,q=11$).
• Step 2: Mathematically calculate the Modulus $n=p\times q$. ($n=33$). This $n$ will be released to the public.
• Step 3: Calculate Euler's Totient $\varphi (n)=(p-1)\times (q-1)$. ($\varphi (33)=2\times 10=20$).
• Step 4: Select the Public Exponent $e$. It must be $1<e<\varphi (n)$, and strictly coprime to $\varphi (n)$. (Let $e=7$).
• Step 5: Calculate the highly secret Private Exponent $d$. It is the modular multiplicative inverse of $e(\mathrm{mod}\varphi (n))$. Meaning, $(d\times e)\equiv 1(\mathrm{mod}\varphi (n))$. (Let $d=3$, because $3\times 7=21\equiv 1(\mathrm{mod}20)$).

The Public Key is $(e,n)\to (7,33)$. The Private Key is $(d,n)\to (3,33)$.

Encryption (Sender using Public Key)

Let Plaintext Message $M=2$. The absolute encryption formula is $C=M^e(\mathrm{mod}n)$.

$C=2^7(\mathrm{mod}33)=128(\mathrm{mod}33)=29$. The Ciphertext $C$ is $29$.

Decryption (Receiver using Private Key)

The receiver violently unlocks $C$ using their Private Key $d$. Formula: $M=C^d(\mathrm{mod}n)$.

$M=29^3(\mathrm{mod}33)=24389(\mathrm{mod}33)=2$. The absolute original plaintext $2$ is flawlessly recovered.

A hacker intercepting $C=29$ and $n=33$ cannot find $d$ without knowing $\varphi (n)$, which requires mathematically factoring $n$ back into $p$ and $q$. For massive 2048-bit numbers, this is physically impossible.