Transcript Mathematical Concepts in Cryptography 355

Mathematical Concepts in
Cryptography 355
Brian Tafel, Mark Shippy
Raymond Fuller, and Mireya
The Hill Cipher uses linear algebra to
disguise frequency patterns that occur in
natural language.
A. In the forward direction or
encryption process we use matrix
multiplication.
B. In the reverse or decryption
process we use matrix inversion.
C. First, let’s learn a little about
linear algebra.
Matrix Multiplication
Linear system
2x + 3y – 4z = 5
-2x
+ z =7
3x + 2y + 2z = 3
| 2 3 -4 | | 5 |
A = | -2 0 1 | | 7 |
| 3 2 2| |3|
|x|
X=|y|
|z|
Linear system in matrix form
AX = B
|5|
B=|7|
|3|
Matrix Multiplication
Key matrix GYBNQKURP = 6,24,1,13,16,10,20,17,15
| 6 24 1 | | 0 |
| 13 16 10 | | 2 |
| 20 17 15| | 19 |
ACT
POH
| 57 |
| 15|
= | 122 | = |14| MOD 26
| 169 |
|7|
A = 0, C = 2, T = 19
Becomes the cipher text
P = 15, O = 14, H = 7
( 6)(0) + (24)(2) + ( 1)(19) = 57
(13)(0) + (16)(2) + (10)(19) = 122
(20)(0) + (17)(2) + (15)(19) = 169
Matrix Decryption
First you take the inverse of the Key matrix,
which is too horrible to explain. This gives you
IFKVIVVMI = 8,5,10,21,8,21,21,12,8
Using are Encrypted cipher text POH = 15,14,7
| 8 5 10 | | 15 |
| 260 |
|0|
| 21 8 21 | | 14 | = | 574 | = | 2| mod 26
| 539 |
|19|
|21 12 8 | | 7 |
Which gives us are message 0,2,19 or ACT
Use of Determinants
If the determinate is zero, or has factors like 2 and 13 then we
cannot use Hill Cipher. One variant uses 3 extra symbols to
make the modulus 29 (prime).
| a b|
= ab–cd
| c d|
2 X 2 Matrix
|a bc |
| d e f | = a(ej – hf) – b(dj – gf) + c(dh – ge)
|g h j |
3 X 3 Matrix
Mechanical Implementation
Hill and a partner were
awarded a patent for a
6 x 6 matrix mod 26
machine using gears and
chains.
Theories such as Hill’s
became automated during the
Industrial Revolution.
In 1927 this led to the
Enigma machine.
Drawbacks of Hill cipher
The Linearity of the cipher is its downfall.
The know Plaintext attack is where the attacker Has
samples of both the Plaintext and Encrypted versions.
During WWII the Germans would give a
weather forecast every day at the same time. The
message would contain the word wetter in the same
location in every message.
Knowing the local weather also helped guess
the other parts of the message.
Question ????
The Hill Cipher utilizes
What type of complex
mathematics?
Answer
Linear Algebra