随机排列密码字符串以限制同一类的连续字符

Question

因此，在 IT 领域工作，我们几乎总是需要生成安全密码，某些组织除了所需的字符类数量和长度要求之外还添加了更严格的要求。我工作的一个这样的组织也限制了可以连续出现的单个字符类（小写、大写、特殊字符、数字）的字符数。我已经构建了一个确实有助于此目的的函数，但是，它本质上只是暴力破解密码，这是非常糟糕的。从计算机科学的角度来看，知道速度至关重要，同时保持随机性，您将如何解决这个特定问题。

\n

我觉得应该有某种我可以实现的洗牌技术，但是我提出的每个解决方案要么太慢，要么降低了字符串的随机性。

\n

Function New-Password {\n        PARAM(\n            [Int]$PasswordLength            = 64,\n            [Int]$MinUpperCase              = 5,\n            [Int]$MinLowerCase              = 5,\n            [Int]$MinSpecialCharacters      = 5,\n            [Int]$MinNumbers                = 5,\n            [Int]$ConsecutiveCharClass      = 0,\n            [Int]$ConsecutiveCharCheckCount = 1000,\n            [String]$LowerCase              = 'abcdefghiklmnoprstuvwxyz',\n            [String]$UpperCase              = 'ABCDEFGHKLMNOPRSTUVWXYZ',\n            [String]$Numbers                = '1234567890',\n            [String]$SpecialCharacters      = '!"$%&/()=?}][{@#*+',\n            [String]$PasswordProfile        = '',\n        \n            #Advanced Options\n            [Bool]$EnhancedEntrophy = $True\n        )\n        \n        If ([String]::IsNullOrEmpty($PasswordProfile) -eq $False) {\n            #You can define custom password profiles here for easy reference later on.\n            New-Variable -Force -Name:'PasswordProfiles' -Value:@{\n                'iDrac' = [PSCustomObject]@{PasswordLength=20;SpecialCharacters="+&?>-}|.!(',_[`"@#)*;$]/\xc2\xa7%=<:{@";}\n            }\n        \n            If ($PasswordProfile -in $PasswordProfiles.Keys) {\n                $PasswordProfiles[$PasswordProfile] |Get-Member -MemberType NoteProperty |ForEach-Object {\n                    Set-Variable -Name $_.name -Value $PasswordProfiles[$PasswordProfile].($_.name)\n                }\n            }\n        }\n        \n        New-Variable -Force -Name:'PassBldr' -Value @{}\n        New-Variable -Force -Name:'CharacterClass' -Value:([String]::Empty)\n        ForEach ($CharacterClass in @("UpperCase","LowerCase","SpecialCharacters","Numbers")) {\n            $Characters = (Get-Variable -Name:$CharacterClass -ValueOnly)\n            If ($Characters.Length -gt 0) {\n                $PassBldr[$CharacterClass] = [PSCustomObject]@{\n                    Min        = (Get-Variable -Name:"min$CharacterClass" -ValueOnly);\n                    Characters = $Characters\n                    Length     = $Characters.length\n                }\n            }\n        }\n        \n        #Sanity Check(s)\n        $MinimumChars = $MinUpperCase + $MinLowerCase + $MinSpecialCharacters + $MinNumbers\n        If ($MinimumChars -gt $PasswordLength) {\n            Write-Error -Message:"Specified number of minimum characters ($MinimumChars) is greater than password length ($PasswordLength)."\n            Return\n        }\n        \n        #New-Variable -Force -Name:'Random' -Value:(New-Object -TypeName:'System.Random')\n        New-Variable -Force -Name:'Randomizer' -Value:$Null\n        New-Variable -Force -Name:'Random' -Value:([ScriptBlock]::Create({\n            Param([Int]$Max=[Int32]::MaxValue,[Int32]$Min=1)\n            if ($Min -gt $Max) {\n                Write-Warning  "[$($myinvocation.ScriptLineNumber)] Min ($Min) must be less than Max ($Max)."\n                return -1\n            }\n        \n            if ($EnhancedEntrophy) {\n                if ($Randomizer -eq $Null) {\n                    Set-Variable -Name:'Randomizer' -Value:(New-Object -TypeName:'System.Security.Cryptography.RNGCryptoServiceProvider') -Scope:1\n                }\n                #initialize everything\n                $Difference=$Max-$Min\n                [Byte[]] $bytes = 1..4  #4 byte array for int32/uint32\n        \n                #generate the number\n                $Randomizer.getbytes($bytes)\n                $Number = [System.BitConverter]::ToUInt32(($bytes),0)\n                return ([Int32]($Number % $Difference + $Min))\n        \n            } Else {\n                if ($Randomizer -eq $Null) {\n                    Set-Variable -Name:'Randomizer' -Value:(New-Object -TypeName:'System.Random') -Scope:1\n                }\n                return ([Int]$Randomizer.Next($Min,$Max))\n            }\n        }))\n        \n        $GetString = [ScriptBlock]::Create({\n            Param([Int]$Length,[String]$Characters)\n            Return ([String]$Characters[(1..$Length |ForEach-Object {& $Random $Characters.length})] -replace " ","")\n        })\n        \n        $CreatePassword = [scriptblock]::Create({\n            New-Variable -Name Password -Value ([System.Text.StringBuilder]::new()) -Force\n        \n            #Meet the minimum requirements for each character class\n            ForEach ($CharacterClass in $PassBldr.Values) {\n                If ($CharacterClass.Min -gt 0) {\n                    $Null = $Password.Append([string](Invoke-Command $GetString -ArgumentList $CharacterClass.Min,$CharacterClass.Characters))\n                }\n            }\n        \n            #Now meet the minimum length requirements.\n            If ([Int]($PasswordLength-$Password.length) -gt 0) {\n                $Null = $Password.Append((Invoke-Command $GetString -ArgumentList ($PasswordLength-$Password.length),($PassBldr.Values.Characters -join "")))\n            }\n        \n            return (([Char[]]$Password.ToString() | Get-Random -Count $Password.Length) -join "")\n        })\n        \n        Switch ([Int]$ConsecutiveCharClass) {\n            '0' { New-Variable -Name NewPassword -Value (& $CreatePassword) -Force }\n            {$_ -gt 0} {\n                New-Variable -Name CheckPass    -Value $False -Force\n                New-Variable -Name CheckCount   -Value ([Int]0) -Force\n                For ($I=0; $I -le $ConsecutiveCharCheckCount -and $CheckPass -eq $False; $I++) {\n                    New-Variable -Name NewPassword -Value (& $CreatePassword) -Force\n                    $TestPassed = 0\n                    ForEach ($CharClass in $PassBldr.Values) {                   \n                        IF ([Regex]::IsMatch([Regex]::Escape($NewPassword),"[$([Regex]::Escape($CharClass.Characters))]{$ConsecutiveCharClass}") -eq $False) {\n                            $TestPassed++\n                        }\n                    }\n                    if ($TestPassed -eq $CheckClasses.Count) {\n                        $CheckPass = $True\n                    }\n                }\n            }\n            Default {Write-Warning -Message "This shouldn't be possible, how did you get here?!"}\n        }\n        \n        Return $NewPassword\n    }\n

\n

Answer 1

从计算机科学的角度来看，知道速度至关重要，同时保持随机性，您将如何解决这个特定问题。

在进一步讨论之前，我应该注意到这些属性（遵守所描述的策略与保持随机性/熵）是相互排斥的 - 你不能通过仔细“纠正”PRNG 输出的分布来“保持随机性”。

我会将问题分成两个单独的函数：

• Test-PasswordCharSequence- 快速验证给定的密码字符串是否符合策略
• Shuffle-PasswordCharSequence- 随机打乱任何给定密码中的字符一次

原子化这些核心操作应该更容易调整/重构。

对于验证函数，使用正则表达式可能很诱人 - 但我建议简单地迭代字符串并跟踪同一类的连续字符。

function Test-PasswordCharSequence {
    param(
        [string]
        $String,

        [System.Collections.IDictionary]
        $CharacterMap,

        [int]$Limit = 5
    )

    # Keep tracking the last seen character class and length of consecutive sequence
    $currentClass = ""
    $counter = 0

    foreach($char in $String.ToCharArray())
    {
        if($CharacterMap.ContainsKey($char) -and $CharacterMap[$char] -eq $currentClass)
        {
            $counter++
        }
        else
        {
            $counter = 1
            $currentClass = $CharacterMap[$char]
        }

        # if we've seen the same class for too many consecutive characters, fail
        if($counter -gt $Limit){
            return $false
        }
    }

    # No sequence over limit observed
    return $true
}

然后我们需要一个函数来打乱密码。据我所知，最有效的真正随机（同样取决于所使用的 RNG）洗牌算法是就地 Fisher-Yates 洗牌算法，其可以按如下方式实现：

function Shuffle-PasswordCharSequence
{
    param(
        [Parameter(Mandatory)]
        [string]$String
    )

    $chars = $String.ToCharArray()

    $max = $chars.Length

    #Fisher-Yates Left to Right
    for($i = 0; $i -lt $max - 1; $i++)
    {
        $j = Get-Random -Minimum 0 -Maximum ($max - $i)
        $chars[$j],$chars[$i+$j] = $chars[$i+$j],$chars[$j]
    }

    return [string]::new($chars)
}

要将它们与您现有的功能结合使用New-Password：

# define character classes to use
$CharacterClasses = @{
    LowerCase = 'abcdefghiklmnoprstuvwxyz'
    UpperCase = 'ABCDEFGHKLMNOPRSTUVWXYZ'
    Numbers = '1234567890'
    SpecialCharacters = '!"$%&/()=?}][{@#*+'
}

# generate inverse character map for the validation function
# we use [Dictionary[char,string]] rather than [hashtable] to ensure case-sensitive handling of keys ('b' vs 'B')
$classMap = [System.Collections.Generic.Dictionary[char,string]]::new()

foreach($entry in $CharacterClasses.GetEnumerator())
{
    foreach($char in $entry.Value.ToCharArray())
    {
        $classMap[$char] = $entry.Name
    }
}

# generate initial password
$passwordCandidate = New-Password -PasswordLength 127 @CharacterClasses

# validate generated password, shuffle until successful
$shuffleCount = 0
while(!(Test-PasswordCharSequence $passwordCandidate -CharacterMap $classMap)){
  $passwordCandidate = Shuffle-PasswordCharSequence $passwordCandidate
  $shuffleCount++
}

Write-Host "Generated valid password after ${shuffleCount} shuffles"