ROUGH DRAFT authorea.com/107265
Main Data History
Export
Show Index Toggle 0 comments

Key Cryptography

RSA encryption can be used for many things such as keeping important messages secured. It is very difficult to break or decode messages that have been encrypted by RSA encryption if not given a public key. There are a few steps that one must go through in order to encrypt and decrypt a message.

We can look at few variables that are needed through the RSA encryption process:

\(e\) will be our public key 
\(d\) is the value used for decoding and is only given to the receiver 
\(p\) and \(q\) are the primes
\(n\) is the result of \(pq\)
\(M\) is the original message 
\(C=M^e\) (mod \(n\)) is used to encrypt messages
\(C^d\) (mod \(n\)) is used to decrypt messages

In order to encrypt a message, primes \(p\) and \(q\) are to be chosen. We can compute \(n\) by multiplying, \(pq\). The value of \(n\) is the value that is made public, however the primes \(p\) and \(q\) are kept a secret. Next \(\phi n\) is calculated also denoted as \(\phi n=\left(p-1\right)\left(q-1\right)\). Afterwards, the value \(d\) is chosen, and \(d\) has to be relatively prime to \(\phi n\), this can be done using Euclidean algorithm. The algorithm then shows how \(e\) is found by using the equation \(de+\phi nf=1\). The value of \(e\) is made public while the value of \(d\) is kept a secret.


Seeing an example can be more helpful. Let’s say that \(p=7\) and \(q=17\), \(n\) can be computed by \(pq\) and in our case \(pq=119\). To calculate \(\phi n\) we do \(\left(7-1\right)\left(17-1\right)\), \(\phi n=\left(6\cdot16\right)=96\). Next, \(d\) will be chosen. Keep in mind that \(d\) must be relatively prime to \(\phi n\). In our case lets say \(d=5\). We now can plug this onto our equation to find the value of \(e\). In our case \(5e+96f=1\) . We can see that \(e=19\) and \(f=-1\) in order to satisfy our equation. Now in order to encrypt the message we take our message \(M\) and raise it to the \(e\) power (mod \(n\)), in this case lets say we want to send the message \(2\), so we can encrpty by saying \(2^{19}\) (mod \(119\)) which equals \(93\). In order for someone to decrypt the message they will take the value \(C\) and raise it to the \(d\) power (mod \(n\)), \(93^5\)(mod \(119\)) .


Suggested Exam Problem: If \(p=3\) and \(q=23\) find an appropriate \(d\) and \(e\)<