QWERTY键盘的助记密码生成算法

12

我有一个"助记词"密码生成函数,大致如下:

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}}的字符串,其中每个奇数字符都是辅音字母,每个偶数字符都是元音字母。虽然我理解这会降低密码复杂度,但通常更容易记忆。现在我想通过生成易于输入的字符串来改进它。

QWERTY Keyboard Layout

例如,虽然我是*nix的新手,但我总是更喜欢基于RHEL的发行版而不是Debian的,主要原因是键入"yum"比键入"apt[-get]"更容易,你可以自己试试。
我应该如何实现逻辑来生成在QWERTY键盘上易于输入的字符串?

1
定义“更容易输入”。我通常发现我最容易打的单词是我可以发音的单词-所以您的方法对此非常有效。 - BlueRaja - Danny Pflughoeft
9
实际上,我认为“apt”比“yum”更容易输入,因为你可以在打字时交替使用双手。 - avakar
1
这些对我来说都差不多一样容易打字,除了"begreen"和"yii",因为有双字母,所以我打得稍微慢一些。我也发现用交替手指打字时,"apt"比"yum"稍微快一点,而且有时我只用两个手指打"yum"。 - BlueRaja - Danny Pflughoeft
1
我必须补充说明,对我来说,“apt”比“yum”更容易。希望有足够的支持者,我们可以说服人们,易于输入与个人的打字风格是模糊的。有些人用一根手指戳键盘;有些人使用课堂上教授的严格打字技巧;有些人使用自己成长出来的方法。我不相信你能找到任何算法,为所有人生成易于输入的密码。 - erisco
2
这是一个非常迷人的问题... - cwallenpoole
显示剩余3条评论
8个回答

3

Carpalx 进行了大量有关计算 打字努力 的研究,其中包括:

  • 手指移动距离
  • 手、指和行惩罚
  • 击键路径

他们研究的结果是 Colemak 键盘布局,声称比 Dvorak 更好

然而,它与您想要的相反 - 他们的目标是基于输入找到更好的键盘布局,而您正在尝试基于键盘布局找到易于输入的方法。

所以,即使你可能无法直接使用它,我认为你可能会发现它很有趣(谁知道,如果你的Perl技能很强,你可能能够提取并反转算法,因为它是GPL许可的)。


我的 Perl 水平不是很强,但我非常感谢这个链接,谢谢。 - Alix Axel
1
这个答案是基于一些研究得出的唯一相关答案。其他所有的都只是猜测。如果没有客观的衡量标准,“更难打”就毫无意义,而且非常主观。 - Vinko Vrsalovic
@Vinko:如果你看一下你所描述的链接,他们没有支持他们选择的启发式算法的数据,事实上他们自己说有些参数是主观的。确定最佳的启发式算法是主观的(针对手头的问题(无恶意))。任何你所做的研究都不会改变这个事实。事实上,你做的研究越多,对OP来说可能就越不相关。话虽如此,我同意打字努力页面应该是有用的,因此并不是不相关的,但我不明白这比任何其他启发式模型的建议更相关。 - Aryabhatta
@Moron:例如,所述的哪些启发式表示完整模型,可以根据主观参数进行调整?这些主观参数在任何答案中都有定义吗?说“研究”是错误的,但我想说的是,carpalx背后有比任何答案都更多的工作,并且这一点表现出来了。 - Vinko Vrsalovic
@Vinko:当然,他们做了很多工作,但其中大部分工作是在他们凭空提出一种启发式之后完成的。我觉得提出一个产生启发式模型的方法比给出一个具体的启发式本身更有价值,因为问题本身是相当主观的。如果他们能够在大样本人群上训练这个启发式,然后提出他们所建议的,那可能会更相关且对提问者更有用,我同意这点。无论如何,由于不清楚提问者想要什么,我们讨论哪个答案更好似乎有点毫无意义。 - Aryabhatta
显示剩余3条评论

2

您可以消除所有使用无名指和小指打字的字符(q、w、x、z、p),然后拆分由左右手键入的字符,并在这些字母之间交替。


+1,这是一个相当不错且易于实现的建议,谢谢! - Alix Axel
我尝试实现这个功能,但我意识到通过在左右手指键之间切换,我的助记符功能有点失去了意义,因为我只能拥有“ae”或“(y)uio”作为元音。 - Alix Axel
随机地,每个按键小于50%的概率保持相同的一侧。我怀疑25%的概率进行交换会导致打字还算合理但分布仍然均匀。 同时确保生成的密码有50/50的机会在任一侧(辅音/元音)开始。这将显著降低您遭受暴力攻击的风险。 - ShuggyCoUk

1

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

例如,考虑移动手指到下一个字符时的成本。这可以是手指需要移动的距离、方向等的函数。

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

在尝试了一些成本后,您可能会找到一个令人满意的解决方案。

希望这有所帮助。


这是我的想法,但我在想如何实现这样的启发式算法时遇到了困难。 - Alix Axel
问题是找出权重还是你实际上在编写代码时遇到了计算搬家成本等问题? - Aryabhatta
@Moron:我最关心的是计算从char到char + 1的移动成本... - Alix Axel
一种简单的方法是计算每对字母的成本。例如 (j,k) = 1, (j,l) = 2, (m,y) = 3 等,将其存储在表中,然后进行查找。为了简单起见,您可以将字符放置在网格上,并计算曼哈顿距离。 - Aryabhatta
对于每26个字母,手动计算一对的成本将会非常繁琐。我能自动加速查找表的生成吗? - Alix Axel
是的,就像我说的那样,使用“曼哈顿”距离可以计算出表格,但如果您已经有计算表格的代码,就不需要维护表格 :) - Aryabhatta

1

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

重量 = 距离 * a + 切换 * b + 相同 * c + 移位 * d + 奇怪的符号 * e + 开始 * f

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

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

切换-负权重;切换很好

相同-aq、qa、az、za使用同一根手指。同样为正

移位-任何带有移位的都是正面且非常糟糕的

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

开始-asdfjkl的开始或结束。可能是负面和好的,因为你的手指在那里休息。

系数 - 只要相对值看起来合理,随便编一些就行了。如果你真的想搞高级一点 - 找个人输入几十组数字,用秒表计时,拟合一个回归模型。
实现 - 假设我们有一个六位字符密码。
现在我需要每个字母开头的六个字符的最小值。想象一下你的 N 个键的数组排成一列。现在想象六列。你的最短密码是通过这六列的最短路径(允许循环)得到的。你可能需要添加一些逻辑来消除循环,但这应该是一个不错的初步尝试。(我在这里有点懒 - 可能有一个图论的公式可以解决这个问题。)
我敢打赌有人以前已经做过这个 - 尤其是按键部分。

1

你可能想要看一下Dvorak键盘中使用的原则,

将这些原则应用于密码生成算法中,可以得到以下结果:

  • 字母应该通过交替手打出。
  • 使用易于输入的组合。查看Dvorak布局并查看常见的双字母组合及其字母的位置。
  • 只使用底行中的一个字母,或者不使用。让它随机!
  • 您可以使比例为2比1(右手打2个字母,左手打1个字母)。
  • 由于比例是2比1,您将连续使用同一只手打2个字母,因此必须确保它们从键盘外部向内部打印。这个原则适用于双字母组合。

我知道你说的是QWERTY键盘,但在QWERTY键盘上使用这些原则可以得到非常好的结果,例如:

ktrd,ogkdo(在Dvorak键盘上意为“打字机”) kjg;g;akd;k(只使用主键盘区) pjedoildupsk(遵循密码原则的随机密码) 所有反对Dvorak键盘的人,闭嘴! 希望这可以帮到你。

你的建议与@superUntitled提供的建议类似,交替使用手的问题在于我只能在偶数位置使用“ae”或“uio”(请参见我的原始函数)。你会如何解决这个问题? - Alix Axel
@Alix Axel:我的方法比@superUntitled更加灵活,因为我建议您使用2比1的比例,而不是1比1,并且它不必完全是RRLRRLRRL。看看随机密码示例,它遵循我的原则(不包括元音)。它是RRLLRRLRRLR,这使得可以使用任何5个元音之一。 - Leo Jweda
pjedoildupsk不遵循您的指南。up由右手从内向外键入,oi也是如此。 - ErikE

1

我把以下内容拼凑在一起。虽然有点粗糙,但似乎运行得很好。

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


0

如果您实现此功能,请考虑用户的语言环境,以确定从一个字符到另一个字符的“成本”。如果用户使用不同的键盘布局,则易于输入的密码可能变得相当繁琐。某些在一种语言键盘上易于访问的键可能在另一种语言键盘上不可用,需要额外的修饰键(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)

生成一系列符合您长度和“打字便捷性”要求的关键位置,然后使用用户当前的按键映射将这些索引重新映射为字符。

0

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

就我个人而言,我不认为连续使用同一只手打字会很慢:只有在前一个字母使用了太近的手指时才会困难。例如,XQ很难打,因为我的手必须向上移动以处理相邻的手指来输入它们。但是我觉得BQ根本不难打,因为当我的食指仍在输入B时,我的小指可以去按Q。

输入AW比QS也容易得多,因为无名指更长,所以自然适合W,而小指在A上,处于接近休息的位置,而QS需要伸展小指并同时使无名指产生冲突的肌肉收缩。

如果你开始建立每个字母相对于其他字母的映射,很快就会找到一种合理的方式来表示各种易或难的方面。以我的XQ/BQ示例为例,你可以使一行更改需要2个或更多手指的距离,两行更改需要3个手指的距离,而三行更改(例如数字)则需要交替使用双手。

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

通过一些分析(我建议使用Excel来“绘制”打字难度图),我相信你可以想出一个算法,帮助你构建易于打字的单词。

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


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接