ecc 椭圆曲线算法（ECC）学习（一）

*本文原作者:苗苗Xi、怀，本文属于FreeBuf原创奖励计划，未经许可禁止转载。

0×00前言

椭圆曲线加密算法是一种基于椭圆曲线数学的公钥加密算法。随着大整数分解方法的进步和完善，计算机计算速度的提高和网络的发展，RSA的利用率越来越高。其密钥的长度一直受到保守的批评，于是新算法ECC逐渐走上了加密算法的大舞台，其利用率和重要性也在逐年提高。所以今天，我们将通过这篇文章介绍椭圆曲线加密算法的数学基础。

0×01正文数学基础1.1椭圆曲线方程

椭圆曲线是指一个齐次方程:

数形结合确定的平面曲线，其中系数AI 定义在某个域中，可以是有理数域、无理数域、复数域、有限域GF，这些域在ECC密码系统中都是在有限域中定义的。

一个称为无穷远的特殊点和椭圆上的所有点一起构成一个集合，通过定义的加法运算构成阿贝尔群

曲线上的每一点都必须是非奇异的，所谓“非奇异”或“光滑”，就是指数学上曲线上的任意一点都有切线。

等式1:

在这个等数中，我们可以看到，当我们知道M和P的时候很容易找到点Q，但是当我们只知道Q和P的时候就很难找到M，这个问题在离散对数问题中叫做椭圆曲线上的点群。

我们所学的椭圆曲线密码系统就是利用上述难题设计的。

椭圆曲线的形状不是椭圆，是因为椭圆曲线的描述方程类似于计算椭圆周长的方程。

数学基础1.2阿贝尔群是什么?

在数学中，群是由集合和二元运算组成的代数结构。如果一个集合或操作是一个组！必须满足以下条件

关闭

结合性

单位元

逆元素

并且满足数学中的交换定律定律:

有一个定义是取椭圆中的两点P和Q，使一条直线与椭圆的一个点A相交，使Y轴的一条平行线与另一个点b相交。

这样加法的和也在椭圆上，也满足交换定律和联想定律。

由上可知，由于Abe群是所有点和特殊点的和，如果有m个相同的点p加在一起，则写成mP，得到方程1:

数学基础1.3椭圆曲线中的有限域

从上面的介绍中，我们对椭圆曲线有了一定的了解。但是椭圆是连续的，点与点之间似乎没有联系。怎么加密？

给出了有限域Fq的描述及其元素的表示。q是奇数或2的幂。当q是奇素数p时，p >:2^191；当q是2 ^ 2m的幂时，m >: 192，是素数。

素数域Fp:

1)当q为奇素数p时，素数域Fp中的元素使用整数0；1;2;；P1代表。

a)加法单位元素为整数0；

b)乘法单位为整数1；

c)定义域元素的加法是整数的模p加法，即如果a；B∈Fp，那么a+b =mod p；

d)域元素的乘法是整数的模P乘法，即如果A；B∈Fp，那么a.b = mod p。

2)Fp上定义的椭圆曲线方程为:

和

椭圆曲线E定义为:

并满足该等式

其中o是无穷远点。

椭圆曲线E上的点数用#E表示，称为椭圆曲线E的阶数。

如果在椭圆曲线上的一个点p处有一个最小正整数n，从而使次数NP = 0∩，那么n就叫p的阶，如果n不存在，我们说p是无穷的。

事实上，有限域上定义的椭圆曲线上的所有点的阶n是存在的。

0×02加密

为了描述Fp上的椭圆曲线，通常使用六个参数:T=。

用来确定一条椭圆曲线，p是素数域中的点数，a和b是其中的两个大数；

x和y是g基点的坐标，也是两个大数；

n是G点基点的阶数；

以上六个量可以描述一条椭圆曲线，有时我们也用H。

现在我们描述一个使用椭圆曲线加密通信的过程:

1.机器a选择一条椭圆曲线Ep,并将椭圆曲线上的一点作为基点g..

2.机器a选择一个私钥K并生成一个公钥K=kG。

机器a将Ep和k，g点传送给用户B..

4.B机收到信息后，将待传输的明文编码到Ep上的一个点m，生成一个随机整数r。

5、乙机计算

6.机器乙将C1和C2点传送给机器甲..

7.收到信息后，a计算C1-kC2，结果是点m。因为

然后，对m点进行解码就可以得到明文。

在这种加密通信中，如果有偷窥狂h，他只能看到Ep，k，g，C1，C2，但是通过k，g或者r通过C2，g找到k相对比较困难，所以h得不到a和B之间传输的明文信息..

代码实现:ecies.py

导入hashlib

从openssl_wrapper导入openssl

从struct导入包，解包

#1.生成临时电子商务密钥对

#我们在二维码场景中使用短且无专利的EC曲线，即‘secp 160 R1’

PUBKEY = ' 02 c 500146 EC 52 c 4 fdae 22 c 1c 18d 81 b 3679 cf 70397 fdaab 8 f 0014 BAC 0 efaf 80 ce 2 EC 719 ba 1 bcaa 53530 BF 03d 6d 95 '

PRIVKEY = ' 02c 500147 BD 49 a3 ea 78 ba 2d 5a 06920 f 4326 e 693002419685 '

#PUBKEY=PUBKEY.decode

#PRIVKEY=PRIVKEY.decode

def gen_ec_keypair:

#此函数生成电子商务密钥对

尝试:

曲线=OpenSSL.curves

key = OpenSSL。EC_KEY_new_by_curve_name

OpenSSL。EC_KEY_generate_key

_pubkey_x = OpenSSL。BN_new

_pubkey_y = OpenSSL。BN_new

_privkey = OpenSSL。EC_KEY_get0_private_key

_pubkey = OpenSSL。EC_KEY_get0_public_key

_group = OpenSSL。EC_KEY_get0_group

OpenSSL。EC _ POINT _ get _仿射_坐标_GFp

privkey = OpenSSL.malloc)

pubkeyx = OpenSSL.malloc)

publikey y = OpenSSL . malloc)

OpenSSL。BN_bn2bin

privkey = privkey.raw

OpenSSL。BN_bn2bin

pubkeyx = pubkeyx.raw

OpenSSL。BN_bn2bin

pubkeyy = pubkeyy.raw

#self.raw_check_key

full_privkey=pack+装) + privkey

full_pubkey=pack+装) + pubkeyx + pack)+pubceyy

返回full_privkey，full_pubkey

最后:

#释放c指针

OpenSSL。无密钥

OpenSSL。BN_free

OpenSSL。BN_free

def ecdh_key:

#键应该是二进制格式

a_curve=int。编码，16)

b_curve=int。编码，16)

if _ curve！= b_curve:

引发异常

sx=int。编码，16)

sy=int。编码，16)

pub_x，pub_y = b_pubkey，b_pubkey

b_key=OpenSSL。EC _ KEY _ new _ by _ curve _ name

_pub_x=OpenSSL。BN_bin2bn

_pub_y=OpenSSL。BN_bin2bn

_group=OpenSSL。EC_KEY_get0_group

_pubkey=OpenSSL。EC_POINT_new

OpenSSL。EC _ POINT _ set _仿射_坐标_GFp

OpenSSL。EC_KEY_set_public_key

#OpenSSL。EC_KEY_check_key

s=int，16)

priv=a_privkey

a_key=OpenSSL。EC _ KEY _ new _ by _ curve _ name

_privkey=OpenSSL。BN_bin2bn，0)

OpenSSL。EC_KEY_set_private_key

#ECDH

OpenSSL。ECDH_set_method)

ecdh_buf = OpenSSL.malloc#计算的缓冲区大小应与密钥长度相同

ecdh_keylen=OpenSSL。ecdh _计算_密钥

返回ecdh_buf.raw

来自加密。密码导入AES

def encrypt:

ecdp=ecdh_key

shared_key=hashlib.md5。我们的二维码场景需要128位密钥

obj = AES.new

密文= obj.encrypt

QR =。编码

返回qr

def decrypt:

qr=qr.decode

sx=int，16)

sy=int，16)

a_pubkey=qr

密文=qr

ecdh2=ecdh_key

shared_key=hashlib.md5。摘要

obj = AES.new

content = obj.decrypt

返回内容

a = gen _ EC _ keypair#密钥是短暂的，每次都会生成

b = gen _ EC _ keypair#在实际代码中，该密钥对应该来自服务器，客户端只有其公钥

打印“为ECDH密钥交换生成的电子商务对:”

打印'爱丽丝->；Private:'+ a。编码，'公共:'+ a。编码

打印'鲍勃->；Private:' + b。编码，'公共:'+ b。编码

e1= ecdh_key

e2=ecdh_key #e2仅用于服务器代码

打印e1.encode

打印e2.encode

bm=buffer

qr=加密

打印'二维码大小为'，len，':'，二维码

#导入二维码

#qrcode.make。显示

#服务器执行以下操作:

内容=解密

打印“解密后，内容为”，内容

openssl_wrapper.py

#!/usr/bin/env python

# -*-编码:utf-8 -*-

导入系统

导入ctypes

import ctypes.util

OpenSSL =无

类别密码名称:

def __init__:

自我。_name = name

自我。_指针=指针

自我。_blocksize = blocksize

def __str__:

返回“密码:“+自我”。_ name+" | Blocksize:“+str+" | Foaction指针:"+ str

def get_pointer:

回归自我。指针

def get_name:

回归自我。名称

def get_blocksize:

回归自我。块大小

class _OpenSSL:

"""

使用ctypes的OpenSSL包装器

"""

def __init__:

"""

构建包装

"""

自我。_lib = ctypes。CDLL

self.pointer = ctypes.pointer

self.c_int = ctypes.c_int

self.byref = ctypes.byref

self . create _ string _ buffer = ctypes . create _ string _ buffer

自我。BN_new = self。_lib。BN_new

自我。BN _ new . rest type = ctypes . c _ void _ p

自我。BN_new.argtypes =

自我。BN_free = self。_lib。BN_free

自我。BN _ free.restype =无

自我。BN _ free . arg types =

自我。BN_num_bits = self。_lib。BN _ num _ bits

自我。BN _ num _ bits . rest type = ctypes . c _ int

自我。BN _ num _ bits . arg types =

自我。BN_bn2bin = self。_lib。BN_bn2bin

自我。BN _ BN 2 bin . rest type = ctypes . c _ int

自我。BN _ BN 2 bin . arg types =

自我。BN_bin2bn = self。_lib。BN_bin2bn

自我。BN _ bin2bn . rest type = ctypes . c _ void _ p

自我。BN _ bin2bn . arg types =

自我。EC_KEY_free = self。_lib。EC_KEY_free

自我。EC _ KEY _ free.restype =无

自我。EC _ KEY _ free . arg types =

自我。EC_KEY_new_by_curve_name = self。_lib。EC_KEY_new_by_curve_name

自我。EC _ KEY _ new _ by _ curve _ name . rest type = ctypes . c _ void _ p

自我。EC _ KEY _ new _ by _ curve _ name . arg types =

自我。EC_KEY_generate_key = self。_lib。EC_KEY_generate_key

自我。EC _ KEY _ generate _ KeY . rest type = ctypes . c _ int

自我。EC _ KEY _ generate _ KeY . arg types =

自我。EC_KEY_check_key = self。_lib。EC_KEY_check_key

自我。EC _ KEY _ check _ KeY . rest type = ctypes . c _ int

自我。EC _ KEY _ check _ KeY . arg types =

自我。EC_KEY_get0_private_key = self。_lib。EC_KEY_get0_private_key

自我。EC _ KEY _ get0 _ private _ KeY . rest type = ctypes . c _ void _ p

自我。EC _ KEY _ get0 _ private _ KeY . arg types =

自我。EC_KEY_get0_public_key = self。_lib。EC_KEY_get0_public_key

自我。EC _ KEY _ get0 _ public _ KeY . rest type = ctypes . c _ void _ p

自我。EC _ KEY _ get0 _ public _ KeY . arg types =

自我。EC_KEY_get0_group = self。_lib。EC_KEY_get0_group

自我。EC _ KEY _ get0 _ group . rest type = ctypes . c _ void _ p

自我。EC _ KEY _ get0 _ group . arg types =

自我。EC _ POINT _ get _仿射_坐标_GFp = self。_lib。EC _ POINT _ get _仿射_坐标_GFp

自我。EC _ POINT _ get _仿射_坐标_ GFp . rest type = ctypes . c _ int

自我。EC _ POINT _ get _仿射_坐标_GFp.argtypes =

自我。EC_KEY_set_private_key = self。_lib。EC_KEY_set_private_key

自我。EC _ KEY _ set _ private _ KeY . rest type = ctypes . c _ int

自我。EC _ KEY _ set _ private _ KeY . arg types =

自我。EC_KEY_set_public_key = self。_lib。EC_KEY_set_public_key

自我。EC _ KEY _ set _ public _ KeY . rest type = ctypes . c _ int

自我。EC _ KEY _ set _ public _ KeY . arg types =

自我。EC_KEY_set_group = self。_lib。EC_KEY_set_group

自我。EC _ KEY _ set _ group . rest type = ctypes . c _ int

自我。EC _ KEY _ set _ group . arg types =

自我。EC _ POINT _ set _仿射_坐标_GFp = self。_lib。EC _ POINT _ set _仿射_坐标_GFp

自我。EC _ POINT _ set _仿射_坐标_ GFp . rest type = ctypes . c _ int

自我。EC _ POINT _ set _仿射_坐标_GFp.argtypes =

自我。EC_POINT_new = self。_lib。EC_POINT_new

自我。EC _ POINT _ new . rest type = ctypes . c _ void _ p

自我。EC _ PONT _ new . arg types =

自我。EC_POINT_free = self。_lib。EC_POINT_free

自我。EC _ POINT _ free.restype = None

自我。EC _ POINT _ free . arg types =

自我。EC_KEY_set_private_key = self。_lib。EC_KEY_set_private_key

自我。EC _ KEY _ set _ private _ KeY . rest type = ctypes . c _ int

自我。EC _ KEY _ set _ private _ KeY . arg types =

自我。ECDH_OpenSSL = self。_lib。ECDH_OpenSSL

自我。_lib。ECDH _ OpenSSL . rest type = ctypes . c _ void _ p

自我。_lib。ECDH_OpenSSL.argtypes =

自我。ECDH _设置_方法=自我。_lib。ECDH _集合_方法

自我。_lib。ECDH _ set _ method . rest type = ctypes . c _ int

自我。_lib。ECDH _ set _ method . arg types =

自我。ECDH _计算_键=自我。_lib。ECDH _计算_密钥

自我。ECDH _ compute _ key . rest type = ctypes . c _ int

自我。ECDH _ compute _ key . arg types =

自我。EVP_CipherInit_ex = self。_lib。EVP_CipherInit_ex

自我。EVP _ Cipherinit _ ex . rest type = ctypes . c _ int

自我。EVP _ Cipherinit _ ex . arg types =

自我。EVP_CIPHER_CTX_new = self。_lib。EVP _ CIPHER _ CTX _新

自我。EVP _ CIPHER _ CTX _ new . rest type = ctypes . c _ void _ p

自我。EVP_CIPHER_CTX_new.argtypes =

#密码

自我。EVP_aes_128_cfb128 = self。_lib。EVP_aes_128_cfb128

自我。EVP _ AES _ 128 _ CFB 128 . rest type = ctypes . c _ void _ p

自我。EVP_aes_128_cfb128.argtypes =

自我。EVP_aes_256_cfb128 = self。_lib。EVP_aes_256_cfb128

自我。EVP _ AES _ 256 _ CFB 128 . rest type = ctypes . c _ void _ p

自我。EVP_aes_256_cfb128.argtypes =

自我。EVP_aes_128_cbc = self。_lib。EVP_aes_128_cbc

自我。EVP _ AES _ 128 _ CBC . rest type = ctypes . c _ void _ p

自我。EVP_aes_128_cbc.argtypes =

自我。EVP_aes_256_cbc = self。_lib。EVP_aes_256_cbc

自我。EVP _ AES _ 256 _ CBC . rest type = ctypes . c _ void _ p

自我。EVP_aes_256_cbc.argtypes =

#自我。EVP _ aes _ 128 _ ctr = self。_lib。EVP_aes_128_ctr

#自我。EVP _ AES _ 128 _ ctrl . rest type = ctypes . c _ void _ p

#自我。EVP _ AES _ 128 _ ctrl . arg types =

#自我。EVP _ aes _ 256 _ ctr = self。_lib。EVP_aes_256_ctr

#自我。EVP _ AES _ 256 _ ctrl . rest type = ctypes . c _ void _ p

#自我。EVP _ AES _ 256 _ ctrl . arg types =

自我。EVP_aes_128_ofb = self。_lib。EVP_aes_128_ofb

自我。EVP _ AES _ 128 _ ofb . rest type = ctypes . c _ void _ p

自我。EVP_aes_128_ofb.argtypes =

自我。EVP_aes_256_ofb = self。_lib。EVP_aes_256_ofb

自我。EVP _ AES _ 256 _ ofb . rest type = ctypes . c _ void _ p

自我。EVP_aes_256_ofb.argtypes =

自我。EVP_bf_cbc = self。_lib。EVP_bf_cbc

自我。EVP _ BF _ CBC . rest type = ctypes . c _ void _ p

自我。EVP_bf_cbc.argtypes =

自我。EVP_bf_cfb64 = self。_lib。EVP_bf_cfb64

自我。EVP _ BF _ CFB 64 . rest type = ctypes . c _ void _ p

自我。EVP_bf_cfb64.argtypes =

自我。EVP_rc4 = self。_lib。EVP_rc4

自我。EVP _ RC 4 . rest type = ctypes . c _ void _ p

自我。EVP_rc4.argtypes =

自我。EVP_CIPHER_CTX_cleanup = self。_lib。EVP _ CIPHER _ CTX _清理

自我。EVP _ CIPHER _ CTX _ clean up . rest type = ctypes . c _ int

自我。EVP _ CIPHER _ CTX _ clean up . arg types =

自我。EVP_CIPHER_CTX_free = self。_lib。免费CTX

自我。EVP _ CIPHER _ CTX _ free . rest type = None

自我。EVP _ CIPHER _ CTX _ free . arg types =

自我。EVP _ CipherUpdate = self。_lib。EVP _密码更新

自我。EVP _ FierUpdate . rest type = ctypes . c _ int

自我。EVP _ FierUpdate . arg types =

自我。EVP_CipherFinal_ex = self。_lib。EVP _密码最终_ex

自我。EVP _ FierField _ ex . rest type = ctypes . c _ int

自我。EVP _ CipherFinal _ ex . arg types =

自我。EVP_DigestInit = self。_lib。EVP_DigestInit

自我。EVP _ digest init . rest type = ctypes . c _ int

自我。_lib。EVP _ digest init . arg types =

自我。EVP_DigestUpdate = self。_lib。EVP_DigestUpdate

自我。EVP _ digestupdate . rest type = ctypes . c _ int

自我。EVP _ digestupdate . arg types =

自我。EVP_DigestFinal = self。_lib。EVP_DigestFinal

自我。EVP _ digest final . rest type = ctypes . c _ int

自我。EVP _ digest final . arg types =

自我。EVP_ecdsa = self。_lib。EVP_ecdsa

自我。_lib。EVP _ ECD sa . rest type = ctypes . c _ void _ p

自我。_lib。EVP_ecdsa.argtypes =

自我。ECDSA_sign = self。_lib。ECDSA_sign

自我。ECDSA _ sign . rest type = ctypes . c _ int

自我。ECDSA _ sign . arg types =

自我。ECDSA_verify = self。_lib。ECDSA _验证

自我。ECDSA _ verify . rest type = ctypes . c _ int

自我。ECDSA _ verify . arg types =

自我。EVP_MD_CTX_create = self。_lib。EVP _ MD _ CTX _创建

自我。EVP _ MD _ CTX _ create . restype = ctypes . c _ void _ p

自我。EVP_MD_CTX_create.argtypes =

自我。EVP_MD_CTX_init = self。_lib。EVP_MD_CTX_init

自我。EVP _ MD _ CTX _ init . rest type =无

自我。EVP _ MD _ CTX _ init . arg types =

自我。EVP_MD_CTX_destroy = self。_lib。EVP _ MD _ CTX _破坏

自我。EVP _ MD _ CTX _ destroy . rest type = None

自我。EVP _ MD _ CTX _ destroy . arg types =

自我。RAND_bytes = self。_lib。RAND _字节

自我。RAND _ bytes.restype =无

自我。RAND _ bytes . arg types =

自我。EVP_sha256 = self。_lib。EVP_sha256

自我。EVP _ sha 256 . rest type = ctypes . c _ void _ p

自我。EVP_sha256.argtypes =

自我。EVP_sha512 = self。_lib。EVP_sha512

自我。EVP _ sha 512 . rest type = ctypes . c _ void _ p

自我。EVP_sha512.argtypes =

自我。HMAC =自我。_lib。HMAC

自我。HMAC . rest type = ctypes . c _ void _ p

自我。HMAC.argtypes =

#自我。PKCS5_PBKDF2_HMAC =自我。_lib。PKCS5_PBKDF2_HMAC

#自我。PKCS5 _ PBKDF 2 _ HMAC . rest type = ctypes . c _ int

#自我。PKCS5 _ PBKDF 2 _ HMAC . arg types =

自我。_set_ciphers

自我。_set_curves

def _set_ciphers:

self.cipher_algo = {

' aes-128-cbc ':密码名，

“aes-256-cbc”:密码名，

' aes-128-cfb ':密码名，

“aes-256-cfb”:密码名，

“aes-128-ofb”:密码名，

“aes-256-ofb”:密码名，

#'aes-128-ctr ':密码名，

#'aes-256-ctr ':密码名，

' bf-cfb ':密码名，

' bf-cbc ':密码名，

' rc4 ':密码名，# 128是初始化大小，不是块大小

}

def _set_curves:

self.curves = {

secp112r1': 704，

secp112r2': 705，

secp128r1': 706，

secp128r2': 707，

secp160k1': 708，

secp160r1': 709，

secp160r2': 710，

secp192k1': 711，

secp224k1': 712，

secp224r1': 713，

secp256k1': 714，

secp384r1': 715，

secp521r1': 716，

第113r1节:717，

section 113 r 2 ':718，

section 131 R1 ':719，

section 131 r 2 ':720，

section 163 k1 ':721，

第163r1节:722，

section 163 r 2 ':723，

section 193 r 1 ':724，

section 193 r 2 ':725，

section 233 k1 ':726，

第233r1节:727，

section 239 k1 ':728，

section 283 k1 ':729，

第283r1节:730，

section 409 k1 ':731，

section 409 R1 ':732，

section 571 k1 ':733，

section 571 R1 ':734，

prime256v1': 415，

}

def _ BN _ num _ bytes:

"""

返回一个字符串的长度

"""

return int + 7) / 8)

def get_cipher:

"""

返回OpenSSL密码实例

"""

如果名称不在self.cipher_algo中:

引发异常

return self.cipher_algo

def get_curve:

"""

返回椭圆曲线的id

"""

如果名称不在自我曲线中:

引发异常

返回self.curves

def get_curve_by_id:

"""

返回带有id的椭圆曲线的名称

"""

res =无

自我曲线中的我:

if self.curves == id:

res = i

打破

如果分辨率为无:

引发异常

返回资源

def rand:

"""

OpenSSL随机函数

"""

buffer = self.malloc

自我。RAND _字节

返回缓冲区. raw

def malloc:

"""

返回create_string_buffer

"""

缓冲=无

if数据！= 0:

如果sys.version_info.major == 3且isinstance):

data = data.encode

buffer = self . create _ string _ buffer

else:

buffer = self . create _ string _ buffer

返回缓冲器

libname = ctypes . util . find _ library

如果库名为“无”:

#对于Windows...

libname = ctypes . util . find _ library

如果库名为“无”:

引发异常

OpenSSL = _OpenSSL

Python代码下载链接:https://pan.baidu.com/s/1nvbyl3F密码:02km

0×03汇总

一般来说，椭圆曲线是密码学中的硬骨头，类似于传统的大整数分解、离散对数等问题。由于难度较大，本文先在这里举报一个失败，下期会带来对ECC的深入了解。

*本文原作者:苗苗Xi、怀，本文属于FreeBuf原创奖励计划，未经许可禁止转载。