ECE6612 Homework Assignment 1 (HW-1) (v.1.1, 1/25/2008)

Due before 9 a.m. Friday Feb. 1. Video students add 7 days (Feb. 8).

Instructions. Copy this document from the Web Page, or save it from your email
program, as a "text" file. Edit it in a word processor to add the answers into
the square brackets after each question. Save it as a "text" file, and email it
back to me: (jcopeland@ece.gatech.edu).

Email the completed document as the body of a message (not as an attached
document) with the Subject exactly as HW-1 (4 characters). Please send
questions or comments in a separate message, with a different Subject (e.g.,
"Question on HW-1"). Mail with the correct subject will be automatically
filtered into the homework grading program. Including quotes or extra spaces may
prevent your homework submission from being automatically graded.

I will not accept paper returns. If you can not complete the assignment on time,
tell me why and turn it in as soon as possible for partial credit. Remember,
home work grades count as 10% of the final grade. You will receive 100% for
assignments which are done on time and appear to be a valid effort. The exact
percentage grade produced by the grading program is for reference only.

Your return will be graded by a computer program that looks for your answers
between square brackets. Please do not add or delete square brackets (or the
***???*** flags). The format and units of answers should be those indicated in
the problem (e.g., a letter, a group of letters, or a number). Each question
counts equally. Each answer within a question counts equally, but the value
depends on the number of answers within the question. All letters after a number
are ignored so do not use letter multipliers (e.g., M, m, k, etc.).

If the answer is a percentage, the format may be 0.52 or 52% (52 is assumed to
mean 5200%). You must include the % or use a decimal fraction.

We are learning in this course how computers talk securely to each other. At
present there must always be a set of rules (protocol or formatting rules) that
govern the data sent so that a protocol layer or application can understand the
messages it receives. In a protocol PDU every bit has to be correct and in
exactly the right order. The homework submission protocol is far more "free
form", but it is still far from accepting as wide a range of formatting as a
human being.

See http://www.csc.gatech.edu/copeland/jac/6612/hw_tips.html", Tips on
Submitting HW for more information.

--------- (Do not delete anything below this line) ------------------
***START_HW***

[Burdell, Jimk ]-NAME Enter your name (form: last, first )

[burdell3 ]-PRISM Enter your GTNUM as shown on the class rolls. This is the primary GT email account name (used before @gatech.edu). Do not use an alias you have chosen.

[burdell33@gatech.edu ]-EMAIL Enter the email address ("account@server") where you would like
to receive your graded homework and other class information (including quiz grades).
If "GTNUM@gatech.edu" is ok, leave this blank.

#1. Break the following ciphertext by frequency analysis or brute force:

"d1zk0z8b02vkdzx1k1878bzk27cebzck_v2b7zcck_8bkzfzbi"

This is a Caesar-type substitution code using the following set of 37 characters
(for plaintext and ciphertext):

"0123456789abcdefghijklmnopqrstuvwxyz_"

There is no quote (") or space ( ) characters in this alphabet.
It uses underscore (_) to separate English words. A character
probability table derived from similar plaintext messages is as follows:

_ 16.7%, e 11.1%, o 9.3%, s 9.3%, r 7.4%, t 7.4%, a 5.6%,
c 5.6%, i 5.6%, d 3.7%, n 3.7%, w 3.7%, f 1.9%, h 1.9%,
l 1.9%, m 1.9%, p 1.9%, y 1.9%

There is a Excel spreadsheet (XLS) that can help,
http://www.csc.gatech.edu/copeland/jac/6612/tools/subs_code_spr08.xls

[k ] - Which cipher character represents space "_". Do this by
inspection, or looking at the frequency analysis on the right side of the XLS.

[the_georgia_tech_honor ] - type in the first 22 characters of the plaintext (be sure
to use "_" and not " ").

You can "cut and paste" the answer above from XLS cell F6 if the key is found.

#2. To be effective, an encryption algorithm must require an uneconomical
amount of resources to break.

Assuming no systematic shortcut is known for breaking a code, what is the
maximum number of keys that would be needed to break the following by an
exhaustive key search:

[64! ] - A Caesar-type substitution, like the above, but with 64 characters).

[1.246e89 ] - A general substitution code (64-characters) Hint: Sterling's
approximation,
n! =sqrt(6.28n)*(n/e)^n e=2.719. (Answer in scientific notation, like
1.234e5).

[2^56 ] - DES with a 56-bit key (express as a power of 2, like 2^19).

[2^64 ] - Word processor with a 64-bit key (express as a power of 2, like 2^19).

[1/2 ] - What percentage of possible keys would be used on the average to find
the correct key (fraction or %).

[137 ] - If a supercomputer can try 100,000,000 keys per second, how long in
months (on average) would it take to decipher a DES message by a brute-force
attack?

#3. Trudi intercepts a DES ECB (Electronic Code Book) encrypted message with 64-
bit blocks c1, c2, c3, ... .

Which of the following can she do without garbling other parts of the message
(True/False)?
"Garbling" means that about half of the bits are randomly changed.

[T ] - She can delete certain blocks of the message or insert copies of blocks
(T/F)?

[T ] - She can rearrange the order of the blocks (T/F)?

[F ] - She can defeat an MIC or MAC by only changing the order of the blocks
(T/F)?

#4. Trudi intercepts a 3-DES CBC (Cipher Block Chaining) encrypted message with
64-bit blocks c1, c2, c3, ... .

She wants to change the bit 8 of the block 6 of the decrypted message m1, m2,
m3, ... .

[5 ] - Which block does she tamper with (the number)?

[8 ] - Which bit does she change (the number)?

[5 ] - Which decrypted message block is garbled (the number, zero if none)?

***END_HW*** (do not delete preceding flag) (1.1 - web)