第一次做椭圆曲线的题目。
from Crypto.Util.number import getStrongPrime, bytes_to_long, long_to_bytes
from hashlib import sha256
flag = open("flag.txt","r").read().strip()
assert flag[:5] == "flag{"
assert flag[-1] == '}'
flag = flag[5:-1]
p = getStrongPrime(512)
q = getStrongPrime(512)
R = Zmod(p*q)
Mx = R.random_element()
My = R.random_element()
b = My^2-Mx^3
E = EllipticCurve(R, [0,b])
Ep = EllipticCurve(GF(p), [0,b])
Eq = EllipticCurve(GF(q), [0,b])
Ecard = Ep.cardinality()*Eq.cardinality()
s = 65537
iqmp = inverse_mod(q,p)
ipmq = inverse_mod(p,q)
print(s,b)
print(s*E(Mx,My))
print(bytes_to_long(sha256(long_to_bytes(Mx)).digest())^^bytes_to_long(flag))
print(Ecard,iqmp,ipmq)
# output
(65537, 94962786219973877605671132537403567692440509416563276506616937465179543052924213419303316878950508729240534157716515828692415753760423373275798742901898988091711366167453291093198455208486860434821584730289796756303755481427944050694278973935430950200226296421295480931709196450582971294555698582300017079681)
(59689554847874056093522894557358652275419512622217938321967925712006032474501517821545301024523968683202653811170349935486275898044517137549261264554824555797167281774084610432672417104059882911623049068014057766046112405707488652409101966085668874020827374430371692420243675165526553501764397026287669226197 : 107033494829289229556075885979462361899987322825365541933972703943968531588265195269186863548962298698045245724642422677734531754208372003685975037164535540426445912448882320720472359490662223819700396239242421138100987404819402823347620606193192681437735774631528857883666813248099478194217107430655559387177 : 1)
8473244269440509775740824389306887881298058795843414842956132145490099061637
(121129302483457450895608650552243558445281823578945131606244911986357957846615219093944273522931121330892846906255621900353518764908058240190274164398929651054604172934407880109536968954842096749981787715589575379360708665738113909945093611320464753611894436549704087447277644447804224219449061523879184664224, 3433993182244742933171077355577942754401256613289749464940723455338441506020894108372280289090874388382515726802296885002734697572085019743996840692246280, 7185352839224592554378149243106036192572722976910322898221597172526458478345990407760099409610815351585677931127109742103079498785227488769888006188378352)发现是个椭圆曲线的题目，开始大致看了下椭圆曲线的知识。
然后发现一个类似的题目RCTF 2020 - infantECC，应该是根据这个题目改的。biu~传送
但是和那个题还有点不一样。总体的思路应该是一致,要先求出p,q然后再去解接下来的东西,逆一下加密过程。
相比原题，这个题会有一些小的改变，导致了求pq的会有些不太一样。但是总体的思路和后面的求解过程有很多地方可以借鉴（主要是我不太了解椭圆曲线，后面会去补代数数论），这样可以省下很多时间，只要跟着魔改就好了。
接下来看下差异点。发现前面都一致，一直到最后给出的q,p的条件不太一致。
首先，此题中新出现了两个条件
iqmp = inverse_mod(q,p)
ipmq = inverse_mod(p,q)
print(Ecard,iqmp,ipmq)
这个给人第一感觉就有点暧昧，感觉是能够联立获得一些信息，所以拿出纸笔开始推导。
但是发现有些东西是不好消除的（基本功不够扎实）,所以还是査下资料。
然后发现了一篇博客,简直完美。他在其中，有基本和我们一致的条件和想要推导出p,q，只是的最后联立方程组时用到的时rsa的特性，我们替换成椭圆曲线中的相关特性应该就能推导出p,q。
拿另一篇2020 RCTF WP中的推导出的1，2个小结论,进行联立。
s.add(iqmp*q+ipmq*p==n+1)
s.add(Ecard==(p+1)*(q+1))
s.add(n==(q*p))这样可以求出p,q,n。
接下来应该就是逆着加密的思路去进行解密。
由于对椭圆曲线不太熟悉。为了减少错误的可能，还是参照原题的wp的后半部分的解题。
我们关注到这里
EE=EllipticCurve(Zmod(N),[0,Cy^2-Cx^3])
dd=inverse_mod(e,(pp+1)*(qq+1))
M=dd*EE(Cx,Cy)
print(long_to_bytes((bytes_to_long(sha256(long_to_bytes(M[0])).digest())<<256^^secret^^dd)>>256))我们的题目和原题基本一致。
R = Zmod(p*q)
E = EllipticCurve(R, [0,b])
dd = inverse_mod(s,(p+1)*(q+1))
M=dd*E(Cx,Cy)
#print(M)
print(long_to_bytes(bytes_to_long(sha256(long_to_bytes(M[0])).digest())^^(flag_xx)))上面所有的变量都已知。
可以解出FLAG。
又是想念天师，后悔没有上好信息安全数学，数论的一天。
后半部分的M的求解，其实原理上还没有很好的理解。只是按照原来的wp类推的。具体原理待补充。