CN1245695C - 一种基于杠杆函数和超递增序列的公钥加密方法 - Google Patents

Abstract

属密码学和计算机科学技术；一种基于杠杆函数和超递增序列的公钥加密方法，包括密钥生成、加密和解密三个部分；其用户拥有两个密钥，一个只能私有，叫私钥，一个可以公开，叫公钥，且从公钥不能推出私钥；公钥用于把明文转换成密文，即加密，私钥用于把密文还原成明文，即解密；该方法能有效抗御Shamir的极小点攻击和LOB-L³归约基攻击，可用于计算机和通信网络中任何文件、数据的保密存储与传输。

Description

一种基于杠杆函数和超递增序列的公钥加密方法

                            (一)技术领域

公开密钥加密方法(简称公钥加密方法)属密码学和计算机科学技术领域。公开密钥加密方法包含两个密钥，一个叫公开密钥，简称公钥，一个叫私有密钥，简称私钥。

                            (二)背景技术

1976年，美国学者Whitfield Diffie和Martin Hellman首次提出了“公开密钥密码系统”的思想。基于这种思想，目前已有一些具体的实现技术，主要包括：(1)MH背包公钥系统；(2)RSA公钥系统；(3)Pohlig-Hellman公钥系统；(4)Rabin公钥系统；(5)ElGamal公钥系统，其在椭圆曲线上的实现也叫ECC公钥系统；(6)McEliece公钥系统；(7)LUC公钥系统；(8)有限自动机公钥密码系统(上述系统可参见《应用密码学》，美国BruceSchneier著，吴世忠、祝世雄等译，机械工业出版社，2000年1月)。

上述系统中，第一种至第七种是外国人发明的，大部分已申请专利，其中，RSA系统和椭圆曲线上的ElGamal系统被广泛使用。最后一种是我国学者陶仁骥教授提出的。

                             (三)发明内容

本发明可用于计算机网络和通信网络中字符、文字、图形、图象和声音等各种文件和数据的加密和解密，以确保文件及数据存储与传输的私密性。希望我们国家在公开密钥密码领域能够拥有自己的核心技术，以确保我国的信息安全和经济安全。

3.1两个基本概念

3.1.1超递增序列

设A₁，A₂，…，A_n为n个互不相同的正整数，且满足

A_i＞∑A_j(i＝2，3，…，n；j＝1，2，…，i-1)

则称这样的正整数序列为超递增序列，记为{A₁，A₂，…，A_n)或{A_i)。

超递增序列有如下性质：对于任意的正整数m(1≤m≤n)，从超递增序列{A_i)中任选m个项，则该m个项的累加和(即子集和)： $E_S=A_{i_1}+A_{i_2}+\·\·\·+A_{i_m}$ 是唯一确定的。

3.1.2杠杆函数

设f(i)是由整数到整数的单射函数，i∈{1，2，…，n}。

其函数值f(1)、f(2)、…、f(n)是n个不同的正整数。在本加密方法中，当从公钥推导私钥或密文时，需考虑f(i)的全排列数n！；但从私钥解开密文时只需考虑f(i)的累加和。因此，若以密文为支点，则f(i)是一端计算量大，另一端计算量小。我们称满足该性质的f(i)为杠杆函数。

3.2技术方案

本发明是一种基于杠杆函数和超递增序列的公开密钥加密方法，简称REESSE2公钥加密方法，根据它生产的密码产品可以是纯粹的数字逻辑电路做成的加解密芯片，或者由数字逻辑电路加固化程序做成的加解密芯片，或者由计算机硬件和软件组成的密码机等。因此，本发明是一种开发密码系统或产品所必须遵循的基本原理与技术方案，而不是物理产品本身。

本公钥加密方法由密钥生成、加密和解密等三个部分组成。

3.2.1本发明的加密与解密模式

假设用户V欲通过网络向用户U发送一个文件或数据，且以保密的方式进行。本文中，把加密之前的文件或数据叫明文，加密之后的文件或数据叫密文。用户V与用户U欲实现这么一个保密通信过程，其模式如下：

密钥生成：首先，用户U应该去第3方权威机构(CA认证中心或数字证书中心)领取一对由密钥生成部件输出的私钥(Private Key)与公钥(Public Key)，私钥必须由用户U自己保管，不得泄密；公钥则允许以公钥证书的形式向外界公开发放，以便于使用。

加密操作：用户V从CA认证中心获得用户U的公钥证书，在运行加密部件的机器上对欲发送的明文进行加密，得到密文，并由网络把密文传送给用户U。

解密操作：用户U接收到用户V发送来的密文后，在运行解密部件的机器上用自己的私钥对密文进行解密，恢复出明文。

在公钥加密方法中，为了提高加密的效率，通常采用混合密码技术，即用对称密码体制来加密明文，再用公钥密码体制来加密会话密钥。对称密码体制所使用的加密密钥与解密密钥本质上是同一个密钥，被称为会话密钥。

3.2.2密钥生成部分

密钥生成部分供CA认证中心使用，用来产生一对私钥和公钥。其实现方法是：

(1)随机产生项数为n的超递增序列{A₁，A₂，…，A_n}

(2)找到一个正素数M，其满足 $M>\left({\mathrm{\Σ}}_{i=1}^n{A}_1\right),$ 且(n/log₂ M)＞0.645

(3)随机产生两两不同的函数值f(1)、f(2)、…、f(n)，5≤f(i)≤(n+4)，i＝1，2，…，n

(4)选取适当的正整数W、Z，其满足W＜M和Z＜M

(5)计算非超递增序列C_i＝((A_i+Z*f(i))*W)mod M，i＝1，2，…，n

(6)从(Z+(-Z))mod M＝0求出-Z，从(W*W^-1)mod M＝1求出W^-1

最后，以({A_i}W^-1、-Z、M)作为私钥，以({C_i}、M)作为公钥。

注意：在本文中，表达式中的“*”代表乘法。{C₁}代表{C₁，C₂，…，C_n}。

3.2.3加密部分

加密部分供发送方使用，用来对明文进行加密。发送方为获得加密密钥即接收方公钥，须从CA认证中心取得接收方的公钥证书。

在加密部分和解密部分，符号“Hash”代表单向散列函数。

设({C_i}、M)为公钥，EF为明文，分组数h≤32。则加密部分的实现方法是：

(1)随机产生h个n比特长的分组b₁₁b₁₂…b_1n、b₂₁b₂₂…b_2n、…、b_h1b_h2…b_hn

(2)以Hash(b₁₁b₁₂…b_1nb₂₁b₂₂…b_2n…b_h1b_h2…b_hn)之n比特输出作为会话密钥K

(3)以会话密钥K对明文EF进行对称加密，得到密文CF

(4)令i＝1

(5)令E₁＝0，j＝1

(6)如果b_ij＝1，则E_i＝(E_i+C_j)mod M

(7)置j＝j+1，如果j≤n，则转至(6)

(8)置i＝i+1，如果i≤h，则转至(5)，否则，结束

最后，得到可安全发送的密文CF和子集和序列{E₁、E₂、…、E_h}。

3.2.4解密部分

解密部分供接收方使用，用来对密文进行解密。接收方以自己的私钥作为解密密钥。

设({A_i}、W^-1、-Z、M)为私钥，CF为密文，{E₁、E₂、…、E_h}为子集和序列。则解密部分的实现方法是：

(1)令i＝1

(2)计算E_i＝(E_i*W^-1)mod M

(3)计算E_i＝(E_i+(-Z))mod M

(4)令b_i1b_i2…b_in各位皆为0，E_s＝E_i，j＝n

(5)如果E_s≥A_j，则b_ij＝1并且E_s＝E_s-A_j

(6)置j＝j-1，如果j≥1并且E_s≠0，则转至(5)

(7)如果E_s≠0，则转至(3)

(8)置i＝i+1，如果i≤h，则转至(2)

(9)以Hash(b₁₁b₁₂…b_1nb₂₁b₂₂…b_2n…b_h1b_h2…b_hn)之n比特输出作为会话密钥K

(10)以会话密钥K对密文CF进行对称解密，得到明文EF

最后，接收方恢复出发送方的明文即原始文件EF。

3.3优点和积极效果

3.3.1安全性满足要求

由于综合利用了杠杆函数和单向散列函数，所以，本加密方法能有效抗御Shamir的极小点攻击和Lagarias-Odlyzko-Brickell的L³归约基攻击。

3.3.2运算速度快

在本加密方法中，加密、解密操作基本上只用到加法和减法运算，且最大整数(即模数)可控制在192比特范围之内，所以，与流行的RSA、ECC算法比较起来，加密、解密速度要快上许多倍。

3.3.3技术可以公开

本发明的实现技术完全可以公开，公钥(Public Key)也可以完全向外界发放。只要私钥(Private Key)不泄密，就可以完全保证密文的安全。

3.3.4对国家的信息安全有利

目前，我国正积极发展电子政务与电子商务，信息安全关系到国家安全和经济安全。但是，泱泱一个大国的信息安全不能完全建立在外国的加密技术基础之上，而没有自主核心技术，所以，研究我们自己的公钥加密技术显得势在必行和具有重大意义。

                       (四)具体实施方式

基于杠杆函数和超递增序列的公钥加密方法能够让每一用户得到两个密钥(从CA认证中心取得)，一个密钥可以公开，一个密钥只能私人拥有，这样，就不会担心密钥在发放和交流过程中泄密了。当在网上传输信息时，发送者使用接收者的公钥对明文进行加密，接收者使用自己的私钥对密文进行解密。

本公钥加密方法用于开发产品时，可以用数字逻辑电路、或者由数字逻辑电路加固化程序、或者由计算机硬件加软件等来实现。本发明是一种生产密码产品所必须遵循的基本原理与技术方案，而不是物理产品本身。

下面，举例说明基于杠杆函数和超递增序列的公钥加密方法：

设序列项数n＝6，分组数h＝6(实际应用中，n至少应为96，h至少应为16)。

设单向散列函数，即Hash函数如下：

H₀＝101100(“101100”为二进制数，下同)

H_i＝(H_i-1T_i)²mod 1000000(“1000000”为二进制数，下同)

其中，表示二进制的异或运算，T_i表示长度为n的二进制块。

设对称加密方案(亦即解密方案)为：

Y_i＝～(X_iK)

其中，～表示二进制的非运算，X_i为n比特的分组数据，K为n比特的会话密钥。

注意，实际应用中，Hash函数和对称加密方案远比上面假设要复杂。

(1)密钥的生成

根据3.2.2密钥生成部分的实现方法：

设随机产生一超递增序列{A_i}为{3，5，9，20，39，79}。

找到 $M=163>{\mathrm{\Σ}}_{i=1}^6{A}_1=(3+5+9+20+39+79)=155,$ 可以验证，163为素数，且(n/log₂ M)＝6/log₂ 163＞0.645。

随机产生杠杆函数值f(1)＝4，f(2)＝5，f(3)＝2，f(4)＝6，f(5)＝7，f(6)＝3。

选取W＝101，Z＝158，显然，W＜M、Z＜M。

做C_i＝((A_i+Z*f(i))*W)mod M，则

C₁＝((3+158*4)*101)mod 163＝76    C₂＝((5+158*5)*101)mod 163＝99

C₃＝((9+158*2)*101)mod 163＝62    C₄＝((20+158*6)*101)mod 163＝131

C₅＝((39+158*7)*101)mod 163＝78   C₆＝((79+158*3)*101)mod 163＝107

因此，得到非超递增序列{C_i}＝{76，99，62，131，78，107}。

从(Z+(-Z))mod M＝0求出(-Z)＝5，从(W*W^-1)mod M＝1并根据扩展欧几里德算法求出W^-1＝92。

以({76，99，62，131，78，107}、163)作为公钥，以({3，5，9，20，39，79}、92、5、163)作为私钥。

(2)加密

已知接收方的公钥为({76，99，62，131，78，107}、163)。

设明文EF为一文本文件，其内容为“Peking”(不含引号，共6个字符)，则其ASCII码二进制形式为：01010000 01100101 01101011 01101001 01101110 01100111。

根据3.2.3加密部分的实现方法：

随机产生6个6比特长的分组b₁₁b₁₂…b₁₆、b₂₁b₂₂…b₂₆、…、b₆₁b₆₂…b₆₆为：

011010、100101、001100、111110、010011、100111。

则Hash(011010100101001100111110010011100111)之输出为：

H₁＝(H₀T₁)²mod 1000000＝(101100011010)²mod 1000000＝100100

H₂＝(H₁T₂)²mod 1000000＝(100100100101)²mod 1000000＝000001

H₃＝(H₂T₃)²mod 1000000＝(000001001100)²mod 1000000＝101001

H₄＝(H₃T₄)²mod 1000000＝(101001111110)²mod 1000000＝010001

H₅＝(H₄T₅)²mod 1000000＝(010001010011)²mod 1000000＝000100

H₆＝(H₅T₆)²mod 1000000＝(000100100111)²mod 1000000＝001001

所以，得到会话密钥K＝H₆＝001001。

下面，对明文EF进行对称加密，按6个比特进行分组，以“Peking”即010100 000110010101 101011 011010 010110 111001 100111作为输入，其加密过程如下：

Y₁＝～(X₁K)＝～(010100001001)＝100010；Y₂＝～(X₂K)＝～(000110001001)＝110000

Y₃＝～(X₃K)＝～(010101001001)＝100011；Y₄＝～(X₄K)＝～(101011001001)＝011101

Y₅＝～(X₅K)＝～(011010001001)＝101100；Y₆＝～(X₆K)＝～(010110001001)＝100000

Y₇＝～(X₇K)＝～(111001001001)＝001111：Y₈＝～(X₈K)＝～(100111001001)＝010001

将输出Y₁、Y₂、Y₃、Y₄、Y₅、Y₆、Y₇、Y₈进行连接，得到密文CF，其二进制内容为100010110000100011011101101100100000001111010001。

根掘3.2.3加密方法，从6个分组011010 100101 001100 111110 010011 100111得到子集和序列为：

E₁＝(b₁₁C₁+b₁₂C₂+b₁₃C₃+b₁₄C₄+b₁₅C₅+b₁₆C₆)mod M＝(99+62+78)mod 163＝76

E₂＝(b₂₁C₁+b₂₂C₂+b₂₃C₃+b₂₄C₄+b₂₅C₅+b₂₆C₆)mod M＝(76+131+107)mod 163＝151

E₃＝(b₃₁C₁+b₃₂C₂+b₃₃C₃+b₃₄C₄+b₃₅C₅+b₃₆C₆)mod M＝(62+131)mod 163＝30

E₄＝(b₄₁C₁+b₄₂C₂+b₄₃C₃+b₄₄C₄+b₄₅C₅+b₄₆C₆)mod M＝(76+99+62+131+78)mod 163＝120

E₅＝(b₅₁C₁+b₅₂C₂+b₅₃C₃+b₅₄C₄+b₅₅C₅+b₅₆C₆)mod M＝(99+78+107)mod 163＝121

E₆＝(b₆₁C₁+b₆₂C₂+b₆₃C₃+b₆₄C₄+b₆₅C₅+b₆₆C₆)mod M＝(76+131+78+107)mod 163＝66

最后，发送方将密文CF及子集和序列E₁、E₂、E₃、E₄、E₅、E₆通过网络传输给接收方。

(3)解密

从3.2.4解密方法中可以看出，解密子集和的过程是边搜索边验证，每轮搜索的次数不会超过 ${\mathrm{\Σ}}_{i=1}^{6}f\left(i\right)=27,$ 与项数n多项式时间复杂度相关，故求解是可行的。注意，解密过程不用到杠杆函数f(i)。

接收方已知私钥为({3，5，9，20，39，79}、92、5、163)；

密文CF的二进制内容为100010110000100011011101101100100000001111010001；

子集和序列E₁、E₂、…、E_m为76、151、30、120、121、66。

根掘3.2.4解密部分的实现方法：

E₁＝(E₁*W^-1)mod M＝76*92 mod 163＝146

并由E₁＝(E₁+(-Z))mod M循环搜索到E_S＝E₁＝53，验证后得b₁₁b₁₂…b₁₆＝011010

E₂＝(E₂*W^-1)mod M＝151*92 mod 163＝37

并由E₂＝(E₂+(-Z))mod M循环搜索到E_s＝E₂＝102，验证后得b₂₁b₂₂…b₂₆＝100101

E₃＝(E₃*W^-1)mod M＝30*92mod 163＝152

并由E₃＝(E₃+(-Z))mod M循环搜索到E_s＝E₃＝29，验证后得b₃₁b₃₂…b₃₆＝001100

E₄＝(E₄*W^-1)mod M＝120*92mod 163＝119

并由E₄＝(E₄+(-Z))mod M循环搜索到E_s＝E₄＝76，验证后得b₄₁b₄₂…b₄₆＝111110

E₅＝(E₅*W^-1)mod M＝121*92 mod 163＝48

并由E₅＝(E₅+(-Z))mod M循环搜索到E_s＝E₅＝123，验证后得b₅₁b₅₂…b₅₆＝010011

E₆＝(E₆*W^-1)mod M＝66*92 mod 163＝41

并由E₆＝(E₆+(-Z))mod M循环搜索到E_s＝E₆＝141，验证后得b₆₁b₆₂…b₆₆＝100111

这样，我们得到6个6比特长的分组011010、100101、001100、111110、010011、100111。

则Hash(011010 100101 001100 111110 010011 100111)之输出为：

H₁＝(H₀T₁)²mod 1000000＝(101100011010)²mod 1000000＝100100

……

H₆＝(H₅T₆)²mod 1000000＝(000100100111)²mod 1000000＝001001

所以，得到会话密钥K＝H₆＝001001。注意，求K过程与加密部分相同。

下面，对密文CF进行对称解密，按6个比特进行分组，以密文CF的二进制内容100010110000100011011101101100100000001111010001作为输入，其解密过程如下：

Y₁＝～(X₁K)＝～(100010001001)＝010100；Y₂＝～(X₂K)＝～(110000001001)＝000110

Y₃＝～(X₃K)＝～(100011001001)＝010101；Y₄＝～(X₄K)＝～(011101001001)＝101011

Y₅＝～(X₅K)＝～(101100001001)＝011010；Y₆＝～(X₆K)＝～(100000001001)＝010110

Y₇＝～(X₇K)＝～(001111001001)＝111001；Y₈＝～(X₈K)＝～(010001001001)＝100111

将输出Y₁、Y₂、Y₃、Y₄、Y₅、Y₆、Y₇、Y₈进行连接，得到明文EF，其二进制内容为010100000110010101101011011010010110111001100111，文本形式为“Peking”。

显然，接收方恢复出了发送方的明文即原始文件EF，且知其内容为“Peking”。

举例完毕。

Claims (1)

1、一种基于杠杆函数和超递增序列的公钥加密方法，由密钥生成、加密和解密三个部分组成，密钥生成部分供第3方权威机构产生用户的一对私钥和公钥，加密部分供发送方利用接收方的公钥把明文转换为密文，解密部分供接收方利用自己的私钥把密文还原成明文，其特征在于

●密钥生成部分采用了下列步骤：

(1)随机产生项数为n的超递增序列{A₁，A₂，…；A_n}

(2)找到一个正素数M，其满足 $M>\left({\mathrm{\Σ}}_{l=1}^n{A}_i\right),$ 且(n/log₂M)＞0.645

(3)随机产生两两不同的函数值f(1)、f(2)、…、f(n)，5≤f(i)≤(n+4)，i＝1，2，…，n

(4)选取适当的正整数W、Z，其满足W＜M和Z＜M

(5)计算非超递增序列Ci＝((Ai+Z*f(i))*W)mod M，i＝1，2，…，n

(6)从(Z+(-Z))mod M＝0求出-Z，从(W*W^-1)mod M＝1求出W^-1

最后，以({A_i}、W^-1、-Z、M)作为私钥，以({C_i}、M)作为公钥，其中，私钥只能由密文接收方私自拥有；

●加密部分采用了下列步骤：

假设接收方的公钥为({C_i}、M)，明文为EF，分组数h≤32，发送方进行

(1)随机产生h个n比特长的分组b₁₁b₁₂…b_1n、b₂₁b₂₂…b_2n、…、b_h1b_h2…b_hn

(2)以Hash(b₁₁b₁₂…b_1nb₂₁b₂₂…b_2n…b_h1b_h2…b_hn)之n比特输出作为会话密钥K

(3)以会话密钥K对明文EF进行对称加密，得到密文CF

(4)令i＝1

(5)令E_i＝0，j＝1

(6)如果b_ij＝1，则E₁＝(E1+C_j)mod M

(7)置j＝j+1，如果j≤n，则转至(6)

(8)置i＝i+1，如果i≤h，则转至(5)，否则，结束

最后，得到密文CF和子集和序列{E₁、E₂、…、E_h}，它们将被发送给接收方；

●解密部分采用了下列步骤：

接收方利用自己的私钥((A_i}、W^-1、-Z、M)，对子集和序列{E₁、E₂、…、E_h}与密文CF进行

(1)令i＝1

(2)计算E_i＝(E_i*W^-1)mod M

(3)计算E₁＝(E₁+(-Z))mod M

(4)令b_i1b_i2…b_in各位皆为0，E_S＝E_i，j＝n

(5)如果E_S≥A_j，则b_ij＝1并且E_S＝E_S-A_j

(6)置j＝j-1，如果j≥1并且E_S≠0，则转至(5)

(7)如果E_S≠0，则转至(3)

(8)置i＝i+1，如果i≤h，则转至(2)

(9)以Hash(b₁₁b₁₂…b_1nb₂₁b₂₂…b_2n…b_h1b_h2…b_hn)之n比特输出作为会话密钥K

(10)以会话密钥K对密文CF进行对称解密，得到明文EF

最后，接收方恢复出发送方的明文即原始文件EF。