EDITED QUESTION FOR A BETTER EXPLAINATION I have this crypted information (RSA):


and the module used is:


I know also that the RSA decrypted is something like this:


decrypted in this way:

enter image description here

my question is: I don't know the private key used to crypt the data before but I want to change data and encrypt it again, I saw that using the cube root is possible to encode the first 0x2D bytes without losing information, is there any way to encrypt more data?

  • $\begingroup$ 1) public key used to encrypt and private key used to decrypt the message. 2) cube root attack is only valid if $m < \sqrt[3]{n}$. $\endgroup$ – kelalaka Nov 27 '18 at 11:24
  • $\begingroup$ @kelalaka thanks for the reply.. yes..is the same thing I wrote before.. $\endgroup$ – FabioEnne Nov 27 '18 at 11:27
  • $\begingroup$ @fgrieu thanks for the reply...if you read well I signed PK as public key.. $\endgroup$ – FabioEnne Nov 27 '18 at 11:29
  • 1
    $\begingroup$ Are you sure you did not forget to invert the modulus? If the bytes are reversed then the modulus suddenly starts and ends with a bit set to 1, which is currently not the case. $\endgroup$ – Maarten Bodewes Nov 27 '18 at 23:38
  • 1
    $\begingroup$ @fgrieu This very much looks like some kind of puzzle to me, finding the weak spots - such as a badly generated modulus / private key - could be part of the puzzle. $\endgroup$ – Maarten Bodewes Nov 28 '18 at 11:16

The current question and its earlier version have many issues:

  • "The module used" is even (when the given is interpreted as big-endian hexadecimal, which is customary), and therefore is not an RSA moduli. This makes the first two values useless.
  • RSA decryption does not involve computing $x\to x^3\bmod n$, as stated. That operation is involved in RSA encryption and RSA signature verification only.
  • Since the public key $(n,3)$ is public, there is nothing to prevent anyone from doing RSA encryption of anything s/he wants, if it became clear by what method exactly that encryption is to be made ("RSA", or even "RSA encryption", does not define a method precisely).
  • The beginning of the "RSA decrypted" value looks like it is formatted per EMSA-PKCS1-v1_5, a deterministic RSA padding intended for RSA signature with appendix per RSASSA-PKCS1-v1_5, not for encryption.
  • The notion of computing a cube root without the private key is incompatible with any safe use of RSA, including proper RSASSA-PKCS1-v1_5.
  • This OP's comment suggests that signature is involved.

In the end, I agree with this comment: the question really is about signature (protecting integrity and origin of a message) rather than encryption (keeping a message confidential), contrary to the title and body of the question. Wrong terminology strikes again!

The OP seems to be trying to perform a forgery for RSASSA-PKCS1-v1_5 or some unspecified variant thereof. That is, come out with a new message/signature pair that pass verification, without knowledge of a private key or factorization of the public modulus (and, here, without anything holding the private key, nor known-good signatures).

That's believed impossible for proper implementation of RSASSA-PKCS1-v1_5 signature verification, even for low public exponent as in the question. But there are precedents with broken implementations and low public exponent: Daniel Bleichenbacher presented such attack at the rump session of Crypto 2006 (as reported by Hal Finney). There are variations targeting various broken implementations, which used to abound.

The degree of brokenness of the signature verification step is unspecified in the question, thus it can't be told if forgery is possible.

  • 1
    $\begingroup$ He also said the private key was used to "crypt" the data. This is simply a signature scheme using "RSA encryption". The decryption step then becomes the verification step. $\endgroup$ – Maarten Bodewes Nov 27 '18 at 23:02

What you are describing is a PKCS#1 v1.5 signature scheme. The later versions explicitly have a different name for modular exponentiation (raw RSA) for signature generation and encryption. Signature generation does not consist of encryption with the public key. Note that the signature scheme does not seem to use the common DER encoding of the hash over the data, but I would be very surprised if that matters for the security.

Of course it is not possible to update a signature using secure scheme such as PKCS#1 v1.5 padding without knowing the private key. If it were possible then anybody could update a signature and the scheme would have failed. With a private key it is possible to update the data. If the key pair was incorrectly generated then this might be the best way of attacking the signature - if that is feasible at all.

However, I think it is more likely that you forgot to reverse a little endian modulus.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.