维普资讯 http://www.cqvip.com
毫一 研究与开发 智能卡ＲＳＡ算法ＤＰＡ的攻击与防御 靳济方，高献伟 （北京电子科技学院电子信息工程系北京１０００７０） 曝 已有的算法级防止ＤＰＡ攻击方法进行了研究，并在此基础上提出一种－Ｘ重掩盖法来全面防御 针对ＲＳＡ算法的ＤＰＡ攻击。且进行了仿真，效果明显。 １ 引言 ２ ＤＰＡ攻击原理 智能卡（ｓｍａｒｔ ｃａｒｄ）也称ＣＰＵ卡，不仅具有数据存储 ＤＰＡ是利用智能卡密码芯片运行时的能量信号与密 功能，还具有数据安全保护、复杂密码运算等功能。智能卡 码算法的密钥之间的相关性，运行多次密码算法就可以暴 采用ＲＳＡ算法作为公钥加密算法．但是智能卡在运行过 露出这种相关性嘲。ＤＰＡ的过程如下。 程中不可避免会泄露一些旁路信息，如能量、电磁波、时问 （１）收集能量消耗信息。攻击者监测密码芯片进行ｍ次 等，利用能耗信息对智能卡进行攻击能够达到很好的效 加密时的能量消耗曲线 们（ ＝１，２，…，ｍ；ｍ是进行加密 果，其危害远远大于传统的数学攻击手段。 运算的次数。 ＝１，２，…，ｋ；ｌｃ是每次测量能耗的采样点 １９９９年Ｐａｕｌ首次提出能量分析…，能量分析是指通过 数），同时记录每次运算后所得到的密文Ｃ ，Ｃ２，…， 。 采集智能卡加密芯片等硬件设备在进行加、解密或签名操 （２）分析信息。攻击者根据已知算法，设计一个与 作时产生的能量消耗信息，利用密码学、统计学原理，分析 密钥相关的区分函数Ｄ（Ｋ。，Ｃ）。其中，Ｋ。是假定的子密 和破译密钥信息的一种攻击方式。通常．可将能量分析攻 钥．Ｃ是密文。 击分为简单能量分析（ｓｉｍｐｌｅ ｐｏｗｅｒ ａｎａｌｙｓｉｓ，ＳＰＡ）攻击和 （３）根据假定的 和函数Ｄ的计算值，把能耗信号分 差分能量分析（ｄｉｆｆｅｒｅｎｔｉａｌ ｐｏｗｅｒ ａｎａｌｙｓｉｓ，ＤＰＡ）攻击两类， 成两类： 其中ＤＰＡ是目前非常快速而有效的攻击方法。所以近年 Ｔｏ＝｛ ］｛Ｄ＝０｝，Ｔ１＝｛ ］｛Ｄ＝Ｉ｝， 来针对ＤＰＡ的各种防御方法成为研究的热点。 ∑ ∑ 令△Ｄ ］－ 一 北京电子科技学院信息安全与保密重点实验室基金项目 （Ｎｏ．ＹＺＤＪＯ６０５） 如果Ｋ 假设不正确，则ＡＤＯ＇ｌ＝０；如果Ｋ 假设正确， 维普资讯 http://www.cqvip.com
研究与开发 则ＡＤⅡ］≠０。正确的 可以从ｋ次采样的差分曲线 ＡＤ［１，２，…， ］出现明显的突变来判断。 ３ 算法级ＤＰＡ攻击ＲＳＡ ３．１算法级ＤＰＡ攻击ＲＳＡ的思想 模幂运算是ＲＳＡ中最根本的运算，模幂运算可以分 解成多个模平方运算和模乘运算，进行模平方运算和模 乘运算所消耗的能量是有差别的。ＤＰＡ攻击ＲＳＡ的主要 思想是利用ＲＳＡ算法平方运算和乘法运算能耗的明显 不同，考虑到噪声对能耗轨迹的干扰，采用均值和差分 的统计运算不断修正能耗轨迹，同时利用设计合理的区 分函数将猜想私钥的比特位对应的能耗轨迹分类，最终 获得私钥指数的比特位信息。 ３．２算法级ＤＰＡ攻击ＲＳＡ的主要方法 根据攻击的前提条件不同，ＤＰＡ攻击ＲＳＡ的方法主 要为以下两类。 （１）获得已知公钥指数前提下的ＤＰＡ攻击 根据ＩＳ０７８１６标准【２１．智能 的使用者可通过手册获 得卡的公钥指数值．可以运行“外部认证”指令使用公钥指 数进行加密操作．可以对任意输入运行“内部认证”指令使 用私钥指数进行签名操作。 此攻击方法就是取大量的随机数让智能卡进行签名和 加密运算。根据公钥推出私钥。假设随机数个数为 ，在 时 刻，智能卡对第ｋ个随机数用私钥指数进行签名的能耗为 ］，用公钥指数进行加密的能耗为 ］，计算能量差分 信号： Ｄ ］＝ ∑Ｓ儿 ＝Ｉ ｎ ｌ＿∑ ］ｋ＝Ｉ 在 时刻，若Ｄ［ ＝０则私钥与公钥在 ．时刻进行相同 的运算，若Ｄ［Ｉ：］≠０则私钥与公钥在 时刻进行相反的运 算。由此结果得到私钥在各个采样点的运算表，根据运算 表得到私钥指数比特位值的对应，从而得到私钥。 （２）根据假设私钥猜测ＲＳＡ私钥的ＤＰＡ攻击 此方法是通过比较真正私钥和攻击者假设私钥对同 一输入进行模幂运算操作时的能耗轨迹，逐位地比较和修 正假设私钥，最终获得真正私钥的信息。过程如下［３１４１： 假设Ｋ 为攻击者假设的私钥，５ ］为智能卡对输入进 行签名时的能耗，ｉ为Ｋ 的第ｉ比特。设Ｋ 为ｌ时，采集的 能耗信号为Ｓ。 １，为０时，采集的能耗信号为Ｓｏ ］，分别 计算两个差分信号： Ｄｏｂ；＝ｓｂ．］－ｓｏ ］， Ｄ。 ］＝５ ］一Ｓ。 ］ 若Ｄ０ ］：０则私钥的第ｉ位是０；若Ｄ。 ］＝０，则私钥的 第ｉ位是１。不断进行此推测，不断修正假设密钥 ，最终 得到真正的密钥。若采集的样本足够多，此法比第一种方 法具有更好的信噪比和攻击效果。 ４算法级防御ＤＰＡ攻击的方法 针对上述算法级攻击方法，目前有几类算法级防范 ＤＰＡ攻击的方法，防御思想都是：消除或减少算法操作数 特征，消除算法执行过程中的操作数和中间值与能耗之间 的对应关系。大致可以分为以下几类。 （１）减小信号强度。减小信号强度的主要实现方法包 括算法执行连续编码，选取小能耗运算指令，均衡汉明重 量。算法执行连续编码可以防止ＤＰＡ判断不同算法的起始 点和结束点．不提供有价值的算法信息；选取小能耗运算 的实现思想是用不易产生显著能耗变化的指令取代一些 原始指令，使指令的能耗减小及不同指令的能耗趋于平 衡：均衡汉明重量可使数据以原码和反码两种形式表示， 避免通过汉明重量与能耗的直接关系泄露能量信息。 （２）增加随机噪声。通过引入随机噪声，使得有用的信 号完全淹没于无用的噪声中，从而增加能量攻击的难度。 但是．这种方法不能从根本上解决问题：其一，攻击者可以 通过有效的滤波，消除这种干扰；其二，ＤＰＡ本身在做统计 平均时就削弱了噪声的影响。 （３）数据随机化掩盖。可分为明文随机化掩盖和指数 随机化掩盖两类，分别通过数算的变换与反变换，使 ＲＳＡ算法中的操作数均为经过～定随机化变形的替代数。 仅通过能量差分运算得不到真实的差异点位置．这为真实 算法做了掩盖，达到防御ＤＰＡ攻击的目的。但是这两种方 法实际上起不到有效的效果，因为从算法上讲平方运算比 乘运算要少近一半的指令．因此平方和乘运算消耗的能量 会有很大的差异．而如果仅仅是操作数不同，运算所执行 的乘和平方的数量不变，这样所带来的能量变化的干扰基 本上可以忽略，这两种掩盖仍不能完全掩盖操作指令的真 实能耗轨迹，攻击者可以通过其平方运算或乘法运算的不 同运算指令的能耗轨迹，获取算法运行的内部信息，再结 合其他攻击手段进行攻击。 ５三重掩盖法 为了弥补上述方法的不足，本文在对ＲＳＡ算法中最 重要的模幂算法进行数据随机化掩盖的基础上，提出一 维普资讯 http://www.cqvip.com
种新的防御ＤＰＡ攻击的方法。设计一个与智能卡进行平 方或乘法运算时的能耗相当的无效算法，在对原模幂算 法进行明文随机化掩盖和指数随机化掩盖的基础上．在 平方和乘法运算指令间加入随机的指令，进行“伪装”。 该算法同样进行真实的平方或乘法运算，运算结果写入 内存，从而使其能耗与算法中产生作用的指令的能耗相 近、轨迹相似，达到掩盖运算能耗轨迹的目的。这样就在 明文、指数和运算指令３个方面对ＤＰＡ攻击进行了全面 防御。防御ＤＰＡ攻击的三重掩盖的ＲＳＡ模幂改进算法 如下。 输入：明文ｍ，对明文进行掩盖和恢复的随机数字对（ ）（其中明文随机数为正整数ｎ，指数ｅ＝（ｅ ｅ …，ｅ。ｅ ＝ ） （ｍｏｄ ｎ），进行指数随机化运算的随机数ｒ’指令掩 盖的随机数，ｖ＝（Ｍ一 Ｎｋ－２＂＇＂Ｎｏ） ，ｋ＞３ｔ。 输出：ｍ￣（ｍｏｄ／２）。 （１）明文随机化掩盖预计算：ｍ ＝ｍｙ （ｍｏｄ ｎ） 指数随机化掩盖预计算：ｅ ＝ｅ＋ｒ ｆ２／）。 （２）初始化 ＝０。 （３）５ １。 （４）对ｉ从ｔ一１依次到０，执行： ①｛ｉｆＮｋ＝ｌ ｒｕｎ Ａ ； 如果 １，运行无效的平方运算｛／ ｅｌｓｅ ｒｕｎ Ａ ； 否则，运行无效的乘法运算｛／ ｋ＋＋；１ ②ｓ￣ｓｓ（ｍｏｄ／２）；厂丰执行模平方运算 ／ ⑧｛ｉｆ Ｍ＝１ ｒｕｎ Ａ ； ｅｌｓｅ ｒｕｎ Ａ ； ｋ＋＋；１ ④如果ｅｉ＂＝１，则５—５ｍ（ｍ０ｄ ｎ） 执行模乘运算 ／ ⑧ｆｉｆ ＝１ ｒｕｎ Ａ ； ｅｌｓｅ ｒｕｎ Ａ ； ｋ＋＋；１ （５）Ｓ ｄ５（ｍｏｄ ｎ）。 （６）返回５。 其中，步骤（３）和（４）的②、④为原来的ＲＳＡ模幂运算， 步骤（４）中的①、③、⑤均为加入的随机掩盖指令，其中Ａ 、 Ａ 为与真实平方运算、乘法运算能耗相当的无效运算。这 样，加入的无效算法在每次的模乘和模加运算后都进行了 ｊ ０ 礴潦 掩盖，真实运算能耗与无效运算能耗相互交织，能量分析攻 击无法判断真伪．达到了有效地防御ＤＰＡ的目的。图１为采 用三重掩盖算法后的仿真能耗轨迹，可见，差分后的能量轨 迹无明显的尖峰出现，攻击者不能通过滤波或统计的方法 获得实际的能耗信息 私钥信息得到有效保护。 （ｍｓ） ０ ４８ ９７ ｌ４５ ｌ９４ ２４２ ２９ｌ ３３０ ３８８ 图１ 采用三重掩盖算法后的能耗轨迹仿真 参考文献 １ Ｋｏｃｈｅｒ Ｃ Ｐ，Ｊａｆｆｅ Ｊ，Ｊｕｎ Ｂ．Ｄｉｆｆｅｒｅｎｔｉａｌ ｐｏｗｅｒ ａｎａｌｙｓｉｓ． Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １９ｔｈ Ａｎｎｕａｌ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｒｙｐｔｏｌｏｇｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ，Ｂｅｒｌｉｎ，Ａｕｇｕｓｔ １９９９ ２ Ｍｅｓｓｅｒｇｅｓ Ｔ Ｓ，Ｄａｂｂｉｓｈ Ｅ Ａ，Ｓｌｏａｎ Ｒ Ｈ．Ｅｘａｍｉｎｉｎｇ ｓｍａｒｔ ｃａｒｄ ｓｅｃｕｒｉｔｙ ｕｎｄｅｒ ｔｈｅ ｔｈｒｅａｔ ｏｆ ｐｏｗｅｒ ａｎａｌｙｓｉｓ ａｔｔａｃｋｓ．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｐｕｔｅｒｓ，２００２（５）：５４１￣５５２ ３李欣，范明钰．能量分析攻击与防御策略研究．信息安全与通信 保密，２００５（７）：１０５～１０７ ４ Ｗａｌｔｅｒ Ｄ Ｃ．ＭＩＳＴ：ａｎ ｅｆｆｉｃｉｅｎｔ，ｒａｎｄｏｍｉｚｅｄ ｅｘｐｏｎｅｎｔｉａｔｉｏｎ ｌａｇｏｒｉｔｈｍ ｆｏｒ ｒｅｓｉｓｔｉｎｇ ｐｏｗｅｒ ａｎａｌｙｓｉｓ．Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｃｒｙｐｔｏｇｒａｐｈｅｒ Ｓ Ｔｒａｃｋ ａｔ ｔｈｅ ＲＳＡ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｔｏｐｉｃｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ，Ｓａｎ Ｊｏｓｅ，Ｆｅｂｒｕａｒｙ ２００２ ５ Ｍｅｓｓｅｒｇｅｓ Ｔ Ｓ，Ｄａｂｂｉｓｈ Ｅ Ａ，Ｓｌｏａｎ Ｒ Ｈ．Ｐｏｗｅｒ ａｎａｌｙｓｉｓ ａｔｔａｃｋｓ ｏｆ ｍｏｄｕｌｒａ ｅｘｐｏｎｅｎｔｉａｔｉｏｎ ｉｎ ｓｍａｒｔ ｃａｒｄｓ．Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ｔｈｅ Ｗｏｒｋｓｈｏｐ ｏｎ Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ， Ｗｏｒｃｅｓｔｅｒ，Ａｕｇｕｓｔ １９９９ ６ Ｎｏｖａｋ Ｒ．ＳＰＡ．ｂａｓｅｄ ａｄａｐｔｉｖｅ ｃｈｏｓｅｎ．ｃｉｐｈｅｒｔｅｘｔ ａｔｔａｃｋ ｏｎ ＲＳＡ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ．Ｉｎ：ＰＫＣ ２００２，Ｐａｒｉｓ，Ｆｅｂｒｕａｒｙ ２００２ ７ Ｍａｎｇｅｒ Ｊ．Ａ ｃｈｏｓｅｎ ｃｉｐｈｅｒｔｅｘｔ ａｔｔａｃｋ ｏｎ ＲＳＡ．Ｏｐｔｉｍａｌ Ａｓｙｍｍｅｔｉｒｃ Ｅｎｃｒｙｐｔｉｏｎ Ｐａｄｄｉｎｇ（ＯＡＥＰ１ ａｓ Ｓｔａｎｄａｒｄｉｚｅｄ ｉｎ ＰＫＣＳ＃ｌ ｖ２．０．ＣＲＹＰＴＯ ２００１，２００１ ８ Ｋｌｉｍａ Ｖ，Ｒｏｓａ Ｔ．Ｆｕｒｔｈｅｒ ｒｅｓｕｌｔｓ ａｎｄ ｃｏｎｓｉｄｅｒａｔｉｏｎｓ ｏｎ ｓｉｄｅ ｃｈａｎｎｅｌ ａｔｔａｃｋｓ ｏｎ ＲＳＡ．Ｉｎ：ＣＨＥＳ ２００２，Ｓａｎ Ｆｒａｎｃｉｓｃｏ Ｂａｙ， Ａｕｇｕｓｔ ２００２ （收稿日期：２００８—０６—１８）
