- WELCOME TO A LESSON ON CRYPTOGRAPHY
AND THE SUBSTITUTION CIPHER.
WHEN PEOPLE NEED TO SECRETLY STORE OR COMMUNICATE MESSAGES,
THEY TURN TO CRYPTOGRAPHY.
CRYPTOGRAPHY INVOLVES USING TECHNIQUES TO OBSCURE A MESSAGE
SO OUTSIDERS CANNOT READ THE MESSAGE.
IT IS TYPICALLY SPLIT INTO TWO STEPS,
ENCRYPTION IN WHICH THE MESSAGE IS OBSCURED
AND DECRYPTION IN WHICH
THE ORIGINAL MESSAGE IS RECOVERED
FROM THE OBSCURED FORM.
ONE SIMPLE ENCRYPTION METHOD IS CALLED A SUBSTITUTION CIPHER.
A SIMPLE EXAMPLE OF A SUBSTITUTION CIPHER
IS CALLED THE CAESAR CIPHER
SOMETIMES, CALLED A SHIFT CIPHER.
IN THIS APPROACH, EACH LETTER IS REPLACED
WITH A LETTER SUM FIXED NUMBER OF SPACE,
IN THIS APPROACH EACH LETTER IS REPLACED
WITH A LETTER SUM FIXED NUMBER OF POSITIONS
LATER IN THE ALPHABET.
AS AN EXAMPLE, THE CAESAR CIPHER WITH A SHIFT OF FIVE RIGHT,
WOULD REPLACE "A" WITH F.
NOTICE HOW F IS FIVE POSITIONS TO THE RIGHT OF "A."
IT WOULD REPLACE B WITH G, C WITH H AND SO ON.
SO THE COMPLETE CIPHER ONLY USING THE LETTERS
IN THE ALPHABET WOULD LOOK LIKE THIS WHERE IN BLACK
WE HAVE THE ORIGINAL LETTERS
AND IN RED WE HAVE THE LETTERS THEY WOULD BE MAPPED TO.
LET'S USE THE SHIFT OF FIVE RIGHT TO ENCRYPT
THE FOLLOWING MESSAGE.
MEET AT THE BANK AT 8:00 A.M.
WE'RE ASKED TO WRITE THE FINAL CODE
IN FOUR LETTER BLOCKS WHICH IS COMMON.
WE WOULDN'T WANT TO LEAVE SPACES
WHERE THERE ARE SPACES BETWEEN THE WORDS,
BECAUSE THAT MIGHT HELP SOLVE THE ENCRYPTION.
SO THE FIRST FOUR LETTERS ARE M, E, E, T.
SO M MAPS TO R, E MAPS TO J, AND T MAPS TO Y.
SO WE'LL HAVE R, J, J, Y SPACE,
THE NEXT FOUR LETTERS ARE "A," T, T, H.
THEN WE'LL HAVE E, B, "A," N.
THEN WE'LL HAVE K, "A," T, E THEN WE'LL HAVE "I," J, H, T,
THEN WE'LL HAVE "A," M.
SO FOR "A," T, T, H, WE WOULD HAVE F, Y, Y, M.
FOR E, B, "A," N, WE'LL HAVE J, G, FOR "A" WE'LL HAVE F,
AND FOR N WE'LL HAVE S.
SO F, S.
NEXT WE HAVE K, "A,", T, E.
SO K WE'LL MAP TO P, "A" MAPS TO F, T MAPS TO Y, AND E MAPS TO J.
NEXT WE HAVE "I," G, H, T, "I" MAPS TO N, G MAPS TO L,
H MAPS TO M, T MAPS TO Y, AND THEN WE HAVE "A," M,
"A" MAPS TO F, AND M MAPS TO R.
NOTICE HOW WE'RE TWO LETTERS SHORT OF A FOUR LETTER BLOCK
SO THIS IS OFTEN PADDED WITH AN EXTRA LETTER.
SO LET'S JUST USE "A" TO COMPLETE THE BLOCK.
"A," "A."
THIS WOULD BE THE ENCRYPTION FOR THE GIVEN MESSAGE
USING A SHIFT OF FIVE RIGHT.
NOW WE WANT TO DECRYPT THE WORD R, P, J, H, T
IF IT WAS ENCRYPTED USING AN ALPHABETIC CAESAR SHIFT CIPHER
WITH SHIFT 15 MEANING WE'D MAP "A" TO P.
SO IF WE MAP "A" TO P, B WOULD MAP TO Q,
C WOULD MAP TO R, T WOULD MAP TO S AND SO ON.
NOTICE HOW AFTER K MAPS TO Z,
L MAPS TO THE FIRST LETTER IN THE ALPHABET, WHICH IS "A"
AND SO ON.
NOW TO DECRYPT THIS, LOOK FOR THESE LETTERS IN THE RED ROW,
THEN DETERMINE WHAT THE ORIGINAL LETTER WAS.
SO HERE'S R, P, J, H, AND T.
SO AGAIN R WAS ORIGINALLY C, P WAS ORIGINALLY "A,"
J WAS ORIGINALLY U, H WAS ORIGINALLY S
AND T WAS ORIGINALLY E.
SO THE ORIGINAL WORD WAS CAUSE.
NOTICE IN BOTH OF THE PREVIOUS CIPHERS,
THE EXTRA PART OF THE ALPHABET WRAPPED AROUND TO THE BEGINNING.
BECAUSE OF THIS, A HANDY VERSION OF A SHIFT CIPHER
IS A CIPHER DISC SUCH AS THE ALBERTI CIPHER DISC
SHOWN HERE FROM THE 1400s.
IN THE CIPHER DISC,
THE INNER WHEEL COULD BE TURNED TO CHANGE THE CIPHER SHIFT.
THIS APPROACH IS USED FOR SECRET DECODER RINGS.
THE SECURITY OF A CRYPTOGRAPHIC METHOD
IS VERY IMPORTANT TO THE PERSON RELYING ON THEIR MESSAGE
BEING KEPT SECRET.
THE SECURITY DEPENDS ON TWO FACTORS.
NUMBER ONE, THE SECURITY OF THE METHOD BEING USED,
AND NUMBER TWO, THE SECURITY OF THE ENCRYPTION KEY USED.
IN THE CASE OF A CIPHER SHIFT,
THE METHOD IS SHIFT CIPHER IS USED
AND THE ENCRYPTION KEY IS A SPECIFIC AMOUNT OF SHIFT USED.
SUPPOSE AN ARMY IS USING A SHIFT CIPHER TO SEND THEIR MESSAGES
AND ONE OF THEIR OFFICERS IS CAPTURED BY THEIR ENEMY.
IT IS LIKELY THAT THE METHOD AND ENCRYPTION KEY
COULD BECOME COMPROMISED.
IT IS RELATIVELY HARD TO CHANGE ENCRYPTION METHODS
BUT RELATIVELY EASY TO CHANGE ENCRYPTION KEYS.
FOR EXAMPLE, FOR A SHIFT CIPHER,
WE COULD JUST CHANGE THE AMOUNT OF SHIFT
AND POSSIBLY THE DIRECTION.
DURING WORLD WAR II, THE GERMANS ENIGMA ENCRYPTION MACHINES
WERE CAPTURED BUT HAVING DETAILS ON THE ENCRYPTION METHOD
ONLY SLIGHTLY HELPED THE ALLIES
SINCE THE ENCRYPTION KEYS WERE STILL UNKNOWN
AND HARD TO DISCOVER.
ULTIMATELY THE SECURITY OF A MESSAGE
CANNOT RELY ON THE METHOD BEING KEPT SECRET
AND NEEDS TO RELY ON THE KEY BEING KEPT SECRET.
SECURITY OF AN ENCRYPTION METHOD
SHOULD DEPEND ONLY ON THE ENCRYPTION KEY
BEING DIFFICULT TO DISCOVER.
IT IS NOT SAFE TO RELY ON THE ENCRYPTION METHOD
OR ALGORITHM BEING KEPT SECRET.
A BRUTE FORCE ATTACK IS A METHOD FOR BREAKING ENCRYPTION
BY TRYING ALL POSSIBLE ENCRYPTION KEYS.
SUPPOSE YOU INTERCEPT A MESSAGE AND YOU KNOW THE SENDER USES
A CAESAR CIPHER, BUT DO NOT KNOW OF A SHIFT BEING USED.
LET'S SAY THE MESSAGE BEGINS E, Q, Z, P.
HOW HARD WOULD IT BE TO DECRYPT THIS MESSAGE?
SINCE THERE ARE ONLY 25 POSSIBLE SHIFTS,
SINCE THERE IS 26 LETTERS IN THE ALPHABET,
WE WOULD ONLY HAVE TO TRY 25 POSSIBILITIES TO SEE
WHICH ONE PRODUCED RESULTS THAT MAKE SENSE.
WELL THAT WOULD BE TEDIOUS.
ONE PERSON COULD EASILY DO THIS BY HAND IN A FEW MINUTES.
AND WHY OUR COMPUTER COULD TRY ALL POSSIBILITIES
IN UNDER A SECOND.
SO ON THIS TABLE HERE BELOW,
HERE ARE ALL 25 POSSIBILITIES FOR E, Q, Z, P.
NOTICE HOW ONLY ONE OF THEM REALLY MAKES SENSE
AND THAT WOULD BE A SHIFT OF 12 RIGHT
WHICH WOULD DECRYPT TO THE MESSAGE SEND.
TO MAKE A BRUTE FORCE ATTACK HARDER,
WE COULD MAKE A MORE COMPLEX SUBSTITUTION CIPHER
BY USING SOMETHING OTHER THAN A SHIFT OF THE ALPHABET.
WE COULD GET A MORE SECURE CIPHER WITH A TRADE OFF
IF THE ENCRYPTION KEY IS HARDER TO DESCRIBE.
THE KEY WOULD NOW BE THE ENTIRE MAPPING
RATHER THAN JUST THE SHIFT AMOUNT.
WELL THERE ARE ONLY 25 POSSIBLE SHIFT CIPHER KEYS,
35 IF WE INCLUDE THE DIGITS 0 THROUGH 9.
THERE ARE ABOUT 10 TO THE 40TH POWER
POSSIBLE SUBSTITUTION CIPHERS.
THAT'S MUCH MORE THAN A TRILLION TRILLIONS.
IT WOULD BE ESSENTIALLY IMPOSSIBLE EVEN
WITH SUPER COMPUTERS TO TRY EVERY POSSIBLE COMBINATION.
HAVING A HUGE NUMBER OF POSSIBLE ENCRYPTION KEYS,
IS ONE IMPORTANT PART OF KEY SECURITY.
THERE ARE 35 CHOICES FOR WHAT "A" MAPS
TO IF WE USE ALL THE LETTERS AND THE NUMBERS 0 THROUGH 9
THEN 34 CHOICES FOR WHAT B MAPS TO AND SO ON.
SO A TOTAL NUMBER OF POSSIBILITIES IS 35 x 34 x 33,
ALL THE WAY DOWN 2 x 2 x 1 WHICH WOULD BE EQUAL TO 35 FACTORIAL.
UNFORTUNATELY, THIS CIPHER IS STILL NOT SECURE
BECAUSE OF A TECHNIQUE CALLED FREQUENCY ANALYSIS
DISCOVERED BY ERA MATHEMATICIAN ALCINDE IN THE NINTH CENTURY.
THIS SHOWS THE COMMON FREQUENCY OF LETTERS
IN THE ENGLISH LANGUAGE.
IT MAY BE HARD TO SEE,
BUT NOTICE HOW E HAS THE HIGHEST FREQUENCY FOLLOWED BY T AND "A"
WHICH WE CAN SEE HERE IN THIS -- CHART.
SO BY ANALYZING THE FREQUENCY OF THE LETTERS USED IN A CODE,
IT WOULD MAKE IT EASIER TO DECRYPT THE MESSAGE.
I HOPE YOU FOUND THIS LESSON HELPFUL.