第3章_密码学基础 导读：就爱阅读网友为您分享以下“第3章_密码学基础”资讯，希望对您有所帮助，感谢您对92to.com的支持!计算系统与网络安全Computer System and Network Security电子科技大学 计算机科学与工程学院2013-7-26第3章密码算法 消息认证 数字签名 身份认证 访问控制 密钥管理2013-7-26密码学基础第3章密码算法 消息认证 数字签名 身份认证 访问控制 密钥管理2013-7-26密码学基础密码算法l密码算法分类密码算法 基于保密的内容 明文处理方法基于密钥保密性基于算法保密性分组密码算法流密码算法对称密码算法非对称密码算法对称密码学： DESAES2013-7-26非对称密码学：RSAECCDES明文IP L0第1轮 32位 32位 64位R048位f +K1L1第2轮32位32位R148位f +K2K加密L2第16轮32位32位R248位f +K16R1632位32位L16IP-12013-7-26密文64位其中： Li = Ri -1 Ri = Li -1 f (ki , Ri -1 )RSAl 1. 2. 3.4.5.6.算法概要： Bob选择保密的素数p和q，并计算n=pq； Bob通过gcd(e,(p-1)(q-1)=1来选择e； Bob通过de1(mod(p-1)(q-1)来计算d； Bob将n和e设为公开的，p、q、d设为秘密的； Alice将m加密为c me(mod n)，并将c发送给 Bob； Bob通过计算m cd(mod n)解密。2013-7-26RSA: 例11. 2. 3. 4. 5.6. 7.选择两个素数: p=17 & q=11 计算 n = pq =1711=187 计算 (n)=(p1)(q-1)=1610=160 选择 e : gcd(e,160)=1; 其中e=7 计算d: de=1 mod 160 且d 160 ，则 d=23 （因 为237=161= 10160+1） 公布公钥KU=7,187 保存私钥KR=23,17,112013-7-26RSA: 例1（续）l l l如果待加密的消息 M = 88 (注意： 88187) 加密：C = 887 mod 187 = 11 解密:M = 1123 mod 187 = 882013-7-26RSA: 例2llBob选择 p=885320693， q=238855417， 则可 以计算 n=p*q=211463707796206571， 设加密系数为 e=9007，将n和e发送给Alice。 假设Alice传递的信息是cat。 令a=01 c=03 t=20，则cat=030120=30120。 Alice计算：c me 301209007 113535859035722866(mod n) 她将c传给Bob。2013-7-26RSA: 例2（续）lBob已知p和q的值，他用扩展欧几里德算法计算d： de 1(mod(p-1)(q-1)， 得到 d=116402471153538991 然后Bob计算： cd 113535859035722866116402471153538991 30120(mod n) 由此他可以得到最初的信息。2013-7-26AESl算法概要：明文Xi 子密钥K0 r轮迭代Xi-1字节代替BS行移位SR 列混合MC Ki-1 Xi （b） 一轮AES结构密文Y（a）AES算法框图2013-7-26AES的设计原则：能够抵御已知攻击、硬 件实现容易且速度快、设计简单ECCl lll lECC: Elliptic Curve Cryptography 1985年，N.Koblitz及V.S.Miller分别提出了椭圆曲线 密码体制（ECC）。 已经开发出的椭圆曲线标准的文档有：IEEE P1363 P1363a、ANSI X9.62 X9.63、 ISO/IEC14888等 。 近年来，ECC已走向工程实现和实际应用阶段。 目前，德国、日本、法国、美国、加拿大等许多西 方国家的密码学研究小组和公司已经实现了椭圆曲 线密码体制。2013-7-26ECC（续）l为什么要提出ECC？lRSA 主要问题之一：l为了保证必要的安全强度，其密钥必须很长 在同等安全强度下，ECC所需密钥比RSA短lECC的优势：l2013-7-26ECC（续）lll椭圆曲线指的是由韦尔斯特拉斯（Weierstrass）方 程所确定的平面曲线 y 2 + a1 xy + a3 y = x 3 + a 2 x 2 + 。x + a 6 a4 其中，系数 a（i =1，2，6）定义在基域K上 i （K可以是有理数域、实数域、复数域，还可以是 有限域，椭圆曲线密码体制中用到的椭圆曲线都定 义在有限域上）。 椭圆曲线并非椭圆2013-7-26ECC（续）l群：l对于非空集合G，其上的一个二元运算（.）满足：封闭性、 结合率、单位元和可逆性 关于是一个交换群（群的条件交换率） 对于乘法x满足：ll环：对于R上的两个二元运算（+，x）满足：l l封闭性结合率分配率l域：对于F上的两个运算（+，x）满足l lF是一个整环：交换环乘法逆元无零因子 乘法逆元存在2013-7-26ECC（续） 域 整环 可交换环 环 可交换群 群 2013-7-26ECC（续）l椭圆曲线加法运算规则：O是加法的单位元，OO；对于椭 圆曲线上的任一点P，有POP l 点P的负元是与P具有现同x坐标和相反 y坐标的点，即若P（x，y），则-P （x，-y）；P（P)=O l 若P（x1，y），Q（x2，z），则 PQR。其中R是直线PQ与椭圆 曲线的第三个交点。 l 若P和Q的 x坐标相同，则为无穷远点 O l 若Q（x，y），则QQ2QS， 其中S为椭圆曲线在Q点的切线与椭圆 2013-7-26 曲线的另一交点。lP Q-(P+Q) R(P+Q)-RP+QPQR=-(P+Q）-R=P+QP+QS Q-S 2QECC（续）l有限域上椭圆曲线y2x3+ax+b mod p p是奇素数,且4a3+27b20 mod p （构成Abel群 的条件，证明过程略） y2+xyx3+ax2+b mod 2m(Galois 域的椭圆曲 线）2013-7-26ECC（续）l有限域上椭圆曲线y2x3+ax+b mod p（1） P+O=P（2）P=(x,y) P(x,y)=O 其中（x,-y) 是P的负元 P（3）加法公式: P=(xp,yp), Q=(xQ,yQ) 若xP=xQ且yP=-yQ则P+Q=O 否则 P+Q=(xR,yR) xR=l2-xP-xQ yR=l(xP-xR)-yP 其中 l=(yQ-yP)/(xQ-xP), 如果PQ l=(3xP2+a)/（2yP）， 如果P=Q(4)重复 相加： nP=P+ +P按照上述定义构成了一个椭圆曲线上的Abel群2013-7-26ECC（续）l示例：有限域上椭圆曲线y2x3+ax+b mod pl条件：a=1, b=1,x=9,y=7,p=23llly2 =72 mod 23=3 x3+ax+b=(93 +9+1) mod 23=3 y2x3+ax+b mod p2013-7-26ECC示例l示例：有限域上椭圆曲线y2x3+ax+b mod pl l条件：a=1, b=1,x=9,y=7,p=23 问题：l求满足上述方程的所有整数对（x，y）以及无 穷远点O组成的集合Ep（a，b） E23（1， 1）？2013-7-26ECC示例（续）E23（1，1）(0,1) (0,22) (6,4) (6,19) (12,19) (13,7)(1,7)(1,16) (3,10) (3,13) ( 4,0) (5,4)2013-7-26(7,11)(7,12) (9,7) (9,16) (11,3) (11,20)(13,16)(17,3) (17,20) (18,3) (18,20) (19,5)(5,19)(12,4)(19,18)ECC示例（续）E23（1，1）(0,1) (0,22) (1,7) (1,16) (3,10) (3,13) ( 4,0) (5,4) (5,19)2013-7-26(6,4) (6,19) (7,11) (7,12) (9,7) (9,16) (11,3) (11,20) (12,4)(12,19) (13,7) (13,16) (17,3) (17,20) (18,3) (18,20) (19,5) (19,18)1）P（0，1）， P+O（0，1） 2）P（13，7） -P=（13，-7） =(13,16) 3）P（3，10）， Q（9，7） P+Q=(17,20) 4）P（3，10） 2P=(7,12)ECC示例（续）lPQ计算过程： mod p ( P Q ) mod p ( P = Q ) x3=l2-x1-x2y3=l(x1-x3)-y1 其中 l=(y2-y1)/(x2-x1), 如果PQ l=(3x12+a)/2y1, 如果P=QP = (3,10), Q = (9, 7) yQ - yP xQ - x p Ql = 2 3 x P + a 2 y p 7 - 10 l = mod 23 = 11 9-3 xR = (l 2 - xP - xQ ) mod p = 17 yR = (l ( xP - xR ) - y p ) mod p = 202013-7-26ECC（续）l有限域上椭圆曲线ly2+xyx3+ax2+b mod 2m(Galois 域的椭圆曲线）（2）P=(x,y)P(x,y)=O 其