使用关联私钥部分更快的公钥加密的系统和方法

摘要

描述使用关联私钥部分更快的公钥加密的系统和方法，包括将明文加密为密文，其中，加密使用公钥和对应的私钥；以及存储密文。

说明书

技术领域

本文所述主题内容一般涉及数据处理，尤其涉及使用关联私钥部分更快的公钥加密的系统和方法。

背景技术

在公钥密码术或不对称密码术中，密码系统包括三个算法：一个用于密钥生成的算法，其生成所有者保有的私钥以及由所有者向公众公布的公钥；一个用于加密的算法，其允许能够得到公布的公钥的任何人使用公钥进行加密；以及一个用于解密的算法，其允许拥有私钥或“暗门”信息的所有者通过使用公钥加密的私钥数据来解密。

在RSA(Rivest、Shamir和Adleman)算法中，例如，私钥和公钥均使用两个质数生成。所有者知道这两个质数并且可以使用所述质数执行解密。“公众”(即，那些被提供公钥的人，公钥至少基于两个质数的某些形式的合数)可以使用公钥进行加密。公众不能有效地分解合数，并且不能执行解密。

在某些情况下，执行加密的一方也是私钥的所有者。例如，所有者可能需要将数据加密，用于在公共网络上传输，和/或存储在第三方存储中(例如云存储)。之后可以检索加密数据并由所有者解密。

发明内容

主题内容包括使用关联私钥部分更快的公钥加密的系统和方法，包括：将明文加密为密文，其中加密使用公钥和对应的私钥；以及存储密文。

所述方法使用一个或多个计算装置和/或系统来实现。所述方法可存储在计算机可读介质中。

附图说明

图1示出快速加密实施方式的高级示意图。

图2示出可以部署快速加密实施方式的示例性环境。

图3示出过程实施方式的示例。

图4示出适合于一些示例性实施方式的示例性环境。

图5示出示例性计算环境，其中示例性计算装置适合于在一些示例性实施方式中使用。

具体实施方式

本文所述主题内容通过示例性实施方式来教导。为了清楚以及为了避免混淆主题内容起见，省略了很多细节。下面所示示例指向用于实施使用关联私钥部分更快的公钥加密的系统和方法的结构和功能。

图1示出快速加密实施方式的高级示意图。示例性快速加密100被实施为使用公钥102的至少一部分以及对应的私钥104的至少一部分(也可以称为解密密钥)将数据或消息M加密，以产生密文C。快速加密100可以是实施一个或多个算法以使用公钥102的至少一部分执行加密的软件模块、过程、软件应用、硬件电路、实体装置、以及它们的任何组合。

快速加密100可以在任何密码系统中实施，例如加密、鉴权、数字签名等等，它们使用公钥等等以及私钥等等。可以使用本文所述技术使其更快的示例性算法包括但不限于传输层安全(TLS)、完美隐私(PGP)、Rivest、Shamir和Adleman(RSA)、同态加密(例如，Paillier加密)等等。算法可包括密钥分配或秘密密钥分配(例如使用Diffie–Hellman密钥交换等等)。

下面如图2所述，密文C可以与使用传统加密算法加密的另一个密文C2等同，传统加密算法只使用公钥102来加密数据。换言之，相同的解密引擎可将密文C和密文C2解密，并且不能区分C是使用快速加密算法100还是使用传统加密算法进行加密。

图2示出可以部署快速加密实施方式的示例性环境。A方200(例如所有者)使用密钥生成210生成公钥102和私钥104(或解密密钥104)。密钥生成120可以是实施一个或多个算法以生成密钥的软件模块、过程、软件应用、硬件电路、实体装置、以及它们的任何组合。公钥102可以提供给希望向所有者200发送加密消息的任何一方(例如B方250)。所有者200使用私钥104将利用公钥102加密的消息解密。所有者200在一个或多个快速加密算法或快速鉴权算法中也使用私钥104或者私钥104的至少一部分。

密钥生成210例如随机并相互独立地计算或选择两个质数p和q来生成密钥(例如公钥102和私钥104)。实施方式可以使用长度相等的质数p和q(例如，256比特、512比特、1024比特、2048比特、非2^X的长度等等)。可以计算最大公因子(即gcd)来验证gcd(pq，(p-1)(q-1))＝1的性质。为了生成公钥(例如公钥102)，密钥生成210计算n＝pq并选择随机整数g，诸如g＝n+1，其中以及公钥为(n,g)。公钥包括合数n，合数n不能有效地破解或分解，以获取p和q。p和/或q越大(例如比特长度越长)，破解n就越难。

在本文所述示例中，使用公式c＝(g^m)(rⁿ)mod>2可将明文m加密为密文c，其中且r是随机选择，并且其中或者以及且gcd(i，n)＝1。可将公式c＝(g^m)(rⁿ)mod>2称为EQ1。本文使用的术语“明文”或“m”(例如图1所示的M以及图2所示的M1和M2)表示要加密的数据、信息或消息。“明文”或“m”可以采用人类可读或机器可辨的形式，也可以采用并非人类可读或机器可辨的形式(例如事先加密)。

只有所有者或者进行解密的一方才知道或者应当知道p和q。一旦知道p和q，就可以容易地生成私钥。为了生成对应的私钥(例如私钥104，用于解密使用公钥102加密的密文)，密钥生成210计算λ＝lcm(p-1，q-1)，其中lcm是最小公倍数。密钥生成210还计算μ＝(L(g^λmodn²))^-1mod>λmodn²)μmod>

如果p和q的长度相同，则生成密钥(例如λ和μ)的另一个示例性方法是计算λ＝Φ(n)＝(p-1)(q-1)；μ＝Φ(n)^-1mod>

例如，p和q可以是512比特长的数，并且所得n可以是1024比特长的合数。如果p和q是1024比特长的质数，那么相应地，n可以是2048比特长的数(这种合数称为“RSA数”)。

因为只有所有者或者进行解密的一方才知道或者应当知道p和q，所以只有所有者(例如所有者的计算装置或系统)才能使用p和/或q进行加密。例如实施快速加密100，以使用私钥104或者私钥的成分(例如p和q)来加快加密。

如图1所示，快速加密100使用公钥102和对应的私钥104(或者私钥104的一部分)两者来加密数据(例如消息M1)，以生成密文(例如密文C1)。

EQ1加密公式为c＝(g^m)(rⁿ)mod>2。如果将n+1用作g，则加密公式变为c＝((n+1)^m)(rⁿ)mod>2，由于(n+1)^mmod>2的二项展开式，可将其简化为c＝(1+nm)(rⁿ) mod>2(称为EQ2)。在EQ2中，消去了一个幂运算(即g^m)，这可以减少计算时间。EQ2只有一个剩余的幂运算(即rⁿ)。

使用p和q，可以消去剩余的幂运算或者减少其计算时间。如果底数固定并且指数变化，则预计算可以很快。为了使用p和q加快加密(即，这只能通过私钥104的所有者进行，私钥104的所有者知道p和q或者能够得到p和q)，可以使用公知的中国剩余定理(CRT)转换EQ2的“(rⁿ)mod>2”部分，从而能够利用固定底数进行预计算。

注意n²＝p²q²。从n²的n次余数选择随机r的操作可以用从p²的n次余数选择随机r1以及从q²的n次余数选择随机r2来代替。使用CRT，可将r1和r2组合，得到p²q²或n²的n次余数。使用CRT，对于随机r1和r2，可将(rⁿ)mod>2＝(rⁿ)mod>2>2转换为(r1)ⁿmod>2和(r2)ⁿmodq²，其中(r1)(r2)＝r；以及

通过选择阶为Φ(p²)的循环群的生成元g1以及从Φ(p²)选择随机元素s1，然后计算y1＝(g1)^s1mod>2，可以随机选择r1的值。Φ(p²)是欧拉函数或Φ函数＝小于p²的正整数中(即1,2,…,(p²-1))与p²互质的数的数目。

通过选择阶为Φ(q²)的循环群的生成元g2以及从Φ(q²)选择随机元素s2，然后计算y2＝(g2)^s2mod>2，可以随机选择r2的值。Φ(q²)是欧拉函数或Φ函数＝小于q²的正整数中(即1,2,…,(q²-1))与q²互质的数的数目。

为了获得n次余数，将y1和y2升幂到n次幂。因此，(y1)ⁿ＝[(g1)^s1mod>2]ⁿ＝[(g1)^s1]ⁿmod>2＝(g1ⁿ)^s1mod>2，且(y2)ⁿ＝[(g2)^s2mod>2]ⁿ＝[(g2)^s2]ⁿmod>2＝(g2ⁿ)^s2mod>2。作为参考，可将g1ⁿmod>2称为GN1，且g2ⁿmod>2＝GN2。结果是固定底数的GN1升幂到随机s1的指数mod>2(即，GN1^s1mod>2)以及固定底数的GN2升幂到随机s2的指数mod>2(即，GN2^s2modq²)。

快速加密100对于p和q的每个组合预计算其值一次且仅此一次。为了简化描述，选择小的p和q值作为示例。在通过计算装置或系统的实际实施方式中，p和q的值在长度上可以是256比特、512比特、1024比特、2048比特或者其他数目的比特。例如，在下面所示的示例中，p＝5且q＝7。前面的示例性实施方式被应用于p和q的值，如以下运算序列所示：

p＝5；p²＝25

的大小＝20

p²的g1＝{1：1，2：20，3：20，4：10，5：2，6：5，7：4，8：20，9：10，10：2，11：5，12：20，13：20，14：10，15：2，16：5，17：20，18：4，19：10，20：2，21：5，22：20，23：20，24：2}，最大阶是20。生成元g1可以是(2,3,8,12,13,17,22,或23)。

例如，g1＝2。

的大小＝42

q²的g2＝{1：1，2：21，3：42，4：21，5：42，6：14，7：2，8：7，9：21，10：42，11：21，12：42，13：14，14：2，15：7，16：21，17：42，18：3，19：6，20：14，21：2，22：7，23：21，24：42，25：21，26：42，27：14，28：2，29：7，30：3，31：6，32：21，33：42，34：14，35：2，36：7，37：21，38：42，39：21，40：42，41：14，42：2，43：7，44：21，45：42，46：21，47：42，48：2}，最大阶是42。生成元g2可以是(3,5,10,12,17,24,26,33,38,40,45,或47)。

例如，g2＝3。

n＝pq＝35；n²＝35²＝1225

GN1＝glⁿmod>2＝2³⁵mod>

GN2＝g²ⁿmod>35mod>

预计算以上恒定值之后，快速加密100例如可以使用以下算法将任何数据或消息m加密为密文c。

EQ2为c＝(1+nm)(rⁿ)mod>2，并且对于GN1^s1mod>2和GN2^s2mod>2可以使用CRT(中国剩余定理)计算“(rⁿ)mod>2”部分。

令D＝(1+nm)mod>2。因此，就最高计算成本而言(例如，关于时间和/或资源消耗)，D的计算基本上为一个倍增。

所进行的从Φ(p²)选择随机元素s1以及从Φ(q²)选择随机元素s2的操作就计算成本而言可以忽略不计。

计算E＝GN1^s1 mod>2和F＝GN2^s2 mod>2。计算成本基本上是固定底数的两个指数运算。经由加法链的方法，特别是Pippenger幂运算算法，可以加快固定底数的幂运算。

快速加密100使用CRT执行计算，将E与F组合，产生结果H＝(rⁿ)mod>2。计算成本不包括进行任何幂运算。

然后，快速加密100计算c＝DH mod>2。

例如，如图2所示，快速加密100可将消息M1加密，生成密文C1。M1＝12(即m＝12)。使用预计算的常数GN1和GN2(基于p＝5和q＝7)，快速加密100选择和/或计算以下值：

D＝(1+nm)mod>2＝(1+35x12)mod>2＝421

s1＝7以及s2＝9(随机选择)

E＝GN1^s1mod>2＝18⁷mod>

F＝GN2^s2mod>2＝19⁹mod>

可以使用以下两个方程计算H。

x≡7mod 25

x≡48mod 49

H＝832

C1＝DH mod>2＝421x832>

如果要通过快速加密100加密的数据与某个时候(例如)能够加密的数量相比更大或更长，那么可将数据分解为片段，以满足每个片段条件。得到的密文可以连接起来。在相反的过程或解密过程中，在解密为个别明文之前可将连接起来的密文分解为个体密文。明文可以连接起来形成原始数据。

在快速加密100将M2加密创建C1之后，例如可将C1存储在A方或所有者200控制的数据库220中。也可以经由网络224(例如公共网络或互联网)，通过路径222将C1例如传输到C方226。C方可以是提供数据存储服务的第三方(例如云存储服务提供者)。在一些实施方式中，可以经由网络224传输密文C1，以用于存储或通过由A方控制的装置或系统(未示出)处理。当A方要访问M1或C1的明文数据时，如果C1存储在数据库220中，则A方可以从数据库220检索C1，或者通过网络224以及路径228从C方检索C1。不管C1的源如何，A方都可以使用解密引擎230(或解密230)将C1解密。

与快速加密100相比，能够得到公钥102(即，在不知道p和q的情况下)的一方(例如B方)只使用公钥进行加密。例如，A方200将公钥102提供给B方250，用于B方将消息M2加密为密文C2发送给A方。M2可以是任何值。B方的加密引擎260使用EQ1 c＝(g^m)(rⁿ)mod>2来加密M2。例如，n＝35且g＝36。B方不知道合数n的因子p和q。加密引擎260选择随机r，如上所述。例如，r＝23。作为比较，M2＝12(即，m＝12)。EQ1变为C2＝(g^m)(rⁿ)mod>2＝(36¹²)(23³⁵)mod1225＝522。B方将C2发送给A方。注意，EQ1不使用私钥(例如因子p和q)，或者λ和/或μ的值。

A方的解密引擎230可通过相同的方式将(即，使用私钥104和公钥102通过快速加密100来加密的)C1和(即，只使用公钥102通过B方的加密引擎260来加密的)C2解密。不管C1和C2何时到达(例如分别地)，都可以使用相同的解密密钥或私钥104(例如λ、μ)独立地将C1和C2解密。

为了解密，解密引擎230检索或计算以下值：

p＝5；q＝7；n＝pq＝35；n²＝1225

g＝n+1＝36

λ＝1cm(p-1，q-1)＝12

μ＝(L(g^λmod>2))^-1mod>

u＝g^λmod>2＝36¹²mod>2＝421

L(u)＝(421-1)/35＝12

μ＝(12)^-1mod>

私钥(λ，μ)＝(12，3)。

解密公式为m＝L(c^λmod>2)μmod>

m＝L(c^λmod>2)μmod>λmod>2)，其中L(u)＝(u-1)/n

解密引擎230将C1解密获得明文M1，将C2解密获得明文M2。解密引擎230计算以下值来解密C1(C1＝1147，通过快速加密100产生)。

u＝C1^λmod>2＝1147¹²mod>

k＝(141-1)/35＝4

M1＝(k)μmod n＝(4)3 mod 35＝12

解密引擎230计算以下值来解密C2(C2＝522，通过加密引擎260生成)

u＝C2^λmod>2＝522¹²mod>

k＝(141-1)/35＝4

M2＝(k)μmod n＝(4)3mod 35＝12

相同的解密引擎230可将密文C1和C2解密，不管是否Cs使用快速加密算法加密且C2使用传统加密算法来加密。

图3示出过程实施方式的示例。过程300例如包括块310，其中快速加密100使用合数n＝p乘以q(例如公钥102)将数据(例如M1)加密为密文(例如C1)，其中p和q可以是质数。为了加快加密操作，快速加密100还分别使用p和q，即私钥104的成分。例如，使用或基于p来计算g1和GN1，且使用或基于q来计算g2和GN2。在块320，可以存储(例如存储在数据库220)加密数据(例如C1)或者将其发送到另一个位置或另一方(例如C方)。

在一些示例中，可通过不同、更少或更多的块来实施处理300。可将处理300实施为计算机可执行指令，计算机可执行指令可以存储在介质上，载入一个或多个计算装置的一个或多个处理器，并作为计算机实施方法执行。

在公钥操作中使用私钥的另一个示例是签名验证(例如，验证使用数字签名来签名的消息或数据的真实性(authenticity))。例如，为了创建RSA签名密钥，生成包含模数N的RSA密钥对(模数N是两个大质数(例如p和q)的乘积)，连同整数e和d一起，使得(e)(d)≡1(modΦ(N))，其中Φ是欧拉Φ函数。签名者的公钥包括N和e，且签名者的私钥包括d。

为了对消息m进行签名，签名者计算σ≡m^d(mod>e≡m(mod>n)mod>2”部分的转换。

例如，将σ升幂到e次方对合数N取余数的操作可以通过从p的n次余数选择随机r1以及从q的n次余数选择随机r2来代替。使用CRT，可将r1和r2组合，得到pq或N的e次余数。使用CRT，对于随机r1和r2，可将(σ^e)mod>e)mod>emod>emod>以及在如上所述计算r1和r2之后操作继续。

可以由知道因子(私钥)的一方将相同的操作应用于RSA加密的另一个示例。例如，为了验证已经使用私钥进行数字签名的数据或消息，可以(例如由知道私钥的一方)使用私钥的至少一部分以及对应的公钥来生成基于消息的验证结果。例如可以“验证”或“拒绝”验证结果。结果例如可以存储在日志或数据库中。

图4示出适合于一些示例性实施方式的示例性环境。环境400包括装置405-445，每个装置例如经由网络460可通信地连接到至少一个其他装置(例如通过有线和/或无线连接)。一些装置可通信地连接到一个或多个存储装置430和445。

一个或多个装置405-445的示例可以是图5所述的计算装置505。装置405-445可包括但不限于计算机405(例如膝上型计算装置)、移动装置410(例如智能电话或平板电脑)、电视415、与车辆相关联的装置420、服务器计算机425、计算装置435-440、存储装置430和445。

在一些实施方式中，可将装置405-420视为用户装置(例如用户用来访问数据的装置，诸如例如云存储服务提供者存储的数据)。装置425-445可以是与服务提供者相关联的装置(例如，服务提供者用来提供服务和/或存储数据，例如存储加密的网页、文本、文本部分、图像、图像部分、音频、音频片段、视频、视频片段、和/或与其有关的信息)。

例如，用户(例如Alice)可以使用装置405或410将加密数据发送给一个或多个装置425-445支持的存储提供者。Alice可以使用私钥将数据加密，以节约计算时间和/或资源。加密数据不能被存储提供者解密。当Alice要访问数据时，Alice从存储提供者检索数据(例如，按照加密的形式)，并在Alice的装置405或410上将数据解密。

图5示出具有示例计算装置的示例性计算环境，所述示例性计算装置适合于在一些示例性实施方式中使用。计算环境500中的计算装置505可包括一个或多个处理单元、核、或处理器510、存储器515(例如RAM、ROM等等)、内部储存器520(例如磁、光、固态存储、和/或有机存储)、和/或I/O接口525，它们的任何一个都可以耦合到用于传递信息的通信机构或总线530，或者嵌入在计算装置505中。

计算装置505可通信地耦合到输入/用户接口535以及输出装置/接口540。输入/用户接口535和输出装置/接口540的一者或二者可以是有线或无线接口，并且可拆卸。输入/用户接口535可包括实体或虚拟的用于提供输入的任何装置、组件、传感器、或接口(例如按钮、触摸屏接口、键盘、指示/光标控制、麦克风、相机、盲文、运动传感器、光学阅读器等等)。输出装置/接口540可包括显示器、电视、监视器、打印机、扬声器、盲文等等。在一些示例性实施方式中，可将输入/用户接口535和输出装置/接口540嵌入计算装置505或者实体连接到计算装置505。在其他示例性实施方式中，其他计算装置可以充当用于计算装置505的输入/用户接口535和输出装置/接口540，或者提供输入/用户接口535和输出装置/接口540的功能。

计算装置505的示例可包括但不限于高度移动装置(例如，智能电话、车辆和其他机器中的装置、人和动物携带的装置等等)、移动装置(例如，平板、笔记本电脑、膝上型计算机、个人计算机、便携电视、无线电等等)，以及并非为移动性设计的装置(例如，桌面型计算机、其它计算机、信息亭、其中嵌入有一个或多个处理器和/或与其耦合的电视、无线电等等)。

计算装置505可通信地耦合(例如经由I/O接口525)到外部储存器545以及网络550，网络550用于与任意数量的网络化组件、装置、和系统通信，包括配置相同或不同的一个或多个计算装置。计算装置505或者任何相连接的计算装置可以充当服务器、客户端、瘦服务器、通用机器、专用机器、或其他标签，或者提供它们的服务，或者称为服务器、客户端、瘦服务器、通用机器、专用机器、或其他标签。

I/O接口525可包括但不限于使用任何通信或I/O协议或标准(例如以太网、802.11x、通用系统总线、WIMAX、调制解调器、蜂窝网络协议等等)的有线和/或无线接口，用于向所连接的组件、装置、以及计算环境500中的网络通信信息和/或从所连接的组件、装置、以及计算环境500中的网络传递信息。网络550可以是任何网络或网络的组合(例如因特网、局域网、广域网、电话网络、蜂窝网络、卫星网络等等)。

计算装置505可以使用计算机可用介质或计算机可读介质和/或使用计算机可用或计算机可读介质来通信，包括暂时性介质和非暂时性介质。暂时性介质包括传输介质(例如金属电缆、光纤)、信号、载波等等。非暂时性介质包括磁介质(例如磁盘和磁带)、光介质(例如CD ROM、数字视频盘、蓝光盘)、固态介质(例如RAM、ROM、闪存、固态存储)、以及其他非易失性存储或存储器。

计算装置505可用于在一些示例性计算环境中实施技术、方法、应用、过程、或计算机可执行指令。计算机可执行指令可以从暂时性介质检索，并存储在非暂时性介质上，以及从非暂时性介质检索。可执行指令可根据任何编程语言、脚本语言、以及机器语言中的一个或多个(例如C、C++、C#、Java、Visual Basic、Python、Perl、JavaScript等等)生成。

在本机或虚拟环境中，(一个或多个)处理器510可以在任何操作系统(OS)(未示出)下执行。可以部署一个或多个应用，包括逻辑单元560、应用程序编程接口(API)单元565、输入单元570、输出单元575、预计算引擎580、随机数生成器585、加密引擎590、以及单元间通信机构595，用于不同单元相互通信、与OS通信，以及与其他应用(未示出)通信。例如，预计算引擎580、随机数生成器585、以及加密引擎590可以实施图1至图4中所示和所述的一个或多个处理。所述单元和元件可以在设计、功能、配置、或实施方式方面变化，并且不限于所提供的描述。

在一些示例性实施方式中，当通过API单元565接收信息或执行指令时，可将其通信给一个或多个其他单元(例如逻辑单元560、输入单元570、输出单元575、预计算引擎580、随机数生成器585、以及加密引擎590)。例如，在输入单元570检测到消息M以后，输入单元570可以使用API单元565将消息M传递给预计算引擎580。预计算引擎580进行检查，保证加密操作中所需的常数和/或值有效。如果情况并非如此，则预计算引擎580生成或预计算这些常数和/或值。然后预计算引擎580呼叫加密引擎590将M加密。如果需要的话，加密引擎590呼叫随机数生成器585，生成s1和s2随机数，用于在加密时使用。在加密引擎590将M加密为密文C之后，加密引擎590将C传递给输出单元575，输出单元575与I/O接口525互动，以存储C或者在网络上传输C。

在一些实例中，可将逻辑单元560配置为控制在单元间流动的信息，并引导在上述一些示例性实施方式中通过API单元565、输入单元570、输出单元575、预计算引擎580、随机数生成器585、以及加密引擎590提供的服务。例如，可单独通过逻辑单元560或结合API单元565控制一个或多个过程或实施方式的流程。

虽然示出和描述了一些示例性实施方式，但是这些示例性实施方式是用于向熟悉本领域的人员传达本文所述主题内容。应当理解，本文所述主题内容可以按照多种形式实施，不限于所述的示例性实施方式。本文所述主题内容没有这些特别限定或描述的内容也可以实践，也可利用其他或不同的元件或者没有描述的内容来实践。本领域技术人员应当理解，在不脱离后附权利要求书及其等同物所限定的本文所述主题内容的情况下，在这些示例性实施方式中可以进行改变。