Imagine we implement RSA padding such that a number of byte zeros are appended to the message until its length is equal to 100 (i.e. 800 bits).

Also, let's assume that the public exponent $e$ is equal to $3$.

How can we break this encryption and find the flag with an approximate size of 150 bits?

Python code for encryption is implemented below.

from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes

flag = b"myflag{a_very_long_flag_is_written_here_with_many_chars}"

def pad(m):
    return m + b'\x00' * (100 - len(m))

key = RSA.generate(1024, e=3)
m = bytes_to_long(pad(flag))
c = pow(m, key.e, key.n)

print(f"e = {key.e}")
print(f"n = {key.n}")
print(f"c = {c}")

And a possible result

e = 3
n = 121093272852844700607509553526921787121889962911469990086240674763527007831445931610394898635953559914236289640814662391916827033328293150498629148607866791309196714798279731781969999612188854037695702368598356696238181576329571780699083311597719535685523585088583041029622133115035189452805449267132314669037
c = 118997582827921095335656050830593701790422781374666251790141811855117179467963374753099989931306799873562201419471821850445048120680741289536557129263492466647328606819668864981583844956072524787465657754032469369844885203438517971541452776224113666392886384116849073492807685359502765750768432203083431246434
  • $\begingroup$ May I ask how the question arises? I'd like to comply with site policy on answering questions like this: crypto.stackexchange.com/help/on-topic $\endgroup$ – Daniel Shiu Mar 25 at 6:50
  • 2
    $\begingroup$ Hint: Can you somehow express this string padding operation "more mathematically"? How does it interact with RSA encryption? $\endgroup$ – SEJPM Mar 25 at 8:50
  • $\begingroup$ @DanielShiu - It's one of the exercises in a cryptography course I'm attending. $\endgroup$ – Ali Mar 25 at 9:00
  • $\begingroup$ With the hint of SEJPM you must be able to solve it. Maybe you need another hint: RSA is multiplicative. What is the size of the flag? $\endgroup$ – kelalaka Mar 25 at 12:03
  • 1
    $\begingroup$ I've got it to work for me. There are a little over 630 bits of padding. $\endgroup$ – Daniel Shiu Mar 25 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.