What is Cryptography?

  Cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Various aspects of information security such as data confidentiality, data integrity, authentication, and non-repudiation are central to modern cryptography.

Prior to the modern age, cryptography was effectively synonymous with encryption, the conversion of information from a readable state to apparent nonsense.

Modern cryptography is heavily based on mathematical theory and computer science. Cryptographic algorithms are designed around computational hardness assumptions, making the algorithms hard for adversaries to break.

There exist information-theoretically secure schemes that probably cannot be broken even with unlimited computing power.

Caesar Cipher

The Caesar cipher is one of the earliest known and simplest ciphers. It is a type of substitution cipher in which each letter in the plaintext is shifted to a certain number of places down the alphabet. For example, with a shift of 1, A would be replaced by B, B would become C, and so on. The method is named after Julius Caesar, who allegedly used it to communicate with his generals.

Here is a quick example of the encryption and decryption steps involved with the Caesar cipher. The text we will encrypt is "defend the east wall of the castle," with a shift (key) of 1.

Plaintext: "defend the east wall of the castle"

Ciphertext: "efgfoe ulf fbtu xbmm pg uif dbtumf"

It is easy to see how each character in the plaintext is shifted up the alphabet. Decryption is just as easy, by using an offset of -1.

Vigenère cipher

The Vigenère cipher is a method to encrypt alphabetic text by using the position of the letter of the input on the key. The key is a word decided by the user and is kept secret.

The message cannot be decrypted without the key.

Let's encrypt the word "sololearn" with the key "web".

Word: sololearn

Key: web

Encrypted message: osmwpfwvo

The explanation follows:

webwebweb

solo learn

W+s=0 e+0=s

b+1=m

W+0=W

b+e=f

w+a=w

e+r=v

b+n=0

Hashing

Hashing means generating value or values from a string of text using a mathematical function.

Hashing is one way to enable security during the process of message transmission when the message is intended for a particular recipient only. A formula generates the hash, which helps to protect the security of the transmission against tampering.

When a user sends a secure message, a hash of the intended message is generated and encrypted and is sent along with the message. When the message is received, the receiver decrypts the hash as well as the message. Then, the receiver creates another hash from the message. If the two hashes are identical when compared, then a secure transmission has occurred. This hashing process ensures that an unauthorized end user does not alter the message.

Here is a small example in Python that encrypts "Hello World" in SHA-1 (Secure Hashing Algorithm):

Hashed Password

When Alice logs into a host computer (or a telephone banking system, or any other type of terminal), how does the host know who she is? How does the host know she is not Eve trying to falsify Alice's identity? Traditionally, passwords solve this problem. Alice enters her password, and the host confirms that it is correct. Both Alice and the host know this secret piece of knowledge, and the host requests it from Alice every time she tries to log in.

The host does not need to know the passwords; the host has to be able to differentiate valid passwords from invalid passwords. This is easy with one-way functions. Instead of storing passwords, the host stores hashes of the passwords.

Procedure:

1. Alice sends the host her password.

2. The host performs a one-way function (hashing) on the password. 3. The host compares the result of the hashing to the value it previously stored.

Since the host no longer stores a table of everybody's valid passwords, the threat of someone breaking into the host and stealing the password list is mitigated.

Salted Passwords

In the previous lesson, we explained why it is better to store hashed passwords. But a file of passwords encrypted with a hash function is still vulnerable. Let's imagine that a hacker compiles a list of the million most common passwords. He operates on all the million of them with the hash function and stores the results. Now, the hacker steals a list of hash values stored in the database. He compares that list with his list of encrypted possible passwords and discovers possible matches.

This is called a dictionary attack. Salt is a way to make it more difficult.

Salt is a random string that is concatenated with the password before hashing it. Both the salt value and the result of the hash function are stored in the database on the host. If the number of possible salt values is large enough, this practically eliminates a dictionary attack against commonly used passwords because the hacker has to generate the one-way hash for each possible salt value.

Methods of Encryption

Symmetric encryption

Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both encryption of plaintext and decryption of ciphertext. Both parties are required to have access to the secret key, so this is one of the main drawbacks of symmetric key encryption.Asymmetric encryption

Asymmetric cryptography 

(or public-key cryptography) is any cryptographic system that uses pairs of keys: public keys which may be disseminated widely, and private keys which are known only to the owner.

This accomplishes two functions: authentication, where the

public key verifies that a holder of the paired private key sent the

message, and encryption, where only the paired private key holder

can decrypt the message encrypted with the public key.

Symmetric Encryption

Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both encryption of plaintext and decryption of ciphertext.

The earliest and simplest example of a symmetric cipher is the Caesar cipher. It is a type of substitution cipher in which each character in the plaintext is replaced by a character some fixed number of positions up or down the alphabet. Let's see how it works in a code example.

For example, if we choose the encryption key as the "right shift by 3" it would be:

AES (Advanced Encryption Standard)

The Advanced Encryption Standard, or AES, is a symmetric block cipher chosen by the U.S. government to protect classified information and is implemented in software and hardware throughout the world to encrypt sensitive data.

NIST (The National Institute of Standards and Technology) specified that the new advanced encryption standard algorithm must be a block cipher capable of handling 128 bit blocks, using keys sized at 128, 192, and 256 bits. Other criteria for being chosen as the next advanced encryption standard algorithm included security, implementation and cost. Intended to be released under a royalty-free basis, the candidate algorithms were to be evaluated on computational and memory efficiency.

AES comprises three block ciphers: AES-128, AES-192 and AES-256. Each cipher encrypts and decrypts data in blocks of 128 bits using cryptographic keys of 128-, 192-, and 256-bits, respectively.

Symmetric ciphers use the same key for encrypting and decrypting, so the sender and the receiver must both know (and use) the same secret key. There are 10 rounds for 128-bit keys, 12 rounds for 192-bit keys, and 14 rounds for 256-bit keys. A round consists of several steps including substitution, transposition, mixing of the input plain text, and transforming it into the final output of cipher text.

For example, the "Hello, world!" encrypted in AES-128 is "AOuS61U0LrJOfnXsO4HCgg==".

Asymmetric Encryption

Public-key cryptography (asymmetric cryptography) is any cryptographic system that uses pairs of keys: public keys which may be disseminated widely, and private keys which are known only to the owner. This accomplishes two functions: authentication, where the public key verifies that a holder of the paired private key sent the message, and encryption, where only the paired private key holder can decrypt the message encrypted with the public key.

Public key algorithms are fundamental security ingredients in cryptosystems, applications, and protocols. Some encryption schemes can be proven secure on the basis of the presumed difficulty of a mathematical problem, such as factoring the product of two large primes or computing discrete logarithms.

Some examples of asymmetric key encryption:

 - Diffie-Hellman key exchange protocol

 - DSS (Digital Signature Standard)

 - Various password-authenticated key agreement techniques

 - RSA encryption algorithm

Diffie-Hellman Key Exchange Protocol

Diffie-Hellman key exchange (DH) was the first public-key algorithm ever invented (1976). It gets its security from the difficulty of calculating discrete logarithms in a finite field, as compared with the ease of calculating exponentiation in the same field.

Diffie-Hellman can be used for key distribution. Alice and Bob can use this algorithm to generate a secret key, but it cannot be used to encrypt and decrypt messages. So it is known as the "Diffie–Hellman Key Exchange Protocol."

The goal is for Alice and Bob have a mutual secret key without using a secure channel or a secure meeting (note that they can't see each other face to face).

First, Alice and Bob agree on a large primes, n and g, such that g is primitive mod n (in modular arithmetic, a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n). These two integers don’t have to be secret; Alice and Bob can agree to them over some insecure channel. They can even be common among a group of users. It doesn’t matter. Then, the protocol goes as follows:

1. Alice chooses a random large integer x and sends to Bob X that is calculated as follows:

X = g^x(mod n)

2. Bob chooses a random large integer y and sends to Alice Y that is calculated as follows:

Y = g^y(mod n)

3. Alice computes k as follows:

k = Y*x(mod n)

4. Bob computes k´ as follows:

k´ = X*y(mod n)

Both k and k´ are equal to g^(x*y) mod n. No one who is listening on the channel can compute that value; they only know n, g, X, and Y. Unless they can compute the discrete logarithm and recover x or y, they cannot solve the problem. So, k is the secret key that both Alice and Bob computed independently and we’ve reached the goal.

RSA (cryptosystem)

RSA is one of the first public-key (asymmetric) cryptosystems and is widely used for secure data transmission. RSA stands for Rivest-Shamir-Adleman, initial letters of the surnames of its creators. This asymmetry is based on the practical difficulty of the factorization of the product of two large prime numbers, the "factoring problem".

Here's how key generation works:

1. Choose two distinct prime numbers, p, and q.

2. Compute n = p * q. n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.

3. Compute λ(n) = least_common_multiple(p − 1, q − 1). This value is private.

4. Choose an integer e such that 1 < e < λ(n), e and λ(n) are coprime.

5. Determine d from d * e ≡ 1 (mod λ(n)).

e is released as the public key exponent.

d is kept as the private key exponent.

Key pair

public key: (e, n)

private key: (d, n)

Currently, the standard sizes for RSA keys are as follows:

512 bits - Low-strength key

1024 bits - Medium-strength key

2048 bits - High-strength key

4096 bits - Very high-strength key

Suppose that Bob wants to send information to Alice. If they decide to use RSA, Bob must know Alice's public key to encrypt the message and Alice must use her private key to decrypt the message. To enable Bob to send his encrypted messages, Alice transmits her public key (n, e) to Bob via a reliable (not necessarily secret) channel. Alice's private key (d) is never distributed.

Let's try to generate very simple key pair:

1. p = 61 and q = 53

2. n = 61 * 53 = 3233

3. λ(n) = lcm(p-1, q-1) = lcm(60, 52) = 780

4. e = 17 (1 < e < λ(n), e and λ(n) are coprime)

5. d = 413 (d * e mod λ(n) = 1)

public key: (n = 3233, e = 17)

private key: (n = 3233, d = 413)

We generated the key pair. We need the public key (n, e) to encrypt plaintext. Let's assign plaintext to m and the ciphertext to c; then ciphertext will be:

c = m ^ e mod n

For example, if our plaintext m = 65, then:

c(m) = 65 ^ 17 mod 3233 = 2790

To decrypt the ciphertext with the private key (n, d), we should use this:

m(c) = c ^ d mod n = 2790 ^ 413 mod 3233 = 65

Digital signature

Imagine that Alice wants to send a message to Bob. The system uses RSA encryption, and no one can read the message because the message is encrypted. How can Bob know that the message came correctly from Alice? A digital signature can help.

A digital signature is a mathematical scheme for presenting the authenticity of digital messages or documents. A valid digital signature gives a recipient reason to believe that the message was created by a known sender (authentication).

Digital signatures are standard elements of most cryptographic protocol suites and are commonly used for software distribution, financial transactions, and contract management software.

So how does it work?

One of the methods is to encrypt a special tag (which can include your name, ID, or any other personal information) with your private key, which can be decrypted only with your public key and send the tag with your message. Then the receiver can check the authenticity using the sender's public key.

Another method is to get the hash code of your message and decrypt it with the private key, and then send it with the message. This method also gives you a chance to check the message’s completeness. As we saw in the hashing lesson, if we change even one character from the message, the hash function gives us an entirely different hash code.

--------------------->END OF Cryptography<------------------