公钥密码体制及典型算法-椭圆曲线密码体制.

密钥
为公钥。 不再需要， 以n，e为公钥。私密钥为d。(p, q不再需要， 可以销毁。 可以销毁。)
RSA算法在计算上的可行性
加密和解密
无论是加密还是解密都需要计算某个整数的模n 整数次幂，即C=Me mod n、M=Cd mod n。但不 、 需要先求出整数的幂再对n取模，而可利用模运 算的性质： (a mod n) * (b mod n)= (a*b) mod n 对于Me mod n，可先求出M1 mod n，M2 mod n， M4 mod n……，再求Me mod n
RSA算法 RSA算法
RSA Algorithm
概况
MIT三位年轻数学家, 1979年发现了一种用数 论构造双钥的方法，称作MIT 体制 MIT体制 MIT 体制，后来被 广泛称之为RSA体制 RSA体制 RSA体制。 它既可用于加密、又可用于数字签字。 RSA算法的安全性基于数论中大整数分解的 困难性。 迄今为止理论上最为成熟完善的公钥密码体 制，该体制已得到广泛的应用。
公钥密码体制有4个组成部分
明文：算法的输入，它们是可读信息或数据，用M 表示； 密文：算法的输出。依赖于明文和密钥，对给定的 消息，不同的密钥产生密文不同。用E表示； 公钥和私钥：算法的输入。这对密钥中一个用于加 密，为Ke，此密钥公开；一个用于解密，为Kd，此 密钥保密。加密算法执行的变换依赖于密钥； 加密、解密算法
选p=7，q=17。 求n=p×q=119，φ(n)=(p-1)(q-1)=96。 取e=5，满足1<e<φ(n)，且gcd(φ(n),e)=1。确 定满足d·e=1 mod 96且小于96的d，因为 77×5=385=4×96+1，所以d为77。 因此公开钥为{5，119}，秘密钥为{77，119}。 设明文m=19，则由加密过程得密文为 C=195 mod 119≡2476099 mod 119=66 解密为6677mod 119=19

首次公开提出了“公开密钥密码编码学”的概念。
这是一个与对称密码编码截然不同的方案。
提出公开密钥的理论时，其实用性并没有又得到证明：
❖ 当时还未发现满足公开密钥编码理论的算法； ❖ 直到 1978 年，RSA 算法的提出。
2.基本特征
❖ 加密和解密使用两个不同的密钥 公钥PK：公开，用于加密，私钥SK：保密，用作解密 密钥
3.优点
❖ 密钥管理
加密密钥是公开的； 解密密钥需要妥善保存； 在当今具有用户量大、消息发送方与接收方具有明显的信息不对称
特点的应用环境中表现出了令人乐观的前景。 新用户的增加只需要产生一对公共/私有密钥。
❖ 数字签名和认证
只有解密密钥能解密，只有正确的接收者才拥有解密密钥。
缺点：公共密钥系统的主要弱点是加密和解密速度慢。
加密与解密由不同的密钥完成； 知道加密算法，从加密密钥得到解密密钥在计算上是不可行的； 两个密钥中任何一个都可以作为加密而另一个用作解密。
6.公钥密码算法
除RSA算法以外，建立在不同计算问题上的其他公钥密码算法 有：
基于因子分解问题的Rabin算法； 椭圆曲线公钥算法； 基于有限域中离散对数难题的ElGamal公钥密码算法 基于代数编码系统的McEliece公钥密码算法； 基于“子集和”难题的Merkle-Hellman Knapsack（背包）公钥密码算 法； 目前被认为安全的Knapsack型公钥密码算法Chor-Rivest。
实际应用中的加密方式
❖ 混合加密技术 对称密码体制：密钥分发困难 公钥体制：加解密效率低 将对称加密算法的数据处理速度和公钥算法对密钥的保 密功能相结合 利用对称加密算法加密传输数据 利用非对称加密算法交换会话密钥
实际应用中的加密方式

ｐ
果有，就有两个满足平方根运算的ｙ值（除非这个值是单个的ｙ值 零）。这些（ｘ，ｙ）值就是Ｅ （ａ，ｂ）中的点。
ｐ
（２）椭圆曲线上点的周期计算 ①选取椭圆上一点ｑ（ｘ ，ｙ ）；
００
②计算 ｑ＋ｑ＋…＋ｑ，使得 ｎｑ＝０ 成立的最小值 ｎ，若 ｙ ＝０，则 ０
此点无周期。 （３）检测 ｎ 是否是素数，如果不是，再回到第（２）步。 采用Ｍｉｌｌｅｒ－Ｒａｂｉｎ随机性素数测试算法：
56
２００４．１１
加 密 技 术
２．１ 椭圆曲线密码体制思想
选取基域 Ｆ ，选择一条椭圆曲线（ａ，ｂ，ｐ值给定），在Ｅ（Ｆ ）中
ｑ
ｑ
选一个周期很大的点，如选了一个点 Ｇ＝（ｘ ， ｙ ），它的周期为一
Ｇ
Ｇ
个很大的素数 ｎ，记为∏（ｐ）＝ｎ（ｎ 为素数）。在椭圆曲线密码体制
①将 ｎ－１ 表示为二进制形式 ｂ ｂ …ｂ ；
④依据 Ｂｏｂ 的公钥计算点（ｘ ， ｙ ）＝ｋＧ（ｋ 个 Ｇ 相加）；
１
１
⑤计算点（ｘ ， ｙ ）＝ｋＱ，如果 ｘ ＝０，则回到第③步；
２
２
２
⑥计算 Ｃ＝ｍ＊ｘ ； ２
⑦传送加密数据（ｘ ， ｙ ，Ｃ）给Ｂｏｂ。
１
１
（２）Ｂｏｂ的解密过程
（阶）。经过计算得 ｎ＝２２３。 经过上面算法的验证，得知 ｎ＝２２３ 是一个素数，所以点 ｖ 可
在用序列密码对媒体流加密时，网络数据包的大小可以根据 网络的需要来设定，与分组加密不同，这里需要考虑的仅仅是网 络传输的需求。
整个加密过程是：播放过程一旦开始，密钥流生成器就不断 地产生出密码序列，服务器也周期性地发送网络数据包。在数据 流化的过程中，将随机数序列与数据包中的明文序列进行逐位

F2m上椭圆曲线的点的加法逆元
• P = (xP, yP)的加法逆元 -P = (xP, xP + yP) • P + (-P) = O • P+O=P
F2m上椭圆曲线不同的点的加法运算
P = (xP, yP) 。如果 P和 Q是不同的点并且P不等于 -Q, 则P + Q = R
s = (yP - yQ) / (xP + xQ) xR = s2 + s + xP + xQ + a yR = s(xP + xR) + xR + yP
F上的椭圆曲线 2m
定义： 对于曲线
y2 +xy= x3 + ax2 + b b不为0，a,b 属于 F2 m
的解的集合构成
F2m 上的椭圆曲线群。记为 E ( F m )
2
F2m上的椭圆曲线举例
• 作为一个简单的例子, 考略 F2 4 , 其上的不可约多项式为 f(x) = x4 + x + 1. • 元素g = (0010)是生成元. • g的幂为: g0 = (0001) g1 = (0010) g2 = (0100) g3 = (1000) g4 = (0011) g5 = (0110) g6 = (1100) g7 = (1011) g8 = (0101) g9 = (1010) g10 = (0111) g11 = (1110) g12 = (1111) g13 = (1101) g14 = (1001) g15 = (0001)
例题
椭圆曲线T=(m=4,f(x)=x4+x+1,g=0010,a=g4,b=g0) 点P=(g6,g8) 求点R=2P

算法参数与辅助函数 综述
1
公钥加密算法规定发送者用接收者的公钥将消息加密成密文， 接收者用自已的私钥对收到的密文进 行解密还原成原始消息。 3.2 椭圆曲线系统参数 椭圆曲线系统参数包括有限域 Fq 的规模 q(当 q = 2m 时，还包括元素表示法的标识和约化多项式)； 定义椭圆曲线 E(Fq)的方程的两个元素 a、b ∈Fq；E(Fq)上的基点 G = (xG, yG) (G ≠ O)，其中 xG 和 yG 是 Fq 中的两个元素；G 的阶 n 及其它可选项(如 n 的余因子 h 等)。 椭圆曲线系统参数及其验证应符合 SM2 椭圆曲线公钥密码算法第 1 部分第 4 章的规定。 3.3 用户密钥对 用户 B 的密钥对包括其私钥 dB 和公钥 PB=[dB]G。 用户密钥对的生成算法与公钥验证算法应符合 SM2 椭圆曲线公钥密码算法第 1 部分第 5 章的规定。 3.4 辅助函数 3.4.1 概述 本部分规定的椭圆曲线公钥加密算法涉及到三类辅助函数： 密码杂凑算法、 密钥派生函数和随机数 发生器。这三类辅助函数的强弱直接影响加密算法的安全性。 3.4.2 3.4.3 密码杂凑算法 密钥派生函数 本部分规定使用国家密码管理局批准的密码杂凑算法，如 SM3 密码杂凑算法。 密钥派生函数的作用是从一个共享的秘密比特串中派生出密钥数据。 在密钥协商过程中， 密钥派生 函数作用在密钥交换所获共享的秘密比特串上，从中产生所需的会话密钥或进一步加密所需的密钥数 据。 密钥派生函数需要调用密码杂凑算法。 设密码杂凑算法为 Hv( )，其输出是长度恰为 v 比特的杂凑值。 密钥派生函数 KDF(Z, klen)： 输入：比特串 Z，整数 klen(表示要获得的密钥数据的比特长度，要求该值小于(232-1)v)。 输出：长度为 klen 的密钥数据比特串 K。 a)初始化一个 32 比特构成的计数器 ct=0x00000001； b)对 i 从 1 到 ⎡klen / v ⎤ 执行： b.1)计算 Hai=Hv (Z || ct)； b.2) ct++； c)若 klen/v 是整数，令 Ha!⎡klen / v ⎤ = Ha ⎡klen / v ⎤ ， 否则令 Ha!⎡klen / v ⎤ 为 Ha ⎡klen / v ⎤ 最左边的 (klen d)令 K = Ha1 || Ha2 || ! || Ha ⎡klen / v ⎤−1 || Ha!⎡klen / v ⎤ 。 3.4.4 随机数发生器 本部分规定使用国家密码管理局批准的随机数发生器。 4 加密算法及流程

定义Z 为小于n的所有非负整数集合 定义 n为小于 的所有非负整数集合 Zn={0,1,2,…,n-1}
4.1.4 费尔玛定理和欧拉定理
费尔玛定理： 费尔玛定理： 是素数， 是正整数且gcd(a,p)=1 gcd(a,p)=1， 若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1 mod p • 证明： 证明： 当gcd(a,p)=1,则a×Zp=Zp 。 则 × 又因为a× 所以a× 又因为 ×0≡0modp,所以 ×(Zp-{0})=Zp-{0} 所以 即：{a mod p,2a mod p,…,(n-1)a mod p} ={1,…,p-1} (a mod p) ×(2a mod p) ×…×(n-1)a mod p=(p-1)!ap-1 mod p × 因此： 因此：(p-1)! ap-1 mod p =(p-1)!modp (p-1)!与p互素，所以乘法可约律，ap-1=1 mod p 与 互素 所以乘法可约律， 互素，
的公因子。 由d|a和d|kb，得d|(a mod b)， 故d是b和a mod b的公因子。 和 ， ， 是 和 的公因子 a,b以及 以及b,a mod b公因子集合相同，故最大公因子也相同。 公因子集合相同， 以及 公因子集合相同 故最大公因子也相同。 gcd(55,22)=gcd(22,11)=gcd(11,0)=11 gcd(11,10)=gcd(10,1)=1
第4章 公钥密码
密码学中常用的数学知识 公钥密码体制的基本概念 RSA算法 椭圆曲线密码体制
4.1.1 群、环、域
<G,*>的定义 的定义: 群<G,*>的定义
*为乘法时，称为乘法群 逆元（a-1） 为乘法时， 逆元（ ） 为乘法时 *为加法时，称为加法群 逆元（-a） 为加法时， 逆元（ ） 为加法时

U htA (PB x2RB ) h(d A x1rA )(dBG x2rBG)=h(d A x1rA )(dB x2rB )G=(xU , yU )
V htB (PA x1RA ) h(dB x2rB )(d AG x1rAG)=h(dB x2rB )(d A x1rA )G=(xV , yV )
KB KDF(xV || yV || Z A || ZB ,klen) SB Hash(0x02 || yV || HASH (xV || Z A || ZB || x1 || y1 || x2 || y2 )) S2 Hash(0x03|| yV || HASH (xV || Z A || ZB || x1 || y1 || x2 || y2 ))
若 S 是无穷远点则报错并退出 4: kPB (x2 , y2 ) 5: t KDF (x2 || y2 ,klen)
若t全0返回1 6: C2 M t 7: C3 Hash(x2 || M || y2 ) 8: 输出M的密文C C1 || C2 || C3
解密算法
1: 验证C1是否满足椭圆曲线方程 2: S hC1
R e' x1' mod n r'
SM2之密钥交换协议
A、B协商密钥， 计算ZA、ZB、w ( log2 n ) / 2 1
阶为n的基点G=(xG , yG)，h 余因子，（dA , PA ）为A的公私钥对，（dB , PB ）为B的公私钥对
A
rA [1..n 1] RA rAG (x1 , y1)
密码学原理
椭圆曲线密码
椭圆曲线离散对数问题
SM2之数字签名算法
CONTENT

Weierstrass方程被称为光滑的或非奇异的是指对所有适合 以下方程的射影点P=(X:Y:Z) ∈ P2(K)来说， F(X,Y,Z)=Y2Z+a1XYZ+a3YZ2-X3-a2X2Z-a4XZ2-a6Z3=0 F F F 在P点的三个偏导数 X , Y , Z 之中至少有一个不 为 0若否称这个方程为奇异的。 椭圆曲线E的定义： 椭圆曲线E是一个光滑的Weierstrass方程在P2(K)中 的 全部解集合。 Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3 注： a) 在椭圆曲线E上恰有一个点，称之为无穷远点。即(0:1:0) 用θ表示。
RSA/DS A ECC 512 106 768 132 1024 160 2048 211 2100 0 600
椭圆曲线基础知识
1 有关的基本概念
(1) 无穷远元素（无穷远点，无穷远直线） 平面上任意两相异直线的位置关系有相交和平行两 种。引入无穷远点，是两种不同关系统一。 L2 L1 A
Q
B

有限域上的椭圆曲线点集产生方 法


对每一x(0≤x<p且x为整数），计算x3+ax+b
mod p 决定求出的值在模p下是否有平方根，如果没有则 椭圆曲线上没有与这一x对应的点；如果有，则求 出两个平方根。
Ep(a,b)上加法

如果P,Q∈ Ep(a,b)
P+O=P 如果P＝(x,y),则(x,y)+(x,-y)＝O
3*. 全体无穷远点构成一条无穷远直线。 注：欧式平面添加上无穷远点和无穷远直线，自然构成射 影平面。 L1 L2 A P∞
(2) 齐次坐标 解析几何中引入坐标系，用代数的方法研究欧氏空 间。这样的坐标法也可推广至摄影平面上，建立平面摄影 坐标系。 平面上两相异直线L1,L2，其方程分别为： L1: a1x+b1y+c1=0 L2: a2x+b2y+c2=0

14
Diffie-Hellman密钥交换算法 密钥交换算法
Diffie和Hellman在其里程碑意义的文章中， 虽然给出了密码的思想，但是没有给出真正意 义上的公钥密码实例，也既没能找出一个真正 带陷门的单向函数 然而，他们给出单向函数的实例，并且基于此 提出Diffie-Hellman密钥交换算法
13
常用的公开密钥算法
公钥算法的种类很多，具有代表性的三种密码： 公钥算法的种类很多，具有代表性的三种密码： 基于整数分解难题（IFP）的算法体制 基于整数分解难题（IFP）的算法体制(RSA) 基于离散对数难题（DLP）算法体制 基于离散对数难题（DLP）算法体制(ElGamal) 基于椭圆曲线离散对数难题（ ECDLP ） 的算法体制 基于椭圆曲线离散对数难题 （ ECDLP） (ECC)
3
4.1 公钥密码体制的基本原理
对称算法的不足
（1）密钥管理量的困难 传统密钥管理：两两分别用一个密钥时， 传统密钥管理：两两分别用一个密钥时，则n个用户需 C(n,2)=n(n-1)/2个密钥 当用户量增大时， 个密钥， 要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空 间急剧增大。 间急剧增大。如: n=100 时， C(100,2)=4,995 n=5000时 n=5000时， C(5000,2)=12,497,500 （2）密钥必须通过某一信道协商，对这个信道的安全 密钥必须通过某一信道协商， 性的要求比正常的传送消息的信道的安全性要高
7
公开密钥密码的重要特性
฀
加密与解密由不同的密钥完成 Y: X: Y = EKU(X) X = DKR(Y) = DKR(EKU(X))
加密: X฀ 解密: Y฀
฀ 知道加密算法,从加密密钥得到解密密钥在计算上 , 是不可行的 ฀ 两个密钥中任何一个都可以用作加密而另一个用 作解密(不是必须的) X = DKR(EKU(X))