Complexity theory often uses the concept of an oracle, which is a function that gives you a correct answer in constant time; some oracles only hand out one bit at a time, while others give you more data than that. One reason that oracles are useful is that they give you lower bounds on how much work is required to do something - if a job requires O(f(x)) time with an oracle doing the hard parts, you know the whole job is at least that complex. NP completeness uses Non-Deterministic Turing Machines, which are one formalization of oracles - an NP complete problem requires polynomial time to solve if the Turing machine is allowed to make O(p(n)) correct non-deuerministic steps (e.g. gets the bits from an oracle), where p(n) is some polynomial or smaller function of the input size. (NP complete problems are normally formalized as a function that returns 0 or 1 depending on whether the input is a correct solution to the problem, so solving is equivalent to demonstrating that a given solution is correct.)
So, if you've got an oracle around (and oracles cost more than the $10,000 Perry bet Jim, if you buy good ones :-), how much work does it require to demonstrate that the oracle just handed you a correct key?
Public Key: n = pq, where p and q are secret, e relatively prime to (p-1)(q-1) Privatekey: d = e**-1 mod (p-1)(q-1), which is about logn bits long. Encrypting: c = m**e mod n Decrypting: m = c**d mod n n, d, c, and m are all about logn bits long; d may be a couple bits shorter. p and q may be shorter, but logp + logq = logn.
One way to demonstrate that the oracle handed you a correct key is to encrypt a piece of data and then decrypt it. This requires two exponentiations, and two or more modulo steps. My copy of Knuth is buried somewhere, so I don't remember the complexity of mod n, but it's got to be at least log n or so. Encryption is fast, since e is a constant (fast is log n in this case), but decryption requires O(logn) multiplies, and each multiply takes at least logn steps since the answer has 2logn bits (it may be slower, I forget; it's probably logn * logn single-bit adds plus carries.) So the time required is >= logn**2, which is too slow for Jim.
The other way to demonstrate that the oracle handed you a correct key is to show that de = 1 mod (p-1)(q-1), which requires knowing p and q, and is thus equivalent to factoring n, as Perry said. I suppose the oracle could hand you (p-1)(q-1) = pq-p-q+1 = n-p-q+1 without handing you p and q, but that's asking a lot from an oracle.
Bill
Thanks Bill, Would you happen to know of any texts which discuss the characteristics of the mod function when nested or applied to other functions? I am having a hard time locating such texts. (this was and is my original question) Take care.