ch 2 非对称加密算法.ppt

非对称加密算法 前情提要 数论基础 加密系统中常用的数论知识 复杂性理论简介 对称加密算法 对称密码体制模型 流密码 分组密码 DES Rijndael密码体制（AES加密算法） 本次课提纲 对称加密算法 KASUMI分组密码 非对称加密算法 RSA加密体制 椭圆曲线密码体制 对称加密算法 KUSAMI分组密码 KUSAMI算法是日本三菱公司在MISY1密码基础上改进产生的分组密码； 用于第三代移动通信系统的信令和数据加密。 是一个迭代分组密码算法，使用一个128bit的密钥加密一个长度为64bit的明文，获得长度为64bit的密文。 KASUMI算法 KUSAMI－非线性盒子S7 KUSAMI－非线性盒子S9 KASUMI轮密钥 需要8个轮密钥，每轮密钥RKi为128位 RKi=KLi||KOi||KIi=KLi1||KLi2||KOi1||KOi2||KOi3||KIi1||KIi2||KIi3 轮密钥取值表 KASUMI算法分析 主算法由线性混合函数FL和非线性混合函数FO组成； 非线性混合函数的非线性部分为FI，FI也是KASUMI函数惟一的非线性变化； 非线性盒子S7和S9是整个非线性子函数FI的核心，也是KASUMI算法的核心，它的强度就决定了密码算法的强度； S盒的设计准测包括非线性度、差分均匀性、代数次数及项目分布、雪崩效应和完全性、扩散性、可逆性以及是否有陷门等多方面来考虑; 非对称加密算法 非对称密钥加密算法 加密系统的加密和解密分别采用不同的密钥实现，且不可能互相导出，则称为非对称密钥体制； 一对密钥分为公钥私钥，公钥用来加密，私钥用于解密，公钥是公开的，密钥是用户自己秘密保存。信息发送者利用接收者的公钥对数据进行加密，然后发送给接收者，接收者使用自己的私钥进行解密； 优点：密钥管理相对简单，可以实现数字签名，从而实现不可抵赖的安全目标； 缺点：为了达到足够的安全强度， 需要增加密钥长度，运算速度和 处理效率较低，不适用处理能力 有限的情况； 典型算法：RSA（大质数分解） ECC（离散对数计算） RSA算法 密钥生成： 选取两个素数p,q； 计算模数n=pq； 随机选取加密密钥e,有e与 (p-1)(q-1)互素； 计算d*e=1 mod ((p-1)(q-1))； 公开密钥为(e,n)，私钥为d； 加解密： 加密：c=me mod n； 解密：m=cd mod n； 其中c为密文，m为明文； 数字签名： 签名：s=md mod n； 验证：m=se mod n； 其中s为签名，m为验证明文； 同密钥长度，软件实现比DES慢100倍，硬件实现慢1000倍。 椭圆曲线ECC加密算法 从平行线谈起 平行线，永不相交。真的吗？ 平行线会不会在很远很远的地方相交了？ 可以假设平行线在很远很远的地方相交了。即平行线相交于无穷远点P∞。 直线上出现P∞点，所带来的好处是所有的直线都相交了，且只有一个交点。这就把直线的平行与相交统一了。 无穷远点性质： 直线L上的无穷远点只能有一个； 平面上一组相互平行的直线有公共的无穷远点； 平面上任何相交的两直线L1,L2有不同的无穷远点； 平面上全体无穷远点构成一条无穷远直线； 平面上全体无穷远点与全体平常点构成射影平面。 射影平面坐标系 为了表示无穷远点，产生了射影平面坐标系，它是对普通平面直角坐标系的扩展。 对普通平面直角坐标系上的点A的坐标(x,y)做如下改造：令x=X/Z ，y=Y/Z(Z≠0)；则A点可以表示为(X:Y:Z)变成了有三个参量的坐标点，这就对平面上的点建立了一个新的坐标体系。 新的直线方程：aX+bY+cZ=0，平行直线的方程是：aX+bY+c1Z =0； aX+bY+c2Z =0? (c1≠c2)； 有c2Z= c1Z= -(aX+bY)，∵c1≠c2 ∴Z=0? ∴aX+bY=0； 无穷远点就是这种形式（X:Y:0）表示。注意，平常点Z≠0，无穷远点Z=0，因此无穷远直线对应的方程是Z=0。 椭圆曲线 椭圆曲线上一点斜率 问题：椭圆曲线方程y2+a1xy+a3y=x3+a2x2+a4x+a6上，平常点A(x,y)的切线的斜率k： 椭圆曲线上的加法 运算法则：任意取椭圆曲线上两点P、Q （若P、Q两点重合，则做P点的切线）做直线交于椭圆曲线的另一点R’，过R’做y轴的平行线交于R。我们规定P+Q=R。 椭圆曲线上加法详解 这里的+不是实数中普通的加法，而是从普通加法中抽象出来的加法，具备普通加法的一些性质，但具体运算法显然与普通加法不同。 根据这个法则，可以知道椭圆曲线无穷远点O∞与椭圆曲线上一点P的连线交于P’，过P’作y轴的平行线交于P，所以有无穷远点