Re: [TLS] [Cfrg] Citing specs in specs

[Watson Ladd <[e-mail]>]

On Mon, Mar 3, 2014 at 9:32 PM, Paul Lambert <[e-mail]> wrote:
>
>
> On 3/3/14, 2:52 PM, "Jon Callas" <[e-mail]> wrote:
>
>>On Mar 2, 2014, at 3:40 PM, Paul Lambert <[e-mail]> wrote:
>>
>>> Implementations are possible by using the readily available open source
>>> implementation.  This is a good thing, but it is also desirable
>>> to have a unambiguous description of the algorithms that is not
>>> a C code file.  This is why we write RFCs...
>>
>>It's hard to disagree with this, in a similar way that it's hard to
>>disagree with the idea of peace on earth, living at one with nature, etc.
>>
>>But in practice, code needs to be in a computer language rather than
>>English and I've seen (and been involved with) a document that started
>>with rough consensus and running code, translated that into English, and
>>the English was (and is) devilishly hard to compile back into C.
> Yes - I¹e seen the same problem.  English is not a concise or clear way to
> document an algorithm.

Really? Because all the people doing algorithms I've seen use English
to describe their results because it is clearer then code.

For instance, consider the following short C code.

typedef struct{ member *p; int rank} member;

void init(member *a){a->p=a; rank=0;}

member * find(member *a){
   member *q=a;
   member *r=NULL;
   member *t;
   while(q !=q->p){
            t=q->p;
            q->p=r;
            r=q;
            q=t;
    }
 while (r !=NULL){
         t=r->p;
         r->p=q;
        r=t;
  }
return q;
}

void union(member *a, member *b){
   a=find(a);
   b=find(b);
   if(a->rank<b->rank){
          a->p=b->p;
          b->rank++;
    } else {
       b->p=a->p;
      a->rank++;
   }
}

The above code is of course union-find. However, I don't know what
looking at the above code tells you about the algorithm. By contrast
the following description gets the point across much more clearly.
"We consider a forest where the root node of each tree points to
itself, and pointers point up. The find operation takes the node it is
given, and follows the chain of pointers to the root, reversing each
pointer. It then descends the chain, setting each encountered pointer
to the root. The union operation links the root with lower rank to the
one with greater rank and increments the rank of the new root."

In particular the description makes clear the invariant that is
maintained: each set has a unique element that points to itself, the
rank of a node is an upper bound on the height of the tree rooted at
that node. The code makes none of this clear: it is concerned entirely
with bookkeeping that seems as important as the main idea.

For something like F5, or point counting, or inverse square root, or
direct sparse matrix factoring, or the Fast Fourier Transform, the gap
between what English is able to do and what an executable
representation can do in terms of ideas is only bigger. There is a
reason computer science produces books, not code.

>
> HAC is pretty clear and is a decent example of cryptographic algorithm
> descriptions (http://cacr.uwaterloo.ca/hac/about/chap8.pdf), but still
> uses a mix of math notation and english text.

Your use of the word "still" implies that you think the two are in
some way opposed. They aren't: programming languages have nowhere near
the capacity of expressing ideas that the English language does.

>>
>>Portably implemented algorithms are hard to do in any computer language.
>>They're harder to do in words. I don't see how you're going to get an
>>unambiguous description of the language in anything but a computer
>>language. It doesn't have to be C, it could be Python, Ruby, or Algol-58
>>(which I mention because it was originally designed as an algorithmic
>>description language). English is a suboptimal implementation language.
>
> Yes, exactly!   'Readable code¹ would be a very good way to provide an
> algorithm description.  Why bother with pseudo code when a executable
> syntax could be used.   I submitted earlier on this list some Python code
> fragments as examples of this approach.  Python allows operator
> overloading, so it can provide some very readable ECC algorithm
> descriptions.

Readable without a working Python implementation to see what happens?

Note that Python code implementing Curve25519 exists in "Cryptography
in NaCl", which also contains test vectors.
Does anyone have an objection to putting equivalent Python in the
draft/would this satisfy those calling for more documentation?
If I have the nroff source of the draft I can do it in a few hours.

Sincerely,
Watson Ladd
>
> Paul
>
>
>
>
>>
>>       Jon
>>
>



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin