1. Historical Ciphers Implementing an attack on Vigenre ciphers (in case the period t is unknown). Breaking the following three ciphertexts: 1. "eiwemwotrnwrbpglqthnkquchtvleznwxzavfnghbmekqtvzmvjztzivvymjlivfjmurmitjyvh cuvzjgxkmpkbtvilgjgiaiadvccmpmukmgrwnyyyifqojkztvitnvbreiauzarkgxvfegtxpakfpm qaqwktmpwfjmuxvktpnibwvvyyinamrvlpglxcgcghzxgifpiaakdnaxumeyycbkinrgslqvvyct tztakutgbgvyatgbctprwxqvxvlibwvqwadfxtgoktvpipzapeivfvjtvbzqdcraivktyafikjultlace yyhmpmgegvfizqkmgfikjultizwxzbtwuwtvqdipukgrtbmfrlsxnnktgtgbugrlhhnmptpnibqq eycwbpgjsqlmywvlibvbtfbjvbqqemuxtmekpdgqkurlsvwurlrxgopcjyaewegucatjwtrrtlkpg dchhnavzjazzmckcgvwurccmbbgofqihnejzawtzmgerxkmtallhnqbgurdimvcebetxmt 2. "efkenhkisrpegjiwgqdzvsuwuirqemrvqgmmsgjqbipvwgqdtnlfvycvxuqyuozsmhjpwczwnis wbfxfkitwpbhreefsexnaejtgmrgjiuhagshjnzcbqvilvpqruepvvetefumeqdnjmsxjcxllvlchuhiy qvljwhfqjgbogsixzgpblnvyusbthtruhexieqvrsdwuiwjaoxproievmccvecsklwvp xjsqplecko gvxlvlesziokckzgqrigrywaciygfertikoievmccvecspliyggvfabyvlrfkkeyoeevucylwlujiwgjigb uvgtvflqzqnelkbqelhzzvglqbtiucbwclxzucbiqcrfsrucvmvfvuinpwqtqcwkcglkwrnphvvqhou wviwmrgkrvfasovxzgpwjrniehddhbgjsplgbotwhucaaejsntsjghgzmqikekwuklroiucrhnbpcy tmeggvecyefxbzlausfvshktxwaeiw gvxvtinmgcmnmkwfbscgrcbpeuiii" 3. "ilvdytrxbkbewbtseiitthbqnmghumsastdrjfincmkwcjmgzwlqwkunntbwbnplelvdjxrfchnlc pfvqibxzdriqjeavmgenixuxvmxcqnmekaceubgprxhswxymtxzgoattaxvgwfdhnmumffqzhf qsdpj Tasks: (a) Try to identify the plaintexts and keys for them, respectively. If you can successfully derive the plaintext and key, give the results; otherwise, discuss why. (b) Submit the source code separately (any programming language). (c) Given different plaintexts and ciphertexts, the designed attack may not accurately re- turn all the results (you may be able to see this in the attacks). Try to compare the difficulties for breaking them. For instance, which one is the most difficult one, and why; which one is likely to return an inaccurate result, and why; and more. 2. Perfect Secrecy. 2.1. Vigenre Cipher. Let II denote the Vigenre cipher where the message space M consists of all 3-character strings (over the English alphabet), and the key is generated by first choosing the period t uniformly from {1,2,3} and then letting the key be a uniform string of length t. = (a) Define A as follows: A outputs mo = aab and m = abb. When given a ciphertext c, it outputs ( if the first character of c is the same as the second character of c, and outputs 1 otherwise. Compute PrPrivk411 = 1). (b) Construct and analyze an adversary A' for which Pr[Privka II 1] is greater than your answer from part (a). 2.2. Permutation Cipher. What is the largest message space M for which the permu- tation cipher provides perfect secrecy? Justify your answer. 3. Pseudorandomness Let l(.) be a polynomial, and algorithm G be a PRG to output a string of length l(n) upon any input s {0,1}". 1() is named as the expansion factor of the PRG. Given l(n) > 2n, in each of the following cases, say whether G' is necessarily a PRG. If yes, give a proof; if not, show a counterexample. (a) Define G'(s) def G(81 - 8[n/21), where s = 81 --- Sn. def G(01s|||s). (b) Define G' (s) (c) Define G'(s) def G(8)||G(s +1). 1. Historical Ciphers Implementing an attack on Vigenre ciphers (in case the period t is unknown). Breaking the following three ciphertexts: 1. "eiwemwotrnwrbpglqthnkquchtvleznwxzavfnghbmekqtvzmvjztzivvymjlivfjmurmitjyvh cuvzjgxkmpkbtvilgjgiaiadvccmpmukmgrwnyyyifqojkztvitnvbreiauzarkgxvfegtxpakfpm qaqwktmpwfjmuxvktpnibwvvyyinamrvlpglxcgcghzxgifpiaakdnaxumeyycbkinrgslqvvyct tztakutgbgvyatgbctprwxqvxvlibwvqwadfxtgoktvpipzapeivfvjtvbzqdcraivktyafikjultlace yyhmpmgegvfizqkmgfikjultizwxzbtwuwtvqdipukgrtbmfrlsxnnktgtgbugrlhhnmptpnibqq eycwbpgjsqlmywvlibvbtfbjvbqqemuxtmekpdgqkurlsvwurlrxgopcjyaewegucatjwtrrtlkpg dchhnavzjazzmckcgvwurccmbbgofqihnejzawtzmgerxkmtallhnqbgurdimvcebetxmt 2. "efkenhkisrpegjiwgqdzvsuwuirqemrvqgmmsgjqbipvwgqdtnlfvycvxuqyuozsmhjpwczwnis wbfxfkitwpbhreefsexnaejtgmrgjiuhagshjnzcbqvilvpqruepvvetefumeqdnjmsxjcxllvlchuhiy qvljwhfqjgbogsixzgpblnvyusbthtruhexieqvrsdwuiwjaoxproievmccvecsklwvp xjsqplecko gvxlvlesziokckzgqrigrywaciygfertikoievmccvecspliyggvfabyvlrfkkeyoeevucylwlujiwgjigb uvgtvflqzqnelkbqelhzzvglqbtiucbwclxzucbiqcrfsrucvmvfvuinpwqtqcwkcglkwrnphvvqhou wviwmrgkrvfasovxzgpwjrniehddhbgjsplgbotwhucaaejsntsjghgzmqikekwuklroiucrhnbpcy tmeggvecyefxbzlausfvshktxwaeiw gvxvtinmgcmnmkwfbscgrcbpeuiii" 3. "ilvdytrxbkbewbtseiitthbqnmghumsastdrjfincmkwcjmgzwlqwkunntbwbnplelvdjxrfchnlc pfvqibxzdriqjeavmgenixuxvmxcqnmekaceubgprxhswxymtxzgoattaxvgwfdhnmumffqzhf qsdpj Tasks: (a) Try to identify the plaintexts and keys for them, respectively. If you can successfully derive the plaintext and key, give the results; otherwise, discuss why. (b) Submit the source code separately (any programming language). (c) Given different plaintexts and ciphertexts, the designed attack may not accurately re- turn all the results (you may be able to see this in the attacks). Try to compare the difficulties for breaking them. For instance, which one is the most difficult one, and why; which one is likely to return an inaccurate result, and why; and more. 2. Perfect Secrecy. 2.1. Vigenre Cipher. Let II denote the Vigenre cipher where the message space M consists of all 3-character strings (over the English alphabet), and the key is generated by first choosing the period t uniformly from {1,2,3} and then letting the key be a uniform string of length t. = (a) Define A as follows: A outputs mo = aab and m = abb. When given a ciphertext c, it outputs ( if the first character of c is the same as the second character of c, and outputs 1 otherwise. Compute PrPrivk411 = 1). (b) Construct and analyze an adversary A' for which Pr[Privka II 1] is greater than your answer from part (a). 2.2. Permutation Cipher. What is the largest message space M for which the permu- tation cipher provides perfect secrecy? Justify your answer. 3. Pseudorandomness Let l(.) be a polynomial, and algorithm G be a PRG to output a string of length l(n) upon any input s {0,1}". 1() is named as the expansion factor of the PRG. Given l(n) > 2n, in each of the following cases, say whether G' is necessarily a PRG. If yes, give a proof; if not, show a counterexample. (a) Define G'(s) def G(81 - 8[n/21), where s = 81 --- Sn. def G(01s|||s). (b) Define G' (s) (c) Define G'(s) def G(8)||G(s +1)
