题目79：通过分析用户的登陆日志，你能否找到用户的数字密码？
本帖最后由 欧拉计划 于 2015-11-5 17:25 编辑Passcode derivation
A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
The text file, keylog.txt, contains fifty successful login attempts.
Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.
题目：
网上银行通用的一种加密方法是向用户询问密码中的三位随机字符。例如，如果密码是 531278，那么银行可以询问第 2,3,5 位字符，预期的回复应该是317。
文本文件包含 50 次成功的登录尝试。
已知三位字符总是按顺序询问，分析文件并找出可能的最短的密码（长度未知）。 一种可能的最短密码组合之一：
73162890
满足以上50次成功登录尝试。 穷举，然后排除
import itertools
logins = [319, 680, 180, 690, 129, 620, 762, 689, 762, 318, 368, 710, 720, 710, 629, 168, 160, 689, 716, 731, 736, 729,
316, 729, 729, 710, 769, 290, 719, 680, 318, 389, 162, 289, 162, 718, 729, 319, 790, 680, 890, 362, 319, 760,
316, 729, 380, 319, 728, 716]
for len_code in range(4, 100):
for code in itertools.permutations(list(range(10)), len_code):
login_counter = 0
for login in logins:
digits = (login // 100, (login % 100) // 10, login % 10)
if digits not in code:
break
pos_0 = code.index(digits)
curr_code = code
if digits not in curr_code:
break
pos_1 = curr_code.index(digits)
curr_code = curr_code
if digits not in curr_code:
break
login_counter += 1
# if all logins fit the code, it is a solution
if login_counter == len(logins):
print code
exit()
既然是排列组合和匹配问题，其实可以用itertools和re模块来解决。
logins = [319, 680, 180, 690, 129, 620, 762, 689, 762, 318, 368, 710, 720, 710, 629, 168, 160, 689, 716, 731, 736, 729,
316, 729, 729, 710, 769, 290, 719, 680, 318, 389, 162, 289, 162, 718, 729, 319, 790, 680, 890, 362, 319, 760,
316, 729, 380, 319, 728, 716]
import re
import itertools as it
def findlog(n):
s = list(str(n))
return '.*'+'.*?'.join(s)+'.*'
for i in it.permutations(['1','2','3','6','7','8','9','0'],8):
flag = 1
for j in logins:
if not re.match(findlog(j),''.join(i)):
flag = 0
break
if flag:
print ''.join(i)
break
秒出答案{:5_108:} 用的matlab
结果是
7 3 1 6 2 8 9 0
7 3 1 6 2 8 9 0
时间已过 0.004162 秒。
>>
页:
[1]