From: Jim choate <ravage@bga.com>
Date: Sun, 19 Jun 94 08:10:24 PDT
To: bill.stewart@pleasantonca.ncr.com +1-510-484-6204)
Subject: Re: Magic O(logn) RSA decryption algorithms
In-Reply-To: <9406182147.AA14634@anchor.ho.att.com>
Message-ID: <199406191510.KAA01680@zoom.bga.com>
MIME-Version: 1.0
Content-Type: text


> 
> 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.