import math
_1_50 = 1 << 50 # 2**50 == 1,125,899,906,842,624
def isqrt(x):
"""Return the integer part of the square root of x, even for very
large integer values."""
if x < 0:
raise ValueError('square root not defined for negative numbers')
if x < _1_50:
return int(math.sqrt(x)) # use math's sqrt() for small parameters
n = int(x)
if n <= 1:
return n # handle sqrt(0)==0, sqrt(1)==1
# Make a high initial estimate of the result (a little lower is slower!!!)
r = 1 << ((n.bit_length() + 1) >> 1)
while True:
newr = (r + n // r) >> 1 # next estimate by Newton-Raphson
if newr >= r:
return r
r = newrfrom Crypto.Util.number import *
f = open("chall.enc", "rb")
ans = bytes_to_long(f.read())
print(ans)from sage.all import Integer
from sage.all import continued_fraction
#from factorization import known_phi
n = 17729028558979019485846420034614601781855286885772116033115998289130663218793249135103097941406615594783564487056148202535602218241261076180277862184340050681277512936764254998557657989633659561175844653871375735119626199870178796372816549333367076487655787617921785826120525919291798195591267544750350222858119219959311035913906885739352404726672836723117136379411134589884489391116922923390687958161705756705708668649262568471831705504852664779788943978721769038284989250803324876493071615384204553854811020877754034576798208169454695001947778015807032019651748938505463608871771494765303144219873993106068807291321
e = 65537
def attack(n, e):
"""
Recovers the prime factors of a modulus and the private exponent if the private exponent is too small.
:param n: the modulus
:param e: the public exponent
:return: a tuple containing the prime factors of the modulus and the private exponent, or None if the private exponent was not found
"""
convergents = continued_fraction(Integer(e) / Integer(n)).convergents()
for c in convergents:
k = c.numerator()
d = c.denominator()
if k == 0 or (e * d - 1) % k != 0:
continue
print("d",d)
attack(n,e)Note: Run on linux
from Crypto.Publickey import RSA
f = open('public.pem','r')
key = RSA.importKey(f.read())
print("n: ",key.n)
print("e: ",key.e)It applied for public key (pem) and private key (pem)
Statement: Find flag when know:
Given:
c = 0x217c8bf9b45601267624c3b1ba89ae93d04c8fae32dc15496262f36f48d06c0dc9e178a77b77a33708dcbe1fcd55ea9eb636fe5684c2f0f08df3389f47b36a128636671eba300491c829ed1e252b1bb4dbb3b93bc46d98a10bb5d55347752052ab45e143fd46799be1d06ac3ff7e8b1eb181dfbba8dfac3910202fd0b9a25befe
E = 266524484526673326121255015126836087453426858655909092116029065652649301962338744664679734617977550306567819672969837450223062478394149960243362563995235387971047857994699247277712682103161537347874310994510059329875060868679654080020041070975648626636209785889112656335054840517934593236597457100751820027783
N = 412460203584740978970185080155274765823237615982150661072746604041385717906706098256415230390148737678989448404730885157667896599397615737297545930957425615121654272472589331747646564634264520011009284080299605233265170506809736069720838542498970453928922703911186788239628906189362646418960560442406497717567
Solution:
Find d using Weiner-Attack
Code:
from sage.all import Integer
from sage.all import continued_fraction
#from factorization import known_phi
n = 412460203584740978970185080155274765823237615982150661072746604041385717906706098256415230390148737678989448404730885157667896599397615737297545930957425615121654272472589331747646564634264520011009284080299605233265170506809736069720838542498970453928922703911186788239628906189362646418960560442406497717567
e = 266524484526673326121255015126836087453426858655909092116029065652649301962338744664679734617977550306567819672969837450223062478394149960243362563995235387971047857994699247277712682103161537347874310994510059329875060868679654080020041070975648626636209785889112656335054840517934593236597457100751820027783
def attack(n, e):
"""
Recovers the prime factors of a modulus and the private exponent if the private exponent is too small.
:param n: the modulus
:param e: the public exponent
:return: a tuple containing the prime factors of the modulus and the private exponent, or None if the private exponent was not found
"""
convergents = continued_fraction(Integer(e) / Integer(n)).convergents()
for c in convergents:
k = c.numerator()
d = c.denominator()
if k == 0 or (e * d - 1) % k != 0:
continue
print("d",d)
attack(n,e)Result:
d = 1
d = 2
d = 3
d = 27979163639208238097581493168255260980791785886427784936313524512033423912647
With every d we find, try find flag:
Code:
from Crypto.Util.number import *
c_hex = "0x217c8bf9b45601267624c3b1ba89ae93d04c8fae32dc15496262f36f48d06c0dc9e178a77b77a33708dcbe1fcd55ea9eb636fe5684c2f0f08df3389f47b36a128636671eba300491c829ed1e252b1bb4dbb3b93bc46d98a10bb5d55347752052ab45e143fd46799be1d06ac3ff7e8b1eb181dfbba8dfac3910202fd0b9a25befe"
c = int(c_hex,16)
e = 266524484526673326121255015126836087453426858655909092116029065652649301962338744664679734617977550306567819672969837450223062478394149960243362563995235387971047857994699247277712682103161537347874310994510059329875060868679654080020041070975648626636209785889112656335054840517934593236597457100751820027783
n = 412460203584740978970185080155274765823237615982150661072746604041385717906706098256415230390148737678989448404730885157667896599397615737297545930957425615121654272472589331747646564634264520011009284080299605233265170506809736069720838542498970453928922703911186788239628906189362646418960560442406497717567
d = 27979163639208238097581493168255260980791785886427784936313524512033423912647
flag = long_to_bytes(pow(c,d,n))
print(flag)Result:
b'Bugs_Bunny{Baby_Its_Cool_Lik3_school_haHAha}'
Note: Using flag.decode() the flag will be: Bugs_Bunny{Baby_Its_Cool_Lik3_school_haHAha}
Given:
c = 24069342720029447645279421073270575353047711895242659815039311355734342330508297195320032629315218226212387151445283779967345116103626286184366740272344305727987474407741946014932936418366083000851440285481560035222386750756966859
e = 65537
n= 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
Find flag using RsaCtfTool
Solve:
-
Download in here
-
Using Kali to solve:
python3 RsaCtfTool.py -n 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413 -e 65537 --uncipher 24069342720029447645279421073270575353047711895242659815039311355734342330508297195320032629315218226212387151445283779967345116103626286184366740272344305727987474407741946014932936418366083000851440285481560035222386750756966859
Flag: tpctf{omg_b1c_m0dulus}
Given:
n = 744818955050534464823866087257532356968231824820271085207879949998948199709147121321290553099733152323288251591199926821010868081248668951049658913424473469563234265317502534369961636698778949885321284313747952124526309774208636874553139856631170172521493735303157992414728027248540362231668996541750186125327789044965306612074232604373780686285181122911537441192943073310204209086616936360770367059427862743272542535703406418700365566693954029683680217414854103
e = 57595780582988797422250554495450258341283036312290233089677435648298040662780680840440367886540630330262961400339569961467848933132138886193931053170732881768402173651699826215256813839287157821765771634896183026173084615451076310999329120859080878365701402596570941770905755711526708704996817430012923885310126572767854017353205940605301573014555030099067727738540219598443066483590687404131524809345134371422575152698769519371943813733026109708642159828957941
c = 305357304207903396563769252433798942116307601421155386799392591523875547772911646596463903009990423488430360340024642675941752455429625701977714941340413671092668556558724798890298527900305625979817567613711275466463556061436226589272364057532769439646178423063839292884115912035826709340674104581566501467826782079168130132642114128193813051474106526430253192254354664739229317787919578462780984845602892238745777946945435746719940312122109575086522598667077632
You can download tool in here
So we get:
d = 108642162821084938181507878056324903120999504739411128372202198922197750954973
Now, flag is:
flag = pow(c,d,n)
Result is:
Flag: d4rk{r3p34t3ed_RsA_1s_f0r_n00bs}
Given:
- ciphertext (base64): PePAW8C9Lm7yxsyA2MShozuHpDrRZJssZECWAYULMEMq7pfcX4cUyKpWvW8ZVQis+KtxT7pa1LEcq4UvYW8Gm44nTUwPOOzqw86MXonJ8Mwgx9gXlZHNReG/X2+bynejQo36b1axIt9RujXCxXzEsOzO/gpSVE24bgvwwvU+C28=
- public key :
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCO5+gAGMWkPvEtXWLRaqxSm3PeNtMMDfbGQs15Gms7trqxGnK+pjZslc4oVyw6cu5RHrt4YpfGY1VeXG8ZeIiY5BagA7eMP8Rv5ixblyhA51MMDNd/+gNcDZH4MvtM1KsDYYeeD9SXKrBI10znG7nxV4fAB39Y4PW8UzMv8GFVEQIDAQAB
Using this website and choose mode public key
Result is:
Flag:
Flag: SBCTF{53cu23_data_724n5m15510n}
Given:
- file
bob.pub
-----BEGIN PUBLIC KEY-----
MDgwDQYJKoZIhvcNAQEBBQADJwAwJAIdDVZLl4+dIzUElY7ti3RDcyge0UGLKfHs
+oCT2M8CAwEAAQ==
-----END PUBLIC KEY-----
- file
bob2.pub
-----BEGIN PUBLIC KEY-----
MDgwDQYJKoZIhvcNAQEBBQADJwAwJAIdCiM3Dn0PsAIyFkrG1kKED8VOkgJDP5J6
YOta29kCAwEAAQ==
-----END PUBLIC KEY-----
- file
bob3.pub
-----BEGIN PUBLIC KEY-----
MDgwDQYJKoZIhvcNAQEBBQADJwAwJAIdDFtp4ZeeVB+F2s3iqhTSciqEb0Gz24Pm
Z+Oz0R0CAwEAAQ==
-----END PUBLIC KEY-----
- file
secret.enc
DK9dt2MTybMqRz/N2RUMq2qauvqFIOnQ89mLjXY=
AK/WPYsK5ECFsupuW98bCFKYUApgrQ6LTcm3KxY=
CiLSeTUCCKkyNf8NVnifGKKS2FJ7VnWKnEdygXY=
Solution:
Using:
from Crypto.PublicKey import RSA
f = open('bob.pub', 'r')
pubkey = RSA.import_key(f.read())
print("n = ", pubkey.n)
print("e = ", pubkey.e)
And use this link to factorizer a number
Part 1:
n = 359567260516027240236814314071842368703501656647819140843316303878351
e = 65537
p = 17963604736595708916714953362445519
q = 20016431322579245244930631426505729
phi_n = (p-1)*(q-1)
d = inverse(e,phi_n)
c_base64 = DK9dt2MTybMqRz/N2RUMq2qauvqFIOnQ89mLjXY=
Part 2:
n = 273308045849724059815624389388987562744527435578575831038939266472921
e = 65537
p = 16514150337068782027309734859141427
q = 16549930833331357120312254608496323
phi_n = (p-1)*(q-1)
d = inverse(e,phi_n)
c_base64 = CiLSeTUCCKkyNf8NVnifGKKS2FJ7VnWKnEdygXY=
Part 3:
n = 333146335555060589623326457744716213139646991731493272747695074955549
e = 65537
p = 17357677172158834256725194757225793
q = 19193025210159847056853811703017693
phi_n = (p-1)*(q-1)
d = inverse(e,phi_n)
c_base64 = AK/WPYsK5ECFsupuW98bCFKYUApgrQ6LTcm3KxY=
Solution:
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
from base64 import b64decode
# First process
# f = open('bob3.pub', 'r')
# pubkey = RSA.import_key(f.read())
# print("n = ", pubkey.n)
# print("e = ", pubkey.e)
# Second process
## Part 1
# n = 359567260516027240236814314071842368703501656647819140843316303878351
# e = 65537
# p = 17963604736595708916714953362445519
# q = 20016431322579245244930631426505729
# phi_n = (p-1)*(q-1)
# d = inverse(e,phi_n)
# c_base64 = "DK9dt2MTybMqRz/N2RUMq2qauvqFIOnQ89mLjXY="
# c = bytes_to_long(b64decode(c_base64))
# flag = long_to_bytes(pow(c,d,n))
# print(flag)
# Ans 1: IW{WEAK_R
## Part 2
# n = 273308045849724059815624389388987562744527435578575831038939266472921
# e = 65537
# p = 16514150337068782027309734859141427
# q = 16549930833331357120312254608496323
# phi_n = (p-1)*(q-1)
# d = inverse(e,phi_n)
# c_base64 = "CiLSeTUCCKkyNf8NVnifGKKS2FJ7VnWKnEdygXY="
# c = bytes_to_long(b64decode(c_base64))
# flag = long_to_bytes(pow(c,d,n))
# print(flag)
# Ans 2: SA_K3YS_4R
## Part 3
# n = 333146335555060589623326457744716213139646991731493272747695074955549
# e = 65537
# p = 17357677172158834256725194757225793
# q = 19193025210159847056853811703017693
# phi_n = (p-1)*(q-1)
# d = inverse(e,phi_n)
# c_base64 = "AK/WPYsK5ECFsupuW98bCFKYUApgrQ6LTcm3KxY="
# c = bytes_to_long(b64decode(c_base64))
# flag = long_to_bytes(pow(c,d,n))
# print(flag)
# # Ans 3: _SO_BAD!}
# FLAG : IW{WEAK_RSA_K3YS_4R_SO_BAD!}Flag: IW{WEAK_RSA_K3YS_4R_SO_BAD!}
Given:
public.pem
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEBITsFfW/evEUntbdCGsHp
PM/+p2xPCHSZHPP6zw6rnvZGohg5ggtNZTqRa2jyWOnT98K6BU5K8F8+TWGz3nct
KtIziw6ubqCPIHbk5LCKsgkg+miF5sRN7BvuKKh2U8dLy56fEpTeiki9YUZSo9ZZ
3857iURhDyW/r5NumlQWfE0ifRbTLmXqRYtp1g3s1/oDTBs72GJxcWTneF6wbcxb
iLqiYuQxIOVGZcDLyz6tUbCgCBm06R1IctP753JOA6txvK+LuEx03slqrfyxhlOo
8FOT1mYGmSO8e5sxNj1tbZtFn0bbW6+W+EBKrxqDHw24qtfZOkJW6BVrK3B1egEg
kwIDAQAB
-----END PUBLIC KEY-----
flag.enc
Cc0GtEY4nL7DhDukClWKaTHChrCVJeVVm3MJ+6hgiqaYUjbx9ArCrH0uzdfDqf4l81NAqV0fGtd8a9H4dlEQRykvOwpFpViK4qTU1H28nEMZ6O1Hnt9NrLxlSvpARZd8hxoJtXiwUbZI6rcI9lQwt+pJLvrvw2/Mz+fBMvrVPFONSYDH/lU0wy4jKbH0zl7zJ09+gCBo9oJ2Hqpsh0BkcS6ix5lDu/6JENG/ChC7jZGYWpte+QIkb/fQTwsw3tGIz1jWYhqQ8MrSxtGpyyPG9Oy/zGHIBEBDesS4r72D8n2mQExRnCH2KW5wz5hsM2TXYRILtJqWCOyv/AF56Ebg9A==
Solution
- Step 1: Find
n,e,c
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from base64 import b64decode
f = open("public.pem","r")
public = RSA.import_key(f.read())
n = public.n
e = public.e
print("n = ",public.n)
print("e = ",public.e)
c_base64 = "Cc0GtEY4nL7DhDukClWKaTHChrCVJeVVm3MJ+6hgiqaYUjbx9ArCrH0uzdfDqf4l81NAqV0fGtd8a9H4dlEQRykvOwpFpViK4qTU1H28nEMZ6O1Hnt9NrLxlSvpARZd8hxoJtXiwUbZI6rcI9lQwt+pJLvrvw2/Mz+fBMvrVPFONSYDH/lU0wy4jKbH0zl7zJ09+gCBo9oJ2Hqpsh0BkcS6ix5lDu/6JENG/ChC7jZGYWpte+QIkb/fQTwsw3tGIz1jWYhqQ8MrSxtGpyyPG9Oy/zGHIBEBDesS4r72D8n2mQExRnCH2KW5wz5hsM2TXYRILtJqWCOyv/AF56Ebg9A=="
c = long_to_bytes(b64decode(c_base64))- Step 2: Using factorize to factorize
n, we havenis prime, sophi(n)=n-1. Then we haved = inverse(e,phi(n))andflag = pow(c,d,n)
Total code:
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from base64 import b64decode
f = open("public.pem","r")
public = RSA.import_key(f.read())
n = public.n
e = public.e
print("n = ",public.n)
print("e = ",public.e)
c_base64 = "Cc0GtEY4nL7DhDukClWKaTHChrCVJeVVm3MJ+6hgiqaYUjbx9ArCrH0uzdfDqf4l81NAqV0fGtd8a9H4dlEQRykvOwpFpViK4qTU1H28nEMZ6O1Hnt9NrLxlSvpARZd8hxoJtXiwUbZI6rcI9lQwt+pJLvrvw2/Mz+fBMvrVPFONSYDH/lU0wy4jKbH0zl7zJ09+gCBo9oJ2Hqpsh0BkcS6ix5lDu/6JENG/ChC7jZGYWpte+QIkb/fQTwsw3tGIz1jWYhqQ8MrSxtGpyyPG9Oy/zGHIBEBDesS4r72D8n2mQExRnCH2KW5wz5hsM2TXYRILtJqWCOyv/AF56Ebg9A=="
c = bytes_to_long(b64decode(c_base64))
print("c = ",c)
phi_n = n-1
d = inverse(e,phi_n)
flag = long_to_bytes(pow(c,d,n))
print(flag)Flag: Flag{S1nGL3_PR1m3_M0duLUs_ATT4cK_TaK3d_D0wn_RSA_T0_A_Sym3tr1c_ALg0r1thm}
Given
n = 0x6b612825bd7972986b4c0ccb8ccb2fbcd25fffbadd57350d713f73b1e51ba9fc4a6ae862475efa3c9fe7dfb4c89b4f92e925ce8e8eb8af1c40c15d2d99ca61fcb018ad92656a738c8ecf95413aa63d1262325ae70530b964437a9f9b03efd90fb1effc5bfd60153abc5c5852f437d748d91935d20626e18cbffa24459d786601
e = 2
c = 0xd9d6345f4f961790abb7830d367bede431f91112d11aabe1ed311c7710f43b9b0d5331f71a1fccbfca71f739ee5be42c16c6b4de2a9cbee1d827878083acc04247c6e678d075520ec727ef047ed55457ba794cf1d650cbed5b12508a65d36e6bf729b2b13feb5ce3409d6116a97abcd3c44f136a5befcb434e934da16808b0b
Require: Find flag
Step 1 : Convert n,c into decimal
n = "0x6b612825bd7972986b4c0ccb8ccb2fbcd25fffbadd57350d713f73b1e51ba9fc4a6ae862475efa3c9fe7dfb4c89b4f92e925ce8e8eb8af1c40c15d2d99ca61fcb018ad92656a738c8ecf95413aa63d1262325ae70530b964437a9f9b03efd90fb1effc5bfd60153abc5c5852f437d748d91935d20626e18cbffa24459d786601"
c = "0xd9d6345f4f961790abb7830d367bede431f91112d11aabe1ed311c7710f43b9b0d5331f71a1fccbfca71f739ee5be42c16c6b4de2a9cbee1d827878083acc04247c6e678d075520ec727ef047ed55457ba794cf1d650cbed5b12508a65d36e6bf729b2b13feb5ce3409d6116a97abcd3c44f136a5befcb434e934da16808b0b"
nn = int(n,16)
cc = int(c,16)Step 2 : Using factorize big number online we found that: n=p*p
Using this algorithm to find p:
import math
_1_50 = 1 << 50 # 2**50 == 1,125,899,906,842,624
def isqrt(x):
"""Return the integer part of the square root of x, even for very
large integer values."""
if x < 0:
raise ValueError('square root not defined for negative numbers')
if x < _1_50:
return int(math.sqrt(x)) # use math's sqrt() for small parameters
n = int(x)
if n <= 1:
return n # handle sqrt(0)==0, sqrt(1)==1
# Make a high initial estimate of the result (a little lower is slower!!!)
r = 1 << ((n.bit_length() + 1) >> 1)
while True:
newr = (r + n // r) >> 1 # next estimate by Newton-Raphson
if newr >= r:
return r
r = newr
nn = 75404462446621433278932073418166377856783371695311741162660984000216286022717332034344886883228963555598915581623574177254937709767805818855313080010310907057693076782794571905025544034519430835894406844610021327070351428935856401291946497064114909504725588880164068827953784803548706132824333011073782801921
print(isqrt(nn))Result: p=8683574289808398551680690596312519188712344019929990563696863014403818356652403139359303583094623893591695801854572600022831462919735839793929311522108161
Now, we will find research some bit knowledge about Quadratic residue
In number theory, an interger q is called a quadratic residue module n if it is congruent to a perfect square modulo n; i.e if there exists an integer x such that x^2=q(mod n).
Otherwise, q is called a quadratic nonresidue modulo n.
Next, we will get familiar with Legendre Symbol
In Legendre symbol we introduced a fast way to determine whether a number is a square root modulo a prime. We can go further: there are algorithms for efficiently calculating such roots. The best one in practice is called Tonelli-Shanks, which gets its funny name from the fact that is was first described by an Italian in the 19th century and rediscovered independently by Daniel Shanks in the 1970s.
All primes that aren't 2 are of the form p=1 (mod 4) or p=3 (mod 4), since all odd numbers obey these congruences. As the previous challenge hinted, in the p=3 (mod 4) case, a really simple formula for computing square roots can be derived directly from Fermat's little theorem. That leaves us still with the p=1(mod 4) case, so a more general algorithm is required.
In a congruence of the form r^2 = a(mod p), Tonelli-Shanks calculates r
Note: Tonelli-Shanks doesn't work for composite(non-prime) moduli. Finding square roots modulo composites is computationally equivalent to integer factorization.
Next, we will have research Legendre symbol:
And some characteristic of this:
and last is example:
Another we can reference some special symbols such as: Jacobi symbol and Kronecker Symbol
-
In this Challenge we were given with two file flag.enc and private.pem.
-
With
flag.enc, we can convert into long:
from Crypto.Util.number import bytes_to_long,long_to_bytes
f = open("flag.enc","rb")
print(bytes_to_long(f.read()))-
Challenge Description says
Our security agency has got hold of a ciphertext and a key. Well..the key got corrupted and the lost character is represented by a x. Can you decipher the message for us? -
Viewing the private.pem file,we can notice a emoji is replaced in the place of a letter,which would make the private key invalid.
-
We can brutefoce all possible lowercase+uppercase alphabets and for each iteration decrypt the flag.enc.
-
Print the flag if we got a hit on the string which matches
KCTF -
Below is the Exploit script
from Crypto.Util.number import long_to_bytes
from Crypto.PublicKey import RSA
import string
import re
a='''-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEAyiytHt1AKzYLwZPm1dd9uT7LgsqVj0eSLpheNd0H4xyiZCYG
ZtRYnNtGNnq7A/ubyFalExm61QNewfy71h6xhM/'''
b = '''IEIoNT0VfMOIzcq0Jmoh+v6k
6/x/3GRkk/vLVolsLbkOKd4aorPMwEsZX4vMd+Sga5Mz0tx5xLFZsbl0r1vvtBl7
CtC/ojWX4+/RSGuaUVVayrU32kyCjJo3hniSaY2EvSXXHdE6nOKkF725LVrnOOIz
1/n9CYrYPV6ESEBdwS7VOen8uPwh5cFGHOV49ofmvVZNvcV2qoKFjY5UXf8fDzZ+
jBzWiCukE+3WFwgEYaBGg/a6HomkobpDqxkrYwIDAQABAoIBABht45FaLLnL8wm2
BGuMeV2b791i+0Vv4YMN2Dxr89sGh7zQN2/PctGpUUed9uEZUw6XIaU4M7IvkRCh
qFTMKqkgrVd4hwE/20vTGMG9H52Qr4Bzqpv1S8Hmw5x6DWzseAziUorOkqtcTH5j
1LIN42wNTTESfW2aRIB26Z6nCSlzHD8jpBYlrBFNsXydApEtA86PPtgs8MUsABFa
Rhy6VG9rNfzaBeRDX1m1lX+yNkqPb3xgABeYgURYgUneiTY/S5GrFfrtRAnLWVm4
audCUkxvF8OV0vJnazcMUopleBonMH2FCl3vKAjTX2xq9X24PeNXDg6SfiEEuI/g
EDtJO1ECgYEAzwBWVwbx/lvc5PP3oYXRr9IpflZ3Z9xSyopY0KpOakAXn6717x6i
s/1DwGvpmFBqUd25vhcn9ztj18GtMCtZ4dNvvyGpPwvM41Z1RVHY5REfC7sgBp8W
0N+IVR2QlyU3pjoS5t19O3g48fhOp8o3wsZ+05RpLtUhNXe0yHxk7fsCgYEA+gfZ
aCr+dgzHfdBOEwwozaRpJANchnGeILSgZZEeYmyE0RuBcatpwxKs+jG82mWYnosN
KR5CZZiPn/laySUQEB5H6Cg/OQDVyj5r49adc2H8hTCluaXtiVyxA3JqV8Ixc9TM
cRWJZdokaDbkyNXCuUuTMinzWjrNBKBZ+zg5w7kCgYBQkjwJEb39mHoJb+CSMUkl
23KlJzjA52QeS+04AyIUfy/yyqIVWeJQlqLZcedxjtNjXB9hGxhGRgqdv1gO6MDK
gob7aTm8PXaZglyRB8OZnals4oAbs66ozGj/YEuYWTco72/OBqYpEKlxnYnYC4Da
wnI5Hoo2XWTYr+hhJPIQIwKBgAxMxo0xUENObaHq1WxqdLdpFyMGZ07V2AmT2TAl
63C8FeyThdKptBI8oPXN7JRx2wgxnvwe2PVWg/pCsgyjHh8s3iy1jianu9yvJW+X
5zb94wZKVlzDpOPVA4A/6KtYikZAea42eQPhr1jRGoAmw+WJqjwVhDs0GVHY8ZRC
N9VBAoGBAJTZwrY+tZkNzURk9JLWzrevfD6BpYrQ0jchaGtzdgjdOpHo3++cdUag
9oQ8ZNKaUVDm3lyzUhO41Hw7xMmmW8JwsVvKdrRL+ZG12Ts/uiy1P0DY+HsNMr9d
xqG9YAHVmm4iJzcHeMdzLwmzR6D/x6+k2cFWwox6PxvA7ikJQEYr
-----END RSA PRIVATE KEY-----
'''
alphabet_string = string.ascii_lowercase
alphabet_string2 = string.ascii_uppercase
ct = 3727860015271984841324159765928537422111591563168703246274534058212860148324984926533129834972015501237164337596283528586314608137883075991757210424415228060370930359406872327945577230190541395424158421129540532799576716844437077695468441298361281287281500731107510110919792316394598802631743356037461925682629386640483698027096813857434182454560793760145474202157717338360918130962780548424537332305217288434027436974151260268471169603628280221742021890088311856300748132434057776577308980718407083905792718517692206286940837721132833739445400411565013638730221599142594621268990711490374043387501971024260884088096
alphabets = alphabet_string+alphabet_string2
length = len(alphabets)
for i in range(0,length):
key = RSA.importKey(a+alphabets[i]+b)
n = key.n
d = key.d
m = pow(ct,d,n)
m = long_to_bytes(m)
if (m.find('KCTF') != -1):
flag = re.compile('KCTF+.*')
print(flag.findall(m)[0])
#Flag KCTF{M4Y_TH3_8RUT3F0rc3_B3_W1TH_Y0U}The problem give us 2 files: chal.sage and out.txt, detailed as follow:
chal.sage
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long
import random
import binascii
from secret import flag
e = 3
BITSIZE = 8192
key = RSA.generate(BITSIZE)
n = key.n
flag = bytes_to_long(flag)
m = floor(BITSIZE/(e*e)) - 400
assert (m < BITSIZE - len(bin(flag)[2:]))
r1 = random.randint(1,pow(2,m))
r2 = random.randint(r1,pow(2,m))
msg1 = pow(2,m)*flag + r1
msg2 = pow(2,m)*flag + r2
C1 = Integer(pow(msg1,e,n))
C2 = Integer(pow(msg2,e,n))
print(f'{n = }\n{C1 = }\n{C2 = }')out.txt
n = 823652328526060931201375649241006048943627312591742662481083103378002522077877852124731191042617160616707714556599692967069663667698601996983528940331840856212083763983210643933408040552418340463683380557808507002495230815546453104038740886365473259236836768987811419579308089803722619415774848441151249684528573808701348303730672001325400435253430057941264536553439343549378798471521843765967413899839467956313753964739101523564712402586172009670872793597148015854112713073516537134244622001863136944934492241145306737850771111625635504275979597201321615004183224138178242850606020061860874365891414739635021953470569531263648279914661978749409495850032838932287660547294983608500552408270453150111004704982673000064474229357303826290412232101668643442191345117752836713723186345029858940323602239828980619674790421554523298312252632246856653570861376722546483845572057592874642653507921669598604980999675710944351125800581153679737947035951167396427406664211538456926422574733908468243848301080202616710219948021550303624199272309262465841979895988543037749409344273271528685813232663250051559875409936374630801262025889212026998068310718442102601557388789291924368011403387710015947533663816312246609754580679612583443687679604653697210741383870120265666560114312552082718765229857906075466911647146394186461224534740685587572846934610230530077015354170886197688407248753878297395666994564903309464938353409270895657559261894379593177576322878056778321362020242262629594237747578073010697822390042229221755183530894661801846645578606229378188194698297341498164221255458973569036112042793665638020083355322818801649079577206155596664351547761867936241825962264402061264130743855926770190009644935373522637016531313612905118696369479379392748765790270985780979092810127202612369788297683386941277137962371308477169065442960974519121200614968578299255908217109555425373639991249942561881066593925137769635916819686179968920303847549317832449280869569173490086055713440659573036379376871313591502012736961740953226823792006776306025493582816361497869257717651668075570919074032100188984609089237083774415809378590512597855039607625398955711313352280354581208986236739705133090250836743923077744209886105632205516098409509945870967048379575392597005574605671295696290105152505109115729545462303929321064678575733744453013844396847747874774560936394947704938716022268449263762808882912779863563062087323815155503567025604594567944510834845389179609006394130719657363087
C1 = 138604270237134534112743212644616449187692378939637896055320936677529897960835117799077267347298678107031857708834234867949004008866584408288272718174944005247281182704110071985982762860316789278723189738430436690943806868878982562799129736576593875631850056775539229239799682738700710216806174002449616599477466210310386600736499714740361747969973718347095697189605303148613119104798603461313289164107162759182110107568729898709265252329895862170091572165860623096748730108315029720395180483240857815537765987240293780559413621634616731611457999105645890254616180108684484111551400204145466579713376335168837095473428132610657311922576659063964864816927637794472255883920363962994040086056352213615355155336047742875321877777043584327913192448537029767660816802421871457551873100279391823455263903450304034557919732645143487533538943198997776987742643929566403463889152262047049873409325737357390275038091407938919150758822963329761264354005399142689352595527066743969291045496548965996410916410974600827179080229802502026992567559903302198282019316525974045236753071662259094177004561587843521123352176047829889922474932560434065169177898287264496750729243672
C2 = 138604270237134534112743212644616449187692378939637896055320936677529897960835117799077267347298678107031857708834234867949004008866584408288272718174944005247281182704110071985982762860316789278723189738430436690943806868878982562801315565156426103645734001592666235894224346424366448014174339619953344112868374944069699668659552171905796026764359565068714399719527680623357405851675409955573477228301886561411896147227291350808930951282598922176120977605666135963906053158934308125639347521515926780372069545707019601637468577493997742590807146827349865640857651027809446746299962731018358206171079317925725680542147150070051957133849278906576405074966481232057919403951090124732230438431203080079109828298282999845576767904877434936923847105040157703725014937676457110907557409863930279230474134789746314617582331031090955073528453085567165286271224442421785911327002274933133905582320854345262688022854226418394665705506630780960278867388105443056536999414456768050350078505683642885335398895190922264436040594316438930099159076822113725497974332635130516805301785291427363314598707750026963533325470071715793252887081074252099626695293515248472454824781000
We have:
-
msg1^3 = C1 (mod n) -
msg2^3 = C2 (mod n) -
msg1 = flag * 2^{m} + r1 -
msg2 = flag * 2^{m} + r2 -
With
m = 510,1<=r1<=r2<=2^m
We will analyze a little bit about number digit of msg1,C1,C2 and n
We have:
-
nhas2466digits -
C1andC2have also1161digits -
2^mhas approxiate153digits =>msg1^3has approxiate459*flag
While C1 has 1161
So from those, we have: msg1^3=C1 and msg2^3=C2
Now, we have C1,C2, actually we need compute only msg1 is enough !
Now, we will use Divide and Conquer Algorithm to compute cube root of C1
This is the code find n'th root of number x
def nth_root(x, n):
# Start with some reasonable bounds around the nth root.
upper_bound = 1
while upper_bound ** n <= x:
upper_bound *= 2
lower_bound = upper_bound // 2
# Keep searching for a better result as long as the bounds make sense.
while lower_bound < upper_bound:
mid = (lower_bound + upper_bound) // 2
mid_nth = mid ** n
if lower_bound < mid and mid_nth < x:
lower_bound = mid
elif upper_bound > mid and mid_nth > x:
upper_bound = mid
else:
# Found perfect nth root.
return mid
return mid + 1And this solution of this problem
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long,long_to_bytes
import random
import binascii
from secret import flag
###### PROBLEM ######
# e = 3
# BITSIZE = 1024
# key = RSA.generate(BITSIZE)
# n = key.n
# flag = bytes_to_long(flag)
# print("n: ",n)
# print("flag: ",flag)
# m = BITSIZE//(e*e) - 50
# r1 = random.randint(1,pow(2,m))
# r2 = random.randint(r1,pow(2,m))
# msg1 = pow(2,m)*flag + r1
# msg2 = pow(2,m)*flag + r2
# C1 = pow(msg1,e,n)
# C2 = pow(msg2,e,n)
# print(f'{n = }\n{C1 = }\n{C2 = }')
# print("Test 1:",pow(msg1,3)-C1)
# print("Test 2:",pow(msg2,3)-C2)
###### SOLUTION ######
def nth_root(x, n):
# Start with some reasonable bounds around the nth root.
upper_bound = 1
while upper_bound ** n <= x:
upper_bound *= 2
lower_bound = upper_bound // 2
# Keep searching for a better result as long as the bounds make sense.
while lower_bound < upper_bound:
mid = (lower_bound + upper_bound) // 2
mid_nth = mid ** n
if lower_bound < mid and mid_nth < x:
lower_bound = mid
elif upper_bound > mid and mid_nth > x:
upper_bound = mid
else:
# Found perfect nth root.
return mid
return mid + 1
m = 510
C1 = 138604270237134534112743212644616449187692378939637896055320936677529897960835117799077267347298678107031857708834234867949004008866584408288272718174944005247281182704110071985982762860316789278723189738430436690943806868878982562799129736576593875631850056775539229239799682738700710216806174002449616599477466210310386600736499714740361747969973718347095697189605303148613119104798603461313289164107162759182110107568729898709265252329895862170091572165860623096748730108315029720395180483240857815537765987240293780559413621634616731611457999105645890254616180108684484111551400204145466579713376335168837095473428132610657311922576659063964864816927637794472255883920363962994040086056352213615355155336047742875321877777043584327913192448537029767660816802421871457551873100279391823455263903450304034557919732645143487533538943198997776987742643929566403463889152262047049873409325737357390275038091407938919150758822963329761264354005399142689352595527066743969291045496548965996410916410974600827179080229802502026992567559903302198282019316525974045236753071662259094177004561587843521123352176047829889922474932560434065169177898287264496750729243672
g1 = nth_root(C1,3)
K = pow(2,m)
r1 = g1 % K
# print(r1)
flag = (g1-r1)//K
print(long_to_bytes(flag))
#flag_final = 154393050551454020090514297200922012210056319897965118750440811938341742022936780608133963214043027836777756205300371216004407768274132755769040020127958503581173320507900533732136817550207767148177469879490070754935314884923896381309
# flag_final1 = 2689276504310631707478400123130984936310976782319770622603922543360881069490035758414301813498217745374830369542722941247551735690124561015564676628519906993119832597021135435970751146045680238055519831015820279678694558572703641886454848236967291037462015700658168832646801086807243098003268469538880
# print(long_to_bytes(flag_final1))And we will get flag
crew{l00ks_l1k3_y0u_h4v3_you_He4rd_0f_c0pp3rsm1th_sh0r+_p4d_4tt4ck_th4t_w45n't_d1ff1cult_w4s_it?}
The problem give us a statement:
== proof-of-work: disabled ==
n: 9099069576005010864322131238316022841221043338895736227456302636550336776171968946298044005765927235002236358603510713249831486899034262930368203212096032559091664507617383780759417104649503558521835589329751163691461155254201486010636703570864285313772976190442467858988008292898546327400223671343777884080302269
Here is RSA encrypted flag.(e=65537)
7721448675656271306770207905447278771344900690929609366254539633666634639656550740458154588923683190330091584419635454991419701119568903552077272516472473602367188377791329158090763546083264422552335660922148840678536264063681459356778292303287448582918945582522946194737497041408425657842265913159282583371732459
Let's see a property of numbers... I like small numbers.
pow(4, x, n) = 3
x->2076118641589166085567213874123474567491402237019668147884288468645748227900602149506213192343093244218866119520289447791172877431433341258605333332347317311240605414266962400678327394383961953495485042589683815930048091844890318004699674982043472077122232159707521022410989077157770575872817558884492139975614597
pow(8, x, n) = 7
x->570481792553282645867016247709264298221131860678573812616921555986238556312142113287582311278495020362100663108209217027748644136334829350490306775744918923811231372691300869181402544517366663817020095330354191043859808572829301218801816885745384781881259366872787514869251800308553996081149858726536089368839064
pow(4, x, n) = 7
x->855722688829923968800524371563896447331697791017860718925382333979357834468213169931373466917742530543150994662313825541622966204502244025735460163617378385716847059036951303772103816776049995725530142995531286565789712859243951828202725328618077172821889050309181272303877700462830994121724788089804134053258596
pow(2, x, n) = 3
x->4152237283178332171134427748246949134982804474039336295768576937291496455801204299012426384686186488437732239040578895582345754862866682517210666664694634622481210828533924801356654788767923906990970085179367631860096183689780636009399349964086944154244464319415042044821978154315541151745635117768984279951229194
pow(9, x, n) = 7
x->1054156663532949017820446207672781543086515249287744969638214339331295245382323409940477418924969955788539945803249537876463709506856113889266213509621440928560104784495364553042394060462684347026550923448282194835059887286242632372339522130562494706847419860622125915531462963858618845383475136682837714340274340
pow(5, x, n) = 7
x->3916704810437927145600864918236836170491099995953699168541731264707734332610664820402524451306018121752526504056848858498261740094610196113519273038900804576322610451175905222231364299872297068281255941214365432478262573598957328534058633443808701127122560630454143760365394739477719428783885592620907691725814382
pow(2, x, n) = 9
x->3754939778354158910107789877335886849355087278630804477809002556307824523516424124875830766489409359374346298779402434539775766276216233569237231723341252968455894584408143678496101610613389877101646294181565422615598678053423609327485531311004778211836628609338110226534895570202818439605250908707603466887326390
pow(4, x, n) = 9
x->1877469889177079455053894938667943424677543639315402238904501278153912261758212062437915383244704679687173149389701217269887883138108116784618615861670626484227947292204071839248050805306694938550823147090782711307799339026711804663742765655502389105918314304669055113267447785101409219802625454353801733443663195
pow(5, x, n) = 4
x->1409828699698033208091409044455165366643801419932373553123260771987699896353688393694756863763560622086506122042233901651495199885942636834433947550336356542178907165298626723075515405354701129627152693478823016506389518956567226250580121882030622556782873851604640300443552173844660124075798887496649067556217390
pow(6, x, n) = 2
x->939292781082112016281996120029640558513504271209074729744679536785999346698143634739122352482233665730748662161995597875421203578208037954730627469631250345432329905035343676336544953322597208540536869444672643207916253721052582779000448220996637632239183670918288993354842447149274646102688185469428348953985987
pow(5, x, n) = 3
x->2133766932864388673682415264428852563157697531212805381722606537415880821651881836036219743693469157186116448622886351607608930829881035994695888699244352664133706885871664208865202356948720814126562878822367646312138979081062675067312895961013235414261084030444892478136847891250703661546259439777289170770933244
pow(6, x, n) = 9
x->2670949225838281399597073379098730303583513127029718654238792244703169694689697203670777297918496286039620854977764160874073336293101055555722846666785515585641867262589018571544118060277263519799220137287824554688761181884032497133312272175175834832173932687655395876399375844129714571680642955891508395107160026
pow(7, x, n) = 4
x->782048530527862007921345086825967824809921804253677698357640394456486443141294396991806703662463153174674499822712272620352264740247063132442983714411111748779418558073361927132656469123102907840771323625012596232213516808553077385813641065260507991821817461035116755889737568582054061118287348291920439180743213
pow(8, x, n) = 3
x->1384079094392777390378142582748983044994268158013112098589525645763832151933734766337475461562062162812577413013526298527448584954288894172403555554898211540827070276177974933785551596255974635663656695059789210620032061229926878669799783321362314718081488106471680681607326051438513717248545039256328093317076398
pow(6, x, n) = 8
x->2817878343246336048845988360088921675540512813627224189234038610357998040094430904217367057446700997192245986485986793626263610734624113864191882408893751036296989715106031029009634859967791625621610608334017929623748761163157748337001344662989912896717551012754866980064527341447823938308064556408285046861957961
pow(5, x, n) = 9
x->4267533865728777347364830528857705126315395062425610763445213074831761643303763672072439487386938314372232897245772703215217861659762071989391777398488705328267413771743328417730404713897441628253125757644735292624277958162125350134625791922026470828522168060889784956273695782501407323092518879554578341541866488
pow(3, x, n) = 7
x->2108313327065898035640892415345563086173030498575489939276428678662590490764646819880954837849939911577079891606499075752927419013712227778532427019242881857120209568990729106084788120925368694053101846896564389670119774572485264744679044261124989413694839721244251831062925927717237690766950273365675428680548680
pow(2, x, n) = 6
x->4152237283178332171134427748246949134982804474039336295768576937291496455801204299012426384686186488437732239040578895582345754862866682517210666664694634622481210828533924801356654788767923906990970085179367631860096183689780636009399349964086944154244464319415042044821978154315541151745635117768984279951229195
pow(7, x, n) = 3
x->302667136777917447885639399855798746783792281082047426137560224394234690761198213214781903275125974443412434383258389499537763965208434880475329103516951799391535587982643066857765962424901807944918698865193821688853878387134235170443608989618620354405251870857636073985822876614487518015398151778674906411808601
pow(6, x, n) = 4
x->1878585562164224032563992240059281117027008542418149459489359073571998693396287269478244704964467331461497324323991195750842407156416075909461254939262500690864659810070687352673089906645194417081073738889345286415832507442105165558000896441993275264478367341836577986709684894298549292205376370938856697907971974
pow(8, x, n) = 6
x->2900590690393612534431831122468320185197775381162401469832242751855554947962396257387149462523050035312950139447444750735753832770794604660798256090247550299662579300397876908524620918563460614623754653785512490988229957671972766233570839527085351416965588116302338635977012964247935005210551481533116457655453731
pow(6, x, n) = 3
x->3610242006920393415879069499128370862097017398238793383983471781489169041387840838409899650400729951770369517139759758749494539871309093510453474136416765931074197167624362247880663013599860728339757006732497197896677435605085079912312720396172472464413116358573684869754218291278989217783331141360936744061146012
pow(3, x, n) = 4
x->1363952586418552326838027389457770381128348610341916654151049344040269791768048789580711074747324279253953986869951673094759791136335614290642926045930520993156736257909660908648437081973019508017016877769804013904226195162132557973767673754417051913608582789200470895254896416316547292509925572389642012264907490
pow(7, x, n) = 9
x->605334273555834895771278799711597493567584562164094852275120448788469381522396426429563806550251948886824868766516778999075527930416869760950658207033903598783071175965286133715531924849803615889837397730387643377707756774268470340887217979237240708810503741715272147971645753228975036030796303557349812823617202
pow(2, x, n) = 7
x->1711445377659847937601048743127792894663395582035721437850764667958715668936426339862746933835485061086301989324627651083245932409004488051470920327234756771433694118073902607544207633552099991451060285991062573131579425718487903656405450657236154345643778100618362544607755400925661988243449576179608268106517192
pow(8, x, n) = 9
x->2768158188785554780756285165497966089988536316026224197179051291527664303867469532674950923124124325625154826027052597054897169908577788344807111109796423081654140552355949867571103192511949271327313390119578421240064122459853757339599566642724629436162976212943361363214652102877027434497090078512656186634152796
pow(6, x, n) = 7
x->4382451963215414951923427484295917714075099595415988392264685392449057783423441922126020145423600985804385331915992918388410803253438498450309874925605271432370368439308396818520118534947166364332426731242512326875404549273011444416465627832281990548624424694040059123529752908838818278511190008322930537534907342
pow(9, x, n) = 4
x->681976293209276163419013694728885190564174305170958327075524672020134895884024394790355537373662139626976993434975836547379895568167807145321463022965260496578368128954830454324218540986509754008508438884902006952113097581066278986883836877208525956804291394600235447627448208158273646254962786194821006132453745
pow(8, x, n) = 4
x->3033023192001670288107377079438674280407014446298578742485434212183445592057322982099348001921975745000745452867836904416610495633011420976789401070698677517671018048439803949478138644614971957920195917451446560736395792884091775127542112411446073397768200019661315908739373825618842575924012884553576728676754666It's quite long, but after analyze, we recognize that, we actually need 3 arguments and last expression
-
n=9099069576005010864322131238316022841221043338895736227456302636550336776171968946298044005765927235002236358603510713249831486899034262930368203212096032559091664507617383780759417104649503558521835589329751163691461155254201486010636703570864285313772976190442467858988008292898546327400223671343777884080302269 -
e = 65537 -
c = 7721448675656271306770207905447278771344900690929609366254539633666634639656550740458154588923683190330091584419635454991419701119568903552077272516472473602367188377791329158090763546083264422552335660922148840678536264063681459356778292303287448582918945582522946194737497041408425657842265913159282583371732459
last expression:
pow(8, x, n) = 4
x->3033023192001670288107377079438674280407014446298578742485434212183445592057322982099348001921975745000745452867836904416610495633011420976789401070698677517671018048439803949478138644614971957920195917451446560736395792884091775127542112411446073397768200019661315908739373825618842575924012884553576728676754666The reason we choose the last expression is because it is a clue for us to find phi(n), specifically as follows:
We have : 8^x = 4 (mod n) or 2^{3x-2} = 1 (mod n)
No we will analyze a litte bit about number of digit of n and phi(n)
We found that: Number of digits of n approxiate Number of digits of phi(n)
Because: n = p*q and phi(n) = (p-1)(q-1) ~ pq = n
And now, we continue see that:
3x-2 has approxiate n , so we boldly guess that 3x-2 is phi(n)
And luckily, Finally we get the flag, detail as follow:
We have: ed = 1 (mod phi(n)), with phi(n)=3x-2
So we will easily find d and flag = c^d (mod n)
And this is my solution:
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long,long_to_bytes
import random
import binascii
n = 9099069576005010864322131238316022841221043338895736227456302636550336776171968946298044005765927235002236358603510713249831486899034262930368203212096032559091664507617383780759417104649503558521835589329751163691461155254201486010636703570864285313772976190442467858988008292898546327400223671343777884080302269
e = 65537
c = 7721448675656271306770207905447278771344900690929609366254539633666634639656550740458154588923683190330091584419635454991419701119568903552077272516472473602367188377791329158090763546083264422552335660922148840678536264063681459356778292303287448582918945582522946194737497041408425657842265913159282583371732459
x = 3033023192001670288107377079438674280407014446298578742485434212183445592057322982099348001921975745000745452867836904416610495633011420976789401070698677517671018048439803949478138644614971957920195917451446560736395792884091775127542112411446073397768200019661315908739373825618842575924012884553576728676754666
phi_n = 3*x-2
d = pow(e,-1,phi_n)
flag = pow(c,d,n)
print(long_to_bytes(flag))And we get result:
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@crew{d15cr373_l06_15_r3duc710n_f0r_f4c70r1n6}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
And flag is:
crew{d15cr373_l06_15_r3duc710n_f0r_f4c70r1n6}
LINK PROBLEM: GOTTA GO FAST
Problem statement: Connect at nc socket.cryptohack.org 13372 and file 13372.py
#!/usr/bin/env python3
import time
from Crypto.Util.number import long_to_bytes
import hashlib
from utils import listener
FLAG = b'crypto{????????????????????}'
def generate_key():
current_time = int(time.time())
key = long_to_bytes(current_time)
return hashlib.sha256(key).digest()
def encrypt(b):
key = generate_key()
assert len(b) <= len(key), "Data package too large to encrypt"
ciphertext = b''
for i in range(len(b)):
ciphertext += bytes([b[i] ^ key[i]])
return ciphertext.hex()
class Challenge():
def __init__(self):
self.before_input = "Gotta go fast!\n"
def challenge(self, your_input):
if not 'option' in your_input:
return {"error": "You must send an option to this server"}
elif your_input['option'] == 'get_flag':
return {"encrypted_flag": encrypt(FLAG)}
elif your_input['option'] == 'encrypt_data':
input_data = bytes.fromhex(your_input['input_data'])
return {"encrypted_data": encrypt(input_data)}
else:
return {"error": "Invalid option"}
"""
When you connect, the 'challenge' function will be called on your JSON
input.
"""
listener.start_server(port=13372)This is my solution:
Firstly, we see that: encrypted_flag = flag[i]^key[i] and encrypted_data = input_data[i]^key[i]
And suppose that, we can input with input_data = crypto{????????????????????}, and the difficult point of this problem is key because key is created follow current time
So, after a few moment thinking and guess, I found that, when distance between moment is very little, key at 2 moment is same !
=> flag = encrypted_flag ^ encrypted_date ^ input_data
And this is my code.
from pwn import *
import time
from Crypto.Util.number import long_to_bytes
import hashlib
import json
r = remote("socket.cryptohack.org",13372)
u = r.recvline()
FLAG_FAKE = b'crypto{????????????????????}'
la_time = str(FLAG_FAKE.hex())
res1 = '{"option":"get_flag"}'
r.sendline(res1.encode())
u = r.recvline()
print(u)
res2 = '{"option":"encrypt_data","input_data":'+chr(34)+la_time+chr(34)+'}'
r.sendline(res2.encode())
u = r.recvline()
print(u)
#y = json.loads(u)
#print(bytes.fromhex(y["encrypted_data"]))And we get result
b'{"encrypted_flag": "39c97bfb78d7007419b01867c812994c53725bf244d7b17533f409e6"}\n'
b'{"encrypted_data": "39c97bfb78d7003f16bf783ec35ed22c187d54921d9dfc233cbe03e6"}\n'
# b'{"encrypted_flag": "39c97bfb78d7007419b01867c812994c53725bf244d7b17533f409e6"}\n'
# b'{"encrypted_data": "39c97bfb78d7003f16bf783ec35ed22c187d54921d9dfc233cbe03e6"}\n'
enc_flag = "39c97bfb78d7007419b01867c812994c53725bf244d7b17533f409e6"
enc_data = "39c97bfb78d7003f16bf783ec35ed22c187d54921d9dfc233cbe03e6"
enc_flag_byte = bytes.fromhex(enc_flag)
enc_data_byte = bytes.fromhex(enc_data)
FLAG_FAKE = b'crypto{????????????????????}'
arr1 = []
arr2 = []
arr3 = []
arr4 = []
ress = ""
for u in enc_flag_byte:
arr1.append(u)
for u in enc_data_byte:
arr2.append(u)
for u in FLAG_FAKE:
arr3.append(u)
for i in range(28):
arr4.append(arr1[i]^arr2[i]^arr3[i])
ress = ress + chr(arr1[i]^arr2[i]^arr3[i])
print(ress)And ger result:
crypto{t00_f4st_t00_furi0u5}
Link: https://github.com/FlorianPicca/ROCA/tree/master
Link: https://github.com/LexMACS/LIT-CTF-2022/tree/main/crypto
😎😎 CRYPTO mà nó lạ lắm, REVERSE thì đúng hơn :_)
✈🧨🏳🌈Cũng lâu lắm rồi, chưa viết cái write up để mọi người đọc cho vui, nên hôm nay được chút rãnh chiều chủ nhật, viết lại chút đỉnh :)
Ok, challenge cho chúng ta 2 file, 1 file là thuật toán mã hoá và 1 file là output
import os
BLOCK_SIZE = 16
FLAG = b'|||REDACTED|||'
def pad_pt(pt):
amount_padding = 16 if (16 - len(pt) % 16) == 0 else 16 - len(pt) % 16
return pt + (b'\x3f' * amount_padding)
pt = pad_pt(FLAG)
key = os.urandom(BLOCK_SIZE)
ct = b''
j = 0
for i in range(len(pt)):
ct += (key[j] ^ pt[i]).to_bytes(1, 'big')
j += 1
j %= 16
with open('output.txt', 'w') as f:
f.write(ct.hex())và file output là:
b4b55c3ee34fac488ebeda573ab1f974bf9b2b0ee865e45a92d2f14b7bdabb6ed4872e4dd974e803d9b2ba1c77baf725😍😍Thì như thường lệ, trước tiên, chúng ta đi hiểu cái thuật toán mã hoá nó nói những gì đã !
🤷♂️ Thì trước tiên, ta đi unhex cái chuỗi b4b55c3ee34fac488ebeda573ab1f974bf9b2b0ee865e45a92d2f14b7bdabb6ed4872e4dd974e803d9b2ba1c77baf725 này để xem nó ra cái gì !
ct_hex = "b4b55c3ee34fac488ebeda573ab1f974bf9b2b0ee865e45a92d2f14b7bdabb6ed4872e4dd974e803d9b2ba1c77baf725"
ct = b''.fromhex(ct_hex)💖💖 Tiếp theo, ta sẽ đi tìm hiểu cái vòng for:
for i in range(len(pt)):
ct += (key[j] ^ pt[i]).to_bytes(1, 'big')
j += 1
j %= 16🤔 Về cơ bản, cái này toàn phép tính toán bình thường, chỉ có cái function to_bytes(1, 'big') này là hơi lạ một chút, nhưng thật ra cũng ez, đó là nó chuyển từ số sang ký tự mà thôi. Ví dụ: 111 --> to_bytes(1,'big') sẽ thành 'o'
🎨🎨🎨 Tiếp theo, ta sẽ đi tìm hiểu cái def pad_pt(pt) nó nói cái gì trong đó:
def pad_pt(pt):
amount_padding = 16 if (16 - len(pt) % 16) == 0 else 16 - len(pt) % 16
return pt + (b'\x3f' * amount_padding)Đoạn code này khá dễ hiểu:
Giả sử cái pt ta truyền vào là FLAG đi, với FLAG = b'TFCCTF{aaaaaaaaaaaaaaaaaaaaaaaa}
Thì kết quả nó trả về là: b'TFCCTF{aaaaaaaaaaaaaaaaaaaaaaaa}????????????
🐱🐉🐱🐉 Chúng ta chú ý: b'\x3f' chính là dấu ?
🙌🙌 Còn cái key = os.urandom(BLOCK_SIZE) thì thực chắc nó sinh một chuỗi random có 16 bytes thôi !
Đến đây, có vẻ mọi thứ đã dễ dàng hơn !
Công việc, của chúng ta là đi tìm cái key random này thôi !
🎪🎪🎪 Nào, ta cùng tiến hành phá vụ án này nhé !
🎨 Bước 1: Đi unhex cái output đề bài cho và xem thử nó có bao nhiêu bytes !
💎 Code:
ct_hex = "b4b55c3ee34fac488ebeda573ab1f974bf9b2b0ee865e45a92d2f14b7bdabb6ed4872e4dd974e803d9b2ba1c77baf725"
ct = b''.fromhex(ct_hex)
print("After unhex: ",ct)
print("Number of bytes",len(ct))
print("Convert into integers array: ")
a = []
for u in ct:
a.append(u)
print(a)😉 Kết quả ta nhận được:
After unhex: b'\xb4\xb5\\>\xe3O\xacH\x8e\xbe\xdaW:\xb1\xf9t\xbf\x9b+\x0e\xe8e\xe4Z\x92\xd2\xf1K{\xda\xbbn\xd4\x87.M\xd9t\xe8\x03\xd9\xb2\xba\x1cw\xba\xf7%'
Number of bytes 48
Convert into integers array:
[180, 181, 92, 62, 227, 79, 172, 72, 142, 190, 218, 87, 58, 177, 249, 116, 191, 155, 43, 14, 232, 101, 228, 90, 146, 210, 241, 75, 123, 218, 187, 110, 212, 135, 46, 77, 217, 116, 232, 3, 217, 178, 186, 28, 119, 186, 247, 37]Okie, và ta sẽ gán mảng này với lên là: arr_long=[180, 181, 92, 62, 227, 79, 172, 72, 142, 190, 218, 87, 58, 177, 249, 116, 191, 155, 43, 14, 232, 101, 228, 90, 146, 210, 241, 75, 123, 218, 187, 110, 212, 135, 46, 77, 217, 116, 232, 3, 217, 178, 186, 28, 119, 186, 247, 37]
🐱🚀🐱🚀 Và chúng ta chú ý là cái mảng này có 48 ký tự đấy nhé !
💖💖 Ok, bây giờ chúng ta sẽ quay lại pt. Vì cái arr_long này nó có 48 ký tự nên cái pt nó sẽ cũng có 48 ký tự và nó sẽ có dạng như sau:
TFCCTF{xx...xxx}??..??
🤔🤔 Bây giờ, chúng ta sẽ tìm hiểu một chút về cái thuật toán mã hoá này !
Vì cái key của chúng ta của 16 bytes nên nó sẽ được lặp lại 3 lần
Và đây chính là thuật toán giải mã:
Bây giờ, pt[0..6] = 'TFCCTF{' và arr_long thì chúng ta cũng đã biết,
do đó công việc còn lại chỉ là chúng ta đi tìm key là xong
✨✨ Đi tính key[0..6]=pt[0..6]^arr_long[0..6]
Và code như sau:
FLAG = b'TFCCTF{aaaaaaaaaaaaaaaaaaaaaaaa}'
key = []
for i in range(0,7):
key.append(FLAG[i]^arr_long[i])
print('key[0..6] = ',key)Và kết quả ta nhận được là:
key[0..6] = [224, 243, 31, 125, 183, 9, 215]🏠🏠 Ok, có được key[0..6] rồi, chúng ta cứ thế sẽ tính được: pt[16:22] và pt[32:38]
Và đoạn code như sau:
😊😊 Tính pt[16:22]
tmp=''
for i in range(0,7):
tmp=tmp+chr(arr_long[16+i]^key[i])
print(tmp)Và kết quả ta nhận được là:
_h4s_l3😊😊 Tính pt[32:38]
tmp=''
for i in range(0,7):
tmp=tmp+chr(arr_long[32+i]^key[i])
print(tmp)Và kết quả ta nhận được là:
4t10n}?Woa, chúng ta chú ý, như vậy hiện tại chuỗi pt của chúng ta bắt đầu lộ dần, và từ mấu chốt pt[32:38] chúng ta có thể xác định được luôn pt[32:47] = 4t10n}??????????
Woa, pt của chúng ta lúc này như sau:TFCCTF{xxxxxxxxx_h4s_l3xxxxxxxxx4t10n}??????????
☀☀ Ok, và quan trọng là khi đã xác định được pt[32:47] thì rõ ràng chúng ta có thể suy luận ra được kết key[0:15] với thuật toán như sau:
find_key1=b'4t10n}??????????'
key1=[]
for i in range(0,16):
key1.append(arr_long[32+i]^find_key1[i])
print('key[0:15]=',key1)Kết quả ta thu được là:
key[0:15]= [224, 243, 31, 125, 183, 9, 215, 60, 230, 141, 133, 35, 72, 133, 200, 26]🏠🏠 Ok, có key toàn bộ rồi, lúc này công việc còn lại của chúng ta là đi tìm cờ thôi nào !
ct=b''
j=0
for i in range(len(arr_long)):
ct += (key1[j] ^ arr_long[i]).to_bytes(1, 'big')
j += 1
j %= 16
print(ct)Và flag của chúng ta là:
b'TFCCTF{th3_tr41n_h4s_l3ft_th3_st4t10n}??????????'✨✨ Ok, như vậy là ta đã hoàn tất bài toán !