[mercury-users] Newbie query about compiler optimisations

[Sandy Harris]

I'm looking at using Mercury to solve a block cipher for the key,
knowing some input plaintext and output ciphertext.

This is clearly possible in principle, and equally clearly ridiculously
expensive in practice unless there are some clever optimisations to
apply. I think I've found a useful optimisation, but am not sure how
to apply it in Mercury.

The structure of the cipher I'm attacking (DES) lets me split the
key neatly into two parts that affect disjoint parts of the cipher.
With k1 and k2 for those, p for plaintext and c for ciphertext, I
can write:

:- pred cipher( p, c, k1, k2).
:- mode cipher( in, out, in, in) is det. % encryption
:- mode cipher( out, in, in, in) is det. % decryption

% the interesting part
% true only if we define plaintext/ciphertext sample to be
% large enough to exceed the cipher's unicity distance
:- mode cipher( in, in, out, out) is det. % crack cipher

I have most of a fairly naive implementation of this in hand,
but that's not very useful. k1 and k2 combined are 56 bits.
The backtracking could take millenia.

What I want to do, and haven't figured out, is to solve for one
of the k's at a time, treating the other as a "don't care"
variable.

e.g. treating k2 as don't care and solving for k1, either of
these functions would do (I'm not yet sure which is preferable):

% solve directly for k1 treating k2 as don't care
:- pred findleft(p, c, k1).
:- mode findleft(in, in, out) is det.

% test a k1 value to see if it works with any value of k2 
% to be called from a loop that tries all possible k1
% and returns the one good one
:- pred testleft(p, c, k1).
:- mode testleft(in, in, in) is semidet. % true if a suitable k2 exists

You then (or in parallel) do something similar to find k2, with k1
treated as "don't care". k1 and k2 are 28 bits and two searches of
2^28 each are a lot better than one of 2^56.

The catch is that I need as much simplification as possible done at
compile time. Ideally, I'd like to optimise the "don't care" stuff
away entirely. Almost any compile-time price is worth paying if it
improves run-time performance. 

How do I tell the compiler I want that?

Compile overheads aren't a big issue. I'd be perfectly happy with
a compile time of a few weeks on a 512 meg 500 MHz machine.
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------