On 2012-03-30, Maxim Kammerer <m...@dee.su> wrote: > On Fri, Mar 30, 2012 at 06:06, Robert Ransom <rransom.8...@gmail.com> wrote: >> Shallot computes a single public modulus p*q and searches for a public >> exponent e which produces a SHA-1 hash with the desired properties. > > For some reason I thought that that would produce non-standard RSA > keys, perhaps because the old ssl-genrsa only supported e={3,65537} > (whereas the new ssl-genpkey doesn't have this limitation). Isn't the > point of e like 3 or 65537 (with few bits set) to make encryption > fast?
Yes. (Note that hidden service identity public keys are only used for signature verification, which is not the same as encryption with any modern padding scheme.) But Tor didn't enforce that requirement for hidden service identity keys soon enough, and I don't think OpenSSL's RSA implementation benefits much from those particular choices of e (other than from the fact that they're short). > Do you know whether Shallot-produced RSA keys have any > noticeable detrimental effect on relays load because of the > unrestricted exponent? Maybe a little. No one will let Shallot run long enough to produce a really big public exponent, though. (Relays raise 1024-bit numbers to 320-bit powers all the time for forward secrecy. Shallot won't generate 320-bit public exponents.) Maliciously generated hidden service identity keys could have much larger public exponents, but hopefully no one will bother implementing that DoS attack. >> That's much faster than doing a 512-bit-by-512-bit bignum multiply for >> each hash, *and* the search for a suitable exponent could (in theory) >> be performed in parallel across many (untrusted) computers. > > Sure, but you don't have to do it in the most straightforward way. You > can multiply once, and then add 2p for each hash. The overhead for a > GPU / FPGA implementation should be negligible, and the search can be > parallelized as well. Maybe. But note that the public exponent is stored at the end of the public key blob, so updating the exponent (or a piece of it) also makes generating each hash easier. > If adding large multiples of p, the nodes can be > untrusted, too, I guess. No -- the Euclidean algorithm would break that *very* quickly. Robert Ransom _______________________________________________ tor-talk mailing list tor-talk@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk