# Cyber Grabs CTF 0x03 Junior - FlagPoisoning
https://flag-poisoning.fr/
## Challenge - Unbr34k4bl3 - 942 points - 7 solves
> No one can break my rsa encryption, prove me wrong !!
>
> Flag Format: cybergrabs{}
>
> Author: Mritunjya
>
> output.txt source.py
Here the content of the output.txt
```
n:267362205744654830055585746250317245125479735269853713372687604676608285629127977574310510441358104169652444917329986129098240750401425257601282268733834091593200445244725460613298199140690597119199763970064359847666802255456013592631532853951273286284878230893809080250386646832110506402289378691079462364884899662707502858007857457806853302449695351229004051902617728418480990341155900565542195318206284041182555579388392863474548687784403795738945489219689610881075059037192656116884269582257788959555951074322245033492165406470004019896763472332962300128378758934128374039937693688718317737657946435827745981009467876838127075176808098467305627394472135213533754815713468369763665632168616054982745256773112537152292099369137072982289095951236065885648588670059655452986720063260146952425798150221407866669449837430999779776718047668562687216933053536759554900663226163021145439386115076821161003965334731127329486856711654741683760749336235855319144478194501034662638054193682000283319917096796971
ip:65491313526527942082900846848440586365393305192439699810712229312474732937502934334921061033822729150056656630858908294464249602368303871630644420585085642204592189073314730233318796675949142968346807766087775542461078648703191450221286915401606901781524237580646760734493950360267230729125514156671619347616
iq:97034409222811998555255396847918439343239825222504093225438959283117395075159811973044380473862026342866489725039905931430797650466599952795602909181290621103197493223080488468216279214006070950393096075839913101687588555346523517436421698916141195686143520143972735534402754157166545851899187305574703394138
c1:103687839591259628532585171241634220321003599759860095236990117623065664975385083122971507015385215246948744078816596026772744294701233346732383214113445480056584639282712898073542520168025667980980057512174927564196375256682206601425714094930670415979638437119896258396784978194294581076901000507291277729888015413204446158926865037965291316577726275211006619643531704449499845352147547986667837681877488120093302675775792115380914560935989896453159186176952126083066619414338359303033325593504442257083571002878083287293828310810483726711816109297046925744157605591270761804522735216774801135342322479770391505911100485259078064775709124730966391629468398187269096529671187877954443617005248499140455160589093379715757808387108825458007733207099871941497372539249357162437077379731766825184301649010270921003130776410066972952756983157217280397531412843118202051922048479332111760976091302376602674590153876045380552746826056547929265785960676415919260117136285580971488670143947003566230254837742519
c2:171159809874438596904787534111610260851529969068192878049771299710688449419966698428704180474774734112617652498954998301185232279153644173070897800123538474930545720934844727376637921072749901149514789723141795042182408704214998390482343965532559149095934231081729041402598776401575561653660624208366051273601230345754361771067242657825194926706328336322383296953817730346429591680463526267530372572332663327157636745578067246913529155120642276894180354494816411827468256127607558873938451944866168777913756913920336763454881108023708284527878322162463081091624350220308273550298342755582044860337692076513609120342318151660103532559583052954725303030103413034880155621982581677423267299780543045375467310718078800411397780269409147558121862038983169509828944551199620508493589091401498720419409158373805529997911655270528589050795214164221299581104149954423726171539700223299445034347915430838395255700425648686205603925507474877720680274914513203566997846945579395522000899007446797091893230195801607
```
Here the content of source.py
```python=
from Crypto.Util.number import *
from secret import *
assert (x>2 and x%2 == 0)
assert (isPrime(e1) and isPrime(e2))
def functor():
val1 , val2 = 0,0
for i in range(x+1):
val1 += pow(e1,i)
for j in range(3):
val2 += pow(e2,j)
assert (val1 == val2)
def keygen():
while True:
p,q = [getStrongPrime(1024) for _ in range(2)]
if p%4==3 and q%4==3:
break
r = 2
while True:
r = r*x
if r.bit_length()>1024 and isPrime(r-1):
r = r-1
break
return p,q,r
functor()
p,q,r = keygen()
n = p*q*r
print(f"p:{p}")
print(f"q:{q}")
ip = inverse(p,q)
iq = inverse(q,p)
c1 = pow(bytes_to_long(flag[0:len(flag)//2].encode('utf-8')),e1,n)
c2 = pow(bytes_to_long(flag[len(flag)//2:].encode('utf-8')),e2,n)
print(f"n:{n}",f"ip:{ip}",f"iq:{iq}",f"c1:{c1}",f"c2:{c2}",sep="\n")
```
For solving this challenge, two ressources have been used:
* Factoring pq with https://ctftime.org/writeup/16770
* H-Rabin cryptosystem - Hayder Raheem Hashim / Journal of Mathematics and Statistics 10 (3): 304-308, 2014
and here the full and commented solution:
```python=
from Crypto.Util.number import *
from sympy import Symbol,Eq,solve
from sympy.crypto.crypto import rsa_private_key
# Challenge Data
n=267362205744654830055585746250317245125479735269853713372687604676608285629127977574310510441358104169652444917329986129098240750401425257601282268733834091593200445244725460613298199140690597119199763970064359847666802255456013592631532853951273286284878230893809080250386646832110506402289378691079462364884899662707502858007857457806853302449695351229004051902617728418480990341155900565542195318206284041182555579388392863474548687784403795738945489219689610881075059037192656116884269582257788959555951074322245033492165406470004019896763472332962300128378758934128374039937693688718317737657946435827745981009467876838127075176808098467305627394472135213533754815713468369763665632168616054982745256773112537152292099369137072982289095951236065885648588670059655452986720063260146952425798150221407866669449837430999779776718047668562687216933053536759554900663226163021145439386115076821161003965334731127329486856711654741683760749336235855319144478194501034662638054193682000283319917096796971
ip=65491313526527942082900846848440586365393305192439699810712229312474732937502934334921061033822729150056656630858908294464249602368303871630644420585085642204592189073314730233318796675949142968346807766087775542461078648703191450221286915401606901781524237580646760734493950360267230729125514156671619347616
iq=97034409222811998555255396847918439343239825222504093225438959283117395075159811973044380473862026342866489725039905931430797650466599952795602909181290621103197493223080488468216279214006070950393096075839913101687588555346523517436421698916141195686143520143972735534402754157166545851899187305574703394138
c1=103687839591259628532585171241634220321003599759860095236990117623065664975385083122971507015385215246948744078816596026772744294701233346732383214113445480056584639282712898073542520168025667980980057512174927564196375256682206601425714094930670415979638437119896258396784978194294581076901000507291277729888015413204446158926865037965291316577726275211006619643531704449499845352147547986667837681877488120093302675775792115380914560935989896453159186176952126083066619414338359303033325593504442257083571002878083287293828310810483726711816109297046925744157605591270761804522735216774801135342322479770391505911100485259078064775709124730966391629468398187269096529671187877954443617005248499140455160589093379715757808387108825458007733207099871941497372539249357162437077379731766825184301649010270921003130776410066972952756983157217280397531412843118202051922048479332111760976091302376602674590153876045380552746826056547929265785960676415919260117136285580971488670143947003566230254837742519
c2=171159809874438596904787534111610260851529969068192878049771299710688449419966698428704180474774734112617652498954998301185232279153644173070897800123538474930545720934844727376637921072749901149514789723141795042182408704214998390482343965532559149095934231081729041402598776401575561653660624208366051273601230345754361771067242657825194926706328336322383296953817730346429591680463526267530372572332663327157636745578067246913529155120642276894180354494816411827468256127607558873938451944866168777913756913920336763454881108023708284527878322162463081091624350220308273550298342755582044860337692076513609120342318151660103532559583052954725303030103413034880155621982581677423267299780543045375467310718078800411397780269409147558121862038983169509828944551199620508493589091401498720419409158373805529997911655270528589050795214164221299581104149954423726171539700223299445034347915430838395255700425648686205603925507474877720680274914513203566997846945579395522000899007446797091893230195801607
# n = p*q*r
print("[+] n = p * q * r ")
# Step One finding x
print("[+] Finding r ...")
r = 2
x = 2
while True:
r = pow(2,x)
if r.bit_length()>1024 and isPrime(r-1) and n % (r-1) == 0:
r = r-1
break
x+=1
# Sanity Check for x
print("[-] Guessing x = 4")
x = 4
# r prime
print("r =",r)
# pq
print("[+] pq found ...")
pq = n //r
print("pq = ",pq)
# Sanity check for pq
assert n == pq * r
# Finding e1 and e2
for e1 in range(2,10):
for e2 in range(2,10):
if (pow(e1,x+1)-1) // (e1-1) == (pow(e2,3)-1)// (e2-1):
_e1=e1
_e2=e2
break
e1=_e1
e2=_e2
print("[+] e1 = ",e1)
print("[+] e2 = ",e2)
# Factoring p*q
print("[+] Factoring pq with https://ctftime.org/writeup/16770")
p=Symbol('p')
q=Symbol('q')
equation1 = Eq(ip*p+iq*q-pq-1,0)
equation2 = Eq(p*q-pq,0)
solution = solve((equation1,equation2),(p,q))
for p,q in solution:
if pq %p == 0:
p=int(p)
q=int(q)
break
print("p = ",p)
print("q = ",q)
# H-Rabin
print("[+] Solving H-Rabin cryptosystem")
print("[+] Hayder Raheem Hashim / Journal of Mathematics and Statistics 10 (3): 304-308, 2014")
mp = pow(c1,(p+1)//4,p)
mq = pow(c1,(q+1)//4,q)
mr = pow(c1,(r+1)//4,r)
_mp = -mp % p
_mq = -mq % q
_mr = -mr % r
b1 = pow((q*r ) % p,-1,p)*1
b2 = pow((p*r ) % q,-1,q)*1
b3 = pow((p*q ) % r,-1,r)*1
x1 = (mp*b1*(q*r)+mq*b2*p*r +mr*b3*p*q)%(p*q*r)
x2 = (_mp*b1*(q*r)+mq*b2*p*r +mr*b3*p*q)%(p*q*r)
x3 = (mp*b1*(q*r)+_mq*b2*p*r +mr*b3*p*q)%(p*q*r)
x4 = (mp*b1*(q*r)+mq*b2*p*r +_mr*b3*p*q)%(p*q*r)
x5 = p*q*r-x1
x6 = p*q*r-x2
x7 = p*q*r-x3
x8 = p*q*r-x4
#print(long_to_bytes(x1))
print("[-] After looking at all values, we keep only the second one ...")
print(long_to_bytes(x2))
#print(long_to_bytes(x3))
#print(long_to_bytes(x4))
#print(long_to_bytes(x5))
#print(long_to_bytes(x6))
#print(long_to_bytes(x7))
#print(long_to_bytes(x8))
print("[+] Multi-prime rsa")
primes=[p,q,r]
args = primes+[e2]
d=rsa_private_key(*args)[1]
pt=long_to_bytes(pow(c2,d,n))
print(pt)
```
**cybergrabs{r481n_cryp70sy5t3m_15_1nt3r35t1n6_8ut_num83r_sy5t3m_15_3v3n_m0r3_1nt3r35t1n6}**
That's all Electro !
# Cyber Grabs CTF 0x03 Junior - FlagPoisoning
## Challenge - Unbr34k4bl3 - 942 points - 7 solves
> No one can break my rsa encryption, prove me wrong !!
>
> Flag Format: cybergrabs{}
>
> Author: Mritunjya
>
> output.txt source.py
# Cyber Grabs CTF 0x03 Junior - FlagPoisoning
## Challenge - Unbr34k4bl3 - 942 points - 7 solves
> No one can break my rsa encryption, prove me wrong !!
>
> Flag Format: cybergrabs{}
>
> Author: Mritunjya
>
> output.txt source.py
## Challenge - t0t13nt - 29 Solves
> numbers numbers everywhere , why cant they leave me alone
>
> Flag Format: cybergrabs{}
>
> Author: Mritunjya
>
> output_1.txt source_1.py
Here the content of the output_1.txt
```
[54751499983812600001595164999947606, 99964672809872376546137976728298625, 53109066146380481534971079770844564, 58137259942365444979479997549034855, 83599752542227961885740894770768516, 61659800043905527133538302215438384, 83599752542227961885740894770768516, 51499811650564080459894297372806965, 53109066146380481534971079770844564, 85819100646121058196943447618203070, 105003982813844976161353898313196914, 8400749730877624158255771399988559, 6240424741484609266392009977454864, 73075186383278314052649120872243371, 7485157899144949411682111055590430, 48379486424936974614387887472243260, 59881263192906899425738121667861480, 90374940243693329303922258576171375, 75104938249367345681206971604866080, 54751499983812600001595164999947606, 9388117281207654321254731172830840, 6638633268326718341544242944266781, 6240424741484609266392009977454864, 75104938249367345681206971604866080, 32264483340980969722020637386275054, 48379486424936974614387887472243260, 75104938249367345681206971604866080, 7485157899144949411682111055590430, 92712108866793232034695893485547544, 7485157899144949411682111055590430, 83599752542227961885740894770768516, 48379486424936974614387887472243260, 54751499983812600001595164999947606, 7485157899144949411682111055590430, 15496388930720047282261773301643045, 8400749730877624158255771399988559, 58137259942365444979479997549034855, 48379486424936974614387887472243260, 88077383691706059347171006086863620, 6240424741484609266392009977454864, 48379486424936974614387887472243260, 7934151132541799341665122998944580, 73075186383278314052649120872243371, 7934151132541799341665122998944580, 102463675364526450047988025312160540, 7485157899144949411682111055590430, 48379486424936974614387887472243260, 73075186383278314052649120872243371, 7485157899144949411682111055590430, 110209866655316842092627871164477875]
```
Here the content of source_1.py
```python=
from sympy import totient
from tqdm import *
flag = "REDACTED"
def functor(n):
val = 0
for j in tqdm(range(1,n+1)):
for i in range(1,j+1):
val += j//i * totient(i)
print(val,j//i,j,i,totient(i))
return val
lest = []
for i in flag:
print(i)
lest.append(functor(ord(i)*6969696969))
print(lest)
```
We solved the challenge in an unintended way, using a plaintext attack ...
The following code is self-explaining !
```python=
import string
# Challenge's data
ct = [54751499983812600001595164999947606, 99964672809872376546137976728298625, 53109066146380481534971079770844564, 58137259942365444979479997549034855, 83599752542227961885740894770768516, 61659800043905527133538302215438384, 83599752542227961885740894770768516, 51499811650564080459894297372806965, 53109066146380481534971079770844564, 85819100646121058196943447618203070, 105003982813844976161353898313196914, 8400749730877624158255771399988559, 6240424741484609266392009977454864, 73075186383278314052649120872243371, 7485157899144949411682111055590430, 48379486424936974614387887472243260, 59881263192906899425738121667861480, 90374940243693329303922258576171375, 75104938249367345681206971604866080, 54751499983812600001595164999947606, 9388117281207654321254731172830840, 6638633268326718341544242944266781, 6240424741484609266392009977454864, 75104938249367345681206971604866080, 32264483340980969722020637386275054, 48379486424936974614387887472243260, 75104938249367345681206971604866080, 7485157899144949411682111055590430, 92712108866793232034695893485547544, 7485157899144949411682111055590430, 83599752542227961885740894770768516, 48379486424936974614387887472243260, 54751499983812600001595164999947606, 7485157899144949411682111055590430, 15496388930720047282261773301643045, 8400749730877624158255771399988559, 58137259942365444979479997549034855, 48379486424936974614387887472243260, 88077383691706059347171006086863620, 6240424741484609266392009977454864, 48379486424936974614387887472243260, 7934151132541799341665122998944580, 73075186383278314052649120872243371, 7934151132541799341665122998944580, 102463675364526450047988025312160540, 7485157899144949411682111055590430, 48379486424936974614387887472243260, 73075186383278314052649120872243371, 7485157899144949411682111055590430, 110209866655316842092627871164477875]
# Flag decoder function
def decoder(ct,guess):
for elt in ct:
_ = str(elt)
if _ in guess.keys():
print(guess[_],end="")
else:
print("-",end="")
print("\n")
# Flag guessing support function
def guesser(ct,guess):
pt =[]
pt.extend(ct)
pt.sort()
for elt in pt:
if str(elt) in guess.keys():
print(elt,guess[str(elt)])
else:
print(elt)
# Clean solve
print("\n[+] Intended solution, sum_1_n (n//k)*phi(k)= n(n+1)/2 and sum of tringular number, from discord")
for elt in ct:
for char in string.printable:
n = ord(char)*6969696969
res = n*(n+1)*(n+2)//6
if res == elt:
print(char,end="")
break
print("\n")
print("[+] Unintended solution, cryptogaphic solving with known plaintext attack...")
print("[+] Assuming the flag format is cybergrabs{some_l337_words}")
guess = {
"54751499983812600001595164999947606": "c",
"99964672809872376546137976728298625": "y",
"53109066146380481534971079770844564": "b",
"58137259942365444979479997549034855": "e",
"83599752542227961885740894770768516": "r",
"61659800043905527133538302215438384": "g",
"51499811650564080459894297372806965": "a",
"85819100646121058196943447618203070": "s",
"105003982813844976161353898313196914": "{",
"110209866655316842092627871164477875": "}"
}
decoder(ct,guess)
print("[+] After monitoring of functor(), functor() is an increasing function ...")
print("[+] Therefore ord('a') < ord('b') ==> functor(ord('a')) < functor(ord('b'))")
print()
steps = [
("59881263192906899425738121667861480","f","Bound by 'e' and 'g'"),
("102463675364526450047988025312160540","z","Bound by 'y' and '}'"),
("48379486424936974614387887472243260","_","Just below 'a', as per ascii table"),
("88077383691706059347171006086863620","t","Just after 's'"),
("90374940243693329303922258576171375","u","Just after 't'"),
("92712108866793232034695893485547544","v","Just after 'u'"),
("75104938249367345681206971604866080","n","because the flag show fu-c"),
("73075186383278314052649120872243371","m","Just below 'n'"),
("7485157899144949411682111055590430","3","1337 speaks for matching 'e'"),
("6240424741484609266392009977454864","0","133t speak for matching 'o' in 'to'"),
("6638633268326718341544242944266781","1","Just after '0'"),
("7934151132541799341665122998944580","4","Just after '3'"),
("8400749730877624158255771399988559","5","Just after '4'"),
("9388117281207654321254731172830840","7","Just after '5'"),
("15496388930720047282261773301643045","A","To make cease"),
("32264483340980969722020637386275054","S","to make functions")
]
for a,b,c in steps:
print("-"*32)
print("[+] Sorting ciphered element ...")
guesser(ct,guess)
print("[+] Guessed ", a , " is ", b , " because ", c )
guess[str(a)]=b
decoder(ct,guess)
input("Show next guess ...")
```
That's all folks - Electro !