Zero Knowledge Proofs Series #6 [Cryptographic Key Exchanges & Elliptic Curves I ]
Tags: zeroknowledge, zkp, ellipticurve, cryptography
Published: 2024-03-18 20:29:06

## History of Cryptography and its Relation to Today -_"The past is the key to the future - Unknown"_

Cryptography, the art of protecting information, boasts a long and fascinating history. This breakdown explores its evolution, focusing on the shift from symmetric to asymmetric methods and the importance of key exchange.

### Early Ciphers

* **1700 BC:** Egyptians utilized  Hieroglyphics: [https://en.wikipedia.org/wiki/Egyptian_hieroglyphs](https://en.wikipedia.org/wiki/Egyptian_hieroglyphs) - a writing system for inscriptions on walls, tombs, and more. While not a true cipher, it offered obscurity to those unfamiliar with the system.
* **50 BC:** Julius Caesar employed a simpler method -  the Caesar cipher: [https://dev.to/anasnmu/caesar-cipher-and-javascript-1kl1](https://dev.to/anasnmu/caesar-cipher-and-javascript-1kl1). This involved shifting letters by a fixed number of positions.
* **16th Century:** The Vigenère cipher emerged, offering more sophistication. It used a keyword to determine the shift value for each letter, creating a more complex pattern compared to the Caesar cipher.
* **World War II:** The Enigma machine, used by Nazi Germany, was an electro-mechanical marvel that employed rotors and plugboards for complex encryption. Breaking Enigma provided crucial intelligence to the Allies.

### A Comparison of Ciphers

| Cipher | Description | Strengths | Weaknesses | Historical Context |
|---|---|---|---|---|
| Caesar Cipher | Shifts plaintext letters by a fixed number of positions. | Simple to implement. | Extremely weak, vulnerable to frequency analysis. | Used by Julius Caesar and throughout history for simple communication. |
| Vigenère Cipher | Uses a keyword to determine the shift value for each letter. | More secure than Caesar cipher due to varying shifts. | Vulnerable to frequency analysis of long texts and statistical techniques to identify keyword patterns. | Developed around the 16th century. |
| Enigma Machine (WWII) | Electro-mechanical cipher device with complex encryption. | Highly complex and dynamic, initially very difficult to crack. | Relied on predictable elements like rotor settings, which were eventually exploited. | Used by Nazi Germany during World War II. |
| Egyptian Hieroglyphs | A writing system using pictures (hieroglyphs) to represent words or sounds. | Visually appealing, offering some obscurity to those unfamiliar with the system. | Not a true cipher, but can be used for limited secret communication. Deciphering requires knowledge of the language and hieroglyphic meanings. | Developed around 3200 BC. |

**Note:** All the ciphers mentioned above are symmetric in nature. This means for nearly 4,000 years, cryptography functioned in a similar way.

### The Rise of Asymmetric Cryptography

In 1975, the first form of asymmetric cryptography was created. This revolutionary approach utilizes a key pair:

* **Public Key (Pb):** Known to everyone, similar to a mailbox address.
* **Private Key (Pb):** Kept secret, like a key to open the mailbox.

Information encrypted with the public key can only be decrypted with the corresponding private key, eliminating the need for secure key distribution.

**Examples of Key Exchange with Asymmetric Cryptography**

* **Secure Email:** When you send an encrypted email, you use the recipient's public key to encrypt the message. Only their private key can decrypt it, ensuring confidentiality.
* **HTTPS:** Secure websites (indicated by the padlock symbol and "https" in the address bar) establish secure connections using asymmetric cryptography. The website's public key encrypts communication, and your browser uses trusted certificates to verify its authenticity.

Symmetric key cryptography offers efficient bulk encryption, while asymmetric cryptography allows for secure key exchange and digital signatures. We still use both methods today.

### Exploring Terminology: Symmetric vs. Asymmetric Cryptography

**Scenario:** Imagine Alice has a secret message (X) for Bob, and Beatrice is eavesdropping.

**Symmetric Encryption:**

1. **Choose a Shift Value:** Decide on the number of positions to shift letters (e.g., 3 positions).

2. **Encryption:** Find the plain text letter on the inner circle (Plaintext Alphabet) and look at the corresponding letter on the outer circle (Ciphertext Alphabet) for the encrypted letter.

   - Example message: "HELLO" becomes "LHORO" with a shift value of 3.

3.**Decryption:** Reverse the process using the same shift value to return to the original message.

> Choose a Shift Value: This is the number of positions you'll move each letter. In our example, let's use a shift value of 3.
> Encrypting a Message: Find the plain text letter on the inner circle (Plaintext Alphabet). Look at the corresponding letter on the outer circle (Ciphertext Alphabet) - that's your encrypted letter!
> For instance, if your message is "HELLO", follow these steps:
> H -> L (Move 3 positions to the right)
> E -> H
> L -> O
> L -> O
> O -> R
> The encrypted message becomes "LHORO".
> Decoding a Message:
> The decryption process is simply the reverse. Use the same shift value but move in the opposite direction on the Caesar Cipher disc. So, to decode "LHORO" with a shift value of 3:
> L -> H (Move 3 positions to the left)
> H -> E
> O -> L
> R -> L
> O -> O
> This gets you back to the original message "HELLO".




## Asymmetric Encryption (Continued)

**Public Key (Pb) and Private Key (Pb):**

* **Public Key (Pb):** This key is available to everyone, including Alice, Beatrice, and even Eve. It's like the mailbox address – anyone can find it.
* **Private Key (Pb):** This key is like a secret key to open the mailbox – only Bob keeps it safe. No one else has access to it.

**Sending the Love Notes**

1. **Alice Encrypts Her Message:** Alice gets hold of Bob's public key (Pb). She uses this key like a special lock to encrypt her message (X) with a complex mathematical algorithm. This transforms her message into an unreadable format, like a love note written in a secret code (Ciphertext, C).
   * Importantly, only Bob's private key can decrypt messages encrypted with his public key. Even if Eve intercepts the encrypted message (C), she cannot decipher it without Bob's private key.

2. **Sending the Encrypted Note:** Alice discreetly sends the encrypted message (Ciphertext, C) to Bob.

3. **Beatrice Does the Same:** Beatrice follows Alice's lead. She also gets Bob's public key (Pb) and encrypts her message (Y) for Bob using the same encryption process. She sends her encrypted love note (Ciphertext, D) to Bob as well.

**Bob Reads the Secret Messages**

1. **Decrypting the Notes:** Bob, the lucky recipient, receives the encrypted messages (Ciphertext, C and D) from Alice and Beatrice. He uses his own private key (Pb), like the secret key to his mailbox, to decrypt each message.

2. **Revealing the Secrets:** The decryption process unlocks the true messages (X and Y) from Alice and Beatrice. Now Bob can finally read their heartfelt confessions!

**The Power of Asymmetry**

* **Secure Communication:** Asymmetric cryptography ensures that only Bob, with his private key, can decrypt the messages encrypted with his public key. This keeps the messages confidential, even if Eve intercepts them.
* **No Risky Key Sharing:** Unlike traditional methods where a shared key needs to be distributed securely, here Bob's public key can be shared freely. Only his private key can unlock the messages.

## Future Exploration

In the next part, we'll delve into:

* **Elliptic Curve Cryptography (ECC):** Explore the math behind this efficient and secure asymmetric cryptography method.
* **Different Forms for Elliptic Curves for the right use-cases**  

This concludes the basic explanation of cryptography. As you can see, cryptography plays a vital role in protecting information in our digital age. By understanding its evolution and different methods, we can appreciate its significance and use it responsibly.