Cryptography review and Vigenere Cipher
General Notes:
For simplicity we will assume that
we are only encoding letters and not numbers. All letters are also upper case.
Shift Cipher
The shift cipher is a simple cipher
that involves identifying a number between 1 and 25 and shifting the alphabet
by that number by the shift to identify the alphabet used for substitution.
For all examples, the message used
in encryption is ‘THIS MESSAGE IS SECURE’. Although not normally used in these
types of exercises, spaces have been preserved.
Shift
of 1
A shift of 1 turns A into B, B into
C, etc. The pattern follows for a shift of 1:
##
ORIGINAL : ABCDEFGHIJKLMNOPQRSTUVWXYZ
##
ENCRYPTED : BCDEFGHIJKLMNOPQRSTUVWXYZA
Decrypting the message involves
reversing the substitution (B becomes A, C becomes B, etc)
The message after encryption is
below:
##
ORIGINAL : THIS MESSAGE IS SECURE
##
ENCRYPTED : UIJT NFTTBHF JT TFDVSF
Shift
of 5
A shift of 5 turns A into F, B into
G, etc. The pattern follows for a shift of 5:
##
ORIGINAL : ABCDEFGHIJKLMNOPQRSTUVWXYZ
##
ENCRYPTED : FGHIJKLMNOPQRSTUVWXYZABCDE
Decrypting the message involves
reversing the substitution (F becomes A, G becomes B, etc)
The message after encryption is
below:
##
ORIGINAL : THIS MESSAGE IS SECURE
##
ENCRYPTED : YMNX RJXXFLJ NX XJHZWJ
Shift
of 13
A shift of 5 turns A into N, B into
O, etc. The pattern follows for a shift of 13:
##
ORIGINAL : ABCDEFGHIJKLMNOPQRSTUVWXYZ
##
ENCRYPTED : NOPQRSTUVWXYZABCDEFGHIJKLM
Decrypting the message involves
reversing the substitution (N becomes A, O becomes B, etc)
The message after encryption is
below:
##
ORIGINAL : THIS MESSAGE IS SECURE
##
ENCRYPTED : GUVF ZRFFNTR VF FRPHER
Breaking
Shift Ciphers
Shift ciphers can be broken easily
by trying a number of combinations (it is also possible to use frequency
analysis). Consider breaking the ROT13 cipher by repeatedly applying the shift
of 1 until something makes sense:
##
ENCRYPTED : GUVF ZRFFNTR VF FRPHER
##
ROTATION 1: HVWG ASGGOUS WG GSQIFS
##
ROTATION 2: IWXH BTHHPVT XH HTRJGT
##
ROTATION 3: JXYI CUIIQWU YI IUSKHU
##
ROTATION 4: KYZJ DVJJRXV ZJ JVTLIV
##
ROTATION 5: LZAK EWKKSYW AK KWUMJW
##
ROTATION 6: MABL FXLLTZX BL LXVNKX
##
ROTATION 7: NBCM GYMMUAY CM MYWOLY
##
ROTATION 8: OCDN HZNNVBZ DN NZXPMZ
##
ROTATION 9: PDEO IAOOWCA EO OAYQNA
##
ROTATION 10: QEFP JBPPXDB FP PBZROB
##
ROTATION 11: RFGQ KCQQYEC GQ QCASPC
##
ROTATION 12: SGHR LDRRZFD HR RDBTQD
##
ROTATION 13: THIS MESSAGE IS SECURE
##
ROTATION 14: UIJT NFTTBHF JT TFDVSF
##
ROTATION 15: VJKU OGUUCIG KU UGEWTG
##
ROTATION 16: WKLV PHVVDJH LV VHFXUH
##
ROTATION 17: XLMW QIWWEKI MW WIGYVI
##
ROTATION 18: YMNX RJXXFLJ NX XJHZWJ
##
ROTATION 19: ZNOY SKYYGMK OY YKIAXK
##
ROTATION 20: AOPZ TLZZHNL PZ ZLJBYL
##
ROTATION 21: BPQA UMAAIOM QA AMKCZM
##
ROTATION 22: CQRB VNBBJPN RB BNLDAN
##
ROTATION 23: DRSC WOCCKQO SC COMEBO
##
ROTATION 24: ESTD XPDDLRP TD DPNFCP
##
ROTATION 25: FTUE YQEEMSQ UE EQOGDQ
##
ROTATION 26: GUVF ZRFFNTR VF FRPHER
We see that shifting the letters in
the message 13 times provides us with a plausible decryption of the secure
message. An important point here is that applying an encryption more than once
does not necessarily strengthen the encryption (ex. a Shift of 2 is equal to
two shifts of 1 implying that it would take equal time to break two shifts of 1
and a single shift of 2).
Your
Turn
Vigenere Cipher
The Vigenere cipher involves an
application of multiple shift ciphers using a specific code word. Consider
first the following table with 26 rows and 26 columns. This table helps to
identify the characters used for substitution for both an encryption and
decryption operation.
Encryption involves the following
process:
- Repeat the key word for the length of the text to be encrypted
- For each letter of the plain text and repeated key, find the row that corresponds with the message letter and the column that corresponds with the key letter. The intersection of these two values in the table is the letter to substitute for the original message letter.
## 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
##
A 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
##
B 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 A
##
C C 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
##
D 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
##
E 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 D
##
F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
##
G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
##
H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
##
I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
##
J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
##
K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
##
L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
##
M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
##
N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
##
O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
##
P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
##
Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
##
R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
##
S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
##
T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
##
U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
##
V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
##
W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
##
X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
##
Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
##
Z Z 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
Demonstrating by example, let’s
consider the encryption of ‘THIS MESSAGE IS SECURE’ with the key word ‘AQUA’.
The table below summarizes the rows/columns used to make the substitution.
The first five steps of the
encryption are illustrated below:
##
Encryption Step 1:
##
##
Message Letter is T and key letter is A. Using row 20, labeled T, and column 1,
labeled A the encrypted letter is T. Visually, this looks like:
##
## A
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
##
T T - - - - - - - - - - - - - - - - - - - - - - - - -
## |
## |
## |
## |
## |
## |
##
Encryption Step 2:
##
##
Message Letter is H and key letter is Q. Using row 8, labeled H, and column 17,
labeled Q the encrypted letter is X. Visually, this looks like:
##
## Q
## |
## |
## |
## |
## |
## |
## |
##
H - - - - - - - - - - - - - - - - X - - - - - - - - -
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
##
Encryption Step 3:
##
##
Message Letter is I and key letter is U. Using row 9, labeled I, and column 21,
labeled U the encrypted letter is C. Visually, this looks like:
##
##
U
##
|
##
|
## |
##
|
##
|
##
|
##
|
##
|
##
I - - - - - - - - - - - - - - - - - - - - C - - - - -
##
|
##
|
## |
##
|
##
|
##
|
##
|
##
|
##
|
##
|
##
|
## |
##
|
##
|
##
|
##
|
## |
##
Encryption Step 4:
##
##
Message Letter is S and key letter is A. Using row 19, labeled S, and column 1,
labeled A the encrypted letter is S. Visually, this looks like:
##
## A
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
##
S S - - - - - - - - - - - - - - - - - - - - - - - - -
## |
## |
## |
## |
## |
## |
## |
##
Encryption Step 5:
##
##
Message Letter is M and key letter is A. Using row 13, labeled M, and column 1,
labeled A the encrypted letter is M. Visually, this looks like:
##
## A
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
##
M M - - - - - - - - - - - - - - - - - - - - - - - - -
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
## |
The encryption operation can be
summarized using the following table:
## plain key row row_letter col col_letter enc
##
1 T
A 20 T
1 A T
##
2 H
Q 8 H
17 Q X
##
3 I
U 9 I
21 U C
##
4 S
A 19 S
1 A S
##
5 M
A 13 M
1 A M
##
6 E
Q 5 E
17 Q U
##
7 S
U 19 S
21 U M
##
8 S
A 19 S
1 A S
##
9 A
A 1 A
1 A A
##
10 G
Q 7 G
17 Q W
##
11 E
U 5 E
21 U Y
##
12 I
A 9 I
1 A
I
##
13 S
A 19 S
1 A S
##
14 S
Q 19 S
17 Q I
##
15 E
U 5 E
21 U Y
##
16 C
A 3 C
1 A C
##
17 U
A 21 U
1 A U
##
18 R
Q 18 R
17 Q H
##
19 E
U 5 E
21 U Y
The result of the encryption
operation can be seen below:
##
ORIGINAL : THISMESSAGEISSECURE
##
ENCRYPTED : TXCSMUMSAWYISIYCUHY
Decryption involves the following
process:
- Repeat the key word for the length of the encrypted text
- For each letter of the encrypted text and repeated key, find the column that corresponds with the key letter and the cell that corresponds with the letter of the encryted text in that column. The row header is the decrypted letter.
In tabular form, for our encrypted
message:
## enc key col col_letter find_in_col row
row_letter dec
##
1 T
A 1 A T
20 T T
##
2 X
Q 17 Q X
8 H H
##
3 C
U 21 U C
9 I I
##
4 S
A 1 A S
19 S S
##
5 M
A 1 A M
13 M M
##
6 U
Q 17 Q U
5 E E
##
7 M
U 21 U M
19 S S
##
8 S
A 1 A S
19 S S
##
9 A
A 1 A A
1 A A
##
10 W
Q 17 Q W
7 G G
##
11 Y
U 21 U Y
5 E E
##
12 I
A 1 A I
9 I I
##
13 S
A 1 A S
19 S S
##
14 I
Q 17 Q I
19 S S
##
15 Y
U 21 U
Y 5 E
E
##
16 C
A 1 A C
3 C C
##
17 U
A 1 A U
21 U U
##
18 H
Q 17 Q H
18 R R
##
19 Y
U 21 U Y 5
E E
The result of the decryption
operation can be seen below:
##
ENCRYPTED : TXCSMUMSAWYISIYCUHY
##
DECRYPTED : THISMESSAGEISSECURE
Your
Turn - Encryption
- Using the Vigenere cipher, encrypt the following message with the key word ‘B’: ‘CIPHERS ARE COOL’
- Using the Vigenere cipher, encrypt the following message with the key word ‘ABCD’: ‘CIPHERS ARE COOL’
- Using the Vigenere cipher, encrypt the following message with the key word ‘ABCDEFGHIJKLMN’: ‘CIPHERS ARE COOL’
- Which of the key words in the first 3 exercises is strongest and why? Which is weakest and why?
Your
Turn - Decryption
The following message has been
intercepted: ‘MYETFJWRKLPSE’. Initial cryptanalysis (study of a message to find
its hidden aspects) suggests that the message may have been encrypted using the
Vigenere Cipher. An additional report has been identified that identifies that
one of the following 5 key words will most likely decrypt the message. Your
task is to determine which of the five words provides the most plausible decryption
of the message:
- APPLE
- PEAR
- ORANGE
- BERRY
- MILK
Answers
- Encryption
- DJQIFSTBSFDPPM
## plain key row row_letter col col_letter enc
##
1 C
B 3 C
2 B D
##
2 I
B 9 I
2 B J
##
3 P
B 16 P
2 B Q
##
4 H
B 8 H
2 B I
##
5 E
B 5 E
2 B F
##
6 R
B 18 R
2 B S
##
7 S
B 19 S
2 B T
##
8 A
B 1 A
2 B B
##
9 R
B 18 R
2 B S
##
10 E
B 5 E
2 B F
##
11 C
B 3 C
2 B D
##
12 O
B 15 O
2 B P
##
13 O
B 15 O
2 B P
##
14 L
B 12 L
2 B M
- CJRKESUDRFEROM
## plain key row row_letter col col_letter enc
##
1 C
A 3 C
1 A C
##
2 I
B 9 I
2 B J
##
3 P
C 16 P
3 C R
##
4 H
D 8 H
4 D K
##
5 E
A 5 E
1 A E
##
6 R
B 18 R
2 B S
##
7 S
C 19 S
3 C U
##
8 A
D 1 A
4 D D
##
9 R
A 18 R
1 A R
##
10 E
B 5 E
2 B F
##
11 C
C 3 C
3 C E
##
12 O
D 15 O
4 D R
##
13 O
A 15 O
1 A O
##
14 L
B 12 L
2 B M
- CJRKIWYHZNMZAY
## plain key row row_letter col col_letter enc
##
1 C
A 3 C
1 A C
##
2 I
B 9 I
2 B J
##
3 P
C 16 P
3 C R
##
4 H
D 8 H
4 D K
##
5 E
E 5 E
5 E I
##
6 R
F 18 R
6 F W
##
7 S
G 19 S
7 G Y
##
8 A
H 1 A
8 H H
##
9 R
I 18 R
9 I Z
##
10 E
J 5 E
10 J N
##
11 C
K 3 C
11 K M
##
12 O
L 15 O
12 L Z
##
13 O
M 15 O
13 M A
##
14 L
N 12 L
14 N Y
- The longest keyword is the strongest because it ensures that each of the ciphers for the Vigenere cipher is used only once, potentially creating dificulties for a cryptanalysis using a tool such as frequency analysis. Use of keys that are unpredictable and equal length to the unencrypted text provide a provably secure system (so long as the key is not obtained in another manner… see also the ‘One Time Pad’ encryption scheme for more details). The weakest key is the shortest key, ‘A’ because only one of the substitution ciphers is used, allowing the message to be brute forced trying 26 possible shifts.
Answers
- Decryption
Using each of the key words for
decryption, the following plain texts are identified:
- decrypt(‘MYETFJWRKLPSE’,‘APPLE’) = ‘MJPIBJHCZHPDP’
## enc key col col_letter find_in_col row
row_letter dec
##
1 M
A 1 A M
13 M M
##
2 Y
P 16 P Y
10 J J
##
3 E P
16 P E
16 P P
##
4 T
L 12 L T
9 I I
##
5 F
E 5 E F
2 B B
##
6 J
A 1 A J
10 J J
##
7 W
P 16 P
W 8 H
H
##
8 R
P 16 P R
3 C C
##
9 K
L 12 L K
26 Z Z
##
10 L
E 5 E L
8 H H
##
11 P
A 1 A P
16 P P
##
12 S
P 16 P S
4 D D
##
13 E
P 16 P E
16 P P
- decrypt(‘MYETFJWRKLPSE’,‘PEAR’) = ‘XUECQFWAVHPBP’
## enc key col col_letter find_in_col row
row_letter dec
##
1 M
P 16 P M
24 X X
##
2 Y
E 5 E Y
21 U U
##
3 E
A 1 A E
5 E E
##
4 T
R 18 R T
3 C C
##
5 F
P 16 P
F 17 Q
Q
##
6 J
E 5 E J
6 F F
##
7 W
A 1 A W
23 W W
##
8 R
R 18 R R
1 A A
##
9 K
P 16 P K
22 V V
##
10 L
E 5 E L
8 H H
##
11 P
A 1 A P
16 P P
##
12 S
R 18 R S
2 B B
##
13 E
P 16 P E
16 P P
- decrypt(‘MYETFJWRKLPSE’,‘ORANGE’) = ‘YHEGZFIAKYJOQ’
## enc key col col_letter find_in_col row
row_letter dec
##
1 M
O 15 O M
25 Y Y
##
2 Y
R 18 R Y
8 H H
##
3 E
A 1 A E
5 E E
##
4 T
N 14 N T
7 G G
##
5 F
G 7 G F
26 Z Z
##
6 J
E 5 E J
6 F F
##
7 W
O 15 O W
9 I I
##
8 R
R 18 R R
1 A A
##
9 K
A 1 A K
11 K K
##
10 L
N 14 N L
25 Y Y
##
11 P
G 7 G P
10 J J
##
12 S
E 5 E S
15 O O
##
13 E
O 15 O E
17 Q Q
- decrypt(‘MYETFJWRKLPSE’,‘BERRY’) = ‘LUNCHISATNOON’
## enc key col col_letter find_in_col row
row_letter dec
##
1 M
B 2 B M
12 L L
##
2 Y
E 5 E Y
21 U U
##
3 E
R 18 R E
14 N N
##
4 T
R 18 R T
3 C C
##
5 F
Y 25 Y
F 8
H H
##
6 J
B 2 B J
9 I I
##
7 W
E 5 E W
19 S S
##
8 R
R 18 R R
1 A A
##
9 K
R 18 R K
20 T
T
##
10 L
Y 25 Y L
14 N N
##
11 P
B 2 B P
15 O O
##
12 S
E 5 E S
15 O O
##
13 E
R 18 R E
14 N N
- decrypt(‘MYETFJWRKLPSE’,‘MILK’) = ‘AQTJTBLHYDEIS’
## enc key col col_letter find_in_col row
row_letter dec
##
1 M
M 13 M M
1 A A
##
2 Y
I 9 I Y
17 Q Q
##
3 E
L 12 L
E 20
T T
##
4 T
K 11 K T
10 J J
##
5 F
M 13 M F
20 T T
##
6 J
I 9 I J
2 B B
##
7 W
L 12 L W
12 L
L
##
8 R
K 11 K R
8 H H
##
9 K
M 13 M K
25 Y Y
##
10 L
I 9 I L
4 D D
##
11 P
L 12 L P
5 E E
##
12 S
K 11 K S
9 I I
##
13 E
M 13 M E
19 S S
Plain text #4 corresponds to the
most readable message. Adding spaces, we recover the message ‘LUNCH IS AT NOON’
No comments:
Post a Comment