Playfair Cipher - Explanation + Setup
Summary
TLDRThis 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
🔐 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.
🔄 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.
💻 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.
🔑 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.
📝 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++.
Mindmap
Keywords
💡Playfair cipher
💡Block cipher
💡Polybius square
💡Diagrams/bigrams
💡Key matrix
💡Modular arithmetic
💡Encrypt function
💡Decrypt function
💡Same row/column rule
💡Remove X function
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
تصفح المزيد من مقاطع الفيديو ذات الصلة
5.0 / 5 (0 votes)