Rating:
Problem Statement(600 points):
The more primes, the safer.. right.?.? Connect with nc 2018shell2.picoctf.com 54915.
Solution:
It is a question of multi prime rsa.IF i get all the factors of n we can easily get d.
I was given the following :
n=7735208939848985079680614633581782274371148157293352904905313315409418467322726702848189532721490121708517697848255948254656192793679424796954743649810878292688507385952920229483776389922650388739975072587660866986603080986980359219525111589659191172937047869008331982383695605801970189336227832715706317
c=3670299277793632058702793297897750202390028862083121193154786454442747778012608037319074059849513143614838290370386310449245926313963594388615873818138122198638842317775671383243272790384729363089911073734180421303462368643415811401399803824480651005886180614400113872470469554939994288906399951020543977
e=65537
I found all the factors on https://factordb.com/ and then wrote the python script( here)
In normal RSA d=modInv(e,pXq)
But in multiprime RSA suppose n has 5 factors a,b,c,d
so accordingly d will be :
d=modInv(e,(a-1)*(b-1)*(c-1)*(d-1))
hexadecimal message=pow(c,d,n)
so i the output of my python script resulted :
7069636f4354467b705f265f715f6e305f725f245f7421215f333632303736327d
Converted to string :
The Flag is : picoCTF{p_&_q_n0_r_$_t!!_3620762}
