[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Photuris // Variable-Precision numbers




I agree with Bill that this is quibbling over a real minor point, but I'll
continue the debate just this once from a desire for mathematical cleanliness.

Let S denote the value of the Size field and let V denote the value of the
Value field, represented as an integer with very large precision:
	V = .....v_5 v_4 v_3 v_2 v_1 v_0
Then the answer we want can be represented as X, computed by the program:
	X = Sum_{0<=i<S} v_i * 2^i
This is correct even when S = 0 (no significant bits), since an empty sum
yields a result of zero.  (Equivalently, we zero out all but the S low-order
bits of V, and call the result X.)  With the approach suggested by Simpson
we have to take:
	X = if (S<=1) 
            then S 
            else Sum_{0<=i<S} v_i * 2^i
in order to avoid reference to an undefined quantity v_0 when S = 1.

The number of BYTES in the value field is 
	# bytes = ceiling{S/8} 
with the approach I am suggesting, whereas with "stealing that number
to make the programming simpler" (as suggested by Simpson) we end up with 
	# bytes = if (S = 1) 
                  then 0
	          else ceiling(S/8)

I think that programming is really simpler without making a special case
out of S = 1.

	Ron Rivest


	



==============================================================================
Return-Path: <ipsec-request@ans.net>
Date: Mon, 16 Oct 95 20:11:56 GMT
From: "William Allen Simpson" <bsimpson@morningstar.com>
To: ipsec@ans.net
Subject: Re: Photuris // Variable-Precision numbers

> From: rivest@theory.lcs.mit.edu (Ron Rivest)
> The problem is for the case t = 1.  It is inconsistent to have no bits in the
> value field at all.  For t=1, you should be able to represent either 0 or 1.
> 	Size       Value        Represents (decimal)
>         0000                    0
What in the world is a number with _no_ significant bits?

>         0001       00           0   *** This is what you want
>         0001       01           1   *** This is what you want

What is the point of a number with 1 significant bit which is always 1?

My answer to these rhetorical questions is:

There is no such thing as a number with no significant bits.  Therefore,
we steal that number to make programming simpler.  0 means a number with
one significant bit, which is 0.

Rather than wasting space on a number with 1 significant bit, when half
the possible values are already special cased, use the size field to
special case that 1, meaning 1 significant bit of value 1.

Oh, and this is all rather a waste of time arguing, since 0 and 1 aren't
legal for exponents anyway.  They are just very commonly used numbers.

Never-the-less, I will try to make the wording clearer next time around.

I presume that you like the 'ff' extension scheme?  Good, thanks for
the suggestion!

And since we are down to little quibbles, I presume that you are happy
with the fields hashed for the signature, session-keys, and others?

Are there any serious cryptographic flaws in the messages?

Bill.Simpson@um.cc.umich.edu
          Key fingerprint =  2E 07 23 03 C5 62 70 D3  59 B1 4F 5E 1D C2 C1 A2



Follow-Ups: