利用相乘半进行数字签名的方法和系统与流程

1.本公开涉及用于验证数字消息或者摘要的真实性的数字签名。

背景技术：

2.在密码学中，针对消息的接收方如何可以验证消息源自预期发送方，数字签名方案定义了规则集。通常，这种方案针对通过诸如互联网的非安全信道发送的消息提供层a验证。
3.存在各种类型的数字签名方案。一种常用的方案使用不对称密码算法(rivest-shamir-adleman，rsa)。在这种算法中，公钥/私钥对中的私钥能够被使用(通常在散列函数中)以“签名”消息。然后，接收方能够使用公钥和相同的散列函数来查值。如果该值与签名匹配，则消息没有被篡改。这种系统的安全性基于大数分解的问题。
4.第二种常用方案是椭圆曲线数字签名算法(ecdsa)，它是使用椭圆曲线密码的数字签名算法(dsa)的扩展。为了安全，这些算法使用模幂运算和离散对数问题。
5.然而，量子计算机正作为潜在的计算平台出现。量子计算机使用
ꢀ“
量子比特”，而不是传统计算机中使用的二进制数字。这种量子计算机理论上能够比经典计算机更快地解决某些问题，包括：整数因式分解(这是rsa算法背后的实力根源)，以及离散对数(这是ecdsa 背后的实力根源)。
6.具体地，彼得肖尔(peter shor)于1994年制定了肖尔量子算法。如果可以构造足够强大的量子计算机，肖尔量子算法已知会攻击基于整数分解或者离散对数的数字签名。利用此类算法，量子计算机针对数字签名方案中的一方发现秘密的风险是非零的。因此，需要针对肖尔算法的对策。
附图说明
7.参考附图将更好地理解本公开，其中：
8.图1是示出了乘法签名方案的数据流程图。
9.图2是示出了散列乘法签名方案的数据流图。
10.图3a是以英文标注示出了杨(young)图的框图。
11.图3b是以法语标注示出了杨图的框图。
12.图4是示出了利用普拉克幺半(plactic monoid)的散列乘法签名方案的数据流图。
13.图5是可以用于本公开实施例的简化计算设备的框图。
具体实施方式
14.本公开提供了一种用于在计算设备处验证通过公共通信信道从第一方接收的签名消息的方法，方法包括：由计算设备从签名消息中提取消息摘要“a”，消息摘要“a”属于半；由计算设备获得针对第一方的公钥[c,e]，公钥的元素包括校验器“c”和端点“e”，校
验器“c”和端点“e”属于半，并且端点包括第一方的私钥“b”和校验器“c”的相乘；将消息摘要“a”和端点“e”相乘，以创建尾标(endmatter)“ae”＝“abc”；由计算设备从签名消息提取签名“d”，签名“d”属于半，并且签名“d”是消息摘要“a”和私钥“b”的相乘；将签名“d”和校验器“c”相乘，以创建签名校验“dc”＝“abc”；以及验证尾标“ae”与签名校验“dc”相匹配，其中校验器是固定值。
[0015]
本公开还提供了一种被配置用于验证通过公共通信信道从第一方接收的签名消息的计算设备，计算设备包括：处理器；以及通信子系统，其中计算设备被配置为：从签名消息中提取消息摘要“a”，消息摘要“a”属于半；获得针对第一方的公钥[c,e]，公钥的元素包括校验器“c”和端点“e”，校验器“c”和端点“e”属于半，并且端点包括第一方的私钥“b”和校验器“c”的乘法；将消息摘要“a
”ꢀ
和端点“e”相乘，以创建尾标“ae”＝“abc”；从签名消息中提取签名“d”，签名“d”属于半，并且签名“d”是消息摘要“a”和私钥“b”的相乘；将签名“d”和校验器“c”相乘，以创建签名校验
ꢀ“
dc”＝“abc”；以及验证尾标“ae”与签名校验“dc”匹配，其中校验器是固定值。
[0016]
本公开还提供了一种用于存储用于验证通过公共通信信道从第一方接收的签名消息的指令代码的计算机可读介质，当指令代码由计算设备的处理器执行时，指令代码使计算设备：从签名消息提取消息摘要“a”，消息摘要“a”属于半；获得针对第一方的公钥[c,e]，公钥的元素包括校验器“c”和端点“e”，校验器“c”和端点“e
”ꢀ
属于半，并且端点包括针对第一方的私钥“b”和校验器“c”的相乘；将消息摘要“a”和端点“e”相乘，以创建尾标“ae”＝“abc”；从签名消息中提取签名“d”，签名“d”属于半，并且签名“d
”ꢀ
是消息摘要“a”和私钥“b”的相乘；将签名“d”和校验器“c”相乘，以创建签名校验“dc”＝“abc”；以及验证尾标“ae”与签名校验“dc”匹配，其中校验器是固定值。
[0017]
根据本公开，半(代数中的数学对象类别)可以被用作乘法签名方案的基础。在本公开的一个实施例中，一个示例半，即，普拉克幺半，可以用于乘法签名方案。
[0018]
乘法签名、散列乘法签名、和普拉克幺半以及它们在乘法签名中的使用在下文中描述。
[0019]
半
[0020]
半是代数中的数学对象的类别。每个半s具有元素集、以及在该集上定义的二元运算。二元运算必须是可结合的(associative)。这意味着：
[0021]
a(bc)＝(ab)c
ꢀꢀꢀꢀ
(1)
[0022]
在上述等式1中，a、b和c在半s中。等式1表明当计算三个元素a、b和c的乘积abc时，不管是首先将a和b相乘，得到某个值 d＝ab，然后将d乘以c，得到abc＝dc，还是首先将b和c相乘，得到值e＝bc，然后将a和e相乘，得到abc＝ae，这都无关紧要。
[0023]
配备有可结合的二元运算的任何集合都是半。
[0024]
半的两个示例包括加法下的正整数{1，2，3，
…
}，和乘法下的正整数{1，2，3，
…
}。这两个示例共享相同的集，但是有不同的二进制运算。如本领域技术人员将理解的，除了上面定义的两个半之外，还有许多其他半。
[0025]
在讨论一般半s时，通常假设运算被写为乘法。此外，当a和 b是利用s中的值表示的变量时，乘积写为ab，省略任何乘法符号。然而，在具体的特定半中，诸如加法下的正整数，针对二元运算的符号“+”被使用，并且该运算可以被写为a+b而不是ab。
[0026]
在某些情况下，半s是可交换的(commutative)，这意味着针对s中的所有a、b，ab＝ba。在如上所限定的使用上述正整数半的示例中，两个示例都是可交换的。
[0027]
其他半是不可交换的。例如，乘法运算下的矩阵是不可交换的。在这种情况下，在乘积abc中，a、b和c的位置对该乘积至关重要。因此，abc可以不同于bac和cab。
[0028]
可结合性是指在乘积abc中，执行两次乘法的顺序无关紧要。因此，可以先计算ab或者bc，但是最终结果是一样的。
[0029]
根据本公开，半具有乘法运算符。
[0030]
然而，不要求半具有除法运算符。在某些情况下，除法运算符可以被形成并且被写为“/”。除法运算符是具有左右输入的二元运算符。假如/是半s上的二元运算符，如果等式(2)成立，则/可以被定义为强除法器：
[0031]
(ab)/b＝a
ꢀꢀꢀꢀ
(2)
[0032]
其中上述等式2针对s中的所有a、b都有效。
[0033]
如果上述等式2仅针对s内a、b值的子集成立，则运算符/可以被定义为部分强除法器。
[0034]
在半命名法中，运算一般写为ab/b，而不是(ab)/b，后者意味着乘法在除法之前完成。
[0035]
此外，还可以针对半定义弱除法器。特别地，有时针对d的许多不同的值，半有其中ab＝db的乘法，在这种情况下，不可能存在强除法器。如果等式(3)成立，则“/”是弱除法器：
[0036]
(ab/b)b＝ab
ꢀꢀꢀꢀ
(3)
[0037]
在等式3中，弱除法器被定义用于所有a、b和s。
[0038]
部分弱除法器利用等式3，但是仅针对s内的值a、b的子集有效。
[0039]
在上述等式2和等式3中，除法器/也被称为右除法器。类似地，二元运算“\”被称为左除法器。如果b\ba＝a，则运算符\是强左除法器。进一步地，如果b(b\ba)＝ba，则二元运算符\是弱左除法器。
[0040]
在各种半中，除法器运算可以是已知的。例如，针对乘法下的正整数，除法器运算是通常的欧几里德(euclidean)除法算法。针对加法下的正整数，除法可以变成减法。针对一些矩阵子，除法器是已知的，其中巴雷斯(bareiss)消除可以被使用。
[0041]
此外，半的构造中的许多构造使用被称为半环的概念。半环r 有两个二元运算，即，加法和乘法，各自在r上形成半。加法也是可交换的。乘法被分布在加法上，这意味着针对r中的所有a、b、c，其中a(b+c)＝ab+ac和(a+b)c＝ac+bc。半环的基本示例包括在通常的加法和乘法运算下的正整数。
[0042]
结构上安全的半
[0043]
诸如椭圆曲线和模乘法等典型的迪菲赫尔曼(diffie-hellman) 是循环，其对模加法是已知同构。如本文所使用的，同构意味着它们共享相同的底层结构，即使它们具有不同的表示 (representation)。模整数加法如果被用作迪菲赫尔曼将是不安全的，因为除法问题很容易。幸运的是，即使已知同构存在，寻同构也是困难的(通过肖尔量子计算机算法除外)。
[0044]
因此，可以说椭圆曲线和模乘法与迪菲赫尔曼一样是“结构上不安全的”，
因为它们与不安全的迪菲赫尔曼(模加法)共享相同的结构。本领域技术人员应当注意，仅仅声称方案在结构上不安全并不意味着方案是不安全的。然而，此类方案可以被怀疑是不安全的，因为此类方案和攻击之间唯一的事情是同构，而同构被已知为是存在的。这种存在性威胁在密码学中是常见的，但是尽管如此，到不存在已知存在性威胁的密码方案可能是有益的。此类方案被认为是在结构上安全的。
[0045]
结构上安全的方案的一个具体示例被称为弗纳姆(vernam)密码，也称为一次性密码本(one-time pad)。已经证明这种密码的保密性是无条件安全的。因此，这种方案在结构上是安全的。然而，一次性密码本有其他安全问题(因为它不提供消息完整性或者验证)，并且具有实用性问题(一次性密码本的大小必须等于消息等因素的大小)。
[0046]
然而，一次性密码本不是签名方案，但是它在上述意义上是结构上安全的。
[0047]
根据本公开，寻求的是结构上安全的签名方案。
[0048]
类似地，如果半具有与已知的弱半相同的结构，则该半可以是结构上不安全的。因此，根据本公开的一个实施例，为了避免结构上不安全的半，两种选择被提供。第一种称为试消除(trialelimination)，第二种称为限制。
[0049]
关于试消除，特定半的结构可以被检查，直到同构。在许多情况下，结构的弱半的存在是明显的。在这种情况下，半可以被消除，并且检查可移动到另一半。因为半是丰富的，甚至具有变化结构的半也是丰富的，所以这个过程可以被继续下去。
[0050]
接下来，试消除可以检查半的结构是否包括弱半。如本文所使用的，“弱”意味着在密码系统中半的使用将允许对密码系统进行计算上可能的攻击，因此此类系统的使用将使密码系统在计算上易受攻击。
[0051]
如果是，则该半可以被消除。
[0052]
如果没有已知的弱半，则该半可以作为签名方案的可选方法 (possibility)而被保留。
[0053]
第二种策略在本文中称为限制。在限制中，半结构的属性可以被考虑。
[0054]
具体地，半可以具有各种属性，诸如交换性(commutativity)，其中针对半内的所有s和t，st＝ts。另一属性可以是正则性 (regularity)，其中针对半内的所有s，存在具有sts＝s的t。其他属性在下面的表1中提供。
[0055][0056]
表1：示例半属性
[0057]
上表1中的属性列表并不详尽。其他属性也可以被考虑。
[0058]
基于上表1中的属性，可以做出确定以考虑该属性是否有利于安全性。如果该属性是不利的，则对于签名方案的半的选择，具有该属性的所有半应当被避免。如果属性使密钥在计算上是易于被发现的，则该属性不利于安全性。
[0059]
备选地，如果该属性有利于安全性，则可以保留该半，并且该属性可以再次与其他属性一起被进一步分析。备选地，如果正在被检查的属性都已经被检查过，那么此类半可以被选择作为签名方案的可选方法。
[0060]
构造的半
[0061]
在进一步的实施例中，半可以通过使用诸如其他半等构建块、或者诸如半环的其他类型的代数对象、甚至任意函数而被构建。这些构建的半能够具有与单独的构建块相同或者更好的安全性。
[0062]
此后，每个半结构可以被用于构建签名方案。半构造可以使用相同或者不同类型的构建块来形成此类半。
[0063]
如本文所用，半环是共享集的半对，其中一个运算为加法运算，另一运算为乘法运算。此外，在半环中，分配律成立。具体地， a(b+c)＝ab+ac并且(a+b)c＝ac+bc。除非另有说明，半环中的加法都被认为是可交换的。
[0064]
为避免混淆，在以下实施例中，通过利用形容词“基(base)
”ꢀ
标记构建块以区分根据构建块的构造。例如，如果给定的半环被当作构建块，诸如正整数的半环r，那么我们构造3
×
3方阵的半环s，方阵的条目属于r。由于r和s都是半环，为了避免混淆，我们设定r 是基半环。在这种情况下，(s的)每个半环元素是其条目属于基半环r的矩阵。
[0065]
下表2提供了可以用于构建半的示例构造的部分列表。在许多情况下，此类半可以根据诸如其他半等其他构建块而被构建，或者有时通过半环而被构建。
[0066][0067]
表2：示例构造
[0068]
利用上表2的实施例，在基半的直积中，所得半至少与最强基半一样安全。这是最强的链接构造。
[0069]
在其他构造中，与基对象相比，每个构造可以提高安全性。因此，目标是增强安全性。
[0070]
在一个实例中，考虑基于二元多项式的结果(resultant)的半。首先数学地描述半。然后描述在密码系统中使用这种半的细节。
[0071]
设z为整数的环。设z[x,y]是具有整数系数的二元多项式的集。通常情况下，在多项式和加法下，z[x,y]被视为环r，但是此处我们给z[x,y]不同的半环结构b。被写为+b的b中的加法是r中的乘法，被写为*的b中的乘法使用了结式运算，所以(f*g)(x,y)＝ res
t
(f(x,t),g(t,y))。
[0072]
现在，b是具有非可交换的乘法的半环。这是根据众所周知的结式论(theory of resultants)得出的。例如，res(f,gh)＝res(f,g)res(f,h) 证明了分配律。
[0073]
具体地，可以通过使用具有b中条目的2
×
2方阵形成半s，其中乘法被记为*，并且s乘法为b-矩阵乘法(使用b中的运算)。
[0074]
s中乘法的示例，设
[0075][0076][0077]
则：
[0078][0079]
相当于如下的矩阵：
[0080][0081]
因此，现在有八个结果(resultant)需要计算。计算结果的一种方法是计算西尔维斯特(sylvester)的行列式。
[0082]
在本公开中，定义了西尔维斯特矩阵的水平升序版本。西尔维斯特矩阵是正方形矩阵，其边长等于活动变量(在本例中为变量t)的次数之和。每个输入多项式的t个系数被以升序从最低次数项到最高次数项水平排列。行的剩余条目进行零填充。每个多项式在与另一多项式的次数相匹配的行数目中被使用。多项式的每次使用都向右移动一次，直到它到达矩阵的右侧。
[0083]
西尔维斯特矩阵的其他排列也是可以的，诸如垂直或者降序(有时在教科书中使
用)，但是其他排列最多改变符号。
[0084]
例如，
[0085][0086]
在这种情况下，行列式是72xy2+64。类似地计算所有8个行列式，可以得到：
[0087][0088]
最后，可以将上面作为标准多项式乘积给出的每个条目扩展为和，如下所示：
[0089][0090]
为了更好的安全性，应当选择具有更高次数和更大系数的起始多项式(例如，私钥b)。此外，可以使用具有更多行和列的矩阵。根据a*b和a确定b应当要困难得多。
[0091]
诸如巴雷斯归约等用于矩阵除法的典型已知算法适用于可交换的环中具有元素的矩阵。但是这里的矩阵元素不是可交换的，甚至不是环。例如，减法是不可能的。也许b可以通过引入形式差(以类似于负整数如何被引入为正整数的形式差的方式)而被扩展到环。但是除法和不可交换性需要被处理。这些困难可能是密码分析的重大障碍。
[0092]
本领域技术人员可以注意到，a*b最初是以其条目为条目a和b 的结果的乘积的形式获得的。如果a*b的条目可以被因式分解，则可以尝试将因子与b的条目匹配，然后在半环b中执行除法，以提取b 的条目。
[0093]
这种攻击策略需要多项式因式分解。针对大整数系数和高次多项式的多项式因式分解针对常规(非量子)计算机可能是困难的。
[0094]
量子计算机可以使多项式因式分解更容易。然而，为了解决量子计算机风险，可以使用另一方法。确保输入矩阵a和b具有也是乘积的条目。乘积a*b矩阵条目仍然可以因式分解，但是现在可以有更多的因子，并且可以没有任何简单方法来将a*b条目的因子与b的因子相匹配。
[0095]
上表2列出了可以用于构建具有更好安全性的半(根据更多基半)的各种已知的半构造。
[0096]
可以通信的两个用户在本文中称为爱丽丝和查理。在乘法签名方案中，通常爱丽丝可以向查理发送签名消息，其中查理将有权使用爱丽丝的公钥来验证签名文档。如果爱丽丝和查理将此类半用于乘法签名方案，他们需要能够彼此发送和表示半元素。所以，这意味着他们必须有一些把半元素转换成字节序列的方法。这种字节表示通常在密码学中被使用。它们在不对称密码算法(rsa)、椭圆曲线密码(ecc)和许多其他系统中被使用。
[0097]
下文描述了基于结果的半系统，其在上文中以数学方式进行了描述。
[0098]
在某些情况下，新的字节编码方案可以用于此类半。备选地，在一个实施例中，
不是设计一种全新的字节编码方案，而是可以使用一些现有的能够做后续陈述的两件事的字节编码方案：编码整数和编码其他对象的序列。抽象语法符号1(asn.1)可以做到这一点(或者更准确地说，asn.1基本编码规则可以做到这一点)。另一编码系统是javascript对象符号(json)。
[0099]
在一个实施例中，矩阵可以被表示为它的行的序列。此外，行可以被表示为条目的序列。变量x和y中的二元多项式可以被表示为y 个系数的序列，从0次开始，以递增的次数排序，每个系数是变量x 中的一元多项式。(但是将零多项式表示为空序列。)x中的一元多项式可以被表示为从零次开始的升序系数序列，每个系数是整数(并且通过空序列表示零多项式)。
[0100]
假设对象a、b、c的序列表示为[a,b,c]，其中每个对象a、b、c 由它们的表示代替。假设整数以通常的十进制形式而被表示。
[0101]
考虑等式13中的示例a*b。它的表示为： [[[[-24],[0,64,270],[0,0,0,-720]],[[-99,0,135],[],[-11,0,15]]],[[[-455],[-13 0],[0,-504],[0,-144]],[[1089,18],[],[121,2]]]]。
[0102]
根据这些嵌套序列和整数，字节编码相对容易。最简单的是只使用ascii文本。
[0103]
如上所述，爱丽丝可能会使用比示例中所示更大的参数，以实现更好的安全性。因此，爱丽丝会使用更大的整数、更高次的多项式和具有更多条目的矩阵。但是它们仍然可以使用上面描述的编码方案，即使它们使用大得多的参数。更大的参数意味着爱丽丝必须与查理交换更多的字节。
[0104]
除了上述使用描述了新的半的结果的实施例和简要概述之外，还有在单独的技术和研究报告中列出的半。同样，这些不同的半可以组合成更大的半。在某些情况下，半包含半环。
[0105]
下表按名称示出了各种此类半：
[0106]
·
数值半
[0107]
·
(半中研究得最多的子范畴)
[0108]
·
子半
[0109]
·
像半
[0110]
·
限制半
[0111]
·
扩展半
[0112]
·
逆半
[0113]
·
乘积半(直积)
[0114]
·
复合域(compositum)半(自由积)
[0115]
·
析取半
[0116]
·
里斯(rees)矩阵半
[0117]
·
多项式函数半
[0118]
·
单基因(循环)半
[0119]
·
零(常数)半
[0120]
·
左右半
[0121]
·
布尔(boolean)半
[0122]
·
字半
[0123]
·
变换(函数)半
[0124]
·
部分变换半
[0125]
·
关系半
[0126]
·
任意二元运算半
[0127]
·
半自动半
[0128]
·
来自全序集和格的半
[0129]
·
半的特性半(见[l])
[0130]
·
来自半环的半(加法或者乘法)
[0131]
·
具有左加法的半环和用于乘法的任何半
[0132]
·
具有左乘法的半环和用于加法的任何幂等半
[0133]
·
作为半代数的半环(见研究报告和[o])
[0134]
·
哈恩(hahn)级数(series)，当半是全序时，半代数的延伸
[0135]
·
半的自同态半环
[0136]
·
来自具有选择的类零集的全序集的半环
[0137]
·
布尔(boolean)半环
[0138]
·
关系半环
[0139]
·
来自使用交(meet)和并(join)的格的半环
[0140]
·
来自使用接合代数的偏序集的半环
[0141]
·
来自使用并(union)用于加法并且使用相交(intersection)用于相乘的拓扑的、具有无限和的半环
[0142]
·
使用连接的作为半运算的定向结或者流形的半
[0143]
·
具有来自非负实数的具有无限和的半环、
[0144]
·
具有一点(one point)延伸的半环
[0145]
·
多项式的半环
[0146]
·
矩阵的半环
[0147]
·
结果的半环
[0148]
·
范畴代数的半环
[0149]
·
具有乘积和余积的范畴中的对象半
[0150]
·
环(半环中研究得最多的子类别)
[0151]
·
韦尔(weyl)代数
[0152]
·
整数值多项式(非诺特林non-noetherian环)
[0153]
·
诸如标准多项式环的环的理想的半环(在理想加法和乘法下)
[0154]
·
(直接和以及张量积下的)环的模的半环
[0155]
·
环的分数理想的半环
[0156]
·
使用弗雷德霍姆运算用于相乘的单位平方上被限定的连续函数的半环
[0157]
·
具有误差校正的半
[0158]
·
或者来自近环的半。
[0159]
考虑标准多项式环的理想的半环。格罗布纳基的理论在其基础方面提供了每个
理想的唯一表示。
[0160]
加法和乘法则很简单：加法只取基的并集，理想乘法只乘基。然后使用布赫贝格尔(buchberger)算法重新归一化基。这给出了半环，即，加法半和乘法半。加法半是幂等的，所以楔形问题很容易。乘法半有已知的有效除法算法，即，理想商算法，它不如乘法算法那么有效。因此，这种半可能不适合直接用于乘法签名方案。
[0161]
然而，半环可以用作更复杂构造的中间步骤。例如，半环可以用作构成矩阵的或者构成半代数的基半环。强减法在理想的半环中是不可能的这一事实可以使得诸如用于矩阵除法的巴雷斯算法的已知算法不可行。
[0162]
将半转换成乘法签名方案
[0163]
任何半均可以转化为乘法签名方案。上面提供了这种半的示例。
[0164]
基于以上所述，如果安全的后量子抗性签名方案是可能的，则可以利用根据本公开的方法和系统以及一些子组来创建该方案。
[0165]
现在参考图1。在图1的实施例中，使用了以下术语：
[0166]
符号名称通常所指：a事件消息摘要b私钥一个签名人的私钥c校验器固定的系统范围d签名被附到签名事件e端点特定于签名人的值[a,d]签名事件待验证的事件[c,e]公钥被验证为签名人的公钥e＝bc秘钥生成签名人使用私钥bd＝ab签名签名人使用私钥bae＝dc验证签名人使用公共信息
[0167]
表3：乘法签名总结
[0168]
根据表3，变量a、b、c、d和e是半的元素。如上所述，半及其元素的主要要求是针对遵守结合律a(bc)＝(ab)c的某种形式的乘法，任意两个元素可以相乘。
[0169]
元素a、b、c、d和e不一定是数字。因此，乘法不一定是传统的数字乘法。例如，可以被使用的半是普拉克幺半，如下所述。
[0170]
公钥是[c,e]元素对。公钥也称为签名验证密钥。元素c是校验器，并且根据这里的实施例，元素在系统范围内是固定的。元素e是端点。通常，元素e特定于单个签名人。
[0171]
为了简化本公开，签名人通过使用他们的公钥而被命名。实际上，公钥基础设施(pki)将用于建立每个签名人的公钥[c,e]，将加密值[c,e] 绑定到签名人的更易读的名称。
[0172]
签名人的公钥通常被嵌入证明[c,e]属于签名人的证书中。典型的 pki手动分发一些证书作为根证书，然后将信任传递给使用数字签名的其他证书。
[0173]
签名事件是[a,d]元素对。元素a是事件，元素d是签名。该事件通常是作为有意义的信息的摘要而被产生。事件有时对许多签名人来说是共同的，例如当短消息需要被签名时。
[0174]
关于术语，通常认为d是关于事件a的签名，或者d是a上的签名。
[0175]
现在参考图1，其中在本文中称为“爱丽丝”的用户希望向第二用户“查理”发送签名消息。在这点上，在框110，爱丽丝可以使用她的私钥(称为元素b)来生成公钥[c,e]。具体地，公钥[c,e]的私钥b 是元素b，使得：
[0176]
e＝bc
ꢀꢀꢀꢀ
(11)
[0177]
如果存在至少一个针对[c,e]的私钥b，则公钥[c,e]是可行的。
[0178]
在框110处，爱丽丝可以在选择公钥[c,e]之前，通过根据上述等式14计算端点e来选择私钥b。这就产生了可行的公钥。
[0179]
所述过程从框110前进至方框120，在框120中，爱丽丝可以生成签名d。具体地，爱丽丝可以根据等式15使用私钥b对事件a进行签名。
[0180]
d＝ab
ꢀꢀꢀꢀ
(12)
[0181]
然后，如消息130所示，爱丽丝可以向查理提供签名事件[a,d]。在一些实施例中，公钥[c,e]也被提供在消息130中。然而，在其他情况下，可以通过其他机制来发布公钥。
[0182]
查理接收消息130，并且可以从该消息中获得签名事件[a,d]。查理还可以从消息130或者通过其他机制获得爱丽丝的公钥[c,e]。
[0183]
此外，由于校验器在本实施例中为通用系统，在某些情况下，消息130可以仅包含端点。在其他情况下，可以通过其他机制来发布端点，而不需要校验器，因为爱丽丝和查理都知道校验器。其他选择也是可能的。
[0184]
在框140中，查理可以通过将元素a和e相乘来计算尾标ae。
[0185]
在框142中，查理可以通过将元素d和c相乘来计算签名校验dc。
[0186]
具体地，有时单独讨论等式1的两侧是有用的，因为它们在无效签名中可以不同，因为它们需要单独的计算，并且因为它们可以帮助标识何时现有签名方案类似于乘法签名方案。
[0187]
因此，在框150处，可以进行验证以确定尾标和签名校验是否相同。具体地，针对[c,e]，签名事件[a,d]是可验证的，因为根据下面的等式13，乘法是可结合的。
[0188]
ae＝a(bc)＝(ab)c＝dc
ꢀꢀꢀꢀ
(13)
[0189]
因此，基于框150的结果，查理可以验证爱丽丝是否签署了事件 a。
[0190]
如本领域技术人员所知，签名人应当保持私钥b的私密性，以使其他人无法在[c,e]下生成签名。
[0191]
将半转换为散列乘法签名方案
[0192]
在密码学中，散列函数是利用单向函数将任意长度的输入映射到固定大小的输出的算法。具体地，散列函数是确定性的，这意味着它对相同的消息给出相同的结果。此外，由于散列函数是单向的，因此在给定散列值的情况下获取消息是不可行的。
[0193]
在一些实施例中，散列函数可以是带密钥的散列函数。在这种情况下，散列函数使用加密密钥k和加密散列函数两者。
[0194]
散列乘法签名方案修改了图1的乘法签名方案，如下所述。表4 提供了该方案的总结。
[0195]
符号名称通常所指：a事件消息摘要
b私钥一个签名人的私钥c校验器固定的系统范围d原始签名被附到签名事件e端点特定于签名人的值f散列函数固定的或者签名人选择的密钥[d,f]签名原始签名的扩展[m,d,f]签名消息要验证的事件[c,e]公钥被验证为签名人的公钥a＝f(m)生成摘要签名人和校验器计算短ae＝bc秘钥生成签名人使用私钥bd＝ab签名签名人使用私钥bae＝dc验证签名人使用公共信息
[0196]
表4：散列乘法签名总结
[0197]
基于表4，散列乘法签名的签名人和校验器将来自散列的事件计算为如下所示：
[0198]
a＝f(m)
ꢀꢀꢀꢀ
(14)
[0199]
在上述等式14中，m为消息，f(m)为应用于消息的散列函数。
[0200]
因此，现在参考图2。在图2的实施例中，爱丽丝在框210处生成消息的散列，以利用上面的等式14来创建消息摘要a。
[0201]
在框212处，爱丽丝可以使用她的私钥(称为元素b)来生成公钥[c,e]。具体地，针对公钥[c,e]的私钥b是元素b，从而上述等式11 得到满足。
[0202]
如果存在至少一个针对[c,e]的私钥b，则公钥[c,e]是可行的。
[0203]
在框212处，爱丽丝可以在选择公钥[c,e]之前通过根据上述等式 11计算端点e来选择私钥b。这就产生了可行的公钥。
[0204]
在框220处，利用上述等式12和等式14，爱丽丝可以计算原始签名d。
[0205]
然后，爱丽丝可以在消息230中以[m,d,f]的形式向查理提供签名消息。在一些实施例中，消息230可以进一步包括爱丽丝的公钥[c,e]。然而，由于c是系统范围内已知的，所以在某些情况下，它可以不构成消息230的部分。此外，除了在消息230中之外，还可以以其他方式发布爱丽丝的端点，因此，在一些情况下，在消息230中不提供公钥。
[0206]
此外，在一些实施例中，散列函数f可以采用等式15的形式。
[0207]
f(m)＝hk(m)
ꢀꢀꢀꢀ
(15)
[0208]
在上述等式15中，h是具有密钥k的密钥散列函数。在这种情况下，散列函数h可以跨整个系统中是固定的，在这种情况下，密钥k 足以指定函数f。这允许f具有短的规格，使得签名[d,f]不会太长。例如，签名可以是[d,k]。
[0209]
在这种情况下，消息230可以将签名消息作为[m,d,k]而不是[m,d,f] 传输。
[0210]
此外，在一些实施例中，整个系统的密钥k可以是固定的。在这种情况下，签名人可能没有必要将密钥k发送给校验器。在这种情况下，签名消息[m,d,f]缩减至消息230中的[m,d]。
[0211]
当密钥k不固定时，可以通过多种方式选择密钥k。有时，爱丽丝可以从密钥空间中随机选择密钥k。有时，爱丽丝可以选择密钥k 作为消息的确定性伪随机函数。例如，可以
使用等式16：
[0212]
k＝hb(m)
ꢀꢀꢀꢀ
(16)
[0213]
因此，在等式16中，基于爱丽丝的私钥导出密钥k。
[0214]
此外，在某些情况下，当散列函数为单一的(unify)时，图1实施例的乘法签名方案可以视为图2的散列乘法签名方案的特殊情况。
[0215]
此外，在一些实施例中，图2使用的散列函数不必然是标准散列函数，因为该散列函数需要使用图2实施例的乘法签名方案将消息映射到半元素中。相反，可以使用某种形式的嵌入式散列。
[0216]
嵌入的使用在其他类型的签名中也很常见。例如，在rsa签名中，这种嵌入式散列通常被称为全域散列。
[0217]
如下所述，在普拉克签名的情况下，消息可以被映射至半标准表格。传统的散列可以表示为字节串。标准技术允许这个字节串根据需要尽可能长。将字节字符串转换成半标准表格的简单方法是将其转换成字符串或者整数或者任何可以排序的条目，然后应用罗宾逊申斯特 (robinson-schensted)算法，将该字符串转换成表格。
[0218]
散列的优点是，长消息m可以具有短散列，这通常意味着签名 d＝ab是短的。此外，散列算法通常比安全半乘法更快。
[0219]
再次参考图2，查理接收消息230，并且在框240处生成事件 a＝f(m)。
[0220]
在框242处，查理可以通过将元素a和e相乘来计算尾标ae。具体地，在这种情况下，尾标为f(m)e。
[0221]
在框244处，查理可以通过将元素d和c相乘来计算签名校验dc。
[0222]
在方框250处，可以进行检查以确定尾标和签名校验是否相同。具体地，针对[c,e]，签名事件[m,d,f]是可以验证的，因为每个元素是半，因此根据下面的等式17，乘法是可结合的。
[0223]
f(m)e＝a(bc)＝(ab)c＝dc
ꢀꢀꢀꢀ
(17)
[0224]
因此，基于框250的结果，查理可以验证爱丽丝是否签署了事件 m。
[0225]
如本领域技术人员所知，签名人应当保持私钥b的私密性，以使其他人无法在[c,e]下生成签名。
[0226]
普拉克幺半
[0227]
可以用于本公开实施例的一个半是普拉克幺半。幺半是任何具有恒等(identity)元素的半。当从上下文中清楚时，恒等元素被写为1。针对幺半中的所有a，作为恒等元素意味着1a＝a＝a1。
[0228]
表格由按长度排序的符号行组成。例如，阿尔佛德杨在1900年定义了以左对齐形式排列的方框或者单元格集，现在称为杨图。图3a 示出了杨图310，其中从上到下按照长度对单元进行排序，顶部最长。这被称为英语符号。图3b示出了按长度排序的杨图312，底部是最长的。这被称为法语符号。本公开的实施例可以使用任一符号，但是法语符号在本公开中被用作示例。
[0229]
杨表格包括利用来自某个有序集的符号来填充杨图中的框。如果有序集合没有重复，这被称为标准表。如果有序集中的符号允许重复，这可以创建半标准表格。具体地，在半标准表格中，每行从最低到最高(从左到右)排序，允许重复。此外，在半标准表格中，
每个列均被排序，但是不允许重复。在法语符号中，列从低到高排序(从下到上)。
[0230]
下表5示出了单个位数字符号的半标准表格示例。
[0231][0232]
表5：具有单个位数字符号的半标准表格示例
[0233]
克努特(1970)通过罗宾逊(1938)和申斯特(1961)的算法，定义了适用于半标准杨表格的可结合的二元运算。舒申贝格尔 (schutzenberger)和拉斯科(lascoux)(1980)研究了由此产生的代数，将其命名为普拉克幺半。
[0234]
乘法可以在逐符号的基础上进行。下面的表6示出了示例，它示出了使用单符号表格基于字符串“helloworld”来创建普拉克幺半。在表6中，必须对每行进行排序。在这种情况下，当下一符号可以被添加到底部行的末尾并且保持该行排序时，它将被添加到该行。当符号不能被添加到底部行的末尾时，它替换该行中的符号，这将使该行保持排序，并且被替换的符号以类似的方式被添加到上面的行。如果符号上方没有行，则创建新行。
[0235]
[0236][0237]
表6：克努特乘法示例
[0238]
如表6所示，乘法是通过在半标准表格中重复插入符号来实现的。
[0239]
在一些实施例中，可以根据表6的表格创建字符串等效性。具体地，不是把普拉克幺半看作半标准表格集，而是把所有字符串形式集看作等效性关系。如果两个字符串生成相同的半标准表格，则它们是等效的。在这种形式中，每个表格都具有作为字符串的备选性表示。
[0240]
针对“helloworld”字符串，从表6的最后一行开始，行读取字符串为“wheedlllor”，列读取字符串为“whedolllor”。这两个字符串以及其他几个字符串将生成与“helloworld”相同的表格。
[0241]“helloworld”和“wheodlllor”字符串是等效的，因为它们都生成相同的表格。因此，他们都是相同的半标准表格的备选性表示。
[0242]
实现这种乘法的c程序的简化示例参见下表7。
[0243][0244]
表7：克努特乘法的c程序示例
[0245]
在表7的示例代码中，程序输入为任何文本，除了空字符和换行符之外的每个ascii字符代表普拉克幺半的生成器元素。根据克努特版本的罗宾逊申斯特算法，程序的输出是这些的乘积，表示为半标准表格，例如表6所示。
[0246]
尽管表6和表7的示例使用ascii字符作为单符号表的有序集，但是在实践中，可以使用任何有序集，只要在数字签名情况下双方同意，如下所述。此外，虽然在示例中提供了单符号表格，但是实际上同样可以使用多符号表格。
[0247]
因此，普拉克幺半的每个元素都是符号的乘积(也称为生成器)。如果符号的乘积可以通过如上所述的克努特变换序列相关联，则它们被认为是等效的。
[0248]
因此，普拉克幺半的元素是这种符号乘积的等效类(classes)。
[0249]
使用普拉克幺半的乘法签名
[0250]
由于普拉克幺半是半，它可以用于乘法签名，在此称为普拉克签名。此外，由于普拉克幺半似乎与rsa或者ecdsa不密切相关，因此普拉克签名的安全性独立于这些签名方案的安全性。因此，普拉克签名似乎可以抵抗已知的量子攻击。
[0251]
现参考图4。在图4的实施例中，爱丽丝希望通过公钥签名方案对消息m进行签名。具体地，如图1和图2所示，爱丽丝和查理相互通信。
[0252]
根据图4的实施例，爱丽丝在框410处利用散列函数来创建消息摘要a。图4使用的散列函数不必然是标准散列函数，因为它需要将消息映射到半元素中。相反，可以使用嵌入式散列形式。
[0253]
具体地，在普拉克签名的情况下，消息可以被映射到半标准表格中。传统的散列可以被表示为字节串。标准技术允许这个字节串根据需要尽可能长。将字节字符串转换成半标准表格的简单方法是将其转换成字符串或者整数或者任何可以排序的条目，然后应用罗宾逊申斯特算法，将该字符串转换成表格。
[0254]
散列的优点是长消息m可以具有短散列，这通常意味着签名d＝ab 较短。此外，散列算法通常比安全半乘法更快。
[0255]
在框412处，爱丽丝可以使用其私钥(称为元素b)生成公钥[c,e]。具体地，针对公钥[c,e]的私钥b是元素b，因此满足上述等式11。
[0256]
如果存在至少一个针对[c,e]的私钥b，则公钥[c,e]是可行的。
[0257]
在框412处，爱丽丝可以在选择公钥[c,e]之前通过根据上述等式 11计算端点e来选择私钥b。这就产生了可行的公钥。
[0258]
因此，可以基于b和c生成e的半标准表格。生成可以使用例如表6和表7的示例。
[0259]
在框420处，可以由爱丽丝计算原始签名d。具体地，可以基于 a和b生成针对d的半标准表格。例如，该生成可以使用表6和表7 的示例。
[0260]
然后，爱丽丝可以在消息230中以[m,d,f]的形式向查理提供签名消息。在一些实施例中，消息430可以进一步包括爱丽丝的公钥[c,e]。然而，由于c是系统范围内已知的，所以在某些情况下，它可以不构成消息430的部分。此外，除了在消息430中之外，还可以以其他方式发布爱丽丝的端点，因此，在一些情况下，在消息430中不提供公钥。
[0261]
此外，如果f是具有密钥k的密钥散列函数，则散列函数h可以跨整个系统中是固定的。在这种情况下，密钥k足以指定函数f。这允许f具有短的规格，使得签名[d,f]不会太长。例如，签名可以是[d,k]。
[0262]
在这种情况下，消息430可以将签名消息作为[m,d,k]而非[m,d,f] 传输。
[0263]
此外，在一些实施例中，针对整个系统的密钥k可以是固定的。在这种情况下，签名人可能没有必要将密钥k发送给校验器。在这种情况下，签名消息[m,d,f]在消息430中缩减到[m,d]。
[0264]
此外，在某些情况下，当散列函数为图4实施例中的恒等函数时，图1实施例中的乘法签名方案可以用于公钥签名。
[0265]
查理接收消息430，并且在框440处生成事件a＝f(m)。具体地，在方框440处，查理利用与爱丽丝所使用的相同的散列函数来创建消息摘要a。
[0266]
在框442处，查理可以通过使用克努特乘法将元素a和e相乘来计算尾标ae。
[0267]
在框444处，查理可以通过使用克努特乘法将元素d和c相乘来计算签名校验dc。
[0268]
在框450处，可以进行检查以确定尾标和签名校验是否相同。特别地，针对[c,e]半标准表格，签名事件[m,d,f]是可验证的。
[0269]
因此，基于框450的结果，查理可以验证爱丽丝是否签署了事件 m。
[0270]
在简化示例中，使用恒等函数作为散列函数，上表6中的消息
ꢀ“
helloworld”可以是上述等式的a或者m。
[0271]
假设爱丽丝使用简单的私钥b作为“私钥”。校验器c是字符串“校验器”。
[0272]
基于这些值，d＝ab导致以下表格：
[0273][0274][0275]
表8：示例签名
[0276]
端点为e＝bc，如下表9所示：
[0277][0278]
表9：示例端点
[0279]
因此[a,d]和[c,e]能够被查理获得，查理能够计算尾标ae为：
[0280][0281]
表10：示例尾标进一步，查理能够计算签名校验dc为s：
[0282][0283]
表11：示例签名校验
[0284]
根据上述内容，尾标和签名校验匹配，因此爱丽丝签署了消息。
[0285]
尽管表8至表11的示例为了说明而被简化，但是实际上将使用更强的校验器和私钥。此外，使用除了单一散列之外的散列也是可以的。
[0286]
在上文中，通过进行困难的除法来提供安全性。特别地，通过计算b＝e/c，可以使用除法运算符到公钥[c,e]的私钥b。
[0287]
为了确保签名的安全性，除法必须是困难的，至少针对签名中使用的任何输入e和c，否则攻击方可以到私钥并且签署任何消息。
[0288]
此外，为安全起见，半不应当具有快速交叉乘法器。特别地，交叉乘法器是运算符，写为*/，使得：
[0289]
(y*/x)x＝(x*/y)y
ꢀꢀꢀꢀ
(18)
[0290]
等式18仅在u和v的值为ux＝vy时成立。
[0291]
一些半具有快速交叉乘法器。在交换半中，x*/y＝x定义了交叉乘法器。在具有零元素的半中，x*/y＝0定义了交叉乘法器。在具有有效逆的中，x*/y＝y-1
定义了交叉乘法器。
[0292]
普拉克幺半是非可交换的，没有零元素，也没有逆元素，因此这三个定义无法给出普拉克幺半的交叉乘法器。
[0293]
另一种攻击向量是伪造无散列签名。为了在无散列乘法中伪造事件a，执行尝试因子分解a＝a2a1。然后，签名人被要求签署事件a1。签名人返回签名d1。然后，伪造者可以计算出d＝a2d1，这是针对事件 a的有效签名。在这种情况下，伪造得到了签名人帮助。
[0294]
基于以上所述，在某些情况下，可能需要使用散列乘法签名来实现普拉克签名。
[0295]
因此，普拉克签名可以用于数字签名。普拉克签名没有已知的量子漏洞，因此可以用于为通信提供附加的安全性。
[0296]
可以使用任何计算设备实施上述方法。参考图5，图5示出了计算设备的简化图。图5的计算设备可以是任何固定的计算设备或者移动计算设备。
[0297]
在图5中，设备510包括处理器520和通信子系统530，其中处理器520和通信子系统530合作以执行上述实施例的方法。在一些实施例中，例如针对不同的无线电技术，通信子系统530可以包括多个子系统。
[0298]
处理器520被配置为执行可编程逻辑，可编程逻辑可以与数据一起存储在设备510上，并且在图5的示例中显示为存储器540。存储器540可以是存储指令代码的任何有形的、非暂时性的计算机可读存储介质，当处理器520执行该指令代码时，该指令代码使得设备510 执行本公开的方法。计算机可读存储介质可以是有形的或者暂态/非暂态介质，例如光学介质(例如，cd、dvd等)、磁介质(例如，磁带)、闪存驱动器、硬盘驱动器、或者本领域已知的其他存储器。
[0299]
备选地，或者作为存储器540的补充，设备510可以例如通过通信子系统530从外部存储介质中访问数据或者可编程逻辑。
[0300]
通信子系统530允许设备510与其他设备或者网络元素通信，并且可以根据所执行的通信类型而变化。此外，通信子系统530可以包括多种通信技术，包括任何有线或者无线通信技术。
[0301]
在一个实施例中，设备510的各种元素之间的通信可以通过内部总线560进行。然而，其他形式的通信也是可以的。
[0302]
本文所述的实施例是其元素对应于本技术的技术的元素的结构、系统或者方法的示例。本书面描述可以使本领域技术人员能够制造和使用具有替代元素的实施例，这些替代元素同样对应于本技术的技术的元素。因此，本技术的技术的预期范围包括与本文所述的本技术的技术没有区别的其他结构、系统或者方法，并且还包括与本文所述的本技术的技术没有实质性区别的其他结构、系统或者方法。
[0303]
虽然在附图中以特定顺序描绘了操作，但是不应当理解为要求以所示特定顺序或者按次序地执行此类操作，或者要求执行所有图示的操作，以实现所需结果。在某些情况下，可以采用多任务和并行处理。此外，上述实现中的各种系统组件的分离不应当被理解为在所有实现中都需要此类分离，并且应当理解，所描述的程序组件和系统通常可以
一起被集成在单个软件产品中或者被封装到多个软件产品中。
[0304]
此外，在各种实现中描述和说明为离散的或者单独的技术、系统、子系统和方法可以与其他系统、模块、技术、或者方法组合或者集成。被示出或者被讨论为彼此耦合或者直接耦合或者通信的其他项目可以通过一些接口、设备或者中间组件间接地耦合或者通信，无论是电耦合、机械耦合、或者其他方式。本领域技术人员可以确定并且做出改变、替换和变更的其他示例。
[0305]
虽然上述详细说明显示了、描述了并且指出了应用于各种实施的本公开的基本的新颖的特征，但是应当理解，本领域技术人员可以对所示系统的形式和细节进行各种省略、替换和变更。此外，方法步骤的顺序并不意味着它们在权利要求中出现的顺序。
[0306]
当向/从电子设备发送消息时，此类操作可以不是即时的或者直接来自服务器。消息可以从支持这里描述的设备/方法/系统的服务器或者其他计算系统基础设施被同步或者异步传递。前述步骤可以全部地或者部分地包括去往/来自设备/基础设施的同步/异步通信。此外，来自电子设备的通信可以是去往网络上的一个或者多个端点。这些端点可以由服务器、分布式计算系统、流处理器等来服务。内容递送网络 (cdn)也可以向电子设备提供通信。例如，除了典型的服务器响应，服务器还可以提供或者指示内容传递网络的数据，以等待诸如电子设备的后续活动的电子设备在稍后的时间下载。因此，数据可以直接从服务器或者其他基础设施被发送，诸如作为系统的部分的分布式基础设施或者cdn或者与系统分离的分布式基础设施或者cdn。
[0307]
通常，存储介质可以包括以下任何或者某些组合：半导体存储设备，诸如动态或者静态随机存取存储器(dram或者sram)、可擦除可编程只读存储器(eprom)、电可擦除可编程只读存储器 (eeprom)和闪存；磁盘，诸如固定盘、软盘和可移动盘；另一种磁介质，包括磁带；诸如光盘(cd)或者数字视频盘(dvd)的光学介质；或者另一类型的存储设备。注意，上面讨论的指令可以被提供在一个计算机可读或者机器可读存储介质上，或者备选地，可以被提供在分布在可能具有多个节点的大型系统中的多个计算机可读或者机器可读存储介质上。这种计算机可读或者机器可读存储介质被认为是物品(或者制品)的部分。制品或者制造物品可以指任何制造的单个部件或者多个部件。一个或者多个存储介质可以位于运行机器可读指令的机器中，或者位于可以通过网络从其下载机器可读指令以供执行的远程站点。
[0308]
在前述说明中，阐述了许多细节，以帮助理解本文公开的主题。然而，可以在没有这些细节的情况下进行实现。其他实现可以包括对上述细节的修改和变化。所附权利要求旨在覆盖这些修改和变化。

技术特征：

1.一种用于在计算设备处验证通过公共通信信道从第一方接收的签名消息的方法，所述方法包括：由所述计算设备从所述签名消息提取消息摘要“a”，所述消息摘要“a”属于半；由所述计算设备获得针对所述第一方的公钥[c,e]，所述公钥的元素包括校验器“c”和端点“e”，校验器“c”和端点“e”属于所述半，并且所述端点包括针对所述第一方的私钥“b”和所述校验器“c”的相乘；将所述消息摘要“a”和所述端点“e”相乘，以创建尾标“ae”＝“abc”；由所述计算设备从所述签名消息提取签名“d”，所述签名“d”属于所述半，并且所述签名“d”是消息摘要“a”和所述私钥“b”的相乘；将所述签名“d”和所述校验器“c”相乘，以创建签名校验“dc”＝“abc”；以及验证所述尾标“ae”与所述签名校验“dc”相匹配，其中所述校验器是固定值。2.根据权利要求1所述的方法，其中所述半基于试消除而被选择，其中具有计算上易受攻击的密码结构的半被消除以免被选择。3.根据权利要求1所述的方法，其中所述半基于限制而被选择，其中限制包括：检查所述半的至少一个属性；以及如果所述属性是在计算上易受攻击的，则移除所述半以免被选择。4.根据权利要求3所述的方法，其中所述属性包括从属性列表所选择的至少一个属性，所述属性列表包括：有限半、幺半、幂等半、交换半、指数增长半、抵消半、、正则半、幂零半、基本半、或者双单半。5.根据权利要求1所述的方法，其中所述半从至少两个构建块的组合而被构成。6.根据权利要求5所述的方法，其中所述每个构建块从列表被选择，所述列表包括：数值半、、子半、像半、限制半、扩展半、逆半、乘积半、复合域半、析取半、里斯矩阵半、多项式函数半、单基因半、零半、左右半、布尔半、字半、变换半、部分变换半、关系半、任意二元运算半、半自动半、来自全序集和格的半、半的特性半、来自半环的半、具有左加法的半环和用于乘法的半、具有左乘法的半环和用于加法的任何幂等半、作为半代数的半环、哈恩级数、当所述半是全序时所述半代数的延伸、半的自同态半环、来自具有选择的类零集的全序集的半环、布尔半环、关系半环、来自使用交和并的格的半环、来自使用接合代数的偏序集的半环、来自使用并用于加法并且使用相交用于相乘的拓扑的、具有无限和的半环、使用连接的和作为半运算的定向结或者流形的半、具有来自非负实数的无限和的半环、具有一点延伸的半环、多项式的半环、矩阵的半环、结果的半环、范畴代数的半环、具有乘积和余积的范畴中的对象半、环、韦尔代数、整数值多项式、诸如标准多项式环的环的理想的半环、直接和与张量积下的环的模的半环、环的分数理想的半环、在使用弗雷德霍姆运算用于相乘的单位平方上被限定的连续函数的半环、具有误差校正的半、或者来自近环的半。7.根据权利要求1所述的方法，其中所述消息摘要是散列值。8.根据权利要求1所述的方法，其中所述半是普拉克幺半，并且其中相乘是克努特相乘。9.权利要求8的方法，其中所述签名“d”和端点“e”包括半标准表格。
10.一种被配置用于通过公共通信信道从第一方接收的签名消息的验证的计算设备，所述计算设备包括：处理器；以及通信子系统，其中所述计算设备被配置为：从所述签名消息提取消息摘要“a”，所述消息摘要“a”属于半；获得针对所述第一方的公钥[c,e]，所述公钥的元素包括校验器“c”和端点“e”，校验器“c”和端点“e”属于所述半，并且所述端点包括针对所述第一方的私钥“b”和所述校验器“c”的相乘；将所述消息摘要“a”和所述端点“e”相乘，以创建尾标“ae”＝“abc”；从所述签名消息提取签名“d”，所述签名“d”属于所述半，并且所述签名“d”是消息摘要“a”和私钥“b”的相乘；将所述签名“d”和所述校验器“c”相乘，以创建签名校验“dc”＝“abc”；以及验证所述尾标“ae”与所述签名校验“dc”相匹配，其中所述校验器是固定值。11.根据权利要求10所述的计算设备，其中所述半基于试消除而被选择，其中具有计算上易受攻击的密码结构的半被消除以免被选择。12.根据权利要求10所述的计算设备，其中所述半基于限制而被选择，其中限制包括：检查所述半的至少一个属性；以及如果所述属性是在计算上易受攻击的，则移除所述半以免被选择。13.根据权利要求12所述的计算设备，其中所述属性包括从属性列表所选择的至少一个属性，所述属性列表包括：有限半、幺半、幂等半、交换半、指数增长半、抵消半、、正则半、幂零半、基本半、或者双单半。14.根据权利要求10所述的计算设备，其中所述半从至少两个构建块的组合而被构成。15.根据权利要求14所述的计算设备，其中所述每个构建块从列表被选择，所述列表包括：数值半、、子半、像半、限制半、扩展半、逆半、乘积半、复合域半、析取半、里斯矩阵半、多项式函数半、单基因半、零半、左右半、布尔半、字半、变换半、部分变换半、关系半、任意二元运算半、半自动半、来自全序集和格的半、半的特性半、来自半环的半、具有左加法的半环和用于乘法的半、具有左乘法的半环和用于加法的任何幂等半、作为半代数的半环、哈恩级数、当半是全序时半代数的延伸、半的自同态半环、来自具有选择的类零集的全序集的半环、布尔半环、关系半环、来自使用交和并的格的半环、来自使用接合代数的偏序集的半环、来自使用并用于加法并且使用相交用于相乘的拓扑的、具有无限和的半环、使用连接的和作为半运算的定向结或者流形的半、具有来自非负实数的无限和的半环、具有一点延伸的半环、多项式的半环、矩阵的半环、结果的半环、范畴代数的半环、具有乘积和余积的范畴中的对象半、环、韦尔代数、整数值多项式、诸如标准多项式环的环的理想的半环、直接和与张量积下的环的模的半环、环的分数理想的半环、在使用弗雷德霍姆运算用于相乘的单位平方上被
限定的连续函数的半环、具有误差校正的半、或者来自近环的半。16.根据权利要求10所述的计算设备，其中所述消息摘要是散列值。17.根据权利要求10所述的计算设备，其中所述半是普拉克幺半，并且其中相乘是克努特相乘。18.根据权利要求17所述的计算设备，其中所述签名“d”和端点“e”包括半标准表格。19.一种用于存储用于通过公共通信信道从第一方接收的签名消息的验证的指令代码的计算机可读介质，当所述指令代码由计算设备的处理器执行时，使所述计算设备：从所述签名消息提取消息摘要“a”，所述消息摘要“a”属于半；获得针对所述第一方的公钥[c,e]，所述公钥的元素包括校验器“c”和端点“e”，校验器“c”和端点“e”属于所述半，并且所述端点包括针对所述第一方的私钥“b”和所述校验器“c”的相乘；将所述消息摘要“a”和所述端点“e”相乘，以创建尾标“ae”＝“abc”；从所述签名消息提取签名“d”，所述签名“d”属于所述半，并且所述签名“d”是消息摘要“a”和私钥“b”的相乘；将所述签名“d”和所述校验器“c”相乘，以创建签名校验“dc”＝“abc”；以及验证所述尾标“ae”与所述签名校验“dc”相匹配，其中所述校验器是固定值。

技术总结

一种利用乘法相乘半进行数字签名的方法和系统。一种用于在计算设备处验证通过公共通信信道从第一方接收的签名消息的方法，该方法包括：从签名消息中提取消息摘要“a”，消息摘要“a”属于半；获得第一方的公钥[c,e]，公钥的元素包括校验器“c”和端点“e”，校验器“c”和端点“e”属于半，并且端点包括第一方的私钥“b”和校验器“c”的乘法；将消息摘要“a”和端点“e”相乘，以创建尾标“ae”＝“abc”；从签名消息中提取签名“d”，签名“d”属于半，并且签名“d”是消息摘要“a”和私钥“b”的乘法；将签名“d”和校验器“c”相乘，以创建签名校验“dc”＝“abc”；以及验证尾标“ae”与签名校验“dc”匹配。匹配。匹配。