Transcribed Text
What is Cryptography?
Cryptography is the science of encoding and decoding a message to be sent between people or
machines. The goal is to protect the content of the message by using an algorithm to first
encode the original content so it is hidden or obscured in some way, send the message to its
destination, and then have it decoded back to its original message using another algorithm that
(hopefully) only the intended recipient is aware of. If someone intercepts the message during its
journey, they will only find the encoded message and will not understand its true content.
Essentially, cryptography is the practice of sending secret messages.
Caesar Shift
A very simple encoding scheme is the Caesar Shift, used by Julius Caesar to communicate
military matters during the rise of the Roman Empire. For this cipher, each letter of the alphabet
is replaced by another letter a constant shift away. For example, say the message to send is
AGENT 007, ATTACK AT DAWN . Encoding with a Caesar Shift of 1 would replace A with B,
B with C, C with D, etc. (Z would wrap around and be replaced with A). If we call the original
text “plaintext” and the encoded text “ciphertext,” we then have:
plaintext: Agent 007, ATTACK AT DA WN!
⇓
(Caesar Shi ft of 1)
⇓
ciphertext: Bhfou 00 7, BUUBDL BU EBXO!
Since the Caesar Shift just rotates the alphabet by a fixed number, it’s also called a ROT cipher.
The above example is a ROT1 cipher. To decrypt a ROT1 cipher, you would use a ROT(-1)
cipher (or a ROT25 cipher). Note that only letters are shifted; punctuation and numbers stay the
same. Also, capital letters remain capital and lower case letters remain lower. A ROT13 cipher
is very common on the Internet since it’s its own decryption cipher. Why should you never use a
ROT26 cipher?
Mathematically, the Caesar Shift can be written using the modulus operator %, which returns
the remainder after dividing two numbers. For example, 10 % 7 returns the value of 3, since 10
divided by 7 is 1 with a remainder of 3. However, 7 % 10 returns the value of 7, since 7 divided
by 10 is zero with a remainder of 7. Assign numbers to each letter of the alphabet (A = 0, B =
1, …, Z = 25). So, if p represents the plaintext and c represents the ciphertext and k is the shift
number, then the i
th letter of the ciphertext (ci
) is computed from the i
th letter of the plaintext (pi
)
by:
ci = (pi + k) % 26
You might want to check out these short videos describing the Caesar Shift. And check out this
video while you’re at it (encoded with, well, I’m sure you can figure out the shift number; it’s a
web address after all; note that the “0” near the end is the number zero):
pbbxa://eee.gwcbcjm.kwu/eibkp?d=sLKFui0d-nG
Vigenère Cipher
You’ve probably guessed that the Caesar Shift is not a very secure cipher. Since there are only
25 possible shifts (or keys), one could just try all 25 until the message was decoded. This is
known as a brute-force attack. Also, since each letter is just substituted for another, the letter
frequencies of the English language are preserved. This can help you determine what the
appropriate key shift is just by looking at the ciphertext. For example, if the letter X appears
most frequently in the ciphertext, then it probably corresponds to the letter E in the plaintext.
A more secure approach is to use a different shift value for each letter of the plaintext. This can
be done using a keyword. Say you want to encode the plaintext ATTACK using the keyword
SECRET. The keyword tells what shift values to use by interpreting each letter as a number (A =
0, B = 1, …, Z = 25). So, for example, the keyword SECRET means to use shift values of 18
(S) for the first letter of the plaintext, 4 (E) for the second letter of the plaintext, 2 (C) for the third
letter of the plaintext, and so on like so:
A T T A C K
⇓ ⇓ ⇓ ⇓ ⇓ ⇓
(Shift of 18; S) (Shift of 4; E) (Shift of 2; C) (Shift of 17; R) (Shift of 4; E) (Shift of 19; T)
⇓ ⇓ ⇓ ⇓ ⇓ ⇓
S X V R G D
Thus the plaintext ATTACK encoded with the keyword SECRET yields the ciphertext SXVRGD.
You can see that the Vigenère Cipher is just a series of Caesar Ciphers with a different shift key
for each letter of the plaintext. You can see one immediate advantage to the Vigenère Cipher:
the letter frequencies of the plaintext are obscured. Even though the letters A and T occur twice
in the plaintext, no letters are repeated in the ciphertext. This makes an attack by frequency
analysis of ciphertext letters much more difficult.
In the above example, the plaintext and keyword had the same length. Typically though, the
plaintext is much longer than the keyword so one just repeats the keyword to the desired
plaintext message length. For example, if the plaintext were AGENT 007, ATTACK AT
DAWN! encoded with a keyword SECRET, we would have:
plaintext: AGENT 007, ATTACK AT DAWN!
keyphrase: SECRE TSECRE TS ECRE
ciphertext: SKGEX 007, TLXCTO TL HCNR!
To decrypt a Vigenère Cipher, just encode the ciphertext with the Vigenère Cipher again but use
negative shifts for the keyword values. Mathematically, to encode plaintext pi
into ciphertext ci
,
ci = (pi + ki
) % 26
where ki
is the appropriate shift determined from the letter of the keyword. To decode ciphertext
ci back into plaintext pi
, do
pi
= (ci
− ki
) % 26
Of course, the real challenge is decoding a Vigenère-encrypted message without knowing the
keyword. In these cases, you first priority is to deduce the length of the keyword. Once the
keyword length (call it n) is known, then there’s only 26n
- 1 keywords that are possible. While
that’s still a large number of keywords to check by hand
(456,975 possible keys for n = 4), it isn’t a problem for a computer to check them all rather
quickly.
Standard Assignment (all must complete)
1. Write a C program (or a Python program) that can both encrypt and decrypt a
message using the Caesar Cipher. The program should handle upper/lower cases and
non-alphabet characters correctly. That is, upper case letters should be rotated to
upper case letters, lower case letters should be rotated to lower case letters, and all
other characters (numbers, spaces, punctuation, etc.) should remain unchanged. When
prompted for a key, it should work for any reasonable positive integer key value (not just
limited from 0 to 25). For example, here is a screenshot of what the program might look
like when run:
2. Write a C program (or a Python program) that can both encrypt and decrypt a
message using the Vigenère Cipher when the keyword is given by the user. The
program should handle upper/lower cases and non-alphabet characters correctly. That
is, upper case letters should be mapped to upper case letters, lower case letters should
be mapped to lowercase letters, and all other characters (numbers, spaces, punctuation,
etc.) should remain unchanged. The keyword should be provided by the user for both
encryption and decryption, and the correctly constructed keyphrase using the keyword
must be shown (see below). For example, here is a screenshot of what the program
might look like when run:
3. Submit a video and answers to the standard questions outlined in the problem set rubric
that we have been using since the beginning of the course. These submissions are in
addition to your actual program.
Hacker Assignment (optional)
Write a C program (or a Python program) that attempts to determine the keyword for a given
Vigenère ciphertext. There are two aspects of a keyword that make it hard to discover. First,
longer keywords repeat less often which makes their discovery dependent on sufficient
quantities of ciphertext. Second, keywords with duplicate letters can appear to repeat more
often than they really do. Below are examples of an easy, a medium, and a hard challenge
including plaintext, keyword, and ciphertext. These are for practice. To get the bragging rights
associated with the hacker assignment you will have to bring your program to our office and
discover the keyword for a ciphertext of our choosing. To complete this challenge, you’ll
probably need to use a Hash and dictionary file.
Easy
plaintext: When in the Course of human events, it becomes necessary for one people to
dissolve the political bands which have connected them with another, and to assume among the
powers of the earth, the separate and equal station to which the Laws of Nature and of Nature's
God entitle them, a decent respect to the opinions of mankind requires that they should declare
the causes which impel them to the separation. We hold these truths to be self-evident, that all
men are created equal, that they are endowed by their Creator with certain unalienable Rights,
that among these are Life, Liberty and the pursuit of Happiness.
keyword: jefferson
ciphertext: Fljs me lvr Lszwwv gt udqfs imwbgb, my gitgarb rjhijkoeh jtw sew drxtqj xf vwfbsqai
kzs cxpnymtsz ojrix ayaqu qeaj gffbrlxji xywa jrxm frflvra, esi xf sgfdqj fqffu gqi utavjg bo xmj
irjhu, clj xigsfnci fsh viinu wyfxzgb gx amngy lvr Uebx sw Fogdvj fru gt Ajxzwi'j Ycq nrynxcw
hunq, f iitwbg aixuitl hb clj ttzfwbww tk qrfyvwh wjulafrb xmfx kzsl bltzpu vspuewj xyw qndwjx
ayaqu rqujp kzsz cs ymi jwdnaeynse. Os uxpi ylvks gayymw kg pr biqk-imarrwx, ymek szy vis
fvv ufrjxji ihmoy, clfy xywm nai jshfosq kc ymizj Qeneytv nahu liwyezf iajpnjrrtzr Amlmxj, lvnc
ertrx lvrbi fwi Catr, Umgjvkq oam xmj tljghrx tk Lrhdvwixx.
Medium
plaintext: We may yet prevail. That's a conceit, but it's a healthy one. I wonder if the Emperor
Honorius watching the Visigoths coming over the seventh hill truly realized that the Roman
Empire was about to fall. This is just another page in history, isn't it? Will this be the end of our
civilization?
keyword: picard
ciphertext: Lm oap btb rrvypqn. Tydi'a c cfqrmkt, sxi qv's r ktintyb dvg. I nrclgr zi ipg Edstzqr
Yrcwtilv livcylco vhv Yxakgfwwa eodlco qvvu ipg svytvvh ylat vrlon zgaclomf tydi bje Irbip
Edsxzg wrv pjquk wd nclc. Wwqu ij mjav aeripgr gdvm kn ylhbqrp, lhv'v ik? Zxtn tylh jg tyh tvf ow
rjz eimlaqbakldv?
Hard
plaintext: So we beat on, boats against the current, borne back ceaselessly into the past.
keyword: nickcarraway
ciphertext: Fw yo derk oj, bmnbu kiazesp tfr kwbteek, bkrlr jcmm cvrsalcfani knkf tde nnav.
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.
###
### Method to perform Vigenere Encoding
###
def vigenereEncode(plaintext, keyword):
alphabet = "abcdefghijklmnopqrstuvwxyz"
i = 0
keyphrase = ""
for j in range(len(plaintext)):
if plaintext[j].lower() in alphabet:
keyphrase += keyword[i]
i += 1
i = i % len(keyword)
else:
keyphrase += " "
ciphertext = ""
for i in range(len(plaintext)):
if keyphrase[i] != " ":
p_i = alphabet.index(plaintext[i].lower())
k_i = alphabet.index(keyphrase[i].lower())
c_i = (p_i + k_i) % 26
c = alphabet[c_i]
if plaintext[i] == plaintext[i].upper():
c = c.upper()
ciphertext += c
else:...