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 很强大，你也许能够提取并反转算法，因为它是 GPL ）。

Answer 2

您可以消除用无名指和小指（q、w、x、z、p）键入的所有字符，然后吐出用左手和右手键入的字符并在这些字母之间交替。

Answer 3

您可能想看看德沃夏克键盘中使用的原理，

这些原理已应用密码生成算法中的内容是：

• 字母应该通过换手来输入。
• 使用易于输入的组合。看一下德沃夏克布局，看看常见的二合字母及其字母的位置。
• 仅使用底行中的一个字母，或不使用。让它随机！
• 您可以将比例设置为 2 比 1（右手键入的 2 个字母与左手键入的 1 个字母）。
• 由于比率是 2 比 1，因此您将用同一只手输入 2 个连续的字母，因此您必须确保它们是从键盘的外侧向内侧输入的。这个原理也适用于有向图。

我知道您说它是 QWERTY 键盘，但是在 QWERTY 键盘上使用这些原理可以给您带来一些非常好的结果，例如：

ktrd,ogkdo（德沃夏克语中的“打字机”）

kjg;g;akd;k（仅使用主行）

pjedoildupsk（只是遵循原则的随机密码）

所有德沃夏克仇恨者，嘘！

我希望这有帮助。

Answer 4

也许您可以使用一些启发式方法来衡量“打字的难易程度”。

例如，考虑转到下一个字符时移动手指的成本。这可以是手指需要移动多远、向哪个方向等的函数。

当需要切换手指或手时，您还可以增加额外的成本。

在考虑了一些成本之后，您可能会找到一个令人满意的解决方案。

希望有帮助。

Answer 5

很好的问题 - 根据上述建议，这里有一个从键 i 到键 j 的距离的公式：

权重 = 距离 * a + switch * b + same * c + shift * d + 奇怪 * e + start * f

距离是一个值，其他均为 0/1 值。

距离 - 通过在 QWERTY 键盘上叠加精细网格来获取，查找 x,y
并计算距离。距离具有正权重。如果字母组合是使用不同的手（例如aj、sk、wu...），则距离为零。

开关-负权重；切换效果很好

相同 - aq、qa、az、za 使用相同的手指。同样是积极的

Shift - 任何有转变的东西都是积极的，而且非常糟糕

奇怪 - 我不知道 $ 或 ~ 是不好的，因为你必须看着键盘。

开始 - asdfjkl 开始或结束。可能是负数&很好，因为您的手指处于休息状态。

系数 - 只要相对值看起来合理，就可以开始设置它们。
如果你真的想要变得更奇特 - 让某人输入几十组数字，使用秒表并拟合回归模型。

实施 - 假设我们有一个六字符的密码。

现在我需要以每个字母开头的六个字符的最小值。想象一下 N 个键组成的数组，位于一列中。现在想象一下六列。您的最短密码是通过六列的最短路径（允许循环）。您可能需要添加一些逻辑来消除循环，但这应该是一个很好的第一步。 （我在这里变得懒惰了 - 可能有一个图论公式可以处理这个问题。）

我敢打赌以前有人做过这个 - 特别是击键部分。

Answer 6

我将以下内容粉碎在一起。这是一项黑客工作，但似乎效果很好。

<?
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 7

构建一个代表键盘的数据结构，并对用于键入每个字符的行、列、手和手指进行编码。编写一个函数，当出现一个字符时，该函数会根据您开发的灵活规则提供“易于键入下一个”字符的列表。它可以依赖另一个计算键之间距离的函数。

就我个人而言，我并不认为用同一只手输入两次字母会很慢：只有当前一个字母使用的手指距离太近时才会很困难。例如，XQ 很难打字，因为我的手必须向上移动才能处理打字所需的相邻手指。但我一点也不觉得 BQ 很难打字，因为当我的食指仍在 B 上时，我的小指可以指向 Q。

打字 AW 也比 QS 容易得多，因为无名指更长因此，自然地适合 W，而小指位于 A，处于接近静止的位置，而 QS 则需要小指的伸展和无名指同时、相互冲突的肌肉紧缩。

如果您开始构建每个字母相对于其他字母的映射，您很快就会找到一种合理的方式来表示难易程度的各个方面。概括我的 XQ/BQ 示例，您可以进行 1 行更改需要 2 个或更多手指的距离，2 行更改需要 3 个手指的距离，而 3 行更改（可能是数字）需要交替双手。

我还注意到，WD 和 IL 之间的距离比 SE 和 KO 之间的距离稍长，这也会改变难度，因为按键的位置略有锯齿状。

通过一些分析（我建议使用 Excel 来“绘制”打字难度），我确信您可以想出一种算法来帮助您构建易于打字的单词。

如果可能，请尝试至少输入一个数字，并考虑使用空格。

Answer 8

如果您实现这一点，请在确定从一个角色移动到另一个角色的“成本”时考虑用户的区域设置。如果用户使用不同的键盘布局，那么易于输入的密码可能会变得相当麻烦。如果不需要额外的修饰键（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)

生成一系列满足您的长度和“易于打字”要求的键位置，然后使用用户当前的键盘映射来重新映射这些索引成字符。