基于椭圆曲线参数化的加密方法

摘要

本发明涉及由控制器(11)根据密码(π)来控制装置(10)的实施方法。为此目的，本发明包括在装置或控制器处，根据随机数值r1来确定在椭圆曲线上有限区域F

说明书

本发明涉及基于使用椭圆曲线上的点进行信息加密的方法，尤其 适用于EKE(密钥交换)类型的算法领域。

利用密码的授权方法是基于使用EKE类型的算法。图1图示说 明了这类算法。

装置D10根据控制器C11的密码π进行授权。这些单元都知道 密码π。然而，考虑椭圆曲线E_a，b和产生在椭圆曲线上的一系列点的 生成函数G，作为公用参数。所述椭圆曲线满足下列等式：

E_a，b(x，y)：x³+ax+b＝y²    (1)

在步骤12中，装置D10生成随机数值r₁。然后，装置D将该随 机数值以椭圆曲线上的点的形式传输至控制器11。为此目的，确定待 传输的数值V应满足下列：

V＝r₁.G

然后，以E_π(r₁.G)形式的密码对结果进行加密，其中E_π是密码的加 密函数。

然后，所述装置将信息13发送至控制器并记为数值E_π(r₁.G)。

一旦接收到信息13，控制器11依次在步骤14中产生随机数值 r₂；接着，再以椭圆曲线上点的形式来传输该数值，并将信息15传 输至装置10，记为结果：E_π(r₂.G)。

以加密形式实现随机数值r₁和r₂的交换之后，装置10在步骤16 中通过使用具有密码D_π的解密函数解密信息15所包含的信息，来恢 复控制器所产生的随机数值r₂：

r₂.G＝D_πE_π(r₂.G)

以及控制器11在步骤17中通过解密信息13所包含的信息来恢 复装置10所产生的随机数值r₁：

r₁.G＝D_πE_π(r₁.G)

接着，进行保护的交换，各个单元能够计算公用密钥K：

K＝r₁.r₂.G

这种类型的算法旨在以密码或由密码产生的密钥进行加密的形 式来交换数值。然而，需要注意的是，根据椭圆曲线在有限区域F_q内满足等式(1)的典型表达式，参考图1所述的交换允许潜在的破 解者推算出关于密码π的信息。实际上，通过两个信息13和15，以 上述加密形式来交换随机数值，可提供允许破解密码加密的信息冗 余。更具体的是，破解者可在各个监听过程中检测密码，以便解密信 息13和15所交换的信息。此后会出现两种情况。在第一种情况下， 解密信息对应于曲线上的点并因密码正确。在第二种情况下，解密信 息不对应于椭圆曲线上的点且也不能获得密码。通过增加监听和分辨 密码，也有可能发现属于有限元素集的密码。

本发明旨在改善上述状况。

本发明的第一方面在于提出一种由控制器根据密码控制装置的 方法；

所述方法在所述装置处或控制器处包括下列步骤：

/1/根据任意数值r₁，确定椭圆曲线上的有限区域F_q的点P(X，Y)， 其中q为整数，椭圆曲线满足下列等式：

E_a，b(x，y)：x³+ax+b＝y²    (1)

/2/获得第一和第二参数k和k′，使之：

P＝F(k，k′)

其中F为F_q域内的F_qxF_q′的满射函数；

/3/通过以密码函数进行加密的加密形式的第一和第二参数；以 及，

/4/将所述第一和第二加密参数传输至控制器；

其中，不论F_q的输入参数z和z′如何，函数F都使得F(z，z′)为 在椭圆曲线上的点且输入参数不满足等式(1)。

籍助于这些设置，就有可能避免诸如上述现有技术的破解。实际 上，在这些条件下，不再有可能通过确定所获得的结果是否对应于椭 圆曲线E_a，b上的点(X，Y)来测试密码，因为函数F始终能提供在椭圆曲 线上的点作为输出而与作为输入所提供的参数无关，且输入参数不再 满足椭圆曲线的典型等式。因此，较为理想的是，使用该满射函数F 以不同方式来表示椭圆曲线上的点，就不会向潜在破解者提供任何有 可能推导出所使用密码的信息。

为了根据除了等式(1)以外的其它参数化方法来确定满足待表示 的椭圆曲线上的点P(X，Y)的函数F，有可能使用可逆函数f_a，b，使用 所述函数的逆函数f_a，b^-1有可能根据不满足等式(1)的两个参数从输入参 数中恢复曲线上的点。

函数F可以表示为：

F(k，k′)＝f′(k′)+f_a，b(k)

其中f_a，b为可逆函数，可基于椭圆曲线的系数a和b，来选择输 入参数和提供在椭圆曲线上的点；

而f′为根据参数的函数来产生在椭圆曲线上的点的函数；以及，

在步骤/2/中，由下列步骤获得参数k和k′：

-随机产生参数k′的数值；

-计算f′(k′)的数值

-根据下列等式确定参数k的数值：

$k=f_{a,b}^{-1}(P(X,Y)-f^{\prime }\left(k^{\prime }\right))$

优选地，通过将函数f′与可逆函数f_a，b相结合，所述函数f′有可能 根据随机数值的参数k′来产生椭圆曲线上的点，所述可逆函数f_a，b基 于椭圆曲线的系数a和b，从而有可能获得函数F，所述函数F允许 曲线上的点参数化，从而避免上述破解。

函数f′可具体表示为：

f′(k′)＝k′.G

其中G为在椭圆曲线上的一系列点的生成函数，并且参数k的数 值由下列等式确定：

$k=f_{a,b}^{-1}(P(X,Y)-k^{\prime }.G)$

在这些条件下，函数F可表示为：

F(k，k′)＝f_a，b(k)+k′.G

另外，函数f′可表示为：

f′(k′)＝f_a，b(k′)

以及，参数k的数值由下列等式确定：

$k=f_{a,b}^{-1}(P(X,Y)-f_{a,b}\left(k^{\prime }\right))$

在这些条件下，函数F可表示为：

F(k，k′)＝f_a，b(k)+f_a，b(k′)

于是，一般而言，根据本发明，为了对曲线上的点P(X，Y)进行参 数化，则第一步应获得对应于参数k′数值的曲线上的点。接着，确定 在曲线上的点，其对应于所要表示的点P(X，Y)和步骤1所获得的点 的减法。随后，获得在椭圆曲线上的另一个点。接着，再对该点使用 f_a，b逆函数并获得参数k的数值。然后，该点P以k和k’的参数对形 式来表示且不满足等式(1)。

在本发明的一个实施例中，函数F至少包括一个可逆函数f_a，b， 使之：

$\forall P=(X,Y)\in E_{a,b},\left|f_{a,b}^{-1}(X,Y)\right|<L$

其中L为具有相对于椭圆曲线上的点的数量足够小数值的整数。

实际上，函数F包括函数f_a，b，即意味着将函数F应用于第一和 第二参数对应于将函数f_a，b应用于第一和第二参数中的至少一个。于 是，一方面，可根据第一参数来产生曲线上的点；另一方面，可应用 f_a.b逆函数来获得第二参数。通过执行该流程，就可根据这两个参数来 表示椭圆曲线上的点。

因此，将函数F应用于第一和第二参数可对应于将函数f_a，b应用 于两个参数中的至少一个，使之：

$\forall P(X,Y)\in E_{a,b},\left|f_{a,b}^{-1}(X,Y)\right|<L---\left(4\right)$

其中，L为具有相对于椭圆曲线(1)上的点的数量足够小数值的 整数。

换句话说，这里所考虑的函数f_a，b具有对应于椭圆曲线E_a，b上的 一系列点P的原图像，所述椭圆曲线E_a，b由相对椭圆曲线上的点的数 量足够小的最大数值作为边界。实际上，如果不采用这样的方法，也 有可能简单地通过随机选择数量使得函数f_a，b取反。在这样的情况下， 可以考虑例如L小于曲线上点的数量的1/2⁸⁰。

通过使用满足条件(4)的可逆函数，能容易地通过参数k和k′来 获得表示曲线上的点的函数F，所述参数k和k′不允许破解对其进 行加密的密码，正如以上所述。

在本发明的一个实施例中，函数f_a，b使得参数对(x，y)对应于参数 u且x为下列等式的唯一解：

x³+ax+b-(ux+Q(u，a，b))²＝0    (5)

以及y满足：

y＝u.x+Q(u，a，b)

等式(5)通过以ux+Q(u，a，b)项替换等式(1)中的y来获得。项Q(u，a，b) 表示变量u、a和b的有理分式。

实际上，该等式(5)仅允许单根等效于下列项的判别表达式Δ(u，a，b) 不是平方项且与参数u无关：

x³+ax+b-(ux+Q(u，a，b))²

若q＝2 mod 3，可表示为：

Δ(u，a，b)＝-3R(u，a，b)²

式中R为有理分式。

实际上，若p＝2mod3，则-3就不是平方项且因此-3R(u，a，b)²也一 定不会是平方项。

由于等式(5)仅允许单根，所以下列项为1次多项式：

gcd(x³+ax+b-(ux+Q(u，a，b))²X^P-X)

式中gcd为最大公分母。

该多项式的根记为X_P，是椭圆曲线上的点的横坐标。最后，横 坐标为X_P和纵坐标为u.X_P+Q(u，a，b)的点就是椭圆曲线上的点。

在一个实施例中，讨论满足下列等式的有理分式Q(u，a，b)：

$Q(u,a,b)=\frac{236196u^2\mathrm{ab}+405u^{8}a-20412u^{6}b-45927u^4{a}^2-u^{12}+19683a^3}{54u(-162a{u}^4+2187a^2-u^8+2916b{u}^2)}$

在一个实施例中，函数f_a，b有利于在F_q(q＝2 mod 3)域内进行 定义，以便参数对(x，y)对应于参数u，使之：

x＝(v²-b-u⁶/27)^1/3+u²/3

以及

y＝u.x+v

其中$v=\frac{3a-u^4}{6u}=Q(u,a,b)$

以及f_a，b(0)＝0。

该函数是可逆的。于是，对于椭圆曲线上的点P(X，Y)而言，函数 f_a，b给出的点的原图为下列等式的解：

u⁴-6u²x+6uy-3a＝0

现在，这类多项式等式可以很容易地进行取反。

此外，函数f_a，b的一系列原图点p是由L作为边界的，L相对于 椭圆曲线上的点的数量足够小的数值。

因此，该函数满足上述定义的特征。

可以假设函数F是基于函数f_a，b的使用，而所述函数f_a，b根据满足 Skalba等式的多项式进行定义。

值得注意的是，满足Skalba等式的多项式在Maciej Ulas于2007 年6月11日发表的文章“Rational points on certain hyperelliptic curves  over finite fields”中作了定义。这些函数都是可逆的。实际上，给定 的多项式X₁(k)、X₂(k)、X₃(k)和U(k)满足Skalba等式，即满足

f(X₁(k)).f(X₂(k)).f(X₃(k))＝U(k)²

其中f为定义椭圆曲线E_a，b的多项式。

更具体的是，f满足等式：

f(x)＝y²

其中x和y是F_q²的元素且该对(x，y)表示为E_a，b上的点。

f_a，b(k)由点P＝(X_i(k)，f(X_i(k))^1/2)进行定义，其中i使得f(X_i(k))为 在F_q域内的平方项。因此，对给定点P＝(X，Y)进行函数f_a，b取反，可 计算三个多项式等式的解k_s：

X₁(k_s)-X＝0

X₂(k_s)-X＝0

X₃(k_s)-X＝0

这些解各自都是f_a，b所给定P的原图。

若F(k，k′)可表示为：

F(k，k′)＝f_a，b(k)+f_a，b(k′)

则可优选获得所述点的均匀的分布，即，对输入数值的均匀分布 的f_a，b输出数值。在这样的情况下，如果输入数值是随机确定的，那 么输出数值也具有随机的分布。

通过执行这样的操作，有可能避免基于能够提供信息的参数所使 用数值的统计分析的破解。实际上，若基于椭圆曲线上的点p的函数 f_a，b的取反逆变换对应于该逆函数的输入参数的多个数值，则在这种情 况下，有可能获得比根据统计规律的其它方法更多的那些数值。于是， 破解者知道统计规律，通过基于所交换的信息来测试密码，就可判定 所交换的参数数值是否遵循该规律。因此，由此可推导出所检测的这 些密码是正确与否。

为了避免这种类型的破解，有利于采用下列算法。

D_i表示为在椭圆曲线E_a，b上的一系列点，其具有由函数f_a，b给出 原图像的准确数量i。在下列实例中，5个点集表示为：D₁、D₂、D₃、 D₄和D₅。

GEN表示随机和均匀分布地产生椭圆曲线上的点的函数。使 即，与集D_i相关的概率。

若t＝0(在T-1处)，其中T为整数，则

-产生函数GEN的点P_t；

-如果P_t为D0的元素，则返回至起始处，

-如果Pt为Di的元素，则：

○随机选择在0至1之间的数值且满足：

Pr(b＝0)＝δ_i

○如果b等于1，则返回步骤(1)

○否则

-随机选择在集中的一个元素u

-返回u

值得注意的是，为了获得1-1/2^k的成功概率，需要使得T等于 1阶k评估的多项式，换句话说，T为k的多项式。

此外，可以执行下列步骤：

-接收由密码加密形式所表述的第一和第二参数；

-解密第一和第二参数并且获得参数p和p′；以及，

-由控制器根据下列等式计算公用加密数值K：

K＝r₁.F(p，p′)

其中r₁为在步骤/1/中所使用的随机数值。

因此，所述装置和控制器最终可具有它们所能支配的公用密钥， 而不需交换将密码秘密处于危险中的信息。

本发明的第二方面提出一种电子实体，其包括适用于执行根据本 发明第一方面的控制方法的部件。

本发明的第三方面提出一种由密码控制的系统，其包括作为控制 器的根据本发明第二部分的第一电子实体，以及作为被控制装置的根 据本发明第二部分的第二电子实体。

本发明的其它方面和优点将通过对下列实施例的讲解变得明晰。

本发明还可以籍助于下列附图获得更好的理解。

-图1示出了根据现有技术的控制方法的主要步骤且已经作 了讨论；

-图2示出了根据本发明一个实施例的控制方法的主要步 骤；

-图3示出了根据本发明一个实施例在装置和控制器之间实 施的控制方法；以及，

-图4示出了根据本发明一个实施例的装置和控制器。

图2示出根据本发明一个实施例的控制方法的主要步骤。

在步骤21中，根据随机数值r₁来确定在椭圆曲线有限区域F_q(q为整数)内的点P＝(X，Y)。随后，在步骤22中，获得第一和第二 参数，使之：

P＝F(k，k′)

其中F为诸如在F_q域内F_q x F_q′的满射函数。

因此，所获得的参数使之有可能有利的表示点P，从而在装置和 控制器交换的过程中保护密码的秘密。

在步骤23中，获得第一和第二参数且采用以密码π的函数E_π(k，k′) 进行加密的加密形式。

采用这样有利的形式，有利于在步骤24中将随机数值r₁从待控 制的装置传输至控制器或从控制器传输至待控制装置，以便产生密码 公用密钥。

函数F使得，无论F_q的元素z和z′如何，F(z，z′)都为椭圆曲线上 的点且z和z′元素不满足等式(1)。

图3示出了根据本发明一个实施例在待控制的装置10与控制器 11之间的信息交换。

首先，待控制的装置D10在步骤31中产生随机数值r₁。当在椭 圆曲线上的点集序列为整数N时，则可以由数值集[0，N-1]随机选择 r₁。

然后，从该随机数值开始，使用生成函数产生在椭圆曲线E_a，b上 的点P＝(X，Y)。所述生成函数使得对在椭圆曲线上的任何点p，都有 数值h，使之：

P＝h.G

于是，获得P₁，使之：

P₁＝r₁.G

随后，在步骤33中，确定参数k₁和k₁′的数值，以根据不同的坐 标X和Y的参数来表示点P₁，对于不同座标部分的点P₁满足等式 (2)。

为了确定这些参数k₁和k₁′，首先产生参数k₁′.的随机数值。随后， 在椭圆曲线上的点P_k1对应于该随机数值k₁′，可以应用将曲线点的坐 标x，y对应于参数的函数f_a，b或使用在椭圆曲线上的点的生成函数G。

然后，通过对点应用f_a，b的逆操作获得参数k₁，对点应用f_a，b的逆 操作对应于在椭圆曲线上的一组点P(X，Y)-P_k1.的减法。

参数k₁和k₁′表示点P(X，Y)。接着，对先前所获得的第一和第 二参数应用基于密码π的加密函数E_π进行加密且通过信息34传输至 控制器。

采用对称的方式，所述控制器在步骤35中产生随机数值r₂。然 后，在步骤36中，控制器将这个数值变换成椭圆曲线上的点P₂。然 后，如同步骤33所述，控制器在步骤37中分别获得第一和第二参数 k₂和k₂′的数值。然后，在通过信息38传输至待控制的装置10之前， 对这些数值进行加密。

因此，待控制装置10就具有随机的数值r₁、数值k₂和k₂′以及函 数F。

于是，在步骤39中，可以恢复点P₂：

P₂＝F(k₂，k′₂)

因此，获得与控制器共享的密钥K且不会提供关于该密码的任何 信息，其满足

K＝r₁.r₂.G

控制器在步骤301中恢复对称形式的密钥K。

上述定义的函数F可以不同的形式来表示。下文将阐述该点p的 不同表示形式，从而有利于在随机数值的加密交换中不会提供信息的 冗余。

函数F为F_q域内的F_q x F_q的满射函数，使之：

P＝F(k，k′)    (3)

且使之对于任何数值对(k，k′)，P都为在椭圆曲线上的点且无需等 式(1)满足k和k′。

在这样的条件下，有利的是，与现有技术相比，根据所交换的随 机数值不能推导出关于密码的任何信息。实际上，数值对(k，k′)可随后 以加密的形式在装置和控制器之间进行交换。但是，无论潜在破解者 怎样试图通过检测密码来恢复所述数值对，都不可能确定该密码正确 与否，因为获得的任何结果都对应于椭圆曲线上的点且无需k和k′ 满足等式(1)。

这样的表示可以根据函数f_a，b(U)的有利特征，f_a，b(U)具有下列特 征：

$\forall P\in E_{a,b},\left|f_{a,b}^{-1}\left(P\right)\right|<L$

其中L为整数。

换句话说，该函数原图的大小是由相比椭圆曲线上的点的数量较 小数值L为边界的。

通过考虑下列函数f_a，b(u)，有利于根据本发明的实施例来确定函 数F，使得在F_q²域内的参数对(x，u.x+v)对应于F_q的参数u，使之：

x＝(v²-b-u⁶/27)^1/3+u²/3

并且

$v=\frac{3a-u^4}{6u}$

且假设f_a，b(0)＝0。

函数F可表示为：

F(k，k′)＝f_a，b(k)+f_a，b(k′)

或

F(k，k′)＝f_a，b(k)+k′.G

还可以考虑，f_a，b为从满足下列Skalba等式的多项式中获得的函 数。

f(X₁(k)).f(X₂(k)).f(X₃(k))＝U(k)²

其中X₁(k)、X₂(k)、X₃(k)和U(k)满足Skalba等式的多项式，如 Maciej Ulas在2007年7月11日所发表的文献“Rational points on  certain hyperelliptic curves over finite fields”中定义的实例一样。这里 将F_a，b(k)定义为(X_i(k)，f(X_i(k))^1/2)，其中i使得f(X_i(k))为F_q域内的平方 项。

图4示出了包括根据本发明一个实施例的待控制装置和控制器的 控制系统。

根据本发明一个实施例，该控制系统包括至少一个电子实体，例 如待控制的装置10和控制实体或控制器11。不论使用待控制装置或 控制器与否，该电子实体包括：

-确定单元(41)，适用于根据随机数值r₁来确定在椭圆曲线上 的有限区域F_q(q为整数)内的点P(X，Y)，椭圆曲线满足等式：

E_a，b(x，y)：x³+ax+b＝y²    (1)

-获取单元(42)，适用于获得第一和第二参数k和k′，使之：

P＝F(k，k′)

其中F为在F_q域内的F_qx F_q′满射函数；

-加密单元(43)，适用于获得以密码函数进行加密的加密形 式的第一和第二参数；以及，

-接口单元(44)，适用于将第一和第二加密参数传输至控制 器；

其中，函数F使得：无论F_q域内的输入元素z和z′如何，F(z，z′) 都为椭圆曲线上的点且输入元素不满足等式(1)。

采用E_π密码的加密函数可有不同的定义。可以选择比特串作为 输入参数和返回比特串作为输出。然而，为了保证密码的机密性，返 回的数值必须不能给出关于密码的任何信息。因此，可以区别两个情 况：

-密码作为典型加密函数的加密密钥来使用；

-或者密码是在数据库中的索引，对应于椭圆曲线的公共参数 数值。

在这两种情况下，加密算法可以进行下述处理，将参数k或k′ 的数值变换成比特串并且执行下列方法：

选择随机数值r。然后，通过下列计算将参数的数值v变换成比 特串：

v′＝v+r.q′

其中q′对应于q或N，且q为基体F_q的元素数量，N为椭圆曲 线上的数量。然后，有可能采用比特串来表示v′。

在密码π是索引的情况下，v′为根据密码的v的加密数值，且仅 有知晓公共参数(q或N)的人可以获得v的数值。

在密码使用典型密码函数的加密密钥的情况下，可使用加密函数 E_π来加密v′。

因此，在接收端，在第一种情况下，v可以通过计算v′mod q′进 行恢复。在第二种情况下，必须解密通过解密函数所发送的比特串， 以便获得v′并且最终能够通过v′mod N来计算v。

本发明可以有效地应用于使用椭圆曲线的各类密码计算。特别有 利于应用在由密码授权的协议中，诸如PACE(密码授权连接建立)。 在这种情况下，可改善计算性能，同时不允许任何与密码计算消耗时 间有关的破解。

本发明还能够有效地应用于私密协议的内容中，例如用于检测诸 如电子护照的电子识别文件。实际上，与现有技术相比，对所使用协 议进行监听不可能获得所使用的椭圆曲线的公共参数。