CN101300570B

CN101300570B - 用于使用数字签名的网络编码内容分发的方法和系统

Info

Publication number: CN101300570B
Application number: CN2006800410654A
Authority: CN
Inventors: K·E·劳特; D·X·查尔斯; K·简恩
Original assignee: Microsoft Corp
Current assignee: Microsoft Technology Licensing LLC
Priority date: 2005-11-04
Filing date: 2006-10-31
Publication date: 2010-09-08
Anticipated expiration: 2026-10-31
Also published as: EP1955198A1; JP5064408B2; KR101311057B1; US7743253B2; JP2009515480A; WO2007056038A1; EP1955198B1; EP1955198A4; CN101300570A; US20070118746A1; KR20080065992A

Abstract

描述了用于网络编码的数字签名。在一方面，描述了用于网络编码的数字签名。在一方面，使用从椭圆曲线生成的同态数字签名来数字地签署要分发的分段内容块。包括数字地签署的内容的分组的线性组合根据一实现的分发方案被分发到目的地设备。该分组的线性组合包括当数字地签署分段块时的公共信息。该同态数字签名和公共信息允许接收该分组的线性组合中的一个或多个分组的设备独立于用于数字地签署该一个或多个分组的密钥和散列摘要的安全传输来验证并认证与该一个或多个分组相关联的内容。

Description

用于使用数字签名的网络编码内容分发的方法和系统

技术领域

本发明涉及网络分发，尤其涉及使用数字签名的网络编码内容分发。

背景技术

增加的网络带宽允许将大量和各种类型的媒体内容分布在互联网上。对等网络通过允许中间节点也发送数据来处理将数据从单个源广播到网络上的多个接收器的问题。为发送一大文件，常规的分布式系统通常将该文件分段成较小的部分用于传输。这一方案的问题是带宽利用不需要是最优的，因为可能存在瓶颈问题。结合大规模内容分发机制使用的网络编码解决了这一问题。网络编码允许网络中的所有节点完成对输入数据的局部编码。已表明这能在理论上和实践中产生最优网络容量利用。然而，就这一点而言，由于安全问题，关于用网络编码来分发内容的任何考虑缺乏真实世界的适用性。例如，常规的网络编码系统和技术不允许对所传送的数据进行认证和验证。

发明内容

提供本概述以便用简化的形式介绍将在以下详细描述中进一步描述的一些概念。本概述并不旨在确定所要求保护的主题的关键特征或必要特征，也不旨在用于帮助确定所要求保护的主题的范围。

鉴于以上原因，描述了用于网络编码的数字签名。在一方面，使用从椭圆曲线生成的同态数字签名来数字地签署用于分发的分段的内容块。根据一实现的分发方案将包括该数字地签署的内容的分组的线性组合分发到目的地设备。该分组的线性组合包括当数字地签署该分段块时的公共信息。该同态数字签名和公共信息允许接收该分组的线性组合的一个或多个分组，以独立于用于数字地签署该一个或多个分组的密钥和散列摘要的安全传输来验证并认证与这些分组之一相关联的内容。

附图说明

在附图中，一组件参考标号最左边的数字标识其中首次出现该组件的特定附图。

图1示出了根据一个实施例的当基于网络编码分发方案分发内容时利用数字签名的示例性系统。

图2示出了根据一个实施例在网络编码分发方案中使用数字签名的示例性过程。

图3示出了其中可全部或部分地实现用于网络编码的数字签名的合适的计算环境的一个示例。

具体实施方式

概要

以下参考图1-3描述用于网络编码的数字签名的系统(例如，系统、装置、计算机可读介质等)和方法。这些系统和方法解决了上述安全问题以及使用网络编码在分布式网络中分发内容的其它现有的安全限制。为此，该系统和方法在网络编码操作中利用了同态散列。给定一散列函数，对该散列函数，找到冲突在计算上是不可行且线性的，该系统和方法根据输入的散列值来计算输入消息的线性组合的散列。所计算的散列基于椭圆曲线的理论用于签名方案中，以确定消息是否被更改或这是否将无用信息插入到消息中。知道了某些消息的签名，该系统和方法签署该消息的线性组合。签名方案是同态的，这意味着签名的线性组合与线性组合的签名相同。这允许该系统和方法直接检测到将无用信息注入到网络(即，污染攻击)的恶意节点并向网络编码方案添加了认证。

用于网络编码中的数字签名的系统和方法在假定椭圆曲线上的离散对数问题是困难(密码学中的一种常见假设)时是安全的。该系统和方法通过在较小的域上工作以提供相对于同一安全等级的其它方案的性能优点，来实现同态散列的相同安全等级。安全性利用局部计算来有效地实现。

鉴于以上内容，用于网络编码中的数字签名的系统和方法在知道了要分发的某些文件的签名之后，产生这些文件的任何线性组合的签名。这允许数据接收者签署在网络中的各节点处组合的分组而无需联系数据源来签署这些分组。这意味着该系统和方法无需保护用于所分发的向量的散列摘要的传输的安全。签名允许对数据的认证。另外，小的比特长度足以确保安全性，这本质上是因为没有已知的(通用)亚指数(sub-exponential)算法能用于有限域上的椭圆曲线上的点群的离散对数。

现在更详细描述用于网络编码中的数字签名的系统和方法的这些以及其它方面。

示例性系统

尽管并非必需，但用于网络编码的数字签名的系统和方法在由诸如个人计算机等计算设备执行的计算机可执行指令(程序模块)的一般上下文中描述。程序模块一般包括执行特定任务或实现特定抽象数据类型的例程、程序、对象、组件、数据结构等。尽管该系统和方法是在前述上下文中描述的，但以下所描述的动作和操作也可用硬件来实现。

图1示出了根据一个实施例的用于网络编码中的数字签名的示例性系统100。在此实现中，系统100表示一内容分发系统。系统100包括通过网络104耦合到任意数目的客户机计算设备106的一个或多个服务器计算设备102。服务器102实现数字地签署内容并使用网络编码操作来将所签署的内容作为分组的线性组合分发到客户机设备106的各操作。响应于接收到分组的线性组合，客户机设备106验证并认证嵌入在所接收的分组中的数字地签署的内容。如果客户机106验证了所接收的内容，并且如果客户机106不是系统104内对于所接收内容的最终目的地，则客户机106实现数字地签署所接收的内容并使用网络编码操作将该经验证且新签署的内容作为分组的新的线性组合分发到不同客户机106的各操作。鉴于以上内容，取决于相应计算设备102和106是否是系统100内针对任何接收的数字地签署的内容的最终目的地，每一计算设备102和106可执行数字地签署并使用网络编码分发内容和验证并认证所接收内容的各操作中的一个或多个。

参考图1，每一服务器102和客户机设备106包括耦合到各自的系统存储器110(例如，110-1和110-2)的一个或多个各自的处理器108(例如，108-1和108-2)。系统存储器110包括计算机程序模块112(例如，112-1和112-2)和程序数据114(例如，114-1和114-2)。处理器108从程序模块112中相应的几个中取出并执行计算机程序指令。程序模块112包括用于网络编码模块116(例如，116-1和116-2)以及诸如操作系统、内容分发模块等其它程序模块118(例如，118-1和118-2)的数字签名。用于网络编码模块(“编码模块”)116的数字签名包括用于在相应的服务器102和客户机106之间通过网络安全并可靠地分发内容的程序逻辑。出于示例性图示的目的，要分发的内容被示为“其它程序数据”120(例如，120-1和120-2)的相应部分。即，编码模块116执行使用网络编码中的数字签名将内容分发到客户机设备106和验证并认证所接收的数字地签署的内容的一个或多个操作。

在此示例中，服务器102的编码模块116-1最初将要分发的内容分段成较小的数据块。这些块分段被示为“其它数据”120-1中的分段内容的相应部分。服务器102使用数字签名方案为每一块分段计算相应的同态数字签名122-1，并用相应的签名122-1签署该块分段以创建相应的已签署块124-1。在系统100中，当通过将一向量空间中的两个向量相加并散列到一椭圆曲线所获得的结果与该椭圆曲线上两个向量的各自的散列之和相同时，显示出同态。一个示例性的签署块分段的这样的方案在以下题为“示例性同态签名方案”的一节中描述。服务器102将已签署块124-1作为分组(或矢量)的线性组合通过网络104传送到一个或多个客户机设备106。生成这一分组的线性组合的示例性网络编码的操作在以下题为“网络编码模型”的一节中更详细描述。

响应于接收到包括已签署块的分组的随机线性组合，客户机设备106对每一已签署块118验证服务器102的签名。一个示例性的基于Weil配对的双线性的这一验证过程在以下题为“示例性同态签名方案”一节中描述。这些验证操作允许客户机106标识内容分发系统100内的不诚实的服务器102。响应于验证并认证了每一已签署块124-1，如果客户机设备106不是针对所接收到的分组的随机线性组合的最终目的地，则客户机设备106实现以上(和以下)对于服务器102所描述的操作，以使用同态散列函数将该数据数字地重新签署到椭圆曲线上的点，并使用网络编码操作来将该已签署的数据重新分发到目的地设备。

即，如果客户机设备106没有被分组的线性组合指定为针对所接收到的内容的最终接收者，并且如果所接收的内容已被成功验证和认证，则知道该所接收内容中的某一些的数字签名的编码模块116-2：(a)重新签署所接收的内容；以及(b)将新的重新签署的内容作为分组的新的线性组合(“其它数据”116-2的相应部分)重新分发到不同的客户机设备106。该过程被迭代，直到相应的客户机设备106是针对从服务器102和/或客户机设备106接收到的分组的线性组合中的内容的最终目的地。这些后面的操作允许数据接收客户机设备106签署在网络104中的各节点处组合的分组，而无需联系源(例如，服务器102和/或另一客户机设备106)来签署该分组的新的线性组合中的分组。

椭圆曲线背景

本节提出了有限域上的椭圆曲线的各方面。有限域F_q上的椭圆曲线E(有时候被简写为E/F_q)。参考该有限域，q＞3是质数的幂，并且P²(F_q)中的射影曲线由以下形式的等式给出

Y²Z＝X³+AXZ+BZ³

其中A，B∈F_q，并且4A³+27B²≠0。该曲线具有两个仿射部分：Z≠0的部分具有仿射型y²＝x³+Ax+B(通过设

x = \frac{X}{Z}

和

y = \frac{Y}{Z}

来获得)；而Z＝0的部分仅有一个(射影)点，即(0:1:0)，将其表示为O。设K是包含F_q的域(不一定是有限的)，则可给予集合

E(K)＝{(x，y)∈K×K：y²＝x³+Ax+B}∪{O}

阿贝尔群的结构，其中O作为该群的恒等式。此外，可有效地计算群运算，特别地，如果P，Q是E上的点且其坐标在F_q中，则可对任何ε＞0在O(log^1+εq)位的运算中计算P+Q和-p。Hasse法则给出了对群E(F_q)的大小的严密估算：

School-Elkies-Atkin算法是计算éE(F_q)的一种确定性多项式时间算法。

Weil配对

设E/F_q是一椭圆曲线，并设是F_q的代数闭包。如果m是对域F_q的特性相对为质数的整数，则m挠率(m-torsion)点的群

E [m] = {P &Element; E ({\bar{F}}_{q}) : mP = O}

具有以下结构：

E[m]＝Z/mZ×Z/mZ

存在映射e_m：

E [m] \times E [m] &RightArrow; {\bar{F}}_{q}^{*},

其具有以下性质：

·映射e_m是双线性的：

e_m(S₁+S₂，T)＝e(S₁，T)e(S₂，T)

e_m(S，T₁+T₂)＝e(S，T₁)e(S，T₂)

·交替：e_m(T，T)＝1，因此e_m(T，S)＝e_m(S，T)^-1。

·非退化：如果e_m(S，T)＝1，则对所有S∈E[m]，T＝O。

设E/F_q是一椭圆曲线，并设S，T是E上的两个m挠率点，其坐标在F_q中。则存在一可在O(logmlog^1+εq)位运算中对e_m(S，T)求值的确定性算法。当从上下文中清楚时，在写e_m时丢弃下标m。

网络编码模型

用于内容分发的标准网络编码框架如下。设G＝(V，E)是一有向图。源s∈V(例如，服务器102和/或客户机106)希望将某一数据(要分发的内容)发送到顶点的集合

T &SubsetEqual; V .

选择一向量空间W/F(例如维数为d)，并将要发送的数据(例如，分段内容)看作是向量w₁，…，w_k∈W的分支。源然后通过设来创建增广向量v₁，…，v_k，其中w_ij是向量w_i的第j个坐标。可不失一般性地假设向量v_i是线性独立的。用V来表示这些向量所跨的子空间(F_p ^k+d的)。每条边e∈E计算进入顶点v＝in(e)的向量的线性组合y(e)，即

y (e) = \underset{f : out (f) = v}{Σ} m_{e} (f) y (f)

其中m_e∈F_p。考虑源具有承载了k个向量w_i的k条输入边。通过归纳，得到任一条边上的向量y(e)是线性组合y(e)＝∑_1≤i≤kg_i(e)v_i，并且是V中的向量。k维向量g(e)＝<g₁(e)，…，g_k(e)>简单地是向量y(e)的前k个坐标。将其行是向量g(e₁)，…，g(e_k)的矩阵称为对于t的全局编码矩阵，并将其表示为G_t，其中e_i是对于t∈T的输入边。在实践中，随机地选择编码向量，因此矩阵G_t非常有可能是不可逆的。由此，任何接收器在接收到y₁，…，y_k时可通过求解下式来找到w₁，…，w_k

[\begin{matrix} y_{1} \\ y_{2} \\ \cdot \\ \cdot \\ \cdot \\ y_{k^{'}} \end{matrix}] = G_{t} [\begin{matrix} w_{1} \\ w_{2} \\ \cdot \\ \cdot \\ \cdot \\ w_{k^{'}} \end{matrix}],

其中y_i是通过去除向量y_i的前k个坐标而形成的向量。

示例性同态签名方案

网络编码模块116实现以下示例性同态签名方案。设p是一质数(示为“其它程序数据”120的相应部分)，而q是一不同质数的幂，且p＜＜q。设V/F_p是维数为d+k的向量空间，并设E/F_q是一椭圆曲线，使得R₁，…，R_k，P₁，…，P_d都是E(F_q)上的(不同)p挠率点。可定义一函数h_{R1，…，Rk，P1，…，Pd}：V→E(F_q)如下：对于v＝<u₁，…，u_k，v₁，…，v_d>∈V

h_{R_{1}, \cdot \cdot \cdot, R_{k}, P_{1}, \cdot \cdot \cdot, P_{d}} (v) = \underset{j}{Σ} u_{j} R_{j} + \underset{i}{Σ} v_{i} P_{i}

函数h_{R1，…，Rk，P1，…，Pd}是从向量空间V到曲线上的p挠率点(“其它程序数据”120的相应部分)的群E[p]的(加性阿贝尔群的)同态。

假设服务器102(或客户机106)希望将v₁，…，v_k∈V分发到客户机设备106，则服务器选择在F_p中为秘密的s₁，…，s_k和r₁，…，r_d。这些秘密被示为“其它程序数据”120的相应部分。服务器102然后通过计算下式来签署分组v_i(即，已签署块124)

h_{i} = h_{s_{1} R_{1}, \cdot \cdot \cdot, s_{k} R_{k}, r_{1} P_{1}, \cdot \cdot \cdot, r_{d} P_{d}} (v_{i})

服务器公布R₁，…，R_k，P₁，…，P_d，Q，s_jQ(1≤j≤k)以及r_iQ(1≤i≤d)(即，服务器公布“其它程序数据”120的数据部分)。此处Q是椭圆曲线上远离其它点的另一p挠率点，使得e_p(R_j，Q)≠1且e_p(P_i，Q)≠1(1≤j≤k且1≤i≤d)。

该签名h_j(即，同态数字签名122)也被追加到数据v_j并根据分发方案来发送。现在，在计算

y (e) = \underset{f : out (f) = in (e)}{Σ} m_{e} (f) y (f)

的任一条边e上，编码模块116还计算

h (e) = \underset{f : out (f) = in (e)}{Σ} m_{e} (f) h (f)

并将h(e)连同数据y(e)一起作为分组的线性组合来发送。由于签名h(e)的计算是同态，因此得到，如果y(e)＝∑_iα_iv_i，则

h (e) = \underset{i}{Σ} α_{i} h_{i}

示例性验证过程

接着描述由相应的客户机设备106实现的验证过程。假设y(e)＝<u₁，…，u_k，v₁，…，v_d>，则用于网络编码模块116-2的数字签名确定是否

\underset{1 \leq j \leq k}{Π} e (u_{j} R_{j}, s_{j} Q) \underset{1 \leq i \leq d}{Π} e (v_{i} P_{i}, r_{i} Q) = e (h (e), Q)

这能起作用，因为如果h(e)是y(e)的合法签名，则按照定义

h (e) = \underset{1 \leq j \leq k}{Σ} u_{j} s_{j} R_{j} + \underset{1 \leq i \leq d}{Σ} v_{i} r_{i} P_{i},

因而

e (h (e), Q) = e (\underset{1 \leq j \leq k}{Σ} u_{j} s_{j} R_{j} + \underset{1 \leq i \leq d}{Σ} v_{i} r_{i} P_{i}, Q)

= \underset{1 \leq j \leq k}{Π} e (u_{j} s_{j} R_{j}, Q) \underset{1 \leq i \leq d}{Π} e (v_{i} r_{i} P_{i}, Q)

(按照双线性性)

= \underset{1 \leq j \leq k}{Π} e (u_{j} R_{j}, s_{j} Q) \underset{1 \leq i \leq d}{Π} e (v_{i} P_{i}, r_{i} Q)

(再次按照双线性性)

验证使用Weil配对的双线性性。注意，以上验证中的所有项或者可从向量y(e)计算，或者可从公共信息中计算。

签名122是椭圆曲线上其坐标在F_q中的点，因此签名的大小为O(logq)位，并且这是传输开销。对签名h(e)的计算需要O(d_inlogplog^1+εq)位运算，其中d_in是in(e)的入度。对签名的验证需要O((d+k)logplog^1+εq)位运算。

安全性证明

上一节的表示法也在本节中使用。为妨碍所描述的签名方案，敌方或者可产生对函数h_{s1R1，…，skRk，r1P1，…，rdPd}的散列冲突，或者可伪造签名，使得验证能通过。注意，在这一情况下，敌方不知道点s₁R₁，…，s_kR_k和r₁P，…，r_dP_d。首先表明，即使敌方知道了这些点，产生冲突仍像计算离散对数那样困难。接着使得该主张更为精确：

问题：散列冲突。固定一整数r＞1。输入：给定椭圆曲线E/F_q上阶数为p(质数)的循环子群中的点P₁，…，P_r。输出：元组a＝(a₁，…，a_r)，

b = (b_{1}, \cdot \cdot \cdot, b_{r}) &Element; F_{p}^{r},

使得a≠b并且

\underset{1 \leq i \leq r}{Σ} a_{i} P_{i} = \underset{1 \leq j \leq r}{Σ} b_{j} P_{j}

命题1。存在从椭圆曲线上阶数为p的循环群上的离散对数到散列冲突的多项式时间减少。

证明：首先处理当r＝2的情况。设P和Q是E(F_q)上不为恒等式的阶数为p的点。假设Q位于由P生成的子群中。目标是找到a，使得Q＝aP，为此，将所声称的解决散列冲突的算法应用于点P和Q。该算法产生两个不同的对

(x, y), (u, v) &Element; F_{p}^{2},

使得

xP+yQ＝uP+vQ

这给出了关系式(x-u)P+(y-v)Q＝O。主张x≠u且y≠v。假设x＝u，则得到(y-v)Q＝O，但是Q是阶数为p(质数)的点，由此y-u≡0mod p，换言之，F_p中y＝v。这与(x，y)和(u，v)是F_p ²中的不同对矛盾。由此，得到Q＝-(x-u)(y-v)^-1P，其中取其逆来模p。

如果有r＞2，则可做以下两件事情。或者可如上一样取P₁＝P且P₂＝Q，并设P_i＝O，i＞2(在这一情况下，证明简化为r＝2的情况)，或者可取P₁＝r₁P且P_i＝r_iQ，其中r_i是从F_p中随机选择的。得到一个未知数中的一个等式(Q的离散对数)。所得到的等式相当有可能不包括该未知数。然而，这只有非常小的概率才会发生，如以下所讨论的。假设用于散列冲突的算法给出

a r_{1} P + \underset{2 \leq i \leq r}{Σ} b_{i} r_{i} Q = O

则只要

就可对Q的离散对数求解。但是r_i对用于散列冲突的谕示是未知的，因此可互换该过程进行的次序。换言之，给定b_i，对2≤i≤r，所选择的r_i满足∑_2≤i≤rb_ir_i＝0的概率是什么？很清楚，后者的概率是

由此，很有可能能对Q的离散对数求解。

还可从Bellare，M.、Goldreich，Q.、Goldwasser，S.的Incremental cryptography：The case of hashing and signing(增量密码学：散列和签署的情况)，Advancesin Cryptology CRYPTO′94，圣巴巴拉，加利福尼亚州，1994中所提出的证明来得出以上命题的结论。该证明处理了有限域，但是论点同样适用于椭圆曲线的情况。

已经表明了在由用于网络编码模块116的数字签名实现的方案中产生散列冲突是很困难的。敌方可用来阻挡该方案的其它方法是通过伪造签名。然而，伪造签名至少与求解所谓的椭圆曲线上的计算性共Diffie-Hellman(co-Diffie-Hellman)问题一样困难。解椭圆曲线上的这一问题的唯一已知的方法是通过计算离散对数。由此，伪造签名至少与求解椭圆曲线上的计算性共Diffie-Hellman一样困难，并且很可能与计算离散对数一样困难。

示例性设置

以上在描述网络编码模型和示例性通体签名方案时所提出的表示法也在本节中使用。为初始化该签名方案，图1的模块116选择一质数p以及如以下所述的合适域上其整个p挠率在该域上定义的椭圆曲线。选择椭圆曲线的示例性技术在以下题为“找出合适的椭圆曲线”一节中描述。模块116还标识定义同态签名122所需的一组p挠率点。在本节中，讨论所有这些问题并还提供一示例。

概括而言：

·选择一大质数p。

·选择一合适的质数(如下在题为“找出合适的椭圆曲线”一节中所描述)l以及F_l上具有p的倍数的点的椭圆曲线E。

·找出域F_l的扩展F_q，使得

E [p] &SubsetEqual; E (F_{q})

(此处E[p]指所有p挠率点的集合)。

·由于éE(F_l)≡0mod p，其具有p挠率点。设O≠P∈E(F_l)是该曲线上的p挠率点。取R_i＝a_iP(1≤i≤k)且P_j＝b_jP(1≤j≤d)，其中a_i和b_i是从集合1，…，p-1中随机选取的。

·Q是使得e(R_i，Q)≠1且e(P_i，Q)≠1的点。为确保这一点，选取在F_q上定义但不在较小的域F_l上定义的p挠率点是足够的。实际上，设Q是这样的一个点，则如果e(R_i，Q)＝1，这意味着对任意A，B∈E[p]，e(A，B)＝1(由于R_i和Q生成E[p])，这与Weil配对的非退化性矛盾。

·最后，模块116从F_p ^*中随机地选择密钥s₁，…，s_k和r₁，…，r_d。

找出合适的椭圆曲线

一般而言，如果有了有限域K上的椭圆曲线E，则可在域K上次数为Θ(p²)的扩展上定义p挠率点。p挠率点是在一小的域上定义的，使得模块116的运算可在多项式时间中进行。在本节中，讨论可如何选取合适的域F_l以及该域上其所有p挠率点都被定义在基域的小的相对扩展上的椭圆曲线。

已知的椭圆曲线的复乘理论可用于生成有限域上具有特定数量的点的椭圆曲线。关于该算法的细节对于此处的使用并不是必需的，但是利用了其运行时间，因此接着将描述该算法。假设希望产生恰好有N个点的椭圆曲线E/F_l(其中l是质数)，其中N落入区间

l + 1 - 2 \sqrt{l} \leq N \leq l + 1 + 2 \sqrt{l}

中。将N写为l+1-t并设Dy²＝t²-4l，其中D或D/4是无平方的(squarefree)(注意由于Hasse界限，D是负的)。因此，产生这一椭圆曲线的算法在时间|D|^O(1)内运行。

在系统100中，寻找具有p的较小倍数的点的椭圆曲线，这表明其上应寻找这一曲线的域F_l必须具有

l + 1 - 2 \sqrt{l} \leq mp \leq l + 1 + 2 \sqrt{l} .

另外，t²-4l应具有小的无平方部分，因为这确定了生成这一曲线的方法的运行时间。选择质数l，使得对小(负)D，4l＝4p²-Dy²，并且l≡-1mod p；并设t＝2p。由此，l+1-t＝l+1-2p≡0mod p，且因此椭圆曲线上的点的个数将是p的倍数，并且因为|D|较小，产生这一曲线的时间将是合理的。

为产生这一质数l，选择(负)D(|D|较小)。确定1/4(p²-Dy²)是否为质数，y＝0，1，…。由于仅对≡-1mod p的质数感兴趣，因此以上检查仅对使得-Dy²≡-4mod p的哪些y值进行。Lang-Trotter猜想表明将存在产生质数的许多y值。这也涉及关于二次多项式的质数值的Hardy-Littlewood猜想。现在，复乘法产生了F_l上具有某些p挠率点的椭圆曲线E。然而，需要使得E[p]被定义在F_l的小次数扩展上的椭圆曲线。这就是使用附加约束l≡-1mod p之处。由于l≡-1mod p，F_p ^*中l的阶数为2。现在，Koblitz-Balasubramanian法则表明在这一情况下，全部p挠率点是在基域的次数为2的扩展上定义的，换言之

E [p] &SubsetEqual; F_{l^{2}} .

现在，得到椭圆曲线E/F_l(“其它程序数据”120的相应部分)，并且知道其所有p挠率点都被定义在E[l]上，但是如何找出这些点？这是下一段的主题。

评论1。复乘理论表明，曲线E仅依赖于量D。更精确地，对每一D，存在一数字域K上的椭圆曲线的有限列表E₁，…，E_m，使得Emodl满足此处的要求。这在以下题为“示例”一节中示出。

找出p挠率点

设E/F_l为使用以上给出的方法标识的椭圆曲线。则éE(F_l)＝l+1-2p，且设m是éE(F_l)的最大约数，其对p相对是质数。设P是曲线E(F_l)上的一个随机点。假设mP≠O，则mP是p次方挠率的点(按照Lagrange法则)。设i≥1为使得mpⁱP＝O但mp^i-1P≠O的最小整数。则mp^i-1P是一个p挠率点。当然，如果找到mP＝O，则通过找出另一随机点P来重复。对一随机点P，mP＝O的概率最多是

并且因此，将很有可能找到非平凡p挠率点。

这给出了在F_l上定义的p挠率部分。为找到在F_l2上定义的p挠率部分，在F_l2上重复以上过程。为执行这一过程，需要知道E(F_l2)上点的个数。看上去如果E是在有限域K上定义的，则K的任何扩展上E上的点的个数由éE(K)来确定。该理论预测对于此处的曲线E，其中α，

是以下等式的两个根(C中)

φ²-2pφ+l＝0

示例

本示例是使用计算机代数包MAGMA来产生的。对于本示例，取D＝-4。对于任何质数p，合适的质数l是满足4l＝4p²+4y²的l，使得l≡-1mod p。该全等意味着y²＝-1mod p，换言之-1应是模p的二次余数。这进而意味着p≡1mod 4，并且需要搜索的y的值应全等于-1mod p的平方根之一。

设p是如下质数：

26330018368571742206574632566065508402231508999153

搜索具有特殊性质的p²+y²的质数值。复乘法表明，椭圆曲线

E：y²＝x³+x(仿射型)

是一合适的椭圆曲线。MAGMA表明éE(F_l)是：

3516881927290816899634862215683448167044556755196219863066511191456976613264142

847616337439963943072004，

这实际上≡0mod p。根据MAGMA，E(F_l2)上的点的个数为

1236845849050477072586861412005782314655826646818745936122594860084650180144846

0142653837393007842909634176991355780216434931187550854726269234703885776384142

268869493894468081319453336772812036965744626464，

并且这≡0mod p²，这是E[p]为E(F_l2)的子群的必要条件。通过找出生成p挠率子群的两个点来示出E[p]实际上包含在E(F_l2)中。遵循在§5.2中概述的方法，找出生成E(F_l2)的整个p挠率的两个p挠率点P和Q

P＝(276701049983509532234106338452082440292711762773463732533683876759414814860205

8330843763239769722154862，736895619074862870441993260428363309212341952700619

999020137331297834986221601940750818713297548511336)

Q＝(170343693342782875614389009934880452275069084044323551866473740367532495756430

3078396992524604785250333u+15712887469866185499501681171672209515250776009

77567312986377817436996986291386148589353156799909434396，

293262979414624776596432402939618431893907517428095829765520553326321029472

565240814005665686795414190u+28272291365284541630011849371574061637952

191623737718932812446648142173368705416653836715431228856385081)。

此处，u是给出对二次不可约f∈F_l[u]的同形

F_{l^{2}} &cong; F_{l} [u] / (f (u))

的变量。P和Q的Weil配对为

e_p(P，Q)＝18803618029983537254653390382035462993205409477769908010460

37660415779359581593172656075406185808275672u+

31284655683961117025378938265048897550540714

78912095275807108199402549356171889616725860797979581965315。

示例性过程

图2示出了根据一个实施例的用于网络编码的数字签名的示例性过程200。出于示例性描述的目的，过程200的操作相对于图1的系统100的组件来描述。一组件参考标号最左边的数字指示首次描述该组件的特定附图。

在框202处，服务器102用相应的同态数字签名122(图1)来数字地签署要分发的内容的一组分段块中的相应块。这是通过将向量(例如，分段块的相应块)变换成椭圆曲线上的一组点来实现的。这些变换是使用作为从向量空间到一椭圆曲线上的一组质数挠率点的(加性阿贝尔群的)同态的抗冲突散列函数来执行的。

在框204处，服务器102将分组连同封装在该分组内的用于签署分段内容的公共信息(例如，椭圆曲线上某些不同质数(p)挠率点)一起通过网络104分发到目的地设备(例如，相应的客户机设备106)。分组和信息是使用一分发方案来分发的。在一个实现中，该分发方案是网络编码分发方案。诸如密钥和散列摘要等在框202的操作中用于数字地签署分段内容(即，向量)的秘密信息不被服务器102随分组的线性组合和公共信息分发。

在框206处，客户机设备106接收所分发的分组的线性组合中的一个或多个。在框208处，客户机设备106使用由服务器连同所接收的分组一起分发的公共信息来验证并认证封装在所接收的分组内的内容。在框210处，客户机设备106确定它是否是接收该所接收分组的最终目的地设备。如果不是，则操作在框202处如上所述地继续，其中客户机设备106实际上变为服务器102。更具体地，在这一情形中，客户机设备106知道了分组的线性组合中的某一些的数字签名之后，可产生分组的任何线性组合(即，所接收的分组)的签名。这允许客户机设备106数字地重新签署该分组而无需联系源(即，在此次迭代中，为服务器102)。另外，这允许客户机设备检测恶意地声称已发送了输入的线性组合，而实际上注入了某些其它数据或无用信息的任何节点(例如，服务器102和/或客户机106)。考虑到这一点之后，客户机设备以新的线性组合分发重新签署的分组以及用于数字地签署该分段块的相关联的公共信息到目的地设备。框202到210的操作由任何数量的服务器102和客户机设备106迭代地重复，直到所分发的内容到达目的地设备。

示例性操作环境

图3示出了在其中全部或部分地实现用于网络编码的数字签名的合适的计算环境的一个示例。示例性计算环境300仅为用于图1的示例性系统和图2的示例性操作的合适的计算环境的一个示例，并非对此处所描述的系统和方法的使用范围或功能提出任何局限。也不应将计算环境300解释为对计算环境300中示出的任一组件或其组合具有任何依赖或需求。

此处所描述的方法和系统可以使用众多其它通用或专用计算系统、环境或配置来操作。适合使用的众所周知的计算系统、环境和/或配置的示例包括但不限于：个人计算机、服务器计算机、多处理器系统、基于微处理器的系统、网络PC、小型机、大型机、包括任一上述系统或设备的分布式计算环境等等。该框架的紧凑或子集形式也可以在诸如手持式计算机或其它计算设备等有限资源的客户机中实现。本发明可以在其中任务由通过通信网络链接的远程处理设备来执行的分布式计算环境中实践。在分布式计算环境中，程序模块可以位于本地和远程存储器存储设备中。

参考图3，用于网络编码的数字签名的示例性系统包括实现例如图1的系统100的计算机310形式的通用计算设备。以下所描述的计算机310的各方面是图1的计算设备102和104的示例性实现。计算机310的组件可包括但不限于，处理单元320、系统存储器330以及将包括系统存储器的各类系统组件耦合至处理单元320的系统总线321。系统总线321可以是若干种总线结构的任一种，包括存储器总线或存储器控制器、外围总线以及使用各类总线体系结构的任一种的局部总线。作为示例而非局限，这类体系结构包括工业标准体系结构(ISA)总线、微通道体系结构(MCA)总线、增强型ISA(EISA)总线、视频电子技术标准协会(VESA)局部总线以及外围部件互连(PCI)总线(也称为小背板(Mezzanine)总线)。

计算机310通常包括各种计算机可读介质。计算机可读介质可以是可由计算机310访问的任一可用介质，包括易失性和非易失性介质、可移动和不可移动介质。作为示例而非局限，计算机可读介质包括计算机存储介质和通信介质。计算机存储介质包括以用于储存诸如计算机可读指令、数据结构、程序模块或其它数据等信息的任一方法或技术实现的易失性和非易失性，可移动和不可移动介质。计算机存储介质包括但不限于，RAM、ROM、EEPROM、闪存或其它存储器技术、CD-ROM、数字多功能盘(DVD)或其它光盘存储、磁盒、磁带、磁盘存储或其它磁存储设备、或可以用来储存所期望的信息并可由计算机310访问的任一其它介质。

通信介质通常以诸如载波或其它传输机制等已调制数据信号来体现计算机可读指令、数据结构、程序模块或其它数据，并包括任一信息传送介质。术语“已调制数据信号”指以对信号中的信息进行编码的方式设置或改变其一个或多个特征的信号。作为示例而非局限，通信介质包括有线介质，如有线网络或直接连线连接，以及无线介质，如声学、RF、红外和其它无线介质。上述任一的组合也应当包括在计算机可读介质的范围之内。

系统存储器330包括易失性和/或非易失性存储器形式的计算机存储介质，如只读存储器(ROM)331和随机存取存储器(RAM)332。基本输入/输出系统333(BIOS)包括如在启动时帮助在计算机310内的元件之间传输信息的基本例程，它通常储存在ROM 331中。RAM 332通常包含处理单元320立即可访问和/或当前正在操作的数据和/或程序模块。作为示例而非局限，图3示出了操作系统334、应用程序333、其它程序模块336和程序数据337。

计算机310也可包括其它可移动/不可移动、易失性/非易失性计算机存储介质。仅作示例，图3示出了对不可移动、非易失性磁介质进行读写的硬盘驱动器341，对可移动、非易失性磁盘332进行读写的磁盘驱动器331，以及对可移动、非易失性光盘336，如CD ROM或其它光介质进行读写的光盘驱动器333。可以在示例性操作环境中使用的其它可移动/不可移动、易失性/非易失性计算机存储介质包括但不限于，磁带盒、闪存卡、数字多功能盘、数字录像带、固态RAM、固态ROM等等。硬盘驱动器341通常通过不可移动存储器接口，如接口340连接到系统总线321，磁盘驱动器331和光盘驱动器333通常通过可移动存储器接口，如接口330连接到系统总线321。

上文讨论并在图3示出的驱动器及其关联的计算机存储介质为计算机310提供了计算机可读指令、数据结构、程序模块和其它数据的存储。例如，在图3中，示出硬盘驱动器341储存操作系统344、应用程序343、其它程序模块346和程序数据347。注意，这些组件可以与操作系统334、应用程序333、其它程序模块336和程序数据337相同，也可以与它们不同。应用程序333包括，例如图1的程序模块122。程序数据337包括，例如图1的程序数据114。这里对操作系统344、应用程序343、其它程序模块346和程序数据347给予不同的标号来说明至少它们是不同的副本。

用户可以通过输入设备，如键盘362和定位设备361(通常指鼠标、跟踪球或触摸垫)向计算机310输入命令和信息。其它输入设备(未示出)可包括话筒、操纵杆、游戏手柄、圆盘式卫星天线、扫描仪等等。这些和其它输入设备通常通过耦合至系统总线321的用户输入接口360连接至处理单元320，但是也可以通过其它接口和总线结构连接，如并行端口、游戏端口或通用串行总线(USB)。

监视器391或其它类型的显示设备也通过接口，如视频接口390连接至系统总线321。除监视器之外，计算机也可包括其它外围输出设备，如打印机396和音频设备397，它们通过输出外围接口393连接。

计算机310可以使用到一个或多个远程计算机，如远程计算机380的逻辑连接在网络化环境中操作。在一个实现中，远程计算机380表示图1的计算设备102或联网计算机104。远程计算机380可以是个人计算机、服务器、路由器、网络PC、对等设备或其它常见的网络节点，并且作为其特定实现的功能可以包括许多或所有相对于计算机310所描述的元件，尽管在图3中仅示出了存储器存储设备381。图3描述的逻辑连接包括局域网(LAN)371和广域网(WAN)373，但也可包括其它网络。这类网络环境常见于办公室、企业范围计算机网络、内联网以及因特网。

当在LAN网络环境中使用时，计算机310通过网络接口或适配器370连接至LAN 371。当在WAN网络环境中使用时，计算机310通常包括调制解调器372或用于通过WAN 373，如因特网建立通信的其它装置。调制解调器372可以是内置或外置的，它通过用户输入接口360或其它适当的机制连接至系统总线321。在网络化环境中，相对于计算机310所描述的程序模块或其部分可储存在远程存储器存储设备中。作为示例而非局限，图3示出远程应用程序383驻留在存储器设备381上。可以理解，示出的网络连接是示例性的，也可以使用在计算机之间建立通信链路的其它手段。

结论

尽管以对结构特征和/或方法操作或动作专用的语言描述了用于网络编码中的数字签名的系统和方法，但可以理解，所附权利要求书中所定义的实现并不一定限于所描述的具体特征或动作。相反，系统100的具体特征和操作是作为实现所要求保护的主题的示例性形式来公开的。

Claims

1.一种使用数字签名的网络编码内容分发方法，包括：

使用相应的同态数字签名来数字地签署一组分段内容块的相应块以创建经数字地签署的内容块，所述数字地签署包括：使用散列函数将分组的线性组合中的相应分组的向量变换成椭圆曲线上的一组点，所述散列函数是从一向量空间到所述椭圆曲线上的一组质数挠率点的同态散列函数，根据输入的散列值计算输入消息的线性组合的散列，所计算的散列基于椭圆曲线的理论用于签名方案中以进行数字地签署要分发的分段内容块；

使用一分发方案来将分组的线性组合分发到目的地设备，所述分组的线性组合包括所述经数字地签署的内容块以及用于数字地签署所述分段内容块中的相应块的公共信息；以及

其中，所述同态数字签名和所述公共信息允许，接收所述分组的线性组合中的一个或多个分组的设备，独立于用于数字地签署该一个或多个分组的密钥和散列摘要的安全传输，来验证并认证与所述分组之一相关联的内容。

2.如权利要求1所述的方法，其特征在于，所述分发方案是网络编码内容分发方案。

3.如权利要求1所述的方法，其特征在于，所述公共信息包括用于签署相应分组的不同于所述一组质数的质数以及椭圆曲线上的点。

4.如权利要求1所述的方法，其特征在于，所述同态数字签名和所述公共信息允许，接收所述分组的线性组合中的一个或多个分组的设备，独立于联系该一个或多个分组的源，来重新签署与所述分组的线性组合的任何子集相关联的内容，所述重新签署的内容用于随后以新的线性组合分发到所述目的地设备，并用于随后由不是目的地设备的任何中间客户机设备来验证和认证并分发。

5.如权利要求1所述的方法，其特征在于，数字地签署还包括使用一抗冲突散列函数将各分组的向量变换成椭圆曲线上的一组点，所述散列函数是从一向量空间到所述椭圆曲线上的一组质数挠率点的同态。

6.一种使用数字签名的网络编码内容分发的系统，所述系统包括：

用于使用相应的同态数字签名来数字地签署一组分段内容块的相应块以创建经数字地签署的内容块的装置，所述数字地签署包括：使用散列函数将分组的线性组合中的相应分组的向量变换成椭圆曲线上的一组点，所述散列函数是从一向量空间到所述椭圆曲线上的一组质数挠率点的同态散列函数，根据输入的散列值计算输入消息的线性组合的散列，所计算的散列基于椭圆曲线的理论用于签名方案中以进行数字地签署要分发的分段内容块；

用于使用一分发方案来将分组的线性组合分发到目的地设备的装置，所述分组的线性组合包括所述经数字地签署的内容块以及用于数字地签署所述分段内容块中的相应块的公共信息；以及

7.如权利要求6所述的系统，其特征在于，所述分发方案是网络编码内容分发方案。

8.如权利要求6所述的系统，其特征在于，所述公共信息包括用于签署各分组的不同于所述一组质数的质数以及椭圆曲线上的点。

9.如权利要求6所述的系统，其特征在于，所述同态数字签名和所述公共信息允许，接收所述分组的线性组合中的一个或多个分组的设备，独立于联系该一个或多个分组的源，来重新签署与所述分组的线性组合的任何子集相关联的内容，所述重新签署的内容用于随后以新的线性组合分发到所述目的地设备，并用于随后由不是目的地设备的任何中间客户机设备来验证和认证并分发。

10.如权利要求6所述的系统，其特征在于，所述系统还包括用于使用一抗冲突散列函数将各分组的向量变换成椭圆曲线上的一组点的装置，所述散列函数是从一向量空间到所述椭圆曲线上的一组质数挠率点的同态。