Introduction to Cryptography

Sahadeo Padhye, Rajeev A. Sahu, Vishal Saraswat

• Publisher: CRC Press
• Year: 2018
• Print ISBN: 9780367781019
• eBook ISBN: 9781351628136
• Edition: 1
• Topic: Computer Science
• Subtopic: Counting & Numeration
• Index: Computer Science

Electronic communication and financial transactions have assumed massive proportions today. But they come with high risks. Achieving cyber security has become a top priority, and has become one of the most crucial areas of study and research in IT. This book introduces readers to perhaps the most effective tool in achieving a secure environment, i.e. cryptography. This book offers more solved examples than most books on the subject, it includes state of the art topics and discusses the scope of future research.

Chapter 1

Overview of Cryptography

CONTENTS

1.1 Introduction

1.2 Goals of Cryptography

1.3 Classification of Cryptosystem

1.4 Practically Useful Cryptosystem

1.4.1 Confusion and Diffusion

1.5 Cryptanalysis

1.5.1 Types of Attackers

1.5.2 Types of Attacks

1.5.3 Security Notions

Cryptography is defined to be as an art and science of secret writing. In more intellectual discussions, the journey of cryptography started from art of writing and moved to the science of writing. Broadly speaking classical cryptography (the art) moved to modern cryptography (the digital science) in the late 20th century. In order to understand these views better, one needs to understand the notion of cryptography that dates back to the beginning of human civilization. There are extensive historical evidences which testify the existence of methods of secret communication in many ancient societies including Mesopotamia, Egypt, India, China and Japan, but details regarding the exact origin of cryptography is debatable. In the ancient period, cryptography was used through some meaningful symbols in a specific art form. Later, these symbols were converted in arranged logics in a scientific way for more sensitive and crucial purpose. The elementary cipher machines (e.g. Enigma Machine) used by military organizations, which played a vital role during world wars, were examples of the use of cryptography. After the precise algorithms and their implementations since 1980s, there was a paradigm shift in the era of cryptography and cryptography entered in more practical world of modern cryptography where its application influenced and involved everyone.

1.1 Introduction

The term cryptography is a combination of two Greek words “Kruptos” (i.e. hidden) and “Graphio” (i.e. writing). Formally, cryptography is the study of secure designs required for the protection of sensitive communication. A communication requires a channel for the transaction of messages. This channel may be a telephone network, internet connection, or something else. However, none of the existing channels are guaranteed to be secure. Cryptography is all about providing a secure communication over an insecure channel.

Cryptography deals with the means and methods of data conversation in a secure form so that the data cannot be used by unauthorized person, authenticity of the data can be established, modification on the data can be avoided and the data cannot be repudiated by the generator. A cryptographic protocol/algorithm used for the above purpose is called a cryptosystem. In cryptography, the original message is usually referred as plaintext and the text converted from plaintext into (usually) non-meaningful form is referred as ciphertext. In general, cryptography deals with encryption of a plaintext into ciphertext and decryption of ciphertext into plaintext. The keys for the conversion are called encryption key and decryption key. The study of ciphertext, in attempt to decrypt it or to recover the key, is called cryptanalysis. The term cryptography and cryptanalysis are not apart of each other and can be viewed as two sides of a single coin. In order to construct secure cryptography, one should design it against all possible cryptanalysis. The term cryptology refers to study of design and analysis of cryptosystems.

Below, we define a cryptosystem more formally as:

Definition 1.1 Cryptosystem: [162] A Cryptosystem is a five-tuple ( $\mathcal{P}$, $\mathcal{C}$, $\mathcal{K}$, $\mathcal{E}$, $\mathcal{D}$), satisfying the following conditions-

1. $\mathcal{P}$ is a finite set of possible plaintexts;

2. $\mathcal{C}$ is a finite set of possible ciphertexts;

3. $\mathcal{K}$, the key space, is a finite set of possible keys;

4. For each key k ∈ $\mathcal{K}$, there is an encryption rule E_k ∈ $\mathcal{E}$, E_k: $\mathcal{P}$ → $\mathcal{C}$ and a decryption rule D_k ∈ $\mathcal{D}$, D_k: $\mathcal{C}$ → $\mathcal{P}$ such that, for any plaintext x ∈ $\mathcal{P}$, y = E_k(x) is the corresponding ciphertext and D_k(E_k (x)) = x.

Figure 1.1: Cryptosystem

It appears from the above definition that in a valid cryptosystem the encryption must be invertible since the decryption function is the inverse of the encryption function.

1.2 Goals of Cryptography

There are four basic goals of cryptography. These goals are abbreviated as ‘PAIN’, where P stands for Privacy (also known as confidentiality); A stands for Authentication; I stands for Integrity, and N stands for Non-repudiation. In addition to these basic goals, access control is now also considered to be one of the goals. We define each goal assuming a communication between a sender $\mathcal{S}$ and receiver $\mathcal{R}$.

▪ Privacy/Confidentiality–No one except the authorized users $\mathcal{S}$ and $\mathcal{R}$ should be able to see/detect the message communicated between them. Secrecy is a term synonymous to privacy and confidentiality. In general we use the term privacy and confidentiality as synonyms. In particular, privacy refers to an individuals right to control access to their personal information where confidentiality refers to how private information provided by individuals will be protected from release.

▪ Authentication–Authentication is a service related to identification. The receiver $\mathcal{R}$ should be able to validate the actual source or origin from where the message has been transmitted. Two parties involved in a communication should be able to identify each other. Also, the information delivered over the channel should be authenticated in the sense that it has been generated from an authorized source. Hence, authentication is required to be checked in two views: entity (or user) authentication and data origin authentication. Authentication of data origin implicitly provides data integrity (altered message implies change of source/origin).

▪ Integrity–During communication no one should be able to modify, alter, change, or delete the message.

▪ Non-repudiation–The actual participants $\mathcal{S}$ and $\mathcal{R}$ should not be able to deny their involvement in the communication.

▪ Access Control–Only the legitimate users are granted access to the resources or information.

Different cryptographic primitives have been devised to achieve these goals. The privacy can be achieved by applying an encryption scheme. Entity authentication can be achieved by digital signature. Integrity can be achieved by hash function and the goal of non-repudiation can be achieved by advanced electronic signature or digital signature with some additional functionality (e.g. undeniable signature). We will precisely discuss each of these crypto-primitives in further chapters.

1.3 Classification of Cryptosystem

For a classified study, the cryptosystems can be categorized in the following classes:

▪ Classical vs Modern–This classification is in the view of pre and post computer era. Classical cryptosystems are the ones which have been used during the pre-computer era and the modern cryptosystems are those being used in the post-computer era. Broadly, they can also be analyzed on the basis of time period i.e. those belonging to early twentieth century and those belonging to late twentieth century. Examples of classical cryptosystems are: Caesar Cipher, Vigenère Cipher, Affine Cipher, Hill Cipher, Auto-key cipher etc. and the examples of modern cryptosystems are DES, AES, RSA, ElGamal etc.

▪ Symmetric Cryptosystem vs Asymmetric Cryptosystem or Secret Key Cryptosystem (SKC) vs Public Key Cryptosystem (PKC)–This classification is on the basis of encryption key e_k and decryption key d_k. If e_k = d_k then the cryptosystem is called symmetric cryptosystem (or secret key crytosystem) and if e_k ≠ d_k then the cryptosystem is called asymmetric cryptosystem (or public key cryptosystem). Examples of symmetric cryptosystems are all classical cryptosystems, Block cipher, Stream cipher etc. Asymmetric cryptosystems are RSA, ElGamal, Knapsack, Rabin, XTR, NTRU etc.

▪ Block Cipher vs Stream Cipher–This classification is on the basis of encryption process. In block cipher, the message is encrypted after being divided into fixed size of blocks. Examples of block ciphers are DES, AES, Triple DES, Serpent, Blowfish, Twofish, IDEA, RC5, Clefia etc. In stream cipher, the entire message is encrypted at a time using a key stream. RC4, ChaCha, SOSEMANUK, SEAL, SNOW, Grain, MICKEY, Trivium, Linear Feed Back Shift Registrar (LFSR) are some popular stream ciphers.

▪ Deterministic vs Randomized–This classification is also based on the nature of encryption process. If the encryption formula always outputs the same ciphertext for a fixed plaintext then the cryptosystem is called deterministic cryptosystem. However, if the output of the encryption algorithm depends on some random number i.e....

Table of contents

• Cover
• Title Page
• Copyright Page
• Dedication
• Foreword
• Preface
• Table of Contents
• 1 Overview of Cryptography
• 2 Basic Algebra
• 3 Number Theory
• 4 Probability and Perfect Secrecy
• 5 Complexity Theory
• 6 Classical Cryptosystems
• 7 Block Ciphers
• 8 Hash Function
• 9 Public Key Cryptosystem
• 10 Digital Signature
• 11 Research Directions in Cryptography
• References
• Index