ECC密码与RSA

本文主要是介绍ECC密码与RSA，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、ECC密码（椭圆曲线密码）

     1.基本知识

              定义：

       ECC 全称为椭圆曲线加密，EllipseCurve Cryptography，是一种基于椭圆曲线数学的公钥密码。与传统的基于大质数因子分解困难性的加密方法不同，ECC 依赖于解决椭圆曲线离散对数问题的困难性。它的优势主要在于相对于其它方法，它可以在使用较短密钥长度的同时保持相同的密码强度。

      目前椭圆曲线主要采用的有限域有

• 以素数为模的整数域 GF(p)，通常在通用处理器上更为有效。
• 特征为 2 的伽罗华域 GF（2^m），可以设计专门的硬件。

     

椭圆曲线的确定

描述一条Fp上的椭圆曲线，常用到六个参数：
T=(p,a,b,G,n,h)。
p 、a 、b 用来确定一条椭圆曲线，
G为基点，
n为点G的阶，
h 是椭圆曲线上所有点的个数m与n相除的整数部分。
这几个参数取值的选择，直接影响了加密的安全性。参数值一般要求满足以下几个条件：

p 当然越大越安全，但越大，计算速度会变慢，200位左右可以满足一般安全要求；
p≠n×h；
pt≠1 (mod n)，1≤t<20；
4a3 + 27b2 ≠ 0 (mod p)；
n 为素数；
h≤4

    

公钥

    椭圆曲线的公钥实际上是曲线上的一个点，可以用坐标点（x,y）表示，通常是将x和y的值分别转换成字符串来存储和传输，如下是一个公钥的例子
57E1174B773A91E743BC719C9C8B24C8F25096411744C0EB09C13AAD4073D547
BBD7DA078002F7C84441B196A8B8532E0046BA8ED71DED0B9E2BEACA31F1EE9A
其中57E1174B773A91E743BC719C9C8B24C8F25096411744C0EB09C13AAD4073D547为公钥的x点坐标，BBD7DA078002F7C84441B196A8B8532E0046BA8ED71DED0B9E2BEACA31F1EE9A为公钥的y点坐标，实际在计算的时候，需要把这些字符串中的元素按照其字面的值转为对应的十六进制，如：0x57，0xE1…
上述是公钥的非压缩表示，通常需要还在坐标点前加上一个字节0x04用于表示使用非压缩的方式，即0457E1174B773A91E743BC719C9C8B24C8F25096411744C0EB09C13AAD4073D547BBD7DA078002F7C84441B196A8B8532E0046BA8ED71DED0B9E2BEACA31F1EE9A。
还有一种压缩的表示方式。根据椭圆曲线方程，我们只需要知道 x 坐标，就可以通过方程计算出 y 坐标，这样就不用同时保存x，y的值，减少了存储和带宽。但是如果只知道x，带入方程会求出两个y，一正一负，对应两个不同的点，所以还必须有一个标志来区别实际使用的是哪个。所以通常采用下面的约定，具体格式为：

前缀02 + x （当y为偶数）
前缀03 + x （当y为奇数）
可以仅用一个坐标长度+1bit表示整个公钥，比如：
02f54ba86dc1ccb5bed0224d23f01ed87e4a443c47fc690d7797a13d41d2340e1a

私钥

私钥是一个随机数，通常是把其十六进制下的数据当作字符串保存（和公钥的保存形式一样），如下：
0A7ECE7EFCA5C5A186FF7340125E2E1F1754D8F27922573F66ABA43D8DA3ECDE
这个私钥其实就是0x0A，0x7E，0xCE…

     椭圆曲线方程

这是在有限域GF（p）上，p为一个很多的素数

椭圆曲线上的运算：
     

      加法：如果椭圆曲线上的三个点位于同一直线上，那么它们的和为O，

O 为加法的单位元，对于椭圆曲线上的任意一点p，有p+ O =p；

椭圆曲线上的一点p=（Xp，Yp），它的加法的逆元-p=（-Xp，-Yp）。这两个点可以用一条垂直的线连起来p+(-p)=p-p=O;

     

密钥生成

    用户 A 先选择一条椭圆曲线Eq(a,b) ，然后选择其上的一个生成元 G，假设其阶为 n，之后再选择一个正整数na 作为密钥，计算Pa=naG

其中，Eq(a,b),q,G都会被公开。公钥为Pa，私钥为 $n_a $。

加密过程

 官方说法，用户 B 在向用户 A 发送消息 m，这里假设消息 m 已经被编码为椭圆曲线上的点，其加密步骤如下

1. 查询用户 A 的公钥Eq(a,b),q,Pa，
2. 在 (1,q-1) 的区间内选择随机数 k 。
3. 根据 A 的公钥计算点(x1,y1)=kG。
4. 计算点(x2,y2)=kPa
5. 如果为 O，则从第二步重新开始。
6. 计算C=m+(x2,y2)
7. 将((x1,y1),C)
8. 发送给 A。

解密过程

1. 利用私钥计算点na(x1,y1)=nakG=kPa=(x2,y2)。
2. 计算消息m=C−(x2,y2)。

二、RSA密码与ECC密码的区别

      RSA：RSA加密算法是应用较早的算法之一，它在密码学领域具有奠基性地位。相较于后来出现的ECC算法，RSA在兼容性和普遍适用性上表现出更强的优势，在传统的数字签名场景中广泛部署。

       ECC：在提供相同安全级别的情况下，ECC所需的密钥长度更短，有效降低了计算资源消耗和存储需求，提高了加密与解密的速度。尽管RSA目前在兼容性和普遍性上仍占有优势，但随着硬件性能的发展以及对效率要求的提升，ECC加密算法因其高效特性而逐渐受到更多关注并得到广泛应用。

三、ECC与SM2

      SM2于2016年成为中国国家密码标准，在商用密码体系中，SM2主要用于替换RSA加密算法。

四、例题

          

[watevrCTF 2019]ECC-RSA

我们可以知道了是RSA和ECC的共同解密

from fastecdsa.curve import P521 as Curve
from fastecdsa.point import Point      #椭圆曲线的操作from Crypto.Util.number import bytes_to_long, isPrime   #数字转换和素数检测from os import urandom
from random import getrandbits      #用于生成随机数def gen_rsa_primes(G):urand = bytes_to_long(urandom(521//8))while True:s = getrandbits(521) ^ urand        #生成随机数#坐标轴Q = s*Gif isPrime(Q.x) and isPrime(Q.y):print("ECC Private key:", hex(s))print("RSA primes:", hex(Q.x), hex(Q.y))print("Modulo:", hex(Q.x * Q.y))return (Q.x, Q.y)#这里的p，q相当于ECC中的x，yflag = int.from_bytes(input(), byteorder="big")ecc_p = Curve.p
a = Curve.a
b = Curve.bGx = Curve.gx
Gy = Curve.gy
G = Point(Gx, Gy, curve=Curve)e = 0x10001
p, q = gen_rsa_primes(G)
n = p*qfile_out = open("downloads/ecc-rsa.txt", "w")file_out.write("ECC Curve Prime: " + hex(ecc_p) + "\n")
file_out.write("Curve a: " + hex(a) + "\n")
file_out.write("Curve b: " + hex(b) + "\n")
file_out.write("Gx: " + hex(Gx) + "\n")
file_out.write("Gy: " + hex(Gy) + "\n")file_out.write("e: " + hex(e) + "\n")
file_out.write("p * q: " + hex(n) + "\n")c = pow(flag, e, n)
file_out.write("ciphertext: " + hex(c) + "\n")

椭圆曲线点的坐标不一定是素数

      满足了椭圆方程  ：    y^2=x^3+a*x+b;      p,q相当于里面的x,y

n=p*q

   化成了，q^2=p^3+a*p+b,

继续化简得到了：
        n*n=p^5+a*p^3+b*p^2

那么就开是解题了：
      在Sage：

a=-0x3      #十六进制的-3b=0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00n=0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28fp0=0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff      #定义了一个非常大的素数R.<x>=Zmod(p0)[]      #创建一个模p0的整数环上的多项式环R[x] f=x**5+a*x**3+b*x**2-n*nf.roots()       #计算多项式在模p0下的根

最终的p:

4573744216059593260686660411936793507327994800883645562370166075007970317346237399760397301505506131100113886281839847419425482918932436139080837246914736557

接下来就是RSA的常规计算：
 

from gmpy2 import*
from libnum import*
n = 0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28f
c = 0x3862c872480bdd067c0c68cfee4527a063166620c97cca4c99baff6eb0cf5d42421b8f8d8300df5f8c7663adb5d21b47c8cb4ca5aab892006d7d44a1c5b5f5242d88c6e325064adf9b969c7dfc52a034495fe67b5424e1678ca4332d59225855b7a9cb42db2b1db95a90ab6834395397e305078c5baff78c4b7252d7966365afed9ep = 4573744216059593260686660411936793507327994800883645562370166075007970317346237399760397301505506131100113886281839847419425482918932436139080837246914736557
e = 0x10001
q  = n//pphi = (p-1)*(q-1)
d = invert(e,phi)
m = pow(c,d,n)
print(n2s(m))      #使用 libnum 的 n2s 函数将解密后的整数 m 转换为字符串并打印出来。
这假设 m 是一个以某种方式编码（如ASCII或UTF-8）的字符串的数值表示

    这里出现了问题：

            

      报错说明了经过，m=pow(c,d,n)后面它的数据类型已经变为了gmpy2.mpz，然而libnum

期待·的数据类型是Python的原生整数（int型），一般直接进行转换就可以了。

那么加上：

# 将 m 转换为 Python 原生整数

m_int = int(m)

   

   最终就可以得到了flag

[第五空间 2021]ecc

这个题目看起来比较简单，主要分为三个部分来解答，

第一部分比较简单，

  

from Crypto.Util.number import *
p = 146808027458411567
a = 46056180
b = 2316783294673
E = EllipticCurve(GF(p),(a,b))
P = E(119851377153561800,50725039619018388)
Q = E(22306318711744209,111808951703508717)num1 =  discrete_log(Q,P,operation = '+')

第二部分：
 

p = 1256438680873352167711863680253958927079458741172412327087203
a = 377999945830334462584412960368612
b = 604811648267717218711247799143415167229480
E = EllipticCurve(GF(p),[a,b])
P = E(550637390822762334900354060650869238926454800955557622817950,700751312208881169841494663466728684704743091638451132521079)
Q = E(1152079922659509908913443110457333432642379532625238229329830,819973744403969324837069647827669815566569448190043645544592) 
# Q = k * P
n = E.order()def Pohlig_Hellman(n,P,Q):factors, exponents = zip(*factor(n))primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]print(primes)dlogs = []for fac in primes:t = int(int(P.order()) // int(fac))dlog = discrete_log(t*Q,t*P,operation="+")dlogs += [dlog]print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime ordernum2 = crt(dlogs,primes)return num2num2 = Pohlig_Hellman(n,P,Q)

第三部分：
 

p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
B = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
E = EllipticCurve(GF(p),[A,B])
P = E(10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861,8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610)
Q = E(964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927,5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537)def SmartAttack(P,Q,p):E = P.curve()Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)for P_Qp in P_Qps:if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:breakQ_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)for Q_Qp in Q_Qps:if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:breakp_times_P = p*P_Qpp_times_Q = p*Q_Qpx_P,y_P = p_times_P.xy()x_Q,y_Q = p_times_Q.xy()phi_P = -(x_P/y_P)phi_Q = -(x_Q/y_Q)k = phi_Q/phi_Preturn ZZ(k)num3 = SmartAttack(P, Q, p)

拼接起来，最终得到了：

print(long_to_bytes(num1) + long_to_bytes(num2) + long_to_bytes(num3))

# NSSCTF{025ab3d9-2521-4a81-9957-8c3381622434}

仔细研究一下大神的脚本，

     里面涉及了pohlig_hellman算法，接下来学习一下，Pohlig-Hellman算法主要是去破解这个群的阶为光滑数的离散对数，所以使用这个算法的前提是椭圆曲线所在的阶的是不是光滑数。

      光滑数，如果一个数的所有质因数都小于等于B，那么我们称这个数为B-光滑数(B-Smooth Integer)。

    

例如：2×32×53×7=15750因为15750的所有质因数为{3,5,7}，
其中7为质因数最大的值，所以该15750是一个7−光滑数需要注意的是，
一个数如果被称之为B−光滑数，那么这个B不一定是这个数的质因数例如上面的式子，
他也可以叫做8−光滑数、13−光滑数等。

在sagemath上，实现该算法，

def PohligHellman(p,a,b,P,G):E = EllipticCurve(GF(p),[a,b]) n = E.order()factors = factor(n)print(factors)result = []factors = [4 ,3 , 1170811] #  for f1  in factors:t = n //f1res = discrete_log(t*P,t*G,operation='+')result  += [res]print(result)k = crt(result,factors)return k

第三部分里面还使用了Smart' Attack

    

    异常子群

      异常子群是椭圆曲线上哪些整个子群的阶，是有限域的模数p的整倍数的点的集合。

因为异常曲线的阶就等于p，所以异常曲线本身就是一个异常子群。

    Smart’s 攻击

          异常曲线可以被特定的攻击方式所破解，其中一个著名的是所谓的Smart’s 攻击。

Smart’s 攻击利用了椭圆曲线上的点可以通过一个同态映射（有限域同态映射）映射到有限域的模数p的加法群上去。

p = 
A = 
B = 
E = EllipticCurve(GF(p),[A,B])
P = E(,)
Q = E(,)
def SmartAttack(P,Q,p):E = P.curve()Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)for P_Qp in P_Qps:if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:breakQ_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)for Q_Qp in Q_Qps:if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:breakp_times_P = p*P_Qpp_times_Q = p*Q_Qpx_P,y_P = p_times_P.xy()x_Q,y_Q = p_times_Q.xy()phi_P = -(x_P/y_P)phi_Q = -(x_Q/y_Q)k = phi_Q/phi_Preturn ZZ(k)r = SmartAttack(P, Q, p)
print(r)

    接下来就来看看其他的，

       超奇异椭圆曲线（MOV攻击）

          对于有限域Fq​上的椭圆曲线E,如果Fq​的特性p整除t，那么称这个椭圆曲线为超奇异椭圆曲线。假设这个域为素数域也就是说q为素数，那么他的特性p就是q。

      假设E(Fq​)为n，那么t=q+1−n。也就是说：t=0  (modp)q+1−n=0  (modq)满足这个式子，它就是超奇异椭圆曲线。

sagemath脚本，

    

### MOV攻击脚本    取之https://zhuanlan.zhihu.com/p/421541257
# 初始化椭圆曲线的参数A2, B2, P2x, P2y, Q2x, Q2y以及质数p2
A2 =    			#需要填写     
B2 =      			#需要填写 
P2x =                #需要填写 
P2y =               #需要填写 
Q2x =                 #需要填写 
Q2y =                    #需要填写 p2 =                  #需要填写 k = 2                # 嵌入度，需要填写   嵌入度k是满足k>=2，且阶n整除p^k−1的最小k。 
# 如果n= q+1 的情况下，当k等于2 ，那么p^2 - 1 =(p-1)*(p+1),所以n一定整除p^k-1，所以k一般为2。_P2 = (P2x,P2y)      # 定义点P2的坐标
_Q2 = (Q2x,Q2y)      # 定义点Q2的坐标# Pohlig Hellman算法的注释示例
# d2p = P2p.discrete_log(Q2p) # 离散对数的示例值
# d2p = 64863796476861801236088764479# 定义有限域F1
F1 = GF(p2)
# 在有限域F1上创建椭圆曲线E1
E1 = EllipticCurve(F1, [0, 0, 0, A2, B2])
# 定义扩展有限域F2
F2 = GF(p2^k)
# 创建从F1到F2的同态映射phi
phi = Hom(F1, F2)(F1.gen().minpoly().roots(F2)[0][0])
# 在扩展有限域F2上创建椭圆曲线E2
E2 = EllipticCurve(F2 ,[0, 0, 0, A2, B2])# 计算椭圆曲线E1的阶
n = E1.order()# 定义E1上的点P1和R1
P1 = E1(_P2)
R1 = E1(_Q2)# 将点P1和R1映射到扩展椭圆曲线E2上的点P2和R2
P2 = E2(phi(P1.xy()[0]), phi(P1.xy()[1]))
R2 = E2(phi(R1.xy()[0]), phi(R1.xy()[1]))# 计算系数
cn1 = p2 + 1
coeff = ZZ(cn1 / n)# 在椭圆曲线E2上生成一个随机点Q
Q = coeff * E2.random_point()
# 计算点P2和Q的Weil配对alpha
alpha = P2.weil_pairing(Q, n)
# 计算点R2和Q的Weil配对beta
beta = R2.weil_pairing(Q, n)
# 计算离散对数d
d = beta.log(alpha)# 打印离散对数d
print(d)

这篇关于ECC密码与RSA的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---