Part 1: Introduction | Public-Key Cryptography
Furkan Akal
Hello everyone! Welcome to the first part of the public-key cryptography series! This series of posts is intended to give the basics of cryptography and specifically public-key encryption. In each post (coming after this one), you’ll find some code snippets (written in Rust) to support the given mathematical idea. At the end of the series, I’m aiming to provide readers with;
basic understanding of cryptography,
mathematical fundamentals of public-key cryptography,
a concise Rust code to generate the keys, apply the relevant mathematical operations, and encrypt/decrypt a message.
Contents
What is cryptography?
- Terminology
Historical Background
Ancient Origins
Middle Ages to Renaissance
The Age of Mechanical Devices
The Modern Era
Types of Cryptography
Symmetric Cryptography (Private-Key Encryption)
Aysmmetric Cryptography (Public-Key Encryption)
Cryptanalysis
- Methods
Conclusion
What is cryptography?
Cryptography is a branch of mathematics focusing on the development of techniques for secure communication. Main goal is to protect the privacy and integrity of any information from third parties.
The word comes from Greek kryptós, meaning "secret," and graphein, meaning "to write." It may be translated as “secret writing”.
Terminology
Plaintext: It is the original, readable, and unencrypted data or message.
Ciphertext: It refers to the encrypted data or message produced by the encryption process. It’s supposed to be unreadable or unintelligible to unauthorized individuals.
Key: It is a piece of information, usually a string of characters, that determines the functional output of a cryptographic algorithm.
Encryption: It is the process of converting plaintext into ciphertext. It involves using a cryptographic algorithm and a key to transform the readable data (plaintext) into an unreadable format (ciphertext).
Decryption: It is the reverse process of encryption. It involves converting ciphertext back into its original plaintext form.
Historical Background
Ancient Origins
The use of cryptography dates back to ancient civilizations. The earliest known use was in Egypt, around 1900 BCE, where hieroglyphs were used in an unusual way, possibly to hide the actual message.
The Greeks and Romans also advanced some cryptographic techniques. The most popular example is the Caesar cipher which I'll give more details in the upcoming sections of this post.
The Middle Ages to Renaissance
The Arab mathematician, Al-Kindi, in the 9th century, wrote a manuscript on deciphering encrypted messages, introducing frequency analysis to break substitution ciphers.
During the Renaissance, European cryptographers developed more sophisticated methods for encryption like the [Vigenere cipher](https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher#:~:text=The%20Vigen%C3%A8re%20cipher%20(French%20pronunciation,of%20another%20text%2C%20the%20key.), a method using a series of different Caesar ciphers based on the letters of a keyword.
The Age of Mechanical Devices
The most popular example would be German's Enigma machine that is used during World War II. It employed a complex system of rotors and electrical circuits to encrypt messages.
The Modern Era
Following the advancement in computer technology, science of cryptography had also a major transformation. In the 1970s, the Data Encryption Standard (DES) was developed by IBM.
One of the most groundbreaking development was the introduction of public-key cryptography in the 1970s by Whitfield Diffie and Martin Hellman. It solved the problem of secure key distribution which was significant limitation back then.
Types of Cryptography
Cryptography is mainly divided into two paradigms:
Symmetric cryptography (private-key encryption)
Asymmetric cryptography (public-key encryption)
Symmetric Cryptography
In symmetric cryptography, the same key is used for both encryption and decryption.
Flow:
Alice encrypts her message (plaintext) using the key and sends it to Bob.
Bob receives the encrypted message (ciphertext), decrypts it using the same key, and then reads it.
Example: Caesar Cipher
Caesar cipher, also known as the shift cipher, is one of the simplest and most widely known encryption techniques. Each letter in the plaintext message is shifted forward in the alphabet by the key number of places. If the shift takes you past 'Z', you wrap around to the start of the alphabet. For example, with a shift of 3:
'HELLO' becomes 'KHOOR'.
'CAESAR CIPHER' becomes 'FDHVDU FLSKHU'.
In order to decrypt a ciphertext, the same process is applied backwards.
As you might have noticed;
Encrypting function: Shifting the letters forward:
where
x = index of the letter in the alphabet,
n = number of shifting.
Decrypting function: Shifting the letters backwards:
where
x = index of the letter in the alphabet,
n = number of shifting.
Key: How many times the number will be shifted:
Limitation
Both parties are responsible with protecting secrecy of the key as well, in addition to the encrypting and decryption functions.
Asymmetric Cryptography
In asymmetric cryptography, different keys are used for encryption and decryption.
Private Key: It is used for decryption. Private keys must be kept secure and confidential by its owner.
Public Key: It is used for encryption and generated from private keys. Public keys can be distributed widely.
We will dive into more details of these in the 3rd post of this series, keys.
Flow
Alice encrypts her message (plaintext) using Bob’s public key, and sends it to Bob.
Bob receives the encrypted message (ciphertext), decrypts it using his own private key, and then reads it.
Formal Expression
Encryption process:
where
E: encrypting function,
pub: public key of the recipient,
m: message to be encrypted,
c: encrypted message or ciphertext.
Decryption process:
where
D: decrypting function,
priv: private key of the recipient,
c: ciphertext to be decrypted,
m: decrypted message (plaintext).
Crucial point here is that the following equation must be satisfied for all messages:
If this equation holds, then the decrypting function can always be used consistently.
Cryptanalysis
Cryptanalysis is the study of analyzing information systems to understand the hidden aspects. It’s primarily used to break cryptographic security systems and gain access to the contents of encrypted messages, even if the cryptographic key is unknown.
Methods
Brute Force Attack: It involves trying every possible key until the correct one is found. Although it’s simple, it can be extremely time-consuming for systems with large key spaces.
Frequency Analysis: Recall the Caesar cipher, which is a type of substitution ciphers, that the letters in the message were shifted according to the key. This method involves studying the frequency of letters or groups of letters in a ciphertext. I't’s effective against simple substitution ciphers where certain letters or patterns occur more frequently.
Side-Channel Attacks: These attacks exploit information gained from the physical implementation of a cryptosystem, such as timing information, power consumption, electromagnetic leaks, or even sound.
Conclusion
In this post, I’ve tried to explain some fundamental concepts in basic cryptography and their historical background.
As progress in this series, we will dive deeper into the mathematical underpinnings of public-key cryptography and explore practical implementations using Rust. My aim is not just to understand the theoretical aspects but also to see how these concepts come to life in code.
Image Reference
https://makeameme.org/meme/crypto-means-cryptography
https://en.wikipedia.org/wiki/Enigma_machine#/media/File:Enigma-plugboard.jpg
Subscribe to my newsletter
Read articles from Furkan Akal directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by