Digital Signatures (Public Key Cryptosystems)
by
I. Utku Moral
Outline
The public key cryptosystems provide sending encrypted messages between two
communicating parties so that they prevent the possible third parties, that
may intrude into the communication link and obtain the transmitted messages,
decoding and interpreting them. These systems also enable the use of digital
signatures. Digital signatures can be considered as the electronic versions of
the handwritten signatures since they feature the same characteristics.
Digital signature can be easily appended to the end of the messages, and
checked by any receiver to verify the authorship. They have also the most basic
characteristic that a signature must have; they are unforgeable.
Consequently, the digital signatures used in the public key cryptosystems
guarantee a perfect authentication as well as the protection of the messages
from intruders.
In a public key cryptosystem, each member of the system has two keys, a public
key and a private key. The public keys are available to everybody in the system
where the private keys are only known by their owners.
Both of these keys are integer numbers. To provide the properties that they
must have they must be such integers that are almost impossible to guess, to
compute or to determine form the public one of the pair. Hence, they are huge
integers with length of around 100 digits. Despite their enormous sizes, they
can be easily created by using RSA method. The main logic behind the digital
signatures is the extreme difficulty of factoring the product of two large
prime numbers. Although there exists some algorithms that can output the prime
factors of its input, if the primes in the factorization are two 100 digit
integers then even the run of the best algorithm on the fastest computer of
todays technology takes years and years. On the other hand, finding such
big arbitrary prime numbers and using them in the creation of the keys is
absolutely easy and can be done in minutes. As a result of these, although the
creation of the private and public keys is not a time consuming process,
determination of the private key by using the public almost lasts forever.
First of all, the public and private keys of a member are encryption
and decryption keys of each other. In other words, a text that is encrypted
with a member's public key can be decrypted with the same person's private key
and vice versa. More specifically
privateX(P) = C and publicX(C) = P , or
publicX(P) = C' and privateX(C') = P ;
i.e.
privateX(publicX(P)) = P and publicX(privateX(P) = P
where P stands for the plain text, C and C' for the crypted texts, and publicX
and privateX are the public and private keys of the member X, respectively.
In the remainder of the text, the expression 'property of the keys' is used for
this property.
Now, let us consider that we have a system of two members, A and B, having
privateA, publicA and privateB, publicB as their private and public keys
respectively.For instance, assume that A wants to send a message, M, to B. To
do that with safety, first A encrypts his/her message in the following way:
publicB(privateA(M)) = C .
Since publicB is available for everybody and privateA is known by A
himself/herself, this encryption can be easily done by A.
When B receives this message in a crypted form, which is represented as C, s/he
follows the procedure below:
publicA(privateB(C)) = M' ,
which only needs the keys publicA and privateB that are known by B. Figure 1
shows this message passing. It uses M instead of M' since their equality is
proved below.
If we consider the entire process done by A and B, then we can write:
M' = publicA(privateB(publicB(privateA(M))))
= publicA(privateB(publicB(D)) { D = privateA(M) }
= publicA(D) { by property of the keys }
= publicA(privateA(M))
= M { by property of the keys }.
As we can see above, the receiver, B, uses the public key of A to decrypt the
crypted messages whose claimed author is A. If the owner of this message is
not A - assuming the private key of A is known only by A - then the resulting
text M' is not equal to M. In such a situation, since C is not decrypted
properly, actually with proper key, the final text M' is a meaningless string
of characters. Hence, this means the claim is false and the authorship of the
message is not verified.
To summarize, in public key cryptosystems, a sender can use his/her private
key as his/her digital signature. Since it is only known by him/her a forgery
of the signature is not possible with todays algorithms. At the other side of
the communication link, the receiver can confirm the authorship of the message
by using the public key of the claimed sender; so the public key provides an
accurate authentication for the receiver. On the other hand, by crypting the
message also with the receivers public key a sender, the sender prevents the
intruders to obtain the message in the plain form. Although the intruders can
know the public key of the sender, they still need the private key of the
receiver to decrypt the overheared message. Hence, as long as the the private
key is private to the receiver the overheared messages do not contain any
meaning for the intruders.
In some public key cryptosystems, some problems may arise in distribution of
the public key to the other members of the system. Use of the 'certificates'
in such cases can solve the problem. For instance, assume that there is
'supervisor', S, in the system whose public key is known by everyone.
When a new member, say A, is accepted to the system s/he gets a
message from S mentioning that 'A's public key is publicA'. This message
becomes the certificate of A. After receiving his/her certificate, A includes
it with his/her signed messages and sends to the other members in the system
(Note that, A only signs its message, not the certificate; but, certainly, the
certificate and A's message, both, are encrypted with receiver's public key
before they are sent). When a member receives that kind of message from A, by
using the public key of S, s/he can decrypt the certificate of A and obtain
the public key of A. Following that the receiver can immidiately verify the
signature of A by using the public key of A; and since this public key
is certified by S whom everybody trusts in the system , the receiver knows
that A's public key is really A's.
[1] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., "Introduction to
Algorithms", McGraw-Hill, 1991, New York, pp:831-837.
[2] Harel, D., "Algorithmics: The Spirit of Computing", Addison-Wesley,
1992, Massachusetts, pp: 325-331.
[3] Kafura, D., "CS5204 Operating Systems: Lecture Notes", Virginia
Tech, Spring 1995, Virginia.