RSA Encryption
Main Concept
RSA (Rivest-Shamir-Adleman) Encryption is a widely-used public-key cryptosystem based on the complexity of factoring large numbers. "Large numbers" used by today's RSA systems are typically greater than 300 decimal digits or 1024 bits in length, and are extremely difficult to factor with the algorithms and computational power currently available. Such systems eliminate the need for a shared key. Information exchange is initiated by the private-key holder. Any party that wishes to send a message can encrypt the message to be sent using the public key. Only a private-key holder can decrypt the ciphertext; the difficulty of factoring such large numbers makes it almost impossible for intercepting parties to decrypt the message.
Generating a Public Key and a Private Key
Take two distinct prime numbers of similar bit-length, $p$ and $q$. These numbers are not chosen from a reserve of known primes, but are instead generated using algorithms that find the nearest probable prime to a very large randomly-generated integer. Probable primes are numbers that are believed to be primes because they share certain properties with known primes. However, due to these numbers being extremely large, it is very difficult to verify that these numbers are in fact prime. As a result, the number's true primality may become irrelevant. Primality tests, such as the Miller-Rabin and Fermat's Little Theorem, are used to generate probable prime numbers that are hundreds of digits in length.
Let $nequals;\mathrm{pq}$, where $n$ is the modulus for the public and private keys.
Compute the totient of $n$, ɸ$\left(n\right)equals;\u0278\left(p\right)\cdot \u0278\left(q\right)equals;\left(p-1\right)\cdot \left(q-1\right)$. The totient of $n$ is the number of positive integers less than or equal to a given number $n$ that are relatively prime to $n$. Two integers $a$ and $b$ are relatively prime or coprime if they do not have a prime factors in common.
Let $e$ be any number such that: $1e\u0278\left(n\right)$ and $e$ and $\u0278\left(n\right)$ are coprime.
$\left(n\,e\right)$ is the public encryption key.
Compute $dequals;{e}^{-1}$$\mathbf{mod}$ɸ$\left(n\right)$. The number $d$ is the private decryption key.
Encryption and Decryption
Encryption:
Apply padding techniques to the original plaintext message, such as random length padding, and permuting the message etc. as needed. Such padding techniques are necessary to subvert commonly know cryptographic attacks.
Convert the padded text to numeric form, by considering it as a representation of a number $m$ in some base (256-bit, 512-bit etc), such that $0mn$.
Compute $cequals;{m}^{e}\mathbf{mod}nperiod;$ This $c$ is the ciphertext,
Send $c$ to the the private-key holder to be decrypted.
Decryption:
1. Compute the original numeric message $mequals;{c}^{d}\mathbf{mod}nperiod;$
2. Recover the original plaintext message by converting $m$ to a string and reversing padding schemes as applied.
Generate a public/private key pair using this app, or using your own technology. You can then try encrypting and decrypting messages.
Generate a Public/Private Key Pair
Encrypt Message Using Public Key
1. Modulus (n)
2. Encryption key (e)
3. Plaintext
4. Numerical message
5. Ciphertext
Decrypt Message Using Private Key
2. Decryption key (d)
3. Ciphertext
5. Plaintext
More MathApps
MathApps/ComputerScience
Download Help Document