西安阿里云网站建设,一个网站开发时间,网站美化工具,江干网站建设背景
ECC英文全称Elliptic Curve Cryptography#xff0c;其背后的密码学原理或者说安全性#xff0c;是基于椭圆曲线离散对数问题#xff08;Elliptic Curve Discrete Logarithm Problem#xff0c;ECDLP#xff09;。ECC密码学被普遍认为是RSA密码系统的接…背景
ECC英文全称Elliptic Curve Cryptography其背后的密码学原理或者说安全性是基于椭圆曲线离散对数问题Elliptic Curve Discrete Logarithm ProblemECDLP。ECC密码学被普遍认为是RSA密码系统的接替算法相比于RSAECC在使用更短的密钥长度即可达到同等的安全性比如ECC164位的密钥相当于RSA 1024位密钥提供的保密强度且由于密钥更短运算速度和带宽占用上也更有优势。 关于ECC的数学原理介绍和使用方法网上有许多教程下面主要是个人对认为比较难理解的知识点的思考和汇总。
椭圆曲线的确定
描述一条Fp上的椭圆曲线常用到六个参数 T(p,a,b,G,n,h)。 p 、a 、b 用来确定一条椭圆曲线 G为基点 n为点G的阶 h 是椭圆曲线上所有点的个数m与n相除的整数部分。 这几个参数取值的选择直接影响了加密的安全性。参数值一般要求满足以下几个条件
p 当然越大越安全但越大计算速度会变慢200位左右可以满足一般安全要求p≠n×hpt≠1 (mod n)1≤t204a3 27b2 ≠ 0 (mod p)n 为素数h≤4
椭圆曲线的选择
使用ECC时应该从密码学家证明过具备安全性的曲线中选择曲线使用如secp256k1, P-521 Curve25519等不应该使用私有的曲线。即不要自行选择或者定义T(p,a,b,G,n,h)中这些确定椭圆曲线的参数。
密钥长度的选项和选择
由于我们对RSA比较熟悉因此我们可以把两种算法中不同密钥长度的安全性进行类比这样就可以基于RSA的经验来选择合适的密钥长度下表是两种算法在提供同等级安全时各自需要的密钥长度。就RSA而言目前主流密钥长度至少都是1024bits以上低于或者等于1024bit的密钥已经不建议使用对于一些政府部门金融机构应选择使用大于2048bits的密钥长度。
椭圆曲线明文密文密钥和椭圆曲线的关系
很多文章对椭圆曲线的数学原理的解释十分详细但是看完还是没办法理解是如何将这个曲线和加解密联系在一起。其实明文密文以及公钥都是椭圆曲线上的点或者点对。 私钥生成一个随机数k_priv这个随机数的范围是[1,n)即大于0但是小于n的数n即曲线的阶是椭圆曲线的参数之一在曲线确定的情况下这个n值也可以确定 公钥k_pub k_privG其中G是T(p,a,b,G,n,h)中的G即椭圆曲线的生成元或者叫基点通过k_priv和G相乘得到的k_pub 仍然是在曲线上的一点 明文将明文编码使之成为T(p,a,b,G,n,h)曲线上的一点表示为M 密文生成随机数r将消息M生成密文EE {rG, Mrk_pub }其中k_pub 为公钥这个密文就是曲线上的一个点对 解密过程 密文 E M rk_pub - k_priv*(rG) M r(k_privG) - k_priv (rG) M 在数学上已知k_priv和G求k_pub k_privG的速度是非常快的但是已知k_pub 和G求k_privk_pub/G却是非常困难的这就是椭圆曲线的离散对数问题ECC加解密算法的安全性正是基于这个离散对数问题而得到保证 综上可以简述加解密过程如下
用户A选定一条椭圆曲线T(p,a,b,G,n,h)用户A选择一个私有密钥k并生成公开密钥KkG用户A将曲线T实际中则是双方约定选择同一个经过安全证明的曲线和点K公钥G传给用户B用户B接到信息后将待传输的明文编码到曲线T上一点M并产生一个随机整数rrn用户B计算点C1MrKC2rG用户B将C1、C2传给用户A用户A接到信息后计算C1-kC2结果就是点M。因为C1-kC2MrK-k(rG)MrK-r(kG)M再对点M进行解码就可以得到明文。 在这个加密通信中如果有一个偷窥者H 他只能看到T(p,a,b,G,n,h)、K、G、C1、C2而通过K、G 求k 或通过C2、G求r 都是相对困难的。因此H无法得到A、B间传送的明文信息。
公钥和私钥的表示方式
公钥
椭圆曲线的公钥实际上是曲线上的一个点可以用坐标点x,y表示通常是将x和y的值分别转换成字符串来存储和传输如下是一个公钥的例子 57E1174B773A91E743BC719C9C8B24C8F25096411744C0EB09C13AAD4073D547 BBD7DA078002F7C84441B196A8B8532E0046BA8ED71DED0B9E2BEACA31F1EE9A 其中57E1174B773A91E743BC719C9C8B24C8F25096411744C0EB09C13AAD4073D547为公钥的x点坐标BBD7DA078002F7C84441B196A8B8532E0046BA8ED71DED0B9E2BEACA31F1EE9A为公钥的y点坐标实际在计算的时候需要把这些字符串中的元素按照其字面的值转为对应的十六进制如0x570xE1… 上述是公钥的非压缩表示通常需要还在坐标点前加上一个字节0x04用于表示使用非压缩的方式即0457E1174B773A91E743BC719C9C8B24C8F25096411744C0EB09C13AAD4073D547BBD7DA078002F7C84441B196A8B8532E0046BA8ED71DED0B9E2BEACA31F1EE9A。 还有一种压缩的表示方式。根据椭圆曲线方程我们只需要知道 x 坐标就可以通过方程计算出 y 坐标这样就不用同时保存xy的值减少了存储和带宽。但是如果只知道x带入方程会求出两个y一正一负对应两个不同的点所以还必须有一个标志来区别实际使用的是哪个。所以通常采用下面的约定具体格式为
前缀02 x 当y为偶数前缀03 x 当y为奇数 可以仅用一个坐标长度1bit表示整个公钥比如 02f54ba86dc1ccb5bed0224d23f01ed87e4a443c47fc690d7797a13d41d2340e1a
私钥
私钥是一个随机数通常是把其十六进制下的数据当作字符串保存和公钥的保存形式一样如下 0A7ECE7EFCA5C5A186FF7340125E2E1F1754D8F27922573F66ABA43D8DA3ECDE 这个私钥其实就是0x0A0x7E0xCE…
椭圆曲线加解密算法的实现
但是实际上和RSA算法不同ECC并没有提供/定义一种具体的加解密算法在目前常用的开源算法库中也没有看到直接实现ECC加解密的接口为了基于ECC实现加解密开发人员通常采用混合加密方案来实现此功能下面是混合加密解决方案的示例图其实就是结合对称加解密密钥派生算法或者密钥协商算法等其他密码学算法同时结合ECC的安全性间接实现ECC加解密。 下面是一个基于ECDH密钥交换方案设计的ECC加解密功能实例 由于使用的密钥较多先逐一介绍这些密钥的功能以及如何产生这些密钥 sharedSecret共享秘密数通过密钥协商算法生成的临时秘密数用于作为密钥派生算法KDF的输入派生出加密明文的加密密钥和摘要计算密钥 sendTempPub发送方的临时ECC公钥用于计算sharedSecret sendTempPriv发送方的临时ECC私钥用于计算sharedSecret recvPubKey接收方的固定的ECC公钥同时也是对外暴露的公钥需要给到发送方 recvPrivKey接收方的固定的ECC私钥 ENC Key用于对实际明文进行加解密的对称密钥 MAC Key用于进行hash计算的对称密钥 关于密钥协商的过程通常使用DH算法可以参考下面的介绍 https://cryptobook.nakov.com/asymmetric-key-ciphers/ecdh-key-exchange
加密过程
假设用户A需要通过ECIES对数据进行加密发送给用户B 加密步骤如下
用户B生成随机数并不是任意的随机数都可以需要是[1,n)这个范围内n为阶数曲线的参数之一作为recvPrivKey用户B通过私钥recvPrivKey生成公钥recvPubKeyrecvPrivKey*GrecvPubKeyG为生成元也是曲线的参数之一并将公钥recvPubKey给到用户A用户A生成随机数作为sendTempPriv并计算出sendTempPubsendTempPriv*G用户A通过sendTempPriv*recvPubKey SharedSecret得到SharedSecret用户A将SharedSecret作为输入通过KDF算出ENC Key和MAC Key使用ENC Key对明文m进行加密得到c使用MAC Key对上一步得到的c进行MAC计算得到tag将sendTempPubc和tag拼接得到sendTempPub | c | tag作为完整的密文发送给到B 上述过程的图形表示如下
解密过程
假设用户B收到了来自用户A的密文sendTempPub | c | tag 解密步骤如下
用户B从sendTempPub | c | tag提取出sendTempPub用户B使用sendTempPub * recvPrivKey计算出SharedSecret用户A是通过sendTempPriv * recvPubKey SharedSecret计算出SharedSecret的又因为sendTempPub sendTempPriv * G因此sendTempPub * recvPrivKey sendTempPriv * G * recvPrivKey sendTempPriv * recvPubKey SharedSecret用户B以SharedSecret作为输入通过KDF算出ENC Key和MAC Key用户B从sendTempPub | c | tag提取出c用户B使用ENC Key对c进行解密得到明文m用户B从sendTempPub | c | tag提取出tag用户B使用MAC Key对c进行hash计算得到tag’将tag和tag’进行比较 上述过程的图形表示如下 综上可以看到ECC在加解密中主要是利用私钥的不可逆推来保护临时的对称密钥的安全性真正加密数据的是通过密钥派生算法计算出的密钥。 从上述的例子可以看出基于ECC进行加解密的方案中具体使用何种密钥派生算法何种对称加解密算法都是非常灵活的为了便于加解密双方协商这些算法或者参数实际工程中可以基于ECIES来实现加解密方案。ECIES集成加密方案elliptic curve integrate encrypt schemeECIES并不是一种具体的方案而是一种基于ECC的加解密框架其中的密钥导出机制加密方法都可以根据自己的需要进行设计。 ECIES也有几个标准ANSI X9.63 IEEE 1363a 和 ISO/IEC 18033-2。其中主要约定ECIES参数是KDF对称加解密算法MAC算法等。
ECC和RSA的比较
