REESSE+2公开密钥密码体制

计算机科学２００４Ｖ０１．３１１№－．９

ＲＥＥＳＳＥ

２公开密钥密码体制

苏盛辉１杨炳儒２

（北京科技大学信息工程学院

北京１０００８３）ｚ

（北京石油化工学院信息管理系北京１０２６１７）１

摘要作者综合利用超递增序列、杠杆函数和ＨＡＳＨ函数的特性提出了能有效地抵御“极小点”攻击和“ＬＯＢ—Ｌ３归

约基”攻击的ＲＥＥＳＳＥ２公开密钥密码体制．详细描述了该体制的数学基础、密钥生成算法、加密算法和解密算法。文章对ＲＥＥＳＳＥ２体制的安全性和优越性做了分析，并归纳了提高公钥密码体制安全性的两冬途径。

关键词杠杆函数．超递增数列，冗余加密，公开密钥密码体制

Ｔｈｅ

ＲＥＥＳＳＥ２ＰｕｂｌｉｃＫｅｙＣｒｙｐｔｏｓｙｓｔｅｍ

ＳＵＳｈｅｎｇ—Ｈｕｉｌ

ＹＡＮＧＢｉｎｇ—Ｒｕ２

ＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄ

（Ｂｅｉｊｉｎｇ

Ｉｎｓｔｉｔｕｔｅｏｆ

ＰｅｔｒｏｃｈｅｍｉｃａｌＴｅｃｈｎｏｌｏｇｙ．Ｂｅｉｊｉｎｇ１０２６１７）１（Ｂｅｉｊｉｎｇ

Ｔｅｃｈｎｏｌｏｇｙ。Ｂｅｉｊｉｎｇ

１０００８３）２

ＡｂｓｔｒａｃｔＯｎｔｈｅｂａｓｉｓｏｆｔｈｅ

ｓｕｐｅｒ

ｉｎｃｒｅａｓｉｎｇｓｅｑｕｅｎｃｅ，ｌｅｖｅｒｆｕｎｃｔｉｏｎａｎｄＨＡＳＨｆｕｎｃｔｉｏｎ，ｔｈｅａｕｔｈｏｒｓ

ｃａｎ

ｐｕｔ

ｆｏｒｗａｒｄ

ｒｅ—

ｔｈｅＲＥＥＳＳＥ２ｐｕｂｌｉｃｋｅｙｃｒｙｐｔｏｓｙｓｔｅｍｗｈｉｃｈｄｕｃｅｄｂａｓｅ，ｅｘｐｏｕｎｄｔｈｅｍａｔｈ

ｄｅｆｅｎｄｅｆｆｉｃｉｅｎｔｌｙａｔｔａｃｋｓｂｙｔｈｅｅｘｔｒｅｍｅｓｍａｌｌｄｏｔａｎｄＬＯＢ—Ｌ３

ｆｏｕｎｄａｔｉｏｎａｎｄｔｈｒｅｅａｌｇｏｒｉｔｈｍｓｆｏｒｇｅｎｅｒａｔｉｎｇ—ｋｅｙ，ｅｎｃｒｙｐｔｉｏｎａｎｄｄｅｃｒｙｐｔｉｏｎｏｆｔｈｅ

ｔＯ

ｃｒｙｔｏｓｙｓｔｅｍ，ａｎａｌｙｚｅａｌｇｏｒｉｔｈｍｉｃｓｅｃｕｒｉｔｙａｎｄａｄｖａｎｔａｇｅ，ａｎｄｉｎｄｕｃｅｔｈｅｔｗｏａｐｐｒｏａｃｈｅｓｌｉｃｋｅｙｃｒｙｔｏｓｙｓｔｅｍｓ．Ｋｅｙｗｏｒｄｓ

ｅｎｈａｎｃｉｎｇｓｅｃｕｒｉｔｉｅｓｏｆｐｕｂ—

Ｌｅｖｅｒｆｕｎｃｔｉｏｎ，Ｓｕｐｅｒｉｎｃｒｅａｓｉｎｇｓｅｑｕｅｎｃｅ，Ｒｅｄｕｎｄａｎｃｙｅｎｃｒｙｐｔｉｏｎ，Ｐｕｂｌｉｃｋｅｙｃｒｙｔｏｓｙｓｔｅｍ

１

引言

１９７８年，在ＷｈｉｔｆｉｅｌｄＤｉｆｆｉｅ和ＭａｒｔｉｎＨｅｌｌｍａｎ提出公开

了但密钥变换仍在单群上进行有本质的不同。经分析，

ＲＥＥＳＳＥ

２体制在安全性和速度方面有其优势。

密钥密码思想两年后。首先由ＲａｌｐｈＭｅｒｋｌｅ和Ｍａｒｔｉｎ

Ｈｅｌｌ—

２

ＲＥＥＳＳＥ２体制的数学基础

２．１三个有关函数

２．１．１杠杆函数在ＲＥＥＳＳＥｌ公钥体制中［５］，私有密

ｍａｎ设计了一个基于背包问题的公钥密码体制．尽管背包问题被证明属于ＮＰ完全类，但是，由于ＭＨ变换（模乘变换）本身的缺陷，该体制先后被以“极小点”方法和“ＬＯＢ－Ｌ３归约基”方法破译口￣３］。

ＭＨ背包体制可以被扩展到伽罗瓦域的多项式环上。此时，虽然超递增序列的元素由整数变成了多项式，但是从私钥到公钥的变换仍是模乘变换．由于多项式模乘变换与整数模乘变换在本质上是一致的，因此这种改变只是原有体制的扩展，而不是新体制的发明［１“３）．显然，多项式环上的ＭＨ公钥体制与椭圆曲线上的Ｅ１Ｇａｍａｌ公钥体制有异曲同工之妙：它们都提高了体制的安全性。这是因为，在多项式环上或椭圆曲线上，对基本运算符进行了组合，形成了一种新的更复杂的群的运算符。

本文介绍的ＲＥＥＳＳＥ２公钥密码体制综合利用了超递增序列、杠杆函数和ＨＡＳＨ单向散列函数的特点，对从私钥到公钥的变换进行了创新，即密钥的变换从单群扩展到了双群，同时在域的两个群上实施变换运算。注意，这与代数系统升级

钥为互索序列｛Ａｌ，Ａｚ，…，Ａ。｝，公开密钥｛Ｃ，，ｃ：，…，ｃ。｝经公式Ｇ＝（Ａ＊Ｗｚ“’）ｒｏｏｄＭ变换后得到。其中，厂（ｉ）为整数到整数的单射函效，且５≤厂（ｉ）≤（ｎ＋４），（？＝１，２，…，珂）。

在上述变换中，厂（ｉ）具有这样的特点：从公开密钥破译：私有密钥时，需考虑，（ｉ）的全排列数靠ｌ，因此当ｎ足够大时．厂（ｉ）的排列在有效时间内不可被穷举；但从私有密钥解开密文时只需考虑厂（ｉ）的累加和，时间复杂度与行多项式相关，故解密是可行的。若把密文当作支点，则，（ｉ）是“公开”一头计算量大，“私有”一头计算量小，因此，称具有这种特征的厂（ｉ）为杠杆函数。

２．１．２超递增序列设Ａ。，Ａｚ．…，Ａ．为ｎ个互不相同

的正整数，且满足：Ａ，＞２Ａ，（ｉ一２，３，…，押；．，＝１，２．…，ｉ一１），则称这样的正整数序列为超递增序列，记为｛Ａ。，Ａ。，…，月．。｝或｛Ａ。｝。

超递增序列有如下性质：对于任意的正整数ｍ（１≤ｍ≤

苏盛辉副教授．博士生．主要从事信息安全、柔性建模与集成技术的研究和开发．杨炳儒教授，博士生导师，主要从事知识发现与智能系统、柔性建模与集成技术的研究．

７

ＰａｎＹ，ＬｉＫ，ＺｈｅｎｇＳＬｉｎｅａｒＡｒｒａｙｗｉｔｈｎｉｃａＪ

ａ

Ｑ．Ｆａｓｔ

Ｎｅａｒｅｓｔ

ＮｅｉｇｈｂｏｒＡｌｇｏｒｉｔｈｍｓ

ｏｎａ９

ＡｔａｌｌａｈＭＪ。ＧｏｏｄｒｉｃｈＭ

ｏｆｔｗｏ

ｃｏｎｖｅｘ

Ｔ．ＰａｒａｌｌｅＩ

ａｌｇｏｒｉｔｈｍｓ

ｆｏｒｓｏｍｅｆｕｎｃｔｉｏｎｓ

ＲｅｃｏｎｆｉｇｕｒａｂｌｅＰｉｐｅｌｉｎｅｄＢｕｓＳｙｓｔｅｍ：［Ｔｅｃｈ—

Ｒｅｐｏｒｔ＃９７－００２）．ＤｅｐａｒｔｍｅｎｔｏｆｃｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，

Ｕｎｉｂｅｒｓｉｔｙ．ＢａｔｏｎＲｏｕｇｅ，ＬＡ７０８０３（１９９７）

Ｊ．Ｃｏｎｖｅｘ

ｈｕｌｌｓｏｆ

ｆｉｎｉｔｅ

ｓｅｔｓ

ｐｏｌｙｇｏｎｓ．ａｌｇｏｒｉｔｈｍｉｃａ，１９８８．３：５３５～５４８

Ｓ．ＦａｓｔＳｏｒｔｉｎｇ

１０Ｄａｔｔａ

ｏｎ

ａ

Ａ，０ｗｅｎｓＲ，Ｓｏｕｎｄａｒａｌａｋｓｈｍｉ

ＬｉｎｅａｒＡｒｒａｙ

ｗｉｔｈ

ｏｎ

ａ

Ａｌｇｏｒｉｔｈｍｓ

ＬｏｕｉｓｉａｎａＳｔａｔｅ８

Ｐｒｅｐａｒａｔａｔｗｏａｎｄ

ＲｅｃｏｎｆｉｇｕｒａｂｌｅＰｉｐｅｌｉｎｅｄＢｕｓＳｙｓｔｅｍ．

ａｎｄ

ＦＰ．ＨｏｎｇＳ

ｏｆｐｏｉｎｔｓ

ｉｎＩＥＥＥ

ＴｒａｎｓａｃｔｉｏｎｓＰａｒａｌｌｅｌ

ＤｉｓｔｒｉｂｕｔｅｄＳｙｓｔｅｍｓ

２００２，１３

ｔｈｒｅｅｄｉｍｅｎｓｉｏｎｓ．Ｃｏｍｍ．ＡＣＭ．１９７７。２（Ｚ０）：８７～９３（３）：２０２～２２２

・１４８・

万方数据　

ｎ），从超递增序列｛Ａ，｝中任选ｍ个元素作为子集，则子集和：Ｂ一（Ａ，。＋Ａ。＋…＋Ａｉ，）唯一确定了原子集的元素。下标ｉ。，

ｉｚ，…，ｉ。代表子集元素在原超递增序列中的序号。

２．１．３

ＨＡＳＨ函数也称单向散列函数。它把一个二进

制明文文件或数据块转换为ｎ比特的输出，该输出称为明文

摘要，ｎ通常为６４、１２８或２５６等。ＨＡＳＨ函数具有这些特点：

（１）给定明文，计算明文摘要很容易；（ｚ）给定明文摘要，逆向

计算明文很困难；（３）从两个不同的明文得到同样的明文摘要几乎是不可能的ｒｚｊ。

２．２从超递增序列得到非超递增序列

设｛Ａ。，Ａｚ，…，Ａ。｝为超递增序列，令：Ｃ，一（（Ａ＋Ｚ＊厂（ｉ））＊Ｗ）ｒｏｏｄＭ（ｉ一１，２．…，ｎ），等式右端称为ＲＥＥＳＳＥ２变

换。在上式中肘为正素数，并且Ｍ＞三Ａ．，Ｗ、Ｚ为小于Ｍ的工作参数，ｆ（ｉ）为单射的杠杆函数，且５≤ｆ（ｉ）≤（ｎ＋４）。从上式可以看到，密钥的变换是在模Ｍ同余类域上进行的，并同

时在域的两个群上实施运算。显然，ＭＨ变换是ＲＥＥＳＳＥ２变换ｚ—ｏ时的特例。

不难验证，（Ｃ，，Ｃｚ，…，Ｃ。｝已不具有超递增序列的性质，

因此它是非超递增序列。

２．５从非超递增序列子集和得到超递增序列子集和

２．３．１

非超递增序列子集和的计算设｛Ｃｌ，Ｃ２，…，Ｃ．）

为ｎ项非超递增序列（可以理解为公钥），ｂ１６。…６＾为ｎ位二进

制数，则非超递增序列子集和为：Ｅ。＝三（Ｃ，＊ｂ，）ｒｏｏｄＭ（ｉ

ｆｒｏｍ

１

ｔｏ行），如果ｂｉｂ２…ｂ。是明文分组，则Ｅ．ｖ是相应的密

文。

２．３．２超递增序列子集和的导出

从近世代数知，倘若

Ⅳ－１为Ｗ的乘法逆元，则有（Ⅳ＊Ｗ＿１）ｍｏｄＭ一１。

倘若一ｚ为Ｚ的加法逆元，则有（Ｚ＋（－－Ｚ））ｒｏｏｄＭ一０。且对任意正整数Ｋ＜Ｍ，有：

（Ｋ＊Ｚ＋Ｋ＊（一Ｚ））ｒｏｏｄＭ一（Ｋ＊Ｚ＋（一（Ｋ＊Ｚ）））

ｒｏｏｄ

Ｍ一０

那么，如何在超递增序列、工作参数和杠杆函数的基础上从Ｅｗ求出超递增序列子集和呢？即如何求出Ｅｓ＝三（Ａ＊

ｂｉ），（ｉｆｒｏｍ１

ｔｏ

ｎ）。如果能．则可以从Ｂ中恢复出原二进制

明文ｂｌｂ２．．・玩。

理论上，我们可以这样来推算．首先．令：Ｋ＝＝（，（ｉ）＊ｂｉ）。则有：ＥＮ（三（Ｃ，＊ｈｉ））ｒｏｏｄＭ＝（三（（Ａｉ＋Ｚ＊，（ｉ））・Ｗ＊ｂｉ））ｒｏｏｄ＾ｆ＝（Ⅳ＊三（（Ａ‘＋Ｚ＊，（ｉ））＊如））ｍｏｄＭ

因此。（ＥＮ＊Ｗ一１）ｒｏｏｄＭ一（三（（Ａ＋Ｚ＊／（ｉ））＊ｈｉ））ｒｏｏｄＭ

＝（三（Ａｉ＊ｂｌ＋Ｚ＊，（ｉ）＊ｂ））ｒｏｏｄＭ＝（２（Ａｉ＊６｜）十三（Ｚ＊厂（ｉ）＊ｂ，））ｒｏｏｄＭ

＝（三（Ａ．＊６１）＋Ｚ＊三（，（ｉ）＊ｂｉ））ｒｏｏｄＭ＝（三（Ａ＊ｈ）＋Ｚ＊Ｋ）ｍｏｄＭ

进而，（ＥⅣ＊Ⅳ一１＋（－－Ｚ）＊Ｋ）ｒｏｏｄＭ一（ＥＮ＊Ｗ一１＋（一（Ｚ＊Ｋ）））ｒｏｏｄＭ

＝（三Ａ．ｂｉ＋Ｚ＊Ｋ＋（一（Ｚ＊五）））ｒｏｏｄＭ＝（三（Ａ＊ｂｉ））ｒｏｏｄＭ

；三（Ａ．＊白）一Ｅｓ

所以，Ｅｓ＝＝（Ａ＊６ｆ）＝（ＥＮ＊Ｉｙ一１＋（－－Ｚ）＊Ｋ）ｍｏｄＭ

然而，在实际情况中，我们并不事先知道二进制明文（６。ｂ。…玩），因而就无法直接确定Ｋ，但由于尺的取值范围有限，因此可以搜索Ｋ，并根据既能否被｛Ａｒ｝的某些项相减为０来验证Ｋ，在Ｋ得到验证的同时，也就推导出了原二进制明文。搜索Ｋ的次数不会超过三厂（ｉ），其与行是多项式时间复杂度相关，故求解是可行的。

２．３．３解的唯一性问题由于｛Ｇ）是非超递增序列，其子集与子集和之间不存在一一对应关系，因此，采用边搜索边验证的方法来求取Ｅｓ时，符合条件的Ｅｓ值可能不止一个，从而会导致明文解６ｌ如…６－的不唯一性．

万　

方数据设密文Ｅｘ可由｛ｃ．）的两个不同子集的累加和得到．因此：

Ｅ．ｖ！（Ｃｘｌ＋Ｃｚ２＋…＋Ｃｘ，）ｉ（国ｌ＋回ｚ＋…＋＠＾）

ｍｏｄ

Ｍ

即：（（Ａｘｌ＋厂（ｚ１）＊ｚ）＋（Ａｘ２＋厂（ｚ２）＊ｚ）＋…＋（Ａｚ，

＋ｆ（ｘ。）＊Ｚ））＊Ｗ

；（（匆、＋ｆ（ｙ・）＊Ｚ）＋（匆２＋ｆ（ｙ２）＊Ｚ）＋…＋（缈＾＋

，（∞）＊Ｚ））＊ＷｍｏｄＭ

（Ａｘｌ＋Ａｓｃ２＋…＋Ａｘ，＋ｋｌ＊Ｚ）兰（毋１＋匆２＋…＋匆＾

＋＾２＊Ｚ）ｍｏｄ

Ｍ

其中，＾１一厂（ｚ－）＋厂（ｚ２）＋…＋厂（ｚ。），ｋ２一厂（ｙ１）＋，（弛）＋…＋厂（帅）

不妨令女１≥ｋ２，由于上述变换是在模Ｍ加法交换群上进

行，故有：

Ｚ＊（ｋｌ—ｋ２）ｉ（匆ｌ＋匆２＋…＋匆＾）＋（一（Ａｘｌ＋Ａｚ２

＋…＋Ａｘ．））ｍｏｄ

Ｍ

简记为：ｚ＊（ｋｌ－－ｋ２）Ｅ（（三Ａｙｉ）＋（一互ＪＡｘ，））ｍｏｄＭ

上式表明，当Ｂ的值不唯一时，必有ｚ的值与（（三Ａ斗）＋（一三Ａ≈））相关。其逆否含义是，如果Ｚ的值与（（三ＡＭ）＋（一三Ａ而））无关，则Ｂ的值将会唯一。

当某个元素Ａ。同时出现在（黝Ｍ）与（一三Ａ劫）中时，则

它们会相互抵消，对ｚ的取值没有影响。因此，考虑到那些不同时出现在（三Ａ∞）与（一ＪＪＡｘｊ）中的元素，当序列长度为ｎ时，（（三Ａ弘）＋（一三以句））型值的个数最多为２。。又由于ｚ在

Ｍ范围内取值，如果让Ｍ＞２“＋３”，即（１０９２Ｍ－－ｎ）＞３２，那么，ｚ取得（（三Ａｙ。）＋（一三Ａ而））相关值的概率会低于１／ｚ”。所以，选取适当的Ｍ，就可以使凰不唯一的概率降至非常非常

低，且同时满足序列｛Ａ｝的密度大于０．６４５。另外，通过事先排

查一些ｚ值，可以使艮不唯一的概率进一步降低。

５

ＲＥＥＳＳＥ

２体制的算法描述

目前，ＲＥＥＳＳＥ２公钥体制包括密钥生成、加密和解密等三个算法。从效率方面考虑，公钥算法一般只用来加密对称算法的会话密钥，而用对称算法去加密明文。为防止“ＬＯＢ—Ｌ３归约基”方法攻击，本体制应用了“冗余加密”的思想，即会话密钥来源于一个随机数据块的ＨＡＳＨ输出，而加密与解密是针对随机数据块进行的。

５．１密钥生成算法

（１）产生项数为ｎ的超递增序列（Ａ。，凡，…，Ａ｝

（２）选取适当的正素数Ｍ，使Ｍ＞三Ａ和（ｎ／ｌ０９２Ｍ）＞

０．６４５以及（１０９２Ｍ—ｎ）＞３２

（３）随机产生两两不同的杠杆函数值厂（１）、ｆ（Ｚ）、…、，

（ｎ），５≤ｆ（ｉ）≤（ｎ＋４）

（４）选取适当的正素数Ⅳ、ｚ，其满足Ⅳ＜肘、ｚ＜Ｍ（５）计算非超递增序列Ｃｉ＝（（Ａ＋ｚ＊ｆ（ｉ））＊ｗ）ｍｏｄ

Ｍ，（ｉ＝１，２，…，靠）

（６）从（ｚ＋（一ｚ））ｍｏｄＭ—ｏ求出一ｚ，从（ｗ＊Ｗ－１）

ｍｏｄ肘＝１递归求出Ⅳ“［６］。

然后，以（｛Ａ，｝、ｗ～、一Ｚ、Ｍ）作为私有密钥，（｛ｃｌ｝、膨）作为公开密钥，，（ｉ）可舍弃。

５．５加密算法

设（｛Ｃｉ｝、Ｍ）为公开密钥，ｈ为随机数据块分组数，ｌ＜ｈ≤３２。

（１）随机产生（＾¨１）比特的数据块６ｔｌ６１２…６。６２－翰…６２．

・１４９・

……６＾１６＾２…６＾．，其ｎ比特的ＨＡＳＨ（６ｌｌｂｌ２…ｂｌ。，ｂ２ｌｂ２２…ｂａ，……，ｂｈｌｂ＾２．・・ｂ一。）输出作为会话密钥尺；

（２）令ｉ一１；

（３）令Ｅ．ｖ．一０，ｊ—Ｉ；

（４）如果ｂ．，一Ｉ，则Ｅ．ｖ．一（Ｅ．ｖ，＋Ｃ，）ｒｏｏｄＭ

（５）做ｊ—ｊ＋Ｉ，如果ｊ≤”，贝４转至（４）；

（６）做ｉ—ｉ＋Ｉ，如果ｉ≤．１ｌ，则转至（３），否则．结束。最后，得到密文（子集和）序列｛Ｅ．ｖ。、Ｅ．ｖ：、…、Ｅｍ）。

５．４解密算法

设（｛Ａ，｝、Ⅳ～、一Ｚ、Ｍ）为私有密钥，｛Ｅ■、ＥＭ、…、Ｅｍ）

为密文（子集和）序列。

（１）令ｉ一１；

（２）做Ｅ．ｖｆ：＝（ＥⅣ，＊Ｗ一１）ｍｏｄＭ；（３）做ＥⅣ，一（ＥＮ，＋（～Ｚ））ｍｏｄＭ；（４）令ｂ１６１２…“各位皆为０，Ｅｓ—Ｅ．ｖ。，ｊ＝ｎ；（５）如果Ｅｓ≥ＡＪ，贝Ⅱｂ。，＝１并且Ｅｓ—Ｅｓ—Ａ，；

（６）做Ｊ一歹一１，如果Ｊ≥１并且Ｂ≠０，则转至（５）；（７）如果Ｂ≠０，则转至（３）；

（８）做ｉ—ｉ＋１，如果ｉ≤＾，则转至（２），否则，结束。最后，以雄比特的ＨＡＳＨ（６１１６１２…６１．，如ｌｂ２２…６２。，…，６＾１“２…ｂｈ．）输出作为会话密钥Ｋ。

４

ＲＥＥＳＳＥ２体制的安全性分析

４．１

有效抵御极小点攻击方法

在ＭＨ变换中ｔＣｉ＝（Ａ＊彬）ｒｏｏｄＭ．由于Ｇ一（Ａ＊Ⅳ）在不求余时仍是超递增序列．因此，这种变换并没有改变超递增序列的特性，ＡｄｉＳｈａｍｉｒ正是抓住了这个“尾巴”以极小点方法从公开密钥中恢复出私有密钥，一举将ＭＨ背包体制破译。如果企图通过多次ＭＨ变换将超递增序列变得彻底一些，则随着模数的增大，背包密度会降低，因而，可利用ＬＯＢ－Ｌ３归约基方法将密文破译【１．３］。这正是Ｍｅｒｋｌｅ和Ｈｅｌｌ—ｍａｎ的两难困惑所在。

在ＲＥＥＳＳＥ２变换中，Ｇ＝（（Ａ＋Ｚ＊厂（ｉ））＊ｗ）ｍｏｄＭ．当Ⅳ≠１时，由于｛Ａ｝＝｛Ａ。＋Ｚ＊厂（ｉ）｝不是超递增序列，｛Ａ：｝不满足“序列的每一项大致是前面一项的两倍”的假设，因此，极小点方法将失效．当Ⅳ一１时，Ｃ，＝（Ａ＋Ｚ＊，（ｉ）），由于，（ｉ）的存在，锯齿曲线极小点的聚点不可能存在，因此，极小点方法同样将失效。

４．２有效抵御ＬＯＢ－Ｌ３归约基攻击方法

对于背包序列｛Ｃｌ，Ｃ：，…，Ｇ｝，其背包密度Ｄ—ｎ／ｌｏｇ：

（ｍａｘ

Ｃｉ），其中ｎ为序列长度（序列项数）。考虑到模数肘＞

（ＺＡ，）和Ｍ＞（ｍａｘＧ），所以，背包密度也可以表示成Ｄ＝ｎ／ｌｏｇ。Ｍ，即序列长度与模数的比特长度之比。

Ｌａｇａｒｉａｓ－Ｏｄｌｙｚｋｏ和Ｂｒｉｃｋｅｌｌ都已证明了对于所有Ｄ＜０．６４５的背包公钥体制皆可以破译其密文Ｃ１】．也就是说，不管是ＭＨ变换还是ＲＥＥＳＳＥ２变换，只要背包密度Ｄ＜０．６４５，就可以通过ＬＯＢ—Ｌ３归约基方法从密文子集和ＥＮ＝（】Ｅ＊ｂｉ）

ｒｏｏｄ

Ｍ中恢复出明文（６ｌ岛…反）．

那么，这是否意味着只要取Ｄ＞Ｏ．６４５，就可以使ＬＯＢ－Ｌ３

归约基方法失效呢？令人遗憾的是Ｌａｇａｒｉａｓ－Ｏｄｌｙｚｋｏ和Ｂｒｉｃｋｅｌｌ的否命题并不总是成立．

作者参照ＬＯＢ方法编制了利用Ｌ３算法破解密文子集和问题的程序，经过对不同长度和模数构成的不同密度的背包所做之实验分析，发现：（１）即使当Ｄ＞Ｏ．６４５时，有些密文也

・１５０・

万　

方数据能被破译，但并不是每个密文都能被破译；（２）随着背包密度

的提高，密文被破译的可能性越小；（３）当背包密度相同时，随着背包长度的增加，密文被破译的可能性越小。关于第（３）点，

作者认为主要是由于背包的攻击密度降低了。所谓攻击密度

是指单位时间内所能攻击的最大次数与背包可能的密文数Ｍ之比。

从上述第（３）点知，当密度相同时（例如０．７５），随着序列

长度的增加．每次攻击的成功率Ｐ会越来越少，如果以ｈ次连续攻击作为一轮，则每轮攻击的成功率为１／ｐ‘。据实验当”≥

９６时，ｈ的值在３２范围之内，并可以使１／ｐ‘＜１／２“，这个概率已经完全达到实用的程度。

在ＲＥＥＳＳＥ２体制中，加密是针对随机数据块（６。。ｂ，∥・ｂ，。

６２。ｂ２ｚ．－・６∥…”以。６＾２．．・乩．）进行的，并生成密文序列｛ＥⅣ１、Ｅ．ｖｉ、

…、Ｅｗ・｝。当ｎ≥９６时，可以选取适当的模数Ｍ，使得ＬＯＢ一１。３

归约基方法不可能连续攻破｛Ｅｗｔ、Ｅ－ｖｚ、…、Ｅｍ｝，即不可能完

整破译出（６１１６１２…ｈｉ．６２１ｂ２２…ｂ２＾．…““ｌ“２…ｂＡ。），从而，依据ＨＡＳＨ函数的特点，不可能破译出ｎ比特的会话密钥ＨＡＳＨ

（６１１６１２…ｂ１．，ｂ２１ｂ２２…ｂ２．，……，６＾ｌ６＾２…ｂｈ．）。注意，该Ｍ还应该

使明文分组ｂｉ。ｂｉ２．．・ｂｉ。的不唯一性概率降至几乎为零。

４．５杠杆函数，（１）的不确定性

首先，如果攻击者企图猜测，（ｉ）的排列，则当ｎ＞８０时，它的全排列数将达Ｐ。。”，远远大于２”，根据目前的万亿次计算机速度，厂（ｉ）的排列数目不可能有效穷举。其次，令Ｚ一（ｚ

＊，（ｉ））ｒｏｏｄＭ，Ｇ一（（Ａ＋Ｚｉ）＊Ⅳ）ｒｏｏｄＭ，根据群的知识，当Ｚ确定时，Ｚ与ｆ（ｏ两者不能唯一确定。当ｚ确定时，由于

Ⅳ的存在，则Ｇ与，（ｉ）之间没有一一对应关系。这些充分说明，在某个具体的公钥序列中，ｆ（ｉ）的排列是不确定的。另外，还可以通过一个置放函数来打破｛Ａ｝的排列顺序。

４．４密钥映射的不充分性和不可逆性

在ＲＥＥＳＳＥ２体制中，私有密钥虽然包括｛Ａ』｝、，（ｉ）、ｚ、Ⅳ四部分（，（ｉ）在解密时未用到），但却只有Ｃｉ＝（（Ａ。＋Ｚ＊，（ｉ））＊Ⅳ）ｍｏｄＭ的显性映射，映射是不充分的。该表达式：实际包含了ｎ个等式和（２ｎ＋２）个未知变量，所以，通过数学：方法求解｛Ａ。｝、Ｗ和ｚ是困难的。同时这种映射的不充分性，使得公钥与私钥之间不存在相对确定的函数可逆性。

５

ＲＥＥＳＳＥ２体制的特点与优越性

５．１

同时利用了计算机的数孛运算与逻辑运算功能

传统的公钥密码体制一般只利用了计算机的数字运算功能，而ＲＥＥＳＳＥ２体制不仅利用了计算机的数字运算功能，也利用了计算机的逻辑运算功能，是数学知识与软件知识相结合的产物。

５．２公钥与私钥之间不存在相对确定的函数可逆性正如４．４节所言，由于公钥与私钥之间映射的不充分性，公钥与私钥之间不存在相对确定的函数可逆性，且大量私钥被隐藏。而传统的公钥密码体制中，公钥与私钥之间一般存在相对确定的函数可逆性，且只有少数几个或一个工作变量作为私钥被隐藏．

５．５揭示了提高公钥体制安全性的另一条途径正如引言所述，多项式环上的ＭＨ背包体制及椭圆曲线上的Ｅ１Ｇａｍａｌ体制的安全性与其在简单代数系统上相比都得到了提高。这是一条对运算符进行组合的途径，是一条纯数学的途径。但是，由于简单代数系统与复杂代数系统之间（包括群之间、环之间、域之间）存在同构或同态现象，因此，简单

代数系统中的安全隐患在复杂代数系统中应该同样存在，并且在复杂代数中，公钥体制的安全性仍较大地依赖于计算机

的运算速度。

而ＲＳＡ是带模乘法，ＥＣＣ是复合运算符，由于乘法、复合运算符是由基本运算符（加法、减法等）构成的，因此，完成一个复合运算所需的时间要远远多于一个基本运算所需的时间。

结束语在本文，我们虽然提出了ＲＥＥＳＳＥ２公钥体制的

理论算法．但是在技术实现上，还应该对ＲＥＥＳＳＥ２的解密算法进行进～步优化，争取使其时间复杂度降至Ｏ（ｎ２）的水平。

另一方面，我们从ＲＥＥＳＳＥｌ和ＲＥＥＳＳＥ２体制中看到，对

运算数进行组合是提高公钥体制安全性的另一条途径．这是

一条数学与软件相结合的途径。这种途径要求公钥体制必须是序列密码体制。在ＲＥＥＳＳＥｌ和ＲＥＥＳＳＥ２体制中，运算数的

组合与排列是由杠杆函数ｆ（ｉ）实现的，使得体制的安全性对

还应在模数和序列长度确定的情况下，测定最少冗余加密次数。最后，我们期待同仁对ＲＥＥＳＳＥ２公钥体制做出更深入的安全性分析。

ｔ

计算机运算速度的依赖程度非常低。通过运算符组合来提高安全性有如对单个ＣＰＵ提高速度，这种提高是有极限的。通过运算数组合来提高安全性有如对多个ＣＰＵ并联提速，这种

提高是无极限的。

参考文献

１卢开澄．计算机密码学（第２版）．北京：清华大学出版社，１９９８

２

Ｓｃｈｎｅｉｅｒ

５．４易于硬件实现且运算速度快

ＲＥＥＳＳＥ２体制的加密算法与解密算法中大部分是模加运算和逻辑判断，所以，易于硬件，特别是简单硬件与ＣＰＵ实

现。

Ｂ（美）．ＡｐｐｌｉｅｄＣｒｙｐｔｏｇｒａｐｈｙ（应用密码学，吴世忠．祝世

雄等译）．北京：机械工业出版社，２０００

３冯登园，密码分析学．北京：清华大学出版社，２０００

４冯克勤，李尚志．近世代数引论．合肥：中国科学技术大学出版社，

２００２

与流行的ＲＳＡ体制、ＥＣＣ（椭圆曲线上的Ｅ１Ｇａｍａｌ）体制相比，ＲＥＥＳＳＥ２也有速度上的优势（即使考虑到冗余加密和

ｏ（ｎ３）时间复杂度解密等因索）。这是因为：（１）ＲＥＥＳＳＥ２的模数可以不超过１９２比特，而ＲＳＡ至少为１０２４比特，ＥＣＣ也常为１９２比特；（２）ＲＥＥＳＳＥ２的运算符主要是基本的带模加法，

５苏盛辉．ＲＥＥＳＳＥｌ公开密钥密码体制．计算机工程与科学，２００３

（Ｓ）

６苏盛辉，李国华，王其文．模运算的新性质及求模逆元的递归算法．

信息安全与通信保密。２００１（１１）

（上接第１３６页）个具体子类。通过委托，客户不需了解子类的细节，就可以具

有不同的行为。

总之，行为抽象可用于以下几种场合：

・需要从类中分离出行为，以便可以交换、保存、修改、共

享或者调用相互独立的行为对象；

・需要在运行时选择行为；

行为抽象方法所产生的结构被认为是在众多设计模式中使用的基本设计模式。我们认为，在设计模式中存在着一些基本的设计方法，它们只使用类、对象、方法、方法调用和数据成

员的概念，但能反映基本的ＯＯ设计原则。我们可以从这些简

・一些类的区别仅仅在于一个或者几个方法的不同。这样，增加新的类，实现这些不同的行为，可以以统一的方式使用具有不同行为的类。

・在选择不同的行为时，需要使用大量的条件判断代码。下面使用ｚ中的方法，以ｂｒｉｄｇｅ模式为例，说明设计模式与行为抽象的关系：

Ｏｂｊｅｃｔｉｆｉｅｒ（Ｉｍｐｌｅｍｅｎｔｏｒ，Ｃｏｎｃｒｅｔｅｌｍｐｌｅｍｅｎｔｏｒ；６１。一，

Ａｂｓｔｒａｃｔｉｏｎ）

ＡｂｓｔｒａｃｔＩｎｔｅｒｆａｃｅ（Ａｂｓｔｒａｃｔｉｏｎ。Ｏｐｅｒａｔｉｏｎ）

ｒ：Ａｂｓｔｒａｃｔｉｏｎ

（１）（２）（３）（４）（５）

单的基本设计方法入手学习面向对象设计方法。另外，研究这些基本设计模式，可以更好地学习和掌握更加复杂的设计模式，发现设计模式之间的关系以及发掘新的设计模式。

参考文献

１

ＧａｌＹｘｌｎａ

ｓｏｎ

Ｅ，ＨｅｌｍＲ，ＪｏｈｎｓｏｎＲ，ＶｌｉｓｓｉｄｅｓＪ．Ｄｅｓｉｇｎ

Ｐａｔｔｅｒｎｓ．Ａｄｄｉ－

Ｗｅｓｌｅｙ．１９９５

Ａ，Ｔｒｏｔｔ

２

Ｓｈａｌｌｏｗａｙ

ｓｐｅｃｔｉｖｅ

ｏｎ

Ｊ

Ｒ．Ｄｅｓｉｇｎ

Ｐａｔｔｅｒｎｓ

Ｅｘｐｌａｉｎｅｄ：ＡＮｅｗ

ｐｅｒ—

Ｏｂｊｅｃｔ・０ｒｉｅｎｔｅｄＤｅｓｉｇｎ．Ａｄｄｉｓｏｎ—Ｗｅｓｌｅｙ，２００２

Ｃ：ＣｏｎｃｒｅｔｅＩｍｐＩｅｍｅｎｔｏｒｉ∈１’‘ｍ

ｒＩ

３熊兵舫．张志祥．设计模式的软件度量分析．青岛大学学报，２００３，

增刊

４

ｏｐｅｒａｔｉｏｎ＜＜。ｃ．ｏｐｅｒａｔｉｏｎｌｍｐ

（Ａｂｓｔｒａｃｔｉｏｎ，

Ｉｍｐｌｅｍｅｎｔｏｒ，

ＡｂａｄｉＭ．Ｃａｒｄｅｌｌｉ

Ｙｏｒｋ，Ｉｎｃ．，１９９６

Ｌ．ＡＴｈｅｏｒｙｏｆＯｂｊｅｃｔｓ．Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ

Ｎｅｗ

Ｂｒｉｄｇｅ

ｃｏｎｃｒｅｔｅｌｍ—

（６）

５

ｐｌｅｍｅｎｔｏｒｊ５“”，ｏｐｅｒａｔｉｏｎ，ｏｐｅｒａｔｉｏｎｌｍｐ）

客户（这里是Ａｂｓｔｒａｃｔｉｏｎ）端增加了一个抽象接口。

Ｓｍｉｔｈ

ＪＭ．ＳｔｏｔｔｓＤ．Ｅｌｅｍｅｎｔａｌ

ａｎｄ

ｄｅｓｉｇｎｐａｔｔｅｒｎｓ：Ａｌｉｎｋｂｅｔｗｅｅｎ

Ｒｅｐｏｒｔ

ＴＲ一０２一

可见，Ｂｒｉｄｇｅ模式中使用了行为抽象方法，在此基础上在总结面向对象中封装性不仅仅体现在对象的状态和行为的封装，行为抽象中也体现了一种封装性：抽象类封装了各

６

ａｒｃｈｉｔｅｃｔｕｒｅｏｂｊｅｃｔ

ｓｅｍａｎｔｉｃｓ“Ｔｅｃｈｎｉｃａｌ

ｏｎ］．Ｕｎｉｖ．ｏｆＮｏｒｔｈ

Ｚｉｍｍｅｒ

ｇｕａｇｅｓ

ｏｆ

Ｃａｒｏｌｉｎａ。２００２

ｂｅｔｗｅｅｎｄｅｓｉｇｎｐａｔｔｅｒｎｓ．ＩｎｐａｔｔｅｒｎＬａｎ・

９９４

Ｗ．Ｒｅｌａｔｉｏｎｓｈｉｐｓ

ＰｒｏｇｒａｍＤｅｓｉｇｎ．Ａｄｄｉｓｏｎ—Ｗｅｓｌｅｙ，１

・１５１・

万方数据　

REESSE 2公开密钥密码体制

作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：

苏盛辉， 杨炳儒

苏盛辉(北京石油化工学院信息管理系,北京,102617)， 杨炳儒(北京科技大学信息工程学院,北京,100083)计算机科学

COMPUTER SCIENCE2004，31(9)1次

参考文献(6条)

1. 卢开澄 计算机密码学 1998

2. Schneier B. 吴世忠. 祝世雄 应用密码学 20003. 冯登国 密码分析学 2000

4. 冯克勤. 李尚志 近世代数引论 2002

5. 苏盛辉 REESSE1公开密钥密码体制[期刊论文]-计算机工程与科学 2003(05)6. 苏盛辉. 李国华. 王其文 模运算的新性质及求模逆元的递归算法 2001(11)

引证文献(1条)

1. 苏盛辉 REESSE1+公钥密码体制的算法[期刊论文]-中国科技论文在线 2006(3)

本文链接：http://d.wanfangdata.com.cn/Periodical_jsjkx200409041.aspx

授权使用：国家图书馆(gjtsg)，授权号：432a0cae-49cc-4f97-aa6f-9eb400e8b0c0

下载时间：2011年3月28日