浅谈椭圆曲线加密算法(ECC)

椭圆曲线加密算法是近十年提出的一个非对称加密算法,这个加密算法非常复杂,加密的数据具有良好的保密性。加密效果比RSA加密算法都高。这次不可能全部将ECC加密算法讲完,只能简单聊聊ECC加密算法的基本概念和ECC加密算法的数学基础了。

什么是ECC加密算法?

椭圆曲线密码学(英语:Elliptic Curve Cryptography,缩写:ECC)是一种基于椭圆曲线数学的公开密钥加密算法。椭圆曲线在密码学中的使用是在1985年由Neal Koblitz(英语:Neal Koblitz)和Victor Miller(英语:Victor Miller)分别独立提出的。

ECC的主要优势是它相比RSA加密算法使用较小的密钥长度并提供相当等级的安全性[1]。ECC的另一个优势是可以定义群之间的双线性映射,基于Weil对或是Tate对;双线性映射已经在密码学中发现了大量的应用,例如基于身份的加密。1

椭圆曲线加密算法,简称ECC,是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA,ECC优势是可以使用更短的密钥,来实现与RSA相当或更高的安全,RSA加密算法也是一种非对称加密算法,在公开密钥加密和电子商业中RSA被广泛使用。据研究,160位ECC加密安全性相当于1024位RSA加密,210位ECC加密安全性相当于2048位RSA加密(有待考证)。2

ECC加密算法需要的数学理论基础相对来说是比较高的层次方面,远比RSA的数学难度高。看来,数学上层理论的基础是对密码学产生了比较大的影响。下面,来简单聊聊数学基础吧。

数学基础

阿贝尔群

刚看到这个的时候,我的第一反应是:这是什么东西?(一脸懵逼)

阿贝尔群其实就是针对椭圆曲线的概念抽象的一个群,简单来说就是针对椭圆曲线的加减乘除规则。概念的变换,就像刚开始学习微积分的加减乘除规则转换到矩阵的加减乘除规律一样。群其实就是一种推广的矩阵。那么,阿贝尔群定义了些什么有趣的东西呢?

  • 封闭性:如果$ a $和$ b $ 都是阿贝尔群的成员,那么 $ a + b $ 也是阿贝尔群的成员
  • 结合律:$ (a+b)+c=a+(b+c) $
  • 单位元:如果$ a+0=0+a=a $,则 $ 0 $就是单位元
  • 逆元:对于任意值$ a $必定存在$ b $,使得$ a+b=0 $
  • 交换律:$ a + b = b + a $

根据这个定义整数集是个阿贝尔群。

椭圆曲线的数学性质

加法

过曲线上的两点$ A $、$ B $画一条直线,找到直线与椭圆曲线的交点,交点关于$ x $轴对称位置的点,定义为$ A+B $,即为加法。

二倍运算

上述方法无法解释$ A + A $,即两点重合的情况,因此在这种情况下,将椭圆曲线在$ A $点的切线,与椭圆曲线的交点,交点关于$ x $轴对称位置的点,定义为$ A + A $,即$ 2A $,即为二倍运算。

同余运算

同余就是有相同的余数,两个整数 a、 b,若它们除以正整数 m所得的余数相等,则称$ a $,$ b $对于模m同余。

$$
a\equiv b(mod\ m)
$$

乘法逆元

这是比较简单的一个概念,在RSA加密算法里面也进行了阐述,这里就举个例子说明吧:

在模7乘法中:

  • 1的逆元为1 $ (1 \times 1) \mod \ 7=1 $
  • 2的逆元为4 $ (2 \times 4) \mod \ 7=1 $
  • 3的逆元为5 $ (3 \times 5) \mod \ 7=1 $
  • 4的逆元为2 $ (4 \times 2) \mod \ 7=1 $
  • 5的逆元为3 $ (5 \times 3) \mod \ 7=1 $
  • 6的逆元为6 $ (6 \times 6) \mod \ 7=1 $

这些大致就是ECC所需要的大致的数学理论,可能也只是很少的一部分数学理论,毕竟ECC加密算法的安全性是非常高的,因此可以考虑在ECC算法的基础进行改进和拓展出更多的ECC变体的加密算法,ECC的数学理论主要是建立在抽象代数相关理论中,可以补抽象代数的相关内容来进行ECC加密算法的深入了解。

参考:

  1. 椭圆曲线密码学-维基百科
  2. 椭圆曲线加密算法(ECC)-知乎

闲聊到此为止,来喝杯茶可好?

Q.E.D.