Tags: iroot
Rating:
# iRoot (crypto 300)
###ENG
[PL](#pl-version)
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`:
```python
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`:
```python
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`.
