# «The University of Sydney Math3024 Elementary Cryptography and Protocols Introduction to Cryptography Cryptography is the study of mathematical ...»

1

Introduction

The University of Sydney

Math3024 Elementary Cryptography and Protocols

Introduction to Cryptography

Cryptography is the study of mathematical techniques for all aspects of information

security. Cryptanalysis is the complementary science concerned with the methods to

defeat these techniques. Cryptology is the study of cryptography and cryptanaylsis. The

**security of information encompasses the following aspects:**

• conﬁdentiality or privacy,

• data integrity,

• authentication,

• nonrepudiation.

Each of these aspects of message security can addressed by standard methods in cryptography. Besides exchange of messages, tools from cryptography can be applied to sharing an access key between multiple parties so that no one person can gain access to a vault by any two of them can. Another role is in the design of electronic forms of cash.

Deﬁnitions and Terminology Encryption = the process of disguising a message so as to hide the information it contains;

this process can include both encoding and enciphering (see deﬁnitions below).

Protocol = an algorithm, deﬁned by a sequence of steps, precisely specifying the actions of multiple parties in order to achieve an objective.

Plaintext = the message to be transmitted or stored.

Ciphertext = the disguised message.

Alphabet = a collection of symbols, also referred to as characters.

Character = an element of an alphabet.

Bit = a character 0 or 1 of the binary alphabet.

String = a ﬁnite sequence of characters in some alphabet.

Example. The following are some standard alphabets.

2 Elementary Cryptography A,..., Z 26 symbols MSDOS (less punctuation) ASCII 7-bit words (128 symbols) American standard extended 8-bit words (256 symbols) ISO-8859-1 8-bit words (256 symbols) European standard Binary {0,1} Numerical alphabet base 2 Octal {0,...,7} Numerical alphabet base 8 Decimal {0,...,9} Numerical alphabet base 10 Hexadecimal {0,...,9,a,b,c,d,e,f} Numerical alphabet base 16 Encode = to convert a message into a representation in a standard alphabet, such as to the alphabet {A,..., Z} or to numerical alphabet.

Decode = to convert the encoded message back to its original alphabet and original form — the term plaintext will apply to either the original or the encoded form. The process of encoding a message is not an obscure process, and the result that we get can be considered equivalent to the plaintext message.

Cipher = a map from a space of plaintext to a space of ciphertext.

Encipher = to convert plaintext into ciphertext.

Decipher = to convert ciphertext back to plaintext.

Stream cipher = a cipher which acts on the plaintext one symbol at a time.

Block cipher = a cipher which acts on the plaintext in blocks of symbols.

Substitution cipher = a stream cipher which acts on the plaintext by making a substitution of the characters with elements of a new alphabet or by a permutation of the characters in the plaintext alphabet.

Transposition cipher = a block cipher which acts on the plaintext by permuting the positions of the characters in the plaintext.

where M is a subset of A∗, C is a subset of A′∗, and K and K′ are sets which are generally strings of ﬁxed ﬁnite length over some alphabets (e.g. An or A′n ). A cryptosystem or encryption scheme is a pair (E, D) of maps

for all M in M. We write EK for the map E(K, ·) : M → C and similarly write DK ′ for D(K ′, ·) : C → M. With this notation the condition on E, D, K and K ′ is that DK ′ ◦ EK is the identity map on M.

We will refer to EK as a cipher, and note that a cipher is necessarily injective. For many cryptosystems, there will exist a unique inverse ciphertext key K ′ associated to each plaintext key K. A cryptosystem for which the inverse key K ′ is K itself (hence K = K′ ) is said to be symmetric. If the inverse key K ′ associated to K is neither K itself nor easily computable function of K, then we say that the cryptosystem is asymmetric or a public key cryptosystem.

A fundamental principle of cryptography is that the security of a cipher EK (i.e. the diﬃculty in ﬁnding DK ′ ) does not rest on the lack of knowledge of the cryptosystem (E, D). Instead, security should be based on the secrecy of K ′.

Recall that a (cryptographic) protocol is an algorithm, deﬁned by a sequence of steps, precisely specifying the actions of multiple parties in order to achieve a (security) objective. An example of a cryptographic protocol, we describe the steps for message exchange using a symmetric key cryptosystem.

The diﬃculty of step 2.a) was one of the fundamental obstructions to cryptography before the advent of public key cryptography. Asymmetric cryptography provides an elegant solution to the problem of distribution of private keys.

Throughout the course we will denote the plaintext alphabet by A and the ciphertext alphabet by A′. We write EK for the enciphering map and DK ′ for the deciphering map, where K and K ′ are enciphering and deciphering keys.

We identify four diﬀerent types of substitution ciphers.

A. Simple substitution ciphers. In this cryptosystem, the algorithm is a characterby-character substitution, with the key being the list of substitutions under the ordering of the alphabet. In other words, a simple substitution cipher is deﬁned by a map A → A′.

Suppose that we ﬁrst encode a message by purging all nonalphabetic characters (e.g.

numbers, spaces, and punctuation) and changing all characters to uppercase. Then the key size, which bounds the security of the system, is 26 alphabetic characters. Therefore the total number of keys is 26!, an enormous number. Nevertheless, we will see that simple substitution is very susceptible to cryptanalytic attacks.

**Example. Consider this paragraph, encoded in this way, to obtain the plaintext:**

## SUPPOSETHATWEFIRSTENCODEAMESSAGEBYPURGINGALLNONALPHABETI

## CCHARACTERSEGNUMBERSSPACESANDPUNCTUATIONANDCHANGINGALLCH

## ARACTERSTOUPPERCASETHENTHEKEYSIZEWHICHBOUNDSTHESECURITYO

## FTHESYSTEMISALPHABETICCHARACTERSTHEREFORETHETOTALNUMBERO

## FKEYSISOFENORMOUSSIZENEVERTHELESSWEWILLSEETHATSIMPLESUBS

## TITUTIONISVERYSUSCEPTIBLETOCRYPTANALYTICATTACKS

then using the enciphering key UVLOIDTGKXYCRHBPMZJQVWNFSAE, we encipher the plaintext**to obtain ciphertext:**

## QWMMPQDVKUVFDTXJQVDBOPIDUHDQQUGDLAMWJGXBGURRBPBURMKULDVX

## OOKUJUOVDJQDGBWHLDJQQMUODQUBIMWBOVWUVXPBUBIOKUBGXBGURROK

## UJUOVDJQVPWMMDJOUQDVKDBVKDCDAQXEDFKXOKLPWBIQVKDQDOWJXVAP

## TVKDQAQVDHXQURMKULDVXOOKUJUOVDJQVKDJDTPJDVKDVPVURBWHLDJP

## TCDAQXQPTDBPJHPWQQXEDBDNDJVKDRDQQFDFXRRQDDVKUVQXHMRDQWLQ

## VXVWVXPBXQNDJAQWQODMVXLRDVPOJAMVUBURAVXOUVVUOCQ

Simple substitution ciphers can be easily broken because the cipher does not change the frequencies of the symbols of the plaintext.Aﬃne ciphers. A special case of simple substitution ciphers are the aﬃne ciphers. If we numerically encode the alphabet {A, B..., Z} as the elements {0, 1,..., 25} of Z/26Z then we can operate on the letters by transformations of the form x → ax + b, for any a for which GCD(a, 26) = 1. What happens if a is not coprime to 26?

Classical Cryptography An aﬃne cipher for which a = 1 is called a translation cipher. Enciphering in a translation cipher is achieved by the performing b cyclic shift operations (A → B, B → C, etc.) on the underlying alphabet.

A classical instance of a translation cipher is the Caesar cipher, used by Julius Caesar, which is the translation cipher with the enciphering key b = 3. Using Caesar’s enciphering key, we obtain the map A → D, B → E,..., Z → C.

Thought Exercise. Consider the number of possible keys for the aﬃne ciphers. Is this suﬃcient to have a secure cryptosystem?

B. Homophonic substitution ciphers. In this cryptosystem the deciphering is a function from a larger alphabet A′ to the alphabet A, but an enciphering of the plaintext can take a character to any one of the elements in the preimage.

One way to realize a homophonic cipher is to begin with m diﬀerent substitution keys, and with each substitution, make a random choice of which key to use. For instance, suppose we take A to be own standard 26 character alphabet, and let the cipher alphabet A′ be the set of character pairs. Suppose now that we the pair of substitution keys in the

**ciphertext alphabet:**

**Then each of the following strings are valid ciphertext:**

## LVRKYHLVABZVRKHOHOVRHOXPWTLXQOMJNUYHFTNBTCFVYHJNQOHOMCZABQMCSH

## UDZAYHUDQKZVZAHOXODSXOMJTCLXSHMJRNBQFTNBWTZVBQXPQOHOIGZABQMCSH

## LVRKYHUDQKZVRKXOXODSHOXPTCLXQOPYRNBQEZNBTCFVBQXPSHHOIGZAYHMCSH

## LVZABMUDABFVRKHOHODSHOXPWTLXQOPYRNBQEZNBTCZVBQXPQOXOIGZABQMCQO

Moreover, each uniquely deciphers back to the original plaintext.ciphers are periodic substitution ciphers, which substitutes the (mj + i)-th plaintext character using the i-th key, where 1 ≤ i ≤ m. The number m is called the period.

Vigen`re cipher. The Vigen`re cipher is a polyalphabetic translation cipher, that is, e e each of the m keys speciﬁes an aﬃne translation.

Suppose that we take our standard alphabet {A, B,..., Z} with the bijection with

**Z/26Z = {0, 1,..., 25}. Then beginning with the message:**

**This gives the encoded plaintext:**

## HUMANSALVATIONLIESINTHEHANDSOFTHECREATIVELYMALADJUSTED

The with the enciphering key UVLOID, the Vigen`re enciphering is given by performing e**the column additions:**

## HUMANS ALVATI ONLIES INTHEH ANDSOF THECRE ATIVEL YMALAD JUSTED

## UVLOID UVLOID UVLOID UVLOID UVLOID UVLOID UVLOID UVLOID UVLOID

-------------------------------------------------------------BPXOVV UGGOBL IIWWMV CIEVMK UIOGWI NCPQZH UOTJMO SHLZIG DPDHMG Recall that the addition is to be carried out in Z/26Z, with the bijection deﬁned by the

**following table:**

## ABCDEFGHIJ K L M N O P Q R S T U V W X Y Z

D. Polygram substitution ciphers. A polygram substitution cipher is a cryptosystem in which blocks of characters are substituted in groups. For instance (for a particular key) AA could map to NO, AB to IR, JU to AQ, etc. These cryptosystems make cryptanalysis harder by destroying the single character frequencies, preserved under simple substitution ciphers.General aﬃne ciphers. An aﬃne cipher can be generalised to polygram ciphers. Rather than a map m → c = ma + b, we can apply a linear transformation of vectors

Recall that a substitution cipher permutes the characters of the plaintext alphabet, or may, more generally, map the plaintext characters into a diﬀerent ciphertext alphabet. In a transposition cipher, the symbols of the plaintext remain the same unchanged, but their order is permuted by a permutation of the index positions. Unlike substitution ciphers, transposition ciphers are block ciphers.

The relation between substitution ciphers and transposition ciphers is illustrated below. The characters and their positions of the plaintext string ACATINTHEHAT appear in a graph with a character axis c and a position index i for the 12 character block 1 ≤ i ≤ n.

We represented as a graph a substitution cipher (with equal plaintext and ciphertext alphabets) is realised as a permutation of the rows of the array, while a transposition cipher is realised by permuting the columns in ﬁxed size blocks, in this case 12.

The symmetric group Sn is the set of all bijective maps from the set {1,..., n} to itself, and we call an elements π of Sn a permutation. We denote the n-th composition of π with itself by π n. As a function write π on the right, so that the image of j is (j)π.

Exercise. Show that for every π in Sn, there exists an positive integer m, such that π m is the identity map, and such that m divides n!. The smallest such m is called the order of π.

The map (j)π = ij can be denoted by [i1,..., in ]. This is the way, in eﬀect, that we have described a key for a substitution cipher — we list the sequence of characters in the image of A, B, C, etc. Although these permutations act on the set of the characters A,..., Z rather than the integers 1,..., n, the principle is identical.

An element of Sn is called a transposition if and only if it exhanges exactly two elements, leaving all others ﬁxed.

Exercise. How many transpositions exist in Sn ? Describe the elements of order 2 in Sn.

How many are there?

Exercise. Show that every element of Sn can be expressed as the composition of at most n transpositions.

refers to a disjoint union, that is, ik is not equal to (iℓ )π j for any j where the symbol unless k = ℓ. The sets {(ik )π j : j ∈ Z} are called the orbits of π, and the cycle lengths of π are the sizes d1,..., dt of the orbits.

Asociated to any orbit decomposition we can express an element π as

Note that if dk = 1, then we omit this term, and the identity permutation can be written just as 1. This notation gives more information about the permutation π and is more compact for simple permutations such as transpositions.