Symmetric Key Encryption
Background:
One way of encrypting a string (or
a password) is to shift every character in the string by a certain value. For
example, the sentence, “who are you” can be encrypted as “gry
kbo iye”, where every letter
is shifted to the right by a value of 10.
During the process of shifting the
letters, if the letters go beyond ‘z’, a wraparound of the letters is performed
to ensure the letters in the encrypted string are between ‘a’ and ‘z’. For
decrypting the string, “gry kbo
iye”, we can shift the letters to the left by 10 to
obtain “who are you”. Again, a wraparound is done to ensure all the letters are
between ‘a’ and ‘z’.
The above technique of encryption,
where an identical key is used for both encryption and decryption is called
Symmetric Key Encryption.
Problem
#1:
Write a program that takes an input string and an integer input
(the value to shift the letters to the right) and prints the encrypted string.
Further, add a method to decrypt the encrypted string. Use the “value” variable
to shift the letters of the encrypted string to the left. Perform the
wraparound to ensure all letters of the decrypted string are the between ‘a’
and ‘z’.
· Solution
Example:
Encryption and Decryption
Input the sentence to be decoded - Only alphabets and spaces and
lower case
who are you
Input shift value - 1, 2.....26
21
Encrypted Text = rcj vmz
tjp
Decrypted Text = who are you
Problem
#2:
The algorithm described above
(shifting right to encrypt and left to decrypt by a certain integer) can be
easily hacked. Let’s say we happen to know a system which uses the symmetric
key encryption as described above. If the encryption key (shift value) is
unknown, we can still gain access to the system by following the steps
below:
1)
Find the most repeated letter in the encrypted string and replace
it with the most common letter in the English language.
2)
Shift the other letters accordingly.
For this problem, you will implement the algorithm below
(describes the above two steps in detail):
Description:
a)
The input to your program will be an encrypted string. Your program should be able to decrypt it without
the knowledge of the value by which all the letters in the encrypted string
have been shifted.
b)
For example, let’s say the input to your program is the encrypted
string: “rcj vmz tjp”
c)
The letter that repeats the most in the encrypted string is ‘j’.
d)
As per this
Wikipedia link, the ten most common letters (in decreasing order) used in
English language are: e, t, a, o, i, n, s, h, r, d. For the
sake of this program, we will assume that the encrypted string will contain at
least one occurrence of these letters.
e)
If we replace the letter ‘j’ in the encrypted string with ‘e’, we
would have shifted ‘j’ by 5 places to the left. Moving all the other letters by
five places to the left would yield, “mxe qhu oek”,
which would be incorrect. We would then replace the next most common letter in
the encrypted string, ‘r’ with ‘e’ and move all other letters accordingly.
f)
The process described in e) will continue until we are able to
successfully decrypt or we are unsuccessful in decrypting even after replacing
every letter (in decreasing order of their frequency) in the encrypted string
with the letter ‘e’. If the latter is true, we will then replace the most
repeated letter in the encrypted string, ‘j’ with ’t’ and repeat step e). If we
are unsuccessful in decrypting with ‘t’, we will repeat step e) with a, o, i, n, s, h, r, d.
g)
Since we have assumed that the encrypted string will contain at
least one occurrence of e, t, a, o, i,
n, s, h, r, d, we will be successful in decrypting it.
h)
Store the string that was encrypted (“who are you” for Example #1)
in a string variable and repeatedly compare it with the decrypted string to
check if the guess is accurate.
(See examples below)
· Solution
Example:
#1:
Decrypting a Symmetric Key String
Input Encrypted Text:
rcj
vmz tjp (“who are you”)
Checking with the letter: e
Try#1 Most Common Letter = j
Try#1 Decrypted Text Guess = mxe qhu oek
Unsuccessful - Trying the next most common letter
Try#2 Most Common Letter = r
Try#2 Decrypted Text Guess = epw izm gwc
Unsuccessful - Trying the next most common letter
Try#3 Most Common Letter = c
Try#3 Decrypted Text Guess = tel xob vlr
Unsuccessful - Trying the next most common letter
Try#4 Most Common Letter = v
Try#4 Decrypted Text Guess = als evi csy
Unsuccessful - Trying the next most common letter
Try#5 Most Common Letter = m
Try#5 Decrypted Text Guess = jub ner lbh
Unsuccessful - Trying the next most common letter
Try#6 Most Common Letter = z
Try#6 Decrypted Text Guess = who are you
Accurate!
Successfully decrypted in 6 trials
#2:
Decrypting a Symmetric Key String
Input Encrypted Text:
uf ime m oaxp yadzuzs
(“it was a cold morning”)
Checking with the letter: e
Try#1 Most Common Letter = u
Try#1 Decrypted Text Guess = ep swo w ykhz iknjejc
Unsuccessful - Trying the next most common letter
Try#2 Most Common Letter = m
Try#2 Decrypted Text Guess = mx aew e gsph qsvrmrk
Unsuccessful - Trying the next most common letter
Try#3 Most Common Letter = a
Try#3 Decrypted Text Guess = yj mqi q sebt cehdydw
Unsuccessful - Trying the next most common letter
Try#4 Most Common Letter = z
Try#4 Decrypted Text Guess = zk nrj r tfcu dfiezex
Unsuccessful - Trying the next most common letter
Try#5 Most Common Letter = f
Try#5 Decrypted Text Guess = te hld l nzwo xzcytyr
Unsuccessful - Trying the next most common letter
Try#6 Most Common Letter = i
Try#6 Decrypted Text Guess = qb eia i kwtl
uwzvqvo
Unsuccessful - Trying the next most common letter
Try#7 Most Common Letter = e
Try#7 Decrypted Text Guess = uf ime m oaxp yadzuzs
Unsuccessful - Trying the next most common letter
Try#8 Most Common Letter = o
Try#8 Decrypted Text Guess = kv ycu c eqnf oqtpkpi
Unsuccessful - Trying the next most common letter
Try#9 Most Common Letter = x
Try#9 Decrypted Text Guess = bm ptl t vhew fhkgbgz
Unsuccessful - Trying the next most common letter
Try#10 Most Common Letter = p
Try#10 Decrypted Text Guess = ju xbt b dpme npsojoh
Unsuccessful - Trying the next most common letter
Try#11 Most Common Letter = y
Try#11 Decrypted Text Guess = al osk s ugdv egjfafy
Unsuccessful - Trying the next most common letter
Try#12 Most Common Letter = d
Try#12 Decrypted Text Guess = vg jnf n pbyq zbeavat
Unsuccessful - Trying the next most common letter
Try#13 Most Common Letter = s
Try#13 Decrypted Text Guess = gr uyq y amjb kmplgle
Unsuccessful - Trying the next most common letter
Checking with the letter: t
Try#14 Most Common Letter = u
Try#14 Decrypted Text Guess = te hld l nzwo xzcytyr
Unsuccessful - Trying the next most common letter
Try#15 Most Common Letter = m
Try#15 Decrypted Text Guess = bm ptl t vhew fhkgbgz
Unsuccessful - Trying the next most common letter
Try#16 Most Common Letter = a
Try#16 Decrypted Text Guess = ny bfx f htqi rtwsnsl
Unsuccessful - Trying the next most common letter
Try#17 Most Common Letter = z
Try#17 Decrypted Text Guess = oz cgy g iurj suxtotm
Unsuccessful - Trying the next most common letter
Try#18 Most Common Letter = f
Try#18 Decrypted Text Guess = it was a cold morning
Accurate!
Successfully decrypted in 18 trials