旁路分析原理与方法 第一.二章.doc

第一章 绪论1.密码学基础1.1 通信环境下的密码系统通过上图可以清楚地了解通信环境下的密码系统主要由明文、密文、密钥（包括加密密钥和解密密钥）、加密算法、解密算法五部分构成。发送者将明文、加密密钥作为加密算法的输入得到密文并发送给接收者，接收者解密密文后得到明文。1.2 密码学发展历程（1） 科学密码学的前夜发展时期： 该时期的密码技术还不是一种科学，密码学专家常凭直觉和信念进行密码设计和分析，而不是推理和证明。（2） 对称密码的早期发展时期： Shannon于1949年发表的保密系统的通信理论使密码编码至于坚实的数学基础上，为对称密码学建立了理论基础，标志着密码学学科的形成。然而对称密码算法双方必须约定使用相同密钥，密钥分配只能通过专用安全途径，密钥管理开销很大，对称密码在密钥分配上存在很大困难。 （3） 现代密码学的发展时期：1. 1976年Diffie和Hellman发表密码编码学新方向，提出公钥密码的概念。2. 1977年美国制定了数据加密标准DES（对称密码算法）。（4） 应用密码学的发展时期：1. 美国AES征集计划2. 欧洲NESSIE征集计划3. 欧洲eSTREAM征集计划4. 美国SHA-3征集计划1.3 传统密码分析（1） 分析假设：密码算法的安全性一般遵循Kirchhoffs准则。根据Kirchhoffs假设，密码系统的安全性应依赖于密钥的保密性，而不是密码算法的保密性。（2） 评估准则：密码算法安全性分析评估一般需要从分析复杂度（数据复杂度、时间复杂度、空间复杂度）、分析结果来衡量。（3） 分析方法：传统密码分析方法主要包括强力攻击和数学分析两种。其中强力攻击包括密钥穷举攻击、查表攻击和时间-空间权衡攻击。数学分析包括差分密码分析、线性密码分析、相关密码分析和代数分析。2. 密码旁路分析概述密码算法设计的安全性并不等同于密码芯片实现的安全性。密码算法的实现总是需要依附一个物理设备平台，即密码芯片。由芯片的物理特性产生的额外信息泄露称为旁路泄漏。这些泄露的信息同密码中间运算、中间状态数据存在一定相关性，可为密码分析提供更多信息，利用这些旁路信息进行密钥分析称为旁路分析。 从图1-2可看出，旁路分析中攻击者除了可在公开信道上截获信息，还可观测加密端的旁路泄漏，然后结合密码算法的设计细节进行密钥分析。1. 发展历程（1） 萌芽期：A 瞬态电磁脉冲辐射大核监测技术研究：贝尔电话公司工程师在进行加密电传终端贝尔电话131-B2调试时，发现电传终端每加密一个字母，调试台对面的示波器就会出现峰值波动，利用该峰值泄漏可将加密电传终端处理的信息转换成明文。进一步研究表明：在所有电子设备上进行信息处理时，都会产生电磁辐射，并可用于信息的还原。B. 声音分析技术研究：1956年，英国情报部门利用声音分析手段，执行了代号为“咽吞”的计划，通过监听手段来窃取密码机情报。（2） 提出期：1996年，学术界陆续有研究人员发现密码芯片存在旁路泄漏问题，并公开在会议和期刊上发表论文，不同类型的密码旁路泄漏被陆续发现并用于密钥分析。（3） 发展期：旁路分析技术飞速发展，各种方法蓬勃产生，旁路分析评估、防御和应用得到重视。（4） 鼎盛期：旁路信息采集：类型更多、速度更快、精度更高旁路分析方法：效率提高，并与数学分析结合起来旁路分析防御：走向设计方式科学化、实现方法灵活化、部署应用体系化旁路分析应用：广泛应用到新的信息安全领域，分析技术走向通用化、广泛化和交叉化 2基本原理 旁路泄漏同明文、密文和子密钥块具有相关性，攻击者可利用一定的分析方法恢复出子密钥块值，最终达到恢复主密钥值的目的。由图1-4可看出密码旁路分析可分为两个阶段：1. 泄漏采集阶段：获得实施密钥分析所需的旁路泄漏2. 泄漏分析阶段：利用采集的旁路泄漏，结合密码算法的输入、输出和设计细节恢复部分密钥片断，然后结合密钥扩展算法设计恢复主密钥。图1-4右上部分是攻击者通过示波器采集的AES执行第一轮16次查找S盒操作的功耗曲线，可看出存在16个明显的峰值，分别对应每次查找S盒操作。3.发展动因（1） 分析对象存在固有脆弱性A 设计安全性不等于实现安全性B 密码系统运行会产生旁路泄漏C 旁路泄漏同密码运算相关（2） 攻击者的能力超出预期（3） 测试计量手段越来越先进（4） 密码算法和芯片发展需要具备旁路分析能力4. 方法分类（1）旁路泄漏采集模式：主动分析：攻击者使用专用设备主动读取密码芯片运行的中间状态比特，并利用密码芯片故障输出进行密钥分析。被动分析：攻击者仅使用专用设备观测密码芯片运行过程中的旁路泄漏进行密钥分析，并不对密码芯片的运行过程进行主动干扰。（2）旁路泄漏采集手段：非侵入式分析：攻击者不需要对密码芯片接口进行破坏，只需要利用专用设备正常访问密码芯片接口，典型的方法包括:计时分析、功耗分析、电磁分析半侵入式分析：攻击者需要使用化学腐蚀等手段破坏密码芯片封装，典型方法包括：激光故障分析侵入式分析：攻击者需要在半侵入式分析基础上对密码芯片进行深一步的剖片，并使用探针读取密码设备运行过程中的中间状态比特，典型方法：探针分析。（3）旁路泄漏信息类型：计时分析、探针分析、故障分析、功耗分析、电磁分析、Cache分析，声音分析（4）旁路泄漏分析方法：简单旁路分析、差分旁路分析、相关旁路分析、模板旁路分析、随机模型旁路分析、互信息旁路分析、Cache旁路分析、差分故障分析、旁路立方体分析、代数旁路分析 第二章 数学基础一. 代数学1.1数论1. 基本概念：模运算：用给定整数n除两个整数a和b所得余数相同，则称a，b关于n同余，记为ab(mod n) 除数：和之前所学定义相同素数：在非负整数情况下，素数指只能被1和它本身整除的数离散对数：令=x(mod p)，求X的问题称为离散对数文题。最大公因子：当两个数除了1之外没有公因子，则两数互素。如果两整数a和n最大公因子（GCD）等于1，则记为GCD(a,n)=1欧拉函数：欧拉函数(m)表示比m小且与m互素的正整数个数。其满足两个性质：（1） m是素数时，(m)=m-1;（2） m=pq，且p和q均为素数时，有(m)=(p)X(q)=(p-1)(q-1)2. 基本定理： 费马定理：如果p是素数且a是不能被p整除的正整数，则ap-11(mod p) 欧拉定理：对于任何互素的整数a和n，有 a（n）1(mod n) 中国剩余定理：有时候在模运算时大数在运算时比较复杂，于是可以将大数分解成小数的形式进行运算。1.2 代数 1. 群、环、域的定义：三者从左至右存在包含的关系，定义条件越来越严苛。群包含一个集合G和一个定义在集合元素上的运算，环包含一个集合和两个定义在集合元素上的运算，域则是在环的条件下加入新的条件。 2. 有限域和域上的多项式：具有有限个元素的域，元素的个数称为域的阶。域F上的多项式可表示为 b(x)=bn-1xn-1+bn-2xn-2+b2x2+b1x+b0 式中，x称为多项式的变元；blF是多项式的系数。3. 汉明重量与汉明距离：汉明重量：x向量中非零分量的个数；汉明距离：x，y向量的差向量（异或）的汉明重量4. 布尔向量与布尔函数：布尔向量：在有限域GF(2)中，只有0和1两个元素，加法为模2下整数相加，乘法是模2下整数相乘，在GF(2)上取值的变量称为布尔变量。布尔函数：如果函数b=(a)将一个布尔向量映射为另外一个布尔向量，则称为布尔函数。 二 信息论2.1 信息和熵 密钥信息的度量常用不确定性（熵）来进行。对于密钥来说，熵的大小同信息的不确定性成正比。信息的不确定性越大熵越大。1. 自信息：离散随机变量X有n个可能取值xi，i=1,2，n。则事件X=xi的自信息定义为 I(xi)=log1p（xi）=-log(p(xi)2. 熵：离散随机变量X有n个可能取值xi，i=1,2，n。则该随机变量X的熵为所有取值的自信息乘以概率之和。3. 联合熵：对于两个离散变量X和Y，X有n个可能取值xi，i=1,2，n，Y有m个可能取值yj，j=1,2,m，则二者联合熵 H(X,Y)=-i=1nj=1mp(X=xi,Y=yj)log(P(X=xi,Y=yj)4. 条件熵：对于两个离散变量X和Y，其条件熵为H(x|y)=-i=1nj=1mP(X=xi|Y=yj)log(P(X=xi|Y=yj)2.2 互信息：互信息：对于两个随机变量X和Y，互信息I(X;Y)的大小反映了变量X和Y的统计依存度。I(X;Y)越大，则X和Y之间的统计关联性越强。 I(X;Y)= I(Y;X)=H(X)+H(Y)-H(X,Y)三 计算复杂性1. 算法的计算复杂度 时间复杂度，空间复杂度2. 问题复杂度 按照求解问题所需的时间，计算复杂性理论可将各种问题分为多类P类问题：可以在多项式时间内求解的问题NP类问题：可以在多项式时间内利用不确定性图灵机求解的问题四：概率论1. 事件与概率事件、样本空间：事件是指实验或观察的结果，简单事件又称样本点，样本点的全体称作样本空间。概率与条件概率：对于一个事件X，其中的样本点xi发生的概率，记为P(X=xi)，且满足 i=1nP(X=xi)此外，在事件为X的情况下，事件Y发生概率，即条件概率可记为 P(Y|X)=P(XY)P(X)分布函数：X是一个随机变量，则F(X)=PXx称为X的分布函数。2. 期望与方差期望：随机变量X取值的均值E(X)方差：随机变量X的取值偏离期望值E(X)的程度偏度：X统计分布的偏斜方向和程度峰度：衡量X统计分布的集中程度协方差：数学期望和方差反映随机变量自身的分布特征，协方差表示随机变量之间相互关系的数值特征。相关性系数：用来度量两个变量之间线性关系的方法3. 概率分布正态分布：对于随机变量，如果它的密度函数服从正态函数，则称该变量服从正态分布二元正态分布：对于两个变量，其密度函数服从正态函数，则两个变量服从二元正态分布。4. 中心极限定理：当样本数量足够大时，随机变量趋于正态分布五数理统计1. 参数估计极大似然估计：多元高斯分布是正态分布向更高维的扩展，可以通过协方差矩阵和均值刻画向量的发生概率。贝叶斯估计：在给定训练数据D时，确定假设空间的最佳假设。即对预先统计结果的利用。2. 假设检验t检验：分析两个不相关总体样本的平均值F检验：用于两个和两个以上样本方差差别的显著性检验存在问题：1. 对离散对数的深入理解？如果n满足1(mod p)的最小正整数，假设0xn，记x=L()，并称为与相关的的离散对数。扩展：给定一个质数p和有限域Zp上的一个本原元，对Zp上整数b寻找唯一整数C，使得Cb(mod p)。如果仔细选择p，则认为该问题难解，且目前还没有找到计算离散对数问题的多项式时间算法。2. 欧拉定理证明？方法一：令Zn=x1,x2,x(n)，S=a*x1 mod n,a*x2 mod n,a*