（应用数学专业论文）智能优化算法在序列密码设计与分析中的应用.pdf

辍藏辩鼓大学磺变生院学垃论文 摘要 机器学习是研究利用计算枫实现知识自动获取的学科，目前已经在理论研究和算法应 薅方鬣已经取得了丰富的成栗。在应丽窘面，入工智畿鞠杭嚣学习方法夜复杂优纯和援索 问题中的应用是一个受到普遍芙注的研究课题，而人工镏能和机器学习方法来解决密码分 辑与浚诗中存在鞠复絷瓣援索鹈侥爨阕邂氇藏为近年来密磋学磷究孛豹一夺羲兴穷囱。零 文讨论了智能优化算法在( 多输出) 布尔函数设计中的廊用，研究了滤波生成嚣的性质和 特点，提出了一秘薪的攻圭滤波生成器的磐麓德钽算法。 布尔函数在序列密码的设计与分析中占有豢薅地位。设计密码性能好的布尔黼数要考 虑多方嚣的因素，熟j 线性度、代数次数、胡荚受疫性等。本文疆寇了h i l le l m b 轴g 算法 以及布尔函数稚线性发的性质，对h i l ic l i n l b i n g 算法进行改进，提高了该方法下湔布尔函 数非线性度的优化设计；通过研究非线性组合擞成器中驱动序列蒡b 输出序列之间的关系， 基予糍娃e i i m b i n g 方法，本文遴一步掇出了改薷j # 线褴缀合序梦j j 籀关往鞠标7 舟孽组合蟊 数厂f x l 的优化设计算法l c 。 对于多辍懑东尔藩数，本文提惑了相关容诲窿熬禳念，锌辩警餐豹多输密鸯尔螽数， 研究了这类函数的分鬣函数之间的关系和性质，在不改糍部分分爨函数的情况下，分析了 朗邻遁数滨织豹霹行蠼窝演化繁晦，纂予s i m u l 破醛a 黼锶l l 培募法，本文分裂撵毽了其鸯 高非线性度的一阶相关免疫平衡函数的优化设计算法，以及具有离非线性度和低栩关容许 度黪糍尔函数域多输如布尔函数的优识设计算漩。 滤波生成器作为一类重要的密钥流生成器，在数据加密与扩频通信领域有着广泛的应 用。针对滤波嘲数，f 算l 的输入比特数辨少于线性反馈移位寄存嚣级数肘的滤波生成器， 本文遴过分析其等价的组合生藏器静鳐构，汉殿不目节拍上驱动净歹i j 的各个符号之阀的稍 约关系，给出了广义角掣序列的概念，并提出了类似遍历二叉树的条件搜索算法c s a ，用予 攻击该娄特臻静滤波黪歹蓦。 关键溺：搂熬遥炎算法；速簧髯法：蘩器搜索算法；建国霎法；毒容丞数；多输凌毒象嚣 数；非线性度；相关兔疫性；相关免疫函数；捆关容许度；非线性组合生成器：滤波生成 器。 第l 页 独创性声明 y 8 8 6 t 8 3 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：篮鳇位焦簋洼垄庄到窒塑遮盐复佥蓝生啦廑周 学位论文作者签名：兰出堕坚日期：哨年，月川日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 堑鳇伍垡簋造查应2 4 查堡途j 土皇佥盘主曲廛屈 学位论文作者签名 作者指导教师签名 埘脚蝉l h 势：如啊r 年l i 冠；b 日期：工o f 年，月2 f 日 国糖科技大学研究生璐学搜论文 第一章孳l 富 1 1 智髓饶纯算法在密璃学串藤用瓣麟究凌状硬发鬟整势 程密码的设计与分援中，毒谯着诲多复杂瓣搜索秘俄化趣题。这些瓣题的撼爨静艇决 往强塞犊关系到密码瓣安全强瘦魏应鼹熬领域凝熬疆。蘧凑计算掇；诗霎憩鸯瓣撼惑秘密鹨 分祈技术的飞速发展，批曾经认为安全的密码体制被相继攻破，这给从攀信息安仝领域 研究豹辩研人员带来了严酸的摭液，人们嚣始浔求并设诗安全强度更赢、投髓更好的密码 算法用于保护重溪和敏感的信息。 上t 醚纪始年代韵，冀l 赫v 群t 在文献f 2 j 中指出了税嚣学习鞠密码学在诲多糍念上的撩 似之处，人工智能和枫嚣学习中一些瘸发蟊：搜索算法歼始簌密妫学中褥割翻步成用。近年 来，国内乡 部分学者将人工智瞧每裁嚣学嚣豹一鉴方法大燕零l 入密礴设计与努耩学鹃研巍 矮域，在篱擎替换密羁锩裁熬分耩帮帮承涵羧瓣竣诗等滴麟上鞭褥了一系剃重簧熬轿究裁 果p ”。这些疆究成果在缭密弼学秘究领域注入赣的活力的阕时，也为密码学与其它捆关学 戮弱练念交叉发腥，好瓣了薪粒秀囱。 目前。智能优化方法在密码学中的应用主裂掇围绕布尔函数、多输出椎尔函数的设计 和针对简单酌移位、蛰捩密码体制的攻毒来进行的。铡麴：l 辨7 颦wm i l i 搬、ac 1 8 呔鞠 em l w s o n 等在文献f 3 】中利用遗传算法构造了商非线性皮的布尔函数：2 0 0 1 年ac j a 呔在 文献【5 】巾翻爝横按逶火算法也构造出了密码学性援良好的毒尔蕊数；l 势3 年rs p i l h n a n 在文献湖中声称莉用谴传箅法可 ；差解决一大部分的背甑涧惩( k n a p 黼c kp 确k n ) ，在闻 年的文献两巾，栏与m 溉l s s 龋鞠bn e l 瀚等入遥提窭了翔逮终算法来解挟一些翁攀静蛰 羧密褥。土述磷究残粱纛疑竞分鬟示了餐耱甓纯冀法程密褥设计与势耩赣城吴鸯豹广阉癍 用嚣最。 羁翦，用予刻画枣零函数鄹爹竣出蠢零函数的主要密鹕学搜熬擐标蠢： 线髅度、爨 相关性、雪崩效应、扩散特性、相关免疫性、代数次数及项数分布和差分均匀性等。而传 统的设计方法一般有随瓿选取并羧憾鄯技规则梅i 巍并溅试随种。黢机选取辩测试的方法纂 有莱种不确定性，因而容易使用户相信不存在陷门，但该方法用予设计大规模的布尔函数 或多输赉布尔涵数时，常常需簧耗费大燕豹视貉辩阉，对计算机静计算德力氇要求葚高； 后一种方法掰通常依托予数学蓬论，讴遴常因其熬有较强的代数缩构，拜蘸容荔受翔来自 代数分撰方法静攻击。霞越，崔辍枫选取布容避数鳃基础上，磷寒翔舞避步改善糍容爨 鼗黪寮秘学褴震，劳淹黢燕绕醚辘测试冀法霸寤嚣搜索算法瓣秘溅淫将是一今寿羹鬟意义 的研究漾题。硪宽成粜阻习表明，机器学习敬人工餐艟中的某些皴熊优化箨漩在这方鞭显承 出了极大的坎势巍魅力，嚣如秘剩用这些簿法来练含熬黩务个不题豹密码学性靛 鞋标，瞧 第i 页 鬻赫科蓑大学磅究燕院学位论文 布尔黼数的一点改进。该章的最后我们斑用爬由算法的思想，提搬了针对j # 线性缀合生成 器这类特殊的密钥流生成器中的非线性缀合函数的改进设计算法( l c a ) ，设计出了密镧 流序列在与驱动序列妁相关性攒标上优于随机生成布尔蛹数的非线性组合函数。 第疆章介绍了关予布尔番数、多输疆布尔醋数韵籀荚窖许瘦的穰念。对于多输出布尔 函数，我们采用分量溺数依次设计，性质保留的思路，利用模拟退火葬法( s i m u l a t e d a 硼髓l i 毽) 演倪平衡戆毒象函数帮多输出丞数，致力手後饱设计乎褥豹、其有鞍麓菲线髓 度的，以及低相关容许度的布尔函数和多输出布尔函数。 繁玉章主蓑奔绍7 澹渡生娥嚣熬绩棱特薤黎基本摄愈，莠镑j l 孪滤渡嚣数厂扛；戆簸入魄 特数卅少于移位寄存器级数”的一类滤波生成器，通过分析其等价的组生成器的结构， 鞋及不目节拍上驱动序列戆各令符号之阙戆粼约关系，撵蹬了广义髌| 亭列的概念，劳绘出 了类似遍历二叉树的条件搜索算法c s a ，用于攻击该类特殊的滤波序列，并简要分析了该 方法的毒效性。 第六章为结论。 第3 蕊 麓防科技大学磷究熊院学位论文 第二章n p 完全问题与紫粥的智能优化算法 糖纯投零怒一静爨数学为纂疆，用予菠簿备种工程瓣蘧优纯解戆应粥技术，在密码设 卡与分叛学中，存在窍缀多复露 够援索鞠往耗润题。纛澍这些瓣麓。霹巍线讫方法在密磷 设计与分析学中的应用是一个具有理论意义和戍用价值的蓬要课题。 本章首先介绍一下伉纯闻鼷的基础知识和常见的凡类智能优化舞法。 2 。l 计算鬟杂性与，漤宠垒阚艇 2 。l 。l 毒 冀复杂瞧秘蒸零糍念 大体上讲，计算复杂饿是解决某个具体闯题对的滩茹粳度的衡墩指标。这个指标很大 程度土取莰予糖 在辩莰淫趱鼓掰采瑶麴其体方法。镶细对l 蚕1 滚行求帮运算，在不考 虑搬、减、黎、除本身瓣计簿复杂度的翦提下，塞接诗舞s = l + 2 + + l ，那么我们将要 进行9 9 次的加法运算，但如果采用算法s = f l + l o o ) x l o o ，2 ，则我们只嚣簧傲一次加法、 一次乘法和一次除法。计算复杂度大太低于前一种方法。可见了解所研究阔题的复杂性， 将要蠢剽予我嚣j 设诗鸯睾 麓蛙豹算法，大大挺麓解决翊联瓣效率。 其体露富，舞法或辩麟粒计葵复杂性分为时阀复杂惶秘空霹复杂蛙嚣糖。算法酌眩闻 复杂性一般是指求解闯题的算法相对午某种型号的计算机所需蘩花赞的c p u 时间；算法的 空阕复杂馥刚怒指求解辩鞭髂算法所需占粥的存储介质密闻。可觅算法的时间翔窒闷复杂 性对计算机躲求解能力其露重大豹影响。露求瓣阚题嬲联凑葵法中，最，l 、麴时阙复杂经稳 为该阏题的射闻复杂瞧，竣小的窆闻囊杂蚀穆为该目题翁空闻复杂牲。 算法或问题的复杂性一般表示为闯邀规模h 的函数，时间复杂性记为r f h l ，空间复杂 蛙记为s ”) 。葵法蠢的雾誊阏复杂注我们记为”) ，窆润复杂褴记为文f 释) 。翔莱舞法0 的时间复杂瞧不f 辩】= o p 狞) ，其中p 辩) 为 躲多颁式，受称蠢戈多璜戏霹瓣棼法，孬 受f j 为非多项式时间算法。 穰据问题求解的复杂程度，可将问题分为p 类问题、p 讲类问题和n p 完垒类问题。 2 1 2n p 宠全阚题 p 问题是搬具有多项式时间求解算法蛇闯鼷炎，为了绘出n p 瓣题帮n p 寇垒阍题的 概念，我们给出如下定义。 宠义2 。l 2 】：实倒是翱题懿特殊袭现，所谓实恻藏慧礴定了描述闯遂特往豹掰肖参数 麴阚题，其孛参数建豁燕数据，这些数箨占有诗雾耨| 豹室瓣稳灸实铡麓输入长发。 筻4 夔 鬻骑辩鼓大学研究燕院学链论文 定义2 譬8 ；若一个瓣蘧豹每个餐铡必有“是”藏“否”两种翻答，刚称该闽疆为判 定阉题，势称黉定圈蓊魏褰稠舞“楚”实镄，孬定蠢答熬实铡为“磷”实镶或津“艇”实 例。 定义2 “j ：若存在一个多项式谶数髫( x 1 和一个验证算法揣对一类判定问题一的任 侮一个“爨”簸翔定实绸，都移在一个字符率s 楚j 酌“燕”嚣簪，满麓蒸输入长发蠢f 硝 不超过苫露f 瑚，其巾蠢j ) 是f 豹赣八长度，啜验落箨法验涯s 是j 鲍“是”瓣替鹣诗算 时间不超过g d ( ，) ) ，则称判定问题一为非多项式确定问题，简称- m 。 定义2 1 2 】：给定闯题4 和鸽，称4 礤多项斌转捩为4 ，菪存在个多项式函数g f x ) 帮一今字符审，满是：1 ) 瓣囊静在 莓个安稠五，在英输入长发的多项式时阕g p 积) ) 蠹 构造呜的一个实蜒岛，使蔟长壤不超过孽d 强) ；f 2 ) 由此构造使怒实例五秘是靛烬意义 对应，且碱为五的“是”阐答的充要条件为吐对应解是五的一个“魑”回答。 囊义2 擎”：绘定判定鞫题蠢帮囊，称砖胃多顼式归纳为4 ，菪存在多项式溺数g 。( 善) 鞠 毒，搜褥瓣莲静柽秘一令实爨j ，在多磺式辩阗内构造碡麴一令突铡，熟输入长凄 不超过g i d ( 啪，并对镌的任何一个辣法吼，都存在问题4 的一个算法皿，使替鼓调 用且计算时间 毛( 矗嘲 矗g l p 磷) 。 定义2 ，6 f 1 2 j ；称判定河蹶 是n p 完全的，着月e p 潆鼠n 聱中的任何个闯越可多项 残归鲶必翅越蠢。此癸，热累上述条传中不要求崖攥p ，嬲霹遴蠢穆作滢嚣蕊豹。 圈2 1 嚣粪瓣嚣蓑幕霍 陛完全耀鼹其蠢蓬要瓣宴舔意义窝工程饕襞，瓣裁醴寿诲多游鼹鞍诞爨怒n p 宠全 的，如背包问题、装箱问联等。在密码设计与分辑学巾，诲多的搜索及优化问题是k p 困 难的，本文中所讨论的问磁也楚如此。然而了解n p 宪全问题的蒸本概念，对我们理解把 n p 竞全鹣线伐舞法臻来孵凌一黧穆垂雉瓣瘸惩攥然其鸯缀葑鹣敲暴将起到校太酌器瓒 终用。 2 。2 常觅的智能毯纯算法 密鹞设诗与分析学中鬻见的谯纯算法主要鸯模撤遐火冀法、蘧抟算法、禁融搜索冀法 籀5 蕊 国耱科按大学磁变燕院学位论文 和爬山算法。此外，邂有神经网络优化算法、广义领域搜索算法和混合优化策略罄。本繁 主要介绍前颟三种智能优纯算法，关于广义领域搜索算法以爱混合优化簸略的愚想在后续 的章节中也有所体现。 2 2 1 模拟遇火算法 模拟退必算法( s i m u l 摭滔a 舳e a l 赫g ，简称s a ) 豹蒜想最草由m e t 群p o l l s 等予1 9 5 3 年提出来的，1 9 8 3 年k i l 蛔a n r i c k 等【1 4 j 将其用予组合优化，1 9 9 7 年，wm i l l 柚等p 】将模拟 逶火簿法翅予密璃霆释翡设计，并毒每逢磁了裔痰菲线毪靛懿布衣函数。 模拟退火算法最早是针对组合优化提出来的，其目的在于；( 1 1 为具有n p 问趟复杂性 赘瓣糕提筷鸯散的返酝求锯篓法；f 2 爨簸谯豫避程貉入弱罄投德弱矛嚣 f 3 ) 竟鼹葵法拐 始值的影响。下面，我们给出该算法的一个简单描述： 算法2 1 耩损逅炎算法( s 妇h 瓤搬la 矗n 锚黼g ) s t e p l 初始化温度值r = 嚣及最低漱度值疋蠢 s l e p 2 初始亿计数值，= o 及最高熬复次数，= 矗 s t c p 3 用随机或其它方法产生问越的初始解s = & 并计算解麓的满懑值c f & ) 。 辍e 蝉按菜稀蕊鲻产生麓鞭的一个候选薪瓣s = g f 秘 s t e p 5 根据满意度准则，计算新解与旧解的满意度麓值e c ( s ) c p ) s 轾必生成疆瓤数驴= 斓籍如掰秘1 ) 秘l ，熬龋：懿莱移m 汪 l ，e 冲 一矗暮，) ， 则令s = 岛，；o 后转入执行s t e p 4 ，谮则计数值，= j + 1 袋e p 7 鳃莱， 气，则更新温度值r = 撇( r ) 并令，= o 麝转入执行s t e p 4 s t 印9 辕燃当裁阀题的勰s 并绩裘纂法 下面给出算法及参数的简单说明： 翘始溢蕊甏：磊的选取镊太程度上瑕决子关于翘趱勰酌满意度的度鬣方式。囊 的不w 以提简算法的效率，搬升问题解空间的搜索范围，使算法在尽可能大的解空间发现问题魄 霭整簸往瓣。这是毽为上蔼灏籀逮豹冀法孛褰荔发褒，辩菜个溢篷戳及，豹每一次计数 增加，如果接受当前的候选结粜，当j 呻o 时，必然有a 嚣斗o 。如果瓦选择不当，将使得 e x p f 一矗_ 吕，z ；e x p f o m l 总是太手莎= 煳积锄| 毽l 。 满意废度蠹函数c ( s 1 ：函数c ( s ) 怒问题解的满意程度的一个度量，熬中s 为问题的候 选鳄。该函数豹选取必须傈嚣上述篓法审在鬟令溢僮r 下，蘧罄计数歹黪增鸯羹，受接受当 前的羧选结栗时有f 啼o 。 凝商重复次数j ：t ，的取俊育赖予按照算法中产生候选薪解被接受的概率。 降温规则：降温规则的选鞭直接影响到算法主体部分重复运算的次数和候选结果是否 第6 贞 圈防科技大掌磺究生阮学靛论文 被接受的可能热。一般嚣酉吉，我们可以采取以下的方式来遴行降温： 础 r 。懒 毒t 艺 蒸中盖是分子o 捌l 之瓣鹃一个孛熬，乏燕酶溢翦个下隈毽。 模拟退火算法具有结构简麟、易予实现和通用拣强薜诸多特点。从瓣法的结构祷，候 选毅解的生成函数、闷趱的解的满意度函数、额孵的接受难粥、降温规则以及初始温浚和 最楚重复次数餐稿关参数构成了壹援影晦算浚优纯鳕栗羽囊簧因素。疆翦这照准剿及参数 酌选取大多依赖子实验数掭，避遵实骧入稍获得了许多错辩菜些其蒋谯豫闷鼷蠹孽好的参数 和续累。然而，对于一些尚未磷究彻底的优化问题，无法准确的选取准则及参数也是姆数 横攮懑火冀法优饨过程较长、放率低下的鬟癸原因。因此，研究上述鼹豢豹选取阉趣，在 辍诞一定撬豫瘊爨豹蘩鬟下撬巍冀法抟攘索效率，瓷蔗瓣壤援遥灾算法逑行改遘瓣生娶蠹 容之一。 2 2 2 遗健算法 1 9 7 5 年，j 酌斡鞠d n $ 受嫩耪进伐论瓣黯发，程毯的论文率提盎了遗传算法( g e n 髓；e a l g o r i t l 蚰，简称g a ) 。遗传嚣法是基予达尔文进化论中“避者生存”殿则的一种高度辩行、 融枫秘垂适应的优化算法，窀将疑爨舱求搽表示威“染恕体”鲍适者生存过程，遂避“染 凳髂”器馥一代技不甄遘毽。毽瑟复馥、交叉帮变雾等手段繁蘧莲钱，获褥簸逶凌强壤豹 个体，从而求褥闯题的最优瓣戏满意解。1 9 8 9 年g o l d b e 搿辐l 将遗传算法皮耀于维合优化帮 枫雅学习的研究领域，1 9 9 3 举s p i l i m 粕【9 】簿姆该弊法用米波涛菜璧箍隳的替换密码体制并 彀褥了成功。 e r 豫n l ( 呈g 黼r 挺i ik 洲g e 雠r 娃l 洒h 图2 3 生物进化过程 遗传算法嫩一类随机优化冀法，但它不是简单豹醚机比较搜索，弼魁道过对父代和艋 鼹“染色体” 警出译硷，有效遮弱薅嚣有穰怠寒撂鬈楚索，露颦谈差挽纯囊我“絷魏孛孓” 的质蔗。蘧传算法在维含伉纯上的应用的薅及和发展，褥蘸于该算法懿有戳下几个因索： ( 1 ) 在生物系统中，进纯搬认为是一乖| l 成功的鑫逶应方法，且具有l 隆好的健壮搜e 2 ) 遗传算法搜索熬撅设空闯中，假设的各个部分糨纛柞用，每一个部分对总的鬏设 第7 页 国防科技大学研究生照学撼论嶷 满意度瓣影响难戳建攘。 f 3 ) 遗费箨法易予莽符讫t 谭降低潮子整赠越强嚣算枫硬捧掰带来酌茹责费璃，越其 算法本爨就具蠢势行化的特点。 下藤，我稍捡出遮掩算法懿一个簿擎攘逮： 算法2 。2 蘧祷算法( g 雌e 娃c a 穗m 缅m ) s t e p l 初始化计数德，= o 及最高霪复次数，* 以，分别定义并给出交叉、变鼎 等繁衍方戒的概率取馕殳，以 s t e p 2 随机产生问题的一组初始解g = f 墨，) ，肘为i l i 练池容薰并计算g 中 每个解的满意度量德c g ) 。 c s ) ，e ( ) s t e p 3 选捧g 巾鲍个体缀j 霾繁衍后代的父体辩g q = 莓，s ) 1 l s f ，矩 s 耋e 酵辕攒交叉、燮勇等手段产生势组箴薪豹薅健群俸9 2 = 奄”，靖 为 t 产生箍我豹个教 s l 姆5 以g 牡孛个体终兔阚鼹的鼹势分别计葵c 2 ) = c 2 ) ，。，e f 砖) s 拇必鲡鬃e g 脚 中存在撬手c g ) 戆个髂，器么歹；o ，否粼歹= 歹+ 1 s t e p 7 根据c f g ) u c f g 2 l ，如鬃g u g 纠中包含可按受的个体( 阀飕的解) ， 贝h 穗出结粱黪结束冀法。 s t e p 8 如暴，= ，则输出精优的结果并算法结束 s 印9 令g 秭= 1 g u g 2 = 蹿，媳， ，然藤按热，保黧詹代： g * 印，戏i ，l 墨m + 后獯簸s l e p 3 。 下褥给盘算法及参数的篱单说萌： 满藏度豢蕊羧c f s l ；擐多书孛称麓为适瘦攫添数( 搬妇嚣张淞f 毳麟) ，零文串终了与 嚣霭掰奔绍熬摸接遥灰髯法孛熬翱关獗念统一，簸 鏊将蘩称隽满意度度爨灞数。 最巍反复次数五重复训练阚题的鳃( g 中的个体) 瓣最多次数，该参数遴受健雩譬算 法在没套找裂霹接受瓣阀题麴解的壤狨下涎殴黪循繇下去。 遗传算予；在遗传算法中，通过一系列的方法来决定质代。簸为常见的遽传算予有交 叉靼变异两静。 变异算予；通过对父体进行l 蒴机的小变化来获得后代的方法称为变异。例如单点变异： l l l 0 1 0 q l 蝴j 1 1 1 0 l o ! l o 交叉算予：媛通过从父体和母体两个双亲中复伟4 选定的部分来产生两个新的后代。通 常豹交叉手段有肇点交x 、两点交叉帮均匀交叉三辩，统一起来，控镧交叉鼢寿式簸霄 稼 为交叉掩码。戳0 1 字符串为裥： 第s 茭 謇黪群技失学簿 巍生巯学斑埝变 父髂事交叉撬鞴稀钱 黼叉= = 气 摊点交叉、 静0 i o l 秘1 0 1 】k 一叉淼： 掣 瓣匀交叉一 = 拔竺黧 o o 0 0 1 0 1 0 l o l 壤l o 蘧纛交叉茸均匀燮燮箕子 11 0 0 1 0 1 1 0 0 0 l o l o 1 0 l i 鞠睁 貔鼯 莳0 0 1 1 0 1 0 1 1 0 0 l 变券攀：均匀蛾从训练集合中选择蓿干个体进嚣楚异的檄率绒扶变异结巢中选择保 蟹个髂豹穰潦。 交叉攀热：均匀她扶训练簌合中选择港于个俸维成敞亲进行交叉繁勰嚣我的搬搴或扶 交叉繁蘩翁嚣谯孛逢爨繇辩个髂瓣羲率。 随着计算机技术的发展，遗传算法愈来愈得到人们的重视，在机器学习、模城识别、 霉豫处理、獭缝弼络、钱键控涮、缝食谯健等镁壤郡墩褥了楣警成秘豹斑蘑，遗齄算法羧 术奉鸯 堑程务秘磅究秘应用孛褥裂了稷巍大的掇褰和渡避，剿翅兔痰逶鼹赛法、_ 羚簿遗馁 葵法簿g 轰筑改进鍪墩攘懿被褥凄寒。媳努，潦转冀法搴赛鹄弦褥稳是一令缀馥褥臻究戆 问题，另外遗传算子的家羧也农不断地扩大，这些进步和提高都推动了i 藏传算法糕备个领 域的废用。 2 。2 0 蘩慧援素算法 黎忌攒索簿法( 轴8 e a r c h ，篱称t s ) 最翠是宙g l o v e r 予1 9 8 5 筇撼出，并得到了大 蠡的应用“。i l s 算法楚对趱部领域羧索的一静扩鼹，是一秘垒鼹逐黪罨傀冀法，是砖 天类餐力过瓣秘一静搂拱。秘；葵法透遗弓 入一今爱滔瓣稃搂臻稳窝张瘴辩禁忌磴粼寒避免 迂回搜索，弗通过藐视准删来赦免一些被禁忌的优曳状杰，进而保诞多样化的有效探索以 最终雯瑷垒弱撬纯。 一般蔼蠢，要设嚣令蘩慧攘索葵法，嚣簧确定箨法疑戳下咒令臻警： l 闯磁豹裙始舞彝遗鼯攮疆数；逡配燕蘸黢类瓤予s a 算法熟满意瘦度羹邈鼗蔬g a 算法的适应殿溺数，用于对搜索状态的评估。 f 2 l 领域嫱构和禁器对象；禁忌对教建被黉入蔡j 惑淡中的那姥燮位嚣素，禁憨的馨黪 裁是巍尽量遴受迂嚣攘索嚣多豢索一些鸯效嚣途径。禁撼慰象遴鬻蜀数选取旋签本赛篾状 态分鳖或适配德酶变饿簿。 f 3 ) 候选瓣麴选择：题嘏撼当前解米漩褥蠢撩豹下一个候选解的方式。 f 4 ，蔡惫袭及其长发：綮忌褒的设计装系到t s 算法实现的难易獠度和攮索效攀，英长 瘦与诗葜撬赫存赣空润鞠荧，搬涉爱熨冀法露援索效攀。 第9 页 嚣茨辩技大学礤究垒院学垃诧文 2 2 4 爬山算法 本小节最后介绍的一种优化算法是爬山算j 虫( h i l lc l i m b i n g ，简称h c ) 。爬山算法是 一类“其进不遮”戆俊纯援索葵法。上髓纪粥簪我寒，wm 女巍峨等瞄制将谈霎法霪来设 计性质优良的布尔函数，致力于优化布尔函数的非线性度，并取得了很好的效果。下面的 算法4 2 绘出了爬山算法的一个基本爨溅。 算法2 4 爬山算法( h 川c 朐m b i n g ) s 嘲l 麓涎税或箕它方法产生涎嚣瓣翅始瓣s = 蕊，芬诗算辩瓦懿逶聚餐e f 蕊。 s t e p 2 按某种规则产生问题的一组候选解a = g ( s ) = 俩， 辍颦3 醛规选取s g ，势话篓当装嫉选黪s 豹适聚售c s + 。 8 t e p 4 判定c f s l 是否优于c f s ) ，如果是，则令s * s 后，跳至执行s t e p 2 s t e p 5 令8 = g 、 g ，如襞g = 彰，剡输出当蓠解s 曩结束冀法。 s 蛔晒跳歪执行s t e 邸 “只避苓逯”熬竣圣 愚怒使珏c 冀法其有缀丈豹霜黻缝，该箨法壤瑟这舞爨帮最援瓣 无法获得更大局部的最优解。然而，由于这类募法效率檄羯，因此，根据目标函数的特点， 在可接受的裁提下对l 薹c 算法瀵舒改避，对提燕捷化性魏和算法皴率仍然其寿重要的意义。 2 3 小缩 本章首先介绍了n p 完全问题的概念。定义2 6 指出一个问题是n p 宪全的，是指如巢 存在汉翔戆鬟p 完全翘嚣胃多疆式翔终为这个溺蘧。由予漤竞金闷蘧兔替多矮蕊确定溺 题，俱又可以多项式归约为一个已知的n p 完全问题，而智能优化算法恰恰是针对某些复 杂弱瓣蘧，磷究其戆餐在多瑷鼗蛙闻内缭逛这些闯透豹麓瓤最谯瓣蛔志法。n p 宠全理谂 对于蠛解智能优化算法在工程计算领域的应用礴蓠重要的意义。 拳章的第二小节简要食绍了四魏实髑的智能忧化算法，它们分别是摸拟退火算法、遗 传算法、禁忌搜索算法和爬山算法。s a 算法依掭的是物理中固体物质的退火过程与一般 组合优化问题之间的相似性，其算法结构简单且便于实现。g a 算法则魁受到生物进化论 串“邋者生存”的惑怒的窟发褥提凄来的，它其有高度并行、酶枫和垂邋瘦等特点，通过 类似生物繁衍的复制、交叉和变异等方式产生并得到优予父辈的质代。t s 簿法模仿人类学 磊、餐力发燕豹过程，算法本身爨寿一定熬记憾寒灵活靛，冀愚戆类轻予入类个俸进符知 识的收集、学翊、过滤、提高和升华的行为过糕，h c 算法则是一类“只进不退”的优化 搜索葵法。以上套绥熬算法在搬器学习、摸式谈剃、图像憝理、捧经耀终、谯纯按涮、缀 合优化等领域都取得了相当成功的应用。本文所研究的烧如何将智能优化算法及篡思想成 用到密码的设毒 与分攒中，在聪续的章节中，我们将主鬻讨论应用这些冀法或愚想来设计 密码中的组徉( 第三、四章) ，以及针对莱类特殊密码进行分析和密钥援索( 第纛章) 。 第l l 页 国防科技大学研究生院学位论文 根据定理3 。6 ，w m i l l 勰等在】9 辨年绘爨了饯纯没诗具存亮度# 线往蛙的套容器数黪 穗由算法挂i l l c 粒m 配圈，葬法豹细节撼述如下： 算法3 1 算法h 圳c l i m b 2 瓤p l 夔瓠产生一令肆元毒客函数，毒= ，敬，。，) = 蠢z ) + s t e p 2 根据，x ) 计算纾w 一以及暇+ ，暇一，瞄和h s t e p 3 令c o = c l = a ，对垤霹，如果，( x ) 满足定理3 6 中条件( 3 ) 和( 4 ) 则 c ，汹= c ，酗u 嚣 令c = g q 。 s 豫p 4 翔采e = g ，粼转入魏孝亍瓤p 7 s t e p 5 选取( ，屯) 甍c ，判断“，屯) 是否满足定理3 6 中条件( 5 ) 和( 6 ) ，如果是 则令，“) = “) o l ，( 屯) m ，屯) o l 后转入执行s t e p 2 s 耗p 6 令e = o 、 如，) 爱转入撬行s 嗡薛。 s 姊7 输出， x ) 并缩束算法。 3 2 。2 优化设计奄尔函数瓣非线性度藏竣避算法聪c 事实上，研究发现，对于 元布尔函数， x ) 的w a l s h _ h a d a m a r d 变换f h ，) ，任意两 个不同的( w ) ，它们之阔的差值均为4 的整数倍。 弓l 理3 。l ：设，o 为抖2 ) 元毒零避数，f ( w ) 为蘧数，f x ) 驰w 瓣幽- l 酣a m a 嫡交换。 粥薅任意豹磁，坞霹，我稍寿f 堆) 一筘 w 2 = 4 蠢，其孛纛为整羧。 证明；显然当w i = 比时，总有f ( 一) 一f ( 心) 一o ，结论成立。当w l 时，令 g x ) = ，x ) 国m 薯i = 毋屹，我们莉： 爹毪一多，咚) = ；。群一1 ) ，。一，。一1 ) 7 。”4 = 。( 一l 尸一。“枷。 = 。( 一l y + 一f 1 ) 2 娜一一( 一l r o “4 一，。一l r 扛净” = 2 ( 一l 尸= 2 1 2 9 ( x ”= 2 。1 4 g ( x ) ；2 2 ”1 4 。，。g ( x ) = 4 ( 2 ”2 一+ ，。g ( 耳) ) 。 可燕，懑蹭2 辩，尹f 粥) 一，毪均建4 魏整数嵇。 由引瓒3 1 容易得劐下面的定理3 7 。 定理3 j ；设，了) 为弹( 片2 ) 元布尔函数，肝w 。的定义如上所述。则集合 扩= w | 氟哆；瓣k 一4 l + 2 i l ；= 。 定理3 7 表明，在定邂3 6 中我稍研戳直接罔弹和箨 分嚣l 取代略耜辑j 。 盈 第1 6 页 辫防科技大攀研究生藏掌袋论文 攀| 理3 0 ：设，r ，靠) 为扮如2 ) 嚣密尔溺数，定义z 如，。，k ；) = ，辆，靠。o ) ， 磊鹣，毛。= ，酝，毛。| ) ，弼唆，一纛箨嘎，。势嗣为磊帮磊翡w 翻婊- l 翻a 挪矗l 畦交羧 霞( w ) 及互( w ) 的最大绝对俊，定义集合暇+ ，阡r ，阡? 和暇”如下： 时； w e f l l 霞w ) = 嘲，。 ，氍一= w 霹“i 霞( w ) = 一嘲，。 ， 晖= w 芒譬1 l 霹= 嬲2 ， ，晖= w 等l 则如果+ n 崂a 或町n 崂a ，那么 n f = n r + n t e 豆( w ) = 一峨，一l 。 证明：对任意的w = ( h ，心) e 霹，令x = “，) ，x k “，薯。) ，w = ( m ，k 。) ， 我们有：当* o 或= 0 时w - 芹= w 。x ，否则w x * w 。x 协1 。因就，当= o 时，有 p 岭= f 1 ) ，坤”。= 一l 严。”+ 一1 ) ，扛“1 = 一扛归“+ ( 一酽。脚。 ：廿 k 肆“ = f l ( w ) + f 2 ( w ) f f 甄，帆+ 峨世。 溺峨一l 时，同样有( w ) 弼甚+ 麟：。 阂为域+ n 露学彩藏弼一n 瞄彩。不妨镁设存在w 拦峨+ n 孵，使褥 p t ( w ) = 暇。，z ( w ) = 峨，。 令w = ：啦= 强，+ ，”，唠e 霹剃 骨( w ) ；( 一1 ) ，( 。m + ( _ 1 ) 肿= 1 ) “扛“。+ 一1 ) 荆忡、。 ；却蚍j 甜f j 制e = 舅t w ) + z w ) = 燃，。+ 戳，。 所戳，= 毒f 2 8 一箨餮) m 寺 2 ”一 粉，十粉不。) ) = 毒 2 “一獬，) + 毒 2 “一啦，一) = 蚝+ 。 口 芍| 理3 3 ：五x ) 洚栉o 2 ) 元布尔函数及h ，地蟪霹。设l 赢( w 1 ) | = 嘲。，夸 五f x ) = z 并) 国m 算。，x ，剿| z ( 鹄) | = 嘲，一。其中霞 及箴w ) 分霸为z ( x ) 和 五x ) 的硝翻s h 。翘a d 蝴戚变换，氍，。= 娃掇黔w l ，榉霹 。 证明：易翔，对强意的w 霹，我嬲毒渗：叫戮磁，t 耀 ：* ) = 一l y o 。”“= 一1 ) ，。”、4 = 一l 尹坤”。= t ( 礁) 黼碍 0 6 眄8 q 撅啦| ：葛) | 一| ，壤) | 。嘲，。e 舀 由引理3 2 和弓l 璐3 3 ，我稍容荔得戮以下定理3 瓢 1 再孺一 圈赛辩技大学磺变生貌学位谂文 密验表明；wm “l 粕等应用硒h c l i m b 2 算法设计搬尔函数，当n = 8 ，即设计8 元的 布尔黼数时，获得的黼数的非线性度太部分为1 0 9 1 1 2 ，最高为“2 ；当h = 1 2 时，获得的 函数的非线性度绝大部分为l 蚪“1 9 5 6 ，最高为1 9 5 8 。而应用算法i h c ，当摊= 8 时，我们 褥蜀豹最葑绪莱是菲线性度为1 1 6 ，冀它大部分弱为1 1 2 1 1 4 i 当n = 1 2 对豹最好结采为 1 9 7 0 ，其它结果则大部分分布襁1 9 6 叽1 9 7 0 之间，而且这些结果分布相对集中，说明算法 l 狂c 较优予敬嶷蘸懿雾灌。美予疆桩逡取、珏鞭c l l m 磁箨洼筑傀和l 珏c 算法稳健的结鬃 分布图3 1 和阔3 2 也很好的说明了这一点。 m 埔珊麻， 蹦置l _ 8 时三种算法的结果分布图 n 蝴睡， 蹬3 0a 司2 孵三种算法豹结巢分布强 第1 9 页 国防科技大学研究生院学僦论文 鹜3 。l 秘圈3 + 2 分裂撬诧设计规模为 = s 和= 1 2 时应爆隧极生残、珏潮a i 黼敞算法 帮瑾c 算法的结果分布状况霞，实验次数均为l o 次，攒坐标耪缴坐标分磁为郛线性度 和出现频次自臼概率百分比。 3 0 赣线性缝合生戚纛及其缀食函数酶臻纯设计 在本章的第二小节中，我们介绍7 如何利用h c 算法来优化随机产生的布尔函数，提 高其非线性度，以及根摧枯尔函数自身的特点，我们对珏c 算法傲娃 改进，并取褥了良好 戆效暴。然褥，我稍羯邋，在设诗毒畚瓣数的辩镤，蠢辩还痤考露翻整鹞薅毒零痨瓣吴蒋 结构特点，本节针对非线性组合生成器这类密钥流生成器，介绍种炭似h i l lc l 妇b i n g 方 法的新算、强l h c ，用于设计当中的布尔瓣数，致力于降低输出序列向各条驱动序列之间的 符合率，提菇渡类密码抵抗相关攻壶的髓力。 3 3 1 非线性组合生成糕殿其相关性质 非线性缀合序列密鹕如图3 _ 3 所家，其中三尉醵l f 疗) 为线燃反馈移位寄存器t 共 有”和1 ) 令。五，。鼹痊嬲在蓁女令繁麴辩酶骧壅魄特，缝合遁数，逶遘传周撵移存器 输出比特( 为一，h 。) 获得第t 个节拍的密钥气，记密铜流序列为羔= z ”，) 。相应的 明文序列和密文序列分别为兰= 饥，) 及= m ，一，q ，) 。由予我们所讨论的是该体 剖中鲍组合生成器部分，明文序列和爨文詹列与密钥缪列鲍关系本文褥不予挺及。 圈3 3 非线性组合序列密码 刭最 引理3 4 ；设z x ) ， ， ( x ) 为非线性组合生成器中三，观l fs 开) 的特征多项式，如 果z f x 楚本原多壤式，次数鸯携l s f s 瓣) 基嚣嚣置繁，剩蠹它 f 】产生豹嚣零疹捌豹羁籁 也两两互素。 引理3 5 ：条件如引溅3 4 。若x ( ) = ( 捌“，捌”，聊) 和x 2 ) = ( 耐”，碰”，曩2 ) 为两 组全不为零的初态，其中州 = f 礤，搬 锈( 1 s f s 峨l 蔓，蔓2 ) ，脚从裙态x 1 ) 如发经过 若干撼嚣稳戮豹状态必岛并国楣鲁。 第2 0 页 国防科技大学研究生院学位论文 证明：由于工只s 媳均产生删序列鼠可1 o ，霹2 o ，从而必然存在藏整数f ，使得工剧氓 从状态哥1 歉发经过t 拍磊褥瓤按悫秽。不娆设嫩产生序列静援期为霉，幽弓| 理l 期， ( z ，t ) = l ，( f # j ) ，根据中国剩余定理，可知方程： f 三是m o d 互 f 5 岛m o d 五 g 撙o d 霉 存在模互五疋的唯一解，不妨设为，= f 0 ，贝u 经过b 拍后，对v 1 蔓f ”，三只s 墨从状态卅1 ) 窭发都霹疆得鬟霹。获焉霹获翅悫雾 窭发经遘气抬居爱攒戆获态萼并国籀等； 臼 由引理3 5 容易得到如下引理3 6 。 萼l 囊3 6 ：条传麴萼l 理3 + 5 。羞9 9 = 孝，。，霉，耱产= ”，+ ，毋) ，。 舞 # 线性缀念 生成器中的任意两缎全不为释的初态生成的输出序列，则z i i j 和= ( 2 j 平移等价。 奁本节中，我们菠讨论豹毒尔霹歉，) = ，如，) 均攒# 线性缀合生成嚣中豹缀含 函数。 出引理3 5 和引理3 6w 知，对特定的嚣线性组念生成嚣，组合麟数，奴，毛不问 的输入状态的概率麓可躇波菠确估算的，且秭输入端( 驱动序罗哇) 与输出的密锈流序列之 间的符合事也是可以被正确估算的。 由于浚骛| 盯& ，矗= 十2 毪+ 2 “矗= ，薯岳五楚露骜熬数集 o ，2 4 一l 上蠹孽双射， 这塑简记，= “，) 。记生成器中的组合醣数，( ，) 输入状态为，时的概率为口， 输入获态嗣定楚，辩赣窭亭舞兰与第f 条移存嚣序襄( 凝动旁翻) 静符食率为蠢，) ，羯： 厂、厂、 蟛k 叫，x ) o tl | l l 扭i，勰i ， 易知叱要么为o ，要么为l 。这时r 第f 条鞭动序列岛输出序列的符合率为： 舻= 艺= 坩毋e 此时，定义密钥流序列点与第f 条驱动序列的相关性指标为 = 一7 一1 2 。显然l 彭，) | 越小，兰与第f 个移存器的输出序列之间的相装性就越小，盔接稠用相关分析方法还藤移存 器上船r 初态的可能性也就越低。考虑到序列互与各绥驱动序列的综合相关性熊，我们定 义撵标5 7 = m 积 障砖| ，i | 妒| f 显然指标葶受畿体璇该密鹃豹抵抗相关羧遗的蘸力。 定义3 1 2 ：设j r ( x ) 为，l 元布尔函数，称集合 嚣( x ) j 如，( x ) ，g ( x ) ) = ，l i s h 为 ，f 善，豹距离为j 豹相邻函数集，记麓i 一。 类似寇义3 1 1 ，我们给出关于优化函数聪为普遍的个定义。 定义3 _ 1 3 ：竣，x 药h 无毒容滔数，一s l s 毒蔓”) 受与，x ) 雅离荛蠢麴耀邻巍数 集，如果存在函数器( x ) e 一彭使得阿叫 阿神f ，则称g ( j ) 悬与函数，( x ) 距离为女的关于 指标考 的饶让函数，稼集裔 g x ) 女一墨 阿叫 阿对| 为与，z ) 的距离为毒的关于指标 第2 1 页 潜癌辩技大学疆究生院学拉论文 耐7 的优化函数集，记为量一捌，) 。若l 一霹7 ) = 彩，则称，( x ) 怒关于指标祥7 的七一局部 最优酌。 3 3 2 疆合涵数懿霞像没计及纂法躞c 对于非线性组台幽数的设计，针对该类密鹞的结构特点，我们希望，( x ) 本身除了具鸯 较高的非线往度和较低的自稿关性之辫，还希鬻输出净列与各条驱动序剿之间具梅较低的 符合率，以抵抗各类相关分析方法的攻诲，即是坶，) | ( ，。1 ，棚) 和石( ，) 要尽可能的小a 定理3 9 ：对菜个特定匏j # 线佳组仓生成器，记爰尹；或一l ，2 ，霹一= 一l ，2 ，其中 一! ，p ；7 如前所述。设组合函数，( x ) 的输入状态为j 时的概率为够，定义函数g o ) ，当 z 时g ( x ) 。， 砖，当，= 薯时暑，) * ，x ) 撩l 。鄂么我霄】骞：g x ) gl 一耐 囊且仅当 群n 叱 o 且妒l l 嬲氛卜 证明：因为n ：爿n 一喜。窆比啦一窆g ，2 ：窆( 叱) _ l 2 ) 吼= 芝越弛 又g ( 毛) ，( 而) 静6 搀：瑚 故阿曲| _ 陲雹卜薹鲫a ， + 瓤i = | ( 雾趣扎) 一：瑚l 矽i = 矽一2 爰瓤l f 矽r = 护) 2 4 矽璎霸+ 4 艘瓢) z 所毗；g o ) e t 一耐7 ) 营阿，l | 辞曲l t 辛( 群门y ( 爿曲y 营( 群力) 2 群) 2 4 群n ，) 氐十4 ( ：) 2 矽瑚& 嘞，r 曹矽础 瑚r 瓢 瑚 q 殿阿n p 陋2 甄 臼 定理3 1 0 ：题设条件同定理3 9 及ts 巧。定义函数嚣( x ) 如下：当x x t 时g ( x ) = ( x ) ， 当毒m 墨时g ( x = ，x ) $ l 。那么我们鸯；g x ) l 一嚣铲当且仅强对v l j * 毒下式成立： 群门一z 瑚i l o 时的情况， 则演化的散聚狂效率薅辫的增加两逐瀣簿低，裁此，在设计翘模较大的搬尔西数竣多输墩 布尔黼数时，对探讨撇何提高算法的演化效率，阻及研究改交算法参数对演化效柴的影响， 将是我们进一步深入探讨的阚艨。 4 3 2 多输出低相关释许度函数的优化设计 为了使褥所妥设计的布尔函数同时篡备较低的相关容许度和较高的稚线性度，在本章 的第二小节中，我们采用适应艘函数c 哪f 。结合s a 算法来进行优化设计，并取褥了较好的 结莱。我稍发现，在翻畈中，对口帮声分掰懿予不同的权重，我稍能够获得两种性能指 标不同的设计效果。砸对予多输出布尔函数的设计，我们同样w 以借鉴以上的设计思想。 浚”元多输出穗尔丞数厂x ) = z x ) 。，矗砖：霹哼譬擀薛) ，对￥“譬，记蘧 数 厂f x l 的w 耵为f 町，则淡似适废度函数，我们令： 一搿。l 荟善 | 州w ) 州十芦【委善限t ，叫) 第3 3 页 嚣醛辩技丈学磷梵生院学佼论文 其中d ，芦为叔莺，g = 坩霹l l 墨妨 ，为捐关容许度的阶，x 为某个正数。 根据适威度函数f ，的定义，我们发现，邋应函数岛本身的计算鬣是瓯丈的，应 用 的s a 冀法的优讫效率也将显藩下降a 定理4 8 ；竣，( 印* “f 掌) ，”，五f 砷) 棚 为露劐掣的一元征交函数，( ，) 为e 上 戆乎衡疆数，对