# Cryptography question: PGP

**URL:** <https://boards.straightdope.com/t/cryptography-question-pgp/338049>\
**Category:** Factual Questions\
**Created:** [January 2, 2006, 5:11am UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049 "2006-01-02T05:11:56Z")\
**Posts on this page:** 16\
**Page:** 2

<div class="post-metadata">

**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\
**Post date:** [January 3, 2006, 6:48pm UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/21 "2006-01-03T18:48:13Z")

</div>

Is prime factorisation in NP?

---

<div class="post-metadata">

**Author:** ![Ponder\_Stibbons](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ponder_stibbons/32/343_2.png) [@Ponder\_Stibbons](https://boards.straightdope.com/u/Ponder_Stibbons)\
**Post date:** [January 3, 2006, 7:06pm UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/22 "2006-01-03T19:06:40Z")

</div>

I just wanted to jump in to say what a great thread this is. I’d always sort of wondered about how PGP works but never actually put the effort into framing the question. Congrats, **Halitosis** , on the great OP and followups and to thos who answered. Particularly to **gotpasswords** who included the link to the T-Shirt. I love that T-Shirt.

---

<div class="post-metadata">

**Author:** ![Digital\_Stimulus](https://avatars.discourse-cdn.com/v4/letter/d/aeb1de/32.png) [@Digital\_Stimulus](https://boards.straightdope.com/u/Digital_Stimulus)\
**Post date:** [January 3, 2006, 7:14pm UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/23 "2006-01-03T19:14:15Z")

</div>

> [@Dominic Mulligan](#):
>
> Is prime factorisation in NP?

Not being an algorithms guy, I defer to (and quote) experts. According to [Garey and Johnson](http://www.bestwebbuys.com/books/compare/isbn/0716710447/isrc/b-search-other) (first useful google link):

> [@](#):
>
> [OPEN11] **Composite Number**  
> INSTANCE: Positive integer N.  
> QUESTION: Are there positive integers m,n\>1 such that N = m\*n?  
> Comment: The problem is in NP intersect co-NP [Pratt, 1975]. Although no polynomial time algorithm is known, there is an algorithm for the problem that runs in polynomial itme if the “Extended Riemann Hypothesis” holds [Miller, 1976]. However, there is no such algorithm known for determining the prime factors of N, and this latter problem may be harder than the basic decision problem. Of course, all these problems are easily solved in pseudo-polynomial time.

---

<div class="post-metadata">

**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\
**Post date:** [January 3, 2006, 9:46pm UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/24 "2006-01-03T21:46:51Z")

</div>

> [@Dominic Mulligan](#):
>
> Is prime factorisation in NP?

Perhaps you should rephrase the question!

---

<div class="post-metadata">

**Author:** ![Nanoda](https://avatars.discourse-cdn.com/v4/letter/n/ce73a5/32.png) [@Nanoda](https://boards.straightdope.com/u/Nanoda)\
**Post date:** [January 4, 2006, 12:24am UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/25 "2006-01-04T00:24:12Z")

</div>

> [@ftg](#):
>
> Perhaps you should rephrase the question!

Heh. IMHO, it’s impossible to talk about cryptography w/o someone mentioning how difficult it is to factor large prime numbers. Coupla times it’s been me. 😉

---

<div class="post-metadata">

**Author:** ![drhess](https://avatars.discourse-cdn.com/v4/letter/d/94ad74/32.png) [@drhess](https://boards.straightdope.com/u/drhess)\
**Post date:** [January 4, 2006, 12:41am UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/26 "2006-01-04T00:41:03Z")

</div>

> [@CurtC](#):
>
> I’ve explained it before (with some success) like this: if someone gives you the number 35, and tells you that it’s the product of two primes, it’s pretty easy to find them, right? How about 91? It’s 7x13, so it’s not too hard, but you don’t know it immediately. How about 391? As the numbers get bigger, it gets harder and harder, because the only way to factor it is to simply test all the possibilities. With a number hundreds of digits long, it’s so tedious that even a powerful computer can’t do it in its MTBF.
> 
> And another point - if a mathematician figured out a shortcut way of factoring large numbers, all our modern public key cryptography schemes would be useless.

What’s MTBF?

---

<div class="post-metadata">

**Author:** ![Whack-a-Mole](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/whack-a-mole/32/141_2.png) [@Whack-a-Mole](https://boards.straightdope.com/u/Whack-a-Mole)\
**Post date:** [January 4, 2006, 1:10am UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/27 "2006-01-04T01:10:39Z")

</div>

> [@drhess](#):
>
> What’s MTBF?

MTBF = Mean Time Before Failure (basically when the manufacturer expects there to be a good chance your computer will fail…your warrantee will _always_ be less than this time).

Of course in a NSA type environment I am sure the computers are looked after rather well and if something breaks it is doubtless fixed and running again in short order.

I have a hard time relating these really big numbers to anything I can more easily grasp. The US is planning a supercomputer that can run 50 trillion calculations per second (sustained). At that speed I would think PGP would crack in relatively short order but then I really have no clue.

If they ever get quantum computers running in a useful way factoring large numbers will become trivial (at least to those with quantum computers).

---

<div class="post-metadata">

**Author:** ![Halitosis](https://avatars.discourse-cdn.com/v4/letter/h/ee7513/32.png) [@Halitosis](https://boards.straightdope.com/u/Halitosis)\
**Post date:** [January 4, 2006, 1:49am UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/28 "2006-01-04T01:49:50Z")

</div>

Arrgh! Now I have a new problem:  
I can’t find any free, non-internet-based, Windows PGP key program with a GUI. I’ve found ones that cost money, ones hosted on the internet, and (lots of) ones for Linux, but are there any that I can create keys from sitting at my Windows box without an internet connection and without going to any prompts?

---

<div class="post-metadata">

**Author:** ![alterego](https://avatars.discourse-cdn.com/v4/letter/a/6bbea6/32.png) [@alterego](https://boards.straightdope.com/u/alterego)\
**Post date:** [January 4, 2006, 2:50am UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/29 "2006-01-04T02:50:41Z")

</div>

> [@Halitosis](#):
>
> Arrgh! Now I have a new problem:  
> I can’t find any free, non-internet-based, Windows PGP key program with a GUI. I’ve found ones that cost money, ones hosted on the internet, and (lots of) ones for Linux, but are there any that I can create keys from sitting at my Windows box without an internet connection and without going to any prompts?

[ul]  
[li][Windows Privacy Tray](http://www.stud.uni-hannover.de/~twoaday/winpt.html)[/li][li][GNUpg](http://clbianco.altervista.org/gnupg/eng/gnupg.html)[/li][/ul]

---

<div class="post-metadata">

**Author:** ![Halitosis](https://avatars.discourse-cdn.com/v4/letter/h/ee7513/32.png) [@Halitosis](https://boards.straightdope.com/u/Halitosis)\
**Post date:** [January 4, 2006, 3:13am UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/30 "2006-01-04T03:13:58Z")

</div>

Whooo, it worked! Would anyone be so kind as to send me their own PGP public key / message so I can make sure that I know how to use it? (Sorry if I keep asking too much!) I uploaded my key to [http://pgp.mit.edu/](http://pgp.mit.edu/) with key ID 0x127A4EE9 . Pretty please!

---

<div class="post-metadata">

**Author:** ![Tim\_T-Bonham.net](https://avatars.discourse-cdn.com/v4/letter/t/46a35a/32.png) [@Tim\_T-Bonham.net](https://boards.straightdope.com/u/Tim_T-Bonham.net)\
**Post date:** [January 5, 2006, 6:33am UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/31 "2006-01-05T06:33:26Z")

</div>

> [@Joey P](#):
>
> I always want to stand up and reply that that would only be the case if the password was the LAST one tried.

Well, duh, of course it’s the LAST one tried.

Why would you keep trying after you’ve found the password that works?

---

<div class="post-metadata">

**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\
**Post date:** [January 5, 2006, 4:29pm UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/32 "2006-01-05T16:29:54Z")

</div>

> [@ftg](#):
>
> Perhaps you should rephrase the question!

:smack:

You knew what I meant 😛

---

<div class="post-metadata">

**Author:** ![Pleonast](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pleonast/32/1183_2.png) [@Pleonast](https://boards.straightdope.com/u/Pleonast)\
**Post date:** [January 5, 2006, 6:57pm UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/33 "2006-01-05T18:57:19Z")

</div>

> [@ed](#):
>
> I’m not sure about encryption, but I know that when discussing hashing algorithms (which are more commonly used for password authentication), they _are_ referring to the number of attempts it would take before you had a roughly 50% chance overall of getting the correct result. For example, for the SHA-1 algorithm you could determine a collision definitively somewhere on the way to 2^160 attempts, but because of the birthday paradox you would have a better than half chance of finding one after “only” 2^80 attempts.
> 
> Of course, you could hit a collision prior to that mark, but the probability drops off exponentially pretty quickly the earlier you go, so half is a pretty good mark.

Clarification:

SHA-1 has 160 bits in its hash. If you were given a message (and its hash) and had to find a second message with the same hash, it will take you on average 2^159 (half of 2^160) random guesses. You only get to choose one of the messages.

Instead, if you are told to find any two messages with the same hash (so you get to choose _both_ message), it will take you on average 2^79 (half of 2^80) random guesses.

By the way, I believe cryptographers have found a way to find two messages with the same SHA-1 faster than random guessing (i.e., brute force). Thus, SHA-1 is considered broken, although only marginally at this time, since it’s still computationally very difficult to find a pair.

---

<div class="post-metadata">

**Author:** ![Hari\_Seldon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hari_seldon/32/5173_2.png) [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)\
**Post date:** [January 5, 2006, 8:47pm UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/34 "2006-01-05T20:47:35Z")

</div>

No one has quite explained how the RSA (Rivet, Shamir, Adelman) system of public key cryptography works. I will try. But first let me say that indeed if someone figures out a fast way of factoring numbers, it will be trivial to crack. There are other schemes (elliptic curve method and, I believe, the discrete logarithm method) that are based on other seemingly difficult problems. Incidentally, factorization is one problem for which a fast method is known, but it is based on a quantum computer. So if anyone succeeds in building a quantum computer…

I will write x^y for x to the power y, enclosing y in braces, that is {y} if it is more than one character long and x^y (mod m) for the remainder that x^y leaves when divided by m. I will write x == y (mod m) to mean either of the following two equivalent statements: m divides x - y; x and y leave the same remainder when divided by m. I will write x^y (m) for the remainder when x^y is divided by m. I will write != for not equal. I will write phi(m) for the number of numbers less than or equal to m and having no common divisors with m. So phi(1) = 1, phi(2) = 1, phi(3) = 2, phi(4) = 2, phi§ = p-1 whenever p is prime and so on. If p != q are prime, then it can be shown that phi(pq) = (p-1)(q-1). (More generally, if a and b have no divisors in common, then phi(ab) = phi(a)phi(b), but we have no need of that more general fact.) It is elementary to show that when p != q are prime, then factoring pq has the same difficulty of calculating phi(pq). That is, answering one of these two questions gives you a trivial computation for the other. The last observation required is that even when n and m are 1000 digit numbers, it is not hard to calculate x^n (mod m) for any x \< m. All this is well known and I will not go into detail.

Fermat proved (Fermat’s little theorem) that if p is prime, then for any number a, a^p == a (mod p). It is not hard to prove, but all proofs I can think of are either somewhat sophisticated or rather computational. It can be found in any book on number theory. Euler generalized this to say that if m is any square free number (not divisible by the square of any prime) and if d and e are numbers such that de == 1 (mod phi(m)), then for any number a, a^{de} == a (mod m). This is really a gloss on Fermat’s theorem. It follows that if a \< m, a^{de} (mod m) is equal to a.

Now here is how RSA works. Let m = pq, a product of, say, two 500 digit primes. (I will say something more about that below.) This will be a number of about 1000 digits (actually 999 or 1000). Since you are the one who has chosen p and q, you can compute m while, presumably, no one else can. Choose d and e so that de == 1 (mod phi(m)) (easy) and publish d and m, while keeping e and phi(m) (as well as p and q) secret. Someone wishing to send you a coded message first encodes it as a string of integers and breaks it up into substrings, all less than m. If a is one of those substrings, you transmit a^d (mod m). If he transmits b, then b^e (mod m) is a and there you have it! The encryption and decryption process are then raising to the power d and then e, mod m, and are therefore completely different. Aside from possibly easy factoring algorithms, it is conceivable that some decryption algorithm exists that is independent of factorization. No one knows. Well, I should say that if anyone knows, he is keeping it secret. That goes for factorization too. Incidentally, although this works in some reasonable time, it is slow enough that RSA is generally used only to generate and exchange keys for some faster kind of symmetric algorithm.

What about finding primes? Well, there is actually a polynomial time algorithm that can test primality. But if I were carrying it out, I would use a probablilistic method. It is based on the fact that, while the converse of Fermat’s little theorem is false, it is nealy true, in the sense that if a number m is such that a^m == a (mod m) for all a having no common divisor with m, then m is most likely prime. Not necessarily, but with probability that is very nearly 1 when m is large. In fact, if even 2^m == 2 (mod m), then most likely m is prime and the probability increases as yoou test other numbers. The test can be refined by taking into account how many times 2 divides m - 1 and you get to 100 nines probability very quickly, far exceeded by the probability of having a mole in your office.

Some years ago, the American Mathematical Monthly had an article on RSA cryptography by Susan Landau, now employed by Microsoft Research, in which she pointed a number of conditions on the primes p and q that had to be avoided to be safe. There were quite a number o them and new ones seemed to be being discovered all the time, which made me wonder how safe it ws even now.

---

<div class="post-metadata">

**Author:** ![ed](https://avatars.discourse-cdn.com/v4/letter/e/c77e96/32.png) [@ed](https://boards.straightdope.com/u/ed)\
**Post date:** [January 5, 2006, 11:11pm UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/35 "2006-01-05T23:11:06Z")

</div>

> [@Pleonast](#):
>
> Clarification:
> 
> SHA-1 has 160 bits in its hash. If you were given a message (and its hash) and had to find a second message with the same hash, it will take you on average 2^159 (half of 2^160) random guesses. You only get to choose one of the messages.
> 
> Instead, if you are told to find any two messages with the same hash (so you get to choose _both_ message), it will take you on average 2^79 (half of 2^80) random guesses.

Interesting, I actually was misundertanding this to mean that you could determine collisions with an existing value within 2^(n/2), but apparently I’m wrong. 🙂

---

<div class="post-metadata">

**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\
**Post date:** [January 6, 2006, 3:00am UTC](https://boards.straightdope.com/t/cryptography-question-pgp/338049/36 "2006-01-06T03:00:45Z")

</div>

> [@Hari Seldon](#):
>
> Some years ago, the American Mathematical Monthly had an article on RSA cryptography by Susan Landau, now employed by Microsoft Research, in which she pointed a number of conditions on the primes p and q that had to be avoided to be safe. There were quite a number o them and new ones seemed to be being discovered all the time, which made me wonder how safe it ws even now.

Susan Landau has worked for [Sun](http://research.sun.com/people/slandau/) for many years.

I brought up the issue of the ratio of “bad primes” with Ron Rivest in 1978. He was surprisingly unconcerned. My doubts have only gotten stronger.

[Previous page](https://boards.straightdope.com/t/cryptography-question-pgp/338049.md?page=1)