Overview
In the age of the internet, data transmission is everything. It allows us to do things as simple as message 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 in theory that bad. 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 and using a key (possibly different from the original key) decrypts the cipher text back into the original message. Here is a simple example using a basic Caesar cipher to exemplify that idea. This is an extremely basic example of using cryptography to send messages since the actual field is extremely complex. 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.
Symmetric key
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 uses the same value to shift the alphabet for replacement and shift the alphabet back to undo the replacement. Another example of a classical encryption method is transposition cipher where the text is arranged to seem unintelligible, but if you read it in the correct path you can make sense of it. The modern uses fall into the two categories of the stream cipher and the 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. A stream cipher works very simply. For each digit in the data, in the case of a computer a bit, it 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 method, 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.
Symmetric key example
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. Too small block size or too large block size are not good, so a preferred block size is a multiple of 8. If the plaintext cannot fit 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, 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
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 at determining if something exists somewhere.
Asymmetric key
An 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 they only way to decrypt a ciphertext is using the private key. There is another popular use of asymmetric key – the digital signature. Because the way algorithm behind asymmetric key works, 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 signiture is basically to use the private key to encrypt a message and other people can use the public key to decrpt 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 to different people so that the 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 key – RSA, D-H, DSA Elgamal, Knapsack, Rabin, Elliptic Curve Cryptography.
Asymmetric key example (RSA)
General definition
Suppose that you want to send your mom a message. If you 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. 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 obtains 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 key e and n. To enable you send your encrypted message, 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, you 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 key e and n.
$ c\equiv m^e\ (mod\ n) $
If you are not familiar with modular arithmetic, a simple example could be $ 2\equiv11\ \left(mod\ 3\right) $ 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
$ c^d\equiv\left(m^e\right)^d\equiv m\ (mod\ n) $
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
$ \phi\left(n\right)=lcm\left(p-1,\ q-1\right)=lcm\left(2,\ 28\right)=28 $
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 $ e\ (mod\ (\phi(n))) $
$ 5d\ \left(mod\ 28\right)\equiv1 $
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.
Now we are ready for the encryption process. During the encryption part, we
$ c\equiv{66}^5\ (mod\ 87) $
Since 66^5 is very large, then we use Euler’s theorem to simplify the computation
$ {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) $
$ \equiv66\times6^2\ \left(mod\ 87\right)\equiv2376\ \left(mod\ 87\right)\equiv27\ \left(mod\ 87\right) $
Some details: 66^2 = 4356, 4356 = 87*50+6, 2376 = 87*27+27 Then we get c = 27
Supposed we know the private key d = 45, we can start the decryption part.
$ {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) $
$ \equiv27\times\left(33\right)^{22}\ (mod\ 87))\equiv27\times\left(1089\right)^{11}\ (mod\ 87))) $
$ \equiv27\times\left(45\right)^{11}\ (mod\ 87)\equiv27\times\left(45\right)^{1+2\times5}\ (mod\ 87)) $
$ \equiv27\times45\times{2025}^5\left(mod\ 87\right)\equiv27\times45\times{24}^5\left(mod\ 87\right) $
$ \equiv27\times45\times{24}^{1+2\times2}\left(mod\ 87\right)\equiv27\times45\times24\times{576}^2\left(mod\ 87\right) $
$ \equiv27\times45\times24\times{576}^2\left(mod\ 87\right)\equiv27\times45\times24\times{54}^2\left(mod\ 87\right) $
$ \equiv85030560\ (mod\ 87)\equiv66\ (mod\ 87) $
Some details: $ 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 $
Finally, we get 66 as our decryption result, which is our m!
Application & pros and cons (Yuke, Yiheng)
Discussion of cybersecurity
how big prime we use? Broken cryptosystem
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 only 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.
