基于随机加法链的抗功耗攻击的方法[发明专利]

(12)发明专利申请

(10)申请公布号 CN 108055126 A(43)申请公布日 2018.05.18

(21)申请号 201711309235.9(22)申请日 2017.12.11

(71)申请人 哈尔滨理工大学

地址 150080 黑龙江省哈尔滨市南岗区学

府路52号哈尔滨理工大学(72)发明人 黄海　冯新新　厚娇　赵玉迎　

刘红雨　(74)专利代理机构 哈尔滨东方专利事务所

23118

代理人 陈晓光(51)Int.Cl.

H04L 9/08(2006.01)H04L 9/28(2006.01)H04L 9/06(2006.01)

()发明名称

基于随机加法链的抗功耗攻击的方法(57)摘要

一种基于随机加法链的抗功耗攻击的方法。目前存在的基于加法链的字节替换方案中，只有固定的一条加法链，这些方案很难抵抗高阶侧信道攻击。十六个输入使用的是同一条加法链，攻击者只要成功攻击其中一条，就能破解密钥，这给密码算法带来严重的威胁。一种基于随机加法链的抗功耗攻击的方法，通过随机数发生器生成不同的数字，其大小在1到16之间且互不相等。每个字节根据对应位置生成的随机大小来调用相应的加法链，这样的操作使得每一轮字节替换各字节调用的加法链都不完全相同，提高了侧信道攻击的难度，攻击者需要通过更加复杂的运算才能破解密码算法。本发明应用于随机加法链的抗功耗攻击的方法。

权利要求书1页 说明书4页 附图3页

CN 108055126 ACN 108055126 A

权　利　要　求　书

1/1页

1.一种基于随机加法链的抗功耗攻击的方法，其特征是：该方法包括如下步骤，具体提出如下两种方案：（1）循环调用加法链：在每轮字节替换开始时，生成一个1～16的随机数，假设生成a，则第一个字节调用第a条加法链，第2个字节调用(a%16+1)条加法链，即是16个字节根据随机数循环调用加法链，保证16条加法链同时用上；

字节替换的输入为16个字节，记为{m1,m2,…m16},16条加法链分别表示为{S1(x),S2(x),…S16(x)}，由于每轮生成的随机数可能都不一样，所以每轮的每一个字节调用的加法链也不同;

（2）随机调用加法链：在每轮字节替换前，通过随机数发生器生成16个1-16不重复的数，组成一个数组，比如{3,6,10,8,7,1,11,13,16,5,2,4,12,14,9,15}，这种情况就是第一个字节调用第3条加法链，第二个字节调用第6条加法链……第十六个字节调用第15条加法链，这样的数组是1-16随机排列，共有16！种情况，所以每轮的调用加法链的情况基本上是不一样，这一点增加了加密算法的随机性，在增加不多的随机数的情况下，很大程度提高了加密算法的安全性，成16个1-16的不同随机数。

2

CN 108055126 A

说　明　书

基于随机加法链的抗功耗攻击的方法

1/4页

[0001]

技术领域：

本发明涉及一种基于随机加法链的抗功耗攻击的方法。[0002]背景技术：

自从Rijndael算法被定为高级加密标准（Advanced Encryption Standard, AES）以来，国内、外密码研究人员对它的研究兴趣越来越大。由于AES算法拥有安全和高效等优点，所以它被广泛应用于移动电话、智能芯片和移动支付等各种实际应用中。因为字节替换是AES算法中唯一的非线性操作，所以对AES的字节替换的研究一直也是一个热门方向。[0003]目前实现字节替换的方法主要有三类：查找表、复合域、加法链。查找表这种方法运算速度快，但是往往以牺牲资源为代价，即这类方法存在占用面积大，耗费资源的缺点。基于复合域这类方法的算法，通过将高阶有限域内的计算转化为低阶的有限域内的计算，该方法尽管减少了占用面积，但是运算速度也降下来了。利用加法链这种方法比其他两种方式更安全。由于侧信道攻击 (Side Channel Attack,SCA)的出现，给密码算法的安全带来严重的威胁。所以提高密码算法的安全性尤为重要。

基于有限域GF（28）上的性质x255=1,则有限域GF（28）上元素x的乘法逆元 

[0004]

,，现有加法链方法通过求有限域上一元素的乘法逆元，即求这个元素的2次方就行。通过有限域中的乘法和平方运算得到元素的2次方，其中中间结果构成了一条加法链，x->x2的一条最短加法链如公式（1）。

[0005]

其中S代表平方操作，M代表乘法操作。[0006]这样就得到元素的乘法逆元，再做仿射变换，最后异或0x63,就得到字节替换的输出。基于加法链的字节替换算法在抵抗高阶侧信道攻击上比其他两种方式更有效。[0007]目前存在的基于加法链的字节替换方案中，只有固定的一条加法链，这些方案很难抵抗高阶侧信道攻击。十六个输入使用的是同一条加法链，攻击者只要成功攻击其中一条，就能破解密钥，这给密码算法带来严重的威胁。[0008]为了使字节替换随机使用加法链，这就要求找到多条最优的加法链。由于明文是含有16个字节，该文需要找到16条功耗特性不同的加法链。这要求找到大量的含有4个乘法操作和7个平方操作的加法链，可以通过穷举法得到一些符合条件的，不过这种方式很费时费力，不一定能在短时间内找到符合条件的16条。该文通过设立条件，比如1->2需要经过11步操作得到的就符合条件，通过构造状态空间树来解决最短加法链的问题。[0009]发明内容：

本发明的目的是提供一种基于随机加法链的抗功耗攻击的方法，是基于加法链方案，旨在寻找多条最优的加法链，且这些加法链之间的功耗特性不同，这样提高了密码算法的抗侧信道攻击，提高了密码算法的安全性。

[0010]上述的目的通过以下的技术方案实现：

一种基于随机加法链的抗功耗攻击的方法，该方法包括如下步骤，具体提出如下两种方案：

3

CN 108055126 A

说　明　书

2/4页

（1）循环调用加法链：在每轮字节替换开始时，生成一个1～16的随机数，假设生成a，则第一个字节调用第a条加法链，第2个字节调用(a%16+1)条加法链，即是16个字节根据随机数循环调用加法链，保证16条加法链同时用上；

字节替换的输入为16个字节，记为{m1,m2,…m16},16条加法链分别表示为{S1(x),S2(x),…S16(x)}，由于每轮生成的随机数可能都不一样，所以每轮的每一个字节调用的加法链也不同。

[0011]

（2）随机调用加法链：在每轮字节替换前，通过随机数发生器生成16个1-16不重复的数，组成一个数组，比如{3,6,10,8,7,1,11,13,16,5,2,4,12,14,9,15}，这种情况就是第一个字节调用第3条加法链，第二个字节调用第6条加法链……第十六个字节调用第15条加法链，这样的数组是1-16随机排列，共有16！种情况，所以每轮的调用加法链的情况基本上是不一样，这一点增加了加密算法的随机性，在增加不多的随机数的情况下，很大程度提高了加密算法的安全性，生成16个1-16的不同随机数如算法1。

[0012]

本发明的有益效果：1.本发明正如图1所示，第i层结点用bi表示，可以看出第i层的儿子结点bi+1>bi。而第i层的结点可以通过公式（2）得到。

[0013]

  （2）

该文根据状态空间树找到所有最短加法链的中心思想是：控制搜索的深度为12，即不

4

CN 108055126 A

说　明　书

3/4页

断向下搜索时，在第12层，遇到2，则找到一条最短加法链，此时回到父结点，再看看其子结点有没有没遍历的，如果有，继续搜索子结点，如果没有，继续返回上一层。无论在12层找没找到2，都返回上一层，直到停留在顶层结点1处，所有最短的加法链都已找到。[0014]本发明对于AES，根据最优的加法链需要4个乘法和7个平方操作，通过C语言将符合条件的加法链全部找到，共有1191条，并且根据功耗特性的不同（即乘法和平方的位置不完全一样），将所有加法链分成117个组，每组里的加法链功耗特性相同，本文方案需要16个不同功耗特性的加法链，所以通过随机数发生器从117组中找到16组不同的加法链，为方便分析，本文采用的16个不同组里的16条加法链如表1所示。

[0015]

由表1可以看出，每条加法链的乘法和平方操作的位置不完全一致，则说明这16条加法链功耗特性不一样。

[0016]由于明文是128位，可以看作16个字节，每一个字节占8位，正好可以在每轮字节替换时，每个字节调用不同的加法链，在硬件实现上是并行调用加法链的，这样不仅提高效率，而且提高安全性。

[0017]本发明比现有的只有单一的加法链方案，算法安全性提高了很多，增加了攻击者攻击的难度，本发明的贡献在于字节替换操作中，每个字节调用了不同的加法链，比以前的一条加法链生成的密码算法更加安全。

[0018]本发明通过随机数发生器生成不同的数字，其大小在1到16之间且互不相等。每个字节根据对应位置生成的随机大小来调用相应的加法链，这样的操作使得每一轮字节替换各字节调用的加法链都不完全相同，提高了侧信道攻击的难度，攻击者需要通过更加复杂的运算才能破解密码算法，这增加了他攻击密码算法的成本。[0019]附图说明：

附图1是最短加法链问题的状态空间树示意图。[0020]附图2为一轮的字节替换部分流程图。

5

CN 108055126 A[0021]

说　明　书

4/4页

附图3为整个AES加解密的流程图。

[0022]具体实施方式：

实施例1：

一种基于随机加法链的抗功耗攻击的方法，该方法包括如下步骤，具体提出如下两种方案：

（1）循环调用加法链：在每轮字节替换开始时，生成一个1～16的随机数，假设生成a，则第一个字节调用第a条加法链，第2个字节调用(a%16+1)条加法链，即是16个字节根据随机数循环调用加法链，保证16条加法链同时用上；

字节替换的输入为16个字节，记为{m1,m2,…m16},16条加法链分别表示为{S1(x),S2(x),…S16(x)}，由于每轮生成的随机数可能都不一样，所以每轮的每一个字节调用的加法链也不同。

[0023]

（2）随机调用加法链：在每轮字节替换前，通过随机数发生器生成16个1-16不重复的数，组成一个数组，比如{3,6,10,8,7,1,11,13,16,5,2,4,12,14,9,15}，这种情况就是第一个字节调用第3条加法链，第二个字节调用第6条加法链……第十六个字节调用第15条加法链，这样的数组是1-16随机排列，共有16！种情况，所以每轮的调用加法链的情况基本上是不一样，这一点增加了加密算法的随机性，在增加不多的随机数的情况下，很大程度提高了加密算法的安全性，生成16个1-16的不同随机数如算法2。

[0024]

6

CN 108055126 A

说　明　书　附　图

1/3页

图1

7

CN 108055126 A

说　明　书　附　图

2/3页

图2

8

CN 108055126 A

说　明　书　附　图

3/3页

图3

9