Мощь пароля ближайшей кнопки клавиатуры

Question

Как найти энтропию паролей из строки, наложенной на нажатия ближайших кнопок на клавиатуре?

Я хотел бы определить с ведьмами алгоритм кодирования в строках, как:

querty 

или

asdfghjk 

проверяются как плохие пароли.

Есть способ рассчитать это без словарей?

Answer 1

Я нашел решение самостоятельно.

На самом деле я проверяю только «qwerty» клавиатуру.

Функция getMaxPathLength дает максимальный путь соседних ключей, поиск во всех направлениях.

<?php 
/* 
* Find the max path in a qwerty keyboard giving an input string 
    Copyright (C) 2013 Danilo Rossini <rossinidan@gmail.com> 

    This program is free software: you can redistribute it and/or modify 
    it under the terms of the GNU General Public License as published by 
    the Free Software Foundation, either version 3 of the License, or 
    (at your option) any later version. 

    This program is distributed in the hope that it will be useful, 
    but WITHOUT ANY WARRANTY; without even the implied warranty of 
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 
    GNU General Public License for more details. 

    You should have received a copy of the GNU General Public License 
    along with this program. If not, see <http://www.gnu.org/licenses/>. 


    USAGE: 

    // Examples 
    $array = array("qwertyui"); //get 8 as result 
    $array = array("quedc");  //get 5 as result 
    $array = array("qaz");  //get 3 as result 
    $array = array("zxcdfvppp"); //get 6 as result 

    $fp = new Path_length("qwertyu"); 
    echo $fp->getMaxPathLength(); 
*/ 
class Path_length{ 

    private $maxPathLength = 1; 

    /* 
    * Keyboard layout: QUERTY 
    */ 
    private $matrix = array( 
     array("1","2","3","4","5","6","7","8","9","0"), 
     array("q","w","e","r","t","y","u","i","o","p"), 
     array("a","s","d","f","g","h","j","k","l"), 
     array("z","x","c","v","b","n","m"), 
    ); 

    private $colSize = 10; 
    private $rowSize = 4; 

    private $arrayInput = array(); 
    private $arraySize = null; 



    public function __construct($inputString) { 

     if(!isset($inputString)) die("NULL input array!"); 

     $this->splitStringInArray($inputString); 
     $this->cycleMatrix(); 
    } 


    public function getMaxPathLength(){ 
     return $this->maxPathLength; 
    } 

    /** 
     * Split each element of the string into an array and store it, with his length 
     * in global variables 
     * @param type $string 
     */ 
    private function splitStringInArray($string){ 

     $length = strlen($string); 
     $tmpArray = array(); 

     for ($i=0; $i<$length; $i++) { 
      $tmpArray[$i] = $string[$i]; 
     } 

     $this->arraySize = $length; 
     $this->arrayInput = $tmpArray; 
    } 

    /** 
     * Iterate each element of the matrix, calling the function $this->findPath 
     */ 
    private function cycleMatrix(){ 

     for($i=0;$i<$this->colSize;$i++){ 
      for($j=0;$j<$this->rowSize;$j++){ 

       if(isset($this->matrix[$j][$i]) && $this->arrayInput[0]==$this->matrix[$j][$i]){ 
        $this->findPath($j, $i, $this->maxPathLength, 1); 
       } 

      } 
     } 

    } 

    /** 
     * Recursive function that search if the closest element in the matrix (up, down, left, right) 
     * is contained in the input array at the cursor pointer. 
     * It save into $this->maxPathLength the maximum length path found. 
     * 
     * @param int $a -> x position on the matrix 
     * @param int $b -> y position on the matrix 
     * @param int $max -> max path lenght found until now by the recursive call 
     * @param int $c -> array cursor on the input array 
     * @return int 
     */ 
    private function findPath($a, $b, $max, $c){ 

     $this->maxPathLength = max(array($this->maxPathLength, $max)); 

     if($a>=($this->rowSize-1) && $b>=($this->colSize-1)) { 
      return 1; 
     } 

     if($c===$this->arraySize) { 
      return 1; 
     } 

     /* Search next right key */ 
     if(isset($this->matrix[$a+1][$b]) && 
      $this->matrix[$a+1][$b]===$this->arrayInput[$c] && 
      $this->findPath($a+1, $b, $max+1, $c+1)){ 
      return 1; 
     } 

     /* Search next bottom key */ 
     if(isset($this->matrix[$a][$b+1]) && 
      $this->matrix[$a][$b+1]===$this->arrayInput[$c] && 
      $this->findPath($a, $b+1, $max+1, $c+1)){ 
      return 1; 
     } 

     /* Search next left key */ 
     if(isset($this->matrix[$a-1][$b]) && 
      $this->matrix[$a-1][$b]===$this->arrayInput[$c] && 
      $this->findPath($a-1, $b, $max+1, $c+1)){ 
      return 1; 
     } 

     /* Search next up key */ 
     if(isset($this->matrix[$a][$b-1]) && 
      $this->matrix[$a][$b-1]===$this->arrayInput[$c] && 
      $this->findPath($a, $b-1, $max+1, $c+1)){ 
      return 1; 
     } 

     return 0; 
    } 
} 

Редактировать

Новая версия предыдущего кода с обнаружением сдвинутых ключей.

<?php 
/* 
* Find the max path in a qwerty keyboard giving an input string 
    Copyright (C) 2013 Danilo Rossini <rossinidan@gmail.com> 

    This program is free software: you can redistribute it and/or modify 
    it under the terms of the GNU General Public License as published by 
    the Free Software Foundation, either version 3 of the License, or 
    (at your option) any later version. 

    This program is distributed in the hope that it will be useful, 
    but WITHOUT ANY WARRANTY; without even the implied warranty of 
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 
    GNU General Public License for more details. 

    You should have received a copy of the GNU General Public License 
    along with this program. If not, see <http://www.gnu.org/licenses/>. 


    USAGE: 

    // Examples 
    $string = "qwertyui"; //get 8 as result 
    $string = "qwedc";  //get 5 as result 

    $fp = new Path_length("qwertyu"); 
    echo $fp->getMaxPathLength(); 
*/ 

class Path_length{ 

    private $maxPathLength = 1; 

    /* 
    * Keyboard layout: QUERTY 
    */ 
    private $keyLower = array(
     array("1","2","3","4","5","6","7","8","9","0"), 
     array("q","w","e","r","t","y","u","i","o","p"), 
     array("a","s","d","f","g","h","j","k","l"), 
     array("z","x","c","v","b","n","m"), 
    ); 

    private $keyUpper = array(
     array("1","2","3","4","5","6","7","8","9","0"), 
     array("Q","W","E","R","T","Y","U","I","O","P"), 
     array("A","S","D","F","G","H","J","K","L"), 
     array("Z","X","C","V","B","N","M"), 
    ); 

    private $matrix = array(); 

    private $colSize = 10; 
    private $rowSize = 4; 

    private $arrayInput = array(); 
    private $arraySize = null; 



    public function __construct($inputString) { 

     if(!isset($inputString) || !is_string($inputString)) die("Invalid input string!"); 

     $this->initKeyboard(); 
     $this->splitStringInArray($inputString); 
     $this->cycleMatrix(); 
    } 

    private function initKeyboard(){ 
     $this->matrix[0] = $this->keyLower; 
     $this->matrix[1] = $this->keyUpper; 
    } 

    public function getMaxPathLength(){ 
     return $this->maxPathLength; 
    } 

    /** 
     * Split each element of the string into an array and store it, with his length 
     * in global variables 
     * @param type $string 
     */ 
    private function splitStringInArray($string){ 

     $length = strlen($string); 
     $tmpArray = array(); 

     for ($i=0; $i<$length; $i++) { 
      $tmpArray[$i] = $string[$i]; 
     } 

     $this->arraySize = $length; 
     $this->arrayInput = $tmpArray; 
    } 

    private function isUpper($chr){ 
     return ctype_upper($chr) ? 1 : 0; 
    } 

    /** 
     * Iterate each element of the matrix, calling the function $this->findPath 
     */ 
    private function cycleMatrix(){ 


     for($i=0;$i<$this->colSize;$i++){ 
      for($j=0;$j<$this->rowSize;$j++){ 


       for($c=0; $c<$this->arraySize; $c++) { 
        $isUp = $this->isUpper($this->arrayInput[$c]); 

        if(isset($this->matrix[$isUp][$j][$i]) && 
         $this->arrayInput[$c]===$this->matrix[$isUp][$j][$i]){ 
          $this->findPath($j, $i, 1, $c+1, $isUp); 
        } 
       } 

      } 
     } 

    } 

    /** 
     * Recursive function that search if the closest element in the matrix (up, down, left, right) 
     * is contained in the input array at the cursor pointer. 
     * It save into $this->maxPathLength the maximum length path found. 
     * 
     * @param int $a -> x position on the matrix 
     * @param int $b -> y position on the matrix 
     * @param int $max -> max path lenght found until now by the recursive call 
     * @param int $c -> array cursor on the input array 
     * @return int 
     */ 
    private function findPath($a, $b, $max, $c, $isUp){ 

     $this->maxPathLength = max(array($this->maxPathLength, $max)); 

     if($a>=($this->rowSize-1) && $b>=($this->colSize-1)) { 
      return 1; 
     } 

     if($c===$this->arraySize) { 
      return 1; 
     } 

     /* Search next right key */ 
     if(isset($this->matrix[$isUp][$a+1][$b]) && 
      $this->matrix[$isUp][$a+1][$b]===$this->arrayInput[$c] && 
      $this->findPath($a+1, $b, $max+1, $c+1, $isUp)){ 
      return 1; 
     } 

     /* Search next bottom key */ 
     if(isset($this->matrix[$isUp][$a][$b+1]) && 
      $this->matrix[$isUp][$a][$b+1]===$this->arrayInput[$c] && 
      $this->findPath($a, $b+1, $max+1, $c+1, $isUp)){ 
      return 1; 
     } 

     /* Search next left key */ 
     if(isset($this->matrix[$isUp][$a-1][$b]) && 
      $this->matrix[$isUp][$a-1][$b]===$this->arrayInput[$c] && 
      $this->findPath($a-1, $b, $max+1, $c+1, $isUp)){ 
      return 1; 
     } 

     /* Search next up key */ 
     if(isset($this->matrix[$isUp][$a][$b-1]) && 
      $this->matrix[$isUp][$a][$b-1]===$this->arrayInput[$c] && 
      $this->findPath($a, $b-1, $max+1, $c+1, $isUp)){ 
      return 1; 
     } 

     return 0; 
    } 
}