ecc加解密算法 c++_ECC相关算法解析

前言

近日NSA向微软公布了一个基于ECC加密的漏洞(CVE-2020-0601)，该漏洞出现于Windows CryptoAPI(Crypt32.dll)做签名验证的部分，该漏洞可能导致严重的威胁。我对此十分好奇，于是学习了ECC相关的知识，在这里和大家分享一下。

ECC原理介绍

首先我们来学习一下ECC(椭圆曲线加密)的原理。ECC全称为“Ellipse Curve Ctyptography”，是一种基于椭圆曲线数学的公开密钥加密算法。椭圆曲线在密码学中的使用是在1985年由Neal Koblitz和Victor Miller分别独立提出的。与传统的基于大质数分解难题的加密算法不同，该加密方式基于 “离散对数” 这种数学难题。该算法的主要优势是可以使用更小的密钥病提供相当高等级的安全。ECC164位的密钥产生一个安全级，相当于RSA 1024位密钥提供的保密强度，而且计算量较小，处理速度更快，存储空间和传输带宽占用较少。目前我国居民二代身份证正在使用 256 位的椭圆曲线密码，虚拟货币比特币也选择ECC作为加密算法。

一、数学基础

以下内容我们小学二年级就学过，带领大家复习一下

首先我们来介绍一下射影。传统的几何几何系统中，我们可以在《几何原本》中照到如下定理：

• 由任意一点到任意一点可作直线。
• 一条有限线段可以无限延长
• 凡直角皆相等
• 三角形内角和为180度
• 同一平面内一条直线a和另外两条直线b.c相交，若在a某一侧的两个内角的和小于两直角，则b.c两直线经无限延长后在该侧相交

以上内容属于欧式几何，然后又一些大佬觉得欧几里得说的不对，他们觉得第五条定理不能作为公理，而且三角形的内角和也不是180度。所以，有些强者就建立了新的几何体系，比如，俄国的罗巴切夫斯基提出“至少可以找到两条相异的直线，且都通过P点，并不与直线R相交”代替第五公设，然后与欧氏几何的四个公设结合成一个公理系统，简称“罗氏几何(双曲几何)”。黎曼大佬也插了一脚，他觉得“找不到一条直线可以通过P点，并且不与直线R相交”，于是建立了黎曼几何(椭圆几何).数学就是这样神奇，只要你能自圆其说，满足自洽性，你也能建立自己的体系。

我们把上面的两种几何体系称之为非欧几何。定义平行线相交于无穷远点P∞，使平面上所有直线都统一为有唯一的交点，那么：

• 一条直线只有一个无穷远点；一对平行线有公共的无穷远点
• 任何两条直线有不同的无穷远点
• 平面上的无穷远点构成的集合组成一条无穷远直线

射影平面可被认为是个具有额外的“ 无穷远点”之一般平面，平行线会于该点相交。因此，在射影平面上的两条线会相交于一个且仅一个点。

（一）椭圆曲线

椭圆曲线就是在射影平面上满足魏尔斯特拉斯方程(Weierstrass)的点构成曲线。对于有限域上的椭圆曲线，一般我们用如下方程定义：