###ENG PL
In the task we get RSA parameters:
c = 2044619806634581710230401748541393297937319
n = 92164540447138944597127069158431585971338721360079328713704210939368383094265948407248342716209676429509660101179587761913570951794712775006017595393099131542462929920832865544705879355440749903797967940767833598657143883346150948256232023103001435628434505839331854097791025034667912357133996133877280328143
The unusual thing is that public exponent is not given and that c is very small compared to n.
This suggests that maybe e was so small that m^e did not exceed n, or did it only very slightly.
We check this by simply computing k-th integer root for c to see if maybe we can find e:
import gmpy2
from src.crypto_commons.generic import long_to_bytes
def main():
c = 2044619806634581710230401748541393297937319
n = 92164540447138944597127069158431585971338721360079328713704210939368383094265948407248342716209676429509660101179587761913570951794712775006017595393099131542462929920832865544705879355440749903797967940767833598657143883346150948256232023103001435628434505839331854097791025034667912357133996133877280328143
for i in range(2, 10):
root = gmpy2.iroot(c, i)[0]
if root**i == c:
print(i, long_to_bytes(root))
main()And we were right - we get info that e = 3 and message is so_low.
###PL version
W zadaniu dostajemy parametry RSA: In the task we get RSA parameters:
c = 2044619806634581710230401748541393297937319
n = 92164540447138944597127069158431585971338721360079328713704210939368383094265948407248342716209676429509660101179587761913570951794712775006017595393099131542462929920832865544705879355440749903797967940767833598657143883346150948256232023103001435628434505839331854097791025034667912357133996133877280328143
Nietypowa rzecz jest taka, ze wykładnik szyfrujący nie jest podany i c jest bardzo małe w porównaniu do n.
To sugeruje że może e było tak małe że m^e nie przekroczyło n, albo tylko nieznacznie.
Żeby to sprawdzić postanowiliśmy policzyć k-te pierwiastki całkowite dla c w poszukiwaniu e:
import gmpy2
from src.crypto_commons.generic import long_to_bytes
def main():
c = 2044619806634581710230401748541393297937319
n = 92164540447138944597127069158431585971338721360079328713704210939368383094265948407248342716209676429509660101179587761913570951794712775006017595393099131542462929920832865544705879355440749903797967940767833598657143883346150948256232023103001435628434505839331854097791025034667912357133996133877280328143
for i in range(2, 10):
root = gmpy2.iroot(c, i)[0]
if root**i == c:
print(i, long_to_bytes(root))
main()I mieliśmy racje - dostaliśmy informacje że e = 3 a flaga to so_low.