This essay is an under-the-hood background piece on how digital signatures work. It is not a how to on what tools to use to sign and verify files.

Digital signatures allow you be confident a file or program came from the author claimed, and that the file has not been tampered with. There are various schemes in widespread use: X.509 v3 certificates, Microsoft’s Authenticode ActiveX unforgeable signatures, Microsoft’s J++ cab files, PGP (Pretty Good Privacy) signing, RSA, Lucent and Java’s signed Applets.

In Java, you may relax some of the usual security constraints you would place on wild Applets you randomly encounter surfing the web. For example, you might allow a trusted Applet to write to your local hard disk. Just because a program is digitally signed is no guarantee it is bug free or harmless. It is not rocket science to sign a file. See Daniel Griscom’s FAQ or Ted Landry’s FAQ on how to do it.

This essay will give you a broad overview of how digital signatures work, partly to give you some confidence in them and partly to show you why they are not 100% secure. This essay tends to get a bit too much into the details of why they are secure. I suggest you read the sections in the Java & Internet Glossary on certificates, PGP, and X.509 v3 before tackling this.

A digitally signed file or message may or may not be encrypted itself. The signature is just an appendage that cannot be forged. The appendage ensures the file has itself has not been changed, and that it came from who it was claimed to be from.

Trapdoors

1. Given an arbitrary bitstream x, p(s(x))==x and s(p(x))==x.

   That is just the way mathematicians say that you must have a way to encrypt and decrypt to get precisely back to where you started. You must both be able to encrypt with a secret key and decrypt with a public one and also to encrypt with a public key and decrypt with a secret one.

2. Knowing the public key P does not permit you to derive the secret key S in any reasonable way. However, knowing S permits you to easily derive P.

It is pretty simple with modern computers to find two arbitrary and very large prime numbers. It is trivially easy to multiply them together yielding a composite number. It is grossly difficult to take the resulting huge composite number and to factor it, yielding the two original prime numbers. Thus the public key P is isomorphic to the composite number and the secret key S is isomorphic to the two primes. In fact, one of RSA’s patented ciphers is based on exactly this, and it’s the one used for signature verification.

Certifying Authority

They come in various flavours and costs, depending on how much checking they do on you, and what you intend to use them for e.g. signing files for Internet Explorer, Netscape, Solaris, email, or posting to newsgroups. (The public key PC has to be built into the browser/whatever when you receive it; this is the point of biggest risk, but only to the degree that like any native program you have to be careful where you get it. But if I download the browser from Microsoft’s web site or from Netscape’s web site, the risk is very low that I’m actually getting a phony version with a bogus path and key for the certification authority. It would require someone to get into the DNS database (the database used to convert web domain names to dotted quad numerical addresses) and redirect accesses intended for Microsoft/Netscape to some other web site which looked enough like MS’s or Netscape’s to fool you-- and for it never to be discovered and publicized afterwards. I consider that risk to be vanishingly small. Redirection at the DNS is conceivable [it’s happened] but I don’t believe it would not be noticed. The guy who did this is currently being prosecuted.

When an Applet is created, the vendor creates a secret key SV and a public key PV. A large checksum c (something like a 128-bit CRC) gets calculated for the Applet, and it is then enciphered using the secret cipher sv(c) yielding a bit stream c' which anyone can decipher using pv(c') to yield again the CRC c. This is only true if they have the ability to get the correct public key PV and know it’s right.

How A Digital Signature Lets You run an Applet

1. The user’s browser downloads the Applet, including the enciphered checksum c' and a vendor ident value.
2. The user’s browser contacts a certification authority for which PC (the certification authority’s public key) is known. The user’s browser requests a copy of the info packet for that vendor ident. In a less secure system, this step may be bypassed. The factory-supplied information in the browser is trusted as up to date.
3. The certification authority sends the info packet back, enciphered using sc().
4. The user’s browser deciphers the info packet using pc() and thus knows that the info packet was not forged. All information in it is as trusted as the certification authority is.
5. Part of the info packet is the true name of the vendor, who registered with the certification authority. Part is his public key PV.
6. The user’s browser calculates the same checksum that the vendor was supposed to calculate.
7. The user’s browser deciphers the enciphered checksum which was included with the file, using PV gotten from the certification authority.
8. If they do not match, the file is corrupt and will not be run.
9. If they do match, the user is prompted with the true identity of the vendor (as sent by the certification authority) and asked whether the vendor is trusted.
10. If the user says yes, then the app is run.

Passwords: Establishing Identity

Diffie-Hellman

Certification Authority’s Security Measures

If you register and then deliberately distribute a harmful program, it won’t take long for someone to connect their grief with your app. Word will get back to the certifying authority who will do two things:

1. They’ll instantly stop certifying you, which means that thereafter anyone trying to load your app will fail. (In the process above, step 4 becomes a "Nyet" response, and the process stops.)
2. They’ll try to verify the failure, and then will contact the proper authorities. And you won’t be able to plead innocent, either, because it will be possible to prove mathematically that the harmful feature was in your app when it left your hands!

Hacking To Defeat the System

So how about stealthily making your harmful app look like it came from someone else? In other words, change the app, recalculate the checksum but set the ident to someone else’s. Well, that requires that you have their SV, the secret key of the vendor you’re trying to mimic. All you have to do is break his cipher. That’s all. Easy, right?

Huh-uh. lots of work, and maybe not practical in any reasonable time period. When RSA originally issued the prime/composite cipher, they published a message in it and offered a prize for anyone who could crack it.

Someone eventually did — one of those "swarms of hobbyists working across the net" efforts. But that particular cipher only used prime numbers with less than 70 digits. The problem is a lot bigger when the primes are 130 digit or 150-digit. (Remember that the problem is not twice as big with 140 digit primes, it’s at least 10^70th times bigger.) It would be essentially impossible to use this kind of approach without word getting out, and your success (assuming you succeeded) would be very fragile because the vendor you’re trying to mimic could choose a new key and recertify in a day or two. Why spend years rounding up support to crack a cipher which can be changed in 24 hours?

In fact, espionage is the only really practical solution if you’re bound to create mischief. It’s a lot easier to steal the key than to get it by brute force. And espionage is definitely not easy, and again the success would be very fragile since it would be so easy to change the key.

Keep in mind that a file being signed, by itself, proves nothing (e.g. the PGP trailer you see on some newsgroup posts). Some evil person could get the original file, modify it, re-checksum it and re-sign it with a different digital signature and pass it off as the original. The recipient would be none the wiser unless he checked the digital signature against the one expected from that author. The recipient either must have requested that expected key directly from the author in some secure way, or from the certifying authority over the insecure Internet, using the certifying authority’s digital signature to prevent tampering.

The Catch

Digital Signatures and Postage Stamps

Summary

• commerce, sending secure financial transactions.
• high integrity against transmission errors.
• digitally dating legal documents (certifying authority adds a digitally signed appendage with the date).
• creating tamper-proof digital copies of legal documents (both parties digitally sign).
• encryption to prevent the contents of documents from being spied upon. Encryption keys for a session can be exchanged. They are encrypted with the public key of the recipient and decrypted with the secret key. Digital signatures are too slow for routinely encrypting entire files.
• proving your authorship in email and public posts.

	recommend book⇒Web Security & Commerce
		paperback
	ISBN10:	1-56592-269-7
	ISBN13:	978-1-56592-269-3
	publisher:	O’Reilly
	published:	1997-06-01
	by:	Simson Garfinkle and Gene Spafford
Good for overview, not practical detail. The shark book.
amazon.ca amazon.com chapters.indigo.ca powells.com amazon.fr barnesandnoble.com amazon.de O’Reilly Safari amazon.co.uk

	recommend book⇒Distributed Programming with Java
		paperback
	ISBN10:	1-884777-65-1
	ISBN13:	978-1-884777-65-3
	publisher:	Manning Publications
	published:	1999-09-01
	by:	Qusay Mahmoud
Discusses how to digitally sign messages going over socket. Manning books.
amazon.ca amazon.com chapters.indigo.ca powells.com amazon.fr barnesandnoble.com amazon.de amazon.co.uk

For email signing and encryption, the two most common schemes are PGP often used with Eudora, and smime often used with MS Outlook.