picoCTF 2021 Crypto (5) Mini RSA

Mini RSA
| 70 points
Tags:
AUTHOR: SARA

Description
What happens if you have a small exponent? There is a twist though, we padded the plaintext so that (M ** e) is just barely larger than N. Let's decrypt this: ciphertext

# cat ciphertext 
N: 1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
e: 3

ciphertext (c): 1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808154558034707767377524500302754459807923331810585173010977657982069888996945830789092526932364658459034145456505057469113036134559745659079236466119515004648189278227777550415021840140147319061470183840214034417917161940379351273394212022847037696265532968684592354941479799473941357715953204487236888712642494877545201005807776354854390358015733495331101077851132489983665939643188064986446883595239842621440918456201787168234988410659153219277329426230136499096098072681939491840913961290536851217677043565743644469862992310241563891464225935615676242084658617931225618537173689559419607688905143683603007487996422560430269750305079282818976557285786253025774883158125978164878245223052992502106

e=3なので、3乗根を取ればいいはず。
$c \equiv m ^ e (mod \ n)$
$m \equiv c ^{1/e} (mod \ n)$

>>> from gmpy2 import *
>>> c = 1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808154558034707767377524500302754459807923331810585173010977657982069888996945830789092526932364658459034145456505057469113036134559745659079236466119515004648189278227777550415021840140147319061470183840214034417917161940379351273394212022847037696265532968684592354941479799473941357715953204487236888712642494877545201005807776354854390358015733495331101077851132489983665939643188064986446883595239842621440918456201787168234988410659153219277329426230136499096098072681939491840913961290536851217677043565743644469862992310241563891464225935615676242084658617931225618537173689559419607688905143683603007487996422560430269750305079282818976557285786253025774883158125978164878245223052992502106
>>> n = 1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
>>> cbrt(c)
mpfr('1.0685333265243248e+335')
>>> hex(int(cbrt(c)))
'0x1ebab45fa208b60000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'
>>> get_context().precision = 10000
>>> hex(int(cbrt(c)))
'0x1ebab45fa208b5e935ab142514c5ed26a3adfa2d78a734b1de5bf560ecd1e2164321f6a9ced9dd66e9607c02cd04f27c7c12b5a5ebf6c6e3980cd11999628f7d18bcbbf27d5f3c31b9a21bb9db47fdbdecf550feefd23486c3664e0e359c92c8b68d38e5a57be5190f9256fa51680bd79d1365836f0ce1efacfed4ede2ade5c5f0aa52741fbce11f4967b7d'
>>> int(cbrt(c)) ** 3 == n
False

単純に3乗根を取ってもダメ見たい。
$c \equiv m ^ e (mod \ n)$
$c = m ^{e} + k \cdot n$
$c - k \cdot n = m ^{e}$
$m = (c - k \cdot n)^{1/e}$
なので、gmpy2.iroot()を使って、正しい値が取れるまでループさせる。

iroot(...)
iroot(x,n) returns a 2-element tuple (y, b) such that y is the integer n-th root of x and b is True if the root is exact. x must be >= 0 and n must be > 0.

Multiple-precision Integers — gmpy2 2.1.0a1 documentation

※iroot(x, n)は x >= 0じゃないといけないので、kの符号を反転させる。

>>> while True:
...   m, b = iroot(c + k * n, 3)
...   if b == True:
...     break
...   k += 1
... 
>>> k
3533
>>> m
mpz(1787330808968142828287809319332701517353332911736848279839502759158602467824780424488141955644417387373185756944952906538004355347478978500948630620749868180414755933760446136287315896825929319145984883756667607031853695069891380871892213007874933611243319812691520078269033745367443951846845107464675742664639073700704505958478225302653)
>>> from Crypto.Util.number import long_to_bytes
>>> long_to_bytes(m)
b'                                                                                                        picoCTF{e_sh0u1d_b3_lArg3r_aef7377d}'
>>>

" $e$ should be larger"