whi

基础知识

环的基本定义

一个环 ( R ) 是一个集合，并且上面定义了两种运算，分别是加法和乘法，且满足以下条件：

1. 加法封闭性：对于集合中的任意两个元素 ( a ) 和 ( b )，它们的和 ( a + b ) 也在这个集合中。
2. 加法结合律：对于任意的 ( a, b, c \in R )，有 ( (a + b) + c = a + (b + c) )。
3. 加法单位元存在：存在一个元素 ( 0 \in R )，使得对于任何 ( a \in R )，都有 ( a + 0 = a )。
4. 加法逆元存在：对于每个 ( a \in R )，存在一个元素 ( -a \in R )，使得 ( a + (-a) = 0 )。
5. 乘法封闭性：对于集合中的任意两个元素 ( a ) 和 ( b )，它们的积 ( a \times b ) 也在这个集合中。
6. 乘法结合律：对于任意的 ( a, b, c \in R )，有 ( (a \times b) \times c = a \times (b \times c) )。
7. 分配律：乘法对加法分配，即对所有 ( a, b, c \in R ) 都有：
   • ( a \times (b + c) = a \times b + a \times c )
   • ( (a + b) \times c = a \times c + b \times c )

多项式环

多项式环 是指多项式组成的环。形式上，假设我们有一个环 ( R )，那么多项式环 ( R[x] ) 就是由变量 ( x ) 和系数来自环 ( R ) 组成的所有多项式的集合。

具体来说，一个多项式是形如：
[
f(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0
]
其中，( a_i \in R )（系数来自环 ( R )），而 ( x ) 是变量，( n ) 是多项式的次数。

题目

from Crypto.Util.number import *
from gmpy2 import *
from random import *
from secrets import flag
 
assert len(flag)==42
p=getPrime(600)
a=bytes_to_long(flag)
b=randrange(2,p-1)
E=EllipticCurve(GF(p),[a,b]) #定义在a,b上模p的椭圆曲线
G=E.random_element()
 
x1,y1,_=G
G=2*G 
x2,y2,_=G
 
print(f"p = {p}")
print(f"b = {b}")
print(f"x1 = {x1}")
print(f"x2 = {x2}")
'''
p = 3660057339895840489386133099442699911046732928957592389841707990239494988668972633881890332850396642253648817739844121432749159024098337289268574006090698602263783482687565322890623
b = 1515231655397326550194746635613443276271228200149130229724363232017068662367771757907474495021697632810542820366098372870766155947779533427141016826904160784021630942035315049381147
x1 = 2157670468952062330453195482606118809236127827872293893648601570707609637499023981195730090033076249237356704253400517059411180554022652893726903447990650895219926989469443306189740
x2 = 1991876990606943816638852425122739062927245775025232944491452039354255349384430261036766896859410449488871048192397922549895939187691682643754284061389348874990018070631239671589727
'''

了解ecc加密方式，题目里的x2,y2是2G，是加密后的x3 y3
$P = Q 则k=\frac{3x_1^2+a}{2y_1}(mod\,p)$
代入
$y_1^2\equiv x_1^3+a*x+b(mod\,p)$
$ x_3\equiv k^2-x_1-x_2(mod,p)\rightarrow x_2= k^2-2x_1$$y_3\equiv k(x_1-x_3)-y_1(mod,p)$$k^2\equiv (\frac{3x_1^2+a}{2y_1})2(mod,p)$$y_1^2\equiv (\frac{3x_1^2+a}{2k})2(mod,p)$$(3x_1+a)^2\equiv 4k^2*(x_13+ax+b)(mod,p)$
然后设a解一个方程

exp

from Crypto.Util.number import *

p = 3660057339895840489386133099442699911046732928957592389841707990239494988668972633881890332850396642253648817739844121432749159024098337289268574006090698602263783482687565322890623
b = 1515231655397326550194746635613443276271228200149130229724363232017068662367771757907474495021697632810542820366098372870766155947779533427141016826904160784021630942035315049381147
x1 = 2157670468952062330453195482606118809236127827872293893648601570707609637499023981195730090033076249237356704253400517059411180554022652893726903447990650895219926989469443306189740
x2 = 1991876990606943816638852425122739062927245775025232944491452039354255349384430261036766896859410449488871048192397922549895939187691682643754284061389348874990018070631239671589727
k_2 = x2 + 2*x1
R.<a> = PolynomialRing(Zmod(p), implementation='NTL')#最好以后这么写
f = 4*k_2*(x1^3+a*x1+b)-(3*x1^2+a)^2
f = f.monic()
x=f.roots()
for each in x:
    m = int(each[0])
    print(long_to_bytes(m))

b’8\xb0e\xd9[\x1c\xe9\x123\xed\xc8\x89_f\xcc\xd7}$\xe3\x04\xd3\x1fx6P\xdc\t\xa9\xb5@8\xf5\x87Q\xb28\xd9T\x1c\xa2[7\xd6\xe0\xe9Y\xa7\xf0\x8dr\x02\x98t\x85\xa2\xac\x0c<\xcf\xa2\xf4k\xab\x8ca\x96\x93\x11V\x81\x93\xd3\xca’
b’flag{fa76cfb1-0052-4416-914d-91517bcebd52}