基于余数系统抗MESD攻击的RSA算法

刘 莺 迎

(河南牧业经济学院信息工程学院 河南 驻马店 450044)

0 引 言

随着当今社会信息化的程度日益加深，各行各业都加大了对信息技术的依赖度，而且这种趋势越来越大。尽管信息化能够为各行业带来便捷，但是日益严重的信息安全问题也为各行业提出了非常大的挑战[1-2]。SoC智能芯片是实现当今各行业信息安全的十分重要的载体，被广泛用于军事、金融、医疗、科研等行业中，加强SoC智能芯片的安全防护对于保护各行业的信息安全具有非常重要的意义。RSA密码算法[3]作为迄今最成熟最广泛应用的公钥密码体制，由于其加密速度快、安全性高、抗数学攻击能力强等优点而被广泛用于SoC智能芯片中。但是能量分析攻击[4]的提出对采用了RSA密码算法的SoC智能芯片的安全产生了很大威胁，这种攻击方法是根据SoC智能芯片在密码算法执行过程中外泄的能量消耗信息进行攻击的。为有效加强RSA的抗MESD差分能量分析攻击能力，本文将余数系统[5]与蒙哥马利模乘[6]结合起来运用在RSA中，有效实现了RSA的抗MESD差分能量分析攻击。这是由于余数系统天然独立以及并行计算的特点能够把大数运算转变为小数运算；为了弥补余数系统无法执行除法运算的不足，结合蒙哥马利模乘算法能够有效替换取模运算中的除法运算。能耗仿真分析结果表明，本文算法能够有效抵抗MESD差分能量分析攻击。

1 相关知识概述

1.1 RSA密码算法

RSA密码算法主要是通过以下4个步骤来生成公私钥密钥对，其中：(n,e)表示公钥；d表示私钥。

步骤1随机选择两个不相同大素数p与q。

步骤2n=pq，φ(n)=(p-1)(q-1)。

步骤3随机选择正整数e，1

步骤4用Euclid算法计算d=e-1modφ(n)，其中1

RSA的自左向右二进制扫描算法如算法1所示。

算法1RSA自左向右的二进制扫描算法

输入：M，(n,e)。

输出：C=Memodn。

Step1e的二进制编码为(et-1,et-2,…,e0)2；

Step2设置C=1；

Step3对i从t-1到0，循环计算：

Step3.1C=C2modn；

Step3.2若ei=1，计算C=C·Mmodn；

Step4返回C。

1.2 余数系统

余数系统(Residue Number System, RNS)为无权的并行数值表示系统，各个元素间均没有进位，主要通过一组基来表示任一整数的余数形式，其中余数系统的基是两两互素的整数。如果余数系统有一组基是(d1,d2,…,dk)，可得任意正整数R余数系统形式：

R…=(r1,r2,…,rk)

(1)

(2)

(U*V)…=(u1*v1,u2*v2,…,uk*vk)

(3)

式中：U与V表示正整数；U…=(u1,u2,…,uk)；V…=(v1,v2,…,vk)；运算符*=(+,-,×)。

1.3 蒙哥马利模乘算法

蒙哥马利算法是非常高效的无除法模乘算法，该算法首先把任一正整数转换为模数形式，再通过多次模加运算与模乘运算即可替代模除运算，然后把所得结果的模数形式转变成正常数制，即是所需求的最终结果。蒙哥马利模乘算法的具体步骤如算法2所示。

算法2蒙哥马利模乘算法

输入：整数a和b，正整数n。

输出：c=a·b·l-1modn，l=22m，m=log2n。

Step1a的二进制编码为(at-1,at-2,…,a0)2；

Step2设置c=0；

Step3对i从0到m-1，循环计算：

Step3.1c=c+ai·b；

Step3.2c=c+c0·n；

Step4若c>n，计算c=c-n；

Step5返回n。

2 MESD差分能量分析攻击算法

MESD差分能量分析攻击表示多指数单输入攻击方法(Multiple-Exponent Single-Data)[7]，该能量分析攻击方法是在已知明文的前提下，采用多个密钥对已知明文实施加密，然后对所得到能量消耗曲线进行统计分析，其具体实施步骤如算法3所示。

算法3MESD差分能量分析攻击算法

输入：明文M，可控私钥d′。

输出：私钥d。

Step1令M为恒定输入，d′=0；

Step2采集Md在运行时的真实能量消耗值Ed[j]；

Step3对于i从n-1到0，循环执行：

Step3.3计算D[j]=Ed[j]-E1[j]；

Step4.3更新d′的值；

Step5返回d=d′。

3 算法设计

本文算法的主要思想如下：(1) 分别把两个大数X和Y与蒙哥马利模乘因子H相乘，由此可把数的表示形式转变到蒙哥马利域下，再自左向右扫描实现二进制模幂运算；(2) 采用余数系统把大数转变成小数计算，但因为整数的余数系统形式不能执行除法运算，而RSA最主要的即是执行除法运算，故利用蒙哥马利模乘替代除法运算，得到基于余数系统的蒙哥马利模乘算法，这样能够较好地把余数系统与蒙哥马利模乘算法结合起来，从而很好地解决不需要执行除法运算的RSA大数模乘问题。由于结合余数系统和蒙哥马利模乘的RAS算法不需要执行模除运算，只需执行蒙哥马利模乘运算，执行过程中没有明显的能量消耗差异，使得攻击者无法获取与密钥相关的信息，所以可以有效抵抗MESD差分能量分析攻击。

算法4基于余数系统的蒙哥马利模乘算法

输入：[X]A∪B，[Y]A∪B，N。

输出：[r]A∪B。

//r=XYH-1modN，且有r<2N

Step1对于i从1到l，重复执行：

Step1.1计算wi=(xi×yi)modai；

Step2令zi=BT(zi,0)；

Step3对于j从0到l，重复执行：

Step3.1计算wj=(xj×yj)modbj；

Step3.2计算fj=(wj+zj×Nj)modbj；

//i=j

Step4计算ri=BT(rj,0.5)；

Step5返回(ri,rj)。

算法5基转换算法

输入：[g]A，β。

//β为基转换修正因子，且有β=0或β=0.5

输出：[g]B。

Step1设置α0=β；

Step2对i从1到l，循环计算：

Step2.3设置xi0=0；

Step3对j从1到l，循环计算：

Step3.1对i从1到l，循环计算：xji=(xj(i-1)+σi|Ai|bj)modbj；

Step3.2xj(l+1)=(xjl+(bj-σl)|A|bj)modbj；

Step4返回xj(l+1)。

由算法4可得大数X的模幂运算Y=XemodN。则可得基于余数系统和蒙哥马利模乘的RSA二进制扫描算法，如算法6所示。

算法6基于余数系统和蒙哥马利模乘算法的RSA二进制扫描算法

输入：[X]A∪B，e=(et-1,et-2,…,e0)2，N。

输出：[Y]A∪B。

Step1预计算W=H2modN；

//H表示蒙哥马利模乘因子，其中H=a1×a2×…×al

Step2[F]A∪B=RNSM([X]A∪B,[H]A∪B,N)；

Step3[Y]A∪B=RNSM([1]A∪B,[H]A∪B,N)；

Step4对i从t-1到0，循环计算：

Step4.1[Y]A∪B=RNSM([Y]A∪B,[Y]A∪B,N)；

Step4.2若ei==1，[Y]A∪B=RNSM([Y]A∪B,[F]A∪B,N);

Step5[Y]A∪B=RNSM([Y]A∪B,[1]A∪B,N)；

Step6返回[Y]A∪B。

4 仿真实验和分析

本节通过MESD能量消耗攻击仿真来检验所给算法6抵抗MESD差分能量分析攻击的能力。仿真主要是利用文献[10]提出的实验平台来实施所给算法的能量分析攻击仿真，其中单片机为AT89C52，数字示波器为Tektronix DPO4032，采用LabView编写虚拟示波器程序来控制数字示波器自动采集能量消耗信息。假设所给算法6采用的真实私钥为d=(1100)2。仿真步骤主要过程如下：

(1) 配置采样控制平台。采样长度为10 000，采样次数为10 000，采样时间为4 ms。

(2) 发送恒定明文信息到单片机，利用真实的私钥d进行加密，采集真实的能量消耗信息并存储。

(4) 采用MATLAB 7.0分别求取两组能量消耗数据，并分别与真实能量消耗信息进行差分计算，生成能量消耗轨迹波形图。

(5) 通过观察所生成的能量消耗轨迹。若能量消耗轨迹在猜测密钥比特位的区域内没有出现尖峰(能量消耗轨迹中出现尖峰是由于猜测密钥与真实密钥操作相反，导致执行的操作指令顺序和数目不同，而不同的操作执行时消耗的时间不同，使得所获得的能量消耗轨迹无法准确对齐，在没有对齐的时段则会出现尖峰)，则判断该密钥比特位取值应为1；若能量消耗轨迹在猜测密钥比特位的区域内出现尖峰，则判断该密钥比特位取值应为0。

(6) 所有密钥比特位猜测完成后，可获取通过MESD差分能量分析攻击得到的密钥，通过与真实的私钥比较，判断猜测的密钥是否正确。

图1 猜测第1个比特位为1时采用MESD攻击的能量消耗轨迹

图2 猜测第2个比特位为1时采用MESD攻击的能量消耗轨迹

图3 猜测第3个比特位为1时采用MESD攻击的能量消耗轨迹

图4 猜测第4个比特位为1时采用MESD攻击的能量消耗轨迹

根据上述4个猜测比特位的能量消耗轨迹可以看出，MESD攻击最终获取的密钥为d′=(0101)，但是实际的密钥为d=(1100)2。因此，采用MESD差分能量分析攻击方法攻击算法6无法得到正确的真实私钥，即表明本文算法能够抵抗MESD差分能量分析攻击。

5 结 语

能量分析攻击对于RSA密码算法具有非常大的安全威胁，特别是差分能量分析攻击中的MESD方法是非常有效的攻击RSA密码算法的方法。为了能够更好地抵抗MESD差分能量分析攻击，本文提出一种基于余数系统和蒙哥马利模乘的RSA二进制扫描算法。首先采用整数的余数系统形式把大数运算转变成小数运算，其主要目的是利用余数系统天然的并行性优点来使RSA密码算法能够高度并行化处理；然后用蒙哥马利模乘替换RAS中的除法运算，其主要目的是弥补采用整数的余数系统形式不能执行除法运算的不足。由实验仿真分析结果可知，对RSA密码算法实施MESD差分能量分析攻击不能得到正确的私钥信息，因此本文算法可以有效抵抗MESD差分能量分析攻击。