公钥密码 ■数论简介 ■公钥密码体制的基本概念 ■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