CN104335217B

CN104335217B - 用于确定密码强度的方法、装置和计算机程序产品

Info

Publication number: CN104335217B
Application number: CN201280073367.5A
Authority: CN
Inventors: 古兰·塞兰德; 马茨·内斯隆德; 弗雷尔·塞韦尔森
Original assignee: Telefonaktiebolaget LM Ericsson AB
Current assignee: Telefonaktiebolaget LM Ericsson AB
Priority date: 2012-05-22
Filing date: 2012-09-20
Publication date: 2017-08-29
Anticipated expiration: 2032-09-20
Also published as: US20150143509A1; US9690929B2; CN104335217A; EP2852912A1; EP2852912A4; EP2852912B1; WO2013176593A1

Abstract

公开了一种用于估计包括两个或更多个段的图形密码的强度的方法。在一些实施例中，该有利解决方案是通过执行多步骤过程来实现的。在一个步骤中，数据处理系统对第一段应用第一操作以产生变换段。在另一步骤中，数据处理系统在变换段与第二段之间执行比较操作。在另一步骤中，数据处理系统基于比较操作的结果对第一段执行惩罚操作。惩罚操作包括以下各项中的一项或多项：(1)计算惩罚值，其中惩罚值可以在计算表示图形密码的强度的值时使用；以及(2)当计算表示图形密码的强度的值时不考虑所述第一段或所述第二段。

Description

用于确定密码强度的方法、装置和计算机程序产品

技术领域

本公开涉及用于估计由用户创建的图形密码的强度的方法、装置和计算机程序产品。

背景技术

如今，很多基于计算机的服务在用户可以访问服务之前需要用户创建用户账户。通常，为了创建用户账户，用户必须选择唯一用户名和密码。通常，密码是基于文本的密码(即，字符串)。为了防止未授权个人利用用户的账户，推荐用户选择“强”密码(即，抵抗猜测或蛮力攻击的密码，例如，高熵密码)。通常，密码的“强度”(即，密码被破解的概率或者密码容易受到破解的程度)是其长度、复杂性和不可预测性的函数。

因为计算机越来越强大，因此短密码容易受到蛮力攻击。因此，很多基于计算机的服务要求其用户选择冗长的密码(例如，长度至少为8个字符的密码)。此外，这种基于计算机的服务还具有与可接受密码有关的规则，所述规则被设计为确保用户选择复杂密码。例如，一些服务不仅要求密码的长度至少为八个字符，而且还要求(i)密码包含特定数量的大写字母、数字和/或特殊字符(例如，！、$、@、#)并且(ii)密码不包含字符重复。然而，密码越长且越复杂，则用户越难以记住他或她的密码。当前存在用于估计基于文本的密码的强度的方法。这种方法可以例如通过尤其确定密码的长度和/或确定密码包含的特殊字符的数量来估计基于文本的密码的强度。

基于文本的密码的替代解决方案是图形密码。与选择字符串相反，使用图形密码而不是基于文本的密码进行认证的服务通常提示其用户选择图案。然后，图案成为用户的密码。图形密码是有利的，这是因为与字符串相比，人脑好像更能够记住图案。与基于文本的密码的长度和复杂性很像，图案越复杂，图形密码将越强，然而，难以规定与可接受的图形密码有关的规则。

因此，需要估计图形密码的强度。

发明内容

所公开的解决方案的特定实施例提供了用于估计图形密码的强度的方法、装置和计算机程序产品。在一些实施例中，该有利解决方案是通过执行多步骤方法来实现的。在一些实施例中，该方法包括：对图形密码的第一段应用第一操作以产生第一变换段。该方法还包括：在第一变换段与图形密码的第二段之间执行比较操作。该方法还包括：基于比较操作的结果，对第一段执行惩罚操作。执行惩罚操作的步骤可以包括以下各项中的一项或多项：(i)计算惩罚值，其中所述惩罚值在计算表示图形密码的强度的值时使用；以及(ii)当计算表示图形密码的强度的值时，不考虑第一段或第二段(例如，忽略第一段或第二段)。

有利地，通过这种方式，数据处理系统可以在不必存储或访问形状字典的情况下估计图形密码的强度。该能力可以允许装置在无需装置通过无线(或其他)通信方式连接到大型形状字典的情况下估计图形密码的强度。在一些实施例中，该能力可以节省诸如移动设备等的装置上的电池功率。另一个优点是系统可以在用户正在创建图形密码时向用户指示所估计的图形密码的强度。

在一些实施例中，该方法还包括：在比较操作期间确定第一变换段是否与第二段相似。

执行比较操作的步骤可以包括：确定第一变换段是否与第二段相同，并且执行惩罚操作的步骤可以响应于确定第一变换段与第二段相似而被执行。

在另一方面，解决方案提供了用于估计包括两个或更多个段的图形密码的强度的计算机程序产品，该计算机程序产品包括存储计算机代码的非瞬时性计算机可读介质。在一些实施例中，计算机可读程序代码包括：(i)用于对图形密码的第一段应用第一操作以产生第一变换段的指令；(ii)用于在第一变换段与图形密码的第二段之间执行比较操作的指令；以及(iii)用于基于比较操作的结果，对第一段执行惩罚操作的指令，其中用于执行惩罚操作的指令包括以下各项中的一项或多项：(a)用于计算惩罚值的指令，其中惩罚值可以在计算表示图形密码的强度的值时使用；以及(b)用于当计算表示图形密码的强度的值时，不考虑第一段或第二段的指令。

下面参照附图描述上述和其他方面和实施例。

附图说明

并入本文中并且形成说明书的一部分的附图示出了本发明的各个实施例，并且与描述一起进一步用于解释本发明的原则并且使相关领域技术人员能够利用和使用本发明。在附图中，相似的附图标记指示相同或功能相似的要素。

图1是用于输入图形密码的屏幕的示例。

图2A是用于输入图形密码的网格的示例。

图2B是用于输入图形密码的网格的另一示例。

图3是示出了用于估计图形密码的强度的过程的流程图。

图4示出了示例性图形密码。

图5是示出了用于估计图形密码的强度的过程的流程图。

图6示出了示例性对称图形密码。

图7示出了用于产生变换段的操作的示例。

图8是示出了用于估计图形密码的强度的过程的流程图。

图9是示出了用于确定图形密码的强度的示例性装置的框图。

图10是用于确定图形密码的强度的系统或其组件的特定实施例的框图。

具体实施方式

现在参照图1，图1是被配置为提示用户创建图形密码(例如，图案)的计算机设备100(例如，移动电话、平板电脑、膝上型计算机、PC)的示例。图案可以是二维图案、三维图案、或者四维图案。设备100包括显示屏幕101，并且在该示例中，在显示屏幕101上显示了用户可以与其交互以通过创建与显示对象102有关的图形图案来创建图形密码的显示对象102。用户创建的图形图案可以是连续的或非连续的。在一些实施例中，显示屏幕是触摸屏，并且用户通过触摸触摸屏来与显示对象102进行交互以创建图形图案。在其他实施例中，用户可以使用除了触摸屏之外的输入设备(例如，鼠标、操纵杆、识别笔、远端控制设备、用于接收语音命令的麦克风、跟踪用户眼睛移动的照相机等)与图形对象102进行交互。

在所示的示例中，显示对象102是二维网格点102，其中，每一个点由不同的正方形单元104表示。用户可以通过选择显示的点(即，单元)来创建图形图案。阴影单元104表示已经由用户选择为图形密码的一部分的图形图案。在图1中通过线106示出了图形图案的方向，并且在该情况下，用户已经创建了连续图形图案。用户所选择的图形图案是用于认证用户的秘密(即，图形密码)，从而替代传统的基于文本的密码。也即是说，终端用户记住的认证秘密是图案，或者更具体地，关于如何产生图案的手势——相对于图的一系列位置和动作。根据实现，该图案可以是用户与例如服务提供商或本地应用之间的共享秘密，或者秘密图案可以被转化/映射为用于认证的一些其他数据结构。

在其他实施例中，替代正方形单元104，显示对象102可以包括其他形状集合，例如，小圆圈(参见图2A)或汽车(参见图2B)。如图2A所示，当创建图形图案时，用户可以不仅选择点，而且还在点之间绘制线(参见例如在点291与292之间绘制的线266)。

图形对象102还可以是照片，并且在一些实施例中，网格可以覆盖照片。此外，在一些实施例中，显示对象102可以并入多于两个维度。例如，显示对象102可以是立方体(或者其他三维对象)，在立方体的每一个面上具有网格。在一些实施例中，显示对象102可以不具有x坐标和y坐标，而是取而代之地使用诸如圆形等的形状来描绘对象102的不同区域。例如，可以存在不同尺寸的圆形，每一个圆形具有相同的中心点。在一些实施例中，可以不在屏幕101上显示显示对象101，而是显示对象102可以是不具有显示器的触摸敏感的输入设备(例如，操纵杆或诸如KoalaPad等的图形平板)的一部分。在一些实施例中，图形密码可以包括用户选择显示对象102的各个部分的速度的时间要素。例如，显示对象102可以像琴键，并且用户可以输入歌曲，每一个音调与时间长度相关联。

不论用户产生的图形密码如何用于认证，贡献密码的安全性的一个因素是用户选择的图形图案的复杂性，还将其称作图案的强度。如果图案不复杂，则与基于字符串的认证系统中的弱密码一样，图案可能更容易被猜测或者可能更容易受到蛮力攻击。

在基于字符串的密码系统中，通过针对“允许”密码的各种策略(例如，密码的所需长度、要使用的所需字符集合(例如，大写字母/小写字母、数字、特殊字符)、以及禁止字符重复)来解决该问题。除了这些策略之外，还存在用于在终端用户产生密码时例如通过使用指示密码的强度的“测量计”(例如，分别具有诸如“弱”、“中等”、“强”等的指示的变量长度和/或诸如红色、黄色和绿色等的变量颜色编码的状态栏)来估计密码的强度的支持工具。强度通常与策略(具有额外字符、几个字符集合、以及没有字符重复)有关，从而提供了状态栏的延长部分。作为这种系统的示例，可以对长度评分，但是然后减去重复的次数。

针对基于图形图案的认证，图案策略可以类似地包括图案的最低长度(例如，所选网格点的数量)，并且可以向用户提供用于估计图案的“强度”的支持工具以向用户提供关于用户提议的图形密码的强度的反馈。

可以用于估计图案的强度的一种技术是在特定字典中进行查询以检查所选的图案是否包含在字典中，因此是可容易预测的。然而，这种字典将非常大，远远大于常见的语言字典。例如，与10⁷个条目量级的普通字典相比，与长度为10的ASCII密码的熵相对应的由5x5网格上长度为14的镜像对称图案构成的字典具有10¹⁵个条目的量级。此外，使用字典来评估秘密的强度对在其中输入密码的客户端设备的实现具有影响，这是因为这种字典可能由于其尺寸而不易于本地存储，并且客户端设备可能无权访问网络资源以远程访问字典。

使用字典以向用户提供与所选秘密有关的反馈的另一个缺点是它未提供与前面提到的“测量计”一样好的用户体验。“测量计”通常向用户提供了迄今为止的图案的强度的等级，并且逐渐改变。相比之下，相对于字典测试秘密实质上以更不连续的方式输出“好”或“差”。实际上，通过字典查询，可以将图案分类为好，直到最后一个手指移动，然后突然使图案呈现为差。

简言之，通过使用字典估计创建的图形密码的强度可能不是最佳解决方案。因此，本文描述了用于估计图形密码的强度的改善技术。

在一些实施例中，例如，针对图形密码的每一段，确定与该段相关联的概率相关值(例如，概率值的倒数)。概率相关值可以例如与段随机发生的概率(即，均匀概率分布)相关联。然后，对所确定的概率相关值进行组合(例如，乘)在一起以产生表示图案不太可能发生的程度的值，其是密码的强度的近似。如本文所使用的，图形密码的“段”可以是图形密码的任意部分，例如，用户选择的单个点、用户选择的两个或更多个点、连接用户选择点与紧邻的下一个用户选择点的直线、或者用户绘制的作为用户的图形密码的一部分的任意线(也称作“笔画”)。

在一般情况下，用户选择的图形图案可以是连续的，但是它也可以由多个不相交笔画构成。如果两个笔画不共享公共点，则笔画与另一笔画“不相交”。例如，用户可以使用触摸屏101上显示的图形对象102通过以下方式创建两个不连续笔画：将他/她的手指放置在图形对象102的第一点上、将他/她的手指从第一点移动到图形对象102的第二点、从触摸屏101上抬起手指、再次在触摸屏101上将他/她的手指放置在图形对象102的第三点上、将他/她的手指从第三点移动到图形对象102的第四点、并且再次从触摸屏101抬起手指。举例说明，图7A示出了包括四个笔画的图案。如上所述，因此用户创建的图形图案的段可以按照用户的笔画来定义，但是不限于此：用户创建的图案的任意部分可以被认为是图案的段。

现在参照图3，图3是示出了用于实时地估计图形密码的强度并且实时地向用户提供与所确定的强度有关的反馈的过程300的示例的流程图。过程300可以由装置100来执行。

过程300可以从步骤304开始，在步骤304，装置100将变量“b”设置为初始值(例如，1)，其中变量b表示图形密码的强度。在步骤306，装置100可以确定用户是否已经为用户的图形密码选择新段。如果不存在新段，则过程可以返回步骤306，直到存在新段为止，否则，过程300前进至步骤308。

在步骤308，装置100可以确定与段相关联的值，并且将变量“a”设置为等于所确定的值。例如，在步骤308，装置100可以基于概率分布来确定概率相关值，例如，逆概率值。例如，概率相关值可以是新段与先前输入的段相关的可能程度的函数。

在步骤309，确定a的值与b的值的乘积，然后将变量b设置为等于该乘积(即，b＝a*b)。在其他实施例中，不是确定a和b的乘积，而是可以执行其他数学运算(加法、减法、除法)。因此，通常在步骤309中确定f(a，b)(即，b＝f(a，b))。

在步骤310，基于b的当前值确定强度值(S)。在一些实施例中，S可以等于的值的可能集合是有限集合。例如，在一些实施例中，S被限制于四个值(例如，“弱”、“中等”、“强”和“非常强”)中的一个。也即是说，根据b的值，可以向密码指派特定的强度标签。在一些实施例中，S不仅是b的函数，而且还是图案的长度的函数(即，S＝f(b，1))。例如，如果所选的图案包括1个笔画，则S可以是函数：b*((k-1)choose(l-1))，其中，乘法因子((k-1)choose(l-1))是在具有l个笔画的情况下长度为k的可能图案的总数。

在步骤312中，显示值S，使得用户将具有与密码的当前强度有关的反馈。例如，在步骤312中，可以显示“密码测量计”状态栏199(参见图1)，其中，栏的长度指示所估计的密码强度。如果将密码指示为弱，则用户可以选择向图案添加另一段(例如，点或笔画)，从而过程将重复并且估计新的强度值。

现在参照图4，在一个实施例中，图4示出了与网格402交互的用户所选择的示例性图形密码400。在图4中，网格402具有16个单元(或点)。如图4中所示，用户已经以特定顺序选择了五个唯一单元以形成图案400。如过程300中所述，在一些实施例中，可以每当用户选择网格的新单元时实时地评估图形密码400的强度。例如，可以首先在用户选择图案的第一单元(在该情况下，单元404)时确定强度。如上文结合过程300所述，估计强度的过程可以首先包括确定与单元404相关联的概率相关值。在一些实施例中，所确定的概率相关值是单元404将是起始位置的可能性的逆概率。如果假设均匀概率分布，则单元404被选择为起始点的概率为1/16。因此，该概率的倒数为16。因此，当执行过程300的步骤308-312时，变量a被设置为16，变量b＝1*16(即，16)，并且所显示的强度(S)取决于b的值。

当用户选择下一个单元(在该示例中，单元406)时，再次执行过程300的步骤308-312。如果再次假设均匀概率分布并且假设用户新选择的单元紧邻先前所选的单元，则当此时执行步骤308时，变量“a”可以被设置为值3，这是因为由于用户先前选择了单元404因此用户仅具有三个选择，并且值“b”将被设置为48(即，(3)(16))。

通过使用上面的假设以及不允许回溯的假设(例如，根据服务提供商的要求)，当下一次执行步骤308-312时(即，当用户选择下一个单元(即，单元408)时)，“a”将被设置为等于4并且b将被设置为192(即，(4)(48))。类似地，当选择下一个单元(即，单元410)时，“a”将被设置为等于7，并且“b”将被设置为1344(即，(7)(192))。然而，在一些实施例中，如果用户未改变图案的方向，则评估惩罚。在图4的示例中，用户未改变图案的方向，这是因为单元410与单元406和408对齐(即，直线连接单元406-410)。因此，在针对未改变图案方向评估惩罚的实施例中，“a”将不会被设置为等于7，而是等于(7)(r)，其中r＜1(例如，r＝0.5)。

当最后一次执行步骤308-312(即，选择最后一个单元(即，单元412))时，“a”将被设置为等于7(假设不评估惩罚)并且b将被设置为等于9408(即，1344*7)。然而，在一些实施例中，由于用户未改变图案的方向，因此将评估惩罚。因为这是用户连续第二次未改变图案的方向，因此惩罚值r可以被设置为等于r²。因此，在一些实施例中，当用户选择最后一个单元412时，“a”被设置为等于7*r²。因此，在评估惩罚的实施例中，“b”的最终值将为9408*r³而不是9408。如示例说明的，如果用户n次都未改变方向，则在一些实施例中，当计算下一个b值时，b值可以乘以rⁿ。示例还说明图形密码的强度可以是数(例如，9408)，使得数越大，图形密码越强。

在上面的示例中，假设均匀概率分布。也即是说，假设选择可用单元中的任意一个的概率是1/x，其中x是要从其中进行选择的可用单元的数量。在其他实施例中，用户将从可用单元集合中选择给定单元的概率可以基于除了均匀概率分布之外的其他内容。例如，基于历史数据，可以观察到与任何其他单元相比，左上角单元更常被选择为第一单元。因此，可以基于先验用户数据或其他分布来确定概率。

人工绘制图案的一个方面是图案通常高度对称，这降低了复杂性(例如，熵)并且使得它们更容易被猜测。因此，在包括上述实施例的一些实施例中，当估计图案的强度时考虑用户选择的图形图案的对称性或结构。例如，如果用户的图形图案在某些方面是对称的，则可以评估惩罚。更具体地，在一些实施例中，几何操作(或者其他操作)用于变换用户的图形图案(或其段)以产生变换图案。然后，将变换图案与用户的原始图案进行比较，以确定原始图案与变换图案之间的相似性。原始图案与变换图案之间的相似性提供了关于原始图案的对称性的指示。因为对称图案指示图案的较低不可测性，这使得图案较弱，因此如果用户提议的图案被发现是对称的(或部分对称的)，则评估惩罚。

可以用于测试图案的对称性的操作包括但不限于：关于特定线、面或点进行反射；关于特定点旋转特定角度；对图案进行线性或非线性缩放(放大或缩小)(线性或非线性是指是否将相同的缩放因子应用于图案的所有部分或者是否使用一个因子缩放图案的一些部分并且使用另一因子缩放其他部分)；其他线性变换，例如，剪切；在特定方向上平移/移动特定距离；回绕网格的边缘，使得在一个边缘/角到达网格边界的(移动的)图案在另一边缘/角继续；上述操作中的一些或全部的组合(例如，顺序地执行操作集合)。

现在参照图5，图5是示出了在一些实施例中可以由装置100执行的过程500的流程图。过程500可以从步骤502开始，在步骤502，装置100对图形密码的至少第一段应用第一操作以产生至少第一变换段。例如，图6示出了用户选择的图案600，图案600具有U形。在步骤502，可以沿着线608反射诸如线604等的U形图案的第一段，从而形成第一变换段。

在步骤504，装置100在第一变换段与图形密码的第二段之间执行比较操作。例如，装置100可以确定第一变换段是否与图形密码的第二段“相似”和/或“相同”。如果第一变换段在外观或字符上像第二段而不是相同，则装置100可以确定第一变换段与图形密码的第二段“相似”。例如，如果第一变换段和第二段相同的程度超过预定阈值(例如，10％或更高)，则可以认为第一变换段与第二段相似。例如，如果例如属于第一变换段的网格点的75％也是第二段的一部分，则可以认为第一变换段与第二段“相似”。如果第一变换段和图形密码的第二段完全相同(即，100％一致)，则装置100可以确定第一变换段与图形密码的第二段“相同”。在图6中所示的示例中，第一变换段(即，沿着线608反射或折叠的线604)与同第二段相对应的线606相同。

在步骤506，装置100在步骤506基于步骤504的结果对第一段执行惩罚操作。例如，如果装置100确定第一变换段与图形密码的第二段既不相似也不相同，则装置100可以执行置零操作或者可以将惩罚值(PV)设置为等于1(步骤512)。另一方面，如果装置100确定第一变换段与图形密码的第二段相似或相同，则装置100可以执行步骤508和510中的一个或多个。

在步骤508，装置100计算或选择惩罚值(PV)，其中惩罚值可以在计算表示图形密码的强度的值时使用。例如，在一些实施例中，可以在过程300的步骤309与310之间执行过程500，以减小(如果必要的话)通过执行步骤309所确定的“b”值。例如，在执行步骤309从而针对图形密码产生“b”值之后，可以执行过程500，并且如果第一变换段与第二段相同/相似，则可以将PV设置为小于1的某一值，然后可以将b设置为等于(b)(PV)，从而在第一变换段与第二段相同/相似的情况下产生减小的“b”值。等同地，如果第一变换段与第二段相同/相似，则可以将PV设置为大于1的某一值，然后可以将b设置为等于(b)/(PV)，从而在第一变换段与第二段相同/相似的情况下产生减小的“b”值。惩罚也可以是“加法”而不是“乘法”。例如，可以通过减去PV来减小b的值，使得B被设置为b-PV或者b+PV(如果PV本身为负)。

在步骤510，装置100在计算表示图形密码的强度的值时(例如，在执行过程300之前)不考虑第一段或第二段。在图7A、图7B和图7C中用图形示出了该特征。图7示出了由段708-712构成的图形密码700。当第一次执行过程500时，段708可以是进行变换的“第一”段。如果假设沿着线704反射段708，则第一变换段将与段710(“第二段”)相同。因此，当估计密码700的强度时，可以不考虑段708。例如，可以从图形密码中“移除”不考虑的段，如图7B中所示。当下一次执行过程500时，段711可以是进行变换的“第一段”。如果假设沿着线706反射段711，则第一变换段将与段709(“第二段”)相同。因此，当估计密码700的强度时，也可以不考虑(例如，忽略)段711或从密码中移除段711，如图7C中所示。因此，与图7A中所示的图案相反，将基于图7C中所示的图案来确定密码700的强度。该方法的理由在于对称布置的段应当仅一次被视为对密码的强度有贡献。

现在参照图8，图8是示出了在一些实施例中可以由装置100执行的用于评估图形密码的强度的过程800的流程图。过程800从步骤802开始，在步骤802，装置100发起过程800。在步骤802，过程800可以设置变量b，以表示图形密码的强度。在步骤802中，过程800还可以设置每一个评估函数值m1……mt至1。

在步骤804，选择用户创建的图形密码的第一段。

如图8中所示，过程800可以在步骤806中基于所选择的段的概率的评估来计算b的新值。该评估可以与图3中的步骤308类似。

在步骤808，过程800执行操作G1以变换所选择的段从而产生变换段。例如，为了产生变换段，操作G1可以是：关于预定线或点反射所选择的段；关于预定点将所选择的段旋转一定角度；缩放所选择的段；在预定方向上将所选择的段平移预定距离；或者执行某一其他变换操作。

在步骤808，确定变换段与用户创建图案的除了所选择的段之外的任意段是否匹配。例如，在一些实施例中，可以执行比较操作以确定变换段是否与用户创建图案的某一其他选择段相同，例如，变换段是否与其他选择段相同。在一些实施例中，可以执行比较操作以确定变换段是否与用户创建图案的其他选择段相似，例如，变换段和其他选择段至少10％相同，或者在其他实施例中，至少50％相同。如果过程800确定变换段与用户创建图案的段相匹配，则过程800可以基于先前的m1以及与所选择的段相关联的概率相关值来计算新的m1(步骤810)。

不论过程800确定所选择的段变换还是未变换到另一段，过程都基于确定从步骤808或步骤810继续进行类似确定。如图8中所示，该确定可以包括基于另一操作(例如，对所选择的段的变换)进行确定，直到在步骤812中向所选择的段应用最后一个变换操作，即，操作Gt，t＝2、3……，以产生新的变换段为止，并且确定新变换的段是否与用户创建图案的已经存在的段相匹配。如果步骤812中的比较操作提供肯定结果，则过程800可以基于先前的mt和与所选择的段相关联的概率相关值来计算新的mt(814)。

不论过程800确定段使用操作Gt变换还是未变换到另一段，过程都可以从812或814继续以在步骤816中计算惩罚值(pv)。在一些实施例中，可以使用评估函数针对所有位置变动的最大乘积以段之间的比值为幂来计算pv：

pv＝max mj^ratioGj

其中，j与具有每一个单独计算的惩罚值中的最高计算惩罚值的评估函数值和变换操作相对应。如本示例中所提供的，与图形密码中的所有段相比，操作中的段在原始图形密码中具有对应项。

在步骤816之后，过程800可以前进至步骤818，在步骤818，确定值S并且向用户显示(或以其他方式指示)值S，其中，S表示迄今为止用户创建的图形密码的估计强度。S可以是b和pv的函数(例如，S＝f(b，pv))。也即是说，步骤818与上文所述并且如图3中所示的步骤310和312相对应。在步骤820中，过程800确定图形密码中是否存在还未处理的任何段，如果是，则选择要处理的下一个段(步骤822)。在步骤822之后，过程800返回步骤806。

应当注意的是，存在除了基于反射、旋转等的前述几何定义之外的其他对称构思。如本领域中公知的，图形由多个顶点(或点)V以及边缘集合E构成，其中每一个边缘连接V中的一些顶点对，例如，如果u和v是顶点，则可能存在标记为(u，v)的边缘。现在可以将用户选择的图形图案视为顶点与用户选择的点(例如，网格点)相对应并且边缘与相邻选择点对相对应的图形。(在图案由多于一个笔画构成的情况下，可以将每一个笔画视为子图形。)将图案解释为图形(集合)使得能够使用接下来讨论的其他对称性构思。

如果可以找到顶点V到顶点V’的(双射)映射函数f使得映射保留边缘，则两个图形A＝(V，E)和B＝(V’，E’)被认为是同形的。即，针对V的所有顶点x、y和V’的所有顶点x’、y’，在f(x)＝x且f(y)＝y’的情况下，当且仅当(x’，y’)是E’中的边缘时，(x，y)才是E的边缘。图形A与自身的同形(即，B＝A)被称作自同构。显而易见，t顶点图形不可能具有多于t！(t的阶乘)个自同构。通常，图形可以具有某一数量的(“n”个)自同构，1＜＝n＜＝t！。图形越对称，自同构组应当越大。因此，一种方法是计算自同构的数量并且使用该数量作为图案复杂性的度量：数量越大，越对称，并且图案复杂性越小。备选地，基于自同构的数量来计算惩罚值PVa。值PVa可以单独使用和/或与先前基于例如旋转或反射对称等所述的惩罚值结合使用。

现在参照图9，图9是根据一些实施例进一步示出装置100的框图。如图9所示，根据一些而非每一个实施例，装置100可以包括用于显示图形对象102的触摸屏902和用于估计用户例如通过与触摸屏902交互创建的图形密码的强度并且用于向用户提供反馈(参见例如图1中所示的强度状态栏199)的数据处理系统904。也即是说，数据处理系统904可以执行用于评估图形密码的强度的过程，如所公开的包括过程300、过程500和过程800。在一些实施例中，数据处理系统904和触摸屏902是同一设备(例如，智能手机)的一部分。在其他实施例中，数据处理系统904位于触摸屏902的远端。此外，如上文所讨论的(参见段落0024)，装置可以不包括触摸屏，并且用户可以使用除了触摸屏之外的输入设备(例如，鼠标、操纵杆、识别笔、远端控制设备、用于接收语音命令的麦克风、跟踪用户眼睛移动的照相机等)与图形对象102交互。

现在参照图10，图10示出了根据实施例的装置100的示例性框图，其中装置100是移动通信设备(例如，智能手机、平板电脑、或膝上型计算机)。图10中的装置100包括触摸屏902；数据处理系统904；收发机1006和天线1004。如图10中所示，数据处理系统904可以包括数据处理器1008，例如，一个或多个微处理器和/或一个或多个电路，例如，专用集成电路(ASIC)、现场可编程门阵列(FPGA)等；数据存储设备1010，其可以包括一个或多个非易失性存储设备和/或一个或多个易失性存储设备(例如，随机存取存储器(RAM))。在数据处理器1008包括微处理器的实施例中，提供了计算机程序产品，计算机程序产品包括执行计算机程序的计算机可读程序代码1043(软件)，该计算机可读程序代码1043被存储在计算机可读介质1042上，例如但不限于：磁性介质(例如，硬盘)、光学介质(例如，DVD)、存储器设备(例如，随机存取存储器)等。在一些实施例中，计算机可读程序代码1043被配置为使得当由数据处理器1008执行时，代码1043使处理器1008执行本文所述的步骤(例如，图3、图5和图8中所示的流程图中所示的一个或多个步骤)。在其他实施例中，装置100被配置为执行上述步骤而无需代码。也即是说，例如，数据处理器1008可以仅由一个或多个ASIC构成。因此，可以在硬件和/或软件中执行本发明的上述特征。

Claims

1.一种用于估计包括两个或更多个段的图形密码的强度的方法，所述方法包括：

(a)对所述图形密码的第一段应用第一操作以产生第一变换段；

(b)在所述第一变换段与所述图形密码的第二段之间执行比较操作，其包括确定所述第一变换段是否与所述第二段相同或相似；

(c)基于所述比较操作的结果，对所述第一段执行惩罚操作，其中执行所述惩罚操作的步骤包括：

(c1)计算惩罚值，其中所述惩罚值用在计算表示所述图形密码的强度的值中；以及

(c2)在所述第一变换段与所述第二段相同或相似的情况下，当计算表示所述图形密码的强度的值时不考虑所述第一段或所述第二段。

2.根据权利要求1所述的方法，其中，

所述图形密码的所述第一段是第一点，所述第一点具有第一坐标，

所述图形密码的所述第二段是第二点，所述第二点具有第二坐标，

所述第一变换段由具有第三坐标的第一变换点构成，以及

步骤(b)包括：确定所述第三坐标是否与所述第二坐标相同。

3.根据权利要求1所述的方法，其中，

所述图形密码的所述第一段包括有序点集合P1、P2、P3、……、Pn，

所述方法还包括：确定表示所述第一段的强度的值，所述确定步骤包括：针对所述有序点集合中包括的每一个点，基于第一概率分布来确定与所述点相关联的概率相关值，以及

表示所述第一段的强度的值是所确定的概率相关值的函数。

4.根据权利要求3所述的方法，其中，

确定表示所述第一段的强度的值的步骤还包括：

确定点P1、P2和P3是否均位于同一直线上，以及

响应于确定点P1、P2和P3均位于同一直线上，评估所述惩罚值。

5.根据权利要求1至4中任一项所述的方法，其中，对所述图形密码的所述第一段应用所述第一操作的步骤包括以下各项中的一项或多项：

(i)将所述第一段绕第一点旋转X度，其中X>0，以及

(ii)沿着第一指定线反射所述第一段。

6.根据权利要求1至4中任一项所述的方法，还包括：

(d)对所述图形密码的所述第一段应用第二操作以产生第二变换段；

(e)在所述第二变换段与所述图形密码的第三段之间执行比较操作；

(f)基于所述第二变换段与所述第三段之间的比较操作的结果，对所述第一段执行惩罚操作，其中执行所述惩罚操作的步骤包括以下各项中的一项或多项：

(f1)计算惩罚值，其中所述惩罚值用在计算表示所述图形密码的强度的值中；以及

(f2)当计算表示所述图形密码的强度的值时，不考虑所述图形密码中的所述第一段或所述第三段。

7.一种用于估计包括两个或更多个段的图形密码的强度的装置，所述装置包括：

数据处理系统，被配置为执行包括以下各项的过程：

8.根据权利要求7所述的装置，其中，

所述第一变换段由具有第三坐标的第一变换点构成，以及

步骤(b)包括：确定所述第三坐标是否与所述第二坐标相同。

9.根据权利要求7所述的装置，其中，

所述图形密码的所述第一段包括第一线，所述第一线从具有第一坐标的第一点延伸到具有第二坐标的第二点，

所述变换段由第一变换线构成，所述第一变换线从具有第三坐标的第三点延伸到具有第四坐标的第四点，以及

步骤(b)包括：确定所述图形密码是否包括从所述第三点延伸到所述第四点的线。

10.根据权利要求7至9中任一项所述的装置，其中，

所述过程还包括：确定表示所述第一段的强度的值，所述确定步骤包括：针对所述有序点集合中包括的每一个点，基于第一概率分布来确定与所述点相关联的概率相关值，以及

表示所述第一段的强度的值是所确定的概率相关值的函数。

11.根据权利要求10所述的装置，其中，

确定表示所述第一段的强度的值的步骤还包括：

确定点P1、P2和P3是否均位于同一直线上，以及

响应于确定点P1、P2和P3均位于同一直线上，评估惩罚。

12.根据权利要求7至9中任一项所述的装置，其中，对所述图形密码的所述第一段应用所述第一操作的步骤包括以下各项中的一项或多项：

(i)将所述第一段绕第一点旋转X度，其中X>0或X<0；以及

(ii)绕第一指定轴折叠所述第一段。

13.根据权利要求7至9中任一项所述的装置，其中，所述过程还包括：

(f1)计算惩罚值，其中所述惩罚值可用在计算表示所述图形密码的强度的值中；以及

(f2)当计算表示所述图形密码的强度的值时，不考虑所述第一段或所述第三段。

14.根据权利要求7至9中任一项所述的装置，其中，所述图形密码是由用户创建的。

15.根据权利要求7至9中任一项所述的装置，其中，所述图形密码是由所述装置从输入设备接收的。

16.根据权利要求15所述的装置，其中，所述输入设备的位置远离所述装置。

17.根据权利要求15所述的装置，其中，所述输入设备包括触摸屏。

18.根据权利要求15所述的装置，其中，输入设备是输入输出设备，并且所述数据处理系统被配置执行的过程还包括：

计算表示所述图形密码的估计强度的值；

使用输入输出设备来向用户指示所述图形密码的估计强度。