[mercury-users] functions returning in values?

[Sandy Harris]

Ralph Becket wrote:

> > >> An interesting application of this stuff is in cryptography: you
> only
> > >> have to describe the cipher function in Mercury and supply the
> > >> appropriate modes and Mercury will give you both enciphering and
> > >> deciphering, ...
>
> You can write
> 
> :- pred cipher(key, plaintext, ciphertext).
> :- mode cipher(in, in, out) is det.
> :- mode cipher(in, out, in) is det.
> 
> cipher(K, P, C) :- ...
> 
> and get both directions from the same code, both of which of course
> will require the key as an input.  I was not suggesting that you should
> expect to get a key-cracker out of it.

Well, given the above, you can also try for a cracker. I'm learning Mercury
mainly to play with some ideas I have for cracking DES.

There's a notion called unicity distance, the amount of known plaintext
it takes to uniquely determine a key. Shannon introduced it in a classic
1950s paper on ciphers; the same one where he introduced "confusion" and
"diffusion". Methods of determining unicity distance for a cipher are
well-known. 

If you have a list of plaintext/ciphertext pairs p1, c1, p2, c2 ... pn, cn
such that the total plaintext/ciphertext length exceeds that distance, then
you have at worst:

:- pred keysearch( key, list) is semidet.

It becomes det if you can guarantee the inputs are actually all valid pairs,
generated with the same key. If not, it may fail. If the list is shorter
than the unicity distance (but valid pairs), then it is multidet.

What mode is cipher(out, in, in)? For most ciphers it could generate
multiple outputs, but it might also fail in some cases.

In theory, any block cipher can be broken this way, just as they can all be
broken by brute force search. In practice of course, both compilation and
execution times for an attack on any reasonable cipher are likely to require
astronomical amounts of resources.

One project to crack DES roughly this way is:
http://grex.cyberspace.org/~enoch/crakfaq.html

I'm working along somewhat similar lines, but with a couple of variations.
Anyone interested in collaborating on such a project, send off-list mail.
I understand the crypto, but am light on logic and constraint programming
skills.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------