（计算机软件与理论专业论文）基于l系统的公钥密码体制密钥特性分析及其应用.pdf

论文题目：基于l 系统的公钥密码体制密钥特性分析及其应用 专业：计算机软件与理论 硕士生：陈颖瑜 指导教师：龙冬阳教授 摘要 本文主要研究了基于l 系统的公钥密码体制的重要特性在电子拍卖方面的 应用。基于l 系统的公钥密码体制通常又称作基于同态的迭代的公钥密码密码体 制，是由s a l o m , a a 等人在1 9 8 6 年提出的基于l i n d e r m a y e r 系统正规语言文法的 公钥密码体制。l 系统公钥密码体制的特点在于其陷门函数设计突破了初等数论 的难解问题，转移到形式语言理论的词析问题。 在文章中我们首先系统地介绍了同态迭代的概念和l 系统公钥密码体制理 论，以及近年来的发展现状。然后，文章围绕三个重点展开研究： 第一，分析了l 系统公钥密码体制的算法复杂性，指出该体制的复杂性是指 数级的。基于这一结论，文章提出了一个改进的密码体制：l 系统m 公钥密码体 制。改进体制丰要利用了密钥中生成规则表的扩展，使该体制加密解密过程每步 能处理的字节数增加。改进体制与分组明文技术结合使用，能降低加密和解密的 复杂度，有效避免发生密文长度指数爆炸的情况。 第二，指出l 系统公钥密码体制密钥对的4 个重要特性，“多翻译同态对应 多公钥”“单一私钥对应多公钥”“链式同态”，“树形密钥结构”。其中 “利用单个私钥与单个同态生成多个公钥”的特点是l 系统区别于现有密码体制 的特点，“树型密钥结构”则是基于l 系统公钥密码体制的电子拍卖协议的理论 基础。 第三以上面两个重点的研究为基础，本文利用“树型密钥结构”的特性， 设计了一个基于l 系统公钥密码体制的电子拍卖协议并进一步提出基于l 系统 l l r 公钥密码体制的改进建议。其后，文章讨论了该协议的安全性与性能。 最后，文章总结l 系统理论应用于公钥密码框架的进一步研究工作的方向。 【关键字】同态的迭代；l 系统公钥密码体制；l 系统m - 公钥密码体制； 密钥特性；电子拍卖 t i t l e：t h ek e y sc h a r a c t e r i s t i c sa n d a p p l i c a t i o no f p u b l i c k e yc r y p t o s y s t e m b a s e do nl s y s t e m s m a j o r：c o m p m e r s o f t w a r ea n dt h e o r y n a m e ：c h e ny i n g y u p r o f e s s o r ：p r o f l o n gd o n g y a n g a b s t r a c t i nt h i st h e s i s ，w eh a v es o m es u c c e s s f u ld i s c u s s i o n sa n dt r i a l so np u b l i c - k e y c r y p t o s y s t e mb a s e do nls y s t e m sr e s e a r c h s y s t e m s i ss h o r tf o rl i n d e n m a y e r s y s t e m ，w h i c hi sap u b l i c k e yc r y p t o s y s t e mb a s e d o nl i n d e n m a y e ra u t o m a t aa n d f o r m a ll a n g u a g et h e o r y h o m o m o r p h i s mi t e r a t e d ，w h i c hi sav e r yi m p o r t a n tc o n c e p t i nl i n d e n n m y e rt h e o r y , i saf o u n d a t i o ni np u b l i c - k e yc r y p t o s y s t e mb a s e do nl s y s t e m s t h ef i r s tp a r to f t h et h e s i sg i v e sas u m m a r yo f t h eb a c k g r o u n dm a t e r i a lo f l i n d e n m a y e rt h e o r y t h e nt h et h e s i sf u l f i l l st h r e ea s p e c t s o fs t u d i e s f i r s t l y , t h e t h e s i sc o n s i d e r sa p p r o x i m a t et i m ea n ds p a c ec o m p l e x i t yo f ls y s t e m s ，a n dt h e ni t g i v e sa ni m p r o v e m e n tn a m e dm - p u b l i c - k e yc r y p t o s y s t e m b a s e do nl s y s t e m s s e c o n d l y , t h et h e s i sf o c u s e so nt h ek e y sc h a r a c t e r i s t i cd i s c u s s i o n i nt h i ss e c t i o n , 4 k e y sc h a r a c t e r i s t i c sa r ei n t r o d u c e d t h ed i s c u s s i o no f t h ck e y sc h a r a c t e r i s t i c s w i t h i n ls y s t e m ss c h e m e sb u i l d su pt h ef o u n d a t i o no f ae - a u c t i o np r o t o c o lb a s eo nl s y s t e m s t h i r d l y , ap u b l i c k e y e a u c t i o np r o t o c o lb a s e d0 nls y s t e m si si n t r o d u c e d ， a sw e l la ss o m ed i s c u s s i o n sf o rs e c u r i t y t h el a s tp a r to f t h et h e s i sg i v e sab r i e f s u r v e yo f t h em o s ti m p o r t a n ta r e a sw i t h i nl s y s t e m s ，a n dd e a l sw i t hs e v e r a li m p o r t a n tf u r t h e rw o r k so f t h els y s t e m ss t u d i e s k e y w o r d s h o m o m o r p h i s mi t e r a t e d ；p u b l i c - k e yc r y p t o s y s t e mb a s e do nls y s t e m s m p u b l i c k e yc r y p t o s y s t e mb a s e do nls y s t e m s ；k e y sc h a r a c t e r i s t i c s e a u c t i o n 1 1 基王坠丕筮笪垒翅蜜亟签趔童翅挂丝坌赶区基廛旦 第1 章引言 基于l 系统的公钥密码体制( 通常又称作基于同态的迭代的公钥密码体制) 是由s a l o m a a 等人在1 9 8 6 年提出的，其理论基础为l i n d e r m a y e r 系统正规语 言文法。1 9 6 8 年，美国的生物学家a r i s t i dl i n d e r m a y e r ( 1 9 2 5 1 9 8 9 ) 提出了 l i n d e r m a y e r 系统，简称l 系统，以它作为数学理论框架，研究植物的进化和造 型嘲。 其后不久，s m i t h 、a n o n o 和k u n i i 率先将l 一系统引入到计算机图形学中哪。 由l 一系统与分形理论的结合在计算机模拟植物方面的表现出极大的潜力，为计 算机模拟植物的真实感图形提供了有力的工具。 s a l o m a a 等人对l 系统公钥密码体制的研究跳出了原有密码体制的局限，使 密码体制的陷门函数设计从初等数论里面的难解问题，转移到l 系统中的形式语 言理论问题：词析问题。从理论上s a l o m a a 等人已证明了l 系统公钥密码体制是 安全可行的“5 。”。 1 1 本文主要工作 本文在现有关于l 系统理论文献的基础上，系统的介绍了同态迭代的概念以 及l 系统公钥密码体制理论。根据已有理论，本文着重从以下三方面进行研究： ( 1 ) 分析了l 系统公钥密码体制的算法复杂性，对该密码体制的加密以及解 密阶段进行了时间与空间复杂性证明。根据分析所得结果，总结说明l 系统体 制的优点与不足。 ( 2 ) 研究了l 系统公钥密码体制密钥对的特性，总结出l 系统密钥四个重要 特性，这些特性在l 系统密钥生成和使用中有非常突出的体现。其中“利用单 个私钥与单个同态生成多个公钥”的特点在其他基于初等数论里面的难解问题的 公钥密码系统中暂时未能实现，本文针对l 系统这个特别的性质做出了理论证 明，并结合l 系统另一特性链式同态，总结出l 系统的树型密钥特性。该特 基王! = 丕筮数垒塑查塑住剑查塑缱丝岔蚯区基廛旦 性是本文第6 章工作基于l 系统公钥密码体制的电子拍卖协议的理论 基础。 ( 3 ) 在对密钥特性进行分析的同时，本文也指出l 系统公钥密码体制以字符 串替换为基础，是限制该体制实际应用的障碍，也是该体制提出之后一直未有基 于l 系统体制的协议产生，也没有人对该体制进行进一步研究的原因。在此基 础上，论文将根据l 系统公钥密码体制的自身优点以及密钥特性，提出l 系统 公钥密码体制的一个可应用方向，设计出一个基于该体制的电子拍卖协议，并证 明了该协议的安全性。 1 2 内容安排和主要成果 文章在引言部分简要介绍基于l 系统的公钥密码体制的理论背景，产生和发 展历史，并且讲述本文的主要工作和贡献。本节主要介绍本文的接下来的章节结 构和内容安排。 第2 章l 系统理论研究意义及现状介绍了l 系统理论在密码学方向的应用原 理，l 系统公钥密码体制的研究意义，发展及其应用现状，和l 系统密钥表 示方面的研究工作。 第3 章基于l 系统公钥密码体制概念与性质本章是全文的理论基础，着重在l 系统公钥密码体制理论的介绍。其中包括两个特殊的l 系统d o l ， d t o i ，适用于构建公钥密码体制的l 系统。其中同态迭代的概念，向 后确定性以及强向后确定性，陷门函数与翻译同态的介绍是l 系统应用在 公钥密码体制上的重要理论基础。 第4 章l 系统公钥密码体制的算法复杂性l 系统公钥密码体制的算法复杂性 的分析与证明，近似推导出加密以及解密阶段的时间复杂性及空自j 复杂性 的数量级。根据复杂性的结论提出了一个改进的密码体制l 系统m 公钥密码体制。 第5 章l 系统公钥密码体制密钥特性分析介绍l 系统密钥生成和使用过程， 研究了l 系统公钥密码体制密钥对的特性，总结出l 系统密钥四个重要特 性：“多翻译同态对应多公钥”“单一私钥对应多公钥”，“链式同态” ，“树形密钥结构”。进一步地，文章针对l 系统“单一私钥对应多公钥” 2 墨王! = 丕筮鲤公翅查塑笠剑窒塑挂丝佥扭区基廑厦 的特点作出了理论证明，并结合“链式同态”特性，总结出l 系统的“树 形密钥结构”特性。最后，文章还指出了l 系统的一个密钥弱点。 第6 章一个电子拍卖协议的设计：l 系统公钥密码体制的应用在这一部分， 文章设计出一个基于l 系统公钥密码体制的电子拍卖协议，这个协议结合 了l 系统的优点和l 系统公钥密码体制的“树型密钥结构”特性，是对l 系 统公钥密码体制实际应用的第一次研究。本章其余部分介绍了电子拍卖已 有的研究成果，并讨论了文章所提出协议的安全性。 第7 章结语总结了本文的研究成果；归结了l 系统公钥密码理论的4 个研究难 点，指出l 系统距离实际应用存在的障碍。 第2 章l 系统理论研究意义及现状 2 1l 系统公钥密码体制原理 l 系统公钥密码体制的内在问题为l 系统中的生成规则，形式上为一系列 可视作字符串替换的同态映射，属于形式语言理论。该体制把l 系统中的生成规 则设置为密钥，利用两个不同的同态( 分别记为和如) 记录明文比特串，实现明 文到字符集合的映射，加密过程为通过对初始状态进行和 的迭代，产生相应 的字符串。陷门的构造通过翻译同态实现，合法的接收者利用陷门对密文进行翻 译，解密时只要在d t o l 系统中作简单的词析；而密码分析者则必须在规模巨大 的t o l 系统中进行词析。 2 2l 系统公钥密码体制的研究意义 l 系统公钥密码体制的研究弥补了公钥密码体制框架研究的空白，使用l 系 统理论作公钥密码体制框架的基础，具有以下的一些优点“1 ： 突破性的理论基础加密过程只需要应用迭代替换规则，对编码字母用码字 替换，突破了传统基于初等数论中困难问题的公钥密码体制框架，其陷门函 数的设计转移为l 系统中的词析问题。 安全性能高因为在公开密钥中找寻傀儡字母是n p 完全问题，所以密码分析 的预处理不可能成功，在把翻译同态推广为满射了之后，即使找到傀儡字母， 密码分析也不能成功。 实现效率较高由于加密过程只需要应用迭代替换规则，对编码字母用码字 替换。同态映射和有限替换在程序中的表示较为简便和易于理解，对于一段 短小明文用程序实现的效率就更高。 4 2 2l 系统公钥密码体制研究现状 l 系统理论应用于公钥密码体制的研究，突破了传统的r s a 公钥密码体制和 基于离散对数的公钥密码体制的框架，也使得自身应用局限于密码学的非主流理 论上。目前出现的且具有较高的安全性的公钥密码体制主要基于以下困难问题 1 ) 基于数论中的大整数分解问题( 诸如r s a ) ； 2 ) 基于离散对数问题( 如e 1 g m a l 、d i i t i e h e l l m a n 密钥交换协议) ； 3 ) 基于椭圆曲线上的离散对数问题( 如e c c ) ； 4 ) 基于线性编码的解码问题( 如m e e l i c e 密码体制) ； 5 ) 基于自动机与语言理论( 如我国学者陶仁骥等提出的基于有限自动机的 公钥密码体制和基于l 系统的公钥密码系统) 。 一方面，由于l 系统基于的形式语言理论问题，和其他基于数论困难问题的 密码体制有本质上的区别；另一方面l 系统理论自身存在很多未解决的问题，这 些问题阻碍了l 系统公钥密码体制的研究，到目前为止对于该种体制的应用及研 究发展相当缓慢，还没有人用高级语言对其做过实现。为使l 系统公钥密码体制 投入实际应用，一些问题急需得到解决： 密钥表示形式问题：现有的密钥形式使得存储十分麻烦，修改密钥付出的代 价相当大。 密文增长率非线性问题：密文长度可能会出现指数爆炸的现象。l 系统可以 加密的长度不大，不适合需要对长明文进行加密的场合。 密钥的批量生成方法：需要找到一个批量的密钥生成方法，使计算机能用程 序自动生成多个公私钥对，并且能适用程序判断生成密钥是否合法。 向后确定性的判定问题：密钥向后确定性的判定的仅停留在理论定义阶段， 尚未有具体的密钥同态生成规则和向后确定性的判定规则。 2 0 0 5 年，论文基于迭代同念的公钥密码体制的实现用u r m 程序转换为 数字的原理，提出了把l 系统密码体制密钥转换为一个数的思路( 图2 - 1 ) ，将加 密与解密中的替换过程转换成为数字，从理论上降底了密钥存储和变更的难度， 对l 系统公钥密码体制从理论到实际应用起到了积极的推动作用。 图2 i 密钥与数字相互转换原理 在此之后，l 系统公钥密码理论的研究围绕密钥与数之间相互转换的思路， 展开了进一步的工作。原有方案中存在密钥转换过程复杂、生成数非常庞大、u r m 程序实现复杂的弱点，而且当密钥产生变化时，必须更改u r m 程序，以适应 新的密钥，降底了方案现实使用的可能性。针对这些弱点，现有成果中提出了一 种结合中国剩余定理和算数编码的密钥转换方案，简称e a c 方案。 e a c 方案主要实现了l 系统密钥从码字表形式和数字形式之间的正向和逆向 转换( 图2 2 ) 。码字表形式向数字形式转换时，首先对密钥码字表通过算术编码 方法转化成数字化的码字表，第二步应用中国剩余定理，利用一系列质数作中国 剩余定理的模数，将数字化的码字表编码成一个自然数。数字形式向码字表形式 转换时，首先对自然数对原先的质数表作模运算，恢复出数字化的码字表，第二 步对数字化的码字表中每条数字化码字生成规则作算术编码的解码，恢复原来的 码字表，即l 系统的密钥。 图2 - 2e a c 方案原理 以上引述的工作综合了已有文献的成果，这些工作都是关于密钥表示形式问 题方面的，其他3 方面的研究工作暂时没有研究人员开展。 第3 章基于l 系统公钥密码体制概念与性质 3 1 基本概念 设z 是一个非空集合( 有限或无限多个元素) 。称为一个字母表，称中 的一个元素为一个字母。集合 0 ，1 ) 是二进制字母表，对于中的任意两个字母 a 与b ，定义一个字母之间的连结( c o n c a t e n a t i o n ) 运算，记为a b 。称字母表 中若干个字母的连结为一个字。记= t e w 是字母表上的任意一个字) ，表 示z 上所有的字的全体。特别地，将中不含任何字母的字称为z 上的空字，用 彳表示。空在连结运算中空字五是一个单位元，即对于任何一个w z ，有 w 2 = aw = 阢 l 系统主要基于两个重要映：同态及有限替换。 3 1 1 同态及有限替换 同态的定义：设和是两个字符集，表示z 上字的全体，包括空字名。设存 在映射h ：f 专，当且仅当h 满足 h ( x y ) = ( x ) ( 力( 3 1 ) 对所有的词工，y + 均成立时，映射 称为f 专a 上的一个同态。 应该注意，和可能相等，互不相交或者重合。特别地有j 1 2 ( a ) = 丑，因为 h ( 2 x ) = h ( a ) h ( x ) = 矗( x a ) = h c x ) h ( 2 ) 。由同态的定义可推出，一个同态完全由它在 z 上的字母的值所确定。 有限替换的定义：设盯是到的有限子集的集合的映射，当且仅当o r 满足 盯( 习，) = 盯( 工) 盯( y ) ( 3 2 ) 对所有的词x ，y 均成立时，映射o r 称为一个有限替换“1 。 同样的和的关系如同态所要求。跟同态相似，有限替换也具有仃( a ) = m 的性质。一个有限替换也完全由它在上的字母的值所确定。 ， 同态和有限替换的区别在于：同态映射的值为中的一个元素，即一个字。 而有限替换的值为中的一个或多个元素组成的集合，即字的集合。例如，令 = = 0 ，1 ) 且h ( o ) = 0 1 ，h ( 1 ) = 1 ，o ( 0 ) = o ，o l ，o - ( 1 ) = l ，l l 。则 根据同态的定义，有 h ( 0 1 ) = 0 1 1 ，h ( 1 0 ) = 1 0 1 。 根据有限替换的定义，有 a ( 0 1 ) = 0 1 ，0 1 1 ，0 l l1 a ( 1 0 ) = 1 0 ，1 0 l ，1 l o ，11 0 1 为了描述方便，我们把同态和有限替换映射的字符串值统称为替换字符串， 简称替换串。 3 2 同态的迭代与l 系统的分支 l 系统即l i n d e n m a y e r 系统，是瑞典u t r e c h t 大学的理论生物学家、植物学 家a r i s t i dl i n d e n m a y e r ( 1 9 2 5 1 9 8 9 ) 于1 9 6 8 年引入的一个著名正规文法4 1 。 l 系统原本作为各种生物组织的形态学模型，目的是为多细胞组织的生长给 出一个证规描述，并阐明植物相邻细胞之阳j 的关系。后来l 系统的描述范围扩 展到更高等的植物和复杂的分支结构，多用于模拟植物的生长过程【4 】。 3 2 1 l 系统普遍定义 一个l 系统是指一个三元组g = ( y ，m ，p ) ，其中矿是字符集，包含所有可以 用于替换的变量；国是系统的初始状态，是由v 中的字符组成的字符串；p 是一 系列的生成规则，从字符集到其闭包的映射p ：y v ，即如果有盯v ，v + ， 使得p ( a ) = ，则用口寸来表示。用e ( g ) 表示由一个l 系统g 生成的字的序 列 p o ( ) = ，p ( m ) ，p 2 ( 国) ，p 3 ( 珊) ，( 3 3 ) 并且，该l 系统g = ( v ，国，p ) 的生成语言表示为t ( g ) 。 介绍一个简单的l 系统g = y ，p ，其中 y = 口，6 ) ，o j = a b ， p = 1 ) 1 ：口寸口，p 2 ：6 j 口6 通过计算递推出前面几代的字如表3 1 。 表3 - il 系统g 生成字序列 a b g o a a b 蜀 a a a b 9 2 a a a a b 易得上述l 系统的生成序列为e ( g ) = a b ，口2 b ，b ，矿b ，。l 系统的生成语 言为l ( g ) = a b i 疗1 。下文中为了描述方便，用符号一表示生成字的转化 关系，即用工一y 表示h ( x ) = y 。特别地，如果字工可通过n 步同态迭代转化 为字y ，则用符号x 三哼j ，表示。习惯上的表示还有工三一y 用于表示字x 通过 l 步或多步生成字y ，以及j 二号j ，用于表示字工通过0 步或多步生成字y 。 3 2 2 l 系统的分支 9 定义了一个l 系统以后，我们可以通过赋予生成规则p 不同的特性，划分出 一些l 系统的分支： 如果p 的所有元素都是单射，即任何一个字符只能生成唯一的一个字词，则 称其为确定的l 系统； 如果存在p f p 是一对多的映射，即存在某个字符可以生成两个以上的词， 则称其为随机( s t o c h a s t i c ) 的l 系统。 借助同态和有限替换的概念，可以构造出一些具有某种特性的l 系统。 3 2 2 1d o l 系统 考虑把l 系统应用于字符集合，利用同态h 作为l 系统的生成规则p ，即， 令p = h ，定义一个新的l 系统为三元组g 。= ( ，h ，0 2 ) ，其中是一个字符集，h 是 z 专z 的自同态，初始状态是一个字符串，称为d o l 系统。g 。生成的 词序列和g d 。生成的语言分别为： e ( q 。) = 矿( ) = ，厅( m ) ，h 2 ( m ) h 3 ( ) ， ( 3 4 ) l ( g 。) = p ( e a ) l i - o ( 3 5 ) d o l 系统是一个确定的l 系统，因为d o l 系统的每次应用的同态都是唯一 相同的，所以其生成语言e ( g 。) 是确定的。因此d o l 系统又称为“单同念迭代 ( s i n g l eh o m o m o r p h y s m si t e r a t e d ) ”【钔。其中缩写d o l 中的0 表示系统中的字 符串替换是上下文无关的，d 代表确定的( d e t e r m i n i s t i 0 ，即对每个字母只应 用唯一的替换，得到的新字也是唯一确定的。 3 2 2 2d t o l 系统 0 修改d o l 系统的同态生成规则h ，把单一同态h 替换为一个有限的同态集合 日= 魄，吃，噍 每步推导时应用的生成规则是同态集合日中随机选取的一个 元素吩。定义一个新系统形式为一个新三元组g = ( z ，日，) ，其中日是一个有限 非空的同态集合，且对于所有的h 日，( ，h ，珊) 是一个d o l 系统，称为d t o l 系统。它所描述的语言为： 三( g ) = 工l 工= 珊，茑h = ( m ) ，其中啊，日 ( 3 - 6 ) d t o l 系统是一个随机的l 系统，因为d t o l 系统的生成词序列是不确定的， 取决于每次选取的同态的顺序。d t o l 系统又称为“多同态的迭代( s e v e r a l h o m o m o r p h i s m si t e r a t e d ) ”1 4 。由定义可见，d o l 系统是d t o l 系统当同态集合日 只有h 一个元素下的特例。 3 2 2 30 l 系统与t o l 系统 以上我们利用同态的概念构造了两个系统确定的l 系统d o l 和随机的l 系统d t o l ，接下来，利用有限替换概念，用同样的方法构造两个新系统： 一个0 l 系统是一个三元组g o = ( z ，h ，) ，其中是一个字符集合，h ：z 是有限替换，是初始状态。 一个t o l 系统是一个三元组g 。= ( ，c o ) ，其中日是关于有限替换的一 个有限非空集合，且对于任意h h ，( ， ，) 组成一个o l 系统。 前文中对d o l 系统和d t o l 系统的分析方法对于0 l 系统及t o l 系统也适 用。把d o l 系统和d t o l 系统中的同态概念换成有限替换概念，对前两个系统 所做的结论现在也成立。 3 2 2 4d o l d t o l o l t o l 系统比较 比较四个系统的异同，t o l 系统的推导和o l 系统的推导区别在于，应用t o l 系统生成规则进行每一步推导t - - + ，时，首先我们在有限替换集合日中选取一 个有限替换的映射h ，由于h 中每个字母映射到的是一个替换串集合，因此第二 步还要从表h 中选取每一个字母对应的替换串，才能最终计算推导所得的字葺 而在o l 系统推导中只需进行第二步的处理。d o l 系统和d t o l 系统的区别与上 述的区别是相类似的。 t o l 系统的推导和d t o l 系统的推导区别在于，在d t o l 系统中应用同态生 成规则进行每一步推导- - - + 时，在同态集合h 中一旦选取了一个同念的表 h ，推导得到的字_ + 。已经由原字一和同态h 唯一地确定了，这是因为同态矗中每 个字母映射到的是唯一的一个替换串，因此对原字蔓中每一个字母替换一个唯一 的替换串后生成的新字+ ，也是唯一的。而在t o l 系统中，有限替换h 中每个字 母映射到的是一个替换串集合，推导所得的字+ 是不确定的。同理，0 l 系统和 d o l 系统也存在上述类似的区别。 另外，四个系统有一些共同的性质：令四元组g = ( ，日，甜) 为一个 d o l f d t o l o l f r o l 系统，则g 具有以下性质： 1 ) 对于任意非负整数r l 以及任意字五，x 2 ，y l ，儿，z + ，如果五山m 且 恐山儿，则有五屯山乃肋。相反地，如果x e x 2 与z ，则存在词 z i ，z 2 ，使得z = 毛之，而三斗毛且而旦专z 2 。 2 ) 对于任意非负整数n 和m ，以及任意字x ，y ，z ，如果x 与y 且j ，山z ， 则有x 里旦斗z 。 3 3 基于l 系统的公钥密码体制 计算机的编码本质上是对二进制的o 1 比特串进行处理的。考虑一个特殊的 d t o l 系统，系统中的同态生成规则集合日包含两个元素，分别记为和 ，把 比特串中o 1 比特与同态生成规则和啊对应起来，我们就可以利用同态和 的迭代，作用在初始状态上，实现一个比特串到字符集合的映射。这个过程充分 地显示了利用l 系统理论实现函数性的公钥密码体制的可能性。要设计基于l 系统公钥密码体制，需要考虑以下几个问题： 设置适当的同态生成规则和初始状态作私钥。 设置适当的同态生成规则和初始状态作私钥。 设计陷门函数 3 3 1l 系统公钥密码体制的设计 3 3 1 1l 系统公钥密码体制的定义 要构造一个完善的密码体制，首先要保证加密和解密的正确性，其次要保 证密码体制的安全性，第三应该保证合法解密者词析工作的简单性。l 系统公钥 密码体制在已有的参考文献【4 】有较详细的介绍，其基本定义为： 基于l 系统的公钥密码体制是一个五元组( p ，c ，k ，e ，d ) ，其中， p = l = o 或l ，t = l ，n 表示明文的集合；c f 是密文的集合； k - - ( h ，g ，g ) ，其中四元组日= ( a ，o o ，矾，甜) 是公开加密密钥，四元组 g = ( ，岛，缈) 和翻译同态g 是解密密钥；e k ( i l ) = 巳巳 ) 是加密函数， 其中= o 或l ，t = l ，打；巩( g ( y ) ) = 是解密函数，其中y = ( ) ， 国= 纠h 。- ( g ( y ) ) 。 分别满足以下条件： 选择使得| | i f 公开加密密钥日= ( ，吼，“) 满足c r o ，q 是有限替换，四元组具有向 后确定性。 解密密钥g = ( z ，魄，c o ) 满足， 是同态，四元组g 具有强向后确定性。 解密密钥中的翻译同态g 满足g ：寸是满同态。必然存在1 1 a 使得 g ( “) = c o ，而且对于d a ，定义有限替换q ( d ) = x i g ( 工) = 啊( g ( d ) ) ， 其中f = o 1 。 显然g 是一个d t o l 系统，而h 则是一个t o l 系统。这样，在基于l 系统的 公钥密码体制中，合法的接收者知道陷门，解密时只要在d t o l 系统中作简单的 词析；而密码分析者则必须在规模巨大的t o l 系统中进行词析。 3 3 1 2l 系统公钥密码体制的加密和解密 由l 系统公钥密码体制的定义，有该体制的应用分为两个步骤： a 加密步骤：应用加密函数气( ) = 吒q ，( ) ，其中= o 或l ，t = 1 ，疗； 输出密文y = e k ( i l ) ； b 解密步骤：应用解密函数以( g ( y ) ) = ，其中j ，= 吼( ) ， 印= 町h 。- 1 ( g ( y ) ) 不妨称中间结果g ( y ) 为中间密文或半密文。解密函数的实 现一般由解密密钥的性质决定，在3 3 2 节中将有详细说明。 为了便于理解，我们借助一个简单的例子说明应用l 系统公钥密码体制整 个加密和解密的过程如下： 例3 3 1 2 a 在一个基于l 系统的密码体制中段置 1 ) 公开密钥为四元组h = ( ，q ，c r 2 ，“) ，其中 a = q ，c 2 ，c 3 ，c 4 ，6 ，“= c 5 c 4 c 2 ， 有限替换c r 0 和c r 定义如下： 4 乞 巳，白c 2 6 6 c 2 ，c 3 岛q q q ，q q 岛 吒巳，q q c 5 c 3 c 3 ，c 4 c l c 5 c 4 一，c i c l c 5 c 5 c 2 ，白q 岛，c 5 c 2 c 4岛- 4 6 ，c 5 c 4 2 ) 合法的接收者拥有解密密钥四元组g = ( ，h o ，啊，国) 和翻译同态g ，其中， 翻译同态定义为g ( q ) = g ( c 4 ) = 五，g ( c 2 ) = 6 ，g ( c 3 ) = g ( c o = 口 = 口，6 ，( 口) = a b ，h o ( b ) = 6 ， ( 口) = 口，啊( 6 ) = b a 国= g ( u ) = g ( c 5 c 4 c 2 ) = a b 。 l 系统加密过程：下面用这个公钥对比特串0 1 1 0 进行加密，即计算 c r o a j a , c r o ( u ) 。 u = c 5 c 4 c 2 q 岛龟q c 2 三巳c 4 c 2 岛q c 2 q _ ! l c 3 q q c 2 白岛c 4 巳巳白- ! l 岛f 2 qc l c 2 岛c 2 巳乞q q c 2 q c 2 g 吒= y l 系统解密过程：合法接收者在接收到密文y 之后，可以借助翻译同态计算 半密文g ( y ) = a b b a b a b b a b a b ，于是可以进行解密计算如下： g ( y ) = a b b a b a b b a b a b , = 。a b a a b a a = 啊( 生g 丝) = 啊( g 丝) 以h 结尾，用h 。解密以a 结尾，用h i 解密以“结蟮，蹦h l 解密 以b 结尾用h o 解密 = ( 口6 ) = 啊( 口) 最终得到明文0 1 1 0 。 l 系统公钥密码体制的数据转换关系如图3 - 1 。 图3 1l 系统公钥密码体制数据转换关系 3 3 2 同态生成规则和初始状态 3 3 2 1 向后确定性 向后确定性定义：设同态， ：_ ，称四元组g = ( ， ，c o ) 是向后确定的， 当且仅当条件 ( 珊) ；勺。q ( 脚) 成立时，总能推出条件 i l i o = j j n 其中国，z o ，1 。 向后确定性意味着，在初始状态上在逐一地把一串同态进行迭代时，两个不 同的迭代序列不可能得出相同的结果。因此具有向后确定性的四元组 g = ( z ，啊，国) 实现了一个功能，把每个迭代的结果唯一地映射到一个迭代的次序 _ 啊上。因此，利用四元组g 构造一个函数性的密码系统，可以保证解密的 唯一性。简单地说，向后确定性保证了l 系统g 上的任一生成字哦都对应了唯 一的一个生成字序列。用形式化语言表述为： 设四元组g = ( e ， ，国) 是向后确定的，则对于任何一个第n 步生成字嚷， 存在一个唯一的一个生成字序列，使 街寸q 斗呸斗_ l 寸q 容易推出以下定理： 在一个基于l 系统的密码体制中，公开密钥为四元组日= ( ，o i ，0 2 ，“) ，解 密密钥为四元组g = ( z ， ，功) 和翻译同态g 。如果g 是向后确定的，那么按照 日的信息解密的结果是唯一的。进一步，如果按照日把比特串加密成y ， 那么按照g 对g ( y ) 解密必然得到比特串【4 l 。 并非所有的d t o l 系统( 即l 系统中的四元组g = ( z ， ，m ) ) 都是向后确定 的。例如对于任意口，( 口) 都是同一个词x 的乘幂，则不难验证 ( 缈) = ( 国) ，即g 不是向后确定的。 进一步地，具有向后确定性的d t o l 系统，并不能作l 系统公钥密码系统的 密钥，因为向后确定性并不能保证词析的简单性吲。考虑g = ( 口，6 ，h o ，啊，动) ， 其中( ) = a b ，h o c b ) = b b ，噍( 口) = b b ， ( 6 ) = a b ，对于词6 6 口6 口6 口6 ，出现一个词有 两个前任的情况( 图3 - 2 ) 。 i h o ( a b ) = b b a b a b a b = l ( a b b b ) = h o ( b a a a ) 图3 2 一个倒具有多个前任 用数学归纳法不难证明g 是向后确定的。设g = ( 口，6 ，h o ， ，曲) 是l 系统公 钥密码系统的解密密钥，在解密过程中，对于密文b b a b a b a b ，会出现一种情况： 系统在第一步的时候寻找到b b a b a b a b 的两个前任，为了确定哪一个才是密文的 正确i j 任，系统不得不采取回溯的办法。由于g 是向后确定的，最终系统仍能唯 的确定迭代序列，但在解密阶段浪费了一定的代价，而且对解密过程的编程工 作也变得复杂。为了解决这个问题需要引入强向后确定的概念。 3 3 2 2 强向后确定性 称四元组g = ( ，啊，国) 是强向后确定的，当且仅当吩( x ) = 曩 ) 成立 时，必有f = ，x = ) 。 对比向后确定性的定义，强向后确定性保证了g 的任一个r l 步生成字， 其生成字序列不仅是唯一的，而且其逆序列都是可确定推出的。用形式化语言表 述为： 设四元组g = ( ，啊，c o ) 是强向后确定的，则对于任何一个r l 步生成字， 存在一个唯一的一个生成字序列，使 0 3 专q 一( 0 2 - - - h 一( o n 1 斗 并且存在唯一的h - l o , h ，使得 h - 1 ( 皑) = ( 皑1 ) 强向后确定性保证了一个词的词析序列仅仅取决于该词本身。这说明了在构 建l 系统公钥密码体制的时候，解密密钥g = ( ，曩，国) 必须具有强向后确定性 的原因。只有g 具备强向后确定性，在解密过程中，词析才可以从右向左完成 而不需要依赖以前的结果。 3 3 3 陷门函数设计 设计l 系统陷门函数，本质上就是设计一个对应关系，使得公开密钥和初 始值通过这个对应关系可以转化成容易词析的形式。确切地讲，陷门函数提供了 一个_ 的对应关系，使得一个t o l 系统h = ( ，c r o ，q ，“) 能通过陷门函数， 对应一个具有向后确定性的d t o l 系统g = ( ，啊，) 。假设已知初值m 和函数 吼，c r 2 ，以及y ，使得) ，= 气巳( 功，尽管向后确定性保证比特串屯是唯一的， 但在缺乏陷门的前提下，寻找比特串是困难的。通过陷门g ：一f 可以 把以上式子转化成如下形式： g ( ) ，) = ( g ( x ) ) ( 3 。7 ) 依赖d t o l 系统中的向后确定性，该比特串就能够很容易地找到。 具体地说，设四元组g = ( ， ，) 是向后确定的，选择使得l i 。设 同态g ：寸f ，使g 满足：a 中的每一个字母映射到z 一个字或空词a ，且有 任意口z ，g - 1 ( 口) o ，即任意字母口z 至少有一个后代。同时我们定义两个 概念： 称字母d a 是字母f i e 的一个后代，如果g 耐) = a 称字母d a 是一个傀儡( c i p h e r ) ，如果g ( d ) = a ，傀儡是空字的后代。 g 所定义的映射需要满足一定的条件，使得g 具有在两个不同的语言之间进 行“翻译”的作用，称g 翻译同态。g 所需的条件将在第5 章作详细介绍。至此， 一个l 系统公钥密码体制的公私钥对构造完成： 四元组日= ( ，o o ，“) 作为公开密钥 四元组g = ( ，h o ， ，国) 和翻译同态g 作为解密陷门，其中关键的参数是 g 。 3 4l 系统与其他技术的结合 尽管基于l 系统的公钥密码体制突破了传统的难解问题范围，但是它并不是 对传统加密方法的否定。在实际应用中，它可以和传统的置换和移位算法结合， 从而得到安全性更高的体制。例如，可以模仿d e s ( 数据加密标准) 对中间密文作 1 9 移位变换。 除了和其他加密方法结合外，l 系统公钥密码体制也可以和其他技术结合得 到更完善的实现。当加密出现了明文过长的情况，如果和数据压缩结合，把得到 的长密文进行压缩，就可以达到更佳的效果。 第4 章l 系统公钥密码体制的算法复杂性 4 1l 系统的生长函数 在密码体制设计的过程中，一个重要问题是生成字的长度。引入一个新的符 号，用# z ( c a ) 或者# ：表示字中包含在字母表中的字母出现的次数。若字母 表包含一个字母q ，则符号# 。细) 表示字国中字母q 出现的次数。不失一般性， i 殳z = a o ，a l ，a 2 ，a 3 ， ，用一个简化的符号# ( ) 表示撑“( 国) 用l 叫表示字彩的长度，则用c o ( i ) 表示字( - 0 中的第f 个字母，其中 0 i s l 酬一1 本节研究的目的在于分析l 系统的生成字序列字长的变化。利用基于l 系统 公钥密码体制中进行加密的时候，生成的密文以及中间密文的长度关系到整个公 钥密码体制的应用价值。若生成密文过大，不仅引起空间的指数爆炸，也让时间 复杂度呈指数级增长。 4 1 1 生长函数定义 生长函数的定义：对任一个d o l 系统g o o = ( ，h ，国) ，e ( g ) 是该l 系统g 生成 的字的序列： e ( g ) = c o o ，0 9 1 ，o ) 2 ， ( 4 一1 ) 定义函数，： r 斗n ，使厂伽) 刊q l ，n 0 ，则函数，( n ) 称为d o l 系统的生 长函数。 在研究生长函数的时候我们不关心l 系统的生成字本身，而只关心l 系统的 生成字字长与迭代步数的对应关系。生长函数的定义是针对确定性l 系统的，因 为只有确定性l 系统的生成字序列才是确定的，其生成字字长的序列才具有函数 性。 4 2d o l 系统的生长函数 生成矩阵的定义： 对任一个d o l