public key cryptography and digital signature

I read the following from Understanding Public Key Cryptography on Microsoft TechNet:

Using a private key to establish identity shows that the full encryption and decryption operation was accomplished successfully. Showing a full operation means that plaintext would have to be encrypted to ciphertext using a private key and then decrypted back to plaintext using the corresponding public key. If this operation is successfully shown, the use of the private key, and only the private key, is demonstrated.

To show a successful encryption and decryption operation, the plaintext before the encryption and decryption operations must match the plaintext after the encryption and decryption operation. Both sets of plaintext must be compared directly and shown to match absolutely. There must be a control that is used for comparison and validation.

I'm unable to understand what actually is being said here.

Can somebody please explain this in somewhat simpler terms and with a simple example?

migrated from stackoverflow.comOct 23 '11 at 2:16

This question came from our site for professional and enthusiast programmers.

• Welcome to Cryptography Stack Exchange. Your question was migrated here because of being not directly related to software development (the topic of Stack Overflow), and being fully on-topic here. Please register your account here, too, to be able to comment and accept an answer. – Paŭlo Ebermann Oct 23 '11 at 3:33

This text tries to explain how digital signatures work, but it actually is a bit misguiding.

It explains digital signatures based on public-key encryption schemes, but this is only valid for schemes like RSA. And even here, you don't simply encrypt some message with your private key to sign it, but you apply the "decryption" operation (i.e. exponentiation with the private key) on a hash of a message, suitably padded.

In RSA, you have a key pair consisting of private key $(n, d)$ and public key $(n, e)$, where $n$, $d$ are quite big numbers (the size of $n$ relates to the security of the scheme), $e$ usually a smaller number like $2^{16}+1$.

In the "textbook version" (without any padding/hashing), to sign a message $M \leq n$, you calculate $s := M^d \bmod n$, where $\bmod$ is the integer remainder operator. The pair $(M, s)$ is then the signed message. To verify the signature, anyone can calculate $M' := s^e \bmod n$ and then check if $M \mathrel{\overset?=} M'$. Here signing looks like RSA-encrypting with the private key and verifying looks like RSA-decrypting with the public key, which is the reason that the article tries to show it as such.

The real RSA-based signature schemes work a bit different: We apply a one-way hash function $H$ and a semi-random padding $P$ on the message before the exponentiation, so the signature is $s := P(H(M))^d \bmod n$, and this can be checked as $P^{-1}(s^e \bmod n) \mathrel{\overset?=} H(M)$ (where $P^{-1}$ also checks if the padding was really correct). This hashing and padding actually makes the scheme secure against forgeries (and it also allows to sign messages longer than $n$).

There are other signature schemes which do not relate directly to an encryption scheme, for example DSA.

To use a digital signature for authentication (or "identity verification", as the article says), you normally don't sign an arbitrary message, but you sign a piece of data which is somehow relevant to the protocol. For example, in the SSH protocol, at the end of a Diffie-Hellman key exchange, the server signs about everything important which was exchanged, to make sure that there was no man-in-the-middle attack which modified the exchanged data.

What this part is saying in a somewhat formal manner, is that there is a mathematical relationship between a public-private key pair.

A public-key can be associated with a single/specific private key that establishes the owners identity.

This relationship can be proven either by encrypting using the public key and decrypting using the private key OR vice versa.

Additionally these operations MUST not alter the input plaintext in any manner, but after the encrypt/decrypt operations the message entity to be transformed should absolutely match the result of the inverse of the transformation occured from encryption, i.e. the decrypted output.

What the author is trying to explain is how digitial signatures work. Plainly said: The sender of a message hashes the original messages using a hash algorithm (with SHA-1 being a popular one) and then encrypts the hash using his private key. The signature is send along with the message.

The recipient performs the hashing of the message again using the same hash algorithm. Then he decrypts the hash value using the public key of the sender and compares his hash value with the one from the sender. If they are equal, the message was not altered during transmission.