2023年7月31日发(作者：)

第２９卷第１０期　计算机应用与软件　Ｖｏ１．２９　Ｎｏ．１０　２０１２年１Ｏ月　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　ａｎｄ　Ｓｏｆｔｗａｒｅ　０ｃｔ．２０１２　基于彩虹表的ＰＤＦ文档口令破解研究　李　超　陈丹伟　（南京邮电大学计算机学院江苏南京２１００４６）　摘　要　彩虹表算法实现简单，被广泛应用于口令破解问题。对ｐｄｆ文档口令生成算法进行研究，并结合彩虹表算法，设计合适　的单向破解函数，提出基于彩虹表的ｐｄｆ文档口令破解方案。实验结果表明该方案相较于传统方案，破解时间最短９７．４８秒，最长　３７２．１２秒，平均时间为１２１．４６秒，均优于现有软件方案。　关键词　彩虹表　时空折中ｐｄｆ文档　密钥搜索　中图分类号ＴＰ３０９　文献标识码Ａ　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００—３８６ｘ．２０１２．１０．０３６　ｏＮ　ＰＤＦ　ＤｏＣＵＭＥＮＴ　ＰＡＳＳＷｏＲＤ　ＣＲＡＣＫＩＮＧ　ＢＡＳＥＤ　ｏＮ　ＲＡＩＮＢｏＷ　ＴＡＢＬＥＳ　Ｌｉ　Ｃｈａｏ　Ｃｈｅｎ　Ｄａｎｗｅｉ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ，　ｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＰｏｓｔｓ　ａｎｄ　Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｎａｎｊｉｎｇ　２１００４６，Ｊｉａｎｇｓｕ，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ　Ｔｈｅ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　ｒａｉｎｂｏｗ　ｔａｂｌｅｓ　ｉｓ　ｓｉｍｐｌｅ　ＳＯ　ｔｈｅｙ　ａｒｅ　ｗｉｄｅｌｙ　ｕｓｅｄ　ｉｎ　ｐａｓｓｗｏｒｄ　ｃｒａｃｋｉｎｇ　ｆｉｅｌｄ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｗｅ　ｆｉｒｓｔ　ｓｔｕｄｙ　ｔｈｅ　ｐａｓｓｗｏｒｄ　ｇｅｎｅｒａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ＰＤＦ　ｄｏｃｕｍｅｎｔｓ，ｔｈｅｎ　ｗｅ　ｄｅｓｉｇｎ　ａ　ｐｒｏｐｅｒ　ｏｎｅ—ｗａｙ　ｃｒａｃｋｉｎｇ　ｆｕｎｃｔｉｏｎ　ｉｎ　ｃｏｍｂｉｎａｔｉｏｎ　ｗｉｔｈ　ｒａｉｎｂｏｗ　ｔａｂｌｅ　ａｌｇｏｒｉｔｈｍ，ａｎｄ　ｐｒｏｐｏｓｅ　ａ　ｐａｓｓｗｏｒｄ　ｃｒａｃｋｉｎｇ　ｓｃｈｅｍｅ　ｆｏｒ　ＰＤＦ　ｄｏｃｕｍｅｎｔ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｒａｉｎｂｏｗ　ｔａｂｌｅｓ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｔｒａｄｉｔｉｏｎａｌ　ｓｃｈｅｍｅｓ，ｔｈｉｓ　ｓｃｈｅｍｅ　ｏｕｔｐｅｒｆｏｒｍｓ　ｔｈｅｍ　ｉｎ　ｃｒａｃｋｉｎｇ　ｔｉｍｅｓ　ｗｉｔｈ　ｔｈｅ　ｓｈｏｒｔｅｓｔ　９７．４８　ｓｅｃｏｎｄ，ｔｈｅ　ｌｏｎｇｅｓｔ　３７２．１２　ｓｅｃｏｎｄ　ａｎｄ　ｔｈｅ　ａｖｅｒａｇｅ　１２１．４６　ｓｅｃｏｎｄ．　Ｋｅｙｗｏｒｄｓ　Ｒａｉｎｂｏｗ　ｔａｂｌｅ　Ｔｉｍｅ　ｍｅｍｏ￣ｔｒａｄｅ—ｏｆｆ　ＰＤＦ　ｄｏｃｕｍｅｎｔ　Ｃｉｐｈｅｒ　ｋｅｙ　ｓｅａｒｃｈ　机制进行研究，并结合彩虹表算法，设计合适可行的从密钥空间　０　引　言　Ａ映射到伪随机流空间Ｂ的单向函数ｗ及逆函数Ｒ，提出基于　彩虹表算法的ｐｄｆ文档口令破解方案。最后在文章末尾对破解　随着信息技术的发展，密码分析得到广泛应用。从理论上　方案进行实验验证，实验结果表明该方案具有较好的性能，能够　来说，可以采用穷举搜索方法…或字典攻击方法　Ｊ，但是前者　在平均１２１．４６秒时间内破解ｐｄｆ文档口令密码，且成功率高于　需要天文数字级别的计算时间，后者需要海量的预存储空间，因　９５％。　此在实际使用中都不可行。１９８０年，Ｈｅｌｌｍａｎ基于这两种方法　提出时间和空间折中算法　，简称为时空折中算法（ＴＭＴＯ），并　１　相关工作　将之用于ＤＥＳ攻击上。假设有ｔ张ｍ　ｘｔ张Ｈｅｌｌｍａｎ表，密钥空　间为Ⅳ，则其需要的存储空间为Ｍ＝ｍｔ　，其计算时间Ｔ＝ｔ２，Ｔ＝　１．１彩虹表算法　＇　＝＾厂｝，因此密钥攻击者能够以选择明文攻击的方式获得比穷　彩虹表主要用于分析对称密码算法的口令破解和攻击，假　，　举方法快Ｊ７、厂『的代价，成功破译密钥最主要的限制为表的大小，　设存在密码系统Ｓ　：ｓ　—　ｓ　，并已知明密文对（　，Ｃｏ），要求　当表增大以获得高成功率时，表中节点碰撞并导致链重合概率　出对应的密钥　。为了应用彩虹表算法来解决此问题，主要完　大增。为此，基于ＴＭＴＯ，多种方法被提出　Ｊ。Ｏｅｃｈｓｌｉｎ在　成两个阶段工作：①预计算阶段一创建彩虹表；②在线分析阶　２００３年结合Ｈｅｌｌｍａｎ表和ＤＰ技术，提出彩虹表算法　，该算法　段一利用彩虹表进行在线分析。　和ＴＭＴＯ最大的不同是每列使用不同的Ｒ函数，这样只有当彩　（１）预计算阶段　虹表中两个节点在同一列发生碰撞时，才会导致链合并。彩虹　从密钥空间Ⅳ中随机选择ｍ个初始节点ｓＰ　（１≤　≤ｍ），分　表算法具有实现简单，攻击效率高特点，被广泛应用于密码分析　收稿日期：２０１２—０８—０６。２０１２中国计算机大会论文。教育部英特　问题　ｔ　。　尔精品课程建设项目（４７００４１０Ｇ０１）；江苏高校优势学科建设工程资助　目前ｐｄｆ文档广泛存在于各行各业，对其密码生成及破解　项目（ＹＸ００２００１）。李超，讲师，主研Ｉ颔域：信息安全，嵌入式系统。陈丹　技术进行研究具有重要的用途。本文首先对ｐｄｆ文档口令加密　伟，教授。　１３８　别代入式（１）进行计算：　ｌ厂（　）＝Ｒ　（Ｓ　（Ｐ））１≤ｉ≤ｔ　计算机应用与软件　２０１２血　字节数据进行ＭＤ５加密，然后将加密字典０条目输入到ＭＤ５　（１）　函数，紧接将Ｐ条目输人到ＭＤ５函数，最后将该ＰＤＦ文档的ＩＤ　标识数组的第一个元素输入到ＭＤ５函数，得到全局密钥。基于　其中Ｓ为加密算法，Ｐ为明文，　为密钥，Ｒ密文空间到密钥空间　的映射函数。则对于每个初始节点　次，得到ｔ个密钥，如式（２）所示：　：　，　．应用式（１）重复计算ｔ　全局密钥计算出对象加密密钥，其产生过程为：将对象号和产生　号作２进制整数对待，将原始的Ⅳ字节长的全局密匙扩展到ｎ　＋５字节，即将对象号的低３个字节和产生号的低２个字节依　次接在前面Ⅳ字节长的加密　密钥上，初始化ＭＤ５哈希函数，　：　…　（２）　将ｍ个＜ｓＰ　ＥＰ，＞对保存在一个表中，中间密钥则略去不　保存，这样得到的表被称为彩虹表。由于彩虹表中间密钥被略　去不保存，相对于字典攻击来说，这样便省去大量存储空间。在　然后将产生的字符串输入到ＭＤ５中产生ｈａｓｈ值，即为对象密　钥。对象密钥可作为ＲＣ４和ＡＥＳ对称加密算法的密匙来对流　对象进行加密。　线分析时，中间密钥可以按照式（２）进行恢复，当然彩虹攻击需　要比字典攻击更多的时间。　由于彩虹表所包含的密钥空间通常小于总密钥空间Ｎ，所　以彩虹攻击并不能保证一定能够成功。对于单个彩虹表来说，　其最大破解概率满足式（３）。所以要想提高成功概率，需采用　多个彩虹表来达到。　Ｐ　（ｔ）≈ｌ一（１一　）　１一ｅ　≈１　≈８６％（３）　（２）在线分析阶段　给定密文ｃｎ，首先使用Ｒ　得到Ｙ。，Ｙ，：Ｒ　（Ｃｏ），如果等　于彩虹表中某一链尾　，，则从链首按照公式（２）重构这个链；　如果不等，则按照Ｃ。　＿三ｙ２　Ｙ１，然后将Ｙ　与彩虹表　链尾元素进行匹配，依次类推　因此对于单个彩虹表来说，最坏　情况下需要迭代计算　次／函数，这比使用Ｈｅｌｌｍ　表　节省一半的计算量。　文献［５］表明，密钥空间Ⅳ、在线分析时间　、彩虹表存储容　量　以及成功概率Ｐ之间满足式（４）：　＾　７１＝　（Ｐ　）　（４）　由此可见如果想要缩短在线分析时间，应该提高彩虹表存　储容量，即增加表中链数目，减少单链的链长。当　（Ｐ　）＝１　时，式（４）可以推导出Ｔ＝Ｍ：ＮＳ－，这表明彩虹表具有传统Ｈｅｌｌ—　ｍａｌｌ表的特性。　１．２　ｐｄｆ文档加密原理　按照ｐｄｆ标准规范　］，其文档加密主要全局密钥生成及　加密等步骤，具体流程如图１所示。　图１　ｐｄｆ文档加密流程　ｐｄｆ文档口令长度最长为　字节，如果不足则以固定数据　填充为３２字节，如果超过３２字节则超过部分会被丢弃。对３２　２　基于彩虹表ＰＤＦ文档口令破解方案设计　２．１彩虹表创建　要得到高效的彩虹攻击效果，必须首先创建高效的彩虹表，　即减少重复数据存储，同时为了便于表的存储及提高执行效率，　可以包含价表（　＞＝１），每个表中包含ｍ条链，每条链包含ｔ　个密钥节点。每个表随机选出ｍ个密钥作为初始节点　（１≤　≤ｍ），按照式（２）迭代ｔ次，生成表结构如下：　ｓＰ　：　．　…　ｘ　：　．　，ｓＰ　：　Ｉ厂　…　三－＋　：ＥＰ：　．　．：ｌ．　；　；　５　：　．　…　：　．将表中每条链的链首和链尾元素存储，得到１个彩虹表　｛（ＳＰ　，ＥＰ　）｝羔　，其它　１个彩虹表按照类似方式产生。　文献［１４］指出，单个完美彩虹表最大链数为ｍ…（ｔ）一　，最大成功概率Ｐ…＝（１一　）　一ｌ—ｅ＿　一８６％，　所以为了得到较高成功率，必须增加彩虹表的数目。假设在给　定存储空间Ｍ＝２ＧＢ，密钥空间Ｎ＝２　以及期望的成功率Ｐ　＝９９．９％，在分析时问最短的目标下可以计算出彩虹表数　每　个彩虹表链的数目ｍ，以及每条链长度　。　，＿ｒ二　二　ｊ—ｄ　一。　２　一。　ｍ＝Ｍ／ｆ＝５３６８７０９ｌ　ｌ　３５３６８　（ｆｌｎ（　一　））　因为ｐｄｆ文档的初始口令长度固定为３２字节，一般情况下　用户不会设置长度为３２字节的１３令，一般１３令长度为ｌ０字节　左右。按照ｐｄｆ文档规范，不足３２字节部分用固定密码内容来填　充。假设口令长度不大于２４字节，则最后８个字节口令明文Ｐｎ　固定为：Ｏｘ２ｆ，０ｘ０ｃ，Ｏｘａ９，Ｏｘｆｅ，０ｘ６４，０ｘ５３，０ｘ６９，０ｘ７ａ，其对应　密文ｃｎ则可以从加密后的ｐｄｆ文档中提取，所以流密钥　：Ｃｏ　０　Ｐｎ记为Ｂ，把决定ＲＣ４初始化向量的４Ｏ　ｂｉｔ密钥记作　，则建　立单向函数　—一Ｂ，即４０ｂｉｔ密钥Ａ映射到６４ｂｉｔ伪随机流Ｂ，其　反向函数Ｒ　可以简单设计为截短函数加上循环变量ｉ即可。　２．２在线分析　按照彩虹表的定义，ｐｄｆ文档口令破解在线分析基本算法流　程如下：　第１０期　李超等：基于彩虹表的ＰＤＦ文档口令破解研究　１３９　步骤１应用函数Ｒ　，计算密文Ｃ所对应的密钥Ｋ；　步骤２应用Ｗ，Ｒ　函数，迭代生成以密钥　开始的密钥　链，链尾元素为ＥＰ　；　步骤３检验ＥＰ　是否匹配彩虹表某链尾元素　［１，ｍ］；　步骤４如果ＥＰ　和某链尾元素ＥＰ　相等，则重新生成以　ＥＰ　为首的链，检验是否确实为密钥，如果是，则算法结束，否则　Ｖｊ∈　（　一　（　其中：　＋　）ｚ　出现假警，转到步骤１继续运算。　步骤５如果遍历到彩虹表中首节点时，还没有匹配成功　则整个算法结束，搜索失败。　一般情况下，单表成功概率最大为８６％，如果想要提高成　功概率，可以增加多个表的方式来完成。另外在线分析时间也　是一个非常关键的要素，缩短链长和增加链数都可以降低在线　分析时间。　在线分析性能好坏取决于多方面的因素，其中假警率是关　键要素之一。当为单张彩虹表时，ｋ次搜索得到的假警总期望　最大不超过　生　二　。　证明：　ｍ　ｋ—ｉ　　．．ｔ一１　Ｅ（Ｆ　）≤　＋÷　：　ｆ二　＋　２　Ｎ－　２　一　—　ｉ　＝１　２±　Ｉ　二　２　２Ⅳ　其中ｍ为单表中链数目，Ⅳ为密钥空间，ｔ为链长度。　３实验及结果分析　为验证算法性能，依据已生成彩虹表（参数见表１）本文在　ＰＣ（ＣＰＵ：２．９９ＧＨｚ，内存：２ＧＢ，操作系统：Ｗｉｎｄｏｗｓ　ＸＰ）环境下　对１０００个样本ｐｄｆ加密文档进行了测试，得出平均分析时间，　最长分析时问，一　成功概率等实验数据，见表１、表２、表３和表４。　表１彩虹表参数　表２在线分析时间　暴力破解　穷尽搜索　彩虹表　最少假警次数　平均假警次数　最多假警次数　４９　１２８　５１７　表２给出了在线分析的理论时间和实际测试时间。理论时　间按照下列公式计算。　．　ｍ　（ｉ一１）　ｑ　一　一　号（１一号）　每个ｐｄｆ文档口令破解时间平均在２分钟时间，而如果采　用暴力破解方法，则破解时间需要８０天左右，破解速度可以提　高５００００倍，效率非常高。当然相对于暴力破解来说，需要预先　花费大量的时间创建彩虹表，并且需要额外的２ＧＢ内存空间来　存放彩虹表。　文献［１４］表明，在线分析时间ｒｒ正比于　，反比于　，和　成功率Ｐ　成正比。本文在不同成功率下测试这几个参数之间　的关系，如图２所示。　图２　ＴｉＭ／ＮｉＰ　关系图　４　结语　彩虹表算法在时间和空间上寻求最佳折中点，在口令破解　中具有非常重要的应用价值。本文针对ｐｄｆ文档加密算法的特　点，构建相应彩虹表，表的参数：表数目／－４，每表链数目ｍ＝　５３６８７０９１，链长度　＝３５３６８，存储空问　＝２ＧＢ。使用该彩虹表　用于ｐｄｆ类型的文档口令破解并进行实验验证，实验结果表明　该方案破解口令时间快于暴力破解方法５００００倍，具有较好效　果。　参考文献　［１］Ｋｅｄｅｍ，ｌｓｈｉｈａｒａ．Ｂｒｕｔｅ　ｆｏｒｃｅ　ａｔｔａｃｋ　ｏｎ　ＵＮＩＸ　ｐａｓｓｗｏｒｄｓ　ｗｉｔｈ　Ｓ１ＭＤ　ｃｏｍｐｕｔｅｒ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ｔｈｅ　８ｔｈ　ＵＳＥＮＩＸ　Ｓｅｃｕｒｉｔｙ　Ｓｙｍｐｏｓｉｕｍ，　１９９９，８：８—８．　［２］Ｄａｎｄａｓｓ　Ｙ　Ｓ．Ｕｓｉｎｇ　ｆｐｇａｓ　ｔｏ　ｐａｒａｌｌｅｔｉｚｅ　ｄｉｃｔｉｏｎａｒｙ　ａｔｔａｃｋｓ　ｆｏｒ　ｐａｓｓｗｏｒｄ　ｃｒａｃｋｉｎｇ［Ｃ］／／Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｍｉｓｓｉｓｓｉｐｐｉ　Ｓｔａｔｅ　ＵＳＡ，２００８．　［３　ｊ　Ｈｅｌｌｍａｎ　Ｍ　Ｅ．Ａ　Ｃｒｙｐｔａｎａｌｙｔｉｃ　Ｔｉｍｅ—ｍｅｍｏｒｙ　Ｔｒａｄｅ　ｏｆｆ［Ｊ］．ＩＥＥＥＴｒａｎｓ—　ａｃｔｉｏｎｓ　Ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ，１９８０，ＩＴ一２６：４０１—４０６．　［４］Ｊｉｎ　Ｈｏｎｇ，Ｋｙｕｎｇ　Ｃｈｕｌ　Ｊｅｏｎｇ，Ｅｕｎ　Ｙｏｕｎｇ　Ｋｗｏｎ，ｅｔ　ａ１．Ｖａｒｉａｎｔｓ　ｏｆ　ｔｈｅ　Ｄｉｓｔｉｎｇｕｉｓｈｅｄ　Ｐｏｉｎｔ　Ｍｅｔｈｏｄ　ｍｒ　Ｃｒｙｐｔａｎａｌｙｔｉｅ　Ｔｉｍｅ　Ｍｅｍｏｒｙ　Ｔｒａｄｅ—ｏｆｆｓ　［Ｃ］／／Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｍａｔｈｅｍａｔｉｃａ１．ＳｃｉｅｎｃｅｓａｎｄＩ　Ｓａ　Ｃ—ＲＩＭ．Ｓｅｏｕｌ：　１４０　ＳｅｏｕｌＮａｔｉｏｎａｌ　Ｕｎｉｖｅｒｓｉｔｙ，２００８：１５１—７４７．　计算机应用与软件　２０１２血　其进行归一化处理，使其欧氏范数为１；随后使用Ｋ均值算法产　ａｔ　Ａ，Ｎａｏｒ　Ｍ．Ｒｉｇｏｒｏｕｓ　ｔｉｍｅ／ｓｐａｃｅ　ｔｒａｄｅｏｆｆｓ　ｆｏｒ　ｉｎｖｅｒｔｉｎｇ　ｆｕｎｃｔｉｏｎｓ　［５］　Ｆｉｃｏｌｌ　∈｜ｏ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ｔｈｅ　２３ｒｄ　Ａｎｎｕａｌ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍ—　ｐｕｔｉｎｇ，ｌ９９１：５３４—５４１．　［６］　Ｄｅｎｎｉｎｇ　Ｄ　Ｅ．Ｃｒｙｐｔｏｇｒａｐｈｙ　ａｎｄ　Ｄａｔａ　Ｓｅｃｕｒｉｔｙ［Ｍ］．Ａｄｄｉｓｏｎ—Ｗｅｓｌｅｙ，　ｌ９８２．　［７］　Ｏｅｃｈｓｌｉｎ　Ｐ．Ｍａｋｉｎｇ　ａ　Ｆａｓｔｅｒ　ＣＤ＇ｐｔａｎａｌｙｔｉｃ　Ｔｉｍｅ—ｍｅｍｏ￣Ｔｒａｄｅ－ｏｆｆ　［Ｃ］／／Ｄａｎ　Ｂｏｎｅｈ．Ａｄｖａｎｃｅｓ　ｉｎ　Ｃｒｙｐｔｏｌｏｇｙ—ＣＲＹＰＴＯ　０３．Ｃａｌｉｆｏｒｎｉａ，　ＵＳＡ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，２００３：６１７—６３０．　［８］　Ｍｅｎｔｅｎｓ　Ｎ，Ｂａｔｉｎａ　Ｌ，Ｐｒｅｎｅｅｌ　Ｂ，ｅｔ　ａ１．Ｃｒａｃｋｉｎｇ　Ｕｎｉｘ　ｐａｓｓｗｏｒｄｓ　Ｕｓｉｎｇ　ＦＰＧＡ　ｐｌａｔｆｏｒｍｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｓｐｅｃｉａｌ　Ｐｕｒｐｏｓｅ　Ｈａｒｄｗａｒｅ　ｆｏｒ　Ａｔｔａｃｋｉｎｇ　Ｃ１７ｐｔｏｇｒａｐｈｉｃ　Ｓｙｓｔｅｍｓ　２００５，ＳＨＡＲＣＳ’０５．　［９］　Ｔｈｅｏｈａｒｏｕｌｉｓ　Ｋ，Ｐａｐａｅｆｓｔａｔｈｉｏｕ　Ｉ，Ｍａｎｉｆａｖａｓ　Ｃ．Ｉｍｐｌｅｍｅｎｔｉｎｇ　Ｒａｉｎ—　ｂｏｗ　Ｔａｂｌｅｓ　ｉｎ　Ｈｉｇｂ－－ｅｎｄ　ＦＰＧＡｓ　ｆｏｒ　Ｓｕｐｅｒ－－ｆａｓｔ　Ｐａｓｓｗｏｒｄ　Ｃｒａｃｋｉｎｇ　［Ｃ］／／２０１０　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　Ｆｉｅｌｄ　Ｐｒｏｇｒａｍｍａｂｌｅ　Ｌｏｇｉｃ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ．　［１０］　Ｃａｒｓｏｎ　Ｔ，Ｂａｋｅｒ　Ｄ．Ａｄｏｂｅ　Ａｃｒｏｂａｔ　ａｎｄ　ＰＤＦ　ｆｏｒ　Ａｒｃｈｉｔｅｃｔｕｒｅ，Ｅｎｇｉｎｅｅｒ—　ｉｎｇ，ａｎｄ　Ｃｏｎｓｔｒｕｃｔｉｏｎ［Ｍ］．Ｌｏｎｄｏｎ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，２００６：２０７．　Ｗａｒｎｏｃｋ，Ｊｏｈｎ．Ｔｈｅ　Ｃａｍｅｌｏｔ　Ｐｒｏｊｅｃｔ［ＯＬ］．１９９１．ｈｔｔｐ：／／ｗｗｗ．ｐｌａｎｅｔ—　ｐｄｆ．ｃｏｎｕ＇ｍａｉｎｐａｇｅ．ａｓｐ　ｗｅｂｐａｇｅｉｄ＝１　８５　１　［１２］　Ａｄｏｂｅ　Ｓｙｓｔｅｍ　Ｉｎｃｏｑ￣ｏｒａｔｅｄ．Ａｄｏｂｅ　Ｐｏｒｔａｂｌｅ　Ｄｏｃｕｍｅｎｔ　Ｆｏｒｍａｔ　Ｒｅ￣ｒ－　ｅｎｅｅ　Ｍａｎｕａｌ［Ｍ］．Ｖｅｒｓｉｏｎ　１．７，２００６．　［１３］　Ａｄｏｂｅ　Ｓｙｓｔｅｍｓ　Ｉｎｃｏｒｐｏｒａｔｅｄ．ＰＤＦ　Ｒｅｆｅｒｅｎｃｅ，Ｔｈｉｒｄ　Ｅｄｉｔｉｏｎ，Ａｄｏｂｅ　Ｐｏｔａｂｌｅ　Ｄｏｃｕｍｅｎｔ　Ｆｏｒｍａｔ　Ｖｅｒｓｉｏｎ　１．４［Ｍ］．Ａｍｅｒｉｃａｎ：Ａｄｄｉｓｏｎ－Ｗｅｓｌｅｙ，２００１．　［１４］　Ａｖｏｉｎｅ　Ｇ，Ｊｕｎｏｄ　Ｐ，Ｏｅｃｈｓｌｉｎ　Ｐ．Ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ　ａｎｄ　ｉｍｐｒｏｖｅｍｅｎｔ　ｏｆ　ｔｉｍｅ－ｍｅｍｏｒｙ　ｔｒａｄｅ—ｏｆｆ　ｂａｓｅｄ　ｏｎ　ｐｅｒｆｅｃｔ　ｔａｂｌｅｓ［Ｊ］．ＡＣＭ　Ｔｒａｎｓ．Ｉｎ—　ｏｆｍｒ．Ｓｙｓｔ．Ｓｅｃｕｒ．，２００８，１１（４）．　（上接第７０页）　因此成为近年来机器学习领域非常流行的评价指标之一。当两　个类别标签一一对应时，ＮＭＩ值达到最大值１。　将本文的算法（简记为ＫＬ）与以下９个算法相比较，它们　是：文献［２］提出的基于图划分算法的ＣＳＰＡ、ＨＧＰＡ、ＭＣＬＡ；文　献［３］提出的ＳＭＳＡ和ＳＧＴＡ；文献［４］提出的４个基于单连接、　全连接、组平均和Ｗａｒｄ的证据累积算法，为方便起见，分别简　记为ＥＡＳＩ　ＥＡＣＬ、ＥＡＡＬ和ＥＡＷＬ。　０３　它　盅　面０２　量　Ｚ　Ｏ１　ｏ．０　哺ｂｅｄｈ　ｒｅｖｉ￣　Ｉａ１２　打３１　ｂ＇４１　Ｄ毒￡ａｓｅｌ　图２聚类集成算法所获得的ＮＭＩ值　将１Ｏ个聚类集成算法分别在不同数据集上进行聚类，获得　的ＮＭＩ值如上图２所示。对于每个数据集，首先将每个文本根　据ＴＦ—ＩＤＦ（ｔｅｒｍ　ｆｒｅｑｕｅｎｃｙ—ｉｎｖｅｒｓｅ　ｄｏｃｕｍｅｎｔ　ｒｆｅｑｕｅｎｃｙ）加权，并对　生１５个聚类成员，Ｋ均值算法每次随机选取初值，并且采用余　弦函数计算文本之间的相似度。因为算法ＨＧＰＡ调用了ＨＭＥ—　¨　ＴＩＳ算法，而ＨＭＥＴＩＳ得到局部最优解，所以ＨＧＰＡ算法获得的　聚类结果不稳定，我们运行１０次取平均值；调用图划分算法　ＭＥＴＩＳ的ＣＳＰＡ和ＭＣＬＡ获得的结果稳定；层次聚类算法，谱聚　类算法和本文设计的算法都获得了稳定的结果。　我们可以根据图２作出以下几个比较：　（１）比较ＣＳＰＡ、ＨＧＰＡ和ＭＣＬＡ，ＣＳＰＡ都获得了最好的结　果，这与文献［２］的结论相符。（２）比较ＥＡＳＬ、ＥＡＣＬ、ＥＡＡＬ和　ＥＡＷＬ，ＥＡＡＬ和ＥＡＷＬ的聚类效果明显优于ＥＡＳＬ和ＥＡＣＬ，这　与文献［４］中的结论相符。（３）比较ＳＭＳＡ和ＳＧＴＡ，两个算法　在６组数据集上的ＮＭＩ值互有高低，这与文献［３］中的结论相　符。（４）与其他９个算法相比，除了在数据集ｌａ１２上获得了比　ＥＡＷＬ略低的ＮＭＩ值，ＫＬ都获得了最高的ＮＭＩ值。　４　结语　本文结合Ｋ均值与谱聚类设计了一种聚类集成算法，它充　分利用了聚类成员提供的属性信息与关系信息。为了有效降低　该算法的计算复杂度，本文通过代数变换方法有效避免了大规　模矩阵的特征值分解问题。在多组真实数据集上的实验结果表　明，本文的算法优于其他聚类集成算法。本文的方法为解决聚　类集成问题提供了一种新思路。　参考文　献　Ｔａｎ　Ｐ　Ｎ，Ｓｔｅｉｎｂａｃｈ　Ｍ，Ｋｕｍａｒ　Ｖ．Ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔｏ　ｄａｔａ　ｍｉｎｉｎｇ［Ｍ］．　ＭＡ，ＵＳＡ：Ａｄｄｉｓｏｎ—Ｗｅｓｌｅｙ　Ｌｏｎｇｍａｎ　Ｐｕｂｌｉｓｈｉｎｇ　Ｃｏ．，Ｉｎｃ．Ｂｏｓｔｏｎ，　２０１０．　［２］　Ｓｔｒｅｈｌ　Ａ．Ｇｈｏｓｈ　Ｊ．Ｃｌｕｓｔｅｒ　ｅｎｓｅｍｂｌｅｓ－ａ　ｋｎｏｗｌｅｄｇｅ　ｒｅｕｓｅ　ｆｒａｍｅｗｏｒｋ　ｆｏｒ　ｃｏｍｂｉｎｉｎｇ　ｐａｒｔｉｔｉｏｎｉｎｇｓ［Ｊ］．Ｔｈｅ　Ｊｏｕｒｎａｌ　ｏｆ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ　Ｒｅ—　ｓｅａｒｃｈ，２００２，３：５８３—６１７．　［３］　徐森，卢志茂，顾国昌．使用谱算法解决文本聚类集成问题［Ｊ］．　通信学报，２０１０　３１（６）：５８～６６．　［４］　Ｆｒｅｄ　Ａ，Ｌｏｕｒｅｎｇｏ　Ａ．Ｃｌｕｓｔｅｒ　ｅｎｓｅｍｂｌｅ　ｍｅｔｈｏｄｓ：ｆｒｏｍ　ｓｉｎｇｌｅ　ｃｌｕｓｔｅｒ－　ｉｎｇｓ　ｔｏ　ｃｏｍｂｉｎｅｄ　ｓｏｌｕｔｉｏｎｓ［Ｍ］．Ｓｕｐｅｒｖｉｓｅｄ　ａｎｄ　Ｕｎｓｕｐｅｒｖｉｓｅｄ　Ｅｎｓｅｍ—　ｂｌｅ　Ｍｅｔｈｏｄｓ　ａｎｄ　ｔｈｅｉｒ　Ａｐｐｌｉｃａｔｉｏｎｓ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２００８：３—３０．　［５］　Ｆｅｒｎ　Ｘ　Ｚ，ＢｒＱｄｌｅｙ　Ｃ　Ｅ．Ｓｏｌｖｉｎｇ　ｃｌｕｓｔｅｒ　ｅｎｓｅｍｂｌｅ　ｐｒｏｂｌｅｍｓ　ｂｙ　ｂｉｐａｒｔｉｔｅ　ｇｒａｐｈ　ｐａｔｒｉｔｉｏｎｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　２０ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ　Ｂａｎｆｆ，Ｃａｎａｄａ，２００４．　［６］　唐伟，周志华．基于Ｂａｇｇｉｎｇ的选择性聚类集成［Ｊ］．软件学报，　２００５，１６（４）：４９６—５０２．　［７］　Ｓｅｖｉｌｌａｎｏ　Ｘ，Ａｌｉａｓ　Ｆ，Ｓｏｅｏｒ６Ｊ　Ｃ．ＢｏｒｄａＣｏｎｓｅｎｓｕｓ：ａ　ｎｅｗ　ｃｏｎｓｅｎｓｕｓ　ｆｕｎｃｔｉｏｎ　ｆｏｒ　ｓｏｆｔ　ｃｌｕｓｔｅｒ　ｅｎｓｅｍｂｌｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　３０ｔｈ　ａｎｎａ—　ａｌ　ｉｎｔｅｒｎａｔｉｏｎａｌ　ＡＣＭ　ＳＩＧＩＲ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ．２００７　７４３—７４４．　［８］　王红军，李志蜀，成飚，等．基于隐含变量的聚类集成模型［Ｊ］．　软件学报，２００９，２０（４）：８２５—８３３．　［９］　Ｗａｎｇ　Ｆ，Ｄｉｎｇ　Ｃ，Ｌｉ　Ｔ．Ｉｎｔｅｇｒａｔｅｄ　ＫＬ（Ｋ—ｍｅａｎｓ－Ｌａｐｌａｅｉａｎ）Ｃｌｕｓｔｅ—　ｉｒｎｇ：Ａ　Ｎｅｗ　Ｃｌｕｓｔｅｒｉｎｇ　Ａｐｐｒｏａｃｈ　ｂｙ　Ｃｏｍｂｉｎｉｎｇ　Ａｔｔｉｒｂｕｔｅ　Ｄａｔａ　ａｎｄ　Ｐａｉｒｗｉｓｅ　Ｒｅｌａｔｉｏｎｓ［ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　２００９　ＳＩＡＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎ—　ｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｓｐａｒｋｓ，Ｕｎｉｔｅｄ　Ｓｔａｔｅｓ．２００９：３８—４８．　

2023年7月31日发(作者：)

第２９卷第１０期　计算机应用与软件　Ｖｏ１．２９　Ｎｏ．１０　２０１２年１Ｏ月　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　ａｎｄ　Ｓｏｆｔｗａｒｅ　０ｃｔ．２０１２　基于彩虹表的ＰＤＦ文档口令破解研究　李　超　陈丹伟　（南京邮电大学计算机学院江苏南京２１００４６）　摘　要　彩虹表算法实现简单，被广泛应用于口令破解问题。对ｐｄｆ文档口令生成算法进行研究，并结合彩虹表算法，设计合适　的单向破解函数，提出基于彩虹表的ｐｄｆ文档口令破解方案。实验结果表明该方案相较于传统方案，破解时间最短９７．４８秒，最长　３７２．１２秒，平均时间为１２１．４６秒，均优于现有软件方案。　关键词　彩虹表　时空折中ｐｄｆ文档　密钥搜索　中图分类号ＴＰ３０９　文献标识码Ａ　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００—３８６ｘ．２０１２．１０．０３６　ｏＮ　ＰＤＦ　ＤｏＣＵＭＥＮＴ　ＰＡＳＳＷｏＲＤ　ＣＲＡＣＫＩＮＧ　ＢＡＳＥＤ　ｏＮ　ＲＡＩＮＢｏＷ　ＴＡＢＬＥＳ　Ｌｉ　Ｃｈａｏ　Ｃｈｅｎ　Ｄａｎｗｅｉ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ，　ｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＰｏｓｔｓ　ａｎｄ　Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｎａｎｊｉｎｇ　２１００４６，Ｊｉａｎｇｓｕ，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ　Ｔｈｅ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　ｒａｉｎｂｏｗ　ｔａｂｌｅｓ　ｉｓ　ｓｉｍｐｌｅ　ＳＯ　ｔｈｅｙ　ａｒｅ　ｗｉｄｅｌｙ　ｕｓｅｄ　ｉｎ　ｐａｓｓｗｏｒｄ　ｃｒａｃｋｉｎｇ　ｆｉｅｌｄ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｗｅ　ｆｉｒｓｔ　ｓｔｕｄｙ　ｔｈｅ　ｐａｓｓｗｏｒｄ　ｇｅｎｅｒａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ＰＤＦ　ｄｏｃｕｍｅｎｔｓ，ｔｈｅｎ　ｗｅ　ｄｅｓｉｇｎ　ａ　ｐｒｏｐｅｒ　ｏｎｅ—ｗａｙ　ｃｒａｃｋｉｎｇ　ｆｕｎｃｔｉｏｎ　ｉｎ　ｃｏｍｂｉｎａｔｉｏｎ　ｗｉｔｈ　ｒａｉｎｂｏｗ　ｔａｂｌｅ　ａｌｇｏｒｉｔｈｍ，ａｎｄ　ｐｒｏｐｏｓｅ　ａ　ｐａｓｓｗｏｒｄ　ｃｒａｃｋｉｎｇ　ｓｃｈｅｍｅ　ｆｏｒ　ＰＤＦ　ｄｏｃｕｍｅｎｔ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｒａｉｎｂｏｗ　ｔａｂｌｅｓ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｔｒａｄｉｔｉｏｎａｌ　ｓｃｈｅｍｅｓ，ｔｈｉｓ　ｓｃｈｅｍｅ　ｏｕｔｐｅｒｆｏｒｍｓ　ｔｈｅｍ　ｉｎ　ｃｒａｃｋｉｎｇ　ｔｉｍｅｓ　ｗｉｔｈ　ｔｈｅ　ｓｈｏｒｔｅｓｔ　９７．４８　ｓｅｃｏｎｄ，ｔｈｅ　ｌｏｎｇｅｓｔ　３７２．１２　ｓｅｃｏｎｄ　ａｎｄ　ｔｈｅ　ａｖｅｒａｇｅ　１２１．４６　ｓｅｃｏｎｄ．　Ｋｅｙｗｏｒｄｓ　Ｒａｉｎｂｏｗ　ｔａｂｌｅ　Ｔｉｍｅ　ｍｅｍｏ￣ｔｒａｄｅ—ｏｆｆ　ＰＤＦ　ｄｏｃｕｍｅｎｔ　Ｃｉｐｈｅｒ　ｋｅｙ　ｓｅａｒｃｈ　机制进行研究，并结合彩虹表算法，设计合适可行的从密钥空间　０　引　言　Ａ映射到伪随机流空间Ｂ的单向函数ｗ及逆函数Ｒ，提出基于　彩虹表算法的ｐｄｆ文档口令破解方案。最后在文章末尾对破解　随着信息技术的发展，密码分析得到广泛应用。从理论上　方案进行实验验证，实验结果表明该方案具有较好的性能，能够　来说，可以采用穷举搜索方法…或字典攻击方法　Ｊ，但是前者　在平均１２１．４６秒时间内破解ｐｄｆ文档口令密码，且成功率高于　需要天文数字级别的计算时间，后者需要海量的预存储空间，因　９５％。　此在实际使用中都不可行。１９８０年，Ｈｅｌｌｍａｎ基于这两种方法　提出时间和空间折中算法　，简称为时空折中算法（ＴＭＴＯ），并　１　相关工作　将之用于ＤＥＳ攻击上。假设有ｔ张ｍ　ｘｔ张Ｈｅｌｌｍａｎ表，密钥空　间为Ⅳ，则其需要的存储空间为Ｍ＝ｍｔ　，其计算时间Ｔ＝ｔ２，Ｔ＝　１．１彩虹表算法　＇　＝＾厂｝，因此密钥攻击者能够以选择明文攻击的方式获得比穷　彩虹表主要用于分析对称密码算法的口令破解和攻击，假　，　举方法快Ｊ７、厂『的代价，成功破译密钥最主要的限制为表的大小，　设存在密码系统Ｓ　：ｓ　—　ｓ　，并已知明密文对（　，Ｃｏ），要求　当表增大以获得高成功率时，表中节点碰撞并导致链重合概率　出对应的密钥　。为了应用彩虹表算法来解决此问题，主要完　大增。为此，基于ＴＭＴＯ，多种方法被提出　Ｊ。Ｏｅｃｈｓｌｉｎ在　成两个阶段工作：①预计算阶段一创建彩虹表；②在线分析阶　２００３年结合Ｈｅｌｌｍａｎ表和ＤＰ技术，提出彩虹表算法　，该算法　段一利用彩虹表进行在线分析。　和ＴＭＴＯ最大的不同是每列使用不同的Ｒ函数，这样只有当彩　（１）预计算阶段　虹表中两个节点在同一列发生碰撞时，才会导致链合并。彩虹　从密钥空间Ⅳ中随机选择ｍ个初始节点ｓＰ　（１≤　≤ｍ），分　表算法具有实现简单，攻击效率高特点，被广泛应用于密码分析　收稿日期：２０１２—０８—０６。２０１２中国计算机大会论文。教育部英特　问题　ｔ　。　尔精品课程建设项目（４７００４１０Ｇ０１）；江苏高校优势学科建设工程资助　目前ｐｄｆ文档广泛存在于各行各业，对其密码生成及破解　项目（ＹＸ００２００１）。李超，讲师，主研Ｉ颔域：信息安全，嵌入式系统。陈丹　技术进行研究具有重要的用途。本文首先对ｐｄｆ文档口令加密　伟，教授。　１３８　别代入式（１）进行计算：　ｌ厂（　）＝Ｒ　（Ｓ　（Ｐ））１≤ｉ≤ｔ　计算机应用与软件　２０１２血　字节数据进行ＭＤ５加密，然后将加密字典０条目输入到ＭＤ５　（１）　函数，紧接将Ｐ条目输人到ＭＤ５函数，最后将该ＰＤＦ文档的ＩＤ　标识数组的第一个元素输入到ＭＤ５函数，得到全局密钥。基于　其中Ｓ为加密算法，Ｐ为明文，　为密钥，Ｒ密文空间到密钥空间　的映射函数。则对于每个初始节点　次，得到ｔ个密钥，如式（２）所示：　：　，　．应用式（１）重复计算ｔ　全局密钥计算出对象加密密钥，其产生过程为：将对象号和产生　号作２进制整数对待，将原始的Ⅳ字节长的全局密匙扩展到ｎ　＋５字节，即将对象号的低３个字节和产生号的低２个字节依　次接在前面Ⅳ字节长的加密　密钥上，初始化ＭＤ５哈希函数，　：　…　（２）　将ｍ个＜ｓＰ　ＥＰ，＞对保存在一个表中，中间密钥则略去不　保存，这样得到的表被称为彩虹表。由于彩虹表中间密钥被略　去不保存，相对于字典攻击来说，这样便省去大量存储空间。在　然后将产生的字符串输入到ＭＤ５中产生ｈａｓｈ值，即为对象密　钥。对象密钥可作为ＲＣ４和ＡＥＳ对称加密算法的密匙来对流　对象进行加密。　线分析时，中间密钥可以按照式（２）进行恢复，当然彩虹攻击需　要比字典攻击更多的时间。　由于彩虹表所包含的密钥空间通常小于总密钥空间Ｎ，所　以彩虹攻击并不能保证一定能够成功。对于单个彩虹表来说，　其最大破解概率满足式（３）。所以要想提高成功概率，需采用　多个彩虹表来达到。　Ｐ　（ｔ）≈ｌ一（１一　）　１一ｅ　≈１　≈８６％（３）　（２）在线分析阶段　给定密文ｃｎ，首先使用Ｒ　得到Ｙ。，Ｙ，：Ｒ　（Ｃｏ），如果等　于彩虹表中某一链尾　，，则从链首按照公式（２）重构这个链；　如果不等，则按照Ｃ。　＿三ｙ２　Ｙ１，然后将Ｙ　与彩虹表　链尾元素进行匹配，依次类推　因此对于单个彩虹表来说，最坏　情况下需要迭代计算　次／函数，这比使用Ｈｅｌｌｍ　表　节省一半的计算量。　文献［５］表明，密钥空间Ⅳ、在线分析时间　、彩虹表存储容　量　以及成功概率Ｐ之间满足式（４）：　＾　７１＝　（Ｐ　）　（４）　由此可见如果想要缩短在线分析时间，应该提高彩虹表存　储容量，即增加表中链数目，减少单链的链长。当　（Ｐ　）＝１　时，式（４）可以推导出Ｔ＝Ｍ：ＮＳ－，这表明彩虹表具有传统Ｈｅｌｌ—　ｍａｌｌ表的特性。　１．２　ｐｄｆ文档加密原理　按照ｐｄｆ标准规范　］，其文档加密主要全局密钥生成及　加密等步骤，具体流程如图１所示。　图１　ｐｄｆ文档加密流程　ｐｄｆ文档口令长度最长为　字节，如果不足则以固定数据　填充为３２字节，如果超过３２字节则超过部分会被丢弃。对３２　２　基于彩虹表ＰＤＦ文档口令破解方案设计　２．１彩虹表创建　要得到高效的彩虹攻击效果，必须首先创建高效的彩虹表，　即减少重复数据存储，同时为了便于表的存储及提高执行效率，　可以包含价表（　＞＝１），每个表中包含ｍ条链，每条链包含ｔ　个密钥节点。每个表随机选出ｍ个密钥作为初始节点　（１≤　≤ｍ），按照式（２）迭代ｔ次，生成表结构如下：　ｓＰ　：　．　…　ｘ　：　．　，ｓＰ　：　Ｉ厂　…　三－＋　：ＥＰ：　．　．：ｌ．　；　；　５　：　．　…　：　．将表中每条链的链首和链尾元素存储，得到１个彩虹表　｛（ＳＰ　，ＥＰ　）｝羔　，其它　１个彩虹表按照类似方式产生。　文献［１４］指出，单个完美彩虹表最大链数为ｍ…（ｔ）一　，最大成功概率Ｐ…＝（１一　）　一ｌ—ｅ＿　一８６％，　所以为了得到较高成功率，必须增加彩虹表的数目。假设在给　定存储空间Ｍ＝２ＧＢ，密钥空间Ｎ＝２　以及期望的成功率Ｐ　＝９９．９％，在分析时问最短的目标下可以计算出彩虹表数　每　个彩虹表链的数目ｍ，以及每条链长度　。　，＿ｒ二　二　ｊ—ｄ　一。　２　一。　ｍ＝Ｍ／ｆ＝５３６８７０９ｌ　ｌ　３５３６８　（ｆｌｎ（　一　））　因为ｐｄｆ文档的初始口令长度固定为３２字节，一般情况下　用户不会设置长度为３２字节的１３令，一般１３令长度为ｌ０字节　左右。按照ｐｄｆ文档规范，不足３２字节部分用固定密码内容来填　充。假设口令长度不大于２４字节，则最后８个字节口令明文Ｐｎ　固定为：Ｏｘ２ｆ，０ｘ０ｃ，Ｏｘａ９，Ｏｘｆｅ，０ｘ６４，０ｘ５３，０ｘ６９，０ｘ７ａ，其对应　密文ｃｎ则可以从加密后的ｐｄｆ文档中提取，所以流密钥　：Ｃｏ　０　Ｐｎ记为Ｂ，把决定ＲＣ４初始化向量的４Ｏ　ｂｉｔ密钥记作　，则建　立单向函数　—一Ｂ，即４０ｂｉｔ密钥Ａ映射到６４ｂｉｔ伪随机流Ｂ，其　反向函数Ｒ　可以简单设计为截短函数加上循环变量ｉ即可。　２．２在线分析　按照彩虹表的定义，ｐｄｆ文档口令破解在线分析基本算法流　程如下：　第１０期　李超等：基于彩虹表的ＰＤＦ文档口令破解研究　１３９　步骤１应用函数Ｒ　，计算密文Ｃ所对应的密钥Ｋ；　步骤２应用Ｗ，Ｒ　函数，迭代生成以密钥　开始的密钥　链，链尾元素为ＥＰ　；　步骤３检验ＥＰ　是否匹配彩虹表某链尾元素　［１，ｍ］；　步骤４如果ＥＰ　和某链尾元素ＥＰ　相等，则重新生成以　ＥＰ　为首的链，检验是否确实为密钥，如果是，则算法结束，否则　Ｖｊ∈　（　一　（　其中：　＋　）ｚ　出现假警，转到步骤１继续运算。　步骤５如果遍历到彩虹表中首节点时，还没有匹配成功　则整个算法结束，搜索失败。　一般情况下，单表成功概率最大为８６％，如果想要提高成　功概率，可以增加多个表的方式来完成。另外在线分析时间也　是一个非常关键的要素，缩短链长和增加链数都可以降低在线　分析时间。　在线分析性能好坏取决于多方面的因素，其中假警率是关　键要素之一。当为单张彩虹表时，ｋ次搜索得到的假警总期望　最大不超过　生　二　。　证明：　ｍ　ｋ—ｉ　　．．ｔ一１　Ｅ（Ｆ　）≤　＋÷　：　ｆ二　＋　２　Ｎ－　２　一　—　ｉ　＝１　２±　Ｉ　二　２　２Ⅳ　其中ｍ为单表中链数目，Ⅳ为密钥空间，ｔ为链长度。　３实验及结果分析　为验证算法性能，依据已生成彩虹表（参数见表１）本文在　ＰＣ（ＣＰＵ：２．９９ＧＨｚ，内存：２ＧＢ，操作系统：Ｗｉｎｄｏｗｓ　ＸＰ）环境下　对１０００个样本ｐｄｆ加密文档进行了测试，得出平均分析时间，　最长分析时问，一　成功概率等实验数据，见表１、表２、表３和表４。　表１彩虹表参数　表２在线分析时间　暴力破解　穷尽搜索　彩虹表　最少假警次数　平均假警次数　最多假警次数　４９　１２８　５１７　表２给出了在线分析的理论时间和实际测试时间。理论时　间按照下列公式计算。　．　ｍ　（ｉ一１）　ｑ　一　一　号（１一号）　每个ｐｄｆ文档口令破解时间平均在２分钟时间，而如果采　用暴力破解方法，则破解时间需要８０天左右，破解速度可以提　高５００００倍，效率非常高。当然相对于暴力破解来说，需要预先　花费大量的时间创建彩虹表，并且需要额外的２ＧＢ内存空间来　存放彩虹表。　文献［１４］表明，在线分析时间ｒｒ正比于　，反比于　，和　成功率Ｐ　成正比。本文在不同成功率下测试这几个参数之间　的关系，如图２所示。　图２　ＴｉＭ／ＮｉＰ　关系图　４　结语　彩虹表算法在时间和空间上寻求最佳折中点，在口令破解　中具有非常重要的应用价值。本文针对ｐｄｆ文档加密算法的特　点，构建相应彩虹表，表的参数：表数目／－４，每表链数目ｍ＝　５３６８７０９１，链长度　＝３５３６８，存储空问　＝２ＧＢ。使用该彩虹表　用于ｐｄｆ类型的文档口令破解并进行实验验证，实验结果表明　该方案破解口令时间快于暴力破解方法５００００倍，具有较好效　果。　参考文献　［１］Ｋｅｄｅｍ，ｌｓｈｉｈａｒａ．Ｂｒｕｔｅ　ｆｏｒｃｅ　ａｔｔａｃｋ　ｏｎ　ＵＮＩＸ　ｐａｓｓｗｏｒｄｓ　ｗｉｔｈ　Ｓ１ＭＤ　ｃｏｍｐｕｔｅｒ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ｔｈｅ　８ｔｈ　ＵＳＥＮＩＸ　Ｓｅｃｕｒｉｔｙ　Ｓｙｍｐｏｓｉｕｍ，　１９９９，８：８—８．　［２］Ｄａｎｄａｓｓ　Ｙ　Ｓ．Ｕｓｉｎｇ　ｆｐｇａｓ　ｔｏ　ｐａｒａｌｌｅｔｉｚｅ　ｄｉｃｔｉｏｎａｒｙ　ａｔｔａｃｋｓ　ｆｏｒ　ｐａｓｓｗｏｒｄ　ｃｒａｃｋｉｎｇ［Ｃ］／／Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｍｉｓｓｉｓｓｉｐｐｉ　Ｓｔａｔｅ　ＵＳＡ，２００８．　［３　ｊ　Ｈｅｌｌｍａｎ　Ｍ　Ｅ．Ａ　Ｃｒｙｐｔａｎａｌｙｔｉｃ　Ｔｉｍｅ—ｍｅｍｏｒｙ　Ｔｒａｄｅ　ｏｆｆ［Ｊ］．ＩＥＥＥＴｒａｎｓ—　ａｃｔｉｏｎｓ　Ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ，１９８０，ＩＴ一２６：４０１—４０６．　［４］Ｊｉｎ　Ｈｏｎｇ，Ｋｙｕｎｇ　Ｃｈｕｌ　Ｊｅｏｎｇ，Ｅｕｎ　Ｙｏｕｎｇ　Ｋｗｏｎ，ｅｔ　ａ１．Ｖａｒｉａｎｔｓ　ｏｆ　ｔｈｅ　Ｄｉｓｔｉｎｇｕｉｓｈｅｄ　Ｐｏｉｎｔ　Ｍｅｔｈｏｄ　ｍｒ　Ｃｒｙｐｔａｎａｌｙｔｉｅ　Ｔｉｍｅ　Ｍｅｍｏｒｙ　Ｔｒａｄｅ—ｏｆｆｓ　［Ｃ］／／Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｍａｔｈｅｍａｔｉｃａ１．ＳｃｉｅｎｃｅｓａｎｄＩ　Ｓａ　Ｃ—ＲＩＭ．Ｓｅｏｕｌ：　１４０　ＳｅｏｕｌＮａｔｉｏｎａｌ　Ｕｎｉｖｅｒｓｉｔｙ，２００８：１５１—７４７．　计算机应用与软件　２０１２血　其进行归一化处理，使其欧氏范数为１；随后使用Ｋ均值算法产　ａｔ　Ａ，Ｎａｏｒ　Ｍ．Ｒｉｇｏｒｏｕｓ　ｔｉｍｅ／ｓｐａｃｅ　ｔｒａｄｅｏｆｆｓ　ｆｏｒ　ｉｎｖｅｒｔｉｎｇ　ｆｕｎｃｔｉｏｎｓ　［５］　Ｆｉｃｏｌｌ　∈｜ｏ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ｔｈｅ　２３ｒｄ　Ａｎｎｕａｌ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍ—　ｐｕｔｉｎｇ，ｌ９９１：５３４—５４１．　［６］　Ｄｅｎｎｉｎｇ　Ｄ　Ｅ．Ｃｒｙｐｔｏｇｒａｐｈｙ　ａｎｄ　Ｄａｔａ　Ｓｅｃｕｒｉｔｙ［Ｍ］．Ａｄｄｉｓｏｎ—Ｗｅｓｌｅｙ，　ｌ９８２．　［７］　Ｏｅｃｈｓｌｉｎ　Ｐ．Ｍａｋｉｎｇ　ａ　Ｆａｓｔｅｒ　ＣＤ＇ｐｔａｎａｌｙｔｉｃ　Ｔｉｍｅ—ｍｅｍｏ￣Ｔｒａｄｅ－ｏｆｆ　［Ｃ］／／Ｄａｎ　Ｂｏｎｅｈ．Ａｄｖａｎｃｅｓ　ｉｎ　Ｃｒｙｐｔｏｌｏｇｙ—ＣＲＹＰＴＯ　０３．Ｃａｌｉｆｏｒｎｉａ，　ＵＳＡ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，２００３：６１７—６３０．　［８］　Ｍｅｎｔｅｎｓ　Ｎ，Ｂａｔｉｎａ　Ｌ，Ｐｒｅｎｅｅｌ　Ｂ，ｅｔ　ａ１．Ｃｒａｃｋｉｎｇ　Ｕｎｉｘ　ｐａｓｓｗｏｒｄｓ　Ｕｓｉｎｇ　ＦＰＧＡ　ｐｌａｔｆｏｒｍｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｓｐｅｃｉａｌ　Ｐｕｒｐｏｓｅ　Ｈａｒｄｗａｒｅ　ｆｏｒ　Ａｔｔａｃｋｉｎｇ　Ｃ１７ｐｔｏｇｒａｐｈｉｃ　Ｓｙｓｔｅｍｓ　２００５，ＳＨＡＲＣＳ’０５．　［９］　Ｔｈｅｏｈａｒｏｕｌｉｓ　Ｋ，Ｐａｐａｅｆｓｔａｔｈｉｏｕ　Ｉ，Ｍａｎｉｆａｖａｓ　Ｃ．Ｉｍｐｌｅｍｅｎｔｉｎｇ　Ｒａｉｎ—　ｂｏｗ　Ｔａｂｌｅｓ　ｉｎ　Ｈｉｇｂ－－ｅｎｄ　ＦＰＧＡｓ　ｆｏｒ　Ｓｕｐｅｒ－－ｆａｓｔ　Ｐａｓｓｗｏｒｄ　Ｃｒａｃｋｉｎｇ　［Ｃ］／／２０１０　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　Ｆｉｅｌｄ　Ｐｒｏｇｒａｍｍａｂｌｅ　Ｌｏｇｉｃ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ．　［１０］　Ｃａｒｓｏｎ　Ｔ，Ｂａｋｅｒ　Ｄ．Ａｄｏｂｅ　Ａｃｒｏｂａｔ　ａｎｄ　ＰＤＦ　ｆｏｒ　Ａｒｃｈｉｔｅｃｔｕｒｅ，Ｅｎｇｉｎｅｅｒ—　ｉｎｇ，ａｎｄ　Ｃｏｎｓｔｒｕｃｔｉｏｎ［Ｍ］．Ｌｏｎｄｏｎ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，２００６：２０７．　Ｗａｒｎｏｃｋ，Ｊｏｈｎ．Ｔｈｅ　Ｃａｍｅｌｏｔ　Ｐｒｏｊｅｃｔ［ＯＬ］．１９９１．ｈｔｔｐ：／／ｗｗｗ．ｐｌａｎｅｔ—　ｐｄｆ．ｃｏｎｕ＇ｍａｉｎｐａｇｅ．ａｓｐ　ｗｅｂｐａｇｅｉｄ＝１　８５　１　［１２］　Ａｄｏｂｅ　Ｓｙｓｔｅｍ　Ｉｎｃｏｑ￣ｏｒａｔｅｄ．Ａｄｏｂｅ　Ｐｏｒｔａｂｌｅ　Ｄｏｃｕｍｅｎｔ　Ｆｏｒｍａｔ　Ｒｅ￣ｒ－　ｅｎｅｅ　Ｍａｎｕａｌ［Ｍ］．Ｖｅｒｓｉｏｎ　１．７，２００６．　［１３］　Ａｄｏｂｅ　Ｓｙｓｔｅｍｓ　Ｉｎｃｏｒｐｏｒａｔｅｄ．ＰＤＦ　Ｒｅｆｅｒｅｎｃｅ，Ｔｈｉｒｄ　Ｅｄｉｔｉｏｎ，Ａｄｏｂｅ　Ｐｏｔａｂｌｅ　Ｄｏｃｕｍｅｎｔ　Ｆｏｒｍａｔ　Ｖｅｒｓｉｏｎ　１．４［Ｍ］．Ａｍｅｒｉｃａｎ：Ａｄｄｉｓｏｎ－Ｗｅｓｌｅｙ，２００１．　［１４］　Ａｖｏｉｎｅ　Ｇ，Ｊｕｎｏｄ　Ｐ，Ｏｅｃｈｓｌｉｎ　Ｐ．Ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ　ａｎｄ　ｉｍｐｒｏｖｅｍｅｎｔ　ｏｆ　ｔｉｍｅ－ｍｅｍｏｒｙ　ｔｒａｄｅ—ｏｆｆ　ｂａｓｅｄ　ｏｎ　ｐｅｒｆｅｃｔ　ｔａｂｌｅｓ［Ｊ］．ＡＣＭ　Ｔｒａｎｓ．Ｉｎ—　ｏｆｍｒ．Ｓｙｓｔ．Ｓｅｃｕｒ．，２００８，１１（４）．　（上接第７０页）　因此成为近年来机器学习领域非常流行的评价指标之一。当两　个类别标签一一对应时，ＮＭＩ值达到最大值１。　将本文的算法（简记为ＫＬ）与以下９个算法相比较，它们　是：文献［２］提出的基于图划分算法的ＣＳＰＡ、ＨＧＰＡ、ＭＣＬＡ；文　献［３］提出的ＳＭＳＡ和ＳＧＴＡ；文献［４］提出的４个基于单连接、　全连接、组平均和Ｗａｒｄ的证据累积算法，为方便起见，分别简　记为ＥＡＳＩ　ＥＡＣＬ、ＥＡＡＬ和ＥＡＷＬ。　０３　它　盅　面０２　量　Ｚ　Ｏ１　ｏ．０　哺ｂｅｄｈ　ｒｅｖｉ￣　Ｉａ１２　打３１　ｂ＇４１　Ｄ毒￡ａｓｅｌ　图２聚类集成算法所获得的ＮＭＩ值　将１Ｏ个聚类集成算法分别在不同数据集上进行聚类，获得　的ＮＭＩ值如上图２所示。对于每个数据集，首先将每个文本根　据ＴＦ—ＩＤＦ（ｔｅｒｍ　ｆｒｅｑｕｅｎｃｙ—ｉｎｖｅｒｓｅ　ｄｏｃｕｍｅｎｔ　ｒｆｅｑｕｅｎｃｙ）加权，并对　生１５个聚类成员，Ｋ均值算法每次随机选取初值，并且采用余　弦函数计算文本之间的相似度。因为算法ＨＧＰＡ调用了ＨＭＥ—　¨　ＴＩＳ算法，而ＨＭＥＴＩＳ得到局部最优解，所以ＨＧＰＡ算法获得的　聚类结果不稳定，我们运行１０次取平均值；调用图划分算法　ＭＥＴＩＳ的ＣＳＰＡ和ＭＣＬＡ获得的结果稳定；层次聚类算法，谱聚　类算法和本文设计的算法都获得了稳定的结果。　我们可以根据图２作出以下几个比较：　（１）比较ＣＳＰＡ、ＨＧＰＡ和ＭＣＬＡ，ＣＳＰＡ都获得了最好的结　果，这与文献［２］的结论相符。（２）比较ＥＡＳＬ、ＥＡＣＬ、ＥＡＡＬ和　ＥＡＷＬ，ＥＡＡＬ和ＥＡＷＬ的聚类效果明显优于ＥＡＳＬ和ＥＡＣＬ，这　与文献［４］中的结论相符。（３）比较ＳＭＳＡ和ＳＧＴＡ，两个算法　在６组数据集上的ＮＭＩ值互有高低，这与文献［３］中的结论相　符。（４）与其他９个算法相比，除了在数据集ｌａ１２上获得了比　ＥＡＷＬ略低的ＮＭＩ值，ＫＬ都获得了最高的ＮＭＩ值。　４　结语　本文结合Ｋ均值与谱聚类设计了一种聚类集成算法，它充　分利用了聚类成员提供的属性信息与关系信息。为了有效降低　该算法的计算复杂度，本文通过代数变换方法有效避免了大规　模矩阵的特征值分解问题。在多组真实数据集上的实验结果表　明，本文的算法优于其他聚类集成算法。本文的方法为解决聚　类集成问题提供了一种新思路。　参考文　献　Ｔａｎ　Ｐ　Ｎ，Ｓｔｅｉｎｂａｃｈ　Ｍ，Ｋｕｍａｒ　Ｖ．Ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔｏ　ｄａｔａ　ｍｉｎｉｎｇ［Ｍ］．　ＭＡ，ＵＳＡ：Ａｄｄｉｓｏｎ—Ｗｅｓｌｅｙ　Ｌｏｎｇｍａｎ　Ｐｕｂｌｉｓｈｉｎｇ　Ｃｏ．，Ｉｎｃ．Ｂｏｓｔｏｎ，　２０１０．　［２］　Ｓｔｒｅｈｌ　Ａ．Ｇｈｏｓｈ　Ｊ．Ｃｌｕｓｔｅｒ　ｅｎｓｅｍｂｌｅｓ－ａ　ｋｎｏｗｌｅｄｇｅ　ｒｅｕｓｅ　ｆｒａｍｅｗｏｒｋ　ｆｏｒ　ｃｏｍｂｉｎｉｎｇ　ｐａｒｔｉｔｉｏｎｉｎｇｓ［Ｊ］．Ｔｈｅ　Ｊｏｕｒｎａｌ　ｏｆ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ　Ｒｅ—　ｓｅａｒｃｈ，２００２，３：５８３—６１７．　［３］　徐森，卢志茂，顾国昌．使用谱算法解决文本聚类集成问题［Ｊ］．　通信学报，２０１０　３１（６）：５８～６６．　［４］　Ｆｒｅｄ　Ａ，Ｌｏｕｒｅｎｇｏ　Ａ．Ｃｌｕｓｔｅｒ　ｅｎｓｅｍｂｌｅ　ｍｅｔｈｏｄｓ：ｆｒｏｍ　ｓｉｎｇｌｅ　ｃｌｕｓｔｅｒ－　ｉｎｇｓ　ｔｏ　ｃｏｍｂｉｎｅｄ　ｓｏｌｕｔｉｏｎｓ［Ｍ］．Ｓｕｐｅｒｖｉｓｅｄ　ａｎｄ　Ｕｎｓｕｐｅｒｖｉｓｅｄ　Ｅｎｓｅｍ—　ｂｌｅ　Ｍｅｔｈｏｄｓ　ａｎｄ　ｔｈｅｉｒ　Ａｐｐｌｉｃａｔｉｏｎｓ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２００８：３—３０．　［５］　Ｆｅｒｎ　Ｘ　Ｚ，ＢｒＱｄｌｅｙ　Ｃ　Ｅ．Ｓｏｌｖｉｎｇ　ｃｌｕｓｔｅｒ　ｅｎｓｅｍｂｌｅ　ｐｒｏｂｌｅｍｓ　ｂｙ　ｂｉｐａｒｔｉｔｅ　ｇｒａｐｈ　ｐａｔｒｉｔｉｏｎｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　２０ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ　Ｂａｎｆｆ，Ｃａｎａｄａ，２００４．　［６］　唐伟，周志华．基于Ｂａｇｇｉｎｇ的选择性聚类集成［Ｊ］．软件学报，　２００５，１６（４）：４９６—５０２．　［７］　Ｓｅｖｉｌｌａｎｏ　Ｘ，Ａｌｉａｓ　Ｆ，Ｓｏｅｏｒ６Ｊ　Ｃ．ＢｏｒｄａＣｏｎｓｅｎｓｕｓ：ａ　ｎｅｗ　ｃｏｎｓｅｎｓｕｓ　ｆｕｎｃｔｉｏｎ　ｆｏｒ　ｓｏｆｔ　ｃｌｕｓｔｅｒ　ｅｎｓｅｍｂｌｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　３０ｔｈ　ａｎｎａ—　ａｌ　ｉｎｔｅｒｎａｔｉｏｎａｌ　ＡＣＭ　ＳＩＧＩＲ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ．２００７　７４３—７４４．　［８］　王红军，李志蜀，成飚，等．基于隐含变量的聚类集成模型［Ｊ］．　软件学报，２００９，２０（４）：８２５—８３３．　［９］　Ｗａｎｇ　Ｆ，Ｄｉｎｇ　Ｃ，Ｌｉ　Ｔ．Ｉｎｔｅｇｒａｔｅｄ　ＫＬ（Ｋ—ｍｅａｎｓ－Ｌａｐｌａｅｉａｎ）Ｃｌｕｓｔｅ—　ｉｒｎｇ：Ａ　Ｎｅｗ　Ｃｌｕｓｔｅｒｉｎｇ　Ａｐｐｒｏａｃｈ　ｂｙ　Ｃｏｍｂｉｎｉｎｇ　Ａｔｔｉｒｂｕｔｅ　Ｄａｔａ　ａｎｄ　Ｐａｉｒｗｉｓｅ　Ｒｅｌａｔｉｏｎｓ［ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　２００９　ＳＩＡＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎ—　ｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｓｐａｒｋｓ，Ｕｎｉｔｅｄ　Ｓｔａｔｅｓ．２００９：３８—４８．