CN112491543B - 基于改进的蒙哥马利模幂电路的ic卡解密方法 - Google Patents

Abstract

本发明公开了基于改进的蒙哥马利模幂电路的IC卡解密方法，本发明选择了RL二进制扫描作为模幂的实现方式，使用了改进的高性能蒙哥马利模乘器来实现解密系统。先进行全硬件实现的参数预计算，再通过高性能的蒙哥马利模幂电路计算RSA解密结果，整个系统结合多种侧信道攻击防御方法，采用了随机进行伪操作来抵抗SPA，随机盲化密钥来抵抗DPA。并行计算模乘和模平方抵抗时间攻击，模幂末尾连续计算两次抵抗FIA。本发明既提高了IC卡密文解密应用场景的灵活性，又克服了常规蒙哥马利模幂模块计算周期较长的问题，大大提高了电路性能和系统安全性。

Description

基于改进的蒙哥马利模幂电路的IC卡解密方法

技术领域

本发明属于可信计算领域，涉及基于改进的蒙哥马利模幂电路的IC卡解密方法。

背景技术

RSA作为最广泛应用的公钥加密算法，其数据加密和数字签名的应用在信息安全领域扮演着重要的角色。随着计算机技术的高速发展，RSA标准密钥的长度越来越大，这对RSA算法的实现提出了更高的要求。尤其是现代IC技术的发展，促使IC卡、USB Key等小型电子设备在电子商务领域得到越来越多的应用；因而将RSA协处理器嵌入到这些小型硬件中，对电子商务高度发达的今天将具有重大的现实意义。

经RSA算法加密后的IC卡密码系统的安全性取决于大数分解的困难性，所以通常IC卡加密系统中RSA 算法的位数都很高，一般需要取到1024位以上才能保证安全性。IC卡密问的解密方法有多种实现的方式，既可以通过软件实现也可以通过硬件实现。使用软件处理大数的运算速度比较慢，硬件实现方式有更多的优势，表现在速度更快、更安全、更稳定、成本更低、成品体积更小等众多优点。而1985年蒙哥马利提出了一种新的算法，这种算法通过将模幂运算的除法运算转化成了更简单的加法运算和移位运算，在此算法的基础上，利用硬件实现IC卡密文的解密变得更加简单，同时伴随着微电子水平的提高，硬件实现方式得到快速发展。

然而随着信息安全性的要求越来越高，目前已知的蒙哥马利模幂电路不论在主频还是防御侧信道攻击方面的表现都无法满足当前需求，提出一种更优化的蒙哥马利大数模幂电路来完成更高安全性的IC卡密文解密方法迫在眉睫。

发明内容

针对现有技术的不足，本发明提出了基于改进的蒙哥马利模幂电路的IC卡解密方法，通过优化蒙哥马利模幂电路中的模乘器，配合多种防御侧信道攻击方法，提高系统的计算速度与安全性，实现更快速、更高安全性的IC卡密文解密。

现有的蒙哥马利模乘器通常包括预计算环节、迭代环节和进位计算环节，基于改进的蒙哥马利模幂电路的IC卡解密方法，所述改进的蒙哥马利模幂电路包括改进的蒙哥马利模乘器、n’[0]计算模块、mont2计算模块、指数盲化模块、真随机数生成模块和模式寄存器模块。其中改进的蒙哥马利模乘器在现有技术的基础上增加了一组寄存器，实现预计算环节与进位计算环节的并行处理。

具体包括以下步骤：

步骤1、系统输入

向所述蒙哥马利模幂电路输入加密后的IC卡密文M、解密位宽长度length、两个素数p、q和密钥E，p与q乘积的位宽等于解密位宽长度length。

步骤2、配置模式寄存器

根据解密位宽长度length对模式寄存器进行配置。

步骤3、预计算参数

3.1、根据素数p和q，使用改进的蒙哥马利模乘器计算模数N与欧拉函数fan；

3.2、使用n’[0]计算模块计算模数N的最低字n’[0]；

3.3、使用mont2计算模块计算基数R和常数2的蒙哥马利形式mont2；

3.4、将基数R和常数2的蒙哥马利形式mont2输入改进的蒙哥马利模乘器计算参数R^2。

步骤4、计算盲化的密钥

指数盲化模块根据真随机数生成模块产生的随机数随机选择1、2、4、8、16、32倍的欧拉函数fan，再将原密钥E与选择的随机倍数的欧拉函数fan进行分组相加，得到盲化后的密钥D。

步骤5、转换乘数的域

使用改进的蒙哥马利模乘器将密文M由自然域转换到蒙哥马利域，得到转换后的密文M’：

M’＝Mont(M,R^2,N)。

步骤6、随机并行的R-L模幂计算

将基数R与密文M’作为输入，使用两个改进的蒙哥马利模乘器并行计算R-L模幂环节中的模乘与模平方，根据以下公式进行模乘与模平方的计算：

R_r＝Mont(M’_r-1,R_r-1,N)；

M’_r＝Mont(M’_r-1,M’_r-1,N)；

其中，r＝1,2…length，R₀＝R，M’₀＝M’。

并在指数为“0”时，随机进行模平方的计算，防御简单功耗攻击和差分功耗攻击。

对每一比特计算完成后，得到结果result：

result＝R_length。

步骤7、转换结果的域

将步骤6得到的蒙哥马利域的结果result送入改进的蒙哥马利模乘器中，将result从蒙哥马利域转换成自然域，得到自然域的结果result’：

result’＝Mont(result,1,N)。

步骤8、冗余计算

将步骤7得到的自然域结果result’再次与模数N进行冗余计算，防御外部注入攻击。

步骤9、解密输出

完成上述解密与防御侧信道攻击的步骤后，改进的蒙哥马利模幂电路向外输出明文result’，完成IC卡密文M的解密。

本发明具有以下有益效果：

1、通过配置模式寄存器，可以根据不同场景的需求灵活改动解密信息的位宽长度，适用范围广，适用性强。

2、采用改进型的蒙哥马利模乘器作为核心部件，可以提高整个系统加解、密计算的性能，加快了计算速度。

3、提出双随机化防御侧信道攻击的方案，配合冗余计算，可以防御三种不同类型的攻击，提高安全性的同时，增加了系统的主频率，提高计算速度。

4、整个解密过程完全硬件实现，所有参数都通过硬件电路计算得到，减少系统复杂性的同时，克服了软件处理大数的运算速度比较慢的缺陷，提高了计算性能。

附图说明

图1为实施例中使用的防御多种侧信道攻击的蒙哥马利模幂电路框图；

图2为实施例中改进的蒙哥马利模幂器实现的状态跳转图；

图3为实施例中n’[0]计算模块。

图4(a)为实施中使用的开源加解密工具对比图；

图4(b)为实施例中解密结果的仿真波形图；

图4(c)为实施例中各个中间参数的仿真波形图；

图5为实施例中系统通过DC综合通过后的时序结果。

具体实施方式

以下结合附图对本发明作进一步的解释说明；

下表为本实施例的系统平台参数：

参数	实施条件
		系统硬件平台	Inter i5-9400
运行环境	Ubuntu 16.04
		编程语言	Verilog
仿真工具	VIVADO2019.1、modelsim2010

本实施例的硬件环境是CPU Intel(R)Core(TM)CPU i5-9400@2.90GHz，在Linux16.04系统下进行，实验手段包括开源加解密工具对比和仿真验证，开源工具为RSATool2v17，仿真工具包括VIVADO2019.1和modelsim2010。

如图1所示，为本实施例使用的改进的蒙哥马利模幂电路，包括改进的蒙哥马利模乘器、n’[0]计算模块、mont2计算模块、指数盲化模块、真随机数生成模块和模式寄存器模块。

现有技术中的蒙哥马利算法需要做大数乘法和大数加法，比如对1024bit的a,b,N,需要做1024x1024-bit乘法，和2048bit加法，并且其中间结果的位数也多达2048bits，消耗的硬件资源无法估量，不适合硬件方式实现，因此需要对其进行适当的优化。在实际应用中，对于大数运算，经常把数分割成多个字，即多精度数，每次只计算出部分值，而不是一次计算出原始算法中的u值。

如图2所示，改进的蒙哥马利模乘器在现有技术的基础上增加了一组寄存器，通过反复利用已定义的寄存器变量减少寄存器定义和使用的总量，同时通过重新排布流水线和算法时序，将关键路径的加法拆解为多拍的加法树操作，然后优化无依赖操作的方法，实现预计算环节与进位计算环节的并行处理，改进的蒙哥马利模乘器具体算法如下：

设计了128位的booth乘法器来减少运算需要的时钟数。并且对部分积生成电路进行改进，减少了部分逻辑门的使用。

准备待解密的IC卡密文M和密钥E，其解密位宽长度为length。

步骤1、参数预计算

1.1、向改进的蒙哥马利模乘器输入两个素数p、q，p与q乘积的位宽等于解密位宽长度length计算得到模数N与欧拉函数fan；

1.2、向n’[0]计算模块输入模数N，在固定周期数后得到输出的逆元的最低字n’[0]，图3为n’[0]计算模块的硬件电路图；

1.3、使用mont2计算模块计算参数R和mont2，用于后续的乘数域转换以及R-L模幂计算中；具体计算方法为：向mont2计算模块输入模数N，根据解密位宽长度length，将中间变量初始为2^r-1，经过一次循环得出R，两次循环得出mont2，最后mont2计算模块同时输出R和mont2。

1.4、将mont2计算模块计算得到的参数R输入改进的蒙哥马利模乘器计算得到参数R^2。

步骤三、加密计算

指数盲化模块根据真随机数生成模块产生的随机数随机选择1、2、4、8、16、32倍的欧拉函数fan，再将原密钥E与选择的随机倍数的欧拉函数fan进行分组相加，得到盲化后的密钥D。

步骤四、防御侧信道攻击

4.1、在密钥E盲化的过程中，通过Euler函数的推论并引入真随机数，使得每次解密过程中的密钥都不同，并且真随机数使得‘0’位的功耗也十分随机，有效防御差分功耗攻击。

4.2、使用两个改进的蒙哥马利模乘器并行‘0’和‘1’的模乘与模平方，即同时执行模乘和模平方，使得每一位的处理速度都是恒定的，防御计时攻击。并在指数为“0”时，随机进行模平方的计算，对密钥的‘0’位引入了随机性的伪操作以及伪赋值，使操作‘0’的功耗与操作‘1’的功耗除了硬件布局布线外完全一致，部分为‘0’的密钥位随机的执行模乘操作，让攻击者无法分析出哪一位是‘0’，有效抵抗简单功耗攻击。

4.3、对整个模幂模块最后的蒙哥马利域变换为自然域的步骤连续做了两次，并且在第二次反变换之前又计算了一次模数N的值，确保比较的正确性。引入了随机盲化密钥的方案后，使得密钥长度和过程中的功耗波动都变化较大，这样可以使得运算过程中想在第二次计算完模数N后再次进行注入攻击的时机难以确定。

如图4(a)所示，使用开源的RSA加密软件对字符串“hello world”进行加密，通过上述步骤可以将加密后的字符成功解密，如图4(b)所示；图4(c)为解密过程中模数N、欧拉函数fan、模数N的最低字n’[0]、基数R、常数2的蒙哥马利形式mont2以及基数R的平方的仿真波形图。

如图5所示，本方法中，电路主频可以达到600MHz，而现有技术中的单一侧信道防御功能的蒙哥马利模幂电路的主频一般在200-300MHz左右，本方法不仅实现了多种侧信道攻击的防御，提高了加密的安全性，还提高了电路的整体性能，提高运算速度。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员，在不脱离本发明构思的前提下，还可以做出若干改进和润色，这些改进和润色也应视为本发明保护范围内。

Claims (1)

1.基于改进的蒙哥马利模幂电路的IC卡解密方法，其特征在于：改进了蒙哥马利模幂电路，包括改进的蒙哥马利模乘器、n’[0]计算模块、mont2计算模块、指数盲化模块、真随机数生成模块和模式寄存器模块；所述改进的蒙哥马利模乘器将乘数A与被乘数B按照128-bits进行分组，具体计算过程如下：

s1.在外循环中对被乘数B进行遍历，将乘数A的最低组与被乘数B的每一组相乘，低128-bits放在S0中，高128-bits放在进位R0中；并对前一次内循环完成的两个高位R0和R1进行相加，低位放在S1，高位放至R0；

s2.将s1中得到的S0与模数N的欧拉函数最低组n’[0]相乘，将低128-bits赋值给中间值m；同时将1得到的S1与上级更新的结果t进行相加，低位放至S1，高位放至R1；

s3.将s2中得到的m与模数N最低组相乘，并与s1中的S0相加，得到新的S0，高位赋值给R0；同时将2中得到的S1赋值到结果t的次高组，R0+R1赋值给最高组；

s4.进入内循环，对a进行遍历，将a与b进行遍历乘法，并与s3中的R0和前一级得到的t的迭代值相加，得到新的S0和R0；

s5.在内循环中，将s3得到的m与遍历的模数n循环相乘，并于前级内循环的R1、S0相加，得到新的R1、S0；

s6.内循环最后，将t按组更新为S0；

解密方法具体包括以下步骤：

步骤1、系统输入

向所述蒙哥马利模幂电路输入加密后的IC卡密文M、解密位宽长度length、两个素数p、q和密钥E，p与q乘积的位宽等于解密位宽长度length；

步骤2、配置模式寄存器

根据解密位宽长度length对模式寄存器进行配置；

步骤3、预计算参数

3.1、根据素数p和q，使用改进的蒙哥马利模乘器计算模数N与欧拉函数fan；

3.2、使用n’[0]计算模块计算模数N的最低字n’[0]；

3.3、使用mont2计算模块计算基数R和常数2的蒙哥马利形式mont2；

3.4、将基数R和常数2的蒙哥马利形式mont2输入改进的蒙哥马利模乘器计算参数R^2；

步骤4、计算盲化的密钥

指数盲化模块根据真随机数生成模块产生的随机数随机选择1、2、4、8、16、32倍的欧拉函数fan，再将原密钥E与选择的随机倍数的欧拉函数fan进行分组相加，得到盲化后的密钥D；

步骤5、转换乘数的域

使用改进的蒙哥马利模乘器将密文M由自然域转换到蒙哥马利域，得到转换后的密文M’：

M’＝Mont(M,R^2,N)；

步骤6、随机并行的R-L模幂计算

将基数R与密文M’作为输入，使用两个改进的蒙哥马利模乘器并行计算R-L模幂环节中的模乘与模平方，根据以下公式进行模乘与模平方的计算：

R_r＝Mont(M’_r-1,R_r-1,N)；

M’_r＝Mont(M’_r-1,M’_r-1,N)；

其中，r＝1,2…length，R₀＝R，M’₀＝M’；

并在指数为“0”时，随机进行模平方的计算，防御简单功耗攻击和差分功耗攻击；

对每一比特计算完成后，得到结果result：

result＝R_length；

步骤7、转换结果的域

将步骤6得到的蒙哥马利域的结果result送入改进的蒙哥马利模乘器中，将result从蒙哥马利域转换成自然域，得到自然域的结果result’：

result’＝Mont(result,1,N)；

步骤8、冗余计算

将步骤7得到的自然域结果result’再次与模数N进行冗余计算，防御外部注入攻击；

步骤9、解密输出

完成上述解密与防御侧信道攻击的步骤后，改进的蒙哥马利模幂电路向外输出明文result’，完成IC卡密文M的解密。

Images