西安电子科技大学：《现代密码学》课程教学资源（PPT课件讲稿）第五章 公钥密码（RSA算法、椭圆曲线（ECC）密码体制）

公钥密码 ■数论简介 ■公钥密码体制的基本概念 ■RSA算法 ■椭圆曲线密码体制 2021/2/21

2021/2/21 2 公钥密码 ◼ 数论简介 ◼ 公钥密码体制的基本概念 ◼ RSA算法 ◼ 椭圆曲线密码体制

RSA算法 RSA Algorithm 2021/2/21

2021/2/21 3 RSA算法 RSA Algorithm

RSA的安全性 pq要大 p-1,q-1都应有大的素因子。 eΦn且d<nl,则d能被容易的确定。 2021/2/21

2021/2/21 4 RSA的安全性 ◼ |p-q|要大 ◼ p-1,q-1都应有大的素因子。 ◼ e<n且d<n1/4 ,则d能被容易的确定

对RSA的攻击一共棋攻击 每一用户有相同的棋数n 设用户的公开密钥分别为e1e2,且e1e2互素,明 文消息为m,密文为 C1≡ nm moa K C,≡m2modn 因为(e1,e2)=1,用欧几里德算法可求r+5e2=1 假定冂为负数,从而可知由 Euclidean算法可计算 (c1)·2s= m mod n 2021/2/21 5

2021/2/21 5 对RSA的攻击－共模攻击 ◼ 每一用户有相同的模数n ◼ 设用户的公开密钥分别为e1 ,e2 ,且e1 ,e2互素，明 文消息为m,密文为 ◼ 因为（e1 ,e2 )=1,用欧几里德算法可求r e1+s e2=1 假定r为负数，从而可知由Euclidean算法可计算 (c 1 -1 ) r  c 2 s=m mod n c m n c m n e e mod mod 2 1 2 1  

对RSA的攻击一低指教攻击 令网中三用户的加密钥e均选3,而有不同的模1, n2,h3,若有一用户将消息传给三个用户的密文 分别为 y=x3 mod n, x<n1 y2=x3 mod n x< n2 y3=x3 mod n3 x<n 3 一般选丌,m2,32互素(否则,可求出公因子,而 降低安金性),利用中国余定理,可从%,y, 求出y=x3mod(mh2n)。由X<h1,x<h2, x<n3,可得x3<m·m2,=故有 2021/2/21 6

2021/2/21 6 对RSA的攻击－低指数攻击 令网中三用户的加密钥e均选3，而有不同的模n1 , n2 , n3，若有一用户将消息x传给三个用户的密文 分别为 y1=x 3 mod n1 x< n1 y2=x 3 mod n 2 x< n 2 y3=x 3 mod n 3 x< n 3 一般选n1 , n2 , n3互素(否则，可求出公因子，而 降低安全性)，利用中国余定理，可从y1 , y2 , y3 求出 y=x 3 mod (n1 n2 n 3 )。 由x<n1 , x<n2 , x<n 3，可得x 3< n1  n 2 ,  n 3 y ， = 故有 x 3

圆曲线(ECC)密码体制 Elliptic Curve Cryptography 2021/2/21

2021/2/21 7 椭圆曲线(ECC)密码体制 Elliptic Curve Cryptography

概述 获得同样的安全性,密钥长度较RSA短得 多 ■被lE公钥密码标准P1363采用 2021/2/21

2021/2/21 8 概述 ◼ 获得同样的安全性，密钥长度较RSA短得 多 ◼ 被IEEE公钥密码标准P1363采用

椭圆曲线 ■椭圆曲线的曲线方程是以下形式的三次方程 y2+axy+by=x3+cx 2+dxte a,b,c,d,e是满足某些简单条件的实数。定义中包合一个 称为无穷远点的元素,记为O (a) y=r-I b)y2=x2+x+1 2021/2/21

2021/2/21 9 椭圆曲线 ◼ 椭圆曲线的曲线方程是以下形式的三次方程 y 2+axy+by=x3+cx2+dx+e a,b,c,d,e是满足某些简单条件的实数。定义中包含一个 称为无穷远点的元素，记为O

椭圆曲线加法的定义 ■如果其上的3个点位于同一直线上,那么 宅们的和为O。 O为加法单位元,即对ECC上任一点P,有 P+O=P 设P1=,y)是ECC上一点,如法逆元定义为 2 P1,P2连线更长到无穷远,得到ECC上另一点O即 P1,P2,三点共线,所以P1+P2+O=O,P1+P2=O, o+O=0.O=-0 2021/2/21

2021/2/21 10 椭圆曲线加法的定义 ◼ 如果其上的3个点位于同一直线上，那么 它们的和为O。 ◼ O为加法单位元，即对ECC上任一点P,有 P+O=P ◼ 设P1=(x,y)是ECC上一点，加法逆元定义为 P2=-P1=(x,-y) ◼ P1 ,P2连线延长到无穷远，得到ECC上另一点O,即 P1 ,P2 ,O三点共线，所以P1+P2+O=O, P1+P2=O, P2=-P1 ◼ O＋O＝O,O=-O

椭圆曲线加法的定义 Q,R是ECC上X坐标不同的两点,Q+R定义为 画一条通过QR的直线与ECC交于P1(交点是 唯一的,除非儆的Q,R点的切线,此附分别 取P=Q或P1=R)。由Q+R+P1=O得Q+R= ■点Q的倍数定义如下:在Q点儆ECC的一条 切线,设切线与ECC交于S,定义 2Q=Q+Q=-S。类似可定义 3Q=Q+Q+Q,, ■上述加渎满足加渎的一般性质,如交换律 20102结合律等

2021/2/21 11 椭圆曲线加法的定义 ◼ Q,R是ECC上x坐标不同的两点，Q+R定义为： 画一条通过Q,R的直线与ECC交于P1 (交点是 唯一的，除非做的Q,R点的切线，此时分别 取P1=Q或P1=R)。由Q+R+P1=O,得Q+R=- P1 ◼ 点Q的倍数定义如下：在Q点做ECC的一条 切线，设切线与ECC交于S,定义 2Q=Q+Q=-S。类似可定义 3Q=Q+Q+Q,…, ◼ 上述加法满足加法的一般性质，如交换律、 结合律等