（基础数学专业论文）公钥密码学中的二次多元多项式.pdf

摘要 由w a n g 等提出的m f e 体制【l 】已经被d i n g 等用s o l e s 攻击方法攻破【2 】。在本论 文中我们给出了一种改进的m f e 体制，其可以抵挡住这种攻击，同时如果选择恰 当的参数其还可以抵挡住秩攻击和x l & g r 6 b n e r - 基攻击 硎体制由于其特殊的设计，加密和解密都很有效设计该体制的实现的 关键在于构造一个次数为m 2 的多项式q m c y l ，办) 和一个关于x l ，而的二 次多项式集合 g l ，。口l 使得锄( 9 ”一，毋) 为关于衲，x s - - 次多项式。我们 称q 肼( 9 l ，吼) 为q 肼- 类型函数。在【3 】中给出了次数为磐( 七3 ) 的q 2 一类型函数 的对称构造方法。在本论文中我们给出了基于该函数的一个t t m 体制的实现，同 时我们用类似： ：d i n g 和h o d g e 在【4 】中提出的方法攻破了该实现。 关键词：m q 一体制，m f e 密码体制，h o l e s 攻击，”聊密码体制。 t h em f e c r y p t o s y s t e mp r o p o s e db yw a n g e ta l - 【l 】i si n s e c u r ed u et oh o l e sa t t a c k b yd i n ge ta 1 1 2 】i nt h i sp a p e rw ed e s c r i b ea l li m p r o v e dm f ec r y p t o s y s t e m ，w h i c hc a l l r e s i s tt h eh o l e sa t t a c k m e a n w h i l ew i t l lw e l l - c h o s e nl y a r m n e t e r si tc a na l s or e s i s tr a n k a t t a c ka n dx 啪r 6 b n e rb a s i sa t t a c k t h et t m c r y p t o s y s t e mi sv e r yf a s ti ne n c r y p t i o na n dd e c r y p t i o nd u et oi t sd e s i g n a n ds m a l lu n d e r l y i n gf i e l d t h es u c c e s so ft h i ss y s t e mr e l i e so nt h ec o n s t r u c t i o no fa p o l y n o m i a lq 朋l ，乃) o f d e g r e em 2a n das e to f p o l y n o m a i l sl 钔，俄) ，a l lo f w h i c hh a v ed e g r e e2i n 却，以，s u c ht h a t 锄臼“，缈) i sap o l y n o m a i lo fd e g r e e2 i n 柏，毛w ec a l lq m ( q l ，吼) q 所m o d u l e c h o ue la 1 g a v eas y s t e m a t i cw a yt o c o n s t r u c tq 一m o d u l e 【3 】i nt h i sp a p e rw ed e s c r i b ea l li m p l e m e n t a t i o no ft t mc r y p - t o s y s t e mb a s e do nt h i sq 2 i m o d u l e ，t h e nw i t hm e t h o ds i m i l a rt ot h eo n ep r o p o s e db y d i n ga n dh o d g e 【4 】，w eb r e a kt h i si m p l e m e n t a t i o n k e yw o r d s ：m q - c r y t o s y s t e m ，m f ec r y p t o s y s t e m ，h o l e sa t t a c k ，t t mc r y t o s y s t e m 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成果。 据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写 过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说 明并表示谢意。 作者签名：卫叠垒垒 日期 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保留学位 论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学位论文 用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学位论文的 内容编入有关数据库进行检索。有权将学位论文的标题和摘要汇编出版。保密的学 位论文在解密后适用本规定。 学位论文作者签名：翌至迎兰! 圭 日期：掣 导师签名：? 存乏王 日 1 引言 1 1 研究背景 在信息化的今天，信息传输的安全性显得至关重要，公钥密码学是保证信 息安全的一个重要工具，然而遗憾的是现在实际应用中的公钥密码体制其安全 性主要基于几个数论问题：要么是大数分解，要么是离散对数，这两个问题目 前都被认为是难解的。不过s h o t 的借助于量子计算机的多项式时间的量子算法 可以解决这两个问题【5 1 ，虽然量子计算机的出现还需要一段时间，但这就要求 我们必须去研究新的密码体制。我们知道无论是基于大数分解的r s a 体制还是 基于离散对数的e i g a m a l 体制，它们的验证条件都是一个一元方程。比如说公钥 为( p ，n ) 的r s a 加密体制，判断消息y 是否是消凰的加密只需判断，兰ym o dn 是 否成立，显然r - - = ym o dn 是一个关于j 【的一元方程。因此一个很自然的推广就 是考虑用几个多变量方程作为判定条件来构造密码体制。下面我们仍以加密为 例看一下这种推广。令( 而，而) 和j 一，) 分别是消息和消息的加密。则我们 称o 一，y 册) 是( 而，而) 的加密，如果 ip i ( x l ，而) = y l i 厶o l ，一，而) = y m 成立，其中只为加密者对外公布的作为其公钥的多变量多项式。 加密的设计者一般可以采用两种方法来构造其公钥： 1 在一个较大的有限域上用较少的变量来构造，这样构造的安全性是基于大数分 解的困难性，和r s a 体制相比，他希望得到相同的安全性，但计算上更有效。 2 在一个较小的有限域上用较多的变量来构造，这样构造的安全性是基于多变量 多项式组即使二元域上的多变量二次多项式组的求解是n p - 完全的。 本文研究的m q 体制便属于第二种类型。一个m q 体制是安全性基于m q - 问题的密 码体制。所谓的m q 问题是指有限域上的二次多变量多项式组的求解。m q 问题 是n p - 完全的，并且到目前为止尚未证明量子计算机能够有效的解决m q 问题。此 外一般而言m q 体制比基于数论问题的密码体制在计算上有效的多。这样就产生了 许多m q 体制。在【6 】中作者把目前存在的m q 体制大致分为4 种m q - 陷门，它们又分 为两类：一类是虽然整个公钥在一个较小的有限域上，但中心映射却在这个较小的 有限域的同一个扩域上，这一类作者称为m i x e d - f i e l d ，如m n 体制【7 】和h f e 体制【8 】； 另一类是整个公钥和中心映射都在同一个有限域上，这一个类称为s i n g l e - f i e l d ， 如u o v 体制【9 】，它是平衡的油和醋密码体制【l o 】的推广，还有s t s 体制【1 l 】。而【1 】中 给出了一种不同- = m i x e d f i e l d 和s i n g l e - f i e l d 的另一类m q 体制，其公钥在一个较小的 有限域上，但中心映射却在这个较小的有限域的几个扩域上，这几个扩域可以相 同也可以不同。作者把这类m q i 体制称为m e d i u m f i e l d ，并给出了m f e 体制，然而遗 憾的是m f e 体制被d i n g 等用s o l e s 的方法攻破t 2 1 。在1 3 节中我们将详细介绍这几 种m q 体制。 在常见的m q 体制中只有删体制【1 2 】( 见1 3 3 节) 的中心映射是通过几个映射的 复合来得到，并且保证复合后的映射仍使公钥为二次映射( 到目前为止所有给出 的硎体制的实现的中心映射均为两个映射的复合) ，在2 1 节中我们利用这种思 想通过在m f e 的中心映射上复合一个新的映射并且保证复合后的映射仍使公钥为 二次映射来构造了一种改进的m f e 体制，据我们所知这是第一次把这种思想运用 到m f e 体制中去，并且这种改进的m f e 体制能够抵挡住h o 蚴击。同时如果选择 恰当的参数其还可以抵挡住秩攻击和x l & g r 6 b n e 堪攻击。 m i 体制是第一个被提出来的有前途的m q 体制【7 】，它已经被p a t a r i n 用线性化方 程的攻击方法攻击掉了【1 3 】。所谓的一个线性化方程是下列形式的方程 口o x i y j + b i x i + 呐+ d = o 其中再是明文变量，”是密文变量。后来p a t 撕n 等提出了x l 方法作为l e 攻击的推 广【1 4 】，这种方法是g r 6 b n e r 基和线性化方法的组合。u ! 攻击的另一种推广是二次线性 化方程( s o l e s ) 攻击【8 】。所谓二次线性化方程是下列形式的方程 口班砌+ 6 u 撕+ q 而+ 靠珊+ 劬+ 厂= o n i e 等用二次线性化攻击攻破了f r 】聊密码体制的一个新实现【1 5 】。刚才我们已经提 到最近d i n g 等用同样的方法攻破了m f e 体制【2 】。作为进一步的推广，在【2 】中作者 提出称关于密文变量为高次，关于明文变量为一次的多项式为高次多项式方程 ( h o l e s ) 。 2 m o h 提出了t i m 密码体制 1 2 1 。由于它的特殊设计，其本身的加密和解密都 非常得快。g o u b i n 和c o u a o i s 给出了关于t t m 密码体制的m i n r a n k 攻击并宣称攻破 了这种体制【1 6 】。然而c h e r t 和m o h 拒绝承认这个结果，他们提出另外一个实现来 支持他们的断言【1 刀但是d i n g 和s c h m i d t 用推广的线性化方法攻破了这个新的实 现d 8 。为了抵挡住g o u b i n - c o u r t o i s 的攻击和d i n g - s c h m i d t 的攻击，m 0 h 等又提出了 另外一个新的实现1 1 9 。不过遗憾的是它也已经被攻破了 1 5 1 。构造这类体制的实 现的关键在于构造一个次数为m 2 的多项式q 啊( ) ，l ，一，y f ) 和一个关于确，矗的 二次多项式集合 g l ，q t l 使得q m ( g l ，缈) 为关于而，毛二次多项式。我们 称q 卅( g l ，纺) 为q m 瑛型函数。目前已经提出来几种关于q m 噗型函数的构造， 比如说f l 了c h o u 等提出的关于q 参一类型函数的对称构造方法【3 】和f h w a n g 和c h a n g 提出的 关于不含平方项的鳊类型函数的对称构造方法【2 0 】。由c h o u 等提出的关于q 2 1 类型 函数的对称构造方法是m 0 l l 在d 2 中提出的1 聊体制的第一个实现中q 8 类型函数的 推广，这个实现已经被d i n g 等用h o l e s 攻击方法攻破了【4 】，并且在【4 】中d i n g 等断言 基于c h o u 等提出的q 磐类型函数的”聊密码体制的实现也可以用类似的方法攻破。 在2 2 节中我们给出了一个基于c h o u 等提出的q 2 类型函数的硎密码体制的实现。 在2 3 节的第一步攻击中我们用类似于d i n g 等在【4 】提出的方法从2 2 节中提到的实现中 找到了形如 n+r露 只日新稍矿2 + 仇) f 2 + c i x i + d = o l 西刍+ r z i五l 的方程。在唯密文攻击中对任意给定的有效密文矿，由这些方程，我们可以找到一个 包钉所对应的明文r 的明文空间的一个仿射子空间v ，使得从q 2 , 类型函数得到的 公钥多项式在y 上变为一个常数，这样整个公钥多项式限制在，上就变为了1 3 3 节中 提到的d ej o n q u i e r e 映射，它很容易求逆【1 2 】，然后对其求逆即可得到) ，所对应的明 文，。从而我们证明- j d i n g 等断言的正确性。 1 2 预备知识 在这篇论文中若无具体说明我们用f = g f ( q ) 表示由g 个元素构成的有限 域。a f f - 1 ( p ) 表示f 上所有可逆仿射线性变换组成的集合，所i w f 上的可逆仿射 线性变换是指可以表示为m x + b 形式的映射，其中m f 玎期是可逆矩阵，b p 是向 量。 3 一般而言m q 体制的私钥为t a j 1 ( p ) ，s a 圹1 ( p ) ，p 朋烈p ，p ) ， 其中尸称为中心映射，朋q p ，p ) 表示有刀个输入，t t l 个输出，的二次多项式全体组 成的集合公钥为尹= t o 手 o s 。其中s 用来隐藏明文变量，列丑来隐藏中心映射p 的 特殊结构。m q 体制即可用于加密又可用于签名，下面我们将分别作以介绍。 1 2 i 签名的生成 为了对消，息yep 进行签名，我们首先计算) ，= t - 1 ，然后计算，= 少- 1 ) ， 最后计算工= s - 1 ( ，) 。x 就是对消, g y 的签名。 首先我们看如何对丁求逆，因为丁是可逆仿射线性变换，所以存在可逆矩醐 p 期和a p 使得r = a x - i - a ，所以r - 1 ( 力= a 1 0 一口) 。s 的求逆类似。而对于不同 的中心映射少，求逆不同，在1 3 节我们再具体讨论。 注1 a 对于给定蝌f m 我们只需要求出一个文f n 使得p 叫、) = y 即可o 。 1 2 2 签名的验证 一个消息j 的签名y 是有效签名当且仅当y = 双曲。 1 2 3 加密 一般而言：p p 不是满射，则尹= t0 0s ：p - p 也不是满射。因此 为了使解密唯一，我们需要添加冗余，也即我们选择一个密码学上安全的哈希函数 对明文进行作用求出其对应的哈希值。我们知道对于安全的哈希函数很难找到两个 不同的值使得它们有相同的哈希值，这样对于明文所对应的哈希值，除非我们求出 的值是明文，否则就很难找到另外一个消息使得其所对应的哈希值等于明文所对应 的哈希值。从而加密就分为两步：首先用公钥进行计算，然后计算冗余戈。 1 y ：= 双曲 2 j = 日( 曲，其中日为哈希函数。 1 2 4 解密 对消息y p 进行解密和对其进行签名的生成类似，不同的是当求出) ，= 丁- 1 后，我们需要计算所有满足( ，) = 少的，刀，对于不同的体制，我们得 4 到的j 【，可能不唯一，我们需要从所有可能的解工= s 一1 ) 中选出满足h = 勋h ， 则石即为密文y 所对应的明文。 1 3 m q 基本陷门的构造 在这一小节中我们给出一些m q 基本陷门的构造 1 3 1 不平衡的油和醋体制：u o v u o v 体制首先在【9 】中被提出来，它是平衡的油和醋密码体制【l o 】的推广。其私钥 和公钥如下： 1 私钥： ( a ) s a 矿1 ( p ) ； ( b ) 少= ( q ，只) ，其中2 d n ，只形如： 尸；( ，) = 弓+ 弓+ y = - o + lk = l卢l 2 公钥：尹= p0s 。 我们称而，而为油变量，l 一，而为醋变量。下面我们看关于中心映射少的求 逆，也即对于一个给定的昕，杉) f o ，我们给出如何求一个元素( 巧，硌i ，) p 使得少( 吖，巧，珞l 一，) = ( 吖，蟛) ：随机选择一个元素( 磁1 一，巧) p 叼，把它代入p 中，这时我们可以看到少的每一个分量q 变为了关于( ，) 的 一次多项式，然后我们解线性方程组 i ( ，略i 一，) = 珂 1 只( ，磁l 一，) = 杉 得到解( 吖，) ，则( 吖，磁l 一，) 即为所求：如果无解，则重新选择新 的( 砹l 一，) p 叼重新计算。其有解的概率大概为l 一旧，本质上就是，上一 个0xd 矩阵是可逆矩阵的概率。 5 注1 2 j 榔制中公钥为尹= pos ，脚= 丁0p 0s ，是因为油变量和醋变 量经s 作用后我们b 经无法区分出油变量和醋变量，又因为p 中的所有分量 多项式p ：的形式都一样，再经少作用得到的就是一个通常的二次多项式f 句量， 因此无需再复合r 隐藏任何特殊结构o 2 当n = 2 0 肘就是平衡的油和醋体制。 脚怔薯： 删仨：篡二： 仨芝篡二：誓：三 6 出的u 0 v 体制的推广t i n b o w 体制便同时用到7 这两个陷门 1 3 3t i m 密码体制：t i m 令x 是由2 肼个元素组成的有限域。假设户：+ ，一+ ，是价可逆映射九，咖的 复合，p = 咖o o 九，其中咖是下面两种类型的映射： 1 可逆的仿射线性映射。 2 d ej o n q u i e r e 映射。 它们是只要输入变量经过某个置换后具有下列形式的映射： ( ) ，l ，+ ，) = 办( x l ，而+ r ) = ( 九l o l ，而+ ，) ，饥+ ，o l ，而+ ，” = ( x l4 - q i , 1 ( x 2 ，而+ ，) ，而+ 卜l + 孙+ r - 1 ( 而+ r ) ，而+ r ) 其中g 订：”_ k 为二次多项式函数。 d ej o n q u i e r e 映射的求逆过程为 ( 而，x n + ，) = 万1 ( ) ，l ，+ ，) = ( 噍- 1 1 ( ) ，l ，r ) ，蚓+ ，劬，+ ，) ) 其中而+ ，= + ，( ) ，l ，+ ，) = + ，乃= 蚓( ) ，l ，+ ，) = 乃一g u ( 蝣1 ，蚶+ ，) ， j = n4 - r l ，1 令f = p ( x l ，而，o ，0 ) 。映射，为硎密码体制的公钥，映射集合恸l ，咖1 为 私钥。t r m 密码体制的安全性基于以下两点：第一找到，的逆是不可能的，因为，不 是可逆映射；第二从数学的角度没有方法从公钥f 恢复出私钥渺l ，咖l 。 注1 4 d ej o n q u i e r e 映射是正则s t s 体制中心映射的一个特例，在f 6 l 中作者是 把玎m 体制当作s t s 体制的一种特殊情形来进行分类的。这里我们z 所以把玎m 体 制单独作为一小节介绍，一则是因为我们在1 1 节中b 经提到盼丌m 体割的中心映射 是通过几个映射的复合来得到并且保证复合后的映射仍使公钥为二次映射这 - t s s t s 体制的中心映射只有一个映射不同并且我们根据这种思想在2 l 节构造7 一种 改进i 的j m f e 体制；另一则是因为在2 2 节中我们在构造一个基f q 2 ti o j t t m 体制的实现 时要用到这部分内容，故在这里提前单独作7 详细介绍o 7 1 3 am a t s u m o t o - l m a i 体制a ：m i a m 认体制是由m a t s u m o t o 和i m a i 在【7 】中提出的，它是第一个用两个不同的有限域 即一个基域和这个基域的有限扩域构造m q 体制。下面我们给出m i a 体制的中心映 射令g ( f ) f 【f 1 是有限域f _ e n 次不可约多项式，令e ：= f 【f 】( g ( d ) ，则e 是f 的n 次扩 域。定义域的同构：e p ， 似印- i - a i r + + 嘞一l p 一1 ) = ( a o ，a l ，q ，卜1 ) 旷1 ( a o ，口“，d n - 1 ) = a o + a l t + + n ，卜l | ，i 一1 令a n 满足( 矿一l ，矿+ 1 ) = l ，其中g = i f i ，定义：e e ，少7 ( x ，) = x , t 1 + 矿) 。因 为( 矿一1 ，矿+ 1 ) = l ，所以存在t 使得f ( 1 + 矿) 兰lm o d ( 矿一1 ) ，则p 1 ) = x 玎。m i a 体 制的中心映射为p - - = 驴0 o 旷1 ，其逆为尸一1 = 妒0 矿一10 旷1 。 1 3 5h i d d e nf i e l de q u a t i o n s ：h f e h f e 首先在【8 】中被提出来，令e 和妒的定义1 3 4 节，令 少7 7 ) ：= c 飞 厂x d + 矿+ 群x 时+ a 寸+ 一s d予s d 其中c ；，展，a 7 e 。 贝o h f e 的中心映射为少= 妒。尸0 矿1 。少是次数不超过d 的一元多项式，其求逆参 见 2 2 1 中的第四章。对于高次的一元多项式的求解问题现在尚没有有效求法，因 此d 不能太大。 m 执体制似乎是h f e 体制的一个特例：因为m 队体制只是一个单项式，而h f e 体 制是一个多项式。但从密码学的角度，h f e 体制比m 队体制强得多，所有可以用来 攻破h f e 体制的方法都可用来攻破m n 体制，反之则不然。此外，m n 体制所用的 单项式是高次的，而h f e 体制则依赖于多项式有效求根算法的存在性，因此次数要 比m m 体制低得多。因此我们把它们视为两个不同的密码体制。 8 1 3 6m y e 密码体制：m y e m f e 体制首先在【l 】中被提出来。令l 是，的厂次扩域，记l 在f 上的一组基为 巩，啡l ， 定义，线性同构 万：l _ ( 口l 岛+ + 口r 毋) 卜( 口l ，a ，) 我们可以把丌推广到两个，线性同构r l ：l 1 2 一，1 知和a 2 ：l 1 5 一p 5 ，令s 是，1 2 7 上的 仿射线性可逆变换，丁是f 1 5 r 上的仿射线性可逆变换，妒l 是m f e 的中心映射，这样就 可以得到m f e 的公钥： ( l ( h l ，u 2 ，) ，h 5 ( u j ，u 1 2 ，) ) - - - to 刀2o 驴1o7 i 1os ( u l ，u 1 2 r ) 其中妒l ( x l ，x 1 2 ) = ( y l ，y 1 5 ) 满足： y j = x j + x s x s + x 6 x 7 + q l ； 1 2 = x 2 + x g x l 2 + x j o x i i + q 2 ； b - - x 3 + x i x 4 + x 2 x 3 + q 3 ； y 4 = x l x 5 + x 2 x t ； y 6 = x 3 x 5 + 甄x 7 ； y 8 = x j x 9 + x 2 x i l ； r , o = x 3 玛+ x 4 x ； y j 2 = x 5 x 9 + x t x ； k 4 = x 6 x 9 + x s x i j ； y 5 = 蜀甄+ 恐x 8 ； i 7 - - x 3 玩+ 甄x 8 ； y 9 - - x l x l o + x 2 x 2 ； y l l2x 3 x o + x 4 x 1 2 ； y 1 3 = x s x o + x t x l 2 ； r 5 = x 6 x j o + x s x l 2 ； 其中( q l ，q 2 ，q 3 ) ：l 3 一p 7 是三角映射，可以如下表示：令 丌( x i ) = ( 而，耳) ；x ( x 2 ) = ( x r + l ，x 2 ，) ；积x 3 ) = ( 恐r + i ，而，) ，q j - - 0 ，q i k x l ，雄l 】，2 i 3 r 是随机选择的二次多项式，则 q l ( x _ ) q j ( x i ，x 2 ) r = q i ( x l ，砟1 ) 砩； 扛l 2 r = 纺( 却，弘1 ) 岛； 扭，+ l 3 ， q l ( x l ，x 2 ，x 3 ) = q i ( x l ，而一i ) 研； 扛2 r + l 9 私钥为：s ，t , m ，万2 ，锄 m f e 的加密：给定一个明文( m l 一，u r n ) ，其对应的密文就是 ( v l ，1 ，1 5 ，) = 伪l ( u l ，h 1 2 ，) ，h i s r ( u l ，h 1 2 ，) ) m f e 的解密：给定一个有效密文l 一，明5 ，) ，其对应明文就是 s 一1o 丌lo 孵1ox i or 一1 “，v 1 5 r ) s 署 i t 都是可逆仿射变换，其求逆前面已提到。具体九，丌l ，恐的求逆参见【l 】的4 2 节和 其附录b 。 1 4 【3 】中介绍的构造q 2 t 的对称方法 d e f i n i t i o n1 1 3 1 令l = 仞l ，p 2 ，肌l 是关矗l ，一，五多项式集合。令以却，蕾) 是 一个多项式。如果 q ( p i ( x l ，而) ，p 2 ( x l ，而) ，p , ( x j ，五) ) = 八x l ，而) 则称q 为f 在l 的生成多项式。此外如果它是f 在l 所有可能的生成多项式中次数最 小的多项式，则称其为f 在l 的极小生成多项式。 当七3 时，对任意的2 七+ 6 向量p = ( z k + l z k + 2 ，z 3 k + 6 ) ，令矿p 表示p 的左 移亿+ 2 ，z 3 舶) 。定义函数 风= 暖+ l i k - ! - ! - 风一l ( ( 矿) 2 p ) 】【 4 - i l k l ( ( 矿) 2 p ) 】，k 4 h 3 ( z 3 k 一5 ，z 3 k 一4 ，z 3 k + 6 ) = s2 【z 4 i 4 + t lt 2 其中 s ( z l ，z 3 k + 6 ) = 毒 一5 + z 3 k l z 3 k + z 3 k + l z 3 k + 2 + z 3 k + 3 z 弘“- i - z 3 k + 5 z 戤+ 6 ， * s t y ，、， l 【z l ，z 3 量+ 6 ) = z ； 一3 + z 3 k i z 3 k + z 3 k + i z 3 k + 2 + z 3 k + 3 2 3 七+ 4 + z 3 k + 5 2 3 k + 6 ， ，丌。、， 12 ( z b ，z 敏+ 6 _ ) 2z ；i 一2 + z 3 k 一! z 3 k + z 3 k + l z 3 k + 2 + z 弘+ 3 z 强+ 4 + z 弧+ 5 z 弧+ 6 t h e o r e m 1 1 ，刀对任意舷3 ，q 2 t ( z l ，一，锄+ 6 ) 是毛在 u = f q j ，小，q k + l ，q 3 k + 6 l = q l ，鲰，( 玖( t k + i ，f 3 + 4 ) l 上的极小生成多项式其中 1 0 q 2 , ( z l ，z 2 ，奴+ 6 ) = z ； + 之+ + 孝+ = 右+ z 2 + + 彳+ 2 1 n ) 风亿+ l ，及+ 2 ，z t + 3 ，z 3 t + 5 ，z 雏“) 乏留+ 看器+ l + s 2 【磊- 4 + t i t 2 1 看薯+ + s 2 【兹4 + t i t 2 1 j 1 乏簋+ i 乏嚣+ i + s 2 t z 4 , 4 + t i 2 1 1 i z i 箸+ l + s 2 【破一4 + t j 7 2 1 j j 缈= 黾+ 。，f = l ，2 ，七一l ， 吼= h + h 1 2 1 b ) g k ( t t + 1 ，。t 3 k + 4 ) 由下面所定义的递归函数给出：令s = t s h s 2 ，) 是一 个有限足够长的或者无限长的正整数序列，对于j23 递归定义关 于x ”x 呦x 1 1 x 垃。的二次多项式序列 g 3 ( s ) = ( 矗+ 如h ，五+ 如h ，+ 如h ，毛+ 如，+ h 五。，+ 工曲墨；妒 x s s x 码，x s s x s i o ，x s 6 x s l ，x s 一砘，x 1 1 x s 9 ，x s x s m ) g j ( r l ，r 2 ，s ) = ( 蠢+ 五。h ，+ 而。如，啄l ( s ) ) ，j 4 也即当k 4 时 g k ( t k + l ，t 3 k + 4 ) = ( + l + h + 3 h “，+ 2 + 3 黾， g t l ( 1 k + 3 ，f 3 矗+ 4 ) ) = ( + + + ，+ ：+ + ，黾“，+ ，+ h + ，h + 6 + 。+ 黾+ ，黾+ 6 g t 一2 ( t k + 5 ，弘+ 4 ) ) = ( + 。+ h + ，黾“，+ ：+ + ，彬+ ，+ h + ，h + h + ，h 彬 ”+ + ，h + ，拍+ 黾钉h + 。， g k 一3 ( t k + 7 ，“) ) = ( + + h + ，。，+ ：+ + ，+ ，+ ，+ + ，h 舻+ + + ，h + 6 ， + ，+ ，h + ，硒+ 黾，h + 。，乇q + 一，一，乇一。+ 一，砘。 g 3 ( 如i s ，f 珏+ 4 ) ) 1 1 g 3 ( - 5 ，+ 4 ) = 叱+ k l ，屯+ k ，工如，屯+ k ， 屯+ 一，七。+ + 以，毛+ + ，+ ， 再址l x r s t + 3 , 而珏- + ，x t 3 k x t 鼙+ ! 幢，砘+ ，3 ，+ 2 ) 例1 1 当七= 3 肘，q s ( z l ，z l s ) = 者+ 之+ 毒+ 飓亿，z 1 5 ) = 右+ 弓+ z 8 + ( 雹+ 毒毒+ 右o z 詈l + 看2 看3 + 右4 看5 ) 【霉+ ( 露+ z s z 9 + z l o z l l i z | 2 2 1 3d z 1 4 z i $ ) ( 弓+ z 8 2 9 + z l o z l l + z 1 2 z d + z 1 4 2 1 5 ) 】l 是焉在 + 畦， + ， 毫+ h ， ， 吒+ 而i o x t n ， 上的极小多项式。 当k = 4 时， 勃+ ，+ h ，g 3 ( t 4 ，1 1 3 ) 1 = + ， + ， + h ，+ h ，+ ， 一 吒+ 而1 2 西舻 五9 j r f l o ，j r 9 而i 五l 而1 2 ， 五i o 而1 2 ， 而1 3 ， 而”再l q 1 6 ( z l ，z 1 8 ) = 右+ z 4 + z ；+ 孝+ h 4 ( z 5 ，z n ) = z ；+ z 4 + z ；+ 撑+ 【z ；+ h 3 ( z 7 ，z 1 8 ) 】【z 芸+ h 3 ( z 7 ，z l s ) = z ；+ 之+ 毒+ z ：6 + i 霉+ ( z 4 + 彳l z 2 2 + 右3 右4 + 右5 右6 + 右7 者8 ) 【z ：+ ( 弓+ z l l z l 2 + z 1 3 2 1 4 + z 5 2 1 6 + z 1 7 z s ) ( 南+ z l l z l 2 + z 1 3 2 1 4 + z j 5 z j 6 + z i t z l 8 ) 毒+ l ( z 4 + 彳。之+ 元元) + 袁袁+ z ；7 者。) 【z 4 + ( 弓+ z l j z l 2 + z 1 3 2 1 4 + z 5 2 1 6 + z j t z j s ) ( 南+ z l l z l 2 + z 1 3 2 1 4 + z 1 5 2 1 6 + z 1 7 2 1 8 ) 】 】 是在 h + 砭，勘+ 砖，h + 砖， 黾+ ， g 4 ( t 5 ，t 1 6 ) = l 五，+ 磋，勘+ ，+ i ， h + ，+ h 五。， + ， + 黾。而。2 ，+ x ，g x t l o 砖+ h 。而1 2 。+ 而五1 2 。+ 而1 3 而乇2 + 再。5 而1 6 而而i ，而五1 6 ，再，2 而1 3 而1 2 而而1 3 玉l ， 而1 4 五蜘 】 上的极小多项式o 1 2 2 主要结果 2 1 一种改进的m f e 体制 前面我们已经介绍过m f e 体制，然而遗憾的是它被d i n g 等用s o l e s 的方法攻破 了【2 】。下面我们简单介绍一下【2 】中提到的攻击方法。令 m 也捌 k 1 k 弱j 坞= 降 l x i ! 暖y ， 5 1 = m t 尬【竞，y 9 = m i 尬【b 9 1 4 2y 1 3 y , s 1 j = 孵慨 z 3 = m i m 2z 2 = m i m 3 = m 乏m 3 m 是二阶矩阵的伴随矩阵。从( 1 ) 中我们可以得到矩阵方程 由这个方程可以得到4 个方程： m 3 z ；z 3 = d e t ( z 2 ) m 2 曷( y 4y l l y 6 y 9 ) + x j o ( - 场y i o + 虼y 8 ) 一玛( y 8 h i y 9y l o ) = o ； ( 1 ) 曷( y 5y l l y 7 b ) + 州一蚝y l 。+ 均y 8 ) 一托( y 8 h l by l 。) = o ( 2 ) x l i ( 1 4y l l y 6 蜘) + x i 2 ( - y 4 y j o + y 6 y 8 ) 一局( y 8 h l y 9 h o ) = o ； x l l ( y 5y l l y 7 y 9 ) + x i 2 ( - 蚝y l o + y 7 y 8 ) 一x s ( y sy l l y 9 h o ) = o ； 将( 筠，x 1 2 ) = 丌1o s ( u l ，m 2 r ) 署o ( y i ，1 5 5 ) = 砭ot ( v l ，v 1 5 ，) 代入( 2 ) 可以 得至l j 4 r + s o l e s ： 以a i j t v j v t + i 矗 b o v ，+ c d + 靠印玖+ 压t e j v j 七 = 0 其* a f j k ，b q ，c i ，靠，e j ，f el f 1 2 r , l jsk 1 5 r 。【2 】中证明由( 1 ) 可以得 到2 4 r 个线性无关的s o l e s 。在唯密文攻击中，将有效密文( 嵋，嵋5 ，) 代入到这2 4 价 线性无关的s o l e s ，可以得到8 厂个关于1 i ，l f 1 2 r 线性无关的方程，此外作者 又发现霹+ 蟹l 和x 南+ 稚可以表示为b ，1 fs1 5 的线性组合，从而总共得到 了1 0 价关于u f ，l is1 2 r 线性无关的方程。然后由高斯消元法可以用s2 价 o 2噩噩 变量不妨设为呐，w t 把其余的变量表示出来，然后把它们代入公钥中，可以得 到j ；l l ，坼) ，j ；1 2 l ，嵋) 最后用甩【1 4 】或者g 飚锄p 厂方法【2 3 】解 即可。 h i ( w 1 ，w 1 ) = ，1 i 1 2 2 1 1 改进的m f e 公钥加密方案 s ，l 7 1 l 7 1 2 与1 3 6 节中的相同，现在定义一个新的函数 九( y l ，y 1 5 ) = ( 鹏，w j 5 ) 其中h ，y 1 5 l ，m ，m 5 l ，川，m 5 可表示为： m = y l + c l y 4 y i i y i 2 - y 弋4 y l o 可y i 3 忑- y 面6 y 9 y 1 2 - i - 一y 6 y s y i 3 = x i + x s x s + x 6 x 7 + q l + c l ( 霹+ 霹) ； w r 2 = y 2 4 - c 2 蚝y l iy 1 2 一y 5 y j oy 1 3 一y 7 y 9y 1 2 + 均蚝y 1 3 蚝y l l b h o = y 3 + g 些k 等等瓮地 = x 3 - 4 - 为甄- 4 - x 2 x 3 - 4 - q 3 + c 3 ( 墨拖- 4 - x t x 8 ) ； 肌= k + a 些坠等等瓮她 = x , x 5 + 憋曷+ c 4 ( 碡+ 霹) ； w 毛= y 5 = 蜀+ 而：w r = y = 熟旅+ 乜泓： w 7 = y 7 = x 3 x 6 + 酗；w ，8 = y 8 = x l x 9 - i - x 2 x h ； w 9 = y 9 = x j x m + x 2 x n ；m o = b o = 为x 9 4 - x 4 x i l ； w l l = y l l = x 3 x l o + x 4 x 1 2 ；m 2 = h 2 = x 5 x 9 + 局置l ，o w j 3 = y 1 3 = 恐x m + x t x l 2 ；m 4 = y 1 4 = 施牺+ 施x l l ； m 5 = y 1 5 = x j o + x s x s 2 ； 1 4 其中g ，扛l ，2 ，3 ，4 表示，上的r r 常数矩阵。 改进后的m f e 的公钥为： q ；( h i ，h 1 2 ，) ， ；5 ( “l ，h 1 2 r ) ) = t o 砣。如。妒lo 死i 1o s ( u l ，h 1 2 ， 私钥为s ，t , 刀r l ，万2 ，九，锄。 改进后的m f e 的加密：给定一个明文( 砌，l l l 曲，其对应的密文就是 ( v l 一，v 1 5 ，) = 喊( m l ，m 1 2 ，) ，嵋5 r ( u l ，h 1 2 ，) ) 改进后的m f e 的解密：给定一个有效密文( ，l 一，v 1 5 r ) ，其对应明文就是 s 一1o 丌lo 町1o 荔1o 丐1o 丁一1 ( y l ，v 1 5 r ) 其中关于s ，l 妒- ，丌l ，丌2 的求逆前面已经介绍过了，下面看晚的求逆。首先依次求出 然后再求 即可。 注2 1 y ：f = m ，f = 1 5 ，5 y l = m c i 堕堕! 垡兰= 堕些旦堕 坠堕堕兰坠坠当! y2=wr2一c2w5wl lw12-w5wiowl3-wtw9w12jrw 7 w 8 w i 3 圪：w 3 一c 3 w 4 w ll w 1 4 - w 4 y | o w 1 5 - w 6 w 9 w 1 4 j r w 6 w s w l 5 y 4 = w 4 一c 4 w s w i l w 1 4 - w 5 1 w i 而o w i 5 习- w 磊t w 9 w 1 4 - i - 一w t w s w l 5 j 7 晚中出现了分母，所以必须保证分母不为零，即托y i l y 9 h o 0 。因此 改进f i f j m f e 密码体制的密文空间为 ( “l ，u 1 2 r ) f 1 2 7 ：y 8y l l y 9 y i o 0 l 对任意的( h l 一，h 1 2 ，) f 协如果它对应的肘。和鸭全部可逆，则此时显然 有y 8y i l y 9y i o 0 ，所以改进f f j m f e 麓够对其进行加密，而，2 j 中已经证明 当驰= 2 1 6 r = 4 时，任意颇比l ，i 曲k 1 打所对应的m l ，和坞不全可逆 所占的比例至多；为2 - 6 2 ，因此任意的哂一u i 稿k 协所对应的m i 和m 3 不全可 逆所占的比例更低，所以此时改进后的m f e 对中f 协几乎所有的元素都能进行 加密 2 从上一页的构造中我们还可以看出帆。巾i 关于x j 仍是二次，所以改进后的m f e 仍 是m q - 体制。 2 1 2 关于改进的m f e 体制