Password Strengths Evaluation 1 (Entropy)

# 对输入的密码进行模式匹配，也就是结果中的match_sequence
matches = matching.omnimatch password
# 计算各种entropy
result = scoring.minimum_entropy_match_sequence password, matches

@dictionary_match #基于字典，也就是查看密码的子串是否出现在字典中，以及在字典中的位置
  passwords:    build_ranked_dict frequency_lists.passwords #常见的密码，概率降序
  english:      build_ranked_dict frequency_lists.english
  surnames:     build_ranked_dict frequency_lists.surnames
  male_names:   build_ranked_dict frequency_lists.male_names
  female_names: build_ranked_dict frequency_lists.female_names
@reverse_dictionary_match #翻转密码字符串
@l33t_match #l33t逆回去之后再进行dictionary_match
@spatial_match #qwerty这类键盘连续的字符串
@repeat_match #aaa这类连续的串
@sequence_match #abcd这类连续的串
@regex_match #匹配连续的符号、数字、大写、小写 （3个以上）
@date_match #匹配日期

  minimum_entropy_match_sequence: (password, matches) ->
    # 计算暴力破解的基数，也就是计算entropy公式中的(b**l)
    bruteforce_cardinality = @calc_bruteforce_cardinality password # e.g. 26 for lowercase
    # 保存到位置k的最小entropy，就是个动态规划嘛
    up_to_k = []      # minimum entropy up to k.
    # for the optimal seq of matches up to k, backpointers holds the final match (match.j == k).
    # null means the sequence ends w/ a brute-force character.
    backpointers = []
    for k in [0...password.length]
      # starting scenario to try and beat:
      # adding a brute-force character to the minimum entropy sequence at k-1.
      up_to_k[k] = (up_to_k[k-1] or 0) + @lg bruteforce_cardinality
      backpointers[k] = null
      for match in matches when match.j == k
        [i, j] = [match.i, match.j]
        # see if best entropy up to i-1 + entropy of this match is less than current minimum at j.
        # 在calc_entropy中，entropy的计算方法因“匹配类型”而异
        candidate_entropy = (up_to_k[i-1] or 0) + @calc_entropy(match)
        if candidate_entropy < up_to_k[j]
          up_to_k[j] = candidate_entropy
          backpointers[j] = match

    # walk backwards and decode the best sequence
    match_sequence = []
    k = password.length - 1
    while k >= 0
      match = backpointers[k]
      if match
        match_sequence.push match
        k = match.i - 1
      else
        k -= 1
    match_sequence.reverse()
    #match_sequence就是不重叠的匹配列表，但是中间可能有没有覆盖的字符串

    # fill in the blanks between pattern matches with bruteforce "matches"
    # that way the match sequence fully covers the password:
    # match1.j == match2.i - 1 for every adjacent match1, match2.
    make_bruteforce_match = (i, j) =>
      pattern: 'bruteforce'
      i: i
      j: j
      token: password[i..j]
      entropy: @lg Math.pow(bruteforce_cardinality, j - i + 1)
      cardinality: bruteforce_cardinality
    # 使用bruteforce计算其中没有覆盖到的字符的entropy
    k = 0
    match_sequence_copy = []
    for match in match_sequence
      [i, j] = [match.i, match.j]
      if i - k > 0
        match_sequence_copy.push make_bruteforce_match(k, i - 1)
      k = j + 1
      match_sequence_copy.push match
    if k < password.length
      match_sequence_copy.push make_bruteforce_match(k, password.length - 1)
    match_sequence = match_sequence_copy

    min_entropy = up_to_k[password.length - 1] or 0  # or 0 corner case is for an empty password ''
    crack_time = @entropy_to_crack_time min_entropy

    # final result object
    password: password
    entropy: @round_to_x_digits(min_entropy, 3)
    match_sequence: match_sequence
    crack_time: @round_to_x_digits(crack_time, 3)
    crack_time_display: @display_time crack_time
    score: @crack_time_to_score crack_time

  calc_entropy: (match) ->
    return match.entropy if match.entropy? # a match's entropy doesn't change. cache it.
    entropy_functions =
      dictionary: @dictionary_entropy
      spatial:    @spatial_entropy
      repeat:     @repeat_entropy
      sequence:   @sequence_entropy
      regex:      @regex_entropy
      date:       @date_entropy
    match.entropy = entropy_functions[match.pattern].call this, match
    
  dictionary_entropy: (match) ->
    ## 依赖于字典中字段的排位
    match.base_entropy = @lg match.rank # keep these as properties for display purposes
    match.uppercase_entropy = @extra_uppercase_entropy match
    match.reversed_entropy = match.reversed and 1 or 0
    match.l33t_entropy = @extra_l33t_entropy(match)
    match.base_entropy + match.uppercase_entropy + match.l33t_entropy + match.reversed_entropy

  START_UPPER: /^[A-Z][^A-Z]+$/
  END_UPPER: /^[^A-Z]+[A-Z]$/
  ALL_UPPER: /^[^a-z]+$/
  ALL_LOWER: /^[^A-Z]+$/

  extra_uppercase_entropy: (match) ->
    word = match.token
    return 0 if word.match @ALL_LOWER
    # a capitalized word is the most common capitalization scheme,
    # so it only doubles the search space (uncapitalized + capitalized): 1 extra bit of entropy.
    # allcaps and end-capitalized are common enough too, underestimate as 1 extra bit to be safe.
    for regex in [@START_UPPER, @END_UPPER, @ALL_UPPER]
      return 1 if word.match regex
    # otherwise calculate the number of ways to capitalize U+L uppercase+lowercase letters
    # with U uppercase letters or less. or, if there's more uppercase than lower (for eg. PASSwORD),
    # the number of ways to lowercase U+L letters with L lowercase letters or less.
    U = (chr for chr in word.split('') when chr.match /[A-Z]/).length
    L = (chr for chr in word.split('') when chr.match /[a-z]/).length
    possibilities = 0
    possibilities += @nCk(U + L, i) for i in [1..Math.min(U, L)]
    @lg possibilities

  extra_l33t_entropy: (match) ->
    return 0 if not match.l33t
    extra_entropy = 0
    for subbed, unsubbed of match.sub
      # lower-case match.token before calculating: capitalization shouldn't affect l33t calc.
      chrs = match.token.toLowerCase().split('')
      S = (chr for chr in chrs when chr == subbed).length   # num of subbed chars
      U = (chr for chr in chrs when chr == unsubbed).length # num of unsubbed chars
      if S == 0 or U == 0
        # for this sub, password is either fully subbed (444) or fully unsubbed (aaa)
        # treat that as doubling the space (attacker needs to try fully subbed chars in addition to
        # unsubbed.)
        extra_entropy += 1
      else
        # this case is similar to capitalization:
        # with aa44a, U = 3, S = 2, attacker needs to try unsubbed + one sub + two subs
        p = Math.min(U, S)
        possibilities = 0
        possibilities += @nCk(U + S, i) for i in [1..p]
        extra_entropy += @lg possibilities
    extra_entropy