生成无密钥数字多重签名的系统和方法

摘要

提供了一种生成无密钥数字多重签名的方法。该方法包括：从一个或多个客户端计算机接收多重签名生成请求，基于该签名生成请求构建子树，并构建包括该子树的搜索树。该方法还包括分配显式长度标记到该搜索树的叶节点以平衡该搜索树并应用哈希函数到该搜索树的每个节点。根哈希值和该搜索树的高度构成生成的总签名请求，然后接收基于该总签名请求的总签名。无密钥数字多重签名基于该总签名生成并包含隐含长度标记以验证签名生成请求的数量受到了限制。如果该搜索树的高度没有超过预定的高度限制，则该总签名被生成。

说明书

技术领域

本发明一般地涉及数字签名的创建。更具体地，本发明涉及生成用于数字 数据的无密钥数字多重签名(keyless digital multi-signatures)的系统和 方法。

背景技术

数字签名常用来认证数字数据，比如文件、报文、财务信息以及其它数据。 当一块数据被数字签名，该数据的接收者可以验证该数据来自于特定的发送者， 通称为签名者，以及该数据从其被签名后没有被修改。数字签名也可以在数据 被创建时或数据被发送时进行验证。现有的数字签名方案使用公钥密码，其中 签名者使用私人密钥创建数字签名，与该私人密钥配对的公钥被用来验证该数 字签名。公钥与使用公钥证书的签名者的身份绑定，而该公钥证书由在这种公 钥基础设施(public-key infrastructure)方案中的受信任的认证机构 (Certificate Authority)发布。接收者使用该公钥证书来验证该数字签名。

但是，这些现有的数字签名方案有一些缺点。只要私人密钥被发布，签名 者可以使用该私人密钥产生无限数量的数字签名。更重要地，如果该私人密钥 失窃，则未被授权的实体也可以作为签名者生成并分发合法的数字签名。在这 种情况下，合法的签名者可以尝试作废该私人密钥，但是很难确定在该私人密 钥丢失和该私人密钥被作废之时之间的时间段内是否已经有伪造的签名被创 建。验证先前创建的签名是否是有效的也变得更加复杂，因为与那些签名关联 的私人密钥已经被作废。而且，由于私人密钥的创建不受签名者的控制，因此 现有的数字签名方案依赖于认证机构的可信度。如果认证机构泄密，则基于该 认证机构发布的私人密钥创建的数字签名将是可疑的。因此，签名者必须给予 认证机构无条件的信任。

其它的数字签名方案试图通过在合法签名者和服务器之间共享私人密钥来 减少如果私人密钥失窃时未被授权的实体创建数字签名的风险。但是公钥密码 仍然包含在这种服务器支持的数字签名方案中，私人密钥仍然可以被未被授权 的实体泄露。还有其它的数字签名方案使用试图减少在私人密钥丢失和该私人 密钥被作废之时之间的时间段内的风险的时间戳服务。但是，这种类型的方案 只支持公钥基础设施和前文详述的与它相关联的风险。并且，由于可能不知道 私人密钥何时丢失或被盗，因此在该私人密钥被作废之前仍然可能有伪造的签 名被创建。

此外，一些现有的数字签名方案不依赖公钥和/或私人密钥，而是使用能够 一次支持来自于客户端计算机的单个签名请求的签名生成服务器。在一个方案 中，无密钥数字签名服务提供商运行顶层的签名生成服务器，该顶层的签名生 成服务器与较低层的服务器通信，该较低层的服务器可以被其它实体运行，比 如该服务提供商的客户。该服务提供商可能希望针对在该顶层签名生成服务器 中生成的签名向该较低层服务器的运行者收费。在这种方案中，一次产生的无 密钥签名的数量可能不容易被追踪或限制。当验证生成的签名时可以执行检查 哈希链的总长度来追踪生成的签名的数量，但是这将要求所有的客户在生成的 签名的数量上有相同的最大限额。在这种方案中不同客户的需求无法被满足。

另一种限制顶层签名生成服务器生成的签名的数量的方法是当验证生成的 签名时在哈希链中的每个步骤包括一个数字标记。对生成的签名的数量的限制 可以为每个客户不同地设置，因此不会所有的客户必须具有相同的最大限额。 在这种方案中，当签名被验证时，为了成功地验证该签名，将检查数字标记以 确保它们是严格地按升序排列的，也就是说，每个数字标记必须比哈希链中前 一个步骤的数字标记大。但是，客户服务器可能在这种方法中回避检查该数字 标记以避开对生成的签名的数量的限制，而剩余的签名将仍然能够成功地验证。

发明内容

本发明提供来基于从一个或多个客户端计算机接收多个签名生成请求而生 成无密钥数字多重签名。通过同时处理多个签名请求，本发明实现了更有效率 和更快地生成无密钥数字签名。而且，本发明可以限制一次能够被生成的签名 的数量从而追踪和/或限额客户端计算机为记账或其它目的而请求的签名。本发 明一个实施例中，揭露了一种生成无密钥数字多重签名的系统和方法，其中服 务提供商的计算机接收来自于客户端计算机的多个签名生成请求。构建包括每 个客户端计算机的子树的搜索树。该搜索树的叶节点与每个签名生成请求对应。 该搜索树通过给该搜索树的叶节点根据需要指定显式长度标记而保持平衡。通 过对节点应用哈希函数，该搜索树中的每个节点的哈希值被计算出来。搜索树 的根节点的哈希值和搜索树高度标记组成总签名请求。该总签名请求产生将在 服务提供商计算机中被创建和接收的总签名。只有当搜索树高度标记没有超过 高度限制时，该总签名才被创建。针对签名生成请求的无密钥数字多重签名基 于该总签名生成。当该无密钥数字多重签名被生成并验证时，在该总签名中的 为空的隐含长度标记被填充，以使得签名生成请求的数量受到限制。其它的特 征和优点将通过下文中的描述和附图进行说明。

附图说明

图1为生成无密钥数字多重签名的方法的整体流程图；

图2为显示在图1中的生成操作中对搜索树的节点应用哈希函数的流程图；

图3为显示在图1中的生成操作中生成总签名的流程图；

图4为显示在图1中的生成操作中接收总签名后生成无密钥数字多重签名 的流程图；

图5A-5D显示了根据本发明实施例的签名生成请求和构建的结果的哈希树；

图6A-6B显示了根据本发明实施例的对哈希树的节点应用哈希函数；

图7A-7B显示了根据本发明实施例的与无密钥数字多重签名的生成关联的 哈希树；

图8显示了根据本发明实施例的与无密钥数字多重签名的生成相关的哈希 链和无密钥数字多重签名。

具体实施方式

本发明容许很多不同形式的实施例，附图中所示的和将在此进行详细描述 的是本发明的优选的实施例，应当理解，当前揭露的内容将被认为是本发明的 原理的实例，而不是想要将本发明的主要方面限制到这些描述的实施例上。

图1显示了生成无密钥数字多重签名的流程100的优选的实施例。该流程 100的结果是响应从一个或多个客户端计算机接收的多重签名生成请求创建无 密钥数字多重签名。该流程100可以在单个的服务器上或者在相互之间电气通 信的多个服务器上实现。在一个实施例中，该服务器可以由为一个或多个客户 端计算机创建数字无密钥多重签名的单个服务提供商和/或其它服务提供商运 行。另一个实施例中，父服务器可以由服务提供商运行而与该父服务器通信的 子服务器可以由其它的实体运行。本实施例中，该子服务器可以将签名生成请 求发送到父服务器。该父服务器然后可以生成无密钥数字多重签名并将该无密 钥数字多重签名发送回子服务器。

该服务器可以包括适宜的处理器，如本领域内技术人员所熟知的一样。该 处理器可操作地连接到至少一个存储设备，比如硬盘或闪存或其它适宜的存储 设备，这些存储设备可以包括易失性存储器元件(例如，随机存取存储器(RAM， 比如动态随机存取存储器(DRAM)、静态随机存取存储器(SRAM)、同步动态 随机存取存储器(SDRAM)等等))和非易失性存储器元件(例如，只读存储器 (ROM)、硬盘、磁带、光盘只读存储器(CDROM)等等)中的任意一个或其结 合。而且，该存储设备可以结合电子的、磁的、光的和/或其它类型的存储介质。 该存储设备可以具有分布式结构，其中不同的元件彼此远离设置，但是仍然可 以被处理器存取。

本发明的步骤和/元件，和/或它们的部分可以使用源程序、可执行程序(目 标代码)、脚本或任何其它包括一系列将被执行的指令的实体实现。当为源程 序时，该程序需要通过可以包括在或未包括在存储器中的编译器、汇编器、解 释器或类似程序进行翻译，以便连同操作系统(O/S)正确地运行。此外，实现 本发明的软件可以用下述语言编写：(a)面向对象的编程语言，其具有数据类 和方法类；或(b)面向过程的编程语言，其具有例行程序、子例行程序和/或 函数，例如但不限于C、C++、Pascal、Basic、Fortran、Cobol、Perl、Java 和Ada。

当服务器在运行中时，处理器用于执行存储在存储设备中的软件、对存储 设备进行数据存取、以及通常按照该软件控制服务器的运行。本发明的软件方 面和操作系统整体地或部分地，但是典型地为后者，被处理器读出，或许在处 理器中被缓冲，然后被执行。

当本发明或其一些方面在软件中实现时，应该注意到该软件可以被存储在 任何计算机可读介质上以被或连同任何计算机相关的系统或方法使用。在本文 的上下文中，计算机可读介质是能够容纳或存储用于被或连同计算机相关的系 统或方法使用的计算机程序的电子的、磁的、光的或其它物理的设备或装置。 本发明可以在任何计算机可读介质中实现以用于被或连同指令执行系统、装置 或设备使用，比如基于计算机的系统、包含处理器的系统或能够从指令执行系 统、装置或设备取得指令并执行指令的其它的系统。在本文的上下文中，“计 算机可读介质”可以是任何能够存储、通信、传播或传送用于被或连同指令执 行系统、装置或设备使用的程序的装置。该计算机可读介质可以是，例如但不 限于：电子的、磁的、光的、电磁的、红外的或半导体的系统、装置、设备或 传播介质。计算机可读介质的更详细的例子(非无遗漏的清单)将包括：具有 一条或多条导线的电气连接(电子的)、便携式计算机磁盘(磁的)、随机存 取存储器(RAM)(电子的)、只读存储器(ROM)(电子的)、可擦除可编程 只读存储器(EPROM、EEPROM(电可擦除可编程只读存储器)或闪存存储器)(电 子的)、光纤(光的)和便携式光盘只读存储器(CDROM)(光的)。注意到该 计算机可读介质甚至可以是程序打印于其上的纸或其它的适宜的介质，该程序 可以通过例如光学扫描该纸或其它介质而被电子地捕获，然后被编译、解释或 如果需要以适宜的方式不同地处理，然后被存储到计算机存储器中。

为了在服务器之间和/或在服务器和客户端计算机之间通讯，服务器中设有 网络通信设备和电路。在一个优选的实施例中，该网络通信设备包括网卡，比 如以太网卡。在一个优选的网络环境中，每个服务器设置为使用传输控制协议/ 互联网协议(TCP/IP协议)通过网络301进行通信。但是，可以理解，还可以 使用多种网络协议，比如互联网分组交换/顺序分组交换(IPX/SPX)协议、网 件(Netware)、点对点协议(PPP)和其它的网络协议。无线网络连接也是可 以考虑的，比如无线以太网(wireless Ethernet)、卫星网(satellite)、 红外(infrared)和射频(radio frequency)网络。

参见图1，在流程100的步骤102，服务提供商计算机可以从一个或多个客 户端计算机接收多个签名生成请求502。每个该签名生成请求502可以包括数据 504、树高度标记506和客户端计算机标识符508，如图5A所示。例如，在图 5A中，第一签名生成请求502具有数据504：x(1)、树高度标记506：4和客户 端计算机标识符508：“AA”。数据504可以表示任何类型的能够用无密钥数字 多重签名签署的数字信息。数据504可以包括文件、电子邮件或任何其它类型 的数字化表现的信息。树高度标记506表示包含在签名生成请求502中的树的 高度。当在流程100中的后续步骤中创建搜索树524时，该签名生成请求502 中的树的高度将被考虑进去，以使得该搜索树524保持恰当的平衡的平衡。该 树的根哈希值可以包含在签名生成请求502中以表示与该数据504相关的多重 签名生成请求。客户端计算机标识符508是发出签名生成请求502的客户端计 算机的唯一标识。该客户端计算机标识符508可以是文本、数字、字母数字混 合或其它的识别客户端计算机的表征。

在步骤104，签名生成请求502可以根据它们各自的客户端计算机标识符 508进行分组。在一个优选的实施例中，该签名生成请求502可以存储在分类数 据库中。在图5A的例子中显示了三个客户端计算机标识符508：AA、AB和BB。 签名生成请求502被客户端计算机标识符508按字母顺序分组。如果客户端计 算机标识符508使用了其它的表征，可以使用标识符508的任何顺序关系将签 名生成请求502分组进分类数据库中。

每个客户端计算机的子树可以在步骤106建立。该子树可以基于在步骤104 执行的该签名生成请求502的分组而建立。特别地，每个子树的叶节点每个被 分配一个签名生成请求502。如从图5B中的例子可见的一样，具有为每个客户 端计算机标识符AA、AB和BB分别建立的三个子树510、512和514。在子树510、 512和514中的叶节点516具有分配给它们的签名生成请求502。对于客户端计 算机标识符AA和AB的子树510和512，还具有另外的节点518，该节点518将 是将在流程100的后续步骤中构建的搜索树524的中间节点。

在步骤108中，可以构建搜索树骨架522并将子树分配到该搜索树骨架522 以构建搜索树524，如图5C和5D中的例子所示。图5C中的搜索树骨架522包 括来自于子树510、512和514的中间节点518以及叶节点“＝BB”516。该叶节 点“＝BB”516被包含在搜索树骨架522中，因为它是在步骤106中构建的客户 端计算机标识符BB的子树514。搜索树骨架522被用来主要基于搜索树524的 叶节点516中的客户端计算机标识符508的词典特征(lexicographical  characteristics)而连接子树510、512和514。图5D中的例子所示的搜索树 524基于子树510、512和514以及搜索树骨架522构建。该搜索树524包括叶 节点516、中间节点518和根节点520。通过对该搜索树524的每个节点应用哈 希函数，可以生成总签名请求528，下文将进一步详细描述。在图5D的搜索树 524中与中间节点518相关的标记“＝AA”、“＝AB”和“＝BB”是分配给该中间 节点518的搜索关键字。每个中间节点518的子节点和孙节点具有与各自的中 间节点相同的客户端计算机标识符(例如，AA、AB或BB)。例如，具有搜索关 键字“＝AA”的中间节点518具有两个子节点，每个子节点具有客户端计算机标 识符AA。

在步骤110，显式长度标记526被分配到每个叶节点516以平衡该构建的搜 索树524。流程100重复步骤110和112直到所有的叶节点都被分配了显式长度 标记526。该显式长度标记526可以为0或不为0。搜索树524可能会由于签名 生成请求502中的树高度标记506和/或由于包含在搜索树524中的单个的哈希 链的长度而不平衡。由于包含在每个签名生成请求502中的树，树高度标记506 增加了搜索树524的高度。

如从图5D中的例子可见的一样，最高的高度来自于签名生成请求502：x(3) 和x(4)。特别地，签名生成请求502：x(3)具有为4的树高度标记506而签名 生成请求502：x(4)具有为3的树高度标记506，但是该签名生成请求502：x(4) 在搜索树524中是比签名生成请求502：x(3)低的层级。由于这些树高度标记 506，在分配任何显式长度标记526之前，搜索树524的高度为7。但是，为了 恰当地平衡该搜索树524，在需要时显式长度标记526被分配到叶节点516。在 图5D所示的例子中，不为0的显式长度标记526需要被分配给签名生成请求502： x(1)、x(5)和x(6)以使得从这些各自的叶节点516到根节点520的高度为7。 也就是说，在步骤110和112，显式长度标记526的分配考虑了叶节点516在搜 索树524中所处的层级以及在签名生成请求502中的树高度标记506。

搜索树524的所有节点的哈希值可以在步骤114计算，这将参考图2进行 进一步详细说明。在步骤202，检查搜索树524的一个确定的节点。在步骤204， 取决于该节点是叶节点516还是非叶节点(中间节点518或根节点520)，步骤 114中的该流程分别走向步骤206或步骤210。如果该节点是叶节点516，在步 骤206，哈希函数602可以被应用到基于数据504、树高度标记506、客户端计 算机标识符508和显式长度标记526的叶节点516。图6A显示了签名生成请求 502：x(5)的例子。结果的哈希值604y可以在步骤208被分配给该确定的叶节 点516。但是，如果在步骤204中被检查的节点是非叶节点518、520，则哈希 函数602可以被应用到客户端计算机标识符508以及连接到该非叶节点518、520 的左侧子节点和右侧子节点606的哈希值。一个例子显示于图6B。该非叶节点 可以包括中间节点518或根节点520。结果的哈希值608y可以在步骤208被分 配给非叶节点518、520。该哈希函数602可以包括安全哈希算法-1(SHA-1)、 安全哈希算法2-224(SHA2-224)、安全哈希算法2-256(SHA2-256)、安全哈 希算法2-384(SHA2-384)、安全哈希算法2-512(SHA2-512)、成熟信息-摘 要算法-160(RIPEMD-160)和其它密码哈希函数。

最后，只要搜索树中所有其它的节点的哈希值已经计算出来，就可以计算 出搜索树524的根节点520的根哈希值530r。该根哈希值530r表示并包括搜索 树524中所有其它节点的哈希值。在步骤116，总签名请求528可以被计算出并 包括根哈希值530r和搜索树高度标记532。在图5D所示的例子中，搜索树高度 标记532为7，该“7”是搜索树524的高度，包括签名生成请求502中的树高 度标记506和显式长度标记526。

总签名请求528可以在服务提供商计算机被处理或可以被传送到与该服务 提供商计算机通信的父服务器。在流程100的步骤118，总签名700可以基于该 总签名请求528被生成并接收，如将参考图3进行进一步详细描述的一样。在 步骤118的流程的步骤302中，总签名请求528可以如前文所述的一样在本地 相同的计算机或在父服务器被接收。在步骤304检查搜索树高度标记532以确 定它是否超出了预先确定的高度限制。该高度限制可以被设置用以给客户端计 算机可以要求产生的签名的数量设置上限或因为效率、已有工作负荷或其它的 原因限制可以被处理的签名的数量。该高度限制也可以由父服务器分配到服务 提供商计算机以控制能够被服务提供商计算机卖出的服务的数量，例如，可以 被服务提供商计算机生成的签名的数量。当服务提供商计算机是由父服务器提 供的签名生成服务的经销商时这种情况可能发生。

在步骤304中如果搜索树高度标记532超出了预定的高度限制，则在步骤 310，该总签名请求528可以被忽略并不再处理。在这种情况下，总签名700和 无密钥数字多重签名800将不会生成。但是，在步骤304中如果搜索树高度标 记532小于或等于预先确定的高度限制，则在步骤306中生成总签名700。在步 骤306中，该搜索树高度标记532也可以被包括在搜索树524中。在步骤308 中，取决于哪个计算机处理该总签名请求528，该总签名700被在服务提供商计 算机内传送或被从父服务器传送到服务提供商计算机。

在一些实施例中，总签名700可以具有与搜索树524相同的哈希树结构。 但是，哈希函数被应用到搜索树524的节点的哈希值，包括根哈希值530r和搜 索树高度标记532，以生成总签名700。该总签名700还可以包括比将在无密钥 数字多重签名800中出现的哈希链更短的哈希链。用于生成总签名700的哈希 函数可以是与用于在搜索树524中产生哈希值的哈希函数相同或不同的确定的 函数。在该总签名700中还可以混入时间戳以标明该总签名700生成的日期和 时间。该总签名700可以响应总签名请求528的接收而被数字化地签署。应用 到该总签名请求528的数字签名可以基于公钥加密方案、公钥/私人密钥加密方 案或能证明签名的发布者的身份的任何其它方案。在总签名700中可以包括唯 一的序列号。在该总签名700中还可以包括隐含长度标记732并且当该总签名 700生成时该隐含长度标记732可以初始地被设为空白。当在该无密钥数字多重 签名800生成和/或验证时计数哈希计算步骤的数量时，该隐含长度标记732可 以被填充。该隐含长度标记732中填充的值可以与搜索树高度标记532比较以 确保客户端计算机发送的签名生成请求的数量在限度之内。在其它的实施例中， 总签名700可以包括具有时间戳和关于该哈希值何时和何地被公开的位置信息 的公开哈希值。例如，该时间戳和位置信息可以被混入该公开哈希值中。该公 开哈希值可以作为附加的数据结构被加入无密钥数字多重签名800中以实现该 无密钥数字多重签名800的更好的可提取性。

如果客户端计算机试图发送具有比在签名生成请求502中的树的实际高度 小的树高度标记506的签名生成请求502，必须被填充以帮助保证对客户端计算 机的签名生成的限制的隐含长度标记732将起作用。例如，如果客户端计算机 试图在该树中增加具有虚假高度的外部数据结构，这将是存在故意滥用签名生 成服务的证据。

无密钥数字多重签名800的生成在步骤120执行，将参考图4进行进一步 详细描述。在图4中所示的步骤120的流程的步骤402，签名生成请求502的最 小子树752可以被从总签名700中提取出。该最小子树752可以基于总签名700 中的树以及该树的对应特定签名生成请求502的特定的叶节点被提取。在图7A 和7B中所示的总签名700包括叶节点716、中间节点718和根节点720。签名 生成请求702和显式长度标记726被分配给并混入叶节点716。如前文所述的一 样，虽然该总签名700可以具有与搜索树524相同的哈希树结构，但是由于哈 希函数的应用、时间戳的加入和总签名700的数字签署，该总签名700的节点 的哈希值与搜索树524的节点的哈希值不同。

在图7B所示的例子中，显示了客户端计算机标识符AB的签名生成请求702： x(5)的最小子树752。该最小子树752包括位于从根节点720到对应于该签名生 成请求702：x(5)的叶节点716的直接路径上的节点。特别地，图7B中所示的 最小子树752包括中间节点718“AB”、“BB”、“＝AB”和“＝AB”。这些节点 也是该最小子树752的上下文中的搜索关键节点。该最小子树752还包括连接 到搜索关键节点718的兄弟节点754的哈希值756。该兄弟哈希链值756包括没 有位于从根节点720到叶节点716的直接路径上但是是总签名700的一部分的 兄弟节点754的哈希值。该兄弟哈希链值756是计算根哈希值730y所需要的。 在步骤404，该最小子树752可以被表示为哈希链850，比如像图8所示的无密 钥数字多重签名800中的一样。该无密钥数字多重签名800包括根哈希值730y、 隐含长度标记732和哈希链850。搜索树524的根哈希值530r等于根哈希值 730y。

在步骤406，检查哈希链850的节点，在步骤408，可以确定该被检查的节 点是否对应叶节点716。如果该节点对应一个叶节点716，则在步骤410，哈希 函数802被应用到签名生成请求702中的数据704、树高度标记706、客户端计 算机标识符708和显式长度标记726。在步骤412，结果的哈希值被分配到该节 点。在步骤408如果该节点没有对应一个叶节点，则在步骤418，该哈希函数 802被应用到搜索关键节点718的搜索关键标识符804(“＝AB”、“BB”和“AB”) 和连接到该非叶节点的左侧子节点和右侧子节点的哈希值，随后在步骤412，将 结果的哈希值分配给该非叶节点。在步骤414，如果在哈希链850中还留有另外 的节点，则步骤120的该流程返回到步骤406以计算剩余的节点的哈希值。该 哈希函数802可以是与用来计算在搜索树524和/或总签名700中的哈希值的哈 希函数相同或不同的确定的函数。在步骤414如果在哈希链850中没有剩余的 节点，则在步骤416中计算无密钥数字多重签名800。最后处理的节点是根节点 720，结果的根节点哈希值730y、隐含长度标记732和哈希链850构成了该无密 钥数字多重签名800。该隐含长度标记732可以通过计数该哈希链850中的步骤 的数量而计算出来。

在图8所示的例子中，完整的哈希链850从在图8底部的签名生成请求702： x(5)开始描述直到在图8顶部的根哈希值730。在哈希链850中的每个计算步骤， 从签名生成请求702：x(5)中的信息开始，哈希函数802被应用。在每个连续的 计算步骤，兄弟哈希值756、搜索关键标识符804和来自先前的哈希函数步骤的 结果哈希值806被哈希函数802混合，直到根哈希值730被计算出来。关于该 哈希链850的隐含长度标记732，在每个计算步骤，树的高度从签名生成请求 702中为1的显式长度标记726开始计算。在第一个计算步骤中，加上签名生成 请求702中的为2的树高度标记706产生为3的中间高度856。在图8所示的例 子中，对于每个连续的计算步骤，加上另外的为1的高度以产生连续的中间高 度856。该被加上的另外的高度可以是另外的值，取决于涉及的特定的节点是否 具有非0的显式长度标记726。当到达根节点时，在该哈希链850中步骤的总数 被置入隐含长度标记732中。在图8的例子中，该隐含长度标记被计算出为7。 这样，无密钥数字多重签名800为签名生成请求702中的一个签名生成请求生 成，并包含了根哈希值730、被填充了的隐含长度标记732和哈希链850。

在一些实施例中，哈希链的计算在无密钥数字签名800的验证过程中进行。 在图8中所示的哈希链850中的每个计算步骤中，当哈希函数被应用时，客户 端计算机标识符708可以与搜索关键标识符804比较，以保证签名生成请求702 处在总签名700的哈希树中最小子树752被从该处提取出的正确的位置。换句 话说，哈希链850中的计算步骤的顺序被检查以保证它与在分类数据库中的签 名生成请求702的顺序一致。如前文所述，签名生成请求702可以按客户端计 算机标识符708的字母顺序或按其它的顺序关系分组。在图8的例子中，搜索 关键标识符804“＝AB”和“AB”与客户端计算机标识符708“AB”比较以确定 它们是相同的。搜索关键标识符804“BB”被比较以检查它是否“大于”客户端 计算机标识符708“AB”。在这个例子中，基于它们的字母顺序，“BB”是“大 于”“AB”的。这也可以见于总签名700的哈希树中，在其中具有客户端计算 机标识符“BB”的签名生成请求702位于具有客户端计算机标识符“AB”的签 名生成请求702的右边。

在图中的任何流程描述或流程框应该被理解为表示包括一个或多个用于实 现流程中特定的逻辑功能或步骤的可执行指令的模块、程序段或代码部分，替 代的实现方式被包括在本发明的实施例的范围中，其中的各功能可以按照与前 文所示或讨论的顺序不同的顺序执行，包括大体上并行的或相反的顺序，取决 于涉及的功能，如将被本领域普通技术人员理解的那样。

应该强调，前文描述的本发明的实施例，特别是任何“优选的”实施例， 是可能的实现的实例，仅仅是在为了清楚地理解本发明的原理而描述。在不实 质性地背离本发明的精神和原理的情况下，还可以对本发明的前文所描述的实 施例做很多变更和修改。所有这些修改在这里都将被包括在本文和本发明中， 并受后续的权利要求保护。