旺旺：旺我旺：能我过能软过软考考
主要内容
ﻫ公钥密码使用的几个单向性很好的函数 ﻫElGamal密码回顾 ﻫ椭圆曲线概述 ﻫ椭圆曲线及解点 ﻫ椭圆曲线的几何意义 ﻫ椭圆曲线的解点等计算 ﻫ椭圆曲线密码体制 ﻫ利用椭圆曲线密码加解密实例
旺旺：我能过软考
公钥密码使用的几个单向性很好的函数
版权所有：我能过软考
1）大合数的因子分解问题： 大素数的乘积容易计算，如（p*q=n），而大合数 的因子分解困难（n推出p和q) 代表：RSA密码
2）有限域上的离散对数问题： 有限域上大素数的幂乘容易计算（ab
对数计算困难（logac b) 乘法群： ElGamal密码
加法群：ECC密码
c），而
3 旺旺：我能过软考
ElGamal密码回顾
版权所有：我能过软考
ElGamal密码是建立在有限域GF(p)之上，其中p是一个大素数， 选取有限域GF（p）的一个本原元α ，并将GF（p）和α公开。
注意：p是大素数，且p-1有大素数因子。
1、密钥生成 用户随机选取一个整数d： 1≤d ≤p-2，并计算出 y= αd mod p
将y作为公开的加密密钥，将d作为保密的解密密钥。
由公钥y求出私钥d，必须求解离散对数，非常困难
4 旺旺：我能过软考
椭圆曲线概述
版权所有：我能过软考
受ELGamall密码启发，在其它离散对数问题难解的群中，同样可以构成ELGamal 密码
有限域GF(p)上的椭圆曲线的解点构成交换群，而且离散对数问题是难解的，于是 可在此群上建立ELGamal密码，并称为椭圆曲线密码
它密钥短、签名短、软件实现规模小、硬件实现电路省电。
应用：基于智能卡的多种应用，如电子商务中的数字签名与认证，移动通讯中的安 全保密等方面
普遍认为160位长的椭圆曲线密码的安全性相当于1024位的RSA密码，而且运算速 度也较快。
6 旺旺：我能过软考
椭圆曲线公钥密码与其他密码算法的对比
对称算法的密 钥长度
56
破解所需时间 （MIPS年）
104
RSA密钥 大小
512
64
108
768
版权所有：我能过软考
ECC的密钥 106 132
RSA/ECC 密钥大小之比 5：1
6：1
80
1012
1024
160
7：1
112
1020
2048
210
10：1
MIPS年：表示每秒钟执行一百万条指令的计算机计算一年的时间
7 旺旺：我能过软考
椭圆曲线及解点
版权所有：我能过软考
设p是大于3的素数， 且4a3+27b2≠0 mod p ， 称y2=x3+ax+b ，a,b∈GF(p)为GF(p)上的椭圆曲线。
由椭圆曲线可得到一个同余方程 y2=x3+ax+b mod p 其解为一个二元组<x,y>，x,y∈GF(p) ，在椭圆曲线上是一个点， 又称其为解点。
8 旺旺：我能过软考
椭圆曲线的几何意义
版权所有：我能过软考
作集合E={全体解点，无穷点O }。
可以验证如上定义的集合E和加法运算 构成加法交换群。
该群定义了一种运算，可以是加、减、乘、除等
椭圆曲线解点加法运算的几何意义：
9 旺旺：我能过软考
椭圆曲线--O元素与逆元
版权所有：我能过软考
为了利用解点构成交换群，需要引进一个需要0元素，并定义如下的加法运算 ①定义单位元
引进一个无穷点O（∞，∞），简记为O ，作为0元素。
O(∞，∞)+ O (∞，∞) =0+0=0， 并定义对于所有的解点P(x,y), P(x,y)+O=O+ P(x,y)= P(x,y)
②定义逆元素 设P(x1,y1)和Q(x2,y2)是解点，如果x1=x2且y1=-y2，则P(x1,y1)+Q(x2,y2)=0 。
这说 明任何解点R(x,y)的逆就是R(x,-y)。
注意:规定无穷远点的逆就是其自己。
10 旺旺：我能过软考
12。