0%

密码学 | 椭圆曲线密码学简介「转载」

这一节要聊的是 ECC ( Elliptic Curve Cryptography ),也就是椭圆曲线密码学。跟 RSA 一样,ECC 也属于公开密钥加密,ECC 算法也是用来生成公钥的私钥的。本节我们不会深入椭圆曲线算法本身,只是对 ECC 做一下简介。


参考资料



ECC 的作用


之所以要解释这么一个生僻的名词,还是因为它很有用。

ECC 跟 RSA 算法一样,都可以生成公钥和私钥,然后进行加密通信和数字签名操作。ECC 在区块链领域有着特殊的地位。因为比特币就是用 ECC 来生成地址和私钥的。注意,比特币地址不是原封不动的公钥,而是公钥的一种转换形式。著名的以太坊项目,也使用了 ECC 。既然区块链领域的两个老大都会用到 ECC ,其他的公链项目中当然也都非常可能用到。HTTPS 也会用到 ECC 。现代的浏览器也都支持基于椭圆曲线密钥对的认证证书。

总之,ECC 应用范围很广,有人说”ECC是下一代的公开密钥加密算法”,似乎有取代 RSA 的意味。


对比 RSA 的改进


我们知道 RSA 是公钥密码学的鼻祖,那么后来者 ECC 到底有何改进呢?其实简单来说就是两个字“性能”。

我们先说 RSA 的不足。RSA 基于整数分解问题,我们可以相信只要两个大素数的乘积的反向求解问题没有解决,RSA 算法就是安全的,所以 RSA 可以说是非常简单的密码学。但是 RSA 的性能是短板,需要设置很长的秘钥,才能保证算法的安全。而秘钥越长,运算效率就越低。一个很尴尬的情况是,我们的超级计算机越来越厉害,所以就要求 RSA 的秘钥要越来越长。但是矛盾的是,移动设备又很流行,这就要求秘钥不能太长,不然在资源有限的移动设备上 RSA 算法就不能用了。这个矛盾越来越尖锐,所以更高效的算法就呼声很高。

ECC 算法从 2004 年开始才被广泛应用,要比 RSA 要晚很多,它的关键改进就是性能。同样的秘钥长度下,ECC 要安全很多。ECC 和 RSA 基于的都是正向运算很容易,反向运算很难的单向函数来设计的。运算越难,也就是意味着破解它运算所耗费的能源越多,或者说对应的碳排放量越多。比如给定一个228字节长度 RSA 秘钥,破解需要花费煮沸一勺水的能量。而同样长度的 ECC 秘钥,需要煮沸整个地球上所有水的能量。

可见,ECC 作为后来出现的算法要比 RSA 高效很多。


ECC 的缺陷


但是,ECC 虽好也不是没有问题,如果真的是完美的,那么 RSA 应该早就被彻底替代了。

ECC 的数学原理是椭圆曲线和离散对数,椭圆曲线并不是一个很好理解的数学理论。造成了 ECC 其实要比 RSA 复杂很多。复杂带来的好处就是性能的提升,但是也同时潜藏了一些问题。椭圆曲线理论不展开讨论,但是粗略的讲,设计 ECC 的一套运算标准,涉及到的一个问题就是要选择一条合适的椭圆曲线。注意,ECC 使用的所谓的椭圆曲线其实并不是椭圆形,而只是在运算上跟椭圆运算有关联,实际上是一个类似乳头的形状。根据曲线选择的不同,ECC 的运算也会不同,所以就会形成不同的标准。

首先第一个潜藏的问题是,一套标准对应的这条曲线,是不是有可能有人暗藏数学机关呢?造成算法其实是可以通过后门来破解的。目前使用面很广的一套标准是 NSA ,也就是美国国家安全局发布的,这套标准就被怀疑是有后门的。

另外一个问题就是专利。基于 ECC 的各种使用方式,有人申请了很多个专利。而且这些专利很多都被一个公司所持有,这个公司就是黑莓。你永远也不知道自己开发一套新的 ECC 方案,会不会被认为触犯了某个专利,这一点也是很恶心的。

总之,虽然 ECC 目前发展良好,但是也面临着各种挑战。


总结


关于椭圆曲线密码学 ECC .首先比较重要的是大家要理解什么是加密,这样才能理解 ECC 的使用场景。ECC 被称为新一代公开密钥加密技术,就是因为它比 RSA 算法更高效。但是 ECC 也因为算法复杂,导致了出各种问题的可能,例如被植入后门或者涉及专利之争。

请我喝杯咖啡吧~