Cryptography-Digest Digest #835, Volume #11 Mon, 22 May 00 11:13:01 EDT
Contents:
Re: More on Pi and randomness ("Trevor L. Jackson, III")
Re: QUESTIONS About ALGOS !! (Runu Knips)
Final Comments from Twofish Team (Bruce Schneier)
Comments on IPSec and AES (Bruce Schneier)
Re: pentium timings (Mok-Kong Shen)
Re: 3DES SOURCE (Mok-Kong Shen)
Re: Compare 3DES's. (Mok-Kong Shen)
Re: More on Pi and randomness (Mok-Kong Shen)
Re: 3DES SOURCE (Runu Knips)
Re: More on Pi and randomness ("Clive Tooth")
Re: Is OTP unbreakable? (Richard Herring)
Re: Interpretation of Hitachi patent claims (Gordon Walker)
Re: Final Comments from Twofish Team (Runu Knips)
Re: AES final comment deadline is May 15 (Paul Koning)
----------------------------------------------------------------------------
Date: Mon, 22 May 2000 09:45:25 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: More on Pi and randomness
Clive Tooth wrote:
> "Trevor L. Jackson, III" wrote:
>
> > Guy Macon wrote:
> >
> > > In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
>wrote:
> > >
> > > >I understand the Nth hexit of pi, irrespective of the value of N, to be
> > > >calculable using the equation derived by Borwein, Borwein and Plouffe.
> > > >The 400 billionth hexit of pi has been thus calculated.
> > >
> > > Really?!? (not questioning you, just suprised). Does the time to compute
> > > the answer get larger as N gets larger? Linearaly? Exponentialy?
> >
> > Since the formula is based upon N, it's implementation grows as the log of N.
>
> No.
Interesting.
>
>
> The time required to calculate the Nth _hex_ digit of pi by these
> non-memory-intensive methods is at most O(N*(log(N))^O(1)).
A simplistic implementation in multi-precision arithmetic requires only a few MP
multiplies
and an MP division to produce a term of the series. Since the MP operations are O(log
N)
your estimate of the overall work implies that O(N) terms of the series are required to
produce a digit.
Why is that? (I thought the number of terms was bounded by a small number)
>
>
> The time required to calculate the Nth digit of pi in an arbitrary base
> by non-memory-intensive methods is at most O(N^3*(log(N))^O(1)).
>
> Some interesting things about these methods (for values of N typically
> attempted):
>
> 1) The amount of memory required is small compared to the typical memory
> on today's PCs.
> 2) Little or no multiprecision arithmetic is required.
> 3) Computing _all_ the hex digits of pi, from 1 to N, using the fastest
> known method (whose memory usage is O(N)) is asymptotically faster than
> using the fastest known non-memory-intensive method to just calculate
> the Nth digit.
>
> There is a distributed processing project, PiHex, to compute the
> quadrillion (=10^15) th bit of pi:
> http://www.cecm.sfu.ca/projects/pihex/index.html
>
> The base formula for that project is described at
> http://www-stud.enst.fr/~bellard/pi/pi_bin/pi_bin.html
>
> Some time ago I posted an explanation of how these Nth hex digit methods
> work. Deja cannot seem to find it now so I reproduce it here.
>
> =================================================================
> Subject: Re: digit extraction algorithms for pi
> Date: Thu, 14 Jan 1999 22:41:04 +0000
> From: Clive Tooth <[EMAIL PROTECTED]>
> Newsgroups: sci.math
>
> Tom Weston wrote:
>
> > I've just been reading about the above algorithms, in particular
> > the Bailey-Borwein-Plouffe method, on the world wide web and am
> > rather puzzled about one aspect.
> >
> > As I understand things, the algorithm is based upon the expression
> >
> > pi= sum_{0}^{\infty} (4/(8n+1) - 2/(8n+4) - 1/(8n+5) -1/(8n+6)).(1/16)^n
> >
> > from which apparently you can extract the nth digit without the need to
> > calculate any of the previous. What puzzles me is how precisely is this
> > is done.
> >
> > If the coefficients of the (1/16)^n were integers less than 16 then
> > clearly the digits would be these numbers. Since it isn't, I imagine you
> > will need to evaluate at least a few of the terms.
> >
> > Is there an easy way to see how this is done? It seems that the when
> > the coefficient is written as a single fraction then the denominator must
> > be a multiple of 8 and that the coefficients lie in the range 0 to 47/15
> > but I can't quite see how to use this to get the digit.
>
> The method is not quite as straightforward as you might have hoped but
> it is fairly simple.
>
> It uses no multiprecision arithmetic - 64 bit floating point will be
> sufficient for interestingly large values of n (the hex digit required).
>
> I follow (but shorten) the exposition in "On the Rapid Computation of
> Various Polylogarithmic Constants" by D H Bailey, P B Borwein and S
> Plouffe, Mathematics of Computation 66 (1997), 903-913. In particular,
> see that paper for a discussion of the accuracy of floating point
> arithmetic required: 64 bit or 128 bit.
>
> First of all, note that, if a and b are positive integers, we can
> calculate a^b mod c in less than 2logbase2(b) multiplications by the
> usual method (which can be related to the binary representation of b).
> Thus to calculate a^25, for example, we evaluate a^2, a^3, a^6, a^12,
> a^24, a^25. All multiplications being done mod c.
>
> Consider a constant, S, defined by a series of the form
>
> S = sigma(k=0, +infinity)[1/((b^(c*k))*p(k))]
>
> where b and c are positive integers, and p(k) is a polynomial with
> integer coefficients. Note that the digits in the base b expansion of S,
> beginning at position n+1, can be obtained from the fractional part of
> S*b^n. So:
>
> S*b^n mod 1 = sigma(k=0, +infinity)[b^(n-c*k)/p(k) mod 1]
>
> = sigma(k=0, floor(n/c))[(b^(n-c*k) mod p(k))/p(k) mod 1] +
> sigma(k=floor(c)+1, +infinity)[b^(n-c*k)/p(k) mod 1]
>
> For each term of the first summation, the binary exponentiation scheme
> is used to evaluate the numerator. Then floating point arithmetic is
> used to perform the division and add the result to the sum mod 1. The
> second summation, where the exponent of b is negative, may be evaluated,
> as written, using floating point arithmetic. It is only necessary to
> compute a few terms of this second summation, just enough to ensure that
> the remaining terms sum to less than the "epsilon" of the floating point
> arithmetic being used. The final result, a fraction between 0 and 1, is
> then converted to the desired base b.
>
> For pi, this algorithm is slightly slower [by a factor log(log(log(n)))]
> than the very fastest known algorithm which calculates all the digits up
> to and including the nth. However, that algorithm uses
> Strassen-Sch�nhage multiplication - which nobody seems to use in high
> precision computations of pi, preferring the slightly slower but easier
> FFT methods.
> =================================================================
>
> --
>
> Clive Tooth
> http://www.pisquaredoversix.force9.co.uk/
> End of document
------------------------------
Date: Mon, 22 May 2000 15:33:28 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: QUESTIONS About ALGOS !!
tomstd wrote:
> In article <8g7lbp$2sa$[EMAIL PROTECTED]>, "Scott
> Fluhrer" <[EMAIL PROTECTED]> wrote:
> > For that matter, the same goes for the security
> > requirement. Maybe he really is hiding things
> > from his kid sister. In that case, DES has
> > plenty of security.
For a kid sister or brother, a simple XOR might be
enough, except if that silbing is really brilliant
in maths.
> > And, in terms of security, I would, at the
> > present state of the analysis, trust 3DES over
> > any of the AES candidates -- DES has had a *lot*
> > of analysis.
>
> So has blowfish, rc5, cast and IDEA. Big deal.
Yep.
> > Actually, 16 cycles/byte is fast for a block
> > cipher, a stream cipher can go much faster.
> > If you can get the rights to Seal (a nontrivial
> > prospect), that can do 4 cycles/byte. IIRC,
> > ARC4 can do about 7-8 cycles/byte. (And, I
> > don't remember the details of RC5: is 12 rounds
> > a reduced round version?
RC5 is defined in a highly parameterizeable way. You
can use it with any number of rounds you wish. The
"broken" variant is called RC5-32/12/128 : 32 bit,
12 rounds, 128 bit key. But RC5-32/16/* is still
relatively secure, while IMHO RC5-32/12/* is way
too weak for practical use now.
> 12 rounds is the original proposal (which is why
> they list it in the paper specifically). The
> attack requires 2^53 pairs, so it's not practical.
2**53 is only 8 * (10**15) which is 8,000 TB. Hmm.
Not too easy :) But also far from being impossible.
------------------------------
From: Bruce Schneier <[EMAIL PROTECTED]>
Subject: Final Comments from Twofish Team
Date: Mon, 22 May 2000 08:46:38 -0500
They're on the Twofish website, at:
http://www.counterpane.com/twofish-final.html
Bruce
**********************************************************************
Bruce Schneier, Counterpane Internet Security, Inc. Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: Bruce Schneier <[EMAIL PROTECTED]>
Subject: Comments on IPSec and AES
Date: Mon, 22 May 2000 08:47:04 -0500
They're available at:
http://www.counterpane.com/aes-agility.html
Bruce
**********************************************************************
Bruce Schneier, Counterpane Internet Security, Inc. Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: pentium timings
Date: Mon, 22 May 2000 16:29:52 +0200
"Gisle S�lensminde" wrote:
> I haven't tried Tom's code, but most operation systems runs each thread
> for slices of 10-100 ms at a time. On a 100 MHz computer with 10 ms time
> slices, that is 1_000_000 cycles, which means that the probability of a context
> swich in the middle is small if you measure ciphers, which in most cases runs
> on less than 1000 cycles.
A supplementary question: If a run takes such a small time, wouldn't
the initialization time of the thread make out a substantial portion of
the total time measured? Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: 3DES SOURCE
Date: Mon, 22 May 2000 16:31:26 +0200
Karim A wrote:
> Where can I find source code of Triple DES encryption ?
I suppose a proper way is to search for code of DES and build
the 3DES yourself.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Compare 3DES's.
Date: Mon, 22 May 2000 16:30:22 +0200
Jonathan Thornburg wrote:
> Take a look at
>
> Stefan Lucks,
> "Attacking Triple Encryption,"
> Fast Software Encryption '98, Volume 1372 of Lecture Notes in
> Computer Science (S. Vaudenay, ed.), Springer-Verlag, 1998.
> http://th.informatik.uni-mannheim.de/m/lucks/papers.html
Another relevant paper is:
H. Handschuh, B. Preneel, On the security of double and 2-key
triple modes of operation. L. Knudsen (Ed) 6th FSE, LNCS 1636.
Springer-Verlag, 1999.
It seems however that all such attacks become impractical if one uses
variable keys. In fact, in another thread, DJohn37050 mentions situations
where keys get changed as often as every 4 blocks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: More on Pi and randomness
Date: Mon, 22 May 2000 16:29:58 +0200
Clive Tooth wrote:
> Consider a constant, S, defined by a series of the form
>
> S = sigma(k=0, +infinity)[1/((b^(c*k))*p(k))]
>
> where b and c are positive integers, and p(k) is a polynomial with
> integer coefficients. Note that the digits in the base b expansion of S,
> beginning at position n+1, can be obtained from the fractional part of
> S*b^n. So:
>
> S*b^n mod 1 = sigma(k=0, +infinity)[b^(n-c*k)/p(k) mod 1]
>
> = sigma(k=0, floor(n/c))[(b^(n-c*k) mod p(k))/p(k) mod 1] +
> sigma(k=floor(c)+1, +infinity)[b^(n-c*k)/p(k) mod 1]
>
> For each term of the first summation, the binary exponentiation scheme
> is used to evaluate the numerator. Then floating point arithmetic is
> used to perform the division and add the result to the sum mod 1. The
A question of ignorance: How about the rounding errors in these divisions?
>
> second summation, where the exponent of b is negative, may be evaluated,
> as written, using floating point arithmetic. It is only necessary to
> compute a few terms of this second summation, just enough to ensure that
> the remaining terms sum to less than the "epsilon" of the floating point
> arithmetic being used. The final result, a fraction between 0 and 1, is
> then converted to the desired base b.
Is the 'a few terms ..... just enough ...' somehow precisely determined
by a formula for estimation or is done heuristically?
Thanks.
M. K. Shen
------------------------------
Date: Mon, 22 May 2000 16:26:21 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: 3DES SOURCE
Mok-Kong Shen wrote:
> Karim A wrote:
>
> > Where can I find source code of Triple DES encryption ?
>
> I suppose a proper way is to search for code of DES and build
> the 3DES yourself.
>
> M. K. Shen
Fine. There is, for example, a DES source at
http://www.btinternet.com/~brian.gladman/cryptography_technology/index.htm
It was mainly implemented for comparing it with the AES candidates. If
you do not have a little endian 32 bit CPU, you might run into trouble,
however. Mr. Gladman only checked this on the x86 family.
------------------------------
From: "Clive Tooth" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: More on Pi and randomness
Date: Mon, 22 May 2000 15:36:15 +0100
Trevor L. Jackson, III wrote in message <[EMAIL PROTECTED]>...
>Clive Tooth wrote:
>
>> "Trevor L. Jackson, III" wrote:
>>
>> > Guy Macon wrote:
>> >
>> > > In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>> > >
>> > > >I understand the Nth hexit of pi, irrespective of the value of N, to
be
>> > > >calculable using the equation derived by Borwein, Borwein and
Plouffe.
>> > > >The 400 billionth hexit of pi has been thus calculated.
>> > >
>> > > Really?!? (not questioning you, just suprised). Does the time to
compute
>> > > the answer get larger as N gets larger? Linearaly? Exponentialy?
>> >
>> > Since the formula is based upon N, it's implementation grows as the log
of N.
>>
>> No.
>
>Interesting.
>
>> The time required to calculate the Nth _hex_ digit of pi by these
>> non-memory-intensive methods is at most O(N*(log(N))^O(1)).
>
>A simplistic implementation in multi-precision arithmetic requires only a
few MP multiplies
>and an MP division to produce a term of the series. Since the MP
operations are O(log N)
>your estimate of the overall work implies that O(N) terms of the series are
required to
>produce a digit.
>
>Why is that? (I thought the number of terms was bounded by a small number)
O(N) terms _are_ required. I did attempt an explanation of this at the end
of my post that you quoted, but let me give an example.
Let S = sigma(k=0, +infinity)[1/(16^k*(100k+7))]
(The well-known "nth hex digit of pi" identity is the sum of 4 things
similar to that.)
So, S is some well-defined real number. Suppose we want to know its 11th,
12th and 13th hexadecimal digits. These hex digits are the first three hex
digits of the number S*16^10.
S = sigma(k=0, +infinity)[1/(16^k*(100k+7))]
So
16^10*S = sigma(k=0, +infinity)[16^(10-k)/(100k+7)]
= 16^10/7 + 16^9/107 + ... + 16^2/807 + 16^1/907 + 16^0/1007 + ...
So, we just need the fractional part of each term.
Set T to 0.
Work out 16^10 mod 7 (using single precision integer arithmetic), divide the
answer by 7 using ordinary floating point arithmetic, add the result to T.
Work out 16^9 mod 107, divide the answer by 107, add the result to T.
And so on.
Go on until the quantity we are adding to T is less than 16^-3 (a few more
terms may be required). In general we will need to take a few more than N
terms (about 14 in this case).
Finally, take the fractional part of T, multiply by 16^3, convert this to
hex, and we have hex digits 11, 12 and 13 of S.
--
Clive Tooth
http://www.pisquaredoversix.force9.co.uk/
End of document
------------------------------
From: [EMAIL PROTECTED] (Richard Herring)
Subject: Re: Is OTP unbreakable?
Date: 22 May 2000 14:32:07 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, Paul Koning ([EMAIL PROTECTED]) wrote:
> Richard Herring wrote:
> >
> > In a...
> > > Still, OTP has two weaknesses though:
> > >...
> > 3. An attacker can modify the message. If he knows the position of
> > some item within the plaintext, he can change it to any other string
> > with the same length.
> Easy to fix: calculate a hash (e.g., HMAC), append it, and encrypt
> the result. The security provided by OTP protects the hash as well,
> though you do want a good hash -- for example, an IP checksum will
> not do at all.
Sure. I'm just pointing out that the "classical" OTP may be totally
*secret* but that's not the same thing as being *secure*.
--
Richard Herring | <[EMAIL PROTECTED]>
------------------------------
From: Gordon Walker <[EMAIL PROTECTED]>
Subject: Re: Interpretation of Hitachi patent claims
Date: Mon, 22 May 2000 15:52:46 +0100
On Sat, 20 May 2000 02:09:44 -0600, Jerry Coffin <[EMAIL PROTECTED]>
wrote:
>In case you care, these may be the longest sentences you've ever
>seen, but as claims go they're really not terribly long -- I've seen
>some that went on (still as a single sentence) for over a page.
Off topic:
George Harrison, the maker of the first timepiece accurate to measure
longitude at sea wrote a book in which the first sentence went on for
178 pages.
--
Gordon Walker
------------------------------
Date: Mon, 22 May 2000 17:00:47 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Final Comments from Twofish Team
Bruce Schneier wrote:
> They're on the Twofish website, at:
> http://www.counterpane.com/twofish-final.html
Whow. Twofish was my favorite AES cipher anyway (its
paper was the second least confusing after RC6, it had
no patent claims, it is highly scaleable for speed or
size, etc), but I didn't realized before that it is
THAT good !
It is however funny, that for any of the five AES
candidates, there seem to be people which fight for
it in this NG. Even Mars still has its fans :))
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: AES final comment deadline is May 15
Date: Mon, 22 May 2000 11:04:05 -0400
Mok-Kong Shen wrote:
>
> DJohn37050 wrote:
>
> > Key agility is the ability to change keys fast or not. Contrast with
> > encrypting a large file with one key. The most extreme case is changing a key
> > for every block. In practise, it is say 4 blocks.
>
> Earlier I learned that for DES hardware the generation of the
> subkeys could be done parallel with the round processing, i.e.
> available just in time for the next round. Doesn't that fact at
> least greatly reduce the significance of the key agility issue?
You've just shown that DES has excellent key agility.
Now Look at Blowfish. If you have to switch keys frequently,
you can't afford to do the key schedule each time (it's far
too slow). So instead you have to store the scheduled keys
in memory and switch those. That is fast -- but it also consumes
a lot of memory. So Blowfish does not have good key agility.
A cipher gets a good rating for key agility if you afford
to switch keys every few blocks *without* consuming unreasonable
amounts of memory. (In judging "reasonable" you should assume
that a system needs to have on the order of 1000 or 10,000 active
keys -- which suggests that consuming 1000 bytes per key is
probably not all that reasonable.)
paul
--
!-----------------------------------------------------------------------
! Paul Koning, NI1D, D-20853
! Lucent Corporation, 50 Nagog Park, Acton, MA 01720, USA
! phone: +1 978 263 0060 ext 115, fax: +1 978 263 8386
! email: [EMAIL PROTECTED]
! Pgp: 27 81 A9 73 A6 0B B3 BE 18 A3 BF DD 1A 59 51 75
!-----------------------------------------------------------------------
! "A system of licensing and registration is the perfect device to deny
! gun ownership to the bourgeoisie."
! -- Vladimir Ilyich Lenin
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
