Subject: HW-1 Date: Wed, 13 Feb 2008 08:49:18 -0500 Thread-Topic: HW-1 Thread-Index: AchuRzraDswEohI0Sr+7TDy69MDSsQ== From: "Burdell" To: 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, Jim ]-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. [burdell3@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)