本视频由声明原创。本视频由声明原创。Coursera_Stanford密码学公开课 Programming Assignment 1
题目：通过11个用同样stream cipher密钥加密的密文求最后一个目标密文的明文：
Many Time Pad
Let us see what goes wrong when a stream cipher key is used more than once.Below are eleven hex-encoded ciphertexts that are the result of encryptingeleven plaintexts with a stream cipher, all with the same stream cipher key.Your goal is to decrypt the last
ciphertext, and submit the secret messagewithin it as solution.
Hint: XOR the ciphertexts together, and consider what happens when a spaceis XORed with a character in [a-zA-Z].
ciphertext #1:
315c4eeaa8b5f8aafedc71d885a804e5ee9fa40bfb778cdf2d3aff021dfff5b403b510d0d0455468aebdae857553ccd520e06e515d22c954ebaee5bc41556bdb36bbca3e8774301fbcaa3b83b815fde0f3dbef3e
ciphertext #2:
234c02ecbbfbafa3ed18510abd11fa724fcda2cf064bbde548b12b07df44baef4081ffde5ad46af543bedb9c861bf29c7e205132edac5c4b45f919cf3a9f1cbfcb24cc5b028aa76eb7b4ab24171ab3cdadb8356f
ciphertext #3:
3b2bba9bbc8a3b8ad40b62b07df44ba6e9d8ae0e7b207b70b9b8261112bacb6c866a232dfe398f5fe503c66e935deafb5f41afa8d661cb
ciphertext #4:
32510ba9aab2a8a4fd005cc0aa0dc91aba8ad5ea06aa8adeafe1ac01ac68a1bfccb4efcd3aead45aefda7d835402bca670bda8ebdabbba246b130f040d8ecf3d30ed81ea2e4c10eaaa
ciphertext #5:
3f561ba9adb4b6ebec54418fac0dd35f8c08d31a1fe9e24fec81d9607cee021dafe1e001b21ade877a5e68bea88d61b93ac5ee0d562e8e5f0a4ae20ed86e935defbc65b40aaa065f2a5e33a5a0bb5dcabaf8ec85b7c2070
ciphertext #6:
32510bfbacfbb9befd595ecabd58c519cd4bd2061bbde24eb76a19d84aba34d8de287be84d07e7e9a30eee22a33ecafe8f8db3f0c621854eba0d79eccf52ffcc61d11902aebc66f2b2e436434eacc0aba800c2ca4eb2c4ceac9f26d71b6cf61a711cc229f77ace7aa88a2fbe87a59c355d25f8e4
ciphertext #7:
32510bfbacfbb9befd595ecabd58c519cd4bd90f1fa6ea5ba47b01c909baef40c04afe1ac0aaded9fea125d298e5f4b44f915cb2bd05af5afd96f83414aaaf261bda2e97b170fb5cce2a53e675c154c0d7ee40582afe87ff2270abcf73bbfbdecfecee0a3bbbeb6bf9b13f1efff71ea313cce
ciphertext #8:
315c4eeaa8b5f8bffd1041c6a00c8a0bbde54ceba708b8afff9e00fa7a3bfc860b92f89ee04132ecbd5e4b45e40ecc3b9d59ebba410e9aa2ca24cbaa3acdaada43dc2e04fda9d3
ciphertext #9:
bbb2aeadecabc300ecaa01bd005e9fe4aad6e04d513e96d99deeeeca709b50a8a987f4264edba716132ddc938fb0fed0fcd6ef9cf57fcefa270bda5e933421cbe88a4ae9bd15f652b653b7071aec59a2705081ffec9ed6d76e48b63ab15deef027
ciphertext #10:
466d06ece998b7a2fb1d464fed2ced7641ddaa3cc31cabbf409ed9ccfafb61d0315fca0a314be138a9f32503bedac8067f03adbfedc9ba7fab0f9f3cd04ff50d66f1d559ba520e89a2cb2a83
target ciphertext (decrypt this one):
32510ba9babebbbefde67149caee11d945cd7fc81a05e9f85aac650ecde6f0a803b54fde9e77472dbff89d71b57bddefccb8fe301d16e9f52f904
For completeness, here is the python script used to generate the ciphertexts. (it doesn't matter if you can't read this)
import sys
MSGS = ( ---
11 secret messages
def strxor(a, b):
# xor two strings of different lengths
if len(a) & len(b):
return "".join([chr(ord(x) ^ ord(y)) for (x, y) inzip(a[:len(b)], b)])
return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a,b[:len(a)])])
def random(size=16):
return open("/dev/urandom").read(size)
def encrypt(key, msg):
c= strxor(key, msg)
print c.encode('hex')
def main():
key = random(1024)
ciphertexts = [encrypt(key, msg) for msg in MSGS]
根据提示，空格space的ASCII码二进制形式为。大写字母A～Z的ASCII码二进制形式为～，小写字母a～z的ASCII码二进制形式为 ～。因此若用space和字母做xor操作，则相当于字母切换大小写，而两个字母做xor操作，结果将不在字母范围内。另外由于xor操作的特点，将两个密文做xor操作相当于将两个密文对应的明文做xor操作，如果结果中某个位置出现字母，则说明这两个明文的其中一个在该位置可能为空格，所以基本思路是对11个密文分别做两两xor操作，然后通过结果判断不同明文中可能存在空格的位置，然后将对应位置上的密文和space做xor操作，就可得到对应位置的密钥信息，当获取足够多的密钥信息后，就可以对最后一个目标密文进行解密了。
需要注意的是两个密文xor的结果中出现的字母不一定是space字符和字母xor的结果，从字母的ASCII码可知，小写字母的前四bit是0110，大写字母的前四bit是0100，所以如果某个字符的ASCII码前四bit是这样的形式，那么它和字母xor的结果也可能是另外一个字母，而文本中经常出现的“？”，“！”和“：”等字符就符合这样的特征。另外如果两个文本正好在同一个位置上有空格，则xor操作后该位置得到的字符将是“NULL”。所以对于特定密文，要判断其对应明文可能存在空格的位置的话，我的想法是将该密文和其他10个密文分别做xor操作，每一次操作后记录结果中出现字母的位置，得到一个集合，最终一共得到10个集合，某一个位置在这10个集合中出现的次数越多，越说明该密文对应的明文在该位置可能是空格，因此空格位置的判定条件就是该位置在10个集合中出现的次数。
Python代码：
import sys
ciphertexts=[
"315c4eeaa8b5f8aafedc71d885a804e5ee9fa40bfb778cdf2d3aff021dfff5b403b510d0d0455468aebdae857553ccd520e06e515d22c954ebaee5bc41556bdb36bbca3e8774301fbcaa3b83b815fde0f3dbef3e",
"234c02ecbbfbafa3ed18510abd11fa724fcda2cf064bbde548b12b07df44baef4081ffde5ad46af543bedb9c861bf29c7e205132edac5c4b45f919cf3a9f1cbfcb24cc5b028aa76eb7b4ab24171ab3cdadb8356f",
"3b2bba9bbc8a3b8ad40b62b07df44ba6e9d8ae0e7b207b70b9b8261112bacb6c866a232dfe398f5fe503c66e935deafb5f41afa8d661cb",
"32510ba9aab2a8a4fd005cc0aa0dc91aba8ad5ea06aa8adeafe1ac01ac68a1bfccb4efcd3aead45aefda7d835402bca670bda8ebdabbba246b130f040d8ecf3d30ed81ea2e4c10eaaa",
"3f561ba9adb4b6ebec54418fac0dd35f8c08d31a1fe9e24fec81d9607cee021dafe1e001b21ade877a5e68bea88d61b93ac5ee0d562e8e5f0a4ae20ed86e935defbc65b40aaa065f2a5e33a5a0bb5dcabaf8ec85b7c2070",
"32510bfbacfbb9befd595ecabd58c519cd4bd2061bbde24eb76a19d84aba34d8de287be84d07e7e9a30eee22a33ecafe8f8db3f0c621854eba0d79eccf52ffcc61d11902aebc66f2b2e436434eacc0aba800c2ca4eb2c4ceac9f26d71b6cf61a711cc229f77ace7aa88a2fbe87a59c355d25f8e4",
"32510bfbacfbb9befd595ecabd58c519cd4bd90f1fa6ea5ba47b01c909baef40c04afe1ac0aaded9fea125d298e5f4b44f915cb2bd05af5afd96f83414aaaf261bda2e97b170fb5cce2a53e675c154c0d7ee40582afe87ff2270abcf73bbfbdecfecee0a3bbbeb6bf9b13f1efff71ea313cce",
"315c4eeaa8b5f8bffd1041c6a00c8a0bbde54ceba708b8afff9e00fa7a3bfc860b92f89ee04132ecbd5e4b45e40ecc3b9d59ebba410e9aa2ca24cbaa3acdaada43dc2e04fda9d3",
"bbb2aeadecabc300ecaa01bd005e9fe4aad6e04d513e96d99deeeeca709b50a8a987f4264edba716132ddc938fb0fed0fcd6ef9cf57fcefa270bda5e933421cbe88a4ae9bd15f652b653b7071aec59a2705081ffec9ed6d76e48b63ab15deef027",
"466d06ece998b7a2fb1d464fed2ced7641ddaa3cc31cabbf409ed9ccfafb61d0315fca0a314be138a9f32503bedac8067f03adbfedc9ba7fab0f9f3cd04ff50d66f1d559ba520e89a2cb2a83",
"32510ba9babebbbefde67149caee11d945cd7fc81a05e9f85aac650ecde6f0a803b54fde9e77472dbff89d71b57bddefccb8fe301d16e9f52f904"
KEY_SIZE=100
NUM_CIPHER=len(ciphertexts)
THRESHOLD_VALUE=5
def strxor(a, b):
"""xor two strings of different lengths"""
if len(a) & len(b):
return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a[:len(b)], b)])
return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a, b[:len(a)])])
def letter_position(s):
""" Return the position of letters in the given string """
position=[]
for idx in range(len(s)):
if (s[idx]&='A' and s[idx]&='Z') or (s[idx]&='a' and s[idx]&='z'):
position.append(idx)
return position
def find_space(cipher):
"""Find the position of space"""
space_position={}
space_possible={}
for cipher_idx_1 in range(NUM_CIPHER):
space_xor=[]
for cipher_idx_2 in range(NUM_CIPHER):
plain_xor=strxor(cipher[cipher_idx_1].decode('hex'),cipher[cipher_idx_2].decode('hex'))
if cipher_idx_2!=cipher_idx_1:
space_xor.append(letter_position(plain_xor)) # record the possible value of space
space_possible[cipher_idx_1]=space_xor
for cipher_idx_1 in range(NUM_CIPHER):
for position in range(KEY_SIZE):
for cipher_idx_2 in range(NUM_CIPHER-1):
if position in space_possible[cipher_idx_1][cipher_idx_2]:
if count&THRESHOLD_VALUE: # if possible position value appear more than THRESHOLD_VALUE times,
# we consider it as a space position
spa.append(position)
space_position[cipher_idx_1]=
return space_position
def calculate_key(cipher):
key=[0]*KEY_SIZE
space=find_space(cipher)
for cipher_idx_1 in range(NUM_CIPHER):
for position in range(len(space[cipher_idx_1])):
idx=space[cipher_idx_1][position]*2; # ciphertext is hex-encoded, so its scale times two
key[space[cipher_idx_1][position]]=ord((ciphertexts[cipher_idx_1][idx]+ciphertexts[cipher_idx_1][idx+1]).decode('hex'))^ord(' '); #derive key
key_str="";
for k in key:
key_str+=chr(k);
return key_str
result="";
key=calculate_key(ciphertexts)
for letter in strxor(ciphertexts[10].decode('hex'),key): # decrypt the target cipher
if (letter&='a' and letter&='z') or (letter&='A' and letter&='Z'):
elif letter==' ':
result+='0';
运行结果：
THRESHOLD_VALUE=9时，解密结果为 Th00s00ue00me00ag000E00hR0jterO00eG00 0qe0th00k0y0000eKRhann0n00，说明判定条件过于严格，受特殊情况影响较大。
THRESHOLD_VALUE=8时，解密结果为 Th00s0cue00me00agei000Wh000us0eg0R0str0amMc0pher000ev00 0se th00k0y 0oreKthannon00。
THRESHOLD_VALUE=7时，解密结果为 The0secuet mes0age is0 Wh000usingR0str0am cipher0 nev00 use th00k0y 0oreKthannonc0。
THRESHOLD_VALUE=6时，解密结果为 The secuet mes0age is0 Whtn usi0gwsstream cipher0 never use the key more than once。
THRESHOLD_VALUE=5时，解密结果为 Thm secuet message is0 Whtn usi0gwsstream cipher0 never use the key more than once。
可以看出当判定条件为6时，解密的结果已经有比较明确的含义，可以大致猜测正确的明文。不过也可以看出来这个思路的缺陷是当提取密钥信息时，是依次利用每个密文可能的空格位置进行提取，但判定的空格位置在不同的密文中可能有重合，这样利用后面密文的提取结果会覆盖前面密文的提取结果，如果后面密文在重合位置的判定结果不准确，则影响到该位置最终密钥的正确性，因此以上解密结果中有特定的几位信息是错误的。
没有更多推荐了，您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
Homology (Saunders Mac Lane)：（同源性）.pdf 437页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
Homology (Saunders Mac Lane)：（同源性）
你可能关注的文档：
··········
··········
C L A S S I C S
I N M A T H E M A T I C S
Saunders Mac Lane
Saunders Mac Lane was born on August 4,1909
in Connecticut. He studied at Yale University
and then at the University of Chicago and at
Gottingen, where he received the D. Phil. in 1934.
He has taught at Harvard, Cornell and the
University of Chicago.
Mac Lane's initial research was in logic and
in algebraic number theory (valuation theory).
With Samuel Eilenberg he published fifteen
papers on algebraic topology. A number of them
involved the initial steps in the cohomology
of groups and in other aspects of homological
algebra - as well as the discovery of category
theory. His famous undergraduate textbook
Survey of modern algebra, written jointly with
G. Birkhoff, has remained in print for over
50 years. Mac Lane is also the author of several
other highly successful books.
Classics in Mathematics
Saunders Mac Lane
Saunders Mac Lane
Reprint of the 1975 Edition
Saunders Mac Lane
Department of Mathematics, University of Chicago
Chicago, IL
Originally published as Vol. 114 of the
Grundlehren der mathematischen Wissenschaften
Mathematics Subject Classification (, 18AXX, 18CXX, 18GXX
ISBN 3-540-58662-8 Springer-Verlag Berlin Heidelberg New York
CIP data applied for
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
concerned, specifically the rights of translation, reprinting, reuse of illustration, recitation, broadcasting,
reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication
or parts thereof is permitted only under the provision of the German Copyright Law of September 9, 1%5.
in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are
liable for prosecution under the German Copyright La
正在加载中，请稍后...