用于通过一个为2的幂的公用指数证明一个实体的真实性和/或者一个消息的完整性的方法

用于通过一个为2的幂的公用指数证明一个实体的真 实性和/或者一个消息的完整性的方法

本发明涉及被设计成证明一个实体的真实性和/或者一个消息的完整性 和/或者真实性的方法、系统与设备。

其发明人为Louis Guillou和Jean-Jacques Quisquater的专利EP0 311 470 B1描述了这样一个方法。以后，通过术语“GQ专利”或者“GQ 方法”来引用该专利发明人的工作。以后，术语“GQ2”，或者“GQ2 发明”或者“GQ2技术”将被用于描述本发明。

根据这个GQ方法，称作一个“委托机构”的一个实体向称作一个“连 署人(witness)”的每一个实体分配一个身份，并且计算其RSA签名。在 一个客户定制的过程中，委托机构给这个连署人一个身份和签名。其后， 这个连署人进行如下的声明：“这是我的身份；我知道其RSA签名”。 这个连署人证明他知道其身份的RSA签名而不用透露这个签名。通过委 托机构分发的RSA公开标识密钥，称作一个“控制者”的一个实体确定 这个RSA签名与所声明的身份相应，而不需要了解其签名。使用这个GQ 方法的机制进行运行而“不需要传送密钥知识”。根据这个GQ方法， 这个连署人不知道RSA私有密钥。使用这个私有密钥，委托机构已经签 署了很多身份。

上面所描述的GQ技术使用了RSA技术。但是，虽然RSA技术确 实与模数n的因式分解相关，但是这个相关性不与其等价，并且实际上 有很大的差异，如可以从称作对实现了RSA技术的各种数字签名标准进 行乘法攻击的方法看出来。

GQ2技术的目的有两个方面：首先，是改善RSA技术的性能特征， 第二是避免RSA技术中固有的问题。对GQ2私有密钥的知识是与对模 数n地因式分解的知识等价的。对三元GQ2的一个攻击导致了对模数n 进行因式分解：这时是等价的。使用这个GQ2技术，就减少了签名的或 者自验证实体和减少了控制者实体的工作负担。由于在安全性和性能两 方面更好地利用了因式分解的问题，GQ2技术避免了RSA技术的缺点。

GQ方法实现了包括512比特或者更多比特的数字的模计算。这些计 算涉及基本上与增加到2¹⁶+1数量级的幂的相同大小的数。现在，已有 的微电子基础技术，特别是在银行卡的领域中，利用了单片自编程微处 理器而不需要算术协处理器。与在方法，例如GQ方法中所包括的乘法 算术应用相关的工作负荷导致了需要比较多的计算时间，在特定的情形 下，对使用银行卡来支付其购买的用户来说，这被证明是不方便的。这 里可能想到，在寻增加支付卡的安全性的过程中，银行权威机构已经 提出了特别难以解决的问题。实际上，需要解决两个明显存在矛盾的问 题：在一个方面，通过增加每一个卡的长度和并且为每一个卡提供不同 的密钥来增加安全性，而另一方面，避免所产生的工作负荷对用户产生 过度的计算时间。因为也必须考虑已有的基础设施和已有的微处理器部 件，所以这个问题就变得特别尖锐。

而GQ2技术提供了解决这个问题的一个方法，而增加了安全性。 方法

更特别地，本发明涉及被设计成来证明一个控制者实体的下述内容的 一个方法：

-一个实体的真实性和/或者

-与这个实体相关的一个信息M的完整性，

通过下面的这些参数或者这些参数的推导的全部或者一部分来建立这 个证据：

-m对私有值Q₁，Q₂，…，Q_m，和公开值G₁，G₂，…，G_m(m可 以是大于或者等于1)，

-一个公开模数n，由f个质数因子p₁，p₂，…，p_f(f可以是大于或 者大于2)的乘积组成，

-一个公开指数v。

所述模数，所述指数和所述值之间的关系如下面的关系式所显示的

G_i·Q_i^v≡1·mod n或者G_i≡Q_i^v mod n。

所述指数v是这样的

v＝2^k

其中k是比1大的一个安全参数。

所述公开值G_i是比f个质数因子p₁，p₂，…，p_f小的一个基数g_i的平 方g_i²。这个基数g_i是这样的：

两个方程：

x²≡g_i mod n和x²≡-g_i mod n 不可以在整数模数n环中被分解为x并且以使：

方程：

x^v≡g_i² mod n 可以在整数模数n环中被分解为x。

用下面的步骤，所述方法实现了称作一个连署人的一个实体。所述 连署人实体具有f个质数因子p_i和/或者质数因子的中国余数的参数和/或 者公开模数n和/或者m个私有值Q_i和/或者私有值Q_i与公开指数v的f.m 分量Q_i，j(Q_i，j＝Q_i mod p_j)。

这个连署人计算整数模数n环中的委托R。每一个委托被进行如下的 计算：

·或者通过执行这类型的操作：

R≡r^v mod n

其中r是一个随机数，以使0＜r＜n，

·或者

··或者通过执行下面类型的操作：

R_i≡r_i^v mod p_i

其中r_i是与质数p_i相关的一个随机数，以使0＜r_i＜p_i，每一个r_i属于 一个随机数值的集合{r₁，r₂，...，r_f}，

··然后通过应用中国余数方法。

这个连署人接收一个或者多个任务d。每一个任务d包括以后被称作 基本任务的m个整数d_i。这个连署人根据每一个任务d来计算一个响应 D，

·或者通过执行下面类型的操作：

D≡r.Q₁^d1.Q₂^d2....Q_m^dm mod n

·或者

··通过执行下面类型的操作：

D_i≡r_i.Q_i，1^d1.Q_i，2^d2....Q_i，m^dm mod p_i 并且然后通过应用中国余数方法。

这个方法使，有如任务d一样多的响应D，和一样多的委托R，每个 数字R，d，D的组形成了称作{R，d，D}的三元组。 证明一个实体真实性的情形

在一第一替代实施方式中，根据本发明的这个方法被设计成向被称作 控制者的一个实体证明被称作一个示范者(demonstrator)的一个实体的真 实性。所述示范者实体包括这个连署人。所述示范者和控制者实体均执 行下面的步骤：

·步骤1：委托R的动作

在每一个调用中，这个连署人通过使用上面所规定的过程来计算每一 个委托R。这个示范者向这个控制者发送每一个委托R的全部或者一部 分。

·步骤2：任务d的动作

在已经接收了每一个委托R的全部或者一部分后，这个控制者产生其 数目与委托R的数目相等的任务d，并且将这个任务d发送给示范者。

·步骤3：响应D的动作

这个连署人通过使用上面所规定的过程来从任务d计算出响应D。

·步骤4：检查的动作

这个示范者将每一个响应D发送给这个控制者。 第一个情形：示范者已经发送了每一个委托R的一部分

如果这个示范者已经发送了每一个委托R的一部分，具有m个公开 值G₁，G₂，…，G_m的控制者从每一个任务d和每一个响应D中计算出 一个重构的委托R′，这个重构的委托R′满足下面的关系：

R′≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R′≡D^v/G₁^d1.G₂^d2....G_m^dm.mod n

这个控制者确定每一个重构委托R′再生了已经被发送给它的每一个委 托R的全部或者部分。 第二个情形：示范者已经发送了每一个委托R的全部

如果示范者已经发送了每一个委托R的全部，具有m个公开值G₁， G₂，…，G_m的控制者确定每一个委托R满足下面的关系：

R≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R≡D^v/G₁^d1.G₂^d2....G_m^dm.mod n 证明这个消息的完整性的情形

在能够与一第一实施方式组合的一第二替代实施方式中，本发明的方 法被设计成向称作控制者实体的一个实体提供关于与称作一个示范者实 体的一个实体相关的一个消息M的完整性的证明。所述示范者实体包括 这个连署人。所述示范者和控制者实体执行下面的步骤：

·步骤1：委托R的动作

在每一个调用中，这个连署人通过使用上面所规定的过程来计算每一 个委托R。

·步骤2：任务d的动作

这个示范者使用其自变量是消息M和每一个委托R的全部或者一部 分的一个杂凑函数h来计算至少一个令牌T。这个示范者将这个令牌T 发送到这个控制者。在已经接收了一个令牌T后，这个控制者产生其数 目与委托R的数目相等的任务d，并且将这个任务d发送给示范者。

·步骤3：响应D的动作

这个连署人通过使用上面所规定的过程来从任务d计算出响应D。

·步骤4：检查的动作

这个示范者将每一个响应D发送给这个控制者。具有m个公开值G₁， G₂，…，G_m的控制者从每一个任务d和每一个响应D中计算出一个重构 的委托R′，这个重构的委托R′满足下面的关系：

R′≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R′≡D^v/G₁^d1.G₂^d2....G_m^dm.mod n

然后这个控制者使用其自变量是这个消息M和每一个重构委托R′的 全部或者一部分的杂凑函数h来重构这个令牌T′。然后，这个控制者确 定这个令牌T′与被发送的令牌T一致。 一个消息的数字签名和其真实性的证明

在可以与上面两个实施方式组合的一第三替代实施方式中，根据本发 明1的这个方法被设计成通过称作一个签名实体的一个实体来产生一个 消息M的数字签名。所述签名实体包括这个连署人。

签名操作

所述签名实体执行一个签名操作，以获得包括下述内容的一个被签名 消息：

-这个消息M，

-任务d和/或者委托R，

-响应D。

所述签名实体通过实施下面的步骤来执行签名操作：

·步骤1：委托R的动作

在每一个调用中，这个连署人通过使用上面所规定的过程来计算每一 个委托R。

·步骤2：任务d的动作

这个签名方使用其自变量是消息M和每一个委托R的一个杂凑函数 h来获得一个二进制序列。从这个二进制序列，这个签名方提取其数目与 委托R的数目相等的任务d。

·步骤3：响应D的动作

这个连署人通过使用上面所规定的过程来从任务d计算出响应D。 检查操作

为了证明这个消息M的真实性，称作一个控制者的一个实体检查被签 名的消息。具有这个被签名消息的所述控制者实体通过进行下面的过程 来执行一个检查操作。

·其中这个控制者具有委托R，任务d，响应D的情形

如果这个控制者具有委托R，任务d，响应D的情形，这个控制者确 定委托R，任务d，响应D满足下面的关系：

R≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R≡D^v/G₁^d1.G₂^d2....G_m^dm.mod n

然后这个控制者确定这个消息M，任务d，和委托R满足这个杂凑函 数：

d≡h(消息，R)

·其中这个控制者具有任务d和响应D的情形

如果这个控制者具有任务d，响应D的情形，这个控制者根据每一个 任务d和每一个响应D来重构满足下面的关系的委托R′：

R′≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R′≡D^v/G₁^d1.G₂^d2....G_m^dm.mod n

然后这个控制者确定这个消息M，任务d满足这个杂凑函数：

d≡h(消息，R′) ·其中这个控制者具有委托R和响应D的情形

如果这个控制者具有委托R和响应D的情形，这个控制者使用杂凑函 数并且重构d′

d′≡h(消息，R)

然后，这个控制者设备确定委托R，任务d′，响应D满足下面的关系：

R≡G₁^d’1.G₂^d’2....G_m^d’m.D^v mod n 或者关系：

R≡D^v/G₁^d’1.G₂^d’2....G_m^d’m.D^v.mod n

                        系统

本发明也涉及被设计成向一个控制者服务器证明下面内容的一个系 统：

-一个实体的真实性和/或者

-与这个实体相关的一个消息M的完整性，

通过下面的这些参数或者这些参数的推导的全部或者一部分来建立 这个证据：

-m对私有值Q₁，Q₂，…，Q_m，和公开值G₁，G₂，…，G_m(m可 以是大于或者等于1)，

-一个公开模数n，由所述f个质数因子p₁，p₂，…，p_f(f可以是大 于或者大于2)的乘积组成，

-一个公开指数v。

所述模数，所述指数和所述值之间的关系如下面的关系式所显示的

G_i·Q_i^v≡1·mod n或者G_i≡Q_i^v mod n。

所述指数v是这样的

v＝2^k

其中k是比1大的一个安全参数。

所述公开值G_i是比f个质数因子p₁，p₂，…，p_f小的一个基数g_i的平 方g_i²。这个基数g_i是这样的两个方程：

x²≡g_i mod n和x²≡-g_i mod n 不可以在整数模数n环中被分解为x并且以使方程：

x^v＝g_i² mod n 可以在整数模数n环中被分解为x。

所述系统包括特别被包括在一个数据库管理系统对象中的一个连署人 设备，例如，这个数据库管理系统的形式是一个基于微处理器的银行卡。 这个连署人设备包括带f个质数因子p_i和/或者质数因子的中国余数的参 数和/或者公开模数n和/或者m个私有值Q_i和/或者私有值Q_i与公开指 数v的f.m分量Q_i，j(Q_i，j≡Q_imod p_j)的一个存储区域。这个连署人设 备也包括：

-随机数值产生装置，以后被称作这个连署人设备的随机数值产生装 置，

-计算装置，以后被称作这个连署人设备计算委托R的装置。

这个计算装置计算整数模数n环中的委托R。每一个委托被进行如下 的计算：

·或者通过执行这类型的操作：

R＝r^v mod n

其中r是这个随机数值产生装置所产生的一个随机数，以使0＜r＜n，    ·或者

··或者通过执行下面类型的操作：

R_i＝r_i^v mod p_i

其中r_i是与质数p_i相关的一个随机数，以使0＜r_i＜p_i，每一个r_i属于 一个随机数值的集合{r₁，r₂，...，r_f}，然后通过应用中国余数方法。

这个连署人设备也包括：

-接收装置，以后被称作这个连署人设备接收任务d的装置，以接收 一个或者多个任务d；每一个任务d包括以后被称作基本任务的m个整 数d_i。

-计算装置，以后被称作这个连署人设备计算响应D的装置，以根据 每一个任务d来计算一个响应D，

·或者通过执行下面类型的操作：

D＝r.Q₁^d1.Q₂^d2....Q_m^dm mod n

·或者

··通过执行下面类型的操作：

D_i＝r_i.Q_i，1^d1.Q_i，2^d2....Q_i，m^dm mod p_i 并且然后通过应用中国余数方法。

这个连署人设备也包括发送装置，以发送一个或者多个委托R和一个 或者多个响应D。有如任务d一样多的响应D，和一样多的委托R，每 个数字R，d，D的组形成了称作{R，d，D}的三元组。 证明一个实体真实性的情形

在一第一替代实施方式中，根据本发明的这个系统被设计成证明被称 作控制者的一个实体和一个示范者的一个实体的真实性。

所述系统是这样的，以使它包括了与一个示范者实体相关的一个示范 者设备。所述示范者设备通过互连装置与这个连署人设备互连。在一个 数据库管理系统对象中，特别的，它的形式可能是逻辑微电路，例如其 形式是一个基于微处理器的银行卡的一个微处理器。

所述系统也包括与这个控制者实体相关的一个控制者设备。特别地， 所述控制者设备的形式可以是一个终端或者远程服务器。所述控制者设 备包括连接装置，包括其电气的连接，电磁的，光学的或者声学的连接， 特别是通过一个数据处理通信网络而连接到这个示范者设备。

所述系统被用于执行下面的步骤：

·步骤1：委托R的动作

在每一个调用中，这个连署人设备计算委托R的装置通过使用上面所 规定的过程来计算每一个委托R。这个连署人设备具有以后被称作这个 连署人设备发送装置的发送装置，以通过互连装置向这个示范者设备发 送每一个委托R的全部或者一部分。这个示范者设备也具有以后被称作 这个示范者设备发送装置的发送装置，以通过互连装置向这个控制者设 备发送每一个委托R的全部或者一部分。

·步骤2：任务d的动作

这个控制者设备包括任务产生装置，用于在已经接收了每一个委托R 的全部或者一部分后，产生其数目与委托R的数目相等的任务d。这个 控制者设备也包括以后被称作控制者的发送装置的发送装置，以通过互 连装置将这个任务d发送给示范者。

·步骤3：响应D的动作

这个连署人设备接收任务d的装置通过互连装置接收来自示范者设备 的每一个任务d。这个连署人设备计算响应D的装置通过使用上面所规 定的过程来从任务d计算出响应D。

·步骤4：检查的动作

这个示范者的发送装置将每一个响应D发送给这个控制者。这个控制 者设备也包括：

-计算装置，以后被称作控制者设备的计算装置，

-比较装置，以后被称作控制者设备的比较装置。 第一个情形：示范者已经发送了每一个委托R的一部分

如果这个示范者的发送装置已经发送了每一个委托R的一部分，具有 m个公开值G₁，G₂，…，G_m的控制者设备的计算装置从每一个任务d 和每一个响应D中计算出一个重构的委托R′，这个重构的委托R′满足下 面的关系：

R′≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R′≡D^v/G₁^d1.G₂^d2....G_m^dm.mod n

这个控制者确定每一个重构委托R′再生了已经被发送给它的每一个委 托R的全部或者部分。 第二个情形：示范者已经发送了每一个委托R的全部

如果示范者的发送装置已经发送了每一个委托R的全部，具有m个 公开值G₁，G₂，…，G_m的控制者设备的计算装置和比较装置确定每一个 委托R满足下面的关系：

R≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R≡D^v/G₁^d1.G₂^d2....G_m^dm.mod n 证明这个消息的完整性的情形

在能够与一第一实施方式组合的一第二替代实施方式中，根据本发 明的系统被设计成向称作控制者实体的一个实体提供关于与称作一个示 范者实体的一个实体相关的一个消息M的完整性的证明。所述系统是这 样的，它包括与示范者实体相关的一个示范者设备。所述示范者设备通 过互连装置与这个连署人设备互连。在一个数据库管理系统对象中，特 别的，它的形式可能是逻辑微电路，例如其形式是一个基于微处理器的 银行卡的一个微处理器。所述系统也包括与这个控制者实体相关的一个 控制者设备。特别地，所述控制者设备的形式可以是一个终端或者远程 服务器。所述控制者设备包括连接装置，包括其电气的连接，电磁的， 光学的或者声学的连接，特别是通过一个数据处理通信网络而连接到这 个示范者设备。 所述系统被用于执行下面的步骤：

·步骤1：委托R的动作

在每一个调用中，这个连署人设备计算委托R的装置通过使用上面所 规定的过程来计算每一个委托R。这个连署人设备具有以后被称作这个 连署人设备发送装置的发送装置，以通过互连装置向这个示范者设备发 送每一个委托R的全部或者一部分。

·步骤2：任务d的动作

这个示范者设备包括以后被称作示范者的计算装置的计算装置，这个 装置使用其自变量是消息M和每一个委托R的全部或者一部分的一个杂 凑函数h来计算至少一个令牌T。这个示范者设备也包括以后被称作示 范者的发送装置的发送装置，用于通过互连装置将每一个令牌T发送到 这个控制者设备。在已经接收了一个令牌T后，这个控制者设备也包括 任务产生装置，用于产生其数目与委托R的数目相等的任务d。这个控 制者设备也包括以后被称作控制者的发送装置的发送装置，用于通过互 连装置将这个任务d发送给示范者。

·步骤3：响应D的动作

这个连署人设备接收任务d的装置通过互连装置接收来自示范者设备 的每一个任务d。这个连署人设备的计算响应D的装置通过使用上面所 规定的过程来从任务d计算出响应D。

·步骤4：检查的动作

这个示范者的发送装置将每一个响应D发送给这个控制者。具有m 个公开值G₁，G₂，…，G_m的控制者设备也包括以后被称作控制者设备的 计算装置的计算装置，用于从每一个任务d和每一个响应D中计算出一 个重构的委托R′，这个重构的委托R′满足下面的关系：

R′≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R′≡D^v/G₁^d1.G₂^d2....G_m^dm.mod n

然后第二，通过使用其自变量是这个消息M和每一个重构委托R′的 全部或者一部分的杂凑函数h来重构这个令牌T′。

这个控制者设备也包括以后被称作控制者设备的比较装置的比较装 置，来将计算的这个令牌T′与被接收的令牌T进行比较。 一个消息的数字签名和其真实性的证明

在可以与上面两个实施方式组合的一第三替代实施方式中，根据本发 明的这个系统被设计成通过称作一个签名实体的一个实体来证明一个消 息M的数字签名，以后称作签名消息。这个被签名消息包括：

-这个消息M，

-任务d和/或者委托R，

-响应D。 签名操作

所述系统是这样的，它包括与这个签名实体相关的一个签名设备。所 述签名设备通过互连装置与这个连署人设备互连。特别地，其形式可以 是一个数据库管理系统对象中的逻辑微电路，例如是基于一个微处理器 的银行卡的一个微处理器。

所述系统被用于来执行下面的步骤：

·步骤1：委托R的动作

在每一个调用中，这个连署人设备计算委托R的装置通过使用上面所 规定的过程来计算每一个委托R。这个连署人设备具有以后被称作这个 连署人设备发送装置的发送装置，以通过互连装置向这个示范者设备发 送每一个委托R的全部或者一部分。

·步骤2：任务d的动作

这个签名设备包括以后被称作签名设备的计算装置的计算装置，它使 用其自变量是消息M和每一个委托R的一个杂凑函数h来计算一个二进 制序列，并且从这个二进制序列，这个签名方提取其数目与委托R的数 目相等的任务d。

·步骤3：响应D的动作

这个连署人设备接收任务d的装置通过互连装置接收来自签名设备的 每一个任务d。这个连署人设备的计算响应D的装置通过使用上面所规 定的过程来从任务d计算出响应D。

这个连署人设备包括以后被称作连署人设备的发送装置的发送装置， 通过互连装置将响应D发送到这个签名设备。 检查操作

为了证明这个消息M的真实性，称作一个控制者的一个实体检查被签 名的消息。

这个系统包括与这个控制者实体相关的一个控制者设备。特别地，所 述控制者设备的形式可以是一个终端或者远程服务器。所述控制者设备 包括连接装置，包括其电气的连接，电磁的，光学的或者声学的连接， 特别是通过一个数据处理通信网络而连接到这个签名设备。

与这个签名实体相关的签名设备包括以后被称作签名设备的发送装置 的发送装置，以用于通过连接装置将被签名消息发送到控制者设备。这 样，控制者设备具有包括下面的一个被签名消息：

-这个消息M，

-任务d和/或者委托R，

-响应D。

这个控制者设备包括：

-计算装置，以后被称作控制者设备的计算装置，

-比较装置，以后被称作控制者设备的比较装置。 ·其中这个控制者设备具有委托R，任务d，响应D的情形

如果这个控制者设备具有委托R，任务d，响应D的情形，这个控制 者设备的计算装置和比较装置确定委托R，任务d，响应D满足下面的 关系：

R≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R≡D^v/G₁^d1.G₂^d2....G_m^dm.mod n

然后这个控制者设备的计算装置和比较装置确定这个消息M，任务d， 和委托R满足这个杂凑函数：

d≡h(消息，R)

·其中这个控制者设备具有任务d和响应D的情形

如果这个控制者具有任务d，响应D的情形，这个控制者根据每一个 任务d和每一个响应D来重构满足下面的关系的委托R′：

R′≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R′≡D^v/G₁^d1.G₂^d2....G_m^dm.mod n

然后这个控制者确定这个消息M，任务d满足这个杂凑函数：

d≡h(消息，R′)

·其中这个控制者具有委托R和响应D的情形

如果这个控制者具有委托R和响应D的情形，这个控制者设备的计算 装置使用杂凑函数和被计算的d′，以使

d′≡h(消息，R)

然后，这个控制者设备的计算装置和比较装置确定委托R，任务d′， 响应D满足下面的关系：

R≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R≡D^v/G₁^d1.G₂^d2....G_m^dm.D^v.mod n

                          终端设备

本发明也涉及与一个实体相关的一个终端设备。特别地，这个终端设 备的形式是一个数据库管理系统对象，例如，其形式是一个基于微处理 器的银行卡中的一个微处理器。这个终端设备被设计成能够向一个控制 服务器证明下面的内容：

-一个实体的真实性和/或者

-与这个实体相关的一个消息M的完整性。

通过下面的这些参数或者这些参数的推导的全部或者一部分来建立这 个证据：

-m对私有值Q₁，Q₂，…，Q_m，和公开值G₁，G₂，…，G_m(m可 以是大于或者等于1)，

-一个公开模数n，由所述f个质数因子p₁，p₂，…，p_f(f可以是大 于或者大于2)的乘积组成，

-一个公开指数v。

所述模数，所述指数和所述值之间的关系如下面的关系式所显示的

G_i·Q_i^v≡1·mod n或者G_i≡Q_i^v mod n。

所述指数v是这样的

v＝2^k

其中k是比1大的一个安全参数。

所述公开值G_i是比f个质数因子p₁，p₂，…，p_f小的一个基数g_i的平 方g_i²。这个基数g_i是这样的两个方程：

x²≡g_i mod n和x²≡-g_i mod n 不可以在整数模数n环中被分解为x并且以使方程：

x^v＝g_i² mod n 可以在整数模数n环中被分解为x。

所述终端设备包括一个连署人设备。这个连署人设备包括带f个质数 因子p_i和/或者质数因子的中国余数的参数和/或者公开模数n和/或者m 个私有值Q_i和/或者私有值Q_i与公开指数v的f.m分量Q_i，j(Q_i，j≡Q_i mod p_j)的一个存储区域。

这个连署人设备也包括：

-随机数值产生装置，以后被称作这个连署人设备的随机数值产生装 置，

-计算装置，以后被称作这个连署人设备计算委托R的装置。这个计 算装置计算整数模数n环中的委托R。

每一个委托被进行如下的计算：

·或者通过执行这类型的操作：

R＝r^v mod n

其中r是这个随机数值产生装置所产生的一个随机数，以使0＜r＜n，

·或者

··或者通过执行下面类型的操作：

   R_i＝r_i^v mod p_i

其中r_i是与质数p_i相关的一个随机数，以使0＜r_i＜p_i，每一个r_i属于 随机数值产生装置所产生的一个随机数值的集合{r₁，r₂，...，r_f}，然后通过 应用中国余数方法。

这个连署人设备也包括：

-接收装置，以后被称作这个连署人设备接收任务d的装置，以接收 一个或者多个任务d；每一个任务d包括以后被称作基本任务的m个整 数d_i。

-计算装置，以后被称作这个连署人设备计算响应D的装置，以根据 每一个任务d来计算一个响应D，

·或者通过执行下面类型的操作：

D＝r.Q₁^d1.Q₂^d2....Q_m^dm mod n

·或者

··通过执行下面类型的操作：

D_i＝r_i.Q_i，1^d1.Q_i，2^d2....Q_i，m^dm mod p_i 并且然后通过应用中国余数方法。

所述连署人设备也包括发送装置，以发送一个或者多个委托R和一个 或者多个响应D。有如任务d一样多的响应D，和一样多的委托R，每 个数字R，d，D的组形成了称作{R，d，D}的三元组。 证明一个实体真实性的情形

在一第一替代实施方式中，根据本发明的这个终端设备被设计成证明 被称作控制者的一个实体和一个示范者的一个实体的真实性。

所述终端设备是这样的，以使它包括了与一个示范者实体相关的一个 示范者设备。所述示范者设备通过互连装置与这个连署人设备互连。在 一个数据库管理系统对象中，特别的，它的形式可能是逻辑微电路，例 如其形式是一个基于微处理器的银行卡的一个微处理器。

所述示范者设备也包括连接装置，包括其电气的连接，电磁的，光学 的或者声学的连接，特别是通过一个数据处理通信网络而连接到与控制 实体相关的这个控制者设备。特别地，所述控制者设备的形式可以是一 个终端或者远程服务器。

所述终端设备被用于执行下面的步骤：

·步骤1：委托R的动作

在每一个调用中，这个连署人设备计算委托R的装置通过使用上面所 规定的过程来计算每一个委托R。

这个连署人设备具有以后被称作这个连署人设备发送装置的发送装 置，以通过互连装置向这个示范者设备发送每一个委托R的全部或者一 部分。这个示范者设备也具有以后被称作这个示范者设备发送装置的发 送装置，以通过互连装置向这个控制者设备发送每一个委托R的全部或 者一部分。

·步骤2和3：任务d的动作，响应D的动作

这个连署人设备接收任务d的装置通过在控制者设备与示范者设备之 间的互连装置和通过在示范者设备和连署人设备之间的互连装置来接收 来自控制者设备的每一个任务d。这个连署人设备计算响应D的装置通 过使用上面所规定的过程来从任务d计算出响应D。

·步骤4：检查的动作

这个示范者的发送装置将每一个响应D发送给执行这个检查的这个控 制者。 证明这个消息的完整性的情形

在能够与一第一实施方式组合的一第二替代实施方式中，根据本发 明的终端设备被设计成向称作控制者实体的一个实体提供关于与称作一 个示范者实体的一个实体相关的一个消息M的完整性的证明。所述终端 设备是这样的，它包括与示范者实体相关的一个示范者设备。所述示范 者设备通过互连装置与这个连署人设备互连。在一个数据库管理系统对 象中，特别的，它的形式可能是逻辑微电路，例如其形式是一个基于微 处理器的银行卡的一个微处理器。所述示范者设备包括连接装置，包括 其电气的连接，电磁的，光学的或者声学的连接，特别是通过一个数据 处理通信网络而连接到与控制者实体相关的这个控制者设备。特别地， 所述控制者设备的形式可以是一个终端或者远程服务器。 所述终端设备被用于执行下面的步骤：

·步骤1：委托R的动作

在每一个调用中，这个连署人设备计算委托R的装置通过使用上面所 规定的过程来计算每一个委托R。这个连署人设备具有以后被称作这个 连署人设备发送装置的发送装置，以通过互连装置向这个示范者设备发 送每一个委托R的全部或者一部分。

·步骤2和3：任务d的动作，响应D的动作

这个示范者设备包括以后被称作示范者的计算装置的计算装置，这个 装置使用其自变量是消息M和每一个委托R的全部或者一部分的一个杂 凑函数h来计算至少一个令牌T。这个示范者设备也包括以后被称作示 范者的发送装置的发送装置，用于通过互连装置将每一个令牌T发送到 这个控制者设备。

在已经接收了一个令牌T后，所述控制者也产生其数目与委托R的数 目相等的任务d。

这个连署人设备接收任务d的装置通过在控制者设备与示范者设备之 间的互连装置和通过在示范者设备和连署人设备之间的互连装置来接收 来自控制者设备的每一个任务d。这个连署人设备的计算响应D的装置 通过使用上面所规定的过程来从任务d计算出响应D。

·步骤4：检查的动作

  这个示范者的发送装置将每一个响应D发送给执行检查的这个控 制者设备。 一个消息的数字签名和其真实性的证明

在可以与上面第一和第二两个实施方式组合的一第三替代实施方式 中，根据本发明的这个终端设备被设计成通过称作一个签名实体的一个 实体来产生一个消息M的数字签名，以后称作一个签名消息。这个被签 名消息包括：

-这个消息M，

-任务d和/或者委托R，

-响应D。

所述终端设备是这样的，它包括与这个签名实体相关的一个签名设备。 所述签名设备通过互连装置与这个连署人设备互连。特别地，其形式可 以是一个数据库管理系统对象中的逻辑微电路，例如是基于一个微处理 器的银行卡的一个微处理器。所述示范者设备包括连接装置，包括其电 气的连接，电磁的，光学的或者声学的连接，特别是通过一个数据处理 通信网络而连接到与控制者实体相关的这个控制者设备。特别地，所述 控制者设备的形式可以是一个终端或者远程服务器。 签名操作

所述终端被用于来执行下面的步骤：

·步骤1：委托R的动作

在每一个调用中，这个连署人设备计算委托R的装置通过使用上面所 规定的过程来计算每一个委托R。这个连署人设备具有以后被称作这个 连署人设备发送装置的发送装置，以通过互连装置向这个签名设备发送 每一个委托R的全部或者一部分。

·步骤2：任务d的动作

这个签名设备包括以后被称作签名设备的计算装置的计算装置，它使 用其自变量是消息M和每一个委托R的全部或者部分的一个杂凑函数h 来计算一个二进制序列，并且从这个二进制序列，这个签名设备提取其 数目与委托R的数目相等的任务d。

·步骤3：响应D的动作

这个连署人设备接收任务d的装置通过互连装置接收来自签名设备的 每一个任务d。这个连署人设备的计算响应D的装置通过使用上面所规 定的过程来从任务d计算出响应D。

这个连署人设备包括以后被称作连署人设备的发送装置的发送装置， 通过互连装置将响应D发送到这个签名设备。

                         控制者设备

本发明也涉及与一个控制者设备。特别地，这个控制者设备的形式是 与一个控制者实体相关的一个终端或者远程服务器。这个控制者设备被 设计成能够检查下面的内容：

-一个实体的真实性和/或者

-与这个实体相关的一个消息M的完整性。

通过下面的这些参数或者这些参数的推导的全部或者一部分来建立这 个证据：

-m对公开值G₁，G₂，…，G_m(m可以是大于或者等于1)，

-一个公开模数n，由所述f个质数因子p₁，p₂，…，p_f(f可以是大 于或者大于2)的乘积组成，它对控制者设备和相关的控制实体来说是未 知的，

-一个公开指数v。

所述模数，所述指数和所述值之间的关系如下面的关系式所显示的

G_i·Q_i^v≡1·mod n或者G_i≡Q_i^v mod n。

所述Q_i指定对控制者设备未知的、与公开值G_i相关的一个私有值，

所述指数v是这样的

v＝2^k

其中k是比1大的一个安全参数。

所述公开值G_i是比f个质数因子p₁，p₂，…，p_f小的一个基数g_i的平 方g_i²。这个基数g_i是这样的两个方程：

x²≡g_i mod n和x²≡-g_i mod n 不可以在整数模数n环中被分解为x并且以使方程：

x^v＝g_i² mod n 可以在整数模数n环中被分解为x。 证明一个实体真实性的情形

在一第一替代实施方式中，根据本发明的这个控制者设备被设计成证 明被称作控制者的一个实体和一个示范者的一个实体的真实性。

所述控制者设备包括连接装置，包括其电气的连接，电磁的，光学的 或者声学的连接，特别是通过一个数据处理通信网络而连接到与示范者 实体相关的这个示范者设备。

所述控制者设备被用于执行下面的步骤：

·步骤1和2：委托R的动作，任务d的动作

所述控制者设备也具有用于通过互连装置接收来自示范者设备的委托 R的全部或者部分的装置。

这个控制者设备也具有任务产生装置，用于在接收每一个委托R的全 部或者部分后，产生数目与委托R的数目相等的任务d，每一个任务d 包括m个整数di，以后被称作基本任务。

这个控制者设备具有以后被称作这个控制者设备发送装置的发送装 置，以通过互连装置向这个示范者设备发送任务d。

·步骤3和4：响应D的动作，检查的动作

这个控制者设备也包括：

-用于通过互连装置从示范者设备接收响应D的装置，

-计算装置，以后被称作控制者设备的计算装置，

-比较装置，以后被称作控制者设备的比较装置。 第一个情形：示范者已经发送了每一个委托R的一部分

如果这个示范者的接收装置已经接收了每一个委托R的一部分，具有 m个公开值G₁，G₂，…，G_m的控制者设备的计算装置从每一个任务d 和每一个响应D中计算出一个重构的委托R′，这个重构的委托R′满足下 面的关系：

R′≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R′≡D^v/G₁^d1.G₂^d2....G_m^dm.mod n

这个控制者设备的比较装置将每一个重构委托R′与所接收的的每一个 委托R的全部或者部分进行比较。 第二个情形：示范者已经发送了每一个委托R的全部

如果示范者设备的发送装置已经发送了每一个委托R的全部，具有m 个公开值G₁，G₂，…，G_m的控制者设备的计算装置和比较装置确定每一 个委托R满足下面的关系：

R≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R≡D^v/G₁^d1.G₂^d2....G_m^dm.mod n 证明这个消息的完整性的情形

在能够与一第一实施方式组合的一第二替代实施方式中，根据本发 明的控制者设备被设计成向称作控制者实体的一个实体提供关于与称作 一个示范者实体的一个实体相关的一个消息M的完整性的证明。

所述控制者设备包括连接装置，包括其电气的连接，电磁的，光学的 或者声学的连接，特别是通过一个数据处理通信网络而连接到这个示范 者设备。 所述系统被用于执行下面的步骤：

·步骤1和2：委托R的动作，任务d的动作

所述控制者设备也具有用于通过互连装置接收来自示范者设备的令牌 T的装置。控制者设备具有任务产生装置，在已经接收到了令牌T后， 用于产生其数目与委托R数目相等的任务d，每一个任务d包括以后被 称作基本任务的m个整数di。这个控制者设备也包括以后被称作控制者 的发送装置的发送装置，用于通过互连装置将这个任务d发送给示范者。

·步骤3和4：响应D的动作，检查的动作

这个控制者设备也包括用于通过互连装置接收来自示范者设备的响应 的装置。具有m个公开值G₁，G₂，…，G_m的控制者设备也包括以后被 称作控制者设备的计算装置的计算装置，用于从每一个任务d和每一个 响应D中计算出一个重构的委托R′，这个重构的委托R′满足下面的关系：

R′≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R′≡D^v/G₁^d1.G₂^d2....G_m^dm.mod n

然后第二，通过使用其自变量是这个消息M和每一个重构委托R′的 全部或者一部分的杂凑函数h来重构这个令牌T′。

这个控制者设备也包括以后被称作控制者设备的比较装置的比较装 置，来将计算的这个令牌T′与被接收的令牌T进行比较。 一个消息的数字签名和其真实性的证明

在可以与上面两个实施方式组合的一第三替代实施方式中，根据本发 明的这个控制者设备被设计成通过称作一个控制者的一个实体来检查一 个签名的消息以证明这个消息M的真实性。

这个被签名消息被与具有一个杂凑函数h(消息，R)的一个签名实 体相关的一个签名设备所发送，它包括：

-这个消息M，

-任务d和/或者委托R，

-响应D。 检查操作

所述控制者设备包括连接装置，包括其电气的连接，电磁的，光学的 或者声学的连接，特别是通过一个数据处理通信网络而连接到与这个签 名实体相关的一个签名设备。所述控制者设备通过互连装置接收来自签 名设备的签名消息。

这个控制者设备包括：

-计算装置，以后被称作控制者设备的计算装置，

-比较装置，以后被称作控制者设备的比较装置。

·其中这个控制者设备具有委托R，任务d，响应D的情形

如果这个控制者设备具有委托R，任务d，响应D的情形，这个控制 者设备的计算装置和比较装置确定委托R，任务d，响应D满足下面的 关系：

R≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R≡D^v/G₁^d1.G₂^d2....G_m^dm.mod n

然后这个控制者设备的计算装置和比较装置确定这个消息M，任务d， 和委托R满足这个杂凑函数：

d≡h(消息，R)

·其中这个控制者设备具有任务d和响应D的情形

如果这个控制者具有任务d，响应D的情形，这个控制者的计算装置 根据每一个任务d和每一个响应D来计算满足下面的关系的委托R′：

R′≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R′≡D^v/G₁^d1.G₂^d2....G_m^dm.mod n

然后这个控制者设备的计算和比较装置确定这个消息M，任务d满足 这个杂凑函数：

d≡h(消息，R′)

·其中这个控制者具有委托R和响应D的情形

如果这个控制者具有委托R和响应D的情形，这个控制者设备的计算 装置使用杂凑函数和被计算的d′，以使

d′≡h(消息，R)

然后，这个控制者设备的计算装置和比较装置确定委托R，任务d′， 响应D满足下面的关系：

R≡G₁^d1.G₂^d2....G_m^dm.D^v mod n 或者关系：

R≡D^v/G₁^d1.G₂^d2....G_m^dm.D^v.mod n 描述

可以回忆一下GQ技术的目的：它是对实体和相关的消息和消息的数 字签名的真实性进行动态认证。

GQ技术的标准版本利用了RSA技术。但是，尽管RSA技术确实决 定于因式分解，但是这个相关性不是等价的，并且离等价非常远，这可 以从对实现了RSA技术的各种数字签名标准进行的攻击，称作乘法攻击 中可以看出来。

在GQ2技术的上下文中，本发明的当前部分与动态鉴权和数字签名 的上下文中的GQ2密钥集合使用更具体地相关。GQ2技术不使用RSA 技术。这个目标有两个方面：第一，是改进了RSA技术的性能，第二是 避免RSA技术所固有的问题。GQ2私有密钥是模数n的因式分解。任何 对GQ2三元组的攻击均是对模数n的因式分解：这时，它们是等价的。 使用了GQ2技术，减少了进行签名或者被进行鉴权的实体和进行检查的 实体的工作负荷。尽管改进了对因式分解问题的使用，但是就安全性和 性能来说，GQ2技术可以与RSA技术相比。

GQ2技术使用了一个或者多个比1大的小整数，例如m个称作基数 和参考g_i的小整数(m≥1)。因为基数是固定的，并且从g_i到g_m，其中 m＞1，按照如下的方法来选择一个公开证实密钥<v，n>。公开证实指数v 是2_k，其中k是比1大的一个小整数(k≥2)。公开模数n是至少两个比基 数大的质因数的乘积，例如称作p_i，从p₁到p_f的f个质因素(f≥2)。这 样选择f个质因数，以使公开模数n对从g₁到g_m的每一个m基数来说均 具有下面的特性。

-首先，方程(1)和(2)不能够在整数模数n的环中以x进行分解， 即，g_i和-g_i是两个非2次的余数(mod n)。

X²≡g_i(mod n)       (1)

X²≡-g_i(mod n)      (2)

-第二，方程(3)可以在整数模数n的环中以x进行分解。

X^2k≡g_i²(mod n)     (3)

因为公开证实密钥<v，n>是根据从g₁到g_m，并且m≥1的基数来确定 的，每一个基数g_i决定了包括一个公开值G_i和和一个私有值Qi的一对 值GQ2：有m对，称作G₁Q₁到G_mQ_m。公开值G_i是基数g_i²的平方：得 出G_i＝g_i²。私有值Qi是方程(3)的解中的一个或者这样一个解的倒数(mod n)。

正如模数n可以被分解为f个质因子，整数模数n的环被分解为f个 Galois伽罗华域，从CG(p₁)到CG(p_f)。这里，是方程(1)(2) 和(3)在CG(p_i)上的投影。

X²≡g_i(mod p_i)      (1.a)

X²≡-g_i(mod p_j)     (2.a)

X^2k≡g_i²(mod p_j)    (3.a)

每一个私有值Q_i可以被唯一地表示为f个私有分量，每一个质因子为 一个分量：Q_i，j≡Q_i(mod p_j)。每一个私有分量Q_i，j是方程(3.a)的一个解， 或者是这样一个解的倒数(mod p_i)。在已经计算出了每一个方程(3.a) 所有可能的解后，中国余数技术根据f个分量Q_i，1到Q_i，f建立每一个私有 值Qi的所有可能值：Qi＝中国余数(Q_i，1，Q_i，2，…Q_i，f)，以获得方程(3) 所有可能的解。

下面是中国余数技术：假设有两个互为质数的正整数a和b，以使0＜a ＜b，并且有两个分量X_a，从0到a-1和从Xb，从0到b-1。需要确定 X＝中国余数(Xa，Xb)，即从0到a.b-1的唯一数X，以使Xa≡X(mod a) 和Xb≡X(mod b)。下面是中国余数的参数：α≡{b(mod a)}^-1(mod a)。下 面是中国余数的操作：ε≡Xb(mod a)；δ＝Xa-ε；如果δ是负的，用δ+a替 代δ；γ≡α.δ(mod a)；X＝γ.b+Xb。

当以增加的顺序来组织质数因子时，从最小的p₁到最大的p_f，中国余 数参数可以如下(有它们中的f-1个，即，比质数因子数少1个)。第一 中国余数参数是α≡{p₂(mod p₁)}^-1(mod p₁)。第二中国余数参数是β≡{p₁·p₂ (mod p₃)}^-1(mod p₃)。第i个中国余数参数是λ≡{p₁·p₂…p_i-1(mod p_i)}^-1(mod p_i)。等等。最后，在f-1个中国余数的运算中，使用第一参数获得了一第 一结果(mod p₂乘以p₁)，并且使用第二参数获得了第二结果(mod p₁·p₂ 乘以p₃)，等等，直到结果(mod p₁·p₂…p_f-1乘以p_f)，即(mod n)。

有几个可能的关于私有密钥GQ2的描述，它表示私有密钥GQ2的多 态的特征。各种描述证明是等价的：它们均等于模数n的因式分解，这 是真正的私有GQ2密钥。如果这个描述确实影响了签名实体或者自鉴权 实体的行为，它就不影响控制者实体的行为。

这里有3个主要的关于GQ2私有密钥的描述。

1)GQ技术中的标准表示包括了保存m个私有值Qi和公开证实密钥＜v， n＞；在GQ2中，这个描述是可以与下面2个相比的。2)就工作负荷来说 最佳的表示包括保存公开指数v，f个质数因子pj，m.f私有分量Qij和 中国余数的f-1个参数。3)就私有密钥来说最佳的表示包括保存公开指数 v，m个基数gi和f个质数因子pj，然后通过建立m个私有值Qi和模数 n来返回到第一描述，或者通过建立m.f私有分量Qi，j和中国余数的f-1 个参数来返回到第二描述，开始每一个使用。

签名实体或者自鉴权实体均可以使用相同的基数。除非有其它指定， 从g1到gm的m个基数然后可以方便地是m个第一质数。

因为动态鉴权机制或者数字签名机制的安全性与模数分解的知识等 价，所以GQ2基数不能够被用于使用相同的模数简单地识别两个实体。 一般来说，每一个对自己进行鉴权或者进行签名的实体均有其自己的GQ2 模数。但是，有可能使用4个质数因子来规定GQ2模数，其中两个是被 一个实体已知的，而另外两个是被另一个实体已知的。

这里，使用k＝6的一第一GQ2密钥集合，可以给出v＝64，m＝-3， 给出3个基：g1＝3，g2＝5，g3＝7，并且f＝3，即具有3个质数因子的一个 模数：两个与3同余(mod 4)一个与5同余(mod 8)。必须注意，g＝ 2是与5同余(mod 8)的一个质数因子不兼容的。 p1＝03CD2F4F21E0EAD60266D5CFCEBB6954683493E2E833 p2＝0583B097E8D8D777BAB3874F2E76659BB614F985EC1B p3＝0C363CD93D6B3FEC78EE13D7BE9D84354B8FDD6DA1FD n＝p1.p2.p3＝FFFF81CEA149DCF2F72EB449C5724742FE2A3630D9 02CC00EAFEE1B957F3BDC49BE9CBD4D94467B72AF28CFBB26144 CDF4BBDBA3C97578E29CC9BBEE8FB6DDDD Q1，1＝0279C60D216696CD6F7526E23512DAE090CFF879FDDE Q2，1＝7C977FC38F8413A284E9CE4EDEF4AEF35BF7793B89 Q3，1＝6FB3B9CO5A03D7CADA9A3425571EF5ECC54D7A7B6F Q1，2＝0388EC6AA1E87613D832E2B80E5AE8C1DF2E74BFF502 Q2，2＝04792CE70284D16E9A158C688A7B3FEAF9C40056469E Q3，2＝FDC4A8E53E185A4DA793E93BEE5C636DA731BDCA4E Q1，3＝07BC1AB048A2EAFDAB59BD40CCF2F657AD8A6B573BDE Q2，3＝0AE8551E116A3AC089566DFDB3AE003CF174FC4E4877 Q3，3＝01682D490041913A4EA5B80D16B685E4A6DD88070501 Q1＝D7E1CAF28192CED6549FF457708D50A7481572DD5F2C335D8 C69E22521B510B64454FB7A19AEC8D06985558E764C6991B05FC2A C74D9743435AB4D7CF0FF6557 Q2＝CB1ED6B1DD649B89B9638DC33876C98AC7AF689E9D1359E4 DB17563B9B3DC582D5271949F3DBA5A70C108F561A274405A5CB8 82288273ADE67353A5BC316C093 Q3＝09AA6F4930E51A70CCDFA77442B10770DD1CD77490E3398A AD9DC50249C34312915E55917A1ED4D83AA3D607E3EB5C8B197 697238537FE7A0195C5E8373EB74D 下面是第二GQ2密钥集合，其中k＝9，即，v＝512，m＝2，即，两个基数： g1＝2，g2＝3，和f＝3，给出与3同余(mod 4)的3个质数因子的一个模数。 p1＝03852103E40CD4F06FA7BAA9CC8D5BCE96E3984570CB p2＝062AC9EC42AA3E688DC2BC871C8315CB939089B61DD7 p3＝0BCADEC219F1DFBB8AB5FE808A0FFCB53458284ED8E3 n＝p1.p2.p3＝FFFF5401ECD9E537F167A80C0A9111986F7A8EBA4D 6698AD68FF670DE5D9D77DFF00716DC7539F7CBBCF969E73A0C49 761B276A8E6B6977A21D51669D039F1D7 Q1，1＝0260BC7243C22450D566B5C6EF74AA29F2B927AF68E1 Q2，1＝0326C12FC7991ECDC9BB8D7C1C4501BE1BAE9485300E Q1，2＝02D0B4CC95A2DD435D0E22BFBB29C59418306F6CD00A Q2，2＝O45ECB881387582E7C556887784D2671CA118E22FCF2 Q1，3＝B0C2B1F808D24F6376E3A534EB555EF54E6AEF5982 Q2，3＝0AB9F81DF462F58A52D937E6D81F48FFA4A87A9935AB Q1＝27F7B9FC82C19ACAE47F3FE9560C3536A7E90F8C3C51E13C 35F32FD8C6823DF753685DD63555D2146FCDB9B28DA367327DD6 EDDA092D0CF108D0AB708405DA46 Q2＝230D0B9595E5AD388F1F447A69918095EBFB05910582E5BA64 9C94B0B2661E49DF3C9B42FEF1F37A7909B1C2DD54113ACF87C6 F11F19874DE7DC5D1DF2A9252D 动态鉴权

动态鉴权机制被设计成向称作一个控制者的实体证明称作一个示范者 的另一个实体的真实性和一个可能的相关消息M的真实性，以使这个控 制中可以确认它是真正的示范者，并且视情况而定，仅该示范者和这个 示范者在说相同的消息M。相关的消息M是可选的。这意味着它可以是 空的。

动态鉴权机制是4个动作的序列：委托的动作，任务的动作，和响应 的动作与检查的动作。示范者完成委托和响应的动作。控制者完成任务 和控制的动作。

在示范者内部，可能隔离一个连署人，以隔离最敏感的参数和示范者 的功能，即委托和响应的产生。这个连署人具有参数k和私有密钥GQ2， 即根据上面所描述的3个中的一个的模数n的因式分解：·f个质数因 子和m个基数，·m.f私有分量，f个质数因子和f-1个中国余数参数，·m 个私有值和模数n。

这个连署人可能对一个部分的实施方式作出响应，例如，∝连接到形 成整个示范者的一个PC的一个芯片卡，或者再∝在一个PC内的特殊保 护程序，或者再，∝一个智能卡内的特殊保护程序。这样被隔离的这个连 署人与下面在一个签名实体内所定义的连署人类似。在机制的每一个执 行阶段，这个连署人产生一个或者多个委托R，并且然后，产生与任务d 的数目一样多的响应D。每一个集合{R，d，D}是一个GQ2三元组。

除了包括这个连署人，示范者也具有一个杂凑函数和一个消息M，如 果需要的话。

这个控制者具有模数n和参数k与m；如果需要，它也具有相同的杂 凑函数和一个消息M。这个控制者能够从任何任务d和任何响应D中重 构一个委托R′。参数k和m告知这个控制者。如果不能够指示任何相反 的，这从g1到gm的m个基数是m个第一质数。每一个任务d必须具 有m个基本任务，称作从d1到dm：每一个基数一个。这个从d1到dm 的基本任务的值可能是0到2^k-1-1中的一个值(v/2到v-1的值没有被使 用)。典型地，每一个任务被用m乘以k-1个比特进行编码(不是m乘 以k个比特)。例如，k＝6，m＝3，并且基数为3，5，7，每一个任务具有 15比特并且在两个字节上被发送；对k＝9，m＝2，和基数为2和3，每一个 任务具有16比特并且在两个字节上被发送。当(k-1).m个可能的任务也 是可能时，值(k-1).m确定每一个GQ2三元组所提供的安全性：由定义 可知为不知道模数n的因式分解的一个冒名顶替者成功的可能性为2^(k-1).m 中仅有一次。当(k-1).m等于15到20时，一个三元组就足以提供合理的 动态鉴权。为了实现任何安全级别，可能并行产生三元组。也可能依次 产生，即重复执行机制。

1)委托的动作包括下面的操作：

当这个连署人具有从Q1到Qm的m个私有值和模数n时，它随机地 和私有地产生一个或者多个随机数值r(0＜r＜n)；然后，通过k次连续平 方(mod n)操作，它将每一个随机数值r转换为一个委托R。

R≡r^v(mod n)

这里是k＝6的一个密钥集合的示例。

r＝ B8AD426C1A10165E94B894AC2437C1B1797EF562CFA53A4AF8 43131FF1C89CFDA131207194710EF9C010E8F09C60D9815121981260 919967C3E2FB4B4566088E R＝FFDD736B666F41FB771776D9D50DB7CDF03F3D976471B25C56 D3AF07BE692CB1FE4EE70FA77032BECD8411B813B4C21210C6B04 49CC4292E5DD2BDB00828AF18

当这个连署人具有从p1到pf的f个质数因子和m.f个私有分量Qij 时，它随机地和私有地产生f个随机数值的一个或者多个集合：每一个集 合中，一个质数因子pi具有一个随机数值ri(0＜ri＜pi)；然后，通过k次 连续的平方操作(mod pi)，它将每一个随机数值ri转换为一个委托的分 量Ri。

R_i≡r_i^v(mod p_i)

这里是k＝9的一第二密钥集合的示例。 r1＝B0418EABEBADF0553A28903F74472CD49DD8C82D86 R1＝022B365F0BEA8E157E94A9DEB0512827FFD5149880F1 r2＝75A8DA8FE0E60BD55D28A218E31347732339F1D667 R2＝057^E43A242C485FC20DEEF291C774CF1B30F0163DEC2 r3＝0D74D2BDA5302CF8BE2F6D406249D148C6960A7D27 R3＝06^E14C8FC4DD312BA3B475F1F40CF01ACE2A88D5BB3C

对每一个f委托分量的集合，这个连署人根据中国余数技术建立一个 委托。委托的数量与随机数值的集合的数量相同。

R＝中国余数(R1，R2，...，Rj) R＝28AA7F12259BFBA81368EB49C93EEAB3F3EC6BF73B0EBD7 D3FC8395CFA1AD7FC0F9DAC169A4F6F1C46FB4C3458D1E37C9 9123B56446F6C928736B17B4BA4A529

在两个情形下，示范者向这个控制者发送每一个委托R的全部或者部 分，或者通过对每一个委托R进行杂凑运算而获得的一个杂凑代码H和 一个消息M中的至少一个。 2)任务的动作包括随机地产生一个或者多个任务d，每一个任务d包括m 个基本任务d1/d2/.../dm；每一个基本任务di的值是0到v/2-1中的一个。

d＝d1/d2/.../dm 这里是k＝6，m＝3的第一密钥集合的示例。 d1＝10110＝22＝’16’；d2＝00111＝7；d3＝00010＝2 d＝0‖d1‖d2‖d3＝0101100011100010＝58E2。

这里是k＝9，m＝2的第二密钥集合的示例。

d＝d1‖d2＝58E2，即，十进制表示为88和226

这个控制者向示范者发送每一个任务d。 3)响应的动作具有下面的操作。

当这个连署人具有从Q1到Qm的m个私有值和模数n时，它使用委 托动作中的每一个随机数值r和根据基本任务的私有值来计算一个或者 多个响应D。

X≡Q₁^d1.Q₂^d2...Q_m^dm(mod n)

D≡r.X(mod n)

这里是第一密钥集合的示例。 D＝FF257422ECD3C7A03706B9A7B28EE3FC3A4E974AEDCDF386 5EEF38760B859FDB5333E904BBDD37B097A989F69085FE8EF6480 A2C6A290273479FEC9171990A17

当这个连署人具有从pi到pf的f个质数因子和m.f个私有分量Qi，j 时，它使用委托动作中每一个随机数值的集合来计算一个或者多个f个响 应分量的集合：每一个响应分量的集合中每一个质数因子有一个分量。

X_i≡Q₁^d1.Q₂^d2...Q_m，i^dm(mod p_i)

D_i≡r_i.X_i(mod p_i)

这里是第二密钥集合的示例。 D₁＝r₁.Q_1，1^d1.Q_2，1^d2(mod p1)＝ O2660ADF3C73B6DC15E196152322DDE8EB5B35775E38 D₂＝r₂.Q_1，2^d1.Q_2，2^d2(mod p2)＝ 04C15028E5FD1175724376C11BE77052205F7C62AE3B D₃＝r₃.Q_1，3^d1.Q_2，3^d2(mod p3)＝ 0903D20D0C306C8EDA9D8FB5B3BEB55E061AB39CCF52

对每一个响应分量的集合，这个连署人根据中国余数技术产生一个响 应。响应的数目与任务的数目相等。

D＝中国余数(D1，D2，...，Df) D＝85C3B00296426E97897F73C7DC6341FB8FFE6E879AE12EF1F36 4CBB55BC44DEC437208CF530F8402BD9C511F5FB3B3A309257A00 195A7305C6FF3323F72DC1AB

在这两个情形下，示范者向控制者发送每一个响应D。 4)检查动作包括确定每一个三元组{R，d，D}证实关于一个非零值的下面 类型的方程， <math> <mrow> <mi>R</mi> <mo>.</mo> <munderover> <mi>&Pi;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>m</mi> </munderover> <msubsup> <mi>G</mi> <mi>i</mi> <mi>di</mi> </msubsup> <mo>&equiv;</mo> <msup> <mi>D</mi> <msup> <mn>2</mn> <mi>k</mi> </msup> </msup> <mrow> <mo>(</mo> <mi>mod</mi> <mi>n</mi> <mo>)</mo> </mrow> </mrow> </math> 或者 <math> <mrow> <mi>R</mi> <mo>&equiv;</mo> <msup> <mi>D</mi> <msup> <mn>2</mn> <mi>k</mi> </msup> </msup> <mo>.</mo> <munderover> <mi>&Pi;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>m</mi> </munderover> <msubsup> <mi>G</mi> <mi>i</mi> <mi>di</mi> </msubsup> <mrow> <mo>(</mo> <mi>mod</mi> <mi>n</mi> <mo>)</mo> </mrow> </mrow> </math> 或者在建立每一个委托中：没有应当为零。 <math> <mrow> <msup> <mi>R</mi> <mo>&prime;</mo> </msup> <mo>&equiv;</mo> <msup> <mi>D</mi> <msup> <mn>2</mn> <mi>k</mi> </msup> </msup> <mo>/</mo> <munderover> <mi>&Pi;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>m</mi> </munderover> <msubsup> <mi>G</mi> <mi>i</mi> <mi>di</mi> </msubsup> <mrow> <mo>(</mo> <mi>mod</mi> <mi>n</mi> <mo>)</mo> </mrow> </mrow> </math> 或者 <math> <mrow> <msup> <mi>R</mi> <mo>&prime;</mo> </msup> <mo>&equiv;</mo> <msup> <mi>D</mi> <msup> <mn>2</mn> <mi>k</mi> </msup> </msup> <mo>.</mo> <munderover> <mi>&Pi;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>m</mi> </munderover> <msubsup> <mi>G</mi> <mi>i</mi> <mi>di</mi> </msubsup> <mrow> <mo>(</mo> <mi>mod</mi> <mi>n</mi> <mo>)</mo> </mrow> </mrow> </math> 如果需要，然后，控制者在对每一个重新建立的委托R′和一个消息M′中 计算一个杂凑代码H′。当在第一委托动作的末尾，控制者这样检索它所 接收的内容，即每一个委托R的全部或者部分，或者杂凑代码H时，动 态鉴权就成功了。

例如，一个基本操作序列将响应D转换为一个委托R′。这个序列具有 被k-1次除以基数或者乘以基数(mod n)所分离的k次平方(mod n)。对 第i次除法或者乘法，这是在第i次平方和第i+1次平方之间被执行的， 基本任务di的第i比特表示需要使用gi，基本任务d2的第i比特表示需 要使用g2，…，直到基本任务dm的第i比特，它表示需要使用gm。

这里是第一密钥集合的示例。 D²(mod n)＝FD12E8E1F1370AEC9C7BA2E05C80AD2B692D341D46F3 2B93948715491F0EB091B7606CA1E744E0688367D7BB998F7B73D5F7 FDA95D5BD6347DC8R978CA217733 3.D²(mod n)＝F739B708911166DFE715800D8A9D78FC3F332FF622D 3EAB8E7977C68AD44962BEE4DAE3C0345D1CB34526D3B67EBE8BF 987041B4852890D83FC6B48D3EF6A9DF 3².D⁴(mod n)＝582A7AF280C49FE230BEE354BF6FFB30B7519E3C8 92DD07E5A781225BBD33920E5ADABBCD7284966D71141EAA17AF 8826635790743EA7D9A15A33ACC7491D4A7 3⁴.D⁸(mod n)＝BE9D828989A2C184E34BA8FE0F384811642B7B548F 870699E7869F8ED851FC3DB3830B2400C516511A0C28AFDD210EC3 939E69D413F0BABC6DEC441974B1A291 3⁵.5.D⁸(mod n)＝2B40122E225CD858B26D27B768632923F2BBE5 DB15CA9EFA77EFA667E554A02AD1A1E4F6B59BD9E1AE4A537D 4AC1E89C2235C363830EBF4DB42CEA3DA98CFE00 3¹⁰.5².D¹⁶(mod n)＝BDD3B34C90ABBC870C604E27E7F2E9DB2D383 68EA46C931C66F6C7509B118E3C162811A98169C30D4DEF768397DD B8F6526B6714218DEB627E11FACA4B9DB268 3¹¹.5³.7.D¹⁶(mod n)＝DBFA7F40D338DE4FBA73D42DBF427BBF195 C13D02AB0FA5F8C8DDB5025E34282311CEF80BACDCE5D0C433444 A2AF2B15318C36FE2AE02F3C8CB25637C9AD712F 3²².5⁶.7².D³²(mod n)＝C60CA9C4A11F8AA89D9242CE717E3DC6C1 A95D5D09A2278F8FEE1DFD94EE84D09D000EA8633B53C4A0E7F0A EECB70509667A3CB052029C94EDF27611FAE286A7 3²².5⁷.7².D³²(mod n)＝DE40CB6B41C01E722E4F312AE7205F18CDD 0303EA52261CB0EA9F0C7E0CD5EC53D42E5CB645B6BB1A3B00C77 886F4AC5222F9C863DACA440CF5F1A8E374807AC 3⁴⁴.5¹⁴.7⁴.D⁶⁴(mod n)，即，用十六进制表示为3^2C.5^E.7⁴. D⁴⁰＝FFDD736B666F41FB771776D9D50DB7CDF03F3D9 76471B25C56D3AF07BE692CB1FE4EE70FA77032BECD8411B813B4C 21210C6B0449CC4292E5DD2BDB00828AF18 我们发现委托R。鉴权就成功了。 这里是第二密钥集合的示例。 D²(mod n)＝C66E585D8F132F7067617BC6D00BA699ABD74FB9D13E 24E6A6692CC8D2FC7B57352D66D34F5273C13F20E3FAA228D70AEC 693F8395ACEF9206B172A8A2C2CCBB 3.D²(mod n)＝534C6114D385C3E15355233C5B00D09C2490D1B8D8E D3D59213CB83EAD41C309A187519E5F501C4A45C37EB2FF38FBF20 1D6D138F3999FC1D06A2B2647D48283 3².D⁴(mod n)＝A9DC8DEA867697E76B4C18527DFFC49F4658473D03 4EC1DDE0EB21F6F65978B3477C4231AC9B1EBD93D5D49422408E47 15919023B16BC3C6C46A92BBD326AADF 2.3³.D⁴(mod n)＝FB2D57796039DFC4AF9199CAD44B66F257A1FF 3F2BA4C12B0A8496A0148B4DFBAFE838E0B5A7D9FB4394379D72A 107E45C51FCDB7462D03A35002D29823A2BB5 2².3⁶.D⁸(mod n)＝4C210F96FF6C77541910623B1E49533206DFB9E91 6521F305F12C5DB054D4E1BF3A37FA293854DF02B49283B6DE5E5D 82ACB23DAF1A0D5A721A1890D03A00BD8 2².3⁷.D⁸(mod n)＝E4632EC4FE4565FC4B3126B15ADBF996149F2D BB42F65D911D3851910FE7EA53DAEA7EE7BA8FE9D081DB78B249 B1B18880616B90D4E280F564E49B270AE02388 2⁴.3¹⁴.D¹⁶(mod n)＝ED3DDC716AE3D1EA74C5AF935DE814BCC 2C78B12A6BB29FA542F9981C5D954F53D153B9F0198BA82690EF 665C17C399607DEA54E218C2C01A890D422EDA16FA3 2⁵.3¹⁴.D¹⁶(mod n)＝DA7C64E0E8EDBE9CF823B71AB13F17E1161487 6B000FBB473F5FCBF5A5D8D26C7B2A05D03BDDD588164E562D0F5 7AE94AE0AD3F35C61C0892F4C91DC0B08ED6F 2¹⁰.3²⁸.D³²(mod n)＝6ED6AFC5A87D2DD117B0D89072C99FB9DC9 5D558F65B6A1967E6207D4ADBBA32001D3828A35069B256A07C3D 722F17DA30088E6E739FBC419FD7282D16CD6542 2¹¹.3²⁸.D³²(mod n)＝DDAD5F8B50FA5BA22F61B120E5933F73B92 BAAB1ECB6D432CFCC40FA95B77464003A705146A0D364AD40F8 7AE45E2FB460111CDCE73F78833FAE505A2D9ACA84 2²².3⁵⁶.D⁶⁴(mod n)＝A466D0CB17614EFD961000BD9EABF4F021 36F8307101882BC1764DBAACB715EFBF5D8309AE001EB5DEDA 8F000E44B3D4578E5CA55797FD4BD1F8E919BE787BD0 2⁴⁴.3¹¹².D¹²⁸(mod n)＝925B0EDF5047EFEC5AFABDC03A830919761 B8FBDD2BF934E2A8A31E29B976274D513007EF1269E4638B4F65F 8FDEC740778BDC178AD7AF2968689B930D5A2359 2⁴⁴.3¹¹³.D¹²⁸(mod n)＝B711D89C03FDEA8D1F889134A4F809B3F2D 8207F2AD8213D169F2E99ECEC4FE08038900F0C203B55EE4F4C803 BFB912A04F11D9DB9D076021764BC4F57D4834 2⁸⁸.3²²⁶.D²⁵⁶(mod n)＝41A83F119FFE4A2F4AC7E5597A5D0BEB4D4C 08D19E597FD034FE720235894363A19D6BC5AF323D24B1B7FCFD8D FCC628021B4648D7EF757A3E461EF0CFF0EA13 2¹⁷⁶.3⁴⁵².D⁵¹²(mod n)，即2⁸⁸.9²²⁶.D⁵¹²(mod n)＝28AA7F12259BFBA8 1368EB49C93EEAB3F3EC6BF73B0EBD7D3FC8395CFA1AD7FC0F9D AC169A4F6F1C46FB4C3458D1E37C99123B56446F6C928736B17B4BA 4A529

我们发现委托R。鉴权就成功了。 数字签名

数字签名机制使称作一个签名实体的一个实体能够产生签名消息，并 且使称作一个控制者的一个实体能够确认签名消息。这个消息M是任何 二进制序列：它可能是空的。通过在这个消息M后附加一个签名，就这 个消息M进行了签名。这个签名附加内容包括委托和/或者任务和相应的 响应中的一个或者多个。

控制者具有相同的杂凑函数，参数k和m和模数n。参数k和m向 控制者提供信息。首先，d1到dm中的每一个基本任务的值必须是0到 2_k-1-1中的一个(v/2到v-1中的值不被使用)。第二，每一个任务d必须包 括从d1到dm的m个基本任务，即，其数目与基数数目相等。另外，无 法能够表示相反的时，从g1到gm的m个基数是m个第一质数。让(k-1).m 等于15到20中一个值，就可能使用并行产生的4个3元组GQ2进行签 名；让(k-1).m等于60或者更多，就可能使用单个3元组GQ2进行签名。 例如，k＝9，m＝2，一单个三元组GQ2就足够了；每一个任务具有8个字 节，并且基数是2，3，5，7，11，13，和19。

签名操作是3个动作的一个序列：一个委托动作，一个任务动作和 一个响应动作。每一个动作产生一个或者多个GQ2三元组，每一个包括： 一个委托R(≠0)，一个含称作d1，d2，...，dm的m个基本任务的一个任 务d和一个响应D(≠0)。

这个签名方具有一个杂凑函数，参数k和GQ1私有密钥，即根据上 面所描述的3个中的一个而对模数n进行的因式分解。在这个签名方内， 可能将执行委托和响应动作的一个连署人进行隔离，以使隔离对示范者 敏感的功能和参数。为了计算委托和响应，这个连署人具有参数k和GQ2 私有密钥，即根据上面所描述的3个中的一个而对模数n进行的因式分 解。这样被隔离的这个连署人与示范者内所定义的连署人类似。它可能 与一个特定的实施方式相应，例如，∝连接到形成整个签名方的一个PC 的一个芯片卡，或者再∝在一个PC内被特殊保护的程序，或者再∝在一 个芯片卡内被特殊保护的程序。

1)委托动作包括下面的操作： 当这个连署人具有从Q1到Qm的m个私有值和模数n时，它随机地和 私有地产生一个或者多个随机数值r(0＜r＜n)；然后，通过k次连续平方 (mod n)操作，它将每一个随机数值r转换为一个委托R。

R_i≡r^v(mod n)

当这个连署人具有从p1到pf的f个质数因子和m.f个私有分量Qij 时，它随机地和私有地产生f个随机数值的一个或者多个集合：每一个集 合中，一个质数因子pi具有一个随机数值ri(0＜ri＜pi)；然后，通过k次 连续的平方操作(mod pi)，它将每一个随机数值ri转换为一个委托的分 量Ri。

R_i≡r_i^v(mod p_i)

对每一个f委托分量的集合，这个连署人根据中国余数技术建立一个 委托。委托的数量与随机数值的集合的数量相同。

R＝中国余数(R1，R2，...，Rj) 2)任务的动作包括对委托R和需要进行签名的消息M进行杂凑计算来获 得一个杂凑代码，从这个杂凑代码，签名方形成一个或者多个任务，每 一个任务d包括m个基本任务；每一个基本任务的值是0到v/2-1中的 一个；例如，对k＝9，m＝8。每一个任务具有8个字节。其任务的数量与 委托的数量相等。

d＝d1/d2/.../dm，并且是从结果杂凑(M，R)中提取出来的。 3)响应的动作包括下面的操作。

当这个连署人具有从Q1到Qm的m个私有值和模数n时，它使用委 托动作中的每一个随机数值r和根据基本任务的私有值来计算一个或者 多个响应D。

X./≡Q₁^d1.Q₂^d2...Q_m^dm(mod n)

D/≡r./X./(mod n)

当这个连署人具有从pi到pf的f个质数因子和m.f个私有分量Qi，j 时，它使用委托动作中每一个随机数值的集合来计算一个或者多个f个响 应分量的集合：每一个响应分量的集合中每一个质数因子有一个分量。

X_i≡Q_1，i^d1.Q_2，i^d2...Q_m，i^dm(mod p_i)

D_i≡r_i.X_i(mod p_i)

对每一个响应分量的集合，这个连署人根据中国余数技术产生一个响 应。响应的数目与任务的数目相等。

D＝中国余数(D1，D2，...，Df)

这个签名实体对这个消息M进行签名，除了它外，一个附加签名包括：

-或者每一个GQ2三元组，即每一个委托R，每一个任务d和每一 个响应D，

-或者每一个委托R，和每一个相应的响应D，

-或者每一个任务d和每一个相应的响应D。

证实操作的运行取决于附加签名的内容。有3个可能的情形。

如果这个附加包括一个或者多个三元组，这个检查操作就有两个独立 的处理，它们之间的时序不重要。控制者接受这个签名的消息，如果并 且仅当如果下面的两个条件被满足。

首先，每一个三元组必须是一致的(对下面需要被证实的类型有一个 合适的关系)和可接受的(需要对一个非零值进行比较)。 <math> <mrow> <mi>R</mi> <mo>.</mo> <munderover> <mi>&Pi;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>m</mi> </munderover> <msubsup> <mi>G</mi> <mi>i</mi> <mi>di</mi> </msubsup> <mo>&equiv;</mo> <msup> <mi>D</mi> <msup> <mn>2</mn> <mi>k</mi> </msup> </msup> <mrow> <mo>(</mo> <mi>mod</mi> <mi>n</mi> <mo>)</mo> </mrow> </mrow> </math> 或者 <math> <mrow> <mi>R</mi> <mo>&equiv;</mo> <msup> <mi>D</mi> <msup> <mn>2</mn> <mi>k</mi> </msup> </msup> <mo>.</mo> <munderover> <mi>&Pi;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>m</mi> </munderover> <msubsup> <mi>G</mi> <mi>i</mi> <mi>di</mi> </msubsup> <mrow> <mo>(</mo> <mi>mod</mi> <mi>n</mi> <mo>)</mo> </mrow> </mrow> </math> 例如，响应D被一个基本操作序列转换：k-1次除以基数或者乘以基数(mod n)所分离的k次平方(mod n)。对第i次除法或者乘法，这是在第i次平 方和第i+1次平方之间被执行的，基本任务di的第i比特表示需要使用gi， 基本任务d2的第i比特表示需要使用g2，…，直到基本任务dm的第i 比特，它表示需要使用gm。这样，就需要检索出现在附加签名中的每一 个委托R。

另外，这个三元组或者多个三元组必须被连接到消息M。提供对所有 的委托R和消息M进行杂凑运算，就获得了一个杂凑代码，每一个任务 d必须被从这个杂凑代码中恢复出来。 d＝d1/d2/.../dm，与从结果杂凑(M，R)中提取出来的一致。

如果附加签名中无任务：检查操作就通过对所有委托R和消息M进 行杂凑而对一个或者多个任务d进行重构。

D′＝d′₁/d′₂/.../d′_m，被从结果杂凑(M，R)中提取出来，

然后，如果并且仅当如果每一个三元组必须是一致的(对下面需要被 证实的类型有一个合适的关系)和可接受的(需要对一个非零值进行比 较)，这个控制者接受这个签名的消息。 <math> <mrow> <mi>R</mi> <mo>.</mo> <munderover> <mi>&Pi;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>m</mi> </munderover> <msubsup> <mi>G</mi> <mi>i</mi> <mi>di</mi> </msubsup> <mo>&equiv;</mo> <msup> <mi>D</mi> <msup> <mn>2</mn> <mi>k</mi> </msup> </msup> <mrow> <mo>(</mo> <mi>mod</mi> <mi>n</mi> <mo>)</mo> </mrow> </mrow> </math> 或者 <math> <mrow> <mi>R</mi> <mo>&equiv;</mo> <msup> <mi>D</mi> <msup> <mn>2</mn> <mi>k</mi> </msup> </msup> <mo>.</mo> <munderover> <mi>&Pi;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>m</mi> </munderover> <msubsup> <mi>G</mi> <mi>i</mi> <mi>di</mi> </msubsup> <mrow> <mo>(</mo> <mi>mod</mi> <mi>n</mi> <mo>)</mo> </mrow> </mrow> </math>

如果附加签名不包括委托，这个检查操作就根据下面两个公式中的一 个，即最合适的一个公式，重构一个或者多个委托R′。重构的委托不应 是0。 <math> <mrow> <msup> <mi>R</mi> <mo>&prime;</mo> </msup> <mo>&equiv;</mo> <msup> <mi>D</mi> <msup> <mn>2</mn> <mi>k</mi> </msup> </msup> <mo>/</mo> <munderover> <mi>&Pi;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>m</mi> </munderover> <msubsup> <mi>G</mi> <mi>i</mi> <mi>di</mi> </msubsup> <mrow> <mo>(</mo> <mi>mod</mi> <mi>n</mi> <mo>)</mo> </mrow> </mrow> </math> 或者 <math> <mrow> <msup> <mi>R</mi> <mo>&prime;</mo> </msup> <mo>&equiv;</mo> <msup> <mi>D</mi> <msup> <mn>2</mn> <mi>k</mi> </msup> </msup> <mo>.</mo> <munderover> <mi>&Pi;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>m</mi> </munderover> <msubsup> <mi>G</mi> <mi>i</mi> <mi>di</mi> </msubsup> <mrow> <mo>(</mo> <mi>mod</mi> <mi>n</mi> <mo>)</mo> </mrow> </mrow> </math> 然后，控制者必须对所有的委托R′和消息M进行杂凑运算，以重构每一 个任务d。 d＝d1/d2/.../dm，与从结果杂凑(M，R)中提取出来的一致。

如果并且仅当如果每一个重构的任务与附加签名中的相应任务一致 时，这个控制者接受这个签名的消息。

在本发明申请中，已经显示了分别用于实现根据本发明的这个方法， 系统，和设备的私有值和公开值对Q和G，根据本发明的方法，系统和 设备被设计成证明一个实体的真实性和/或者一个消息的完整性和/或者真 实性。

在与本发明申请同一天由France Telecom，TDF和公司Math Rizk 提出申请的、挂起的申请中，该申请的发明人是Louis Guillou和Jean- Jacques Quisquater，描述了分别产生GQ2密钥集合，即模数n和公开 与私有值G与Q对的一个方法，当指数v是2^k时。这个专利申请在这里 被用作参考。