Modern Cryptography RSA

Cryptography is very important to mantain us secure on Internet when we want to store or send valuable data. One of the most used cryptographic algorithms is the RSA algorithm. If you have never heard it, it’s used in banks, online shopping and important companies.

The idea of the cryptography is to prevent atackers from accessing your data. This is achieved with the computational cost of decryption. Computers have improved a lot during last years but they are not powerful enough to reverse heavy operations of cryptographic algorithms.

RSA Calculations and Explanation

We have two users Alice and Bob that want to share some information. Alice want to send Bob confidential information but Mallory is listening to them. With the RSA algorithms Alice will create a public and private key. The public key will be neccessary needed to encrypt a message and the private key for decrypting it. If Mallory decides to decrypt the message, his computer won’t achieved it because it requires a very high computational cost. A computer will spend thausends of years trying to decrypt it.

GENERATING PUBLIC AND PRIVATE KEY

STEP 1

We will create two random primes $p$ and $q$. The bigger they are the more secure they are. Then she will calculate $n$ that will be half of the public and private key by multiplying both primes. $n=pq$

The euler function that will be required for the second half of the keys will be defined as $\phi(n)=(p-1)(q-1)$.

STEP 2 

Then we should calculate a positive integer $e$ that must be a coprime with $\phi(n)$. The $e$ values is recommended to be a high number because it can suppose a risk in the RSA security. This integer will be the exponent, second parameter of the public key.

The public key will have to parameters: publicKey(n,e). She will be able to encrypt messages that Bob will be able to decrypt

STEP 3

To get the second parameter of the private key $d$ we should solve a modular inverse.

$e
\cdot d\equiv 1 \pmod{
\phi(n) } \rightarrow e
\cdot d-1 \equiv 0 \pmod{
\phi(n) }$

The private key of Bob will be: privateKey(n,d). He will be able to decrypt Alice’s encrypted messages

ENCRYPTING

When Alice want to encrypt a string message she will get the ASCII value of every char of the message and with an special reversible protocol. For example we can get a numerical string with the ascii values. We want to get the value of the message “test” that has as ASCII values $t[116], e[69], s[115], t[116]$.

$sequence=116 \cdot 256^3 + 69
\cdot 256^2 +
115
\cdot 256 +
116 $

Then the numerical sequence $m$ will be encrypted with the module $n$ and the exponent $e$.

$c\equiv m^e \pmod{n}$

DECRYPTING

When the encrypted message $c$ is sent by Alice, Bob will decrypt it with his private key $(n,d)$

$m\equiv c^d
\pmod{n} $

When the encryption and decryption want to be done in both directions each user will have a public and private key to encrypt and decrypt.

You can test the RSA algorithms with the Java source code I have made for you. Cryptography in Java