[Cryptography] Encodings for crypto

Patrick Chkoreff patrick at rayservers.net
Wed Feb 19 08:10:16 EST 2014

ianG wrote, On 02/18/2014 07:54 AM:

> We need one number that simply expands to fill the needs.  This
> is done with the 7 bit trick, where the high bit being set says there is
> a following extra byte.

Yes, I've done this in Perl, so I'm showing the Perl code here.  I
haven't needed to do it in C yet, otherwise I'd show C code.

# Read a natural number from stream $in.
sub get_nat
    my $in = shift; # The input stream

    my $n = 0;
    my $pow = 0;

    while (1)
        my $x = ord(stream_get_char($in));
        $n += ($x << $pow);
        return $n if $x < 128;
        $pow += 7;

# Convert a natural number to a string.
sub put_nat
    my $n = shift;

    my $out = "";
    while (1)
        last if $n < 128;

        # Find x and r where (n = 128*r + x) and (128 <= x <= 255).
        my $r = ($n - 128) >> 7;
        my $x = $n - ($r << 7);
        $out .= chr($x);

        $n = $r;

    $out .= chr($n);
    return $out;

> Next, we should really be thinking in OO terms. ...

In 40 years of programming I've been down more rabbit holes than I can
shake a stick at, including that one, so I'll not argue.  All I can say
is that my current favourite rabbit hole is:  Functions which operate on
immutable data.  I've got lots of dry hay down here and I'll be snug
until the next flash flood flushes me out.

> We do however need a sequence of bytes, and a byte array is constructed
> simply with a length (number as above) and a sequence of bytes.  That's
> 2 primitives so far.

Yep, in Perl again:

# Read a string from stream $in.
sub get_str
    my $in = shift;
    my $len = get_nat($in);
    return stream_get_chars($in,$len);

# Convert a string to, er, an encoded string.
sub put_str
    my $str = shift;
    return put_nat(length($str)) . $str;

> Once we get thinking in OO terms, we can then create anything that is
> desired within the context of the class.  Need a version?  Add a number.
>  Need a boolean?  Add a flags number.  Need a negative?  Add another flag.

For me, cozy in my "immutable data" hole for now, I'm encoding
"arbitrary data" as nested lists with strings at the leaves.  I'm not
even putting longs or floats down there, as such.

> Next.  When we get more complicated, we can simply encapsulate the
> complications into a new class/object.  This would be idea for floats
> for example.  Which leads us to the second observation:  composition of
> objects is a far more natural way to build up protocol elements.

Incidentally, when I was in the OO rabbit hole, I did favour composition
over inheritance.  (Now I just end-run the whole issue by just writing a
plain-old function which can "reside" anywhere, but that's just me.)

> One more thing.  Without a seriously good testing and debugging system,
> this whole area breaks down with complexity, which is why people eschew
> binary and go for text.  There is a loopback technique I use to solve
> this issue, which I call the Ouroboros pattern.  In short it is this:
> 1.  each object has an example() method which produces a correct object
> with with each field constructed randomly.
> 2.  write that out through the stream process.
> 3.  read it back in to a new object, using the converse stream process.
> 4.  compare the two objects with standard equals() method.

Yep, right on, been there done that.  Except for the "constructed
randomly" thing -- I tend to cherry-pick corner-case and normal-case
examples for unit testing.  My normal development method these days is
"death-driven development", meaning I start off with a function that
just dies when I call it, and then start branching the possible cases,
hitting each case with a specific test.  I iterate this until "die" no
longer appears inside the function.

> Doing protocols with OO thinking is so much easier
> you never ever go back.  Once you do that, all of the formats, ideas,
> layouts, MLs start to look a little .. 20th century, steampunk, historical.

For a while I was enamoured with the idea that "the data knows how to
modify itself", but now I'm more charmed with the idea that "this
function knows how to take a list as input and produce another list as
output."  I try to marginalize any side effects as far as possible,
including an ultimate operation which conditionally locks and updates
one or more files in an atomic fashion.

Again though, my history of 40 years of programming is marked by veering
from one extreme to another, and this happens to be my current extreme.

-- Patrick

More information about the cryptography mailing list