基于多种群遗传算法的相关能量分析中个体结合策略探究*

王 安,李 圆,丁瑶玲,祝烈煌,王永娟

1.北京理工大学计算机学院,北京 100081

2.河南省网络密码技术重点实验室,郑州 450001

1 引言

侧信道攻击通过利用密码设备加密过程中泄露的功耗、电磁、时间等侧信息,获取敏感数据.经典的侧信道攻击方法有能量攻击[1,2]、故障攻击[3]、模板攻击[4]、碰撞攻击[5]等;近年来,出现一些基于人工智能的侧信道攻击方法,尤其是机器学习在侧信道领域受到广泛关注,包括支持向量机[6,7]、随机森林[8,9]、多层感知器神经网络[10,11]、卷积神经网络[12-14]等.

文献[15]提出一种非建模类的基于人工智能的侧信道攻击方法,将遗传算法(genetic algorithm,GA)与相关能量分析(correlation power analysis,CPA)结合,应用到密码算法硬件实现场景下的侧信道攻击中,通过更高信噪比的泄露模型达到了超越传统CPA的表现.文献[16]在其基础上,针对其存在的早熟收敛的问题,使用多种群的方法,每个种群仍旧采用类似于文献[15]的简单遗传算法,分别独立进化,但是对不同种群迭代结束得到的最优个体进行“组合”,来获取更优的个体,这种方法可以一定程度上克服早熟收敛的问题.

学界有很多关于多种群遗传算法的研究.文献[17]提出基于多种群的强者进化遗传算法,使用多个单种群和一个主种群进行两阶段进化,第一阶段由多个异构单种群单独进化到一定代数,将各自的最优个体传递给主种群,第二阶段进行由强者构成的主种群的进化,使用自定义的变异算子.文献[18]提出变搜索区域多种群遗传算法,依据各种群最优个体的分布不断缩小搜索区域,并且随着搜索区域减小种群规模成正比减小,新种群中的个体一部分来自该区域已存在的优秀个体,另一部分由随机均匀方法产生.文献[19]提出一种改进的双种群遗传算法.同时进化两个种群,一个种群让高相似个体之间具有相对高的交叉率,注重局部搜索;另一个种群让低相似个体之间具有相对高的交叉率,注重全局搜索,在两个种群间使用移民,使得算法兼具较强的局部搜索与全局搜索能力.文献[20]使用两个辅助种群和一个主种群,三个种群分别独立进化,每完成一次种群更新,都用两个辅助种群的最优个体替换主种群中最差的两个个体.文献[21]采用多个普通种群和一个优良种群,通过纵横协同方式进化多轮,以实现多种群之间的信息共享和优势互补,一定程度克服了遗传算法的早熟收敛特性.文献[22]常用于解决多目标优化,通过设置不同的控制参数或目标函数,并且通过移民算子相互引入种群中的优秀个体,实现种群协同进化,并设置精英种群用以保留每代的最优个体,避免早熟收敛.

本文在文献[16]的基础上针对由多个种群独立进化得到的优秀个体间的结合策略进行探究,提出小组赛、投票法及二次进化三种结合策略.小组赛不再采用文献[16]中第一个种群与之后每个种群中最优个体相继组合的方式,而是将优秀个体进行两两分组,再进行组合.投票法通过让所有优秀个体进行投票,决出一个最优个体.二次进化与文献[17]相似,但是采用的是多个同构单种群,且在再次进化时,通过使用稳态遗传的方式,并且选择合适的参数,加快收敛速度.将上述三种策略与文献[16]的方法从成功率和计算代价两个角度进行了对比实验,并对结果进行了分析.

文章接下来的结构:第2节介绍预备知识,包括CPA、简单遗传算法、稳态遗传算法、基于简单遗传算法的CPA和基于多种群遗传算法的CPA;第3节介绍小组赛、投票法和二次进化这三种结合策略的思想和算法步骤;第4节介绍遗传算法的参数选取;第5节介绍效率对比实验;第6节总结和讨论.

2 预备知识

2.1 相关能量分析

汉明距离模型与汉明重量模型是能量分析中两种常用能量模型,用于将操作数映射为能量消耗值,作为对设备的能量仿真.x的汉明重量HW(x)等于二进制形式x中为1的比特数量,x与y之间的汉明距离HD(x,y)=HW(x⊕y),汉明重量(距离)模型认为能量消耗与两个操作数的汉明重量(距离)呈线性关系.公式(1)代表能量消耗与操作数间的线性关系模型,其中T代表能量消耗,a是标量增益,H代表操作数的汉明重量或汉明距离,b包含偏移量、与时间相关的分量及噪声.

CPA基于能量模型和相关系数恢复密钥,下面以恢复AES-128算法密钥第一字节为例对CPA分两阶段进行介绍,分别是数据准备阶段和分析阶段.假设攻击位置是AES-128第一轮S盒的输出,能量消耗服从汉明重量模型.在数据准备阶段,攻击者需获取一组明文波形对,波形是指在固定密钥、随机明文下加密时位于攻击位置时刻的真实能量消耗值.用k代表密钥字节的可能取值,k有256种取值.在分析阶段,首先使用公式(2)计算与k相关的操作数m,其中p代表一字节明文,Sbox代表AES-128的S盒运算;再计算m下的汉明重量H=HW(m),依据公式(1)计算假设能量消耗T,依据相关系数计算公式(3)计算假设能量消耗H与波形T的相关系数;k有256种取值,所以k参与运算的m、H、ρH,T相应也有256种取值,最后找到最大相关系数所对应的密钥字节取值,认为是该密钥字节的正确取值.其余密钥字节也采取同样的方式进行恢复.

2.2 简单遗传算法和稳态遗传算法

GA是一类模拟生物进化过程、用于解决优化或搜索问题的启发式算法.对GA的描述涉及“个体”、“种群”、“代”、“适应度”、“选择”、“交叉”和“变异”等概念.其中,“个体”指问题的一个候选解,需进行编码表示,二进制编码是一种常见方式.“种群”由一组个体构成,比如由N个个体构成,则种群规模大小就是N.由一个初始种群,繁殖产生新的一组个体,这组个体又构成一个种群,继续繁殖产生新个体,整个繁殖过程不断迭代,每次迭代产生一“代”个体.“适应度”用于评估个体的优劣,计算方法基于目标函数.“选择”类似于生物界的自然选择,选择策略有多种,但共同原则是让更优的个体以更大概率被保留下来并进行交叉和变异.“交叉”和“变异”是产生新个体的方式,类似于生物界的染色体交叉和变异,表1描述了8比特表示的个体间的单点交叉,箭头位置代表交叉点.表2描述了8比特表示的个体的单比特变异,粗斜体标识的比特发生了变异.

表1 单点交叉Table 1 One-point crossover

表2 单比特变异Table 2 One-bit mutation

GA的过程可描述为:首先初始化一个种群作为初代,接着不断迭代繁殖.繁殖过程中,种群中每个个体需要计算适应度.继而通过选择策略,让适应度更高的个体以更大概率被选中,未被选中的个体将被淘汰,以此提高整个种群的平均适应度.被选中的个体作为父代,再以一定概率进行交叉和变异产生子代个体.子代个体是否替换父代进入下一代取决于遗传方式,对于简单遗传算法,子代将替换父代进入下一代,对于稳态遗传算法,子代只有适应度高于父代,才能替换父代进入下一代.种群的下一代重复同样的繁殖过程,不断迭代至算法收敛到一个最优解.

2.3 基于简单遗传算法的CPA

在硬件实现的密码算法中,同一时刻多个S盒运算并行执行.对这类算法进行经典CPA,若只利用其中一个S盒的信息量,其余S盒的信息量就只能被视作噪声,导致低信噪比.将多个S盒的假设能量消耗相加,与波形计算相关系数,所得结果比单个S盒的假设能量消耗与波形的相关系数要高,且S盒的数量越多,相关系数越高.经典CPA若要利用全部S盒的信息量,以提高信噪比,获得更大的相关系数,会导致巨大的搜索空间.因此,文献[15]提出基于简单遗传算法的CPA,利用了全部S盒的信息量,且遗传算法的启发式搜索特性使得巨大的搜索空间也变得可行,相比经典CPA,信噪比提高,因而攻击效率也得到显著提高.

算法首先初始化一组密钥猜测,作为初始种群,这一步骤用函数Selection()表示;种群适应度的计算通过将各个S盒的假设能量消耗相加与波形计算相关系数,这一步骤用函数CalculateFitness()表示;随后选择适应度大的个体,按一定交叉概率和变异概率进行交叉和变异,其中交叉操作用函数Crossover()表示,变异操作用函数Mutation()表示,交叉和变异以字节为单位,交叉策略见表1,变异策略见表2;种群不断迭代,直至找到正确密钥或者达到繁殖代数上限. 具体步骤见算法1,我们将这个算法称作SGA_CPA().

算法1基于简单遗传算法的CPA Input:繁殖代数上限gen_thre,种群规模N,交叉率p c,变异率p m,明文plaintext,波形trace Output:最优个体best_key 1 count_gen←0;2 Initialize(pop,N); //初始化种群3 while count_genFitness(comebine_key)then 14 comebine_key[i]:=tmp[i];15 else 16 tmp[i]:=comebine_key[i];17 end 18 end 19 end 20 if Equal(combine_key,right_key=true)then 21 break;22 end 23 else 24 return best_key; //如果单种群找到正确密钥,则输出25 end 26 end 27 return combine_key;

2.4 基于多种群遗传算法的CPA

基于简单遗传算法的CPA存在早熟收敛问题,尤其在S盒大、数量多的时候.为了克服这个问题,文献[16]提出基于多种群遗传算法的CPA.虽然单个种群在进化时由于早熟收敛,最终只能猜对部分密钥字节,但各个种群基本都能猜对差不多数量的密钥字节,并且猜对的密钥字节序数也有不同,通过收集多个种群的最优个体,进行“组合”,有机会恢复全部密钥字节.算法首先让第一个单种群进化得到一个最优个体,记为combine_key,若没有得到正确密钥,则开始新的单种群进化,得到的最优个体记为individual.individual如果也不是正确密钥,则对combine_key和individual进行“组合”,“组合”后的结果仍记为combine_key,若仍不是正确密钥,则继续新的单种群进化,得到的最优个体继续与combine_key“组合”,直到恢复密钥成功或达到种群个数上限.其中“组合”是指:依次将combine_key中各字节取值替换为individual中相应字节取值,并重新计算适应度,若适应度低于原来的combine_key,则还原该字节.具体步骤见算法2.

多种群中各个单种群进化方式仍采用算法1,只是选择、交叉和变异的策略进行了改进.选择策略采用算法3截断选择的方式,只在适应度靠前的一段范围内选择个体.交叉策略采用算法4按字节交叉的方式,交换的是个体间的字节.变异策略采用算法5按字节随机变异的方式,变异方向为一字节内的任意取值.

算法3截断选择Input:按适应度从高到低排序的种群Pop,种群规模N,截断选择阈值p t Output:选中的个体individual 1 i←Random(1,N×p t);2 individual:=Pop[i];3 return individual;算法4按字节交叉Input:要交叉的两个个体individual1,individual2,交叉率p c Output:更新后的两个个体individual1,individual2 1 for i←1 to n word do 4 tmp:=individual1[i];2 r:=Random(0,1);3 if r

3 多种群遗传算法个体结合策略

基于多种群遗传算法的CPA使用多个单种群,分别进化得到多个优秀个体,通过对个体进行组合以利用各个个体的信息量来克服遗传算法容易早熟收敛的缺点.如何充分利用优秀个体的信息量获取正确密钥,是基于多种群遗传算法的相关能量分析中个体结合策略要解决的问题.接下来分别介绍“小组赛”、“投票”及“二次进化”这三种个体结合策略,以及基于这三种策略的多种群遗传算法与CPA的结合.

3.1 小组赛

基于小组赛多种群遗传算法的CPA,本文简称为小组赛.文献[16]中个体结合策略通过将第一个种群的最优个体依次与之后的种群得到的最优个体进行组合,小组赛仍旧使用相同的组合方式,这个方式在2.4节已经介绍,与文献[16]不同的是小组赛使用了另一种组合顺序.图1描述了种群个数上限为8时小组赛的组合顺序,类似于一棵倒置的二叉树,所以种群个数需是2的整数次方,图中每个圆圈代表一个优秀个体,种群1、种群2的最优个体最先进行组合,得到的结果记为组合1.接下来种群3和种群4组合,得到的结果记为组合2,然后组合1和组合2组合,得到的结果记为组合3.种群5至种群8的组合顺序类似于种群1至种群4,依次产生的结果是组合4至组合6,最后由组合3与组合6产生组合7.组合1至6任意一个为正确密钥时,程序就会结束,不再继续新的单种群进化和组合.小组赛中各个单种群的进化方式与2.4节中的单种群进化方式相同,具体步骤见算法6.

图1 小组赛示例Figure 1 Group match example

3.2 投票法

基于投票法多种群遗传算法的CPA,本文简称为投票法.投票法首先需要收集各个种群进化得到的最优个体,并且让每个个体对密钥各个字节的可能取值进行投票,再根据投票结果决出最终输出密钥各个字节的取值.个体对密钥第一字节最基本的投票方式是让该个体第一字节的取值得1票,但这种方式对于适应度不同的个体的投票权重是一样的,有可能导致适应度最高的个体的各字节的取值不能脱颖而出,因而更合适的投票方式是令个体在该字节的取值增加的票数为个体的适应度,其余密钥字节也采取同样方式.最后统计各个字节在各个可能取值下的票数,每个字节得票最多的取值作为最终输出密钥在该字节的取值.投票法中各个单种群的进化方式与2.4节中的单种群进化方式相同,具体步骤见算法7.在单种群进化不能收敛到全局最优时,投票法需要先收集全部单种群的最优个体,没有中间结果来辅助判断是否找到正确密钥.而文献[16]及小组赛在各个单种群进化结束时,通过组合产生的新个体可辅助判断是否找到正确密钥,有机会不需要等到全部单种群进化结束就可以结束程序.投票法方式一次性对全部优秀个体统一进行整合,文献[16]及小组赛对优秀个体分阶段进行整合.

3.3 二次进化

基于二次进化多种群遗传算法的CPA,本文简称为二次进化.文献[16]、小组赛及投票法利用的信息量全部来自于各个种群进化得到的最优个体,如果这些个体各个字节的取值没有全部覆盖正确密钥各个字节的取值,那么上述方法都不能够成功恢复密钥.二次进化分两阶段,第一阶段先让各个单种群分别独立进化,进化方式与2.4节中的单种群进化方式相同,第二阶段将各个单种群进化得到的最优个体构成一个初始种群,进行再次进化,由于进化过程中涉及交叉和变异操作,使得原本错误的部分密钥字节有机会进化正确,从而成功恢复密钥,具体步骤见算法8.

算法6基于小组赛多种群遗传算法的CPA Input:繁殖代数上限gen_thre,种群规模N,种群个数上限pop_thre,截断选择阈值p t,交叉率p c,变异率p m,明文plaintext,波形trace Output:最优个体best_key 1 height←log2 pop_thre+1;2 count_pop←0;3 while count_pop

图2比较了二次进化第二阶段分别使用简单遗传、简单遗传和保留全局最优的组合、稳态遗传时的效果,三种方法在二次进化第二阶段的种群规模都等于第一阶段进化所使用的种群个数上限,这里统一设置为35,使用100次仿真实验统计每10代最优个体的平均正确密钥字节数.可以看到,使用简单遗传的二次进化完全没有收敛,这与种群规模太小有关;使用简单遗传并且保留全局最优的方式进行二次进化,种群收敛非常缓慢;使用稳态遗传方式进行二次进化,种群收敛速度最快.故二次进化第二阶段选用稳态遗传方式进化,产生的子代个体只有适应度高于相应父代,才能替换父代被保留下来,这样适应度高于所产生子代的父代始终能被保留,种群整体稳步向适应度更高的方向进化.

图2 三种遗传方式比较Figure 2 Comparison of three genetic methods

算法8基于二次进化多种群遗传算法的CPA Input:繁殖代数上限gen_thre,种群规模N,种群个数上限pop_thre,截断选择阈值p t,交叉率p c,变异率p m,二次进化的子代更新比例r,二次进化的繁殖上限sgen_thre,二次进化的交叉率sp c,二次进化的变异率sp m,明文plaintext,波形trace Output:最优个体best_key 1 count_pop←0;2 while count_pop

Fitness(p1)then 22 p1:=c1;23 end 24 if Fitness(c2)>Fitness(p2)then 25 p1:=c2;26 end 27 end 28 best_key:=MaxFitness(pop_good); //寻找适应度最高的个体29 if Equal(best_key,right_key=true)then 30 break;31 end 32 end 33 return best_key;

4 参数选取

4.1 单种群遗传算法参数选取

文献[16]已经针对单种群遗传算法涉及的参数及多种群时的种群个数上限进行过选参,最终择优选取的参数包括,种群规模500,繁殖代数上限150,截断阈值0.4,交叉率0.5,变异率0.12,种群个数上限35.小组赛和投票法中的单种群遗传算法也将采用这一组参数,其中小组赛的种群个数上限需是2的整数次方,故不采用35,而是32.投票法需要在多个种群迭代结束后才能进行票数统计决出各个密钥字节的取值,考虑到计算复杂度,种群个数上限不宜设置过大,设置过小会影响投票结果的正确性,故仍旧设置为35.二次进化所需的初始种群来源于多个单种群的最优个体,这些个体越好,二次进化第二阶段越容易收敛到正确密钥,因而对于单种群的选参,仍旧参考文献[16],即截断阈值0.4,交叉率0.5,变异率0.12.考虑到二次进化第二阶段仍然需要计算适应度,为了避免过高的计算复杂度,单种群参数设置也有不同之处,包括种群规模设置为200,繁殖代数上限设置为100.

4.2 二次进化参数选取

二次进化第二阶段涉及种群个数上限、子代更新比例、繁殖代数上限、交叉率和变异率这5个参数的选取,下面将通过实验选取合适参数值.

4.2.1 种群个数上限与子代更新比例

种群个数上pop_thre直接决定二次进化第二阶段时的种群规模,而使用稳态遗传的二次进化,子代数量为r×pop_thre,r代表子代更新比例,即每代产生的子代个体数量与种群规模的比值,这两个参数共同影响收敛速度,故对种群个数上限pop_thre和子代更新比例r进行组合寻优.由于文献[16]中种群个数上限为35,而二次进化涉及继续迭代,为了避免过大的计算复杂度,这里测试种群个数上限的范围为[10,35],步长为5,测试子代更新比例的范围为[0.2,1],步长为0.2.对种群个数上限和子代更新比例的各个组合进行100次仿真实验,统计每50代的最优个体平均正确密钥字节数,繁殖代数上限为8000,每次实验使用180条仿真波形,噪声标准差为3.实验结果如图3,可以看到,当种群个数和子代更新比例分别是最大值35和最大值1时,平均正确密钥字节数最高,为15.34,但此时次优点15.24也不错,对应种群个数上限与子代更新比例的组合为(30,1),此时计算复杂度更低,所以后续实验将采用这组参数.

图3 种群个数与子代更新比例选参Figure 3 Selection of pop_thre and r

4.2.2 第二阶段繁殖代数上限

图4是上述实验结果的另一种表示方式,每一条线代表种群个数上限与子代更新比例的一个组合,展示了随着繁殖代数上升,平均正确密钥字节数的变化.其中红色线代表种群个数上限与子代更新比例的最优组合(35,1),绿色线代表次优组合(30,1),灰色线代表其他组合.上面已经分析过后续实验会采用次优组合,从图中可看出次优组合在2500代时已经收敛,故后续实验的二次进化第二阶段繁殖代数上限设置为2500.

图4 不同种群个数与子代更新比例表现Figure 4 Peformance of pop_thre and r

4.2.3 交叉率和变异率

二次进化第二阶段采用稳态遗传方式,其收敛速度与简单遗传方式不同,故不再采取与前面简单遗传一致的交叉率和变异率,而是对交叉率和变异率的组合进行新的寻优.交叉率的测试范围[0.1,0.5],步长0.1,变异率的测试范围[0.05,0.15],步长0.01,每次实验使用130条仿真波形,噪声标准差为3,进行100次实验,统计平均正确密钥字节数.实验结果如图5,(交叉率,变异率)存在两个最优组合,分别是(0.1,0.14)和(0.15,0.12),后续实验采取的组合是(0.15,0.12).

图5 二次进化交叉率与变异率选参Figure 5 Selection of crossover rate and mutation rate for secondary evolution

5 效率对比实验

5.1 仿真实验

仿真实验针对AES-128算法,攻击位置为第一轮S盒的输出.假定仿真波形服从汉明重量模型,噪声服从高斯分布,噪声标准差为3.探究文献[16]中多个种群进化得到的最优个体间的结合策略、小组赛、投票法及二次进化这四种方法在同一组波形上的表现,下面将文献[16]中使用的方法简称为原始方法.在多组不同数量的波形下均进行了实验,波形数量的范围[100,500],步长为10.每组波形进行100次实验统计四种方法的成功率和计算代价,其中计算代价用适应度的计算次数表示.

原始方法使用的参数包括(种群规模,单种群繁殖上限,截断阈值,交叉率,变异率,种群个数上限),对应取值为(500,150,0.4,0.5,0.12,35),小组赛使用的参数类型相同,对应取值为(500,150,0.4,0.5,0.12,32).投票法使用与原始方法完全一致的一组参数.二次进化也使用到原始方法涉及的参数类型,对应取值为(200,100,0.4,0.5,0.12,30),除此之外,还有二次进化第二阶段进行稳态遗传时涉及的参数,包括(繁殖代数上限,交叉率,变异率,子代更新比例),对应取值为(2500,0.15,0.12,1).

四种方法成功率对比如图6,计算代价对比如图7.二次进化在190条波形时成功率达到91%,计算代价0.63×106,同样的波形条数,原始方法、小组赛和投票法的成功率分别为60%、57%和22%,计算代价分别为1.60×106、1.66×106和2.24×106.同样的波形条数下,二次进化的成功率最高,投票法的成功率最低,原始方法与小组赛的成功率接近;对于计算代价,波形数不超过200条时,二次进化的计算代价最小,投票法的计算代价最大,其余两种方法介于中间,且计算代价接近,这是因为在波形数量少时,单个种群很难收敛到全局最优,投票法需要在各个单种群进化结束后才能决出最终密钥,二次进化虽然也需要在各个单种群进化结束后才进入第二阶段,但是二次进化中种群规模和单种群繁殖上限设置得小很多,且二次进化第二阶段种群规模更小.波形数超过220条后二次进化的计算代价逐渐变成四种方法中最大的,这是因为二次进化中种群规模和单种群繁殖上限设置与其他三种方法相比,不是最优的.实际上,随着波形条数增加到250条,使用最优参数的单种群表现通常已经很好,这时二次进化中的单种群参数也可以设置成与其他三种方法一样的,基本上在二次进化第二阶段开始之前,密钥就已经恢复正确了,这样二次进化的计算代价可以降至与其它三种方法差不多的水平.

图6 噪声标准差为3时成功率对比Figure 6 Comparison of success rate when noise standard deviation is 3

图7 噪声标准差为3时计算代价对比Figure 7 Comparison of computation cost when noise standard deviation is 3

我们又在噪声标准差为5的场景下进行了同样的实验,考虑到噪声标准差增加,二次进化的单种群参数由200改为300,迭代上限仍为100,并且,当波形数量充足时,单个种群就能大概率恢复密钥,因此在波形条数大于等于400时,二次进化的单种群参数由300改为500,迭代上限由100改为150,其余三种方法的参数保持不变,所得实验结果如图8和9所示.可以看到,当波形条数小于360时,二次进化的成功率和计算代价都是最有优势的,当波形条数大于等于360时,小组赛方法的成功率与二次进化方法接近,但计算代价略小于二次进化方法.

图8 噪声标准差为5时成功率对比Figure 8 Comparison of success rate when noise standard deviation is 5

图9 噪声标准差为5时计算代价对比Figure 9 Comparison of computation cost when noise standard deviation is 5

5.2 FPGA上的实验

我们在FPGA上进行了真实实验,通过采集2000条由随机明文固定密钥的AES-128算法在SAKURA-G上运行时所产生的能量波形,并选取攻击位置为算法最后一轮S盒的输入.首先通过在不同波形条数下计算错误密钥与正确密钥的相关系数,结果如图10所示,当波形条数至少为260条时,正确密钥的相关系数高于错误密钥,因此可以从错误密钥中区分出来.随后固定波形条数为260条,进行400次实验统计四种方法的成功率和计算代价,每次实验从2000条波形中随机抽取260条波形,实验结果如表3所示.可以看到,二次进化的方法在成功率和计算代价上相比其余三种方法都有明显优势.

表3 真实场景下效率对比Table 3 Efficiency comparison in real scenarios

图10 不同密钥取值下的相关系数与波形条数的关系Figure 10 Relationship between correlation coefficient and number of traces for different candidate keys

6 总结

本文受基于多种群遗传算法的CPA启发,研究多个种群进化得到的最优个体间的结合策略,引入小组赛、投票法及二次进化这三种个体结合策略,并与多种群遗传算法、CPA结合,从成功率和计算代价两个层面将三种方法与原始方法进行比较,发现二次进化的方式不再局限于多个最优个体的各字节取值,而是通过进化使得更有机会找到正确密钥,故成功率是四种方法中最高的,且在波形数量不充足使得成功率小于80%时,二次进化方法由于使用的单种群的种群规模和繁殖代数上限更小,因而计算代价显著小于其余三种方法,而在波形数量充足使得成功率大于80%时,二次进化方法的单种群的种群规模和繁殖代数上限也可以保持与其余三种方法一致,此时二次进化方法的计算代价与其余三种方法接近.因而在实际攻击中采用二次进化方法从成功率和计算代价角度上分析都是最具优势的.小组赛和原始方法这两种方法的成功率和计算代价都相近,投票法的成功率和计算代价均是四种方法中较差的.

通过对多种群中最优个体间的原始结合策略进行优化,我们发现二次进化方法在拥有更高的成功率的同时,计算代价也更低,有助于提升基于多种群遗传算法的CPA的效率,并且进一步克服了遗传算法容易早熟收敛的固有缺点.我们希望找到更多思路并加以实践来克服遗传算法在侧信道分析中容易早熟收敛的问题.