View source for Swanson MA279 Fall2022 topic10 - Rhea

<h1 style="font-size: 40px">Encryption methods in Cyber security</h1>

<h1 style="font-size: 30px">1. Overview</h1>

In the age of the internet, data transmission is everything. It allows us to do things as simple as messaging our family members, or as complex as completing bank transactions. But we do sadly live in a world with bad actors who are willing to intercept these messages. Imagine if you send a message to your mother involving an important situation. Just directly sending your message over the internet means that anyone in between you and your mother could read that message too. While it could be embarrassing it is not catastrophic. Imagine now that instead of a message to your mother, it is your credit card details while you are making an online transaction. A bad actor viewing this is obviously a danger, so we need some sort of security to counteract that.

In the field of cybersecurity, there is thankfully a counterattack to this in the form of cryptography. The field of cryptography is best defined as “the practice and study of techniques for secure communication in the presence of adversarial behavior.” The way it works is when we have a message, we use a key to encrypt the message before sending it over the web. This encryption can massively shift how the original message looks and often makes it an unintelligible message known as the cipher text. This cipher text is then sent, using a key (possibly different from the original key), and is decrypted back into the original message. A Caesar Cipher is an encryption method that hides messages by shifting the alphabet. Here is a simple example using a basic Caesar cipher to exemplify that idea. Say for example we shift the alphabet 3 letters.

ABCDEFGHIJKLMNOPQRSTUVWXYZ

becomes

DEFGHIJKLMNOPQRSTUVWXYZABC

So a message saying "Hello world!" would now say "Ebiil tloia!"

If we know that the alphabet shifted 3 letters, with 3 as the key, we can just reverse the shift to return the cipher text back to the original message.

In the explanation of how encryption works above, we mentioned using a key to encrypt and decrypt the message. In the example above, our key was how far we wanted to shift the alphabet, and then we used it to change the message into the cipher text. In more advanced cryptography, the process is similar in using a key in calculations with the message to create the cipher text, except their keys tend to be prime. From here this is where cryptography splits into two sections, methods with symmetric keys and asymmetric keys.

<h1 style="font-size: 30px">2. Symmetric key</h1>

A symmetric key algorithm is one that shares the same key for both encrypting the message and decrypting the cipher text. This can be split into classical methods, which we will briefly touch on, and modern methods.

You’ve actually already seen an example of a classical encryption method above. The Caesar cipher is a symmetric key algorithm, specifically a substitution cipher since it shifts the alphabet forwards for replacement and shifts the alphabet backward to undo the replacement for the same amount. Another example of a classical encryption method is transposition cipher where the text is divided into units, typically groups of characters, and reordered to produce a ciphertext which is a permutation of the plaintext, but you can reorder it back if know the rule of permutation. The modern uses fall into the two categories of stream cipher and block cipher. Classical ciphers could be done by hand, but moving into these ciphers tends to involve a computer of some sort or it will take a very long time. The way both of these encryption methods work is with a numeric key.

For each digit in the data, a stream cipher, in the case of a computer a bit, performs an operation on that bit using the key to create a bit in the cipher text. It gets more complicated since with each bit encrypted, the state of the encryption method changes which then affects how the next bit is encrypted. A notable historical example of this type of cipher is the Enigma Code the Germans used in WWII. When a key was pressed on an Enigma Machine it would have another key light up to show what it had been encrypted to. The actual encryption method was inside of the machine, and as for the key it used how its plug board was laid out to affect encryption. 

A block cipher uses a very similar encryption method to the stream cipher, but rather than encrypting each bit one by one it divides the message into blocks of data which it then encrypts separately.

<h1 style="font-size: 30px">3. Symmetric key example</h1>

'''Block cipher'''

Block cipher is a symmetric key cryptosystem that takes a block of plaintext to generate a block of ciphertext with same block size given a scheme. If block sizes are too small, it is easier to be broken. If block sizes are too large, the cipher becomes inefficient to encrypt and decrypt. So a preferred block size is a multiple of 8. If the plaintext cannot fit an exact number of blocks say 140 bits cannot fit in three 64 bits block, we will add 22 more redundant bits to complete an additional block, which we call padding. There are many block cipher schemes, such as Data Encryption Standard (DES), Advanced Encryption Standard (AES), and IDEA.

Let’s dive into more details about DES. It is an example of a block cipher, with a block size of 64 bits and a key length of 64 bits, though the effective key length is 56 bits. DES implements a Feistel scheme, and it uses a 16-round round Feistel structure. To construct a DES, we need a key schedule, a Round function (Feistel function), and an Initial and final permutation. The round-key generator creates sixteen 48-bit keys out of a 56-bit cipher key. In each round, the Round function, which is the Feistel function, applies each 48-bit key to the rightmost 32 bits (half block) to produce a 32-bit output. To realize this, expansion, key mixing, substitution, and permutation are applied. To be mentioned, the initial and final permutations are straight Permutation boxes (P-boxes) that are inverses of each other, but they have no cryptography significance in DES.

To comment, the choice of block size does not directly affect the strength of the encryption scheme. The strength of the cipher depends on the key length. In general, It will be fairly easy to construct a block cipher that is cryptographically secure, simply by using a large number of rounds. However, we need to balance the efficiency of the cipher by reducing the number of rounds.

'''Hash function'''

While not a block cipher or even a cipher method, hash functions are an important part of cyber security that should also be mentioned. They have specific encryption methods that called a hash function that creates a unique identifier for the data given to it. Let’s take for example the SHA-1 hash function which acts like a block cipher by separating the message into blocks and then performing the encryption method on each block. This encryption creates essentially another form of the data that allows for it to be recognized without giving away any of the data. From this, it should be impossible to turn it back into the original data. While not useful to send a message, it is good giving a unique identifier to data that is not the data itself.
 
<h1 style="font-size: 30px">4. Asymmetric key</h1>

Asymmetric key cryptography (also called public-key cryptography) is a system that uses a pair of related keys. A pair contains a public key and a private key. The public key is openly distributed and everyone can use the public key to encrypt their message, yielding a ciphertext, but the only way to decrypt a ciphertext is by using the private key. 

There is another popular use of asymmetric keys – the digital signature. Because of the way the algorithm behind the asymmetric key works, the public key, and private key can actually be exchanged, which means whichever key is used to encrypt a message, the other key can always decrypt it. We just call the key we distribute the public key and the one we keep the private key. Digital signature basically to use the private key to encrypt a message and other people can use the public key to decrypt it to prove that you have the accessibility of the private key. 
Sometimes there can be multiple public keys. A private key can generate several public keys and distribute them to different people so that security can be ensured amongst all the public key holders. 

RSA is a relatively slow algorithm. Because of this, it is not commonly used to directly encrypt user data. More often, RSA is used to transmit shared keys for symmetric-key cryptography, which are then used for bulk encryption–decryption. (wiki)
Some examples of asymmetric keys – are RSA, D-H, DSA Elgamal, Knapsack, Rabin, and Elliptic Curve Cryptography.

<h1 style="font-size: 30px">5. Asymmetric key example (RSA)</h1> 

'''General definition'''

Suppose that you want to send your mom a message. If they decide to use RSA, you must know your mom’s public key to encrypt the message, and your mom must use her private key to decrypt the message. To enable you to send your encrypted messages, your mom transmits her public key (n, e) to you via a reliable, but not necessarily secret, route. Your mom’s private key (d) is never distributed. After you obtain your mom’s public key, he can send a message M to your mom. To encrypt this message, you first convert M into an integer m such that 0 ≤ m ≤ n by padding scheme. The following equation how you encrypt m into a ciphertext called c using your mom’s public keys e and n.

<math>c\equiv m^e\ (mod\ n)</math>

If you are not familiar with modular arithmetic, a simple example could be <math>2\equiv11\ \left(mod\ 3\right)</math> where 11 has remainder 2 after it is divided by 3.

After your mom receive the ciphertext c, she wants to recover m from c by using her private key d by computing

<math>
c^d\equiv\left(m^e\right)^d\equiv m\ (mod\ n)
</math>

Once she has m, she can further recover the original message M by reversing the padding scheme.

'''Example'''

Taking a simple example, imagine that the message you want to send to your mom is letter B, letter B can be converted to m = 66 as decimal number from ASCII table. In RSA, n needs to be the product of two prime numbers, say p and q.

Suppose we choose two prime numbers say 3 and 29 as our p and q, which gives us n = p*q = 87 > m as another part of public key. To get e, we need to first compute the Carmichael's totient function of the n

<math>
\phi\left(n\right)=lcm\left(p-1,\ q-1\right)=lcm\left(2,\ 28\right)=28
</math>

Choose any number between 1 and 28, that is co-prime to 28 to be e. Here we can choose e = 5. 
Then to compute d, we do the modular multiplicative inverse of <math>e\ (mod\ (\phi(n)))</math>

<math>
5d\ \left(mod\ 28\right)\equiv1
</math>

Then we can get d can be 45, 101, 157… For simplicity, we can choose d = 45. Since it is hard to find two prime factors for n if n is an enormous number, then it makes RSA hard to crack.

Now we are ready for the encryption process. 
During the encryption part, we 

<math>
c\equiv{66}^5\ (mod\ 87)
</math>

Since 66^5 is very large, then we use Euler’s theorem to simplify the computation

<math>
{66}^5\ \left(mod\ 87\right)\equiv{66}^{1+2\times2}\ \left(mod\ 87\right)\equiv66\times\left(4356\right)^2\ \left(mod\ 87\right)
</math>

<math>
\equiv66\times6^2\ \left(mod\ 87\right)\equiv2376\ \left(mod\ 87\right)\equiv27\ \left(mod\ 87\right)
</math>

Some details: 66^2 = 4356, 4356 = 87*50+6, 2376 = 87*27+27
Then we get c = 27

Suppose we know the private key d = 45, we can start the decryption part.

<math>
{27}^{45} \left (mod \ 87 \right) \equiv {27}^{1+2 \times 22} \left (mod \ 87 \right) \equiv27\times\left(729\right)^{22}\ \left(mod\ 87\right)
</math>

<math>
\equiv27\times\left(33\right)^{22}\ (mod\ 87))\equiv27\times\left(1089\right)^{11}\ (mod\ 87)))
</math>

<math>
\equiv27\times\left(45\right)^{11}\ (mod\ 87)\equiv27\times\left(45\right)^{1+2\times5}\ (mod\ 87))
</math>

<math>
\equiv27\times45\times{2025}^5\left(mod\ 87\right)\equiv27\times45\times{24}^5\left(mod\ 87\right)
</math>

<math>
\equiv27\times45\times{24}^{1+2\times2}\left(mod\ 87\right)\equiv27\times45\times24\times{576}^2\left(mod\ 87\right)
</math>

<math>
\equiv27\times45\times24\times{576}^2\left(mod\ 87\right)\equiv27\times45\times24\times{54}^2\left(mod\ 87\right)
</math>

<math>
\equiv85030560\ (mod\ 87)\equiv66\ (mod\ 87)
</math>

Some details: <math>27^2 = 729, 729 = 87*8+33, 33^2 = 1089, 1089=87*12+45, 45^2=2025, 2025 = 87*23+24, 24^2 = 576, 85030560=977362\times87+66</math>

Finally, we get 66 as our decryption result, which is our m!

'''Proof'''

So what makes RSA work and how can we generate RSA keys?

It all starts with four numbers: n, p, q, 𝜙

<math>n=p⋅q</math>  

<math>𝜙=(p−1)⋅(q−1)</math>

In here, p and q are supposed to be prime numbers.

With these numbers, there is an equation that we call it Euler's theorem and it looks like this: 

<math>m^𝜙 mod n=1</math>

Here some variables are the same as the ones using in the example part above. We have m for the message and n for a part of the key. The 𝜙 isn’t part of the actual encryption/decryption sections but it is still extremely crucial. It is also important to note that in the equation here, m needs to be smaller than n and m,n need to be relatively prime to each other.  

The three professors (RSA) modified this theorem: 

They firstly added a power of k (a random number), and the equation is now like this: 

<math>(m^𝜙)^k mod n = 1^k</math>

<math>m^{𝜙⋅k} mod n = 1 </math>

Since we are trying to figure out an encryption method, what we want the answer to be is actually m itself here. So, we can multiply both part by m and we get: 

<math>({m}^{𝜙⋅k}⋅m) mod n = 1⋅m</math>

<math>m^{𝜙⋅k+1} mod n = m</math>

This means if we do m(message) to the power of 𝜙⋅k+1 and then mod it to n, we can get the same m(message) back! Exactly what we want for an encryption method!


But it's not done yet.


we need to seperate this equation into two parts – one for encryption and one for decryption.  

We can use the idea of e (public key) and d (private key). We want: 

<math>m^e (mod n) = c (cipher)</math>

<math>c^d (mod n) = m</math>

And combine them into one equation: 

<math>(m^e mod n)^d (mod n) ≡ m^{e⋅d} (mod n) =m</math>

We also need to prove this equation is valid, so we can have: 

<math>a = b (mod n)  →  a^d ≡ b^d (mod n)</math>

This is basically how modular arithmetic works. 

<math>Set b = m^e , then a = m^e (mod n)</math>

<math>(m^e mod n)^d ≡ (m^e)^d  (mod n)</math>

<math>(m^e mod n)^d (mod n) ≡ m^{e⋅d} (mod n) </math>

If we compare the equation before with the one we just proved, we can see that the only difference is 𝜙⋅k+1 and e*d, the equations are: 

<math>m^{𝜙⋅k+1} mod n = m^{e⋅d} mod n</math>

To achieve this equation above, we only need: 

<math>m^{𝜙⋅k+1} = m^{e⋅d} </math>

or more specifically, 

<math>𝜙⋅k+1 = e⋅d </math>

Since k is a randomly chosen number, the only property we need to apply here is: 

<math>(e⋅d−1)  mod  𝜙 = 0</math>

which means e⋅d-1 can be divided exactly by 𝜙

So whenever we can fit this rule, the RSA algorithm will be valid. 


Now we can conclude everything:

we want n, e, d to be generated.  

We generate two random (extremely)large primes p and q, then we do

<math>n=p⋅q</math>

<math>𝜙=(p−1)⋅(q−1)</math>

<math>(e⋅d−1)  mod  𝜙 = 0</math>

We can basically generate any e and d based on the p, q we have.  

<h1 style="font-size: 30px">6. Discussion of cybersecurity</h1>

One major thing that was brought up throughout our examples is the use of prime numbers. If you look at modern systems today, very large prime numbers are used to create encryptions, but why is that? Take for example the number: 

131,070,368,271,748,928,392,117,277,094,418,306,663,610,253,813,522,899,176,853

This number is made of multiplying two large prime numbers together. Can you find them?
Did you get:

560,414,063,837,046,769,282,344,474,077

233,881,297,293,532,307,552,036,792,089

	It is a very difficult task to perform a prime factorization when a number is composed of two very large primes. Because of this it makes it very difficult and time consuming to try and derive what the original message is from the cipher. Which takes us back to why we’re talking about this subject.

'''Ethics and Society'''

	Cybersecurity is a field that is constantly evolving, and one part of this field is the arms race between creating encryption methods and breaking existing encryption methods.

Earlier we brought up the example of trying to send a message to your mother and having someone in-between grab your message. The point of this encryption is to make it difficult for bad actors to steal your message. Noticeably, not impossible, but difficult. Encryptions methods can be “broken” meaning there is a better than brute force way to obtain the message from the ciphertext and this happens quite often. The example of the block cipher we showed earlier, DES, is a broken encryption method. Same goes for the Enigma Code or the SHA-1 hash also mentioned above. There are many systems that had to be retired or had security warnings put on them because over time their security strength degrades.

There are a few ethical issues that come up with encryption, such as does it hinder law enforcement, do you have a right to privacy, or does it help or hinder the “common good?” If the FBI wants to get into an iPhone that is encrypted, should they be allowed to? If you commit a crime, is it okay that the details of that crime and in some form encrypted? Does transparency contribute more to the “common good” then privacy does? It all comes down to if it’s okay to hide something. 

Sources:

https://www.scu.edu/ethics/focus-areas/technology-ethics/resources/ethical-questions-about-encryption/ 

https://www.youtube.com/watch?v=5jpgMXt1Z9Y

https://www.tutorialspoint.com/what-are-the-applications-of-rsa-algorithm 

https://www.di-mgt.com.au/rsa_alg.html  

https://en.wikipedia.org/wiki/Enigma_machine 

[[Category:MA279Fall2022Swanson]]