Cryptography: Under the Hood

Cryptography is a process of converting a plain/clear text into cipher/unreadable text and vice-versa. It’s a method to keep information secret and unintelligible to unauthorized users. In this article, I will not spend too much time talking about the specific algorithms/ciphers. Without further ado, let’s take a deep dive into cryptography…

Hashing

It is a string or number that is generated from a string of text. The hash function will always return the same length of output, and the output will always be the same for a given input. So, whether the input is “1”, “A” or “Today is a sunny day!” the length of the output will stay the same.  Here is an example using SHA256:

Input:

·         1

·         A

·         Today is a sunny day!

·         Today is a Sunny day!

Output:

19a365f45a230083f170074b49072583c406ce5e20fa5929201d3f5d1be914a5

e1ac082a61516f4be1718e23fe4dc328057eb9effa544b3765e4122191b315c9

237a6e01bf816ba5a603d10ce8f985a5a77001d0c961c1c67f3c2c7a604a32be

f5f2299adf6c9a2801fbcb5f810e6e7e927b7e7eb266131114cb24a003fb4efc

One of the most important aspects of a hash function is that it is “one way”. In other words, it is not possible to use the hash output to determine what the input was. The hash algorithm is considered broken and insecure if you are able to reverse it. Another detail to note is that even replacing a lower case “s” with an upper case “S” will completely change the hash as the example above points out.

Use cases:

1.     Storing and protecting passwords – Being that hashing is one way, it would be very difficult for someone to reverse it. However, what adversaries typically do is perform a rainbow table attack. This table contains a large pre-computed dictionary of hashes and the passwords from which they were pre-computed. This is very efficient way to “brute force” password hashes. One method to slow this attack down is to use a salt when hashing passwords. A salt is random value added to hash function.

2.     Comparing an input with stored value. Think of comparing hashes of newly downloaded software on your PC to ensure the software is legit.

Encryption

There are two types of encryption – symmetric and asymmetric. Symmetric encryption/algorithm also known as “secret key” use the same key to both encrypt and decrypt data. Both sender and recipient must know the secret key. The main disadvantage with this encryption method is the key distribution as it must be exchanged between the sending and receiving individuals. The most popular symmetric algorithm used today is Advanced Encryption Standard (AES - 128-bit, 192-bit, and 256-bit).

Asymmetric encryption is also known as Public Key Cryptography (PKI) which uses different keys to encrypt and decrypt data. This key pair is known as public/private pair and is comprised of two mathematically related cryptographic keys. You can share/publish your public key with anyone publicly, but your private key must be kept secret and known only to you. We can encrypt things to the public key, and then only the private key can decrypt it.

One approach to distribute public keys is by using digital certificates – client-server model. The certificate contains information that identifies an organization along with a public key. One of the most popular asymmetric algorithms is RSA.

Digital Signatures

A digital signature can only be created with a private key, and then your public key can be used to verify that your private key was indeed used to create it.  The digital signature proves that the signer is who they claim to be. Only the signer should have access to the private key, thus proving that they were indeed the signer. Digital signature provides no encryption. One of the most popular digital signature algorithms is ECDSA.

Let’s walk through two examples to see how cryptography works under the hood using RSA algorithm…

1.       How can we create a private and public key; then encrypt a message with a private key and decrypt it with a public key.

2.       How can we use our private key to digitally sign some text, and then use our public key to verify that we indeed signed it. This process proves that we own the private key, but it does not reveal our private key to anyone else.

Let’s start….

1.

Ø  We need to choose 2 prime numbers, p and q. To make this very simple, let’s choose small numbers. In reality, your prime numbers would be very large.

p= 337

q= 255

Ø  Now the product of p and q is n (n=p*q), so let’s calculate it:

n = 337 x 255 = 85,935

Ø  Next, we need to calculate the euler totient using the following formula:

φ(n) = (p-1) * (q-1)

φ(n) = (337-1) * (255-1) = 336 * 254 = 85,344

Ø  The next step is to choose another prime number (e). This prime number must be relatively prime (no common positive divisors except 1) to the above equation. Let’s choose “e” to be 19.

Ø  Now we have our public key created, which is the pair of “e” and “n”. In reality, your public key would be a very long number.

Public key: n = 85,935, e = 19

Ø  Our next step is to find a value for d.  This value must be chosen so that is the inverse of e, modulo n.  To do so, we will use the following formula:

e * d [=] 1 mod φ(n) (online calculators available)

19 * d [=] 1 mod 85,344

In other words, 19 * d / 85,344 must give us a reminder of 1. In order to calculate this, one must use the Extended Euclidean algorithm *(ax + by = gcd(a, b)* . In our case the number 22,459 works.

19 x 22,459 = 426,721

426,721 / 85,344 = 5 (reminder 1)

Ø  Now we have calculated everything we need to encrypt and decrypt data…

p=35

q=27

n=85,935

φ(n)= 85,344

e=19

d=22,459

Public Key: n and e

Private Key: n and d

How can we use these keys to encrypt and decrypt data?

Ø  Let’s give out our public key to someone to send us encrypted message (n and e pair). Once they receive our key, they will use the following formula to encrypt the message:

C=M^e mod n (modular exponentiation – online calculators available)

Ø  In this case “C” represents our encrypted message. To continue keeping it simple, let’s send a single character “z” as our encrypted massage, whose value is 7537.

Ø  Let’s apply the formula above:

C=7537^19 mod 85,935

                = 43498

Ø  Now let’s send this encrypted message to the server that contains a private key.

Ø  The formula to decrypt this message is the following:

M = C^d mod n (modular exponentiation)

Ø  In our case it will be:

M = 43498^22459 mod 85935

                = 7537 (= ”z”)  (Successfully decrypted)

2.

How can we use the public/private key pair to sign a message…

Ø  Let’s choose the following sentence to be digitally signed “My password is password1”

Ø  First, we need to create a message digest (hash) of the information we want to send. The information we want to send is “My password is password1” – and here is the hash using SHA-1:

96e5848f249022d1911b2e73115825d8cead6845

Ø  Now we need to represent this hash as an integer. This integer must be between 1 and n-1. Let’s choose 7113.

Ø  Now we need to use our private key to compute the signature. The formula we will use is:

Signature = hash^private key mod n (modular exponentiation)

Signature = 7113^22459 mod 85935 (online calculators available)

Signature = 17337

Ø  Now when recipient wants to validate the signature to ensure the message did not change, they will have to use the sender’s public key to compute integer using the following formula:

Validation = signature^19 mod 85935 (modular exponentiation)

Validation = 17337^19 mod 85935

Validation = 7113 (This proves that message was not modified in any way)

It is the math that makes cryptography possible – the math is the heart of cryptography.  And remember, hashing does not equal encryption, but we often hear these terms used interchangeably. With encryption, one needs a key(s) to encrypt and decrypt data. With hashing on the other hand, there is no keys involved.

 

Being that blockchain and crypto-currencies are the hot topic – one must understand hashing, private/public key, and digital signatures to truly understand how these technologies work. The signature algorithm used by bitcoin is called Elliptic Curve Digital Signature Algorithm (ECDSA). ECDSA is asymmetric-key algorithm (private/public key pair) used to produce/verify signatures. While SHA-256 hashing algorithm is used to create bitcoin addresses, chain blocks, etc.