[Cryptography] List of Proven Secure Ciphers / Hashes

[Benjamin Kreuter]

On Thu, 2014-09-11 at 01:13 +1200, Peter Gutmann wrote:
> "R. Hirschfeld" <ray at unipay.nl> writes:
> 
> >Translate your factoring instance into a SAT instance via a poly-time (or
> >log-space) reduction.
> 
> Yeah, and now you're back to the how-to-travel-to-Mars problem:
> 
> 1. Build a big rocket.
> 2. Round up some astronauts.
> 3. Fly to Mars.  QED.
> 
> The fact that you can state a solution doesn't mean that you can actually do
> it.  I specifically chose SAT because of its everything-maps-to-SAT status,
> but was trying to point out that having a SAT solver doesn't automatically
> break RSA or DH or whatever.

Actually it is easy to factor integers using a SAT solver.  Start with a
circuit that outputs 1 if N = P*Q and 0 otherwise, with P and Q as
inputs and N fixed to the integer you want to factor.  Now for each bit
of P, fix the bit as 0 (leaving the others unknown) and apply your SAT
solver; now you know which bits of P are 0 i.e. you know the value of P.

You can do something similar for DLOG.

-- Ben

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140910/dc732a40/attachment.sig>