Алгоритм генерации мнемонических паролей для клавиатур QWERTY

Question

У меня есть " мнемоническая " функция генерации пароля , которая работает примерно так:

function Mnemonic($mnemonic)
{
    $result = null;
    $charset = array(str_split('aeiou', 1), str_split('bcdfghjklmnpqrstvwxyz', 1));

    for ($i = 1; $i <= $mnemonic; $i++)
    {
        $result .= $charset[$i % 2][array_rand($charset[$i % 2])];
    }

    return $result;
}

В основном это генерирует строку длиной $mnemonic, где каждый нечетный символ является согласной, а каждый четный символ - гласной. Хотя я понимаю, что это уменьшает сложность пароля, обычно легче запомнить . Теперь я хочу улучшить его, генерируя строки, которые легко набрать .

Например, хотя я * nix новичок, я всегда предпочитаю дистрибутивы на основе RHEL, а не дистрибутивы Debian, главная причина заключается в простоте ввода yum вместо простоты ввода apt[-get], просто попробуйте это сами.

Как мне реализовать логику для генерации строк, которые легко набирать на клавиатурах QWERTY?

Answer 1

Carpalx имеет много исследований по вычислению усилия при наборе текста , который включает в себя:

• расстояние перемещения пальца
• штрафы за руки, пальцы и ряды
• Ход хода

Результатом их исследования является раскладка клавиатуры Colemak , которая утверждает, что она лучше, чем у Дворжака .

Тем не менее, он написан в обратном направлении от того, что вы хотите - их цель - найти лучшую раскладку клавиатуры на основе ввода, но вы пытаетесь найти легкий ввод на основе раскладки клавиатуры.

Так что - даже если вы не сможете использовать его напрямую, я подумал, что вы найдете его интересным (и кто знает, если ваш Perl-fu силен, вы можете извлечь и повернуть алгоритм, так как он 1026 * под лицензией GPL *).

Answer 2

Вы можете удалить все символы, которые набираются с помощью кольца и мизинца (q, w, x, z, p), затем выплевывать символы, набранные левой и правой руками, и чередовать эти буквы.

Answer 3

Я разбил следующее. Это хакерская работа, но, кажется, она работает довольно хорошо.

<?
function Mnemonic($mnemonic)
{
    $result = null;
    $charset = array(str_split('@a3e!1i0ou', 1), str_split('#$*bcdfghjklmnpqrstvwxyz', 1));

    $lastchar = ' ';
    for ($i = 1; $i <= $mnemonic; $i++)
    {
      do {
        $char = $charset[$i % 2][array_rand($charset[$i % 2])];
      } while (!nextkey($lastchar, $char));
      $result .= $char;
    }

    return $result;
}

function nextkey($lastchar, $requestchar)
{
  $map = array();
  $map[] = '!qaz'; // ll
  $map[] = @#wsx1'; // lr
  $map[] = 'ed23'; // lm
  $map[] = '$%^rtfgcvb456'; // li
  $map[] = '&yhnujm7'; // ri
  $map[] = '*()ik89'; // rm
  $map[] = 'olp,.'; // rr
  $map[] = ';[]'; // rl
  $map[] = '!@#$%^&*()[]'; // special chars, don't follow
  $map[] = 'pbvcnmq'; // consonant clusters, don't follwo

  if($lastchar == $requestchar) return true;
  foreach($map as $string)
    if(strpos($string, $requestchar) && strpos($string, $lastchar)) return false;
  return true;
}

printf("%s\n", Mnemonic(8));
?>

Answer 4

Вы можете взглянуть на принципы, используемые в клавиатуре Dvorak ,

Те принципы, которые применяются в алгоритме генерации пароля:

• Буквы должны быть набраны изменением руки.
• Используйте легко набираемые комбинации. Взгляните на макет Дворжака и посмотрите на общие орграфы и положения их букв.
• Использовать только одну букву из нижнего ряда или нет. Сделай это случайным!
• Вы можете сделать соотношение 2 к 1 (2 буквы, набранные правой рукой, к 1 букве, набранной левой рукой).
• Поскольку отношение равно 2 к 1, вам нужно набрать 2 последовательных буквы одной и той же рукой, поэтому вам нужно будет убедиться, что они напечатаны снаружи клавиатуры и внутри. Этот принцип применяется к орграфам.

Я знаю, что вы сказали, что это клавиатура QWERTY, но использование этих принципов на клавиатуре QWERTY может дать вам очень хорошие результаты, например:

ktrd, ogkdo («пишущая машинка» в двораке)

kjg; g; akd; k (используя только домашний ряд)

pjedoildupsk (просто случайный пароль, следуя принципам)

Все ненавистники Дворжака, замолчи!

Надеюсь, это поможет.

Answer 5

Отличный вопрос - принимая приведенные выше предложения, вот формулы для расстояния от ключа i до ключа j:

Вес = расстояние * a + переключатель * b + тот же * c + shift * d + странный * e + start * f

Расстояние - это значение, остальные значения равны 0/1.

Расстояние - наложив точную сетку на QWERTY-клавиатуру, найдите x, y и рассчитать расстояние. Расстояние имеет положительный вес. Если комбинация букв используется разными руками (например, aj, sk, wu ...), расстояние равно нулю.

Switch - отрицательный вес; переключение хорошо

То же самое - aq, qa, az, za используют один и тот же палец. Это же положительно

Сдвиг - все, что смещается, положительно и очень плохо

Странно - я не знаю $ или ~ плохо, потому что вы должны смотреть на клавиатуру.

Начало - asdfjkl, начиная или заканчивая. Вероятно, отрицательно и хорошо, так как ваши пальцы находятся в состоянии покоя.

Коэффициенты - просто начните до тех пор, пока относительные значения кажутся разумными. Если вы ДЕЙСТВИТЕЛЬНО хотите придумать - попросите кого-нибудь набрать несколько десятков наборов цифр, используйте секундомер и установите регрессионную модель.

Реализация - скажем, у нас есть пароль из шести символов.

Теперь мне нужно самое низкое значение для шести символов, начиная с каждой буквы. Представьте себе массив ваших N ключей в столбцах. Теперь представьте шесть столбцов. Ваш самый короткий пароль - это самый короткий путь через шесть столбцов (с допустимыми циклами). Возможно, вам придется добавить некоторую логику для устранения циклов, но это должно быть хорошим первым проходом. (Мне здесь лень - вероятно, есть теоретическая формулировка графа, которая решает эту проблему.)

Бьюсь об заклад, кто-то делал это раньше - особенно часть нажатия клавиш.

Answer 6

Возможно, вы можете использовать эвристику, чтобы измерить «простоту ввода».

Например, рассмотрите стоимость перемещения пальца при переходе к следующему персонажу. Это может зависеть от того, как далеко должен двигаться палец, в каком направлении и т. Д.

Вы также можете добавить дополнительные расходы, когда требуется переключить пальцы или руки.

Немного поиграв с расходами, вы, вероятно, найдете удовлетворительное решение.

Надеюсь, это поможет.

Answer 7

Если вы реализуете это, пожалуйста, примите во внимание локаль пользователя при определении «стоимости» перехода от одного персонажа к другому. Простой в вводе пароль может стать довольно громоздким, если пользователь использует другую раскладку клавиатуры. Некоторые клавиши, которые могут быть легко доступны на клавиатуре одного языка, могут быть недоступны на клавиатуре другого языка, не требуя дополнительных клавиш-модификаторов (shift, meta и т. Д.).

Чтобы сделать эту идею универсальной, я бы рекомендовал игнорировать, какой символ принадлежит какому ключу, и вместо этого рассматривать ключи как массив со строками и столбцами. Каждая строка обычно смещена относительно предыдущей примерно на 1/3 ширины ключа. Имея это в виду, не должно быть сложно рассчитать расстояние между любыми двумя произвольными ключами:

# Key at top left corner is {0, 0}
key1 @ {x1, y1}
key2 @ {x2, y2}

xdistance = absolute_value(x2 - x1)
ydistance = absolute_value(y2 - y1)

if y1 > y2
  xdistance += (1/3 * ydistance)
else
  xdistance -= (1/3 * ydistance)

total_distance = square_root(xdistance^2 + ydistance^2)

Создайте серию ключевых позиций, соответствующих вашей длине и требованиям "простоты ввода", а затем используйте текущую раскладку клавиш пользователя, чтобы переназначить эти индексы в символы.

Answer 8

Создайте структуру данных, которая представляет клавиатуру и кодирует строку, столбец, руку и палец, используемые для ввода каждого символа. Напишите функцию, которая при представлении с символом предоставляет список символов «легко вводить следующий» на основе гибких правил, которые вы разрабатываете. Он может полагаться на другую функцию, которая вычисляет расстояние между клавишами.

Лично я не нахожу, чтобы печатать буквы одной и той же рукой дважды медленно: только если предыдущее письмо использовало слишком близко расположенный палец, это трудно. Например, XQ сложно печатать, потому что моя рука должна двигаться вверх, чтобы обрабатывать смежные пальцы, необходимые для их ввода. Но я совсем не нахожу BQ трудно печатать, потому что, пока мой указательный палец все еще работает на B, мой мизинец может идти к Q.

Также гораздо легче набрать AW, чем QS, потому что безымянный палец длиннее и поэтому естественно помещается на W, когда мизинец находится на A, в положении покоя, в то время как QS требует растягивания мизинца и одновременный, противоречивый мышечный хруст безымянного пальца.

Если вы начнете составлять карту каждой буквы друг против друга, вы скоро найдете разумный способ изобразить различные аспекты легкости или сложности. Обобщая мой пример XQ / BQ, вы могли бы внести изменения в одну строку, требующие расстояния в 2 или более пальцев, изменения в 2 рядах - в 3 пальца, а для изменения в 3 ряда (возможно, числа) - альтернативные руки.

Я также заметил, что немного большее расстояние между WD и IL, чем у SE и KO, также меняет сложность из-за слегка зазубренного расположения клавиш.

С некоторым анализом (я рекомендую использовать Excel, чтобы «отобразить» трудности при наборе текста), я уверен, что вы можете придумать алгоритм, который поможет вам создавать простые для ввода слова.

Если возможно, попробуйте ввести хотя бы одно число и подумайте и об использовании пробелов.