学习一下复数域下的RSA
[来源未知]Complex_RSA
import os
import hashlib
from Crypto.Util.number import *
from secret import flag, totient
# where totient is a function used to calculate phi
class Complex:
def __init__(self, re, im):
self.re = re
self.im = im
def __mul__(self, c):
re_ = self.re * c.re - self.im * c.im
im_ = self.re * c.im + self.im * c.re
return Complex(re_, im_)
def show(self):
print([self.re, self.im])
def complex_pow(c, exp, n):
result = Complex(1, 0)
while exp > 0:
if exp & 1:
result = result * c
result.re = result.re % n
result.im = result.im % n
c = c * c
c.re = c.re % n
c.im = c.im % n
exp >>= 1
return result
def pad(msg, length):
pad_length = length - len(msg) - 1
pad_data = os.urandom(pad_length)
return msg + b'\x00' + pad_data
def unpad(msg):
return msg.split(b"\x00")[0]
bits = 512
p = getPrime(bits)
q = getPrime(bits)
n = p * q
sha_flag = hashlib.sha256(flag).digest()
m1 = Complex(
int.from_bytes(sha_flag[:len(sha_flag)//2], "big"),
int.from_bytes(sha_flag[len(sha_flag)//2:], "big"),
)
m2 = Complex(
int.from_bytes(pad(flag[:len(flag)//2], bits//4-1), "big"),
int.from_bytes(pad(flag[len(flag)//2:], bits//4-1), "big"),
)
phi = totient(p, q)
e = q * inverse(p, phi)
c1 = complex_pow(m1, e, n)
c2 = complex_pow(m2, e, n)
c1.show()
c2.show()
print(f'n = {n}')
"""
[90554536599623574119664951128649936419332926063696768860765928746438458550068553748440108394673303800443215316190882880737918820592384729010491685487061658710808286341751196450604089438847354206384322610922839055308138101241906861635339635907663440043442187064090630207952625897567214431195621589834131462698, 9144096375153318849308858335764188418198064372272913164911615933938183103747900881824918069830188301084043148828961577193063557255905230182831945580084452509300200269659063051152684191139872067872645370760797859584822240361290678189844670289832298393156571913616456958845361092243648857334156534377833472900]
[62925714576233017213228404230949787334346543378320798964656732359587152905032848271156799538355748406136742979043729040728123730886381468564779041856310262770766050213464073568850702827835472680885186487027698395099598698463717279017013124488699475168052581476224742146967412904416266652605031934025266540003, 62818668456104375760667670741457826560706388018921820295286033114468271151921637926389738844622672202424650967678199715932465104135980734708459543588178208672956785650944371545080965650112025782049517299538052360417245732776384089052839997333049599655001615752078742624898059780909287845495731050387891926520]
n = 94040393367054633265453751757391098049234338193258976478647369399924701067077628840760704857546243644552533845934146003988635403227234096447871132283820920489003286967145732739404245319615714787916756200564828237043658350145929927911058782352154997346295194977765305107634012698472977467843980475009837261877
"""
其实复数域和实数域也没太大的区别，只有
这道题我们知道
可以得到
得到
所以
那么可以知道
推出
现在只需要求出来就可以了
通过式子
cooper算出来
然后，得到q之后正常算RSA即可
from Crypto.Util.number import *
class Complex:
def __init__(self, re, im):
self.re = re
self.im = im
def __mul__(self, c):
re_ = self.re * c.re - self.im * c.im
im_ = self.re * c.im + self.im * c.re
return Complex(re_, im_)
def show(self):
print([self.re, self.im])
def getvalue(self):
return self.re, self.im
def complex_pow(c, exp, n):
result = Complex(1, 0)
while exp > 0:
if exp & 1:
result = result * c
result.re = result.re % n
result.im = result.im % n
c = c * c
c.re = c.re % n
c.im = c.im % n
exp >>= 1
return result
c1 = Complex(90554536599623574119664951128649936419332926063696768860765928746438458550068553748440108394673303800443215316190882880737918820592384729010491685487061658710808286341751196450604089438847354206384322610922839055308138101241906861635339635907663440043442187064090630207952625897567214431195621589834131462698, 9144096375153318849308858335764188418198064372272913164911615933938183103747900881824918069830188301084043148828961577193063557255905230182831945580084452509300200269659063051152684191139872067872645370760797859584822240361290678189844670289832298393156571913616456958845361092243648857334156534377833472900)
c2 = Complex(62925714576233017213228404230949787334346543378320798964656732359587152905032848271156799538355748406136742979043729040728123730886381468564779041856310262770766050213464073568850702827835472680885186487027698395099598698463717279017013124488699475168052581476224742146967412904416266652605031934025266540003, 62818668456104375760667670741457826560706388018921820295286033114468271151921637926389738844622672202424650967678199715932465104135980734708459543588178208672956785650944371545080965650112025782049517299538052360417245732776384089052839997333049599655001615752078742624898059780909287845495731050387891926520)
n = 94040393367054633265453751757391098049234338193258976478647369399924701067077628840760704857546243644552533845934146003988635403227234096447871132283820920489003286967145732739404245319615714787916756200564828237043658350145929927911058782352154997346295194977765305107634012698472977467843980475009837261877
#part1 get p,q
m1 = complex_pow(c1, n, n).getvalue()
n = 94040393367054633265453751757391098049234338193258976478647369399924701067077628840760704857546243644552533845934146003988635403227234096447871132283820920489003286967145732739404245319615714787916756200564828237043658350145929927911058782352154997346295194977765305107634012698472977467843980475009837261877
PR.<x> = PolynomialRing(Zmod(n))
f = x-m1[0] #这里可以写成m1[1],下面也改一下就行了
f= f.monic()
res = f.small_roots(X=2^130,beta=0.4,epsilon=0.03)
m1_=int(res[0])
q = GCD(m1[0]-m1_,n)
p = n // q
#part2 get flag
phi = (p^2-1)*(q^2-1)
e = q * inverse(p, phi)
d = inverse(e,phi)
flag = complex_pow(c2, d ,n).getvalue()
print(long_to_bytes(int(flag[0])))
print(long_to_bytes(int(flag[1])))
#flag{3ef6db06-b837-11ed-9825-00155dfcdef9}
[2024 XYCTF] Complex_rsa
题目：
from Crypto.Util.number import *
from secrets import flag
class Complex:
def __init__(self, re, im):
self.re = re
self.im = im
def __mul__(self, c):
re_ = self.re * c.re - self.im * c.im
im_ = self.re * c.im + self.im * c.re
return Complex(re_, im_)
def __str__(self):
if self.im == 0:
return str(self.re)
elif self.re == 0:
if abs(self.im) == 1:
return f"{'-' if self.im < 0 else ''}i"
else:
return f"{self.im}i"
else:
return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"
def complex_pow(c, exp, n):
result = Complex(1, 0)
while exp > 0:
if exp & 1:
result = result * c
result.re = result.re % n
result.im = result.im % n
c = c * c
c.re = c.re % n
c.im = c.im % n
exp >>= 1
return result
m = bytes_to_long(flag)
key = getRandomNBitInteger(m.bit_length())
c = m ^ key
com = Complex(key, c)
p = getPrime(512)
q = getPrime(512)
e = 9
enc = complex_pow(com, e, p * q)
print(enc)
print(Complex(p, q) * Complex(p, q))
# 66350931528185981323649477263900844564494528747802437244889229343520648562164950914433406604580038018765783183569276743239888668912948977370163046257917321742455772852779551569446155827368453262479370103326286297164105599131090881306108546341785251895116423206455175290083968296281375908109039893280371271943 + 65266730684129269806656018828265187384002656633231286337130178390517924611751697965395744944541329793503617856896706439809241745206839328124348693486741656130890593895436661857688522977866438805549144904296596887218275440542852887148071837153436265722614658566275517205322945316112048487893204059562830581004i
# -28814875173103880290298835537218644402443395484370652510062722255203946330565951328874411874019897676900075613671629765922970689802650462822117767927082712245512492082864958877932682404829188622269636302484189627580600076246836248427780151681898051243380477561480415972565859837597822263289141887833338111120 + 235362412848885579543400940934854106052672292040465052424316433330114813432317923674803623227280862945857543620663672974955235166884830751834386990766053503640556408758413592161122945636548462064584183165189050320898315823173824074873376450569212651128285746330837777597290934043912373820690250920839961482862i
题解：
from Crypto.Util.number import *
from gmpy2 import *
e = 9
pq2 = 235362412848885579543400940934854106052672292040465052424316433330114813432317923674803623227280862945857543620663672974955235166884830751834386990766053503640556408758413592161122945636548462064584183165189050320898315823173824074873376450569212651128285746330837777597290934043912373820690250920839961482862
p2_q2 = -28814875173103880290298835537218644402443395484370652510062722255203946330565951328874411874019897676900075613671629765922970689802650462822117767927082712245512492082864958877932682404829188622269636302484189627580600076246836248427780151681898051243380477561480415972565859837597822263289141887833338111120
class Complex:
def __init__(self, re, im):
self.re = re
self.im = im
def __mul__(self, c):
re_ = self.re * c.re - self.im * c.im
im_ = self.re * c.im + self.im * c.re
return Complex(re_, im_)
def __str__(self):
if self.im == 0:
return str(self.re)
elif self.re == 0:
if abs(self.im) == 1:
return f"{'-' if self.im < 0 else ''}i"
else:
return f"{self.im}i"
else:
return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"
def complex_pow(c, exp, n):
result = Complex(1, 0)
while exp > 0:
if exp & 1:
result = result * c
result.re = result.re % n
result.im = result.im % n
c = c * c
c.re = c.re % n
c.im = c.im % n
exp >>= 1
return result
p = 10205509456040823453782883291824829705816298450992336115902525676510986341532486274067943978039013674207011185602314114359146043975207543018267242312660911
q = pq2 // 2 // p
com = Complex(66350931528185981323649477263900844564494528747802437244889229343520648562164950914433406604580038018765783183569276743239888668912948977370163046257917321742455772852779551569446155827368453262479370103326286297164105599131090881306108546341785251895116423206455175290083968296281375908109039893280371271943 , 65266730684129269806656018828265187384002656633231286337130178390517924611751697965395744944541329793503617856896706439809241745206839328124348693486741656130890593895436661857688522977866438805549144904296596887218275440542852887148071837153436265722614658566275517205322945316112048487893204059562830581004)
re = int(complex_pow(com, inverse(3,(p^2-1)//3), p).re)
im = int(complex_pow(com, inverse(3,(p^2-1)//3), p).im)
PR.<a,b> = PolynomialRing(Zmod(p))
f1 = a^3 - 3*a*b^2 - re
f2 = 3*a^2*b - b^3 - im
h = Matrix.determinant(f1.sylvester_matrix(f2, a))
res1 = h.univariate_polynomial().monic().roots()
print(res1)
re = int(complex_pow(com, inverse(3,(q^2-1)//3), q).re)
im = int(complex_pow(com, inverse(3,(q^2-1)//3), q).im)
PR.<a,b> = PolynomialRing(Zmod(q))
f1 = a^3 - 3*a*b^2 - re
f2 = 3*a^2*b - b^3 - im
h = Matrix.determinant(f1.sylvester_matrix(f2, a))
res2 = h.univariate_polynomial().monic().roots()
print(res2)
# from Crypto.Util.number import *
# from sympy.ntheory.modular import crt
# #M = crt(n,c)[0]
# pq2 = 235362412848885579543400940934854106052672292040465052424316433330114813432317923674803623227280862945857543620663672974955235166884830751834386990766053503640556408758413592161122945636548462064584183165189050320898315823173824074873376450569212651128285746330837777597290934043912373820690250920839961482862
# p2_q2 = -28814875173103880290298835537218644402443395484370652510062722255203946330565951328874411874019897676900075613671629765922970689802650462822117767927082712245512492082864958877932682404829188622269636302484189627580600076246836248427780151681898051243380477561480415972565859837597822263289141887833338111120
# p = 10205509456040823453782883291824829705816298450992336115902525676510986341532486274067943978039013674207011185602314114359146043975207543018267242312660911
# q = pq2 // 2 // p
# resp = [(5741279734159523094711430662094390392066954482529914882030709450295074947781529110509321968864008611691202383770840412010325910906148313511187473860891035, 1), (4429927739780647098163182245695850111737474361073472216489514077452142827783532166774438977867801037416377640995299677179237078298139871084989841206362410, 1), (34301982100653260908270384034589202011869607388949017382302148763768565967424996784183031307204025099431160836174025169583054770919358422089927245407466, 1)]
# resq = [(10739940731745824081418381715901342901309159762856543362640396906171107996295925365437945464907432967788383551341616951552057327658847904490010061152434332, 1), (8586549363626610854952590733794044071899545915261216635206863621255915665043556027382073545902963458915586846862230166123268280750109862724278599667847493, 1), (7045447028567292693464036821896048537001778022349939312880599967825498301190014724113928977446846014453607030578761699581827447107524459504793000974080961, 1), (5276901669007862459606429311418416791067007412160397323233728060764482838272522831695179159225558247215591099096136610833622276098301992005638773878483349, 1), (4073305908343434001432234700505703739500538013701467077531217640906529193773037971902079461771703238283853345951042314327641038705737553746426200870882295, 1), (3735799333948544298117875399520421256169239519249120000907464407334065474418981528427034590769440802753611282812668144292181442455716588786153175184716817, 1), (3722039472368511317694313824581779119019195065732852920938680419139949899687211960294412748248774573691326211744547172363931044270883035467641541946900209, 1), (2532203573284115839943680788607708204602770120790189755204953987476111829919496668633934893315585793821873529667573847786200205063152150526940602177115763, 1), (412391777749762922348152402206151838186656562632033608965544858648517072916178764607518361571369361991330463978453617074285039619075164749001716157536065, 1)]
# cp = []
# cq = []
# for i in resp:
# cp.append(i[0])
# for i in resq:
# cq.append(i[0])
# KEY = []
# for i in cp:
# for j in cq:
# n = [p,q]
# c = [i,j]
# key = crt(n,c)[0]
# KEY.append(key)
# resp = [(8001885192071749859699066040025029961395167917875583646644249565155819105797467000967544636712092306411149367493633723366623965498649673837196063800580404, 1), (1662435559780994004386842122204566836802794060667449753807174598739830437128828179292947062605594949711892539092095892832053999186054026591407366803020136, 1), (541188704188079589696975129595232907618336472449302715451101512615336798606191093807452278721326418083969279016584498160468079290503842589663811709060371, 1)]
# resq = [(8503432605028099223082740882529347146997316989367545950492333769305549393260049047195629451308480848275471020811688622917531588079409913760096873405190234, 1), (8366627759634051290333268012004602352405002740363136177900446298441200900164136168489014946546974693508397220434695162939560760156985163750847606373150919, 1), (7838336389145961788946008207588532360344213223957590603935032631402061939530140801549439038388256401440065798242555755132126684810445868962728928464941121, 1), (6857325280540966155209571629622673516628729233046153216919246004917826296064185951208599616644606134509118662339264343895819605897243323286865301166906602, 1), (6192229064658828721072838954681858729975625467636197870361944867014338842334277705562409203724381687673713439770131476110414702628279278489497356226657489, 1), (4121694029664041978927797165221546618939268589175297893513650941901521328887423207726634825943843128912526687991267349501555811582062174969259522939168771, 1), (2475586705176908911054627912314872988570680832853905159940563177513798231691560111739604991279968415146174329518843070479843829399895584496027950700885139, 1), (1217221620337618917243787804704498765774078541871944235501766658464684396657530547334482771121693798142550712746858805371783011221995724541464038836673061, 1), (552125404455481483107055129763683979120974776461988888944465520561196942927622301688292358201469351307145490177725937586378107953031679744096093896423948, 1)]
# cp = []
# cq = []
# for i in resp:
# cp.append(i[0])
# for i in resq:
# cq.append(i[0])
# CC = []
# for i in cp:
# for j in cq:
# n = [p,q]
# c = [i,j]
# cc = crt(n,c)[0]
# CC.append(cc)
# for i in CC:
# for j in KEY:
# if(b"flag" in long_to_bytes(i ^ j)):
# print(long_to_bytes(i ^ j))
# print(len(CC))
#flag{Complex_is_so_fun_and_I_think_you_know_Sylvester!}
[2023-极客大挑战] EzComplex
#sage9.3
from Crypto.Util.number import *
flag = b'FAKE{Do_You_know_Complex_numbers}'
p = random_prime(1 << 384)
q = random_prime(1 << 384)
n = p * q
e = 0x10001
N = pow(p, 2) + pow(q, 2)
m = bytes_to_long(flag)
c = pow(m,e,n)
print(c)
print(N)
'''
122977267154486898127643454001467185956864368276013342450998567212966113302012584153291519651365278888605594000436279106907163024162771486315220072170917153855370362692990814276908399943293854077912175867886513964032241638851526276
973990451943921675425625260267293227445098713194663380695161260771362036776671793195525239267004528550439258233703798932349677698127549891815995206853756301593324349871567926792912475619794804691721625860861059975526781239293017498
'''
这题就分解一下n就行了
from Crypto.Util.number import *
c = 122977267154486898127643454001467185956864368276013342450998567212966113302012584153291519651365278888605594000436279106907163024162771486315220072170917153855370362692990814276908399943293854077912175867886513964032241638851526276
N = 973990451943921675425625260267293227445098713194663380695161260771362036776671793195525239267004528550439258233703798932349677698127549891815995206853756301593324349871567926792912475619794804691721625860861059975526781239293017498
e = 65537
zn = ZZ[i](N)
for d in divisors(zn):
p = int(d[0])
q = int(d[1])
if isPrime(p) and isPrime(q) and p.bit_length() > 380:
break
phi = (p-1)*(q-1)
n = p*q
d = inverse(e,phi)
print(long_to_bytes(int(pow(c,d,n))))
#SYC{D0_you_like_r41n?_i_pref3r_R1_ng}