10 min read

On the Terminology of Cryptography

November 30, 2018

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….

  1. Basic Terminology
  2. Function Terminology
  3. Encryption Domains and Codomains
  4. Encryption and Decryption Transformations
  5. Communication Participants
  6. Channels
  7. 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.

Example

Let f be the rule that for each x ∈ X, f(x) = rx, where rx is the remainder
when x2 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 as onto (surjective). Note that if f is a bijection, then so is f−1. 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.

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.

Example

Define f(x) = rx for all x ∈ X where rx is the remainder when 3x 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\
		 7647263568137200677133330187177812269497007251370100980768018353

The 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-way and trapdoor one-way functions 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−1. An equivalent way of stating this is 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 Ee, where each element e ∈ K uniquely determines a bijection from M to C. Note that Ee must be a bijection if the process is to be reversed and a unique plaintext message recovered for each distinct ciphertext.

    • The process of applying the transformation Ee to a message m ∈ M is usually referred to as encrypting m or the encryption of m.

More generality is obtained if Ee is simply defined as a 1 − 1 transformation from M to C. That is to say, Ee is a bijection from M to Im(Ee) where Im(Ee) is a subset of C.

  • Decryption function - Also known as a decryption transformation, it is denoted by Dd, where each element d ∈ K uniquely determines a bijection from C to M (i.e., Dd : C → M).

    • The process of applying the transformation Dd to a ciphertext c is usually referred to as decrypting c or the decryption of c.

  • Encryption scheme - Sometimes referred to as a cipher, it consists of a set {Ee : e ∈ K} of encryptions transformations and a corresponding set {Dd : d ∈ K} of decryption transformations with the property that for each e ∈ K there is a unique key d ∈ K such that Dd = E−1; that is, Dd(Ee(m)) = m for all 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 {Ee : e ∈ K}, and a corresponding set of decryption transformations {Dd : d ∈ K}.

An encryption scheme is said to be breakable if 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-key and public-key.