RSA cryptosystem - Proofs of correctness
RSA Introduction Most of us know RSA cryptosystem which is the most widely spread cryptosystem even today. The system was invented by three scholars Ron Rivest, Adi Shamir, and Len Adleman and hence, it is termed as RSA cryptosystem. In RSA, the process of encryption and decryption is depicted in the following illustration. RSA Algorithm Now let’s drill down this $encryption (E)$ and $decryption (D)$ process furthermore. As we all know the RSA algorithm [1] works as follows: Choose two prime numbers $p$ and $q$, Compute the modulus in which the arithmetic will be done: $N = pq$, Pick a public encryption key $e \in Z_n$, Compute the private decryption key as $d$ such that $ed = 1\; mod\; \phi(N)$, Encryption of message $m: c = m^e\; mod\; N$, Decryption of ciphertext $c: m=c^d\; mod\; N$. Proof Our simple proof uses the Euler-Fermat Theorem. Let’s first have a look at it. Euler-Fermat Theorem Let $n$ be a positive integer, and let $a$ be an int