Let's assume that you want to send an encrypted message to Bob. How do you know what key to use? If you use the wrong key, then you will potentially disclose the contents of your message to a third party. You don't want that. You need someway to securely get a copy of Bob's public key.
The easiest way to get a copy of Bob's public key is to meet with Bob. He could tell you his key's fingerprint and you could write it down. (Or, he could give you a business card, etc.) Since you were with Bob, you are probably confident that you have the right key. Now you can confidently send an encrypted message to Bob.
If you know Bob personally, you could even exchange fingerprints using a telephone. A telephone is not secure, but the public key is public and you recognize his voice. The only reasonable attack is for an adversary to intercept the conversation in real time and to use a voice impersonator to replace Bob reciting his fingerprint with another fingerprint. This is almost certainly technically possible, but extremely unlikely unless you are targeted by a nation state.
If you can't meet with Bob and you don't feel confident that you would recognize his voice, you need someone to introduce you. This could be your mutual friend Alice. In this case, you meet with Alice to get her fingerprint and ask her to meet with Bob. She then emails you Bob's fingerprint and you can directly contact Bob!
The web of trust is a way to formalize this type of interaction. When Alice meets with Bob she can sign his key and upload the signature to a key server. Since you trust Alice, you can use the publicly available signature to discover Bob's key.
Meeting people and signing keys is straightforward, but can be time consuming. When you get someone's key and are confident that that person really controls it, you can create a signature as follows:
$ gpg2 --recv-key 1E42B367
gpg: key 1E42B367: "Werner Koch <wk@gnupg.org>" not changed
gpg: Total number processed: 1
gpg: unchanged: 1
$ gpg2 --sign-key 1E42B367
pub dsa2048/1E42B367
created: 2007-12-31 expires: 2018-12-31 usage: SC
trust: unknown validity: full
sub rsa2048/FA8FE1F9
created: 2008-03-21 expired: 2011-12-30 usage: E
sub dsa1024/77F95F95
created: 2011-11-02 expires: never usage: S
sub rsa2048/C193565B
created: 2011-11-07 expired: 2013-12-31 usage: E
sub rsa2048/664D7444
created: 2014-01-02 expires: 2016-12-31 usage: E
[ unknown] (1). Werner Koch <wk@gnupg.org>
[ unknown] (2) Werner Koch <wk@g10code.com>
[ unknown] (3) Werner Koch <werner@eifzilla.de>
Really sign all user IDs? (y/N)
pub dsa2048/1E42B367
created: 2007-12-31 expires: 2018-12-31 usage: SC
trust: unknown validity: unknown
Primary key fingerprint: 8061 5870 F5BA D690 3336 86D0 F2AD 85AC 1E42 B367
Werner Koch <wk@gnupg.org>
Werner Koch <wk@g10code.com>
Werner Koch <werner@eifzilla.de>
Are you sure that you want to sign this key with your
key "Testing" (9E4DA08C)
Really sign? (y/N)
$ gpg2 --send-key DBFC6AD9
gpg: sending key DBFC6AD9 to hkp server pool.sks-keyservers.netThe important thing is to check that the fingerprint actually matches the fingerprint that the person gave you; it's completely feasible for there to be multiple keys with the same long id.
Let's assume that Alice followed these instructions when she met Bob. You should now be able to download Bob's public key and verify Alice's signature. Unfortunately, this is not enough for GnuPG to be able to actually use this information! The reason is that you have to tell GnuPG that Alice is a trusted introducer.
$ gpg2 --edit-key 1E42B367
gpg (GnuPG) 2.1.8-beta52; Copyright (C) 2015 Free Software Foundation, Inc.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
pub dsa2048/1E42B367
created: 2007-12-31 expires: 2018-12-31 usage: SC
trust: unknown validity: full
sub rsa2048/FA8FE1F9
created: 2008-03-21 expired: 2011-12-30 usage: E
sub dsa1024/77F95F95
created: 2011-11-02 expires: never usage: S
sub rsa2048/C193565B
created: 2011-11-07 expired: 2013-12-31 usage: E
sub rsa2048/664D7444
created: 2014-01-02 expires: 2016-12-31 usage: E
[ unknown] (1). Werner Koch <wk@gnupg.org>
[ unknown] (2) Werner Koch <wk@g10code.com>
[ unknown] (3) Werner Koch <werner@eifzilla.de>
gpg> trust
pub dsa2048/1E42B367
created: 2007-12-31 expires: 2018-12-31 usage: SC
trust: unknown validity: full
sub rsa2048/FA8FE1F9
created: 2008-03-21 expired: 2011-12-30 usage: E
sub dsa1024/77F95F95
created: 2011-11-02 expires: never usage: S
sub rsa2048/C193565B
created: 2011-11-07 expired: 2013-12-31 usage: E
sub rsa2048/664D7444
created: 2014-01-02 expires: 2016-12-31 usage: E
[ full ] (1). Werner Koch <wk@gnupg.org>
[ full ] (2) Werner Koch <wk@g10code.com>
[ full ] (3) Werner Koch <werner@eifzilla.de>
Please decide how far you trust this user to correctly verify other users' keys
(by looking at passports, checking fingerprints from different sources, etc.)
1 = I don't know or won't say
2 = I do NOT trust
3 = I trust marginally
4 = I trust fully
5 = I trust ultimately
m = back to the main menu
Your decision? 4
pub dsa2048/1E42B367
created: 2007-12-31 expires: 2018-12-31 usage: SC
trust: full validity: full
sub rsa2048/FA8FE1F9
created: 2008-03-21 expired: 2011-12-30 usage: E
sub dsa1024/77F95F95
created: 2011-11-02 expires: never usage: S
sub rsa2048/C193565B
created: 2011-11-07 expired: 2013-12-31 usage: E
sub rsa2048/664D7444
created: 2014-01-02 expires: 2016-12-31 usage: E
[ full ] (1). Werner Koch <wk@gnupg.org>
[ full ] (2) Werner Koch <wk@g10code.com>
[ full ] (3) Werner Koch <werner@eifzilla.de>
Please note that the shown key validity is not necessarily correct
unless you restart the program.Now the key is marked as a trusted introducer and any keys that person signed will be considered valid by GnuPG. It is also possible to mark an introducer as partially trusted. In this case, 3 partially trusted introducers are needed to trust a key.
There are two serious shortcomings with this approach. First, it requires a fair amount of work. Most people don't want to curate this type of data. But, if they don't the web of trust is effectively useless to them: GnuPG will only verify keys that they directly sign. Second, even if you are willing to add trusted introducers you are probably only willing to add people whom you know. This means that you'll only get a single level of indirection. Since you don't directly know Bob, you probably won't mark him as a trusted introducer. This greatly limits the usefulness of the web of trust.