I’ve made it a goal to learn as much about cryptography as I can. I’m talking about the mathematics that enable it, of course, the stuff that has always terrified me. As a programmer, I’ve (mostly) never shrunk from a challenge, but the sheer amount of preparatory work necessary to even understand a post on Stack Overflow or Stack Exchange had me shivering in my timbers.

But this is all about to change, and I’ve selected my entry point to be The Handbook of Applied Cryptography. I really enjoy reading Bruce Schneier and subscribe to his Crypto-Gram, so I’m sure I’ll augment my studies with his writings in the near future, as well.

This will be the first in a series of articles on cryptography as I attempt to go as far as I can on my own steam. My goal is to document the content that seems most meaningful and instructive to me. It’s not intended to be exhaustive.

Although it may seem boring and perhaps even intimidating, there’s no getting around that one needs to build a solid foundation before getting to the really interesting topics. I think this is true in any endeavor, and so I found myself facing frightening terms and symbols as soon as I opened the book.

So, as a reference and a cheat sheet, here are some of the terms that I’ve encountered. Some of the definitions I’ve lifted whole cloth from the aforementioned book, and I in no way am trying to pass them off as my own.

Let’s dig in….

- Basic Terminology
- Function Terminology
- Encryption Domains and Codomains
- Encryption and Decryption Transformations
- Communication Participants
- Channels
- Cryptology

## Basic Terminology

**Cryptography**- The study of mathematical techniques related to aspects of information security such as confidentiality, data integrity, entity authentication, and data origin authentication.**Cryptographic primitives**- Basic cryptographic tools used to provide information security. Examples include encryption schemes, hash functions and digital signature schemes.**Cipher**- An encryption scheme.**Set**- Consists of distinct elements which are known as*elements*of the set. For example, a set`X`

might consist of the elements`a`

,`b`

and`c`

and is denoted`X = {a,b,c}`

.**Information security service**- A method to provide some specific aspect of security. For example, integrity of transmitted data is a security objective, and a method to ensure this aspect is an information security service.**Symmetric-key encryption**- An encryption scheme is said to be*symmetric-key*if for each associated encryption/decryption key pair`(e, d)`

, it is computationally “easy” to determine`d`

knowing only`e`

, and to determine`e`

from`d`

.**Public-key encryption**- An encryption scheme where for each associated encryption/decryption pair`(e,d)`

, one key`e`

(the*public key*) is mad publicly available, while the other`d`

(the*private key*) is kept secret. For the scheme to be**secure**, it must be computationally infeasible to compute`d`

from`e`

.**Digital signature**- A cryptographic primitive which is fundamental in authentication, authorization and non-repudiation, its purpose is to provide a means for an identity to bind its identity to a piece of information.**Hash function**- Often informally called a*one-way hash function*, it is a computationally efficient function mapping binary strings of arbitrary length to binary strings of some fixed length, called*hash-values*.

## Function Terminology

**Function**- Alternatively referred to as a*mapping*or a*transformation*, a*function*is defined by two sets`X`

and`Y`

and a rule`f`

which assigns to each element in`X`

precisely one element in`Y`

. The set`X`

is called the*domain*of the function and`Y`

the*codomain*.**image**of`x`

- If`x`

is an element of`X`

(usually written`x ∈ X`

), the*image*of`x`

is the element in`Y`

in which the rule`f`

associates with`x`

. The image`y`

of`x`

is denoted by`y = f(x)`

.**preimage**of`y`

- If`y ∈ Y`

, then a*preimage*of`y`

is an element`x ∈ X`

for which`f(x) = y`

.**image**of`f`

- Denoted`Im(f)`

. The set of all elements in`Y`

which have at least one preimage.

Let f be the rule that for each x ∈ X, f(x) = rExample_{x}, where r_{x}is the remainder when x^{2}is divided by 11. X = {1,2,3,4,5,6,7,8,9,10} f(1) = 1 f(2) = 4 f(3) = 9 f(4) = 5 f(5) = 3 f(6) = 3 f(7) = 5 <--- The preimage of element 5 is 7. f(8) = 9 f(9) = 4 f(10) = 1 Im(f) = {1,3,4,5,9}

## Types of Functions

Standard notation for a function

`f`

from set`X`

to set`Y`

is`f : X → Y`

.

### 1-1

A function or transformation is 1-1 (one-to-one) if each element in the codomain

`Y`

is the image of at most one element in the domain`X`

.A 1-1 function is bijective.

Inverse functions:

If

`f`

is a bijection from`X`

to`Y`

then it is a simple matter to define a bijection`g`

from`Y`

to`X`

as follows: for each`y ∈ Y`

define`g(y) = x`

where`x ∈ X`

and`f(x) = y`

. This function`g`

obtained from`f`

is called the*inverse function*of`f`

and is denoted by`g = f`

^{−1}.The domain of

`g`

is`Y`

and the codomain is`X`

.

## bijection

If a function

`f : X → Y`

is 1−1 and`Im(f) = Y`

, then f is called a bijection. There are no unpaired elements.Bijective functions are

one-to-one(injective) as well asonto(surjective). Note that if`f`

is a bijection, then so is`f`

. In cryptography, bijections are used as the tool for encrypting messages and the inverse transformations are used to decrypt. Notice that if the transformations were not bijections then it would not be possible to always decrypt to a unique message.^{−1}

### one-way

A function

`f`

from a set`X`

to a set`Y`

is called a*one-way function*if`f(x)`

is “easy” to compute for all`x ∈ X`

but for “essentially all” elements`y ∈ Im(f)`

it is “computationally infeasible” to find any`x ∈ X`

such that`f(x) = y`

.Alternatively, for a random

`y ∈ Im(f)`

, it is computationally infeasible to find any`x ∈ X`

such that`f(x) = y`

.

DefineExample`f(x) = r`

for all_{x}`x ∈ X`

where`r`

is the remainder when 3_{x}^{x}is divided by 17. Now, given a number between between 1 and`t`

, determine`x`

provided`f(x) = 8`

. For small numbers, this is not a hard problem, as one can simply try every number in the range 1 through 16: f(1) = 3 f(2) = 9 f(3) = 10 f(4) = 13 f(5) = 5 f(6) = 15 f(7) = 11 f(8) = 16 f(9) = 14 f(10) = 8 <--- Dude! f(11) = 7 f(12) = 4 f(13) = 12 f(14) = 2 f(15) = 6 f(16) = 1 But, let's say the modulus is the product of two 100-digit prime numbers? p = 56282904590578772918091824503812389276973148221339/ 23421169378062922140081498734424133112032854812293 q = 72126101472954749095445237850434924099693821481867/ 65460082500085393519556525921455588705423020751421 n = pq =40594664876927152429464221872014903331305438593550203566566567434044\ 09274728618132558293704275021893950727842396795312164019235290143106\ 7647263568137200677133330187177812269497007251370100980768018353The domain of the function now becomes: X = {1, 2, 3, ..., n - 1} Good luck!

The important point here is that there is a difference in the amount of work to compute `f(x)`

and the amount of work to find `x`

given `f(x)`

.
What is needed is a shortcut or “trapdoor” where the latter becomes knowable, i.e., easy to reverse.

### trapdoor one-way

A trapdoor one-way function is a one-way function

`f : X → Y`

with the additional property that given some extra information (called the*trapdoor information*) it becomes feasible to find for any given`y ∈ Im(f)`

, an`x ∈ X`

such that`f(x) = y`

.In the example above, the trapdoor is knowing the two prime factors. This is the integer factorization problem.

One-wayandtrapdoor one-wayfunctions are the basis for public-key cryptography.

### permutations

Let

`S`

be a finite set of elements. A*permutation p*on`S`

is a bijection from`S`

to itself (i.e.,`p : S → S)`

.Since permutations are bijections, they have inverses. The inverse of

`p`

is`p`

.^{-1}

### involutions

Involutions have the property that they are their own inverses.

Let

`S`

be a finite set and let`f`

be a bijection from`S`

to`S`

(i.e.,`f : S → S`

). The function`f`

is called an*involution*if`f = f`

. An equivalent way of stating this is^{−1}`f(f(x)) = x`

for all`x ∈ S`

.

## Encryption Domains and Codomains

**Alphabet of definition**- Is a finite set denoted by`A`

. For example,`A = {0,1}`

is the*binary alphabet*and is a frequently-used alphabet of definition.

Any alphabet can be encoded in terms of the binary alphabet.

**Message space**- Denoted by the set`M`

, it consists of strings of symbols from an alphabet of definition. An element of`M`

is called a*plaintext message*or simply a*plaintext*.**Ciphertext space**- Denoted by the set`C`

, it consists of strings of symbols from an alphabet of definition, which may differ from the alphabet of definition for`M`

. An element of`C`

is called a*ciphertext*.

## Encryption and Decryption Transformations

**Key space**- Denoted by the set`K`

. An element of`K`

is called a*key*.**Encryption function**- Also known as an*encryption transformation*, it is denoted by`E`

, where each element_{e}`e ∈ K`

uniquely determines a bijection from`M`

to`C`

. Note that`E`

must be a bijection if the process is to be reversed and a unique plaintext message recovered for each distinct ciphertext._{e}- The process of applying the transformation
`E`

to a message_{e}`m ∈ M`

is usually referred to as*encrypting m*or the*encryption*of*m*.

- The process of applying the transformation

More generality is obtained if

`E`

is simply defined as a 1 − 1 transformation from_{e}`M`

to`C`

. That is to say,`E`

is a bijection from_{e}`M`

to`Im(E`

where_{e})`Im(E`

is a subset of_{e})`C`

.

**Decryption function**- Also known as a*decryption transformation*, it is denoted by`D`

, where each element_{d}`d ∈ K`

uniquely determines a bijection from`C`

to`M`

(i.e.,`D`

: C → M)._{d}- The process of applying the transformation
`D`

to a ciphertext_{d}`c`

is usually referred to as`decrypting c`

or the`decryption`

of`c`

.

- The process of applying the transformation
**Encryption scheme**- Sometimes referred to as a*cipher*, it consists of a set`{E`

of encryptions transformations and a corresponding set_{e}: e ∈ K}`{D`

of decryption transformations with the property that for each_{d}: d ∈ K}`e ∈ K`

there is a unique key`d ∈ K`

such that`D`

; that is,_{d}= E^{−1}`D`

for all_{d}(E_{e}(m)) = m`m ∈ M`

.

To construct an encryption scheme requires one to select a message space

`M`

, a ciphertext space`C`

, a key space`K`

, a set of encryption transformations`{E`

, and a corresponding set of decryption transformations_{e}: e ∈ K}`{D`

._{d}: d ∈ K}An encryption scheme is said to be

breakableif a third party, without prior knowledge of the key pair`(e, d)`

, can systematically recover plaintext from corresponding ciphertext within some appropriate time frame.

**Key pair**- In the preceding definition, the keys*e*and*d*are referred to as a*key pair*and sometimes denoted by`(e,d)`

. Note that*e*and*d*could be the same.

## Communication Participants

**Entity**- Also known as a*party*, it is someone or something which sends, receives or manipulates information. An entity may be a person, computer terminal, etc.**Sender**- An entity in a two-party communication which is the legitimate transmitter of information.**Receiver**- An entity in a two-party communication which is the intended recipient of information.**Adversary**- An entity in a two-party communication which is neither the sender nor receiver, and which tries to defeat the information security service being provided between the sender and receiver. Various other names are synonymous with adversary such as enemy, attacker, opponent, tapper, eavesdropper, intruder and interloper. An adversary will often attempt to play the role of either the legitimate sender or the legitimate receiver.

## Channels

**Channel**- A means of conveying information from one entity to another.**Physically secure channel**- Also known as a*secure channel*, is one which is not physical accessible to the adversary.**Unsecured channel**- A channel from which parties other than those for which the information is intended can reorder, delete, insert or read.**Secured channel**- A channel from which an adversary does not have the ability to reorder, delete, insert or read.

## Cryptology

– **Cryptanalysis** - The study of mathematical techniques for attempting to defeat cryptographic techniques, and, more generally, information security services.

– **Cryptanalyst** - Someone who engages in cryptanalysis.

– **Cryptology** - The study of cryptography and cryptanalysis.

– **Cryptosystem** - A general term referring to a set of cryptographic primitives used to provide information security services. Most often the term is used in conjunction with primitives providing confidentiality, i.e., encryption.

Cryptographic techniques are typically divided into two generic types:

symmetric-keyandpublic-key.