# Does digital signature really ensure data integrity?

Suppose attacker knows public-key of sender. He can make his own private key derived from public-key of sender. Then he can alter message and sign it with his private key.

Probably I'm missing the point but I can't find explanation anywhere. Please, help.

• What do you mean by "...make his own private key derived from public-key of the sender"? In which sense is that "derivation" to be understood? May 15 '16 at 12:06
• If you come up with a way to derive the private key from a public key, let me know. May 15 '16 at 12:22
• Even though this question is incredibly basic and the fault in the logic is glaringly obvious, I would suggest it doesn't get downvoted because there are no bad questions - only duplicates and spam - and i'm sure there are many on the wider SE network who might benefit.
– J.J
May 15 '16 at 12:25
• Sorry guys, I totally forgot that for making private key attacker needs to know phi(n) value to derive {n, d} pair in RSA... May 15 '16 at 13:08
• actually a digest is an "integrity keeper"... Signature is for verification/authenticity May 15 '16 at 13:47

Assuming the cryptographic algorithm is strong and the key used does not have any weakness, the attacker will NOT be able to generate the corresponding private key from a public key. That is the whole point of Public Key Cryptosystems.

The attacker would usually be needed to solve a computationally impossible problem in finite time (Factorize a huge number in case of RSA or solve discrete logarithm problem in case of ElGamal) to generate the private key just from the public key.

So, the attacker will not be able to forge any signatures unless and until she does, what is described above.

He can make his own private key derived from public-key of sender.

No, he cannot. At least unless the crypto (or implementation thereof) is horrifyingly bad in some way.

Public key cryptography as used today is generally based on one of two mathematical problems. For example RSA relies on the difficulty of factoring the product of two large prime numbers (select two primes p and q, calculate and publish n = pq but keep p and q secret; then, given n, find p and q to match), and for example ElGamal relies on the discrete logarithm problem (select b, k and n, calculate g = b^k mod n, publish b, g and n but keep k secret; then given b, g and n, find k to match).

There is a lot more than this to practical and secure public key cryptography, but those are the problems generally relied on to provide confidentiality of the private key. (Confidentiality of the private key, in turn, allows making guarantees about such things as confidentiality and non-repudiation of data.)

If the numbers involved are sufficiently large, there is no currently publicly known, practical way to solve these problems in reasonable amounts of time. They function as a sort of trap door: it's easy to do the calculation in one direction, but impossible in practice to reverse the calculation.

If it becomes possible to solve these types of problems in reasonable amounts of time, then many of our current real-world public-key-based cryptosystems fall apart. There is concern that, if they turn out to be practical, quantum computers could allow quick breaking of many of our current real-world public-key cryptosystems; as a result, there is currently discussion in the cryptographic community on what has been termed post-quantum cryptography.

Note that the above applies only to public-key (asymmetric, different keys used for encryption and decryption) cryptography. Private-key (symmetric, a single key used for both encryption and decryption) cryptography, such as DES or AES, generally does not rely on either integer factorization or the discrete logarithm problem for their security, and as such are not affected by this. There are some issues with symmetric encryption algorithms as well, but those are fairly easily mitigated simply by doubling the key length or hash output length.

That depends on what you mean by "really". ​ A computationally-unbounded adversary
can break all digital signature schemes, along with most other cryptography too.
However, there's not publicly known to be a feasible classical algorithm with a
non-negligible probability of finding a compatible private key for an inputted RSA public key,
and one can build other signature algorithms for which there's not publicly known to
even be a feasible quantum algorithm with a non-negligible SUF-CMA advantage.

(You might be interested in Fail-Stop Signatures, although there are lots of
references to proving forgery when the only thing being proven is a break,
since property #4 can only hold against computationally-bounded signers.)