-----BEGIN PGP SIGNED MESSAGE----- On Sun, 8 Jun 1997, Robert A. Costner wrote:
I have a question for any of you that may know the answer. This is for a paper I am giving to the Social Security Administration on Tuesday, so I would appreciate any answer I get.
If I generate a personal PGP keypair on some machine it takes a specific period of time to do the intensive calculations, let's assume ten minutes for this example. If I needed 10,000 such individual keyspairs for a unspecified authentication attack, does this have to take 10,000 times 10 minutes (over two months with this CPU), or is there a faster way to generate a large number of keypairs to appear to be a large number of people.
There are a few shortcuts you could take. For instance, instead of finding two random, prime numbers for every key, just keep one prime constant and generate another random prime for each key. This has the disadvantage that any one key factored would allow the other keys to be factored trivially. I know there are other ways, but I'm not very good with number theory. Using this technique, it would take about half as long to generate 10,000 public keys.
The larger question is since 10,000 unique written signatures seems to indicate that 10,000 unique individuals exist, would 10,000 unique PGP signatures also seem to indicate that these are not from the same person?
The basis of PGP is the web of trust. Keys are signed by people who are trusted to be competent and truthful, so the user can be sure to a certain degree that the key really is owned by the person listed in the ID field. There are problems that arise with this simplistic key management system, but I won't reiterate what has been discussed many times before. There are a few papers that discuss this in detail. Here are some pointers: ds.internic.net/internet-drafts/draft-ietf-spki-cert-req-00.txt draft-ietf-spki-cert-structure-01.txt research.att.com/dist/mab/policymaker.ps http://theory.lcs.mit.edu/~rivest/ So the simple answer to this question is that one would not be able to get all 10,000 keys signed, so there would only be one key that could be trusted to belong to that person. Mark -----BEGIN PGP SIGNATURE----- Version: 2.6.3 Charset: noconv iQEVAwUBM5teJSzIPc7jvyFpAQF68wf/YiMlEkZV0axYIAp+WNCGlhuG9JTmu5st 4YUXGvkxwg4icePatfz+yttWfpYEmnSKP/9ZiLAAegsfuWcaK9frnntguUsH5jxE SZMXVWQzIqjW8sTNWY5KtDLbAkNE99gLCbPGq4zaksryzWYwwqOukHFXHFZkKWF6 0sEk3H+AVY5SOCUf/MuNZACc1d6CLsWBHoUl2BFCi0seUcFqdBnEmydIaIyI4fee Kdezl/QPnVWQKBmZVuYfUtIrP+Kc1cD30D7LAqcPd+rr9UkstOv0rsRR5vH2SZwp 7T8MFCeRQx1gs/j4QUvKgS/Y+vYrewTUmjdpADBF70ck0io23z4JZQ== =n5hc -----END PGP SIGNATURE-----