Cryptography

1. Cryptography's Core Purpose & Basic Concepts

The idea of a cipher system is to disguise confidential information in such a way that its meaning is unintelligible to an unauthorized person.

Disguising information. Cryptography is the science of scrambling plaintext messages into unintelligible ciphertext using an encryption algorithm and a key. The intended recipient uses a decryption algorithm and key to recover the original message. This protects information during storage or transmission over insecure channels like the internet.

Basic terminology. Key terms include plaintext (original message), encryption (scrambling), ciphertext (scrambled message), decryption (unscrambling), algorithm (the rules), and key (secret information controlling the algorithm). Cryptanalysis is the art of breaking ciphers without the key, while cryptology encompasses both cryptography and cryptanalysis.

Security depends on keys. The security of a cryptographic system fundamentally relies on keeping the decryption key secret. Attackers, or interceptors, are assumed to know the algorithm and have access to ciphertext, making key secrecy paramount. Good key management is therefore critical.

2. Symmetric vs. Asymmetric: The Key Difference

One important fact that should already be clear from our introduction is that knowledge of the encryption key is not necessary for obtaining the message from the cryptogram.

Shared secret vs. key pair. Cryptographic systems divide into two types based on key relationship. Symmetric (or secret key) systems use keys where decryption is easily derived from encryption (often they are the same), requiring sender and receiver to share a secret. Asymmetric (or public key) systems use a pair: a public encryption key and a private decryption key, where the private key cannot be practically deduced from the public one.

Trust and distribution. Symmetric systems require a secure way to distribute the shared secret key before secure communication can begin, necessitating mutual trust. Asymmetric systems allow the encryption key to be public, removing the need for a shared secret initially and enabling secure communication between parties who don't necessarily trust each other beforehand.

Different applications. Symmetric algorithms are typically faster and used for encrypting large volumes of data. Asymmetric algorithms are slower but are essential for applications like digital signatures and securely distributing symmetric keys, leveraging the unique property that only the private key holder can decrypt data encrypted with the corresponding public key.

3. Early Ciphers Were Simple and Statistically Vulnerable

From the numerous examples discussed in the last sections it is clear that there are many factors that influence an attacker’s chances of breaking a cipher system.

Simple substitutions. Early ciphers like the Caesar cipher (a simple letter shift) or Simple Substitution ciphers (each letter replaced by another fixed letter) were easy to describe and implement manually. While Simple Substitution ciphers have a vast number of keys (26!), they are weak.

Exploiting language structure. These ciphers are vulnerable because they preserve the frequency characteristics of the underlying language. Attackers can analyze ciphertext letter frequencies and compare them to known language statistics (like English letter frequencies: E, T, A, O, I, N, S, H, R, D, L, U).

• English letter frequencies are highly uneven (E is most common).
• Simple Substitution maps one letter frequency to another.
• Analyzing common letters and patterns (like 'THE') can reveal the key.

Polyalphabetic improvements. Ciphers like the Vigenère cipher (using multiple Caesar shifts based on a keyword) aimed to flatten frequency distributions by having one plaintext letter map to different ciphertext letters depending on its position. However, repeating keywords introduced periodicity, which could be detected (e.g., Kasiski test) and exploited.

4. The Myth & Reality of Unbreakable Ciphers

A system that achieves this objective is said to offer perfect secrecy, and we now give a small example to show that perfect secrecy is achievable.

The quest for unbreakable. Historically, many cipher designers believed their creations were unbreakable, often leading to their eventual compromise (e.g., Mary Queen of Scots' cipher, Enigma). The belief in strength often stemmed from complex mechanisms or a large number of keys, but overlooked cryptanalytic techniques or implementation flaws.

Perfect secrecy defined. Perfect secrecy means that observing the ciphertext gives an attacker no additional information about the plaintext beyond what they already knew. It doesn't prevent guessing the message, but ensures the ciphertext doesn't help. This is theoretically achievable.

The One-Time Pad. The only known perfectly secure cipher is the One-Time Pad (OTP). It uses a random key sequence as long as the message, used only once. Encryption is typically XORing plaintext bits with key bits. Decryption is the same. Its security relies entirely on the key's randomness, secrecy, and single use. However, distributing and managing such long, truly random keys for every message is practically infeasible for most applications, limiting its use to highly sensitive, low-volume communication.

5. Modern Symmetric Ciphers Operate on Bits and Use Complex Modes

As we stressed earlier, most modern ciphers do not involve letter substitutions.

Digital operations. Modern symmetric algorithms operate on binary data (bits) rather than characters. Messages are converted into bit-strings (e.g., using ASCII). Ciphers are either stream ciphers (encrypting bit-by-bit) or block ciphers (encrypting fixed-size blocks of bits).

Stream ciphers. Stream ciphers typically generate a pseudorandom keystream from a short key and XOR it with the plaintext bitstream. Like the OTP, decryption is the same process. They are fast and don't propagate errors if a bit is corrupted during transmission, making them suitable for noisy channels like mobile phone networks (e.g., GSM).

Block ciphers and modes. Block ciphers encrypt fixed-size blocks (e.g., 64 or 128 bits). Simple Electronic Code Book (ECB) mode encrypts each block independently. This is weak as identical plaintext blocks yield identical ciphertext blocks, revealing patterns and allowing manipulation. Modes like Cipher Block Chaining (CBC) or Cipher Feedback (CFB) link blocks together, ensuring each ciphertext block depends on all previous plaintext blocks, hiding patterns and providing better integrity properties.

6. Asymmetric Ciphers Rely on Hard Math Problems

Most practical public key algorithms are block ciphers that regard the message as a sequence of large integers and rely on the difficulty of solving a particular mathematical problem for their security.

Public/Private key pairs. Asymmetric cryptography uses distinct public and private keys. The public key encrypts data or verifies signatures; the private key decrypts data or creates signatures. Security relies on the computational difficulty of deriving the private key from the public key.

Underlying mathematical hardness. Unlike symmetric ciphers relying on complex bit manipulations, asymmetric ciphers are based on hard mathematical problems that are easy to perform in one direction but computationally infeasible to reverse without secret information.

• RSA: Security based on the difficulty of factoring large numbers into their prime factors.
• El Gamal: Security based on the difficulty of the discrete logarithm problem.

Key and block sizes. Due to the nature of these mathematical problems, asymmetric keys and block sizes are much larger than symmetric ones (hundreds or thousands of bits vs. 64-256 bits). This makes asymmetric operations computationally intensive and slower, typically limiting their use to encrypting smaller amounts of data like symmetric keys or for digital signatures.

7. Security Strength Depends on More Than Just Key Size

The estimated time needed for an exhaustive key search being considerably longer than the cover time is one obvious ‘hurdle’ for a system to pass before it can be deemed to be suitable for a specific application.

Assessing security. Determining if a cipher is "secure enough" involves more than just the theoretical difficulty of breaking the algorithm. It requires assessing the value of the data, the attacker's resources (computational power, time, skill), and the required cover time (how long the data needs protection).

Exhaustive key search. A basic measure is the time needed for a brute-force attack trying every possible key. This time must significantly exceed the cover time. Key size is crucial here; adding just one bit doubles the search space (2^s keys for s bits).

• DES (56-bit key) was breakable by dedicated hardware/distributed computing by the late 1990s.
• AES (128+ bit keys) is currently considered immune to brute force.

Beyond brute force. A well-designed algorithm should have no significantly faster attacks than brute force. Designers aim for properties like diffusion (small plaintext change affects many ciphertext bits), confusion (ciphertext/key relationship is complex), and completeness (each key bit affects all ciphertext bits) to thwart other attacks. Future threats like quantum computing could drastically reduce the time needed to break certain mathematical problems (affecting asymmetric ciphers more) and speed up brute force searches.

8. Cryptography Secures More Than Just Secrecy

In many situations it is the detection of unauthorized changes that is required, rather than their prevention.

Beyond confidentiality. While traditionally associated with keeping information secret (confidentiality), cryptography is increasingly used for other security services, especially in digital transactions. Simply encrypting data doesn't prevent manipulation if the attacker can substitute encrypted values.

Key security services:

• Data Integrity: Ensuring data hasn't been altered. Achieved using hash functions or Message Authentication Codes (MACs).
• Entity Authentication: Verifying the identity of a person or device. Often involves cryptographic protocols using shared secrets or key pairs.
• Data Origin Authentication: Verifying the source of data. Often combined with integrity checks.
• Non-Repudiation: Preventing someone from denying an action (like sending a message). Digital signatures are key here.

Integrity checks. Data integrity is often provided by creating a small cryptographic value (a hash or MAC) based on the message and a secret key. The recipient recalculates this value and compares it to the received one. Any mismatch indicates alteration. Unlike simple checksums, these are resistant to deliberate manipulation by an attacker without the key.

9. Digital Signatures Provide Trust and Non-Repudiation

For a digital signature scheme based on a public key system such as RSA or El Gamal, the basic principle is very simple.

Electronic proof of origin. Digital signatures use asymmetric cryptography to provide data integrity and non-repudiation, acting as an electronic equivalent of a handwritten signature. They bind a message to a specific sender in a way that can be verified by anyone but created only by the sender.

How they work. The sender uses their private key to sign a hash (condensed representation) of the message. The recipient uses the sender's public key to verify the signature on the hash. If it verifies, it proves the signature was created by the holder of the corresponding private key (the sender) and that the message hasn't been altered since signing.

• Signature creation: Hash(Message) -> Encrypt with Sender's Private Key -> Signature.
• Signature verification: Decrypt Signature with Sender's Public Key -> Compare result to Hash(Message).

Public Key Infrastructure (PKI). A major challenge is ensuring the authenticity of public keys. PKI addresses this through Certification Authorities (CAs) who issue digital certificates. A certificate binds a public key to an identity and is signed by the CA. Users trust the CA's signature to verify the public key's owner. PKI involves managing certificates, revocation (invalidating certificates), and establishing trust relationships between different CAs.

10. The Critical Role of Key Management

The security of any cryptographic system is totally dependent on the security of the keys.

Keys are the weak point. Even the strongest algorithm is useless if the keys are compromised. Key management encompasses the entire lifecycle of a key, from generation to destruction, ensuring its secrecy and integrity throughout.

Key lifecycle stages:

• Generation: Creating unpredictable keys.
• Distribution: Securely transferring keys between parties.
• Storage: Protecting keys when not in use.
• Usage: Defining and enforcing how keys can be used.
• Change: Regularly replacing keys.
• Destruction: Securely erasing keys when no longer needed.
• Archiving: Storing keys for potential future decryption needs (e.g., legal).

Distribution challenges. Secure key distribution is a major hurdle, especially for symmetric systems requiring shared secrets. Solutions include manual transfer (slow, expensive), key hierarchies (using higher-level keys to encrypt lower-level ones), or key establishment protocols (like Diffie-Hellman) where parties collaboratively generate a shared secret. Asymmetric systems simplify distribution of public keys via certificates, but private keys still require secure storage and handling.

11. Cryptography is Integrated into Everyday Life

Many of them represent scenarios that the man in the street encounters almost every day, but probably does not appreciate either the security risks or the role played by encryption.

Ubiquitous protection. Cryptography is no longer confined to military or government use; it's an invisible layer of security in many daily activities, protecting sensitive information and verifying identities without users needing to understand the technical details.

Common examples:

• ATM transactions: Encrypting PINs and transaction details between the ATM and the bank's server.
• Online shopping (HTTPS): Securing communication between your browser and the website using TLS/SSL protocols, often involving asymmetric key exchange followed by symmetric encryption.
• Mobile phone calls (GSM): Encrypting voice data using stream ciphers.
• Email security (PGP, S/MIME): Encrypting email content and adding digital signatures.
• Access control: Protecting passwords (often by hashing) or using cryptographic authentication protocols for logging into systems.

Balancing security and usability. The challenge is integrating strong cryptography seamlessly so users benefit from enhanced security without encountering complex key management or technical hurdles. While providing strong protection against technical attacks, cryptography doesn't solve all security problems; physical security, policy, and user behaviour remain critical components of overall security.

Last updated: May 8, 2025