拖了好久了
easySign
from secret import r, t
from Crypto.Util.number import *
flag = b'xxx'
flag = bytes_to_long(flag)
e = 0x10001
def gen_keys():
p = getPrime(1024)
q = getPrime(1024)
phi = (p-1)*(q-1)
d = inverse(e,phi)
n = p*q
print(f'n = {n}')
WHATF = (d ** 3 + 3) % phi
print(f'WHATF= {WHATF}')
return d, n, WHATF
def easy_sign(n,d):
m = flag * pow(r,e**2+d**2,n) % n
s = pow(m,d,n)
return s
def gift():
assert t > 0
gift = pow(r,t) - 1
#print(t)
print(isPrime(gift))
d,n,WHATF = gen_keys()
gift()
sign = easy_sign(n,d)
print(f'sign = {sign}')
# n = 17501785470905115084530641937586010443633001681612179692218171935474388105810758340844015368385708349722992595891293984847291588862799310921139505076364559140770828784719022502905431468825797666445114531707625227170492272392144861677408547696040355055483067831733807927267488677560035243230884564063878855983123740667214237638766779250729115967995715398679183680360515620300448887396447013941026492557540060990171678742387611013736894406804530109193638867704765955683067309269778890269186100476308998155078252336943147988308936856121869803970807195714727873626949774272831321358988667427984601788595656519292763705699
# WHATF= 7550872408895903340469549867088737779221735042983487867888690747510707575208917229455135563614675077641314504029666714424242441219246566431788414277587183624484845351111624500646035107614221756706581150918776828118482092241867365644233950852801286481603893259029733993572417125002284605243126366683373762688802313288572798197775563793405251353957529601737375987762230223965539018597115373258092875512799931693493522478726661976059512568029782074142871019609980899851702029278565972205831732184397965899892253392769838212803823816067145737697311648549879049613081017925387808738647333178075446683195899683981412014732
# 1
# sign = 12029865785359077271888851642408932941748698222400692402967271078485911077035193062225857653592806498565936667868784327397659271889359852555292426797695393591842279629975530499882434299824406229989496470187187565025826834367095435441393901750671657454855301104151016192695436071059013094114929109806658331209302942624722867961155156665675500638029626815869590842939369327466155186891537025880396861428410389552502395963071259114101340089657190695306100646728391832337848064478382298002033457224425654731106858054291015385823564302151351406917158392454536296555530524352049490745470215338669859669599380477470525863815
分析可得下面的关系：
- $WHATF = (d^3 + 3) \space mod \space phi$
- $m = (flag*r^{e^2+d^2}) \space mod \space n$
- $sign = m^d \space mod \space n$
根据关系式2，两边加上d次方：
$m^d = (flag^d*r^{e(ed)}*r^{d^3}) \space mod \space n$
用欧拉定理进行化简：
$m^d = (flag^d)r^er^{WHATF-3} \space mod \space n$
据此可以求出$flag^d$，再带上e次方并再次利用欧拉定理即为flag。
r还未分析：
def gift():
assert t > 0
gift = pow(r,t) - 1
#print(t)
print(isPrime(gift))
$r^t-1$是素数，分情况讨论：
当$t==1$，则$r=一个素数+1$，那么r有无限中情况；
当$t!=1$，$r^t-1可分解为*r^t−1=(r−1)(r^{t−1}+r^{t−2}+⋯+r+1)$，这个数想要为素数，那么$r-1$肯定等于$1$，即$r==2$。
r解出来了，开始敲代码：
e = 0x10001
n = ...
WHATF= ...
sign = ...
r = 2
flagd = sign * inverse(pow(r,e+WHATF-3,n),n)
flag = pow(flagd,e,n)
print(long_to_bytes(flag))
#b'DASCTF{RSA_Bl1nd_Signatur3_With_M4th}'
ECC
from Crypto.Util.number import *
from secret import flag, p, q, a, b, e1, e2, e3
assert isPrime(p) and isPrime(q)
assert flag.startswith("DASCTF{") and flag.endswith("}")
class ECC():
def __init__(self, a, b, p, q, e):
self.p, self.q = p, q
self.a, self.b = a, b
self.N = p * q
self.e = e
self.Kbits = 8
self.Ep = EllipticCurve(IntegerModRing(p), [a, b])
self.Eq = EllipticCurve(IntegerModRing(q), [a, b])
N1 = self.Ep.order()
N2 = 2 * p + 2 - N1
N3 = self.Eq.order()
N4 = 2 * q + 2 - N3
self.d = {
( 1, 1): inverse_mod(e, lcm(N1, N3)),
( 1, -1): inverse_mod(e, lcm(N1, N4)),
(-1, 1): inverse_mod(e, lcm(N2, N3)),
(-1, -1): inverse_mod(e, lcm(N2, N4))
}
self.E = EllipticCurve(IntegerModRing(self.N), [a, b])
def enc(self, plaintext):
msg_point = self.msg_to_point(plaintext, True)
mp = self.Ep(msg_point)
mq = self.Eq(msg_point)
cp = (self.e * mp).xy()
cq = (self.e * mq).xy()
cp = (int(cp[0]), int(cp[1]))
cq = (int(cq[0]), int(cq[1]))
c = (int(crt([cp[0], cq[0]], [self.p, self.q])), \
int(crt([cp[1], cq[1]], [self.p, self.q])))
c = self.E(c)
return c.xy()
def dec(self, ciphertext):
x = ciphertext
w = x^3 + self.a*x + self.b % self.N
P.<Yp> = PolynomialRing(Zmod(self.p))
fp = x^3 + self.a*x + self.b -Yp^2
yp = fp.roots()[0][0]
P.<Yq> = PolynomialRing(Zmod(self.q))
fq = x^3 + self.a*x + self.b -Yq^2
yq = fq.roots()[0][0]
y = crt([int(yp), int(yq)], [self.p, self.q])
cp, cq = self.Ep((x, y)), self.Eq((x, y))
legendre_symbol_p = legendre_symbol(w, self.p)
legendre_symbol_q = legendre_symbol(w, self.q)
mp = (self.d[(legendre_symbol_p, legendre_symbol_q)] * cp).xy()
mq = (self.d[(legendre_symbol_p, legendre_symbol_q)] * cq).xy()
return crt([int(mp[0]), int(mq[0])], [self.p, self.q]) >> self.Kbits
def msg_to_point(self, x, shift=False):
if shift:
x <<= self.Kbits
res_point = None
for _ in range(2 << self.Kbits):
P.<Yp> = PolynomialRing(Zmod(self.p))
fp = x^3 + self.a*x + self.b - Yp^2
P.<Yq> = PolynomialRing(Zmod(self.q))
fq = x^3 + self.a*x + self.b - Yq^2
try:
yp, yq = int(fp.roots()[0][0]), int(fq.roots()[0][0])
y = crt([yp, yq], [self.p, self.q])
E = EllipticCurve(IntegerModRing(self.p*self.q), [self.a, self.b])
res_point = E.point((x, y))
return res_point
except:
x += 1
return res_point
ecc1 = ECC(a, b, p, q, e1)
ecc2 = ECC(a, b, p, q, e2)
ecc3 = ECC(a, b ,p, q, e3)
gift = p * q * getPrime(1000)
secret = bytes_to_long(flag[7:-1].encode())
ciphertext1 = ecc1.enc(secret)
ciphertext2 = ecc2.enc(secret)
ciphertext3 = ecc3.enc(secret)
with open("output.txt", "w") as f:
f.write(f"e1 = {e1}\n")
f.write(f"e2 = {e2}\n")
f.write(f"e3 = {e3}\n")
f.write(f"gift = {gift}\n")
f.write(f"C1 = {ciphertext1}\n")
f.write(f"C2 = {ciphertext2}\n")
f.write(f"C3 = {ciphertext3}\n")
定义了三个椭圆曲线，a、b、n都没给，所以先想办法求a、b。
引入Gröbner基理论工具。知识有限，大致了解就是，可用于计算多项式环中的基础元素，即解一般的多项式方程组，包括非线性方程组和多项式不定方程。对于大型或高阶方程组，可能得不到结果。且目标多项式方程组需要满足一些条件。其中最重要的条件是方程组必须是一个“零维”方程组，也就是说，它必须有有限个解。
从题中我们可以列出多项式方程组来：
$f1 = C1[0]^3 + aC1[0] + b - C1[1]^2$
$f2 = C2[0]^3 + aC2[0] + b - C2[1]^2$
$f3 = C3[0]^3 + aC3[0] + b - C3[1]^2$
gift = ...
P.<a,b>=PolynomialRing(Zmod(gift))
C1 = (..., ...)
C2 = (..., ...)
C3 = (...,...)
f1 = C1[0]^3 + a*C1[0] + b - C1[1]^2
f2 = C2[0]^3 + a*C2[0] + b - C2[1]^2
f3 = C3[0]^3 + a*C3[0] + b - C3[1]^2
F = [f1,f2,f3]
Ideal = Ideal(F)
I = Ideal.groebner_basis()
print(I)
#[a + 6383454939215515141151308275756464378147341998868124849701666287931118728967033226489555343116783930020043447064021757870443190275344745221658277278096846919402186283335931329880274804317278840879511880105400148227288592654329031719888755699046101784104099741865444662504240509089508615358820602230534486420527588876985837918460253592556268354478308719338006099829036747790521589851108766488409474143802894481467371124474, b + 2061828487946313274444567336921027851992389239431896215882831043443098187273467324250117099919991128038110286667574268827149737102849843003427760947370452301720570966798422301991069233423052047573723017573811854447144591388611545295336479676711135093748524215062079916506134402329979650885359052525127585725226235274380415403877926132099800327766309604816799309017969361197829094471646886280677088152723532310326801778432, 1858284081017011776897142483530706248351014197676168270132930318711536519639284920939350511528325590655669305434894548271]
注意这里的结果，为三个一次多项式组，即：
a + 6383454939215515141151308275756464378147341998868124849701666287931118728967033226489555343116783930020043447064021757870443190275344745221658277278096846919402186283335931329880274804317278840879511880105400148227288592654329031719888755699046101784104099741865444662504240509089508615358820602230534486420527588876985837918460253592556268354478308719338006099829036747790521589851108766488409474143802894481467371124474 = 0
b + 2061828487946313274444567336921027851992389239431896215882831043443098187273467324250117099919991128038110286667574268827149737102849843003427760947370452301720570966798422301991069233423052047573723017573811854447144591388611545295336479676711135093748524215062079916506134402329979650885359052525127585725226235274380415403877926132099800327766309604816799309017969361197829094471646886280677088152723532310326801778432 = 0
1858284081017011776897142483530706248351014197676168270132930318711536519639284920939350511528325590655669305434894548271
故a、b相应取相反数，第三个数为n的值。
a、b、n求出来了，构造曲线：$E=EllipticCurve(Zmod(n),[a,b])$
再来看加密函数，有$c = e*m$，这个数乘运算是在ECC上点的运算。现有同一个m用三组不同e加密得到的c，这可以类比rsa的共模攻击，第一次在ECC与RSA结合中遇到共模攻击，很有必要作下对比，先看常规共模的解题方式：
s = gcdext(e1,e2)#扩展欧几里得算法，得到x，y，即ax+by=gcd(a,b)
m1 = pow(c1,s[1],n1)
m2 = pow(c2,s[2],n1)
m = (m1 * m2) % n1
print(long_to_bytes(m))
#运用的前提的是gcd(e1,e2) == 1
而在此题中，有$gcd(e1,e3) == 1$，故计算$gcdext(e1,e3)$
E1=E(C1[0],C1[1])
E3=E(C3[0],C1[1])
#这里是计算椭圆曲线上的点，用于计算
s = gcdext(e1,e3)
m1 = s[1]*E1
m3 = s[2]*E3
m = m1 + m3
print(m)
#(568187760467717269610985553206613709901686770919725280411069329483654912 : 902383579564357536192281359415338858998812047575951055596174651153047572493238086026951049981445179941533576636231499174 : 1)
print(long_to_bytes(568187760467717269610985553206613709901686770919725280411069329483654912))
#b'RSA_0n_ECC_1s_mor3_Ineres7ing\x00'
主要区分点：
$m1 = s[1]*E1$
$m3 = s[2]*E3$
$m = m1 + m3$
这得根据加密所用的公式而定。
其余两题暂时放着？😅
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com