Since my last post I've been more interested into RSA cryptography, but I'm questioning one thing.

Lets say we are using standard textbook RSA with no padding and with the standard signature generation in lets say the Microsoft crypto API and you got the part you want to remove by itself is it possible to remove that from another signature with the same thing on the beginning or end?

  • $\begingroup$ Can you be more specific? $\endgroup$ Dec 5 '17 at 16:06
  • $\begingroup$ @SqueamishOssifrage Lets say you have m1 which is a separate signature from m2 but m2 contains the message of m1 with some more stuff before-hand, as you know you can combine two signatures because of the multiplicative property. but lets say you have m1 at the end of m2 is it possible to remove that same message of m1 at the end of m2? $\endgroup$ Dec 5 '17 at 16:26

As soon as you are working using standard textbook RSA without padding (or hashing), you can fully exploit the malleability of the RSA cipher.

So, let's say you have a message $m$ which is equal to $a\cdot b$, for $a,b$ two values you know. If you can get the signer to sign both $a$ and $b$, you can compute the value of the signature of $m$, thanks to that malleability: $$m^d = (a\cdot b)^d = a^db^d \mod N$$

Now regarding the possibility to "cancel out a factor" thanks to this malleability, it is partly possible and is actually used in the so-called "blind RSA signatures". (Read it, it explains all the maths.)
However it requires to be able to get the signer to sign a specially crafted message.

  • $\begingroup$ I think I understand it so far, I'm new to all this rsa stuff still but it mostly makes sense, anyways thanks this will be the accepted answer. $\endgroup$ Dec 5 '17 at 18:01

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.