From: wcs@anchor.ho.att.com (bill.stewart@pleasantonca.ncr.com +1-510-484-6204)
Date: Sat, 18 Jun 94 14:48:17 PDT
To: cypherpunks@toad.com
Subject: Magic O(logn) RSA decryption algorithms
Message-ID: <9406182147.AA14634@anchor.ho.att.com>
MIME-Version: 1.0
Content-Type: text/plain


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