Playfair Cipher - Explanation + Setup

Summary

This video tutorial delves into the Playfair cipher, a block cipher that encrypts pairs of letters using a 5x5 matrix, known as the Polybius square. It contrasts with stream ciphers by encrypting two letters at a time, creating 600 possible 'digrams'. The video explains the cipher's initialization with a key matrix, handling of repeated letters, and the encryption process involving shifting within rows or columns and swapping for diagonals. It also covers decryption, which reverses these steps, and provides insights into coding the algorithm in C++, emphasizing modular arithmetic and matrix manipulation.

Takeaways

• 🔐 The Playfair cipher is a block cipher that encrypts two letters at a time, unlike stream ciphers which encrypt one letter at a time.
• 🔢 It uses a 5x5 matrix known as the Polybius square to arrange the letters of the alphabet, omitting one letter (traditionally 'J') to fit into the matrix.
• 🔄 The Playfair cipher has three rules for encryption: shift right for same row, shift down for same column, and swap columns for diagonal.
• 🔐 The process involves a pre-initialization stage where a key matrix is generated from the user's input key.
• 🔡 The key matrix is filled by first placing the key letters into the matrix without repetition, then filling the rest with the remaining letters of the alphabet.
• ✂️ If a plain text has an odd number of letters, 'X' is added to make it even for the encryption process.
• 🔄 Decryption in Playfair is the reverse of encryption, using the same rules but in opposite directions for shifting.
• 💻 The script describes a method for coding the Playfair cipher in C++, including functions for encryption, decryption, creating pairs, and generating the key matrix.
• 🔍 The 'find in matrix' function is used to check if a letter has already been used in the key matrix to avoid repetitions.
• 🔗 The script emphasizes the importance of managing spaces and ensuring the string length is even for the encryption process to work correctly.

Q & A

What is the main difference between stream ciphers and block ciphers?

Stream ciphers encrypt one letter at a time, whereas block ciphers encrypt multiple letters at once. The Playfair cipher, for example, encrypts two letters at a time.

Why is the Playfair cipher considered a block cipher?

The Playfair cipher is considered a block cipher because it encrypts two letters at a time, forming what are called 'digrams', as opposed to the one-letter-at-a-time approach of stream ciphers.

How many possible digrams are there in the Playfair cipher?

There are 600 possible digrams in the Playfair cipher, calculated by the formula 25 factorial over 23 factorial, since it encrypts two letters at a time.

What is a Polybius square and how does it relate to the Playfair cipher?

A Polybius square is a 5x5 2D array or matrix used in the Playfair cipher to place each letter of the alphabet. It's related to the Playfair cipher as it forms the basis of the key matrix used for encryption.

Why is the letter 'J' omitted in the Playfair cipher's Polybius square?

The letter 'J' is omitted in the Playfair cipher's Polybius square because the matrix is 5x5, allowing only 25 letters. 'J' is typically removed, but any letter can be omitted; 'J' is a standard choice.

What is the pre-initialization stage in the Playfair cipher?

The pre-initialization stage in the Playfair cipher involves generating a key matrix using the user-provided key, which is then used for encryption.

How are pairs created from plain text in the Playfair cipher?

Pairs are created by splitting the plain text into pairs of two letters each. If a letter is repeated, an 'X' is inserted to break the repetition, and if the text length is odd, an 'X' is added at the end.

What are the three rules for encrypting pairs in the Playfair cipher?

The rules for encrypting pairs are: if pairs are on the same row, shift right modulo 5; if on the same column, shift down modulo 5; if diagonal, swap the columns but keep the rows.

How does decryption work in the Playfair cipher?

Decryption in the Playfair cipher is the reverse of encryption: shift left modulo 5 for same-row pairs, shift up modulo 5 for same-column pairs, and swap columns for diagonal pairs.

Why is the 'removeX' function necessary in the Playfair cipher?

The 'removeX' function is necessary to remove any 'X' letters that were inserted to handle repeated letters or odd-length plain text, ensuring the original message is accurately reconstructed after decryption.

Outlines

00:00

🔐 Introduction to the Playfair Cipher

The video introduces the Playfair cipher, contrasting it with stream ciphers by explaining that it's a block cipher encrypting two letters at a time instead of one. The concept of digraphs is introduced, and the necessity of a 5x5 Polybius square is explained, which accommodates 25 unique letters of the alphabet (excluding 'j'). The video also covers the pre-initialization process of creating a key matrix using the user-inputted key, ensuring no letter repeats in the matrix. The process of preparing the plaintext for encryption by creating pairs of letters is also discussed, including the handling of repeated letters and odd-length strings.

05:01

🔄 Playfair Cipher Encryption Process

This section delves into the encryption rules of the Playfair cipher. It explains how to handle pairs of letters based on their position relative to each other in the key matrix: shifting right for same-row pairs, shifting down for same-column pairs, and swapping columns for diagonal pairs. The video provides a step-by-step example of how to encrypt the word 'hello' using the Playfair cipher, resulting in the ciphertext 'kgyvrv'. The decryption process is also briefly touched upon, indicating that it involves reversing the encryption steps.

10:01

💻 Coding the Playfair Cipher Algorithm

The paragraph discusses the implementation of the Playfair cipher algorithm in C++. It emphasizes the need to handle spaces and repeated letters when preparing the plaintext for encryption. The process involves adding letters one by one, inserting an 'x' when a repeat is detected, and ensuring the final string length is even by appending an 'x' if necessary. The paragraph also mentions the inclusion of necessary header files and the use of a 'find in matrix' function to locate letters within the key matrix.

15:02

🔑 Generating the Key Matrix

This part of the script explains how to generate the key matrix for the Playfair cipher. It involves inserting letters of the key into a 5x5 grid while ensuring no repeats, then filling the remaining spaces with the rest of the alphabet, excluding any letters already used. The process is facilitated by a 'used' vector to track inserted letters and a counter to manage the transition from inserting key letters to filling in the alphabet. Special attention is given to omitting the letter 'j' by default.

20:07

📝 Final Thoughts on the Playfair Cipher Implementation

The final paragraph briefly confirms the successful implementation of the key matrix generation for the Playfair cipher. It implies that the algorithm is working as expected, suggesting a positive outcome from the efforts to code the cipher in C++.

Keywords

💡Playfair cipher

The Playfair cipher is a type of encryption technique categorized as a block cipher. It encrypts two letters (a pair) at a time, rather than individual letters as in stream ciphers. In the video, this cipher is the focus of the explanation, and its encryption process involves a 5x5 matrix and rules that dictate how pairs of letters are encrypted.

💡Block cipher

A block cipher encrypts data in fixed-size blocks, in contrast to stream ciphers, which encrypt one letter at a time. In the Playfair cipher, two letters are encrypted at a time, forming what are called diagrams or bigrams. This concept is central to understanding how the Playfair cipher operates, as it processes chunks of data rather than individual letters.

💡Polybius square

The Polybius square is a 5x5 grid used in the Playfair cipher to arrange letters of the alphabet for encryption. It can only hold 25 letters, so one letter (usually 'J') is omitted. This square is essential for mapping pairs of letters and applying the rules of encryption in the Playfair method.

💡Diagrams/bigrams

In the Playfair cipher, two-letter combinations (called diagrams or bigrams) are used instead of single letters. This pairing method expands the possible encrypted outputs, increasing the complexity of the cipher. The video explains that there are 600 possible diagrams, which greatly strengthens the encryption compared to single-letter (monogram) ciphers.

💡Key matrix

The key matrix is a 5x5 grid filled with letters used in the Playfair cipher. This matrix is generated based on a key provided by the user. It determines how pairs of letters are encrypted. In the video, the 'create key matrix' function is essential for setting up the encryption process by arranging the alphabet and filling in the remaining letters after accounting for the key.

💡Modular arithmetic

Modular arithmetic is used in the Playfair cipher to handle shifts when encrypting letters. For example, when letters are shifted right or down within the 5x5 matrix, if they go beyond the edge of the grid, they wrap around to the beginning, using modulo 5 arithmetic. This ensures that the encryption process stays within the boundaries of the matrix.

💡Encrypt function

The encrypt function in the Playfair cipher takes the key matrix and the pairs of letters (bigrams) and applies the rules of encryption. Depending on whether the pairs are in the same row, column, or diagonal in the matrix, different shifting or swapping operations are performed to encrypt the data. This function is crucial to the overall process described in the video.

💡Decrypt function

The decrypt function reverses the Playfair encryption process by applying inverse operations to retrieve the original plaintext. The same key matrix is used, and the encrypted pairs of letters are shifted or swapped in the opposite direction. This concept highlights the reversible nature of the cipher, allowing encrypted messages to be decoded using the same method.

💡Same row/column rule

In the Playfair cipher, if a pair of letters appears in the same row of the key matrix, they are shifted right (or left during decryption). Similarly, if the pair is in the same column, they are shifted down (or up during decryption). These specific rules govern how letters are encrypted or decrypted, ensuring that the transformation follows a logical pattern within the matrix.

💡Remove X function

The remove X function is used in the decryption process to handle placeholder letters, such as 'X', which are inserted during encryption when duplicate letters or odd-length plaintexts occur. This function ensures that the decrypted message restores the original text by removing unnecessary 'X' characters added during the encryption phase.

Highlights

Introduction to the Playfair cipher, a block cipher that encrypts two letters at a time.

Explanation of the shift from stream ciphers to block ciphers in cryptographic methods.

The Playfair cipher uses a 5x5 matrix, called a Polybius square, to encrypt text.

The concept of 'diagrams' is introduced for two-letter combinations in the Playfair cipher.

Calculation of possible diagrams in the Playfair cipher: 25 factorial over 23 factorial.

Omission of the letter 'j' in the Polybius square to fit 25 letters into a 5x5 matrix.

Pre-initialization stage required to generate a key matrix using the user-inputted key.

Process of filling the Polybius square with the rest of the alphabet after inserting the key.

Handling of repeated letters in plaintext by inserting an 'x' and adjusting pairs.

Ensuring the plaintext length is even for encryption, with an 'x' added if odd.

Three sets of rules for encryption in the Playfair cipher: same row, same column, and diagonal.

Use of modular arithmetic for shifting letters in the matrix.

Decryption process as the reverse of encryption with adjusted shifting directions.

The creation of pairs from plaintext and the handling of repeated letters.

Coding considerations for managing spaces and ensuring even string lengths.

Algorithm for generating the key matrix with checks for repeated letters.

Use of a vector to track used letters and ensure no repeats in the matrix.

Two-stage process for filling the key matrix: inserting the key and then filling in the alphabet.

Method for ensuring no gaps are left in the matrix during the insertion of letters.

Final output of the encrypted text after applying the Playfair cipher rules.

Testing the algorithm with the example 'hello' and the key 'playfair'.

Transcripts

welcome back to another video this video

is on the playfair cipher

so this cipher method is different to

the previous videos we've done

because the previous videos are in a

certain classification of ciphers called

stream ciphers

now we've seen what stream ciphers do a

stream cipher just takes in one letter

at a time

and encrypts over the key the play for

cipher is however

a different type of cipher called a

block cipher

this still isn't modern encryption but

modern cryptography is highly

um oriented around a block ciphers

so in a block cipher instead of

encrypting one letter at a time

this time we're encrypting two letters

at a time

so with the substitution cipher if we're

encrypting one at

a time that means we have 26 possible

monograms right

since there's 26 letters in the alphabet

whereas in the play first cipher

because we're encrypting two letters at

a time but and when you're encrypting

two letters they're called diagrams

instead of monograms

or bi-grams and because we're encrypting

two letters at a time

mata means we have 600 possible diagrams

and you get that by just doing 25

factorial over 23 factorial

and i'll show you why it's 25 and not

26.

in the play first cipher we make use of

this concept called

a polybius square and what this is is

it's simply

a 5x5 2d array or a matrix

and we simply put in each letter in the

alphabet inside of this matrix

although we don't repeat any of the

letters and because

it's five by five that means we can only

have 25 possible entries in the matrix

right

so we can only put 25 letters from the

alphabet in this matrix

as such we have to emit a letter

in this case we omit the letter j so if

you look

at the sequence in in the key block we

go

h i k and we miss the letter j that's

just a standard for the playfair cipher

you can change the letter to anything

you want you can emit whatever

letter you want so unlike the other

cipher methods where you just take in

the key and you encrypt one letter at a

time

in the playfair cipher there is a

pre-initialization stage where you need

to

generate a key matrix using the key

that's inputted by the user and so

simply

if we have the key playfair and we throw

it into this

create key matrix function the output we

get is

is this 2d array and if you noticed we

don't repeat

any of the letters so your p l a

y f and when you get to a we've seen a

is already in the 2d array

so we skip a and we move to i and then

we go r

now we filled in every letter in the key

so

what we do is we fill in the 2d array

with the rest of the alphabet

starting from the beginning so you try

to add an a because we can see a is

already there

so we do b instead then we add c and d

and then f is already used so we go to g

is already so we go to h okay l is used

so you do m instead

n o p is used so you do q

s t u v w

x and z and y is used in the original

key

and now we're just left with one more

pre-initialization stage

before we can start encrypting and

that's creating the pairs out of our

plain text

now since we're encrypting two letters

at a time we want to

split our string into pairs two letters

at a time right

so if you have the plain text hello and

we throw hello into create pairs

we first split the string into pairs of

two

so we put he on its own l on its own and

o on its own

first of all the playfair cipher doesn't

let you repeat any letters

so instead of pairing l with another l

we pair the first l with an

x that we insert in and then pair the

second l with the o

so it becomes h e l x l o instead

and um they're supposed to be in pairs

but when we're coding this

there won't be any gaps there won't be

any spaces in between so in the end

it'll just look like h e l

x l o now what's important to notice is

since they're in pairs

the length of the string is even however

if we had the case where

the length of our string was odd at this

point that means there is no pair for

the final letter

and so to fix this we would just throw

an x at the end

so now that we've finished

pre-initializing our data

we can start encrypting as you can see

we combine our key matrix with the pairs

that we've generated together and throw

it into the encrypt function

now the playfair cipher has three sets

of rules for encrypting

if our pairs of letters are on the same

row then we

shift right modulo 5. if our pairs of

letters are on the same column then we

shift down modulo 5.

by module 5 i just mean we're doing

modular arithmetic

so if i would usually get an index out

of bounds exception we just use module 5

to loop around the 2d array

and if it's the case that it's neither

on the same row or column that means the

letters are diagonal

and so the method we use is we just swap

the columns but keep the rows

let's take the letters h and e so let's

find where h

and e is in our 2d array so h is here

and e is here so let's look at our rules

that are on the same row

so we shift right to modulo 5. so we

shift h by one unit and it becomes k

and we shift the e by one unit and it

becomes g so our output is k

g as you can see we got kg here

now let's do the next one lx our l is

here and our x is here

they're not on the same row and they're

not on the same color column

so they're diagonal so let's look at the

rule for diagonal we swap the columns

so if i swap the columns first of all

you need to notice that we create a box

here we create a rectangle

and we want the letters on the opposite

corner so we have l and x on these

corners

so the one the opposite one for l is y

and the opposite corner for x is v

so our output is y v such we get y v

here let's look at the final one l o

we have l here and o here they're on the

same row

so we shift down modulo 5. as such we

shift l down to r and o down to v so we

got r

v and as you can see our output is rv so

now that we have

each individual output for our pairs we

just join them together we can cut any

to the strings together so we get kgyv

rv

and that's our final encrypted text

now decrypting is very easy we just do

the exact same thing but in reverse

we have our decrypt function we throw in

the same

k matrix but this time we throw in the

encrypted text instead now if you look

at our encrypt

in our encryption rules if they're on

the same row instead of shifting right

we shift to left modulo 5.

for the same column instead of shifting

um down we shift up modulo 5

and for diagonals that the rule is the

same swap the columns

let's look at kg so k is here

and g's here they're on the same row so

we shift the left modulo 5.

so for k we get h and for g we get to e

so

our output is h e for the next one we

have y

v so y is here and v is here

and there are diagonal so we swap the

columns our output is l and x

such we get l and x and finally r

v we have r here and v here and they're

on the same

row so we they're on the same column

sorry and we shift up modulo 5.

so our output is l in r we concatenate

these together and we get h-e-l-x-l-o

so remember we had this x in the middle

because there was a repeat

l and because of this we need an extra

function here called removex so we throw

this output

into the remove x function and then this

just spits out the original input

without that

x in the middle and here that's that's

how the playfast cipher works and

we cannot start coding it in c plus plus

this looks pretty much identical to what

we've already done

so the functions we're going to be use

we'll be using is encrypt and decrypt

create pairs create key matrix and

remove x

those are the ones i showed you in the

presentation we also have this other one

called find in matrix

you'll see why we need to use that later

and to represent

our key block our key matrix we use a 2d

array

of size 55 i've included the mod

function from the previous videos

because we're going to be using modular

arithmetic

this part's not too important you can

just copy it down because it's not part

of the algorithm

the only difference is i've decided to

make

the generation of the key an option for

the user i don't want to generate the

key every single time

because it requires more computation

than the previous videos

methods so instead we create the key

matrix first

and then we just keep asking for a new

input and an option

and the if the user decides to change

they can put to and for new and then

enter the new key

and so i'll just quickly explain what

this does although why is this

here if they say encode then we

create pairs first like i shot in the

presentation and then we encrypt

we already have the key matrix from here

if they wanted decode

then we can decrypt since we have all

the required information

and then we throw that into removex to

get rid of the x's

and if they want to generate a new key

then

we get the new key and create a key

matrix

i just want to make it clear that we

want to write this algorithm

in a way that we touch spaces because

when we throw this

string into the encrypt function we

don't want the encryption to have to

deal with the overhead of managing

managing spaces

so the first process we're doing is

we're adding one letter at a time

and if it's the case that the letters

that the letters repeat

then we add an x in between them right

that's essentially what we're doing here

i minus one is our current index this is

three times minus one is the current

letter we're dealing with if that letter

is

not a space then we can add the letter

hence why we're doing

plus equals input minus one

um but if we find that there's a repeat

if we find that

i minus one equals a and i also equals a

then instead of adding the second a we

want to add

we want to add a new string plus equals

x and then

we end the for loop there and then we

come back up

we see it's in our space and then we out

of the third a all right

so we add a here then we add x here and

then we need we'll be out the second day

here back when we leave round

[Music]

[Music]

because we treat i minus 1 as the

current letter

and we stop at i is less than size that

means i only gets

as far as size minus 1 right

which means the current letter only gets

as far as size minus 2

which means size -1 isn't included

so no matter the string input

the last letter is always missed we

added that to last letter

an e-string plus equals input size minus

1.

and i remember when i said the length of

the string needs to be even

if it's the case that it's not even and

it's odd then we just

throw that x on the end and then we're

done we can return the string back

oh yeah one more thing you also want to

include these header files

just so you don't get any errors and

also in my

create pairs i had a

reference on the input you want to make

sure that's not there

um i've commented out to the parts of

intermin that i'm not going to use

and i'm just going to output the input

and just to see that we've done this

correctly

so we'll just see our keys play for and

we're trying to encode

hello and let's make sure that we get

what we tested was correct

and yeah we get h e l x l

o as we wanted

um we can now move on to the more

the more interesting part of the

algorithm which is the generation of the

key matrix

how are we going to generate the k

matrix

well if you remember in the explanation

when we take in this

key as a parameter you want to add each

key in the 2d array in order

make sure there's no repeats and then we

want to fill in the rest of the alphabet

the method we're going to use to to make

sure there's no repeats in the 2d array

we'll have this a vector of type char

called used

and this will store all the letters that

we've currently used

so each time that we add a new letter

into the 2d array we want to make sure

that it's not used first

so we'll iterate through this every

single time

um we're going to have to write a little

helper function to

to do that check for us though

[Music]

if this letter points to use dot end

the the memory address after the very

last

element in the vector and that means it

wasn't found so if it's not the case

that it points to out a memory address

then we found it it means it's been used

once we have that done

um accordingly this algorithm is

relatively simple

[Music]

do

so how do we keep track of how many

letters we've added in the 2d array

there's two stages to this algorithm we

first add in the key

and then we fill in the gaps and we can

do that

by using an enter counter variable

if this count is greater than or equal

to the size

then that means we've added in all the

letters in the key

and we're on to the second stage

i remember at the beginning of the video

i saw that

in our key matrix we omit

the letter j by default which means when

we're filling in this k matrix we don't

want to add the letter j we want to skip

it we want to emit this letter

so we do this by simply just adding j

before we enter the loop

we initially add the j to our used

vector

so in the insert key stage we take the

current letter

using our count and we check that this

letter is not found in the vector

if it's the case that we haven't found

the letter that means we can use it

so we just insert the current letter at

the current row and column position

and now that we've used this letter we

don't want to use it again so we

push this letter onto our used vector

if it's the case that we have found this

letter

then we have a problem because

essentially if we don't have this else

statement here

we continue this for loop and we

increment to the column

which means we've just left a gap in the

2d array

if you remember in the previous video

and our solution was to

log back so we log back by doing minus

minus call

so we decrement to the call value and

i'll tell you we're not leaving any gaps

in the 2d array

although we still want to increment the

count because we're moving on to the

next letter

in this this if block here this entire

section is

the insert key stage as i've labeled in

this comment

okay so how do we know where to start

from because

we've already added a bunch of letters

in the 2d array

and we don't know which ones we need to

fill in

well there is no way of knowing so

[Music]

we just saw from the beginning

so when we reach the sauce block we

start from the letter a

and then we iterate all the way to the

letter z

and keep attempting to add on letters

each time

so starting from the letter a if the

letter a has not been found in the

vector

then we add the letter in the key matrix

and then we keep doing this for every

single letter we keep adding on

a letter given that it's not found the

same method i'll use it up here

if it's the case start to be half on the

letter

then we don't want to leave any gaps so

we log behind again

and move on to the next letter in the

alphabet

and this works because the letters are

grouped together and ascii in a

numerical order

and we don't have to worry about going

outside the range of the

of the letters in the ascii table

because we know we're only adding our

marks 25 letters so we're never going to

go that far

and now we have a working cr

key matrix function and we can output it

and see if it works

and as you can see an example it should

be working

yeah it looks like it's working

you