digital signature non-repudiation issue

Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

Threaded View
I read that, given a message M, a digital signature C_(M) is
sufficient to undisputedly certify that M was written by person/entity
A (where sA is A's secret key with the corresponding public key pA
publicly known, and C is an asymmetric cipher like RSA, parameterized
with the key sA in this case).

However, I wonder how this can be the case, given that C is a total
function (which is true at least for RSA):

Doesn't that mean that anyone could choose a random X =: C_(M),
then calculate M = C_(X), and then publish both M and X and
falsely claim that M was created by A?

(it may be difficult to choose X such that you get a meaningful M,
i.e. one that doesn't just look like a bunch of random bits, but

What do you make of that?

Olaf Klischat            | TU Berlin       computer science
Roedernallee 168         |
13407 Berlin, Germany    |
phone: +49 176 24214061  | e-mail:

Re: digital signature non-repudiation issue

Olaf Klischat wrote:

Quoted text here. Click to load it

Not news!

All public key cryptographic systems depend on things that are easy to
compute one way, but take a time that is exponential on the size of the
problem, to solve the other way.  The trick is to keep key lengths long
enough that brute force will attacks will not complete in time to be useful.

Any finite key length private key system depends on the complexity of
searching the key space, in real life, where you have some idea of what
the encrypted message means.  That was partly why Bletchely Park was so
successful; they developed machines that could try all possibilities so
much faster than the Germans assumed possible (although there was also
some good maths to simplify the problem).

Site Timeline