Introduction to Cryptography

Introduction to Cryptography

• Cryptography comes from the Greek words "krypto" (secret) and "graphein" (write), thus meaning secret writing
• Cryptography is the art and science of securing messages
• Cryptography involves techniques for secure communication, for creating documents that can be shared secretly over public channels
• Modern cryptography combines mathematics, computer science, and electrical engineering
• Cryptography applications include ATM cards, computer passwords, and e-commerce

History of Cryptography

• 50 B.C.: Julius Caesar used cryptographic techniques
• 400 A.D.: Kama Sutra mentions cryptographic techniques in India
• 1250: Roger Bacon described simple ciphers
• 1466: Leon Alberti developed a cipher disk
• 1861: Union forces used a cipher during the Civil War
• 1914: Encryption technology was used in World War I by British, French, and German forces
• 1917: William Friedman started a school for cryptanalysis
• 1917: Gilbert Vernam (AT&T) invented the polyalphabetic cipher
• 1919: Germans developed the Enigma machine
• 1937: Japanese designed the Purple machine for encryption
• 1942: Navajo windtalkers aided secure communication during World War II
• 1948: Claude Shannon developed statistical methods for encryption/decryption
• 1976: IBM developed the Data Encryption Standard (DES)
• 1976: Diffie-Hellman developed public key / private key cryptography
• 1977: Rivest, Shamir, and Adleman developed the RSA algorithm for public key / private key cryptography

Plaintext

• Plaintext is the original message or data in a readable form before encryption
• Plaintext is sometimes called clear text
• Plaintext is denoted by M (message) or P (plaintext)
• Plaintext can be a stream of bits, a text file, a bitmap, or digitized voice

Ciphertext

• Ciphertext is an encrypted message, represented by C
• Ciphertext sometimes has the same size as the plaintext, or sometimes larger
• Ciphertext results from applying an encryption algorithm to the plaintext
• Ciphertext is unreadable except to intended recipients

Encryption

• Encryption disguises a message to hide its substance
• Encryption is the process of scrambling a message using a cryptographic algorithm to make it unreadable by anyone except for intended recipients
• The encryption function E, when applied to M, generates C in mathematical notation: E(M) = C

Decryption

• Decryption converts the ciphertext back to the original plaintext
• The decryption function D, operates on C to produce M, represented as: D(C) = M
• The decryption process recovers the original plaintext, therefore D(E(M)) = M

Cryptanalysis

• Cryptanalysis is the art and science of breaking ciphertext
• Cryptanalysis's practice seeks to see through the disguise
• Cryptanalysis finds encryption keys to decipher cryptographic algorithms without knowing the encryption
• A Cryptanalyst is someone breaking cryptographic codes, referred to as "the attacker" or "the intruder”

Cryptology

• Cryptology is the study of cryptography and cryptanalysis collectively
• Cryptology encompasses both cryptography and cryptanalysis, and its practitioners are called cryptologists
• Modern cryptologists are typically trained in theoretical mathematics

Confidentiality Characteristics

• Authentication: verifying the sender's origin to prevent intruders from masquerading
• Integrity: ensuring that a message hasn't been altered in transit, preventing substitution of false messages
• Nonrepudiation: preventing a sender from denying that they sent a message

Authentication

• Authentication means proving that you are who you claim to be, verifying the creator and sender of a message
• Digital signatures authenticate the source of messages, ensuring recognition of the message sender
• Authentication ensures only authorized parties gain access to a message
• Authentication can be ensured through passwords and digital signatures

Integrity

• Integrity ensures the message delivered remains intact, unaltered, and trustworthy
• Digital signatures ensure message integrity
• Sending a message over a network ensures the arriving data matches what was originally sent without any modification
• Encryption and hashing algorithms are technical solutions for maintaining message integrity

Non-Repudiation

• Non-repudiation prevents the sender's denial and ensures message authentication through digital signatures, guaranteeing receipt and identity

Cryptographic Algorithms (Ciphers)

• A cryptographic algorithm (or cipher) is the mathematical function for encryption and decryption
• There are typically two related functions: one for encryption and one for decryption
• An algorithm’s security is based on its secrecy of operation, it is a restricted algorithm.
• Restricted algorithms are historically interesting but often inadequate

Types of Cryptographic Algorithms

• Algorithms are classified based on the number of utilized keys
• Symmetric algorithms (Secret Key Cryptography or SKC) uses a single key for both encryption and decryption
• Asymmetric algorithms (Public Key Cryptography or PKC) uses one key for encryption and another for decryption
• Hash Functions involve mathematical transformations to irreversibly encrypt information

Secret Key Cryptography

• In Secret Key Cryptography (SKC), the same key is used for encryption and decryption, and encryption and decryption keys are sometimes calculated from each other
• The sender encrypts, sends ciphertext, and the receiver decrypts using the same key
• Because a single key is used for both encryption and decryption, it is known as symmetrical encryption
• This form requires key secrecy and distribution
• Algorithms are called single-key or one-key algorithms and require sender and receiver to agree on a unique key before communication
• The security of symmetric algorithms relies on the key
• Symmetric key algorithms in use: DES , Triple DES, AES , Blowfish, CAST, IDEA, and Rivest Ciphers RC2-6
• Symmetric algorithms categorized as stream and block ciphers
• Stream ciphers encrypt on single bits or bytes, while block ciphers encrypt groups of bits

Public Key Cryptography

• Asymmetric Encryption (Public Key Encryption -PKC) was devised in 1975 by Diffie & Hellman based on using a pair of keys - one for encryption called the public key, and the other for decryption called the private key
• Designed so the encryption key differs from the decryption key, and the decryption key is non-calculatable
• It's called "public-key cryptography" because the encryption key is public
• Only the person with the corresponding decryption key can decrypt messages
• Messages encrypted with the private key are sometimes decrypted with the public key; as with a digital signature
• Examples include: RSA, DSA, and Diffie-Hellman

Mathematical Base of PKC

• PKC works through one-way functions that are easy to compute, but hard to reverse
• The mathematical "trick" is to find a trap door in the one-way function to make reverse calculations easy with specific knowledge

Hash Function

• Hashing involves transforming a string of characters into a shorter, fixed-length key
• A Hash function maps digital data of any size to the same data of a fixed size
• Hash functions return hash values, codes, sums, or simply hashes
• Hash functions are irreversible

Restricted Algorithm Drawbacks

• Restricted algorithms work best with small groups of users because time a user leaves the group, they switch to a different algorithm
• Any accidental secret leaks requires everyone to change algorithms
• Restricted algorithms are not quality controlled or standardized
• Every group must design own algorithms which can lead to vulnerabilities

Cryptanalytic Attacks

• An attempted cryptanalysis is an attack or cryptanalytic attack
• Loss of a key through non-cryptanalytic means is a compromise
• Four general types of cryptanalytic attacks assume complete knowledge of the encryption algorithm: ciphertext-only, known-plaintext, chosen-plaintext, adaptive-chosen-plaintext

Ciphertext-Only Attack

• For this attack, the cryptanalyst only has the ciphertext of several messages encrypted via the same algorithm
• The cryptanalyst recovers the plaintext of multiple messages, or determines the key (or keys) to decrypt future messages

Known-Plaintext Attack

• The cryptanalyst possesses the ciphertext and the corresponding plaintext for several messages
• The goal is to determine the key (or keys) to decrypt new messages
• A known-plaintext attack is more powerful and easier than a ciphertext-only attack
• Known-plaintext (and chosen-plaintext) attacks were common practice during World War II

Chosen-Plaintext Attack

• The cryptanalyst has access to the ciphertext and associated plaintext, and they are able to choose text to encrypt
• This attack is easier to utilize than a known-plaintext attack because the cryptanalyst chooses and encrypts specific plaintext blocks for more information about the key
• The job involves deducing keys used to encrypt messages

Adaptive-Chosen-Plaintext Attack

• Adaptive-chosen-plaintext attack: cryptanalyst chooses plaintext with modifiable choices based on previous encryption results
• The cryptanalyst chooses a smaller plaintext block with another choice based on results

Other Types of Cryptanalytic Attacks

• Additional forms of cryptanalytic attacks: Chosen-ciphertext, Chosen-key, Rubber-hose cryptanalysis

Chosen-Ciphertext Attack

• A cryptanalyst can choose different ciphertexts to decrypt and access the decrypted plaintext
• This is applicable to public-key algorithms sometimes has effects against a symmetric algorithm also
• Chosen-plaintext and chosen-ciphertext attacks together are a chosen-text attack

Chosen-Key & Rubber-Hose Attack

• Chosen-key attack refers to cryptanalysts with knowledge regarding relationships of different keys
• Rubber-hose cryptanalysis refers to extortion tactics and a purchase-key attack refers to bribing for the key

Complexity of An Attack

• Attack complexity can be measured in three separate ways
• Data Complexity refers to the amount of data used to perform the attack
• Processing or Time Complexity (Work Factor) refers to the time it would take to perform the attack
• Storage Requirements refers to the memory needed to perform the attack

Kerckhoff's Assumption

• One should not rely on the secrecy of the algorithm to secure a cryptosystem
• The math should be secure enough that any algorithm can withstand attacks without it being top secret

Security of Algorithms

• Algorithms provide varied security based on how difficult breaking them is

• Protection is possible if the cost of breaking the algorithm is more than the value the encrypted data

• Protection is possible if the time required to break an algorithm is longer than secret data remains secret

• Security depends on the amount of data encrypted with one key

• Since there is always a chance of cryptanalysis, the value of the data should be less than the cost to break the security

• Protection is achieved if the cost to break the encrypted data is more than value the data is worth.

Unconditionally Secure Algorithms Vs Computationally Secure Algorithms

• An algorithm is unconditionally secure there is too little information to recover the plaintext, no matter how much ciphertext

• A one-time pad is unbreakable where other cryptosystems are breakable in a ciphertextonly attack

• An algorithm is computationally secure if available resources, current and future, cannot break it

Key and Key Space

• A key controls the operation and behavior of a cryptographic algorithm.
• Rules used convert a document into something secret.
• Keyspace is the range of possible Key values
• Example: E(M)=C , D(C)=M then D(E(M))=M

Cryptosystem

• A cryptosystem combines algorithms, plaintext, ciphertext, keys, and key management functions for cryptographic operations
• A cryptosystem is a 5-tuple (E,D,M,K,C) including encryption/decryption functions, plaintexts set, keys set, and ciphertexts set

Substitution Ciphers

• Substitute or replace each character plaintext with another character
• Receiver inverts the substitution for the ciphertext
• Easy to break due to statistical properties of written language.
• Substitution ciphers come one of four types: simple mono alphabetic, homophonic, polygram, and poly alphabetic

Types of Substitutions Ciphers

• Simple substitution cipher: also mono alphabetic cipher is one in which original character is replaced with a corresponding character of ciphertext
• Homophonic substitution: single character replaces other forms character
• Polygram substitution cipher: encrypts blocks of characters are encrypted in groups.
• Polyalphabetic substitution cipher: Made up of multiple simple substitution ciphers that uses the position of each character of plaintext to change the cipher

Transposition cipher

• Changes order of the letters
• Involves a simple columnar transposition cipher where plaintext is written on graph paper and is read off vertically
• Easy to break when analyzing structure of language