【网络安全】【密码学】常见数据加(解)密算法及Python实现(二)、椭圆曲线密码ECC

发布时间:2024年01月05日

本文介绍椭圆曲线密码及其Python实现。

一、实验目的

1、 掌握椭圆曲线上的点间四则运算和常见的椭圆曲线密码算法
2、 了解基于ECC的伪随机数生成算法和基于椭圆曲线的商用密码算法。

二、算法原理

1、算法简介

椭圆曲线密码学(Elliptic Curve Cryptography,ECC)是一种基于椭圆曲线数学的公开密钥加密算法。椭圆曲线在密码学中的使用是在1985年由Neal Koblitz和Victor Miller分别独立提出的。
ECC的主要优势是在某些情况下它比其他的算法(比如RSA加密算法)使用更小的密钥并提供相当的或更高等级的安全。ECC的另一个优势是可以定义群之间的双线性映射,基于Weil对或是Tate对;双线性映射已经在密码学中发现了大量的应用,例如基于身份的加密。

2、椭圆曲线的数学原理

椭圆曲线(ECC)可以用下述方程表示
y^^2 = x^^3 + ax + b,其中a、b是实数,椭圆曲线记为E(a,b)。由方程可知,每一条椭圆曲线都关于x轴对称。
1、加法(+):
为了在群上定义加法,参数a和b需要满足不等式4a^^3 + 27b^^2 ≠ 0.加法的运算规则为:若椭圆曲线上的3个点在同一条直线上,则它们的和为O(无穷远点)。
2、减法(-):
点P的负元定义如下:
点P(x,y)的负元是具有相同x坐标和相反的y坐标的点,即若P = (x,y),则-P = (x, -y)。则P和-P可用一条垂直的线连接起来,且P + (-P) = P – P = 0.
P – Q = P + (-Q)。
3、数乘
n为非负整数,则nP = P + …… + P(n个P相加)。
4、除法
m为非负整数,则P / m = P * m^^-1,其中m-1为m在模p下的逆元。

3、椭圆曲线加密原理

首先,将要发送的消息明文m编码为形为(x,y)的点Pm,并对点Pm进行加密和其后的解密。加/解密系统需要点G和椭圆群参数(p,a,b)。用户A悬念则一个私钥nA,并产生公钥PA = nA * G. A随机选择一个正整数k,并产生密文Cm,该密文时一个点对
Cm = {kG, Pm + kPB},其中PB为B的公钥。B在对密文解密时,则需用第二个点减去第一个点与B的私钥之积,得到消息Pm。
算法流程由下图简要表示:
在这里插入图片描述

三、算法实现

1、Python代码

文件1ecc.py,定义椭圆曲线上的运算
文件内容:

# 加法
def add(xp, yp, xq, yq, a, b, p):  # 计算(Zp上的)椭圆曲线上两点P(xp, yp)和Q(xq, yq)的和
    if (4 * (a ** 3) + 27 * (b ** 2)) % p == 0:
        print('不能形成abel群')
        return
    else:
        if yp + yq == 0:
            print('infinity')
            return
        else:
            if (xp == xq) and (yp == yq):
                delta = (3 * (xp ** 2) + a) * inverse((2 * yp), p) % p
                xr = (delta ** 2 - xp - xq) % p
                yr = (-yp + delta * (xp - xr)) % p
                return xr, yr
            else:
                delta = (yq - yp) * inverse((xq - xp), p) % p
                xr = (delta ** 2 - xp - xq) % p
                yr = (-yp + delta * (xp - xr)) % p
                return xr, yr

# 减法
def sub(xp, yp, xq, yq, a, b, p):
    return add(xp, yp, xq, -yq, a, b, p)

# 乘法
def mul(n, xp, yp, a, b, p):
    ans_x = xp
    ans_y = yp
    for i in range(0, n - 1):
        (ans_x, ans_y) = add(ans_x, ans_y, xp, yp, a, b, p)
    return ans_x, ans_y

# 求逆
def inverse(a, p):
    for i in range(1, p):
        if ((i * a) % p) == 1:
            return i

# 除法
def div(n, xp, yp, a, b, p):
    m = inverse(n, p)
    return mul(m, xp, yp, a, b, p)

# 以下为测试
# print(add(-3, 9, -2, 8, 0, -36, 11))
# print(sub(10, 2, 3, 5, 1, 6, 11))
# print(mul(7, 8, 3, 1, 6, 11))
# print(inverse(2, 3))
# print(div(12, 3, 10, 1, 1, 23))

文件2dh.py,用于产生公钥和私钥
文件内容:

from ecc import *


def generateKey_a(na, xg, yg, a, b, p):
    (x_pa, y_pa) = mul(na, xg, yg, a, b, p)
    return x_pa, y_pa


def generateKey_b(nb, xg, yg, a, b, p):
    (x_pb, y_pb) = mul(nb, xg, yg, a, b, p)
    return x_pb, y_pb


def secret_a(na, x_pb, y_pb, a, b, p):
    (xka, yka) = mul(na, x_pb, y_pb, a, b, p)
    return xka, yka


def secret_b(nb, x_pa, y_pa, a, b, p):
    (xkb, ykb) = mul(nb, x_pa, y_pa, a, b, p)
    return xkb, ykb


(xpa, ypa) = generateKey_a(121, 2, 2, 0, -4, 211)
(xpb, ypb) = generateKey_b(203, 2, 2, 0, -4, 211)
(xka, yka) = secret_a(121, xpb, ypb, 0, -4, 211)
(xkb, ykb) = secret_b(203, xpa, ypa, 0, -4, 211)
print('A的私钥:121')
print('B的私钥:203')
print('A的公钥:', xpa, ypa)
print('B的公钥:', xpb, ypb)
print('A产生的秘密钥: ', xka, yka)
print('B产生的秘密钥: ', xkb, ykb)

文件3crypt.py,用于椭圆曲线加、解密
文件内容:

from dh import *


def encrypt(pm_x, pm_y):  # 椭圆曲线加密
    (x_pb, y_pb) = generateKey_b(101, 2, 2, 0, -4, 257)
    k = 41
    (cm1_x, cm1_y) = mul(k, 2, 2, 0, -4, 257)  # Cm1 = kG
    (temp_x, temp_y) = mul(k, x_pb, y_pb, 0, -4, 257)
    (cm2_x, cm2_y) = add(temp_x, temp_y, pm_x, pm_y, 0, -4, 257)
    return cm1_x, cm1_y, cm2_x, cm2_y


def decrypt(cm1_x, cm1_y, cm2_x, cm2_y):  # 椭圆曲线解密
    nb = 101
    (tempx, tempy) = mul(nb, cm1_x, cm1_y, 0, -4, 257)
    (pmx, pmy) = sub(cm2_x, cm2_y, tempx, tempy, 0, -4, 257)
    return pmx, pmy


(cm1x, cm1y, cm2x, cm2y) = encrypt(112, 26)
(pmx, pmy) = decrypt(136, 128, 246, 174)
# (xpb, ypb) = generateKey_b(101, 2, 2, 0, -4, 257)
# print(xpb)
# print(ypb)
# (kpbx, kpby) = mul(41, xpb, ypb, 0, -4, 257)
# print(kpbx)
# print(kpby)
print('加密结果:')
print(cm1x)
print(cm1y)
print(cm2x)
print(cm2y)
print()
print('解密结果:')
print(pmx)
print(pmy)

2、运行测试

经运行,解密结果==明文

在这里插入图片描述

至此,本次实验结束。

四、参考文献

1、《密码编码学与网络安全——原理与实践(第七版)》(Cryptography and Network Security, Principles and Practice, Seventh Edition),【美】威廉 斯托林斯 William Stallings 著,王后珍等 译,北京,电子工业出版社,2017年12月。

2、《密码学实验教程》,郭华 刘建伟等 主编,北京,电子工业出版社,2021年1月。

文章来源:https://blog.csdn.net/weixin_43031313/article/details/135405209
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。