下周二停课1次
下周二停课 1 次
4椭圆曲线密码体制的安全性 目前的有效算法表明,在椭圆曲线上求 解离散对数问题,其算法复杂性是完全 指数时间,因此一般认为它比大数分解 问题和Z上的离散对数问题要难
4.椭圆曲线密码体制的安全性 目前的有效算法表明，在椭圆曲线上求 解离散对数问题，其算法复杂性是完全 指数时间，因此一般认为它比大数分解 问题和 Z p *上的离散对数问题要难
但对于某些椭圆曲线,已有一些有效攻 击方法。 例如当椭圆曲线点群E(F0的阶也是q时, 就能容易求解离散对数,其有效算法由 Semave,smar和 Satoh,Arak分别独立给 出。这类椭圆曲线我们称为反常椭圆曲 线,在实际使用时应去除这类曲线 除此之外, Menezes, Okamoto和 Vanstone(MOV)提出了一种方法,当 E(Fg)=1时,可将E(F上的离散对 数问题化归到有限域上的离散对数问题
但对于某些椭圆曲线，已有一些有效攻 击方法。 例如当椭圆曲线点群E(F q )的阶也是 q时， 就能容易求解离散对数，其有效算法由 Semave,Smart 和Satoh,Araki分别独立给 出。这类椭圆曲线我们称为反常椭圆曲 线，在实际使用时应去除这类曲线。 除此之外， Menizes,Okamoto 和 Vanstone(MOV)提出了一种方法，当 (|E(F q)|,q)=1时，可将E(F q )上的离散对 数问题化归到有限域上的离散对数问题
◆在构造椭圆曲线密码体制时,应避免上 述两类椭圆曲线。 ◆用合适的椭圆曲线可以构造安全强度高 的公钥密码体制。 ◆根据现有结论,使用160bit模的椭圆曲 冷线密码体制与1024bit模的RSA有同样的 密码安全强度,其加解密速度则比 1024bi模的RSA快近10倍,等同于RSA 采用低加密指数的速度,因此应用前景 有可能较广
在构造椭圆曲线密码体制时，应避免上 述两类椭圆曲线。 用合适的椭圆曲线可以构造安全强度高 的公钥密码体制。 根据现有结论，使用160bit模的椭圆曲 线密码体制与1024bit模的RSA有同样的 密码安全强度，其加解密速度则比 1024bit模的RSA快近10倍，等同于RSA 采用低加密指数的速度，因此应用前景 有可能较广
◆对于椭圆曲线E通常有2种情形: ◆(1)E是域Fn上的椭圆曲线,p为素数,a是E中 阶为素数q=Eh的元素,典型的是h=124 ●(2)E是域F2上的椭圆曲线,p为素数,a是E 中阶为素数q=E/h的元素,典型的是h=2,4 有估计,安全性要保持到2020年,一般应取p 为160位。 ◆在2000年4月,联合了40个国家,9500台计算 机完成了 Certicom公司发出的ECC2K-108挑 战,解决了定义在F2m上的椭圆曲线的离散对 数问题
对于椭圆曲线 E通常有 2种情形： (1)E是域 F p上的椭圆曲线， p为素数， a 是 E 中 阶为素数q=|E|/h的元素，典型的是h=1,2,4 (2) E是域 F 2 n上的椭圆曲线， p为素数， a 是 E 中阶为素数q=|E|/h的元素，典型的是h=2,4 有估计，安全性要保持到2020年，一般应取 p 为160位。 在2000 年 4月，联合了40个国家，9500台计算 机完成了Certicom公司发出的ECC2K-108 挑 战，解决了定义在 F 2109上的椭圆曲线的离散对 数问题
35.5概率加密 概率加密是由 S Goldwasser和 S Mical提出的。 基本想法是使公钥密码体制的信 息泄露为0 在多项式时间内由密文不能推出 明文或密钥的任何信息
3.5.5 概率加密 概率加密是由 S.Goldwasser 和 S.Micali提出的。 基本想法是使公钥密码体制的信 息泄露为0 在多项式时间内由密文不能推出 明文或密钥的任何信息
对给定的公开密钥,对一个确定的明文 加密总是得到一个相应的密文,因此攻 击者就可采用已知明文进行攻击。 如果对于一个明文,在给定密钥下,加 密结果不是确定的,而是概率的,使 6个明文在同二个密钥下可对应多个密文, 就使得上述攻击变得相当困难 SA EIGam密码体制以及椭圆曲线上的 EIGamal密码体制属于这类
对给定的公开密钥，对一个确定的明文 加密总是得到一个相应的密文，因此攻 击者就可采用已知明文进行攻击。 如果对于一个明文，在给定密钥下，加 密结果不是确定的，而是概率的，使一 个明文在同一个密钥下可对应多个密文， 就使得上述攻击变得相当困难。 ElGamal密码体制以及椭圆曲线上的 ElGamal密码体制属于这类
定义中的条件(1)规定了加解密方法,特别是引进了 随机数ro 条件(2)则保证明文m的所有可能密文分布与m≠m的 所有可能密文分布是不可区分的,这就使得攻击者无 法确认密文是对应什么明文的。 1)对母个k∈K,母个E1∈E,D1∈D,有 p(E(m,r)m(对m∈M,vr∈R),并且当 冷Ymm(m∈M时,有Em,m)≠Em,n) 其中E1:MxR→C,D:C→M A2没是安全参数,对任意keK,任意meM,在C 上定义一个概率分布Pkm 这里PM(l)表示在给定密钥k和明文的条件下c是密 文的概率(概率在所有r∈R上计算) 如果m、m'∈M,有m≠m且keK,则概率分布Pkm ≠PLm不是E可区分的
定义3.4：一个概率公钥密码体制是一个 6元组 (M,C,K,E,D,R)。其中 M 、 C 、 K分别是明文空间、 密文空间和密钥空间， E 和 D分别是公开加密规则 集和秘密解密规则集， R为随机量空间，它们满足 以下要求： (1)对每个 k K，每个 E k E，D k D，有 D k(E k(m,r))=m( 对 m M, r R) ，并且当 m m'(m' M)时，有 E k(m,r) E k(m',r) 其中 E k：M R → C，D k：C → M (2) 设 ε是安全参数，对任意 k K，任意 m M，在 C 上定义一个概率分布 Pk,m 。 这里 Pk,M(c)表示在给定密钥 k和明文的条件下 c是密 文的概率 (概率在所有 r R上计算 ) 。 如果 m 、m' M，有 m m' 且 k K，则概率分布 Pk,m Pk,m’不是 ε可区分的。 定义中的条件(1)规定了加解密方法，特别是引进了 随机数 r 。 条件(2)则保证明文 m的所有可能密文分布与m' m 的 所有可能密文分布是不可区分的，这就使得攻击者无 法确认密文是对应什么明文的
1 Goldwasser-Micali概率公钥密码 体制 Goldwasser-Micali在1984年给出了一个 概率公钥密码方案。 该体制是基于奇合数n平方剩余难解问 题建立的。 奇合数n平方剩余问题对于给定的一个 多人A奇合数n和整数a,决定a是否为模m的平 方剩余,即判定x2= a mod n是否有解 若有解,则是modn的平方剩余,否则 a是模n的非平方剩余
1.Goldwasser-Micali概率公钥密码 体制 Goldwasser-Micali在1984年给出了一个 概率公钥密码方案。 该体制是基于奇合数n平方剩余难解问 题建立的。 奇合数n平方剩余问题:对于给定的一个 奇合数n和整数a，决定a是否为模n的平 方剩余，即判定x2=a mod n是否有解， 若有解，则a是mod n的平方剩余，否则 a是模n的非平方剩余
Euler准则:设p是奇素数,则x是p的平方剩余当且仅 当xP)2= I modp 对于n=pq,x是n的平方剩余当且仅当x|=(x|=1。 p/( Zn=x1sx<n,J(n, x)=1 在Zn上定义谓词Qn x是模n的平方剩余 Q 10x是模n的非平方剩余 当n是素数或n的素因子已知时,Q是容易 计算的, 当n的素因子未知时,Q的计算是难的。 这就是所谓的平方剩余假设
Goldwasser-Micali的方案具体过程： 设 N 表示正整数集， nN 。 令 Zn*={x|1≤x<n,(x,n)=1}， Zn'={x|1≤x<n,J(n,x)=1}。 在Zn'上定义谓词Qn： 是模 的非平方剩余 是模 的平方剩余 x n x n Qn 01 当n是素数或n的素因子已知时，Qn是容易 计算的， 当n的素因子未知时，Qn的计算是难的。 这就是所谓的平方剩余假设。 Euler 准则：设 p 是奇素数，则 x 是 p 的平方剩余当且仅 当 x(p-1)/21modp。 对于 n=pq，x 是 n 的平方剩余当且仅当 1 qx px