1 of 28

Basic Cryptography

By:

Dr. Mohammad Shoab

Week 2

2 of 28

Symmetric Encryption

or conventional / private-key / single-key
sender and recipient share a common key
all classical encryption algorithms are private-key
was only type prior to invention of public-key in 1970’s
and by far most widely used

2

Cryptography

Department of Computer Science

3 of 28

Some Basic Terminology

plaintext - original message
ciphertext - coded message
cipher - algorithm for transforming plaintext to ciphertext
key - info used in cipher known only to sender/receiver
encipher (encrypt) - converting plaintext to ciphertext
decipher (decrypt) - recovering plaintext from ciphertext
cryptography - study of encryption principles/methods
cryptanalysis (codebreaking) - study of principles/ methods of deciphering ciphertext without knowing key
cryptology - field of both cryptography and cryptanalysis

3

Cryptography

Department of Computer Science

4 of 28

Symmetric Cipher Model

4

Cryptography

Department of Computer Science

5 of 28

Requirements

two requirements for secure use of symmetric encryption:

a strong encryption algorithm
a secret key known only to sender / receiver

mathematically have:

Y = E(K, X)

X = D(K, Y)

assume encryption algorithm is known
implies a secure channel to distribute key

5

Cryptography

Department of Computer Science

There are two requirements for secure use of conventional encryption that mean we assume that it is impractical to decrypt a message on the basis of the cipher- text plus knowledge of the encryption/decryption algorithm, and hence do not need to keep the algorithm secret; rather we only need to keep the key secret. This feature of symmetric encryption is what makes it feasible for widespread use. It allows easy distribution of s/w and h/w implementations.

Can take a closer look at the essential elements of a symmetric encryption scheme: mathematically it can be considered a pair of functions with: plaintext X, ciphertext Y, key K, encryption algorithm E, decryption algorithm D. The intended receiver, in possession of the key, is able to invert the transformation. An opponent, observing Y but not having access to K or X, may attempt to recover X or K.

6 of 28

Cryptography

can characterize cryptographic system by:

type of encryption operations used

substitution
transposition
product

number of keys used

single-key or private
two-key or public

way in which plaintext is processed

block
stream

6

Cryptography

Department of Computer Science

Cryptographic systems can be characterized along these three independent dimensions.

The type of operations used for transforming plaintext to ciphertext. All encryption algorithms are based on two general principles: substitution, in which each element in the plaintext (bit, letter, group of bits or letters) is mapped into another element, and transposition, in which elements in the plaintext are rearranged. The fundamental requirement is that no information be lost (that is, that all operations are reversible). Most systems, referred to as product systems, involve multiple stages of substitutions and transpositions.
The number of keys used. If both sender and receiver use the same key, the system is referred to as symmetric, single-key, secret-key, or conventional encryption. If the sender and receiver use different keys, the system is referred to as asymmetric, two-key, or public-key encryption.
The way in which the plaintext is processed. A block cipher processes the input one block of elements at a time, producing an output block for each input block. A stream cipher processes the input elements continuously, producing output one element at a time, as it goes along.

7 of 28

Cryptanalysis

objective to recover key not just message
general approaches:

cryptanalytic attack
brute-force attack

if either succeed all key use compromised

7

Cryptography

Department of Computer Science

Typically objective is to recover the key in use rather then simply to recover the plaintext of a single ciphertext. There are two general approaches:

Cryptanalysis: relies on the nature of the algorithm plus perhaps some knowledge of the general characteristics of the plaintext or even some sample plaintext- ciphertext pairs. This type of attack exploits the characteristics of the algorithm to attempt to deduce a specific plaintext or to deduce the key being used.

Brute-force attacks try every possible key on a piece of ciphertext until an intelligible translation into plaintext is obtained. On average,half of all possible keys must be tried to achieve success.

If either type of attack succeeds in deducing the key, the effect is catastrophic: All future and past messages encrypted with that key are compromised.

8 of 28

Cryptanalytic Attacks

ciphertext only

only know algorithm & ciphertext, is statistical, know or can identify plaintext

known plaintext

know/suspect plaintext & ciphertext

chosen plaintext

select plaintext and obtain ciphertext

chosen ciphertext

select ciphertext and obtain plaintext

chosen text

select plaintext or ciphertext to en/decrypt

8

Cryptography

Department of Computer Science

9 of 28

More Definitions

unconditional security

no matter how much computer power or time is available, the cipher cannot be broken since the ciphertext provides insufficient information to uniquely determine the corresponding plaintext

computational security

given limited computing resources (eg time needed for calculations is greater than age of universe), the cipher cannot be broken

9

Cryptography

Department of Computer Science

10 of 28

Brute Force Search

always possible to simply try every key
most basic attack, proportional to key size
assume either know / recognise plaintext

Key Size (bits)	Number of Alternative Keys	Time required at 1 decryption/µs	Time required at 10⁶ decryptions/µs
32	2³² = 4.3 × 10⁹	2³¹ µs = 35.8 minutes	2.15 milliseconds
56	2⁵⁶ = 7.2 × 10¹⁶	2⁵⁵ µs = 1142 years	10.01 hours
128	2¹²⁸ = 3.4 × 10³⁸	2¹²⁷ µs = 5.4 × 10²⁴ years	5.4 × 10¹⁸ years
168	2¹⁶⁸ = 3.7 × 10⁵⁰	2¹⁶⁷ µs = 5.9 × 10³⁶ years	5.9 × 10³⁰ years
26 characters (permutation)	26! = 4 × 10²⁶	2 × 10²⁶ µs = 6.4 × 10¹² years	6.4 × 10⁶ years

10

Cryptography

Department of Computer Science

11 of 28

Classical Substitution Ciphers

where letters of plaintext are replaced by other letters or by numbers or symbols
or if plaintext is viewed as a sequence of bits, then substitution involves replacing plaintext bit patterns with ciphertext bit patterns

11

Cryptography

Department of Computer Science

12 of 28

Caesar Cipher

earliest known substitution cipher
by Julius Caesar
first attested use in military affairs
replaces each letter by 3rd letter on
example:

meet me after the toga party

PHHW PH DIWHU WKH WRJD SDUWB

12

Cryptography

Department of Computer Science

13 of 28

Caesar Cipher

can define transformation as:

a b c d e f g h i j k l m n o p q r s t u v w x y z

D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

mathematically give each letter a number

a b c d e f g h i j k l m n o p q r s t u v w x y z

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

then have Caesar cipher as:

c = E(k, p) = (p + k) mod (26)

p = D(k, c) = (c – k) mod (26)

13

Cryptography

Department of Computer Science

14 of 28

Cryptanalysis of Caesar Cipher

only have 26 possible ciphers

A maps to A,B,..Z

could simply try each in turn
a brute force search
given ciphertext, just try all shifts of letters
do need to recognize when have plaintext
eg. break ciphertext "GCUA VQ DTGCM"

14

Cryptography

Department of Computer Science

15 of 28

Monoalphabetic Cipher

rather than just shifting the alphabet
could shuffle (jumble) the letters arbitrarily
each plaintext letter maps to a different random ciphertext letter
hence key is 26 letters long

Plain: abcdefghijklmnopqrstuvwxyz

Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN

Plaintext: ifwewishtoreplaceletters

Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA

15

Cryptography

Department of Computer Science

16 of 28

Monoalphabetic Cipher Security

now have a total of 26! = 4 x 10²⁶ keys
with so many keys, might think is secure
but would be !!!WRONG!!!
problem is language characteristics

16

Cryptography

Department of Computer Science

17 of 28

Language Redundancy and Cryptanalysis

human languages are redundant
eg "th lrd s m shphrd shll nt wnt"
letters are not equally commonly used
in English E is by far the most common letter

followed by T,R,N,I,O,A,S

other letters like Z,J,K,Q,X are fairly rare
have tables of single, double & triple letter frequencies for various languages

17

Cryptography

Department of Computer Science

18 of 28

English Letter Frequencies

18

Cryptography

Department of Computer Science

19 of 28

Use in Cryptanalysis

key concept - monoalphabetic substitution ciphers do not change relative letter frequencies
discovered by Arabian scientists in 9^th century
calculate letter frequencies for ciphertext
compare counts/plots against known values
if caesar cipher look for common peaks/troughs

peaks at: A-E-I triple, NO pair, RST triple
troughs at: JK, X-Z

for monoalphabetic must identify each letter

tables of common double/triple letters help

19

Cryptography

Department of Computer Science

The simplicity and strength of the monoalphabetic substitution cipher meant it dominated cryptographic use for the first millenium AD. It was broken by Arabic scientists. The earliest known description is in Abu al-Kindi's "A Manuscript on Deciphering Cryptographic Messages", published in the 9th century but only rediscovered in 1987 in Istanbul, but other later works also attest to their knowledge of the field. Monoalphabetic ciphers are easy to break because they reflect the frequency data of the original alphabet. The cryptanalyst looks for a mapping between the observed pattern in the ciphertext, and the known source language letter frequencies. If English, look for peaks at: A-E-I triple, NO pair, RST triple, and troughs at: JK, X-Z.

Monoalphabetic ciphers are easy to break because they reflect the frequency data of the original alphabet.

20 of 28

Example Cryptanalysis

given ciphertext:

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ

VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX

EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

count relative letter frequencies (see text)
guess P & Z are e and t
guess ZW is th and hence ZWP is the
proceeding with trial and error finally get:

it was disclosed yesterday that several informal but

direct contacts have been made with political

representatives of the viet cong in moscow

20

Cryptography

Department of Computer Science

Illustrate the process with this example from the text in Stallings section 2.2. Comparing letter frequency breakdown with Figure 2.5, it seems likely that cipher letters P and Z are the equivalents of plain letters e and t, but it is not certain which is which. The letters S, U, O, M, and H are all of relatively high frequency and probably correspond to plain letters from the set {a, h, i, n, o, r, s}. The letters with the lowest frequencies (namely, A, B, G, Y, I, J) are likely included in the set {b, j, k, q, v, x, z}. A powerful tool is to look at the frequency of two-letter combinations, known as digrams. A table similar to Figure 2.5 could be drawn up showing the relative frequency of digrams. The most common such digram is th. In our ciphertext, the most common digram is ZW, which appears three times. So we make the correspondence of Z with t and W with h. Then, by our earlier hypothesis, we can equate P with e. Now notice that the sequence ZWP appears in the ciphertext, and we can translate that sequence as "the." This is the most frequent trigram (three- letter combination) in English, which seems to indicate that we are on the right track. Next, notice the sequence ZWSZ in the first line. We do not know that these four letters form a complete word, but if they do, it is of the form th_t. If so, S equates with a. Only four letters have been identified, but already we have quite a bit of the message. Continued analysis of frequencies plus trial and error should easily yield a solution from this point. The complete plaintext, with spaces added between words, is shown on slide.

21 of 28

Rotor Machines

before modern ciphers, rotor machines were most common complex ciphers in use
widely used in WW2

German Enigma, Allied Hagelin, Japanese Purple

implemented a very complex, varying substitution cipher
used a series of cylinders, each giving one substitution, which rotated and changed after each letter was encrypted
with 3 cylinders have 26³=17576 alphabets

21

Cryptography

Department of Computer Science

The next major advance in ciphers required use of mechanical cipher machines which enabled to use of complex varying substitutions.

A rotor machine consists of a set of independently rotating cylinders through which electrical pulses can flow. Each cylinder has 26 input pins and 26 output pins, with internal wiring that connects each input pin to a unique output pin. If we associate each input and output pin with a letter of the alphabet, then a single cylinder defines a monoalphabetic substitution. After each input key is depressed, the cylinder rotates one position, so that the internal connections are shifted accordingly. The power of the rotor machine is in the use of multiple cylinders, in which the output pins of one cylinder are connected to the input pins of the next, and with the cylinders rotating like an “odometer”, leading to a very large number of substitution alphabets being used, eg with 3 cylinders have 26³=17576 alphabets used.

They were extensively used in world war 2, and the history of their use and analysis is one of the great stories from WW2.

22 of 28

Hagelin Rotor Machine

22

Cryptography

Department of Computer Science

23 of 28

Rotor Machine Principles

23

Cryptography

Department of Computer Science

The basic principle of the rotor machine is illustrated in Figure 2.8. The machine consists of a set of independently rotating cylinders through which electrical pulses can flow. Each cylinder has 26 input pins and 26 output pins, with internal wiring that connects each input pin to a unique output pin. If we associate each input and output pin with a letter of the alphabet, then a single cylinder defines a monoalphabetic substitution. If an operator depresses the key for the letter A, an electric signal is applied to the first pin of the first cylinder and flows through the internal connection to the twenty-fifth output pin. Consider a machine with a single cylinder. After each input key is depressed, the cylinder rotates one position, so that the internal connections are shifted accordingly. Thus, a different monoalphabetic substitution cipher is defined. After 26 letters of plaintext, the cylinder would be back to the initial position. Thus, we have a polyalphabetic substitution algorithm with a period of 26.

A single-cylinder system is trivial and does not present a formidable cryptanalytic task. The power of the rotor machine is in the use of multiple cylinders, in which the output pins of one cylinder are connected to the input pins of the next. Figure 2.8 shows a three-cylinder system. With multiple cylinders, the one closest to the operator input rotates one pin position with each keystroke. The right half of Figure 2.8 shows the system's configuration after a single keystroke. For every complete rotation of the inner cylinder, the middle cylinder rotates one pin position. Finally, for every complete rotation of the middle cylinder, the outer cylinder rotates one pin position. The result is that there are 26 " 26 " 26 = 17,576 different substitution alphabets used before the system repeats.

24 of 28

Steganography

an alternative to encryption
hides existence of message

using only a subset of letters/words in a longer message marked in some way
using invisible ink
hiding in LSB in graphic image or sound file

has drawbacks

high overhead to hide relatively few info bits

advantage is can obscure encryption use

24

Cryptography

Department of Computer Science

25 of 28

Cryptography in Digital Forensics

The Role of Cryptography in Digital Forensics-

Encryption Protection

Cryptography is used to secure sensitive information, often making it essential to digital forensics when recovering data.
It involves algorithms that can encode data, preventing unauthorized access.

Forensic Challenges

Investigators often encounter encrypted files, disks, or communications that must be decrypted.
Cryptographic methods ensure data integrity and verify the authenticity of digital evidence.

25

Cryptography

Department of Computer Science

26 of 28

Cont…

How Cryptography Impacts Evidence Collection and Analysis?

Decryption of Evidence

Forensics requires decrypting encrypted files, messages, or communications (e.g., emails, chat logs) for investigation purposes.
Investigators use tools or vulnerabilities in encryption systems to access critical evidence.

26

Cryptography

Department of Computer Science

27 of 28

Cont…

Digital Signatures & Hash Functions

Digital signatures and hash functions ensure that evidence has not been tampered with.
Hash values verify that files collected during an investigation are the exact originals, ensuring authenticity.

Secure Communication & Data Integrity

Cryptography allows secure communication between forensic teams and law enforcement.
It ensures that evidence exchanged over networks is protected from tampering.

27

Cryptography

Department of Computer Science

28 of 28

The End

28

Cryptography

Department of Computer Science