Cryptography-Digest Digest #831, Volume #11 Sun, 21 May 00 18:13:00 EDT
Contents:
Re: Q: Recording on magnetic cards (Troed)
Re: More on Pi and randomness (Clive Tooth)
Re: Interpretation of Hitachi patent claims (Mok-Kong Shen)
Re: Reasonably secure OTP passing (Mok-Kong Shen)
Re: Interpretation of Hitachi patent claims (Mok-Kong Shen)
Re: Reasonably secure OTP passing (Mok-Kong Shen)
Re: NSA hardware evaluation of AES finalists (David A. Wagner)
Re: NSA hardware evaluation of AES finalists (David A. Wagner)
pentium timings (tomstd)
tea in x86 assembler (tomstd)
Blowfish Claims ... something not right (tomstd)
Re: Plain simple (?) question (Mok-Kong Shen)
Re: pentium timings (Mok-Kong Shen)
Re: Q: Recording on magnetic cards (Mok-Kong Shen)
Re: Reasonably secure OTP passing (Sundial Services)
Re: Blowfish Claims ... something not right ("Kasper Pedersen")
Re: Blowfish Claims ... something not right ("Kasper Pedersen")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Troed)
Subject: Re: Q: Recording on magnetic cards
Reply-To: [EMAIL PROTECTED]
Date: Sun, 21 May 2000 19:10:07 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>a chip. BTW, why do you think that it is 'necessary' to
>secretly hide the presence of a chip? The normal telephone
Why _not_ when the chip isn't supposed to ever be in contact with
anything?
___/
_/
------------------------------
From: Clive Tooth <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: More on Pi and randomness
Date: Sun, 21 May 2000 20:57:43 +0100
"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.
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)).
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
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Interpretation of Hitachi patent claims
Date: Sun, 21 May 2000 22:32:05 +0200
Jerry Coffin wrote:
[EMAIL PROTECTED] wrote
> Now what you have classified as '!' and '@' are, as
> you pointed out, not clearly defined and general (all
> > encompassing??) and fuzzy. Such are far from being
> > acceptable in any serious preliminary specifications of
> > any software projects, not to mention prototype coding.
> > Thus what the patent claims is indefinite, incomplete,
> > ambigious, unclear and misleading.
>
> For better or worse, that doesn't necessarily follow. It may simply
> be that _any_ method of deriving that particular piece of data is
> covered. I don't have the wording of the claim handy at the moment,
> but if a court interpreted it as a "means claim", then they might be
> restricted to means that are outlined in the disclosure of the patent
> or "reasonable equivalents thereof."
I don't think that a patent could be granted to applying ANY method
of deriving pieces of data. Note that all operations on these data
are known, i.e. prior art, in the present case. Otherwise one could
apply a patent that cover ALL encryption methods, known or ever
to be invented in the future.
> > Consequently the
> > patent should be considered to be invalid.
>
> _If_ the disclosure of the patent didn't provide any suggestions as
> to how this derivation might take place, and/or it was important that
> the derivation be done in a way that isn't known to a person of
> ordinary skill in the art, then the patent might well be invalid.
> Based only on this claim, by itself, that would be a nearly
> impossible argument to make though.
Thus there does seem to be good prospective that Hitachi's
claims are futile.
> > Anyway,
> > the scheme has a certain structure consisting of eight
> > steps. So any other scheme differing either in the
> > nature of the individual steps or in the number of
> > steps are certainly not covered by the scheme.
>
> Yes and no -- simply adding more steps would NOT (by itself) prevent
> the claim from applying. If you added something like more steps in
> the middle, it migth no longer apply; if you simply added more to the
> beginning or end, but those steps remained intact somewhere in the
> overall sequence, it would almost certainly still apply.
O.k. Then surely no AES candidate conflicts with Hitachi's patents.
> > In the above, I have attempted to develop some
> > arguments that eventually could be useful to refute
> > Hitachi's claims. (The claim 1 and 10 are basically of
> > the same nature and can be treated together.) It would
> > be nice, if a number of persons of the group would
> > attempt the same task so that with joint efforts there
> > may soon result in something that is really strong and
> > useful.
>
> I might take a shot at it, but I don't think most of the arguments
> you've advanced are very strong the way they sit right now.
That's why I was solicitating work from others of the group.
> > On the other hand, does anyone know a good way to
> > 'elicite' the opinions of the patent experts of NIST,
> > IBM and RSA?
>
> I'm not at all sure NIST _has_ any patent experts. Most large
> companies (including IBM) DO, but getting their time devoted to this
> would probably require convincing some high-ranking IBM executives
> that it was going to make some sort of difference to IBM to do it.
> I'm not ready to say that's impossible, but I'm not at all sure how
> you'd even make a serious attempt at it either.
>
If IBM is any serious with its submission of MARS, the management
should let the patent issue be clarified, I believe.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Reasonably secure OTP passing
Date: Sun, 21 May 2000 22:32:25 +0200
John Savard wrote:
> Here's another thought:
>
> Send, enciphered very thoroughly, a whole bunch of OTPs, each of which
> comes with an identifying number. Now, the cryptanalyst also has to
> determine which OTP one's message is related to...
>
> and if a returning message is sent with a header (all also enciphered
> thoroughly in a conventional system) identifying _two_ of the OTPs,
> and starting points within them, the cryptanalyst has quite a search
> task ahead before even starting the difficult job of analyzing the
> correlations between two enciphered texts.
I think that within the framework of practical requirement, i.e. we
don't need 'absolute' security, the two OTPs could be replaced
by something that do not exactly qualify being (ideal) OTP. On the
other hand, a bit inferior quality could plausibly be compensated by
using more streams and starting points than the two streams
you suggested. And, persuing the idea further, one could use
a fairly good encryption algorithm to encrypt known texts (books
etc.) to generate the streams. That means, one doesn't need to
transmit large amounts of streams for later use in encrypting
messages. One needs only a way to communicate to the partner
the known texts (books etc.), the starting points of these and
perhaps also the encryption algorithm used in order to obtain
the streams for application of the scheme. Some time back I
sketched the idea above. Using further a superencipherment
with another algorithm as you indicated in the post certainly
would render the stuff more tough for the analyst.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Interpretation of Hitachi patent claims
Date: Sun, 21 May 2000 22:32:15 +0200
Jerry Coffin wrote:
> In article <dlAV4.4$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> says...
> > Has anyone compared the Hitachi patents to the two RC5 patents?
>
> Not that I know of. Do you happen to know the numbers of those
> patents?
>
Would Tom St Denis, who had received a letter from RSA about
patent issue of RC5, provide that information?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Reasonably secure OTP passing
Date: Sun, 21 May 2000 22:32:41 +0200
Guy Macon wrote:
> It seems to me that, for most users, the following is more accurate:
>
> [1] They have some clues know which available cryptosystems are better
> or worse, but they really can't be sure.
>
> [2] They currently use what they believe to be the best available
> cryptosystem, but they are not sure that thay chose wisely.
>
> In that case, they can't make tradeoffs between using a better
> cryptosystem and improving the present scheme. Instead they must
> make tradeoffs between thier valuation of various costs such as
> bandwidth, time to learn the new system, etc., the estimated added
> security of the change, the estimated resources of the attacker,
> and the cost of having somneone crack the cryptosystem.
I agree. If one can afford, I suppose one should consider using
multiple encryptions and other possiblities such as incresing the
number of rounds. The decision is in effect not fundamentally
different from those that the business people always make
in their undertakings. It's an economical decision in the end.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: NSA hardware evaluation of AES finalists
Date: 21 May 2000 13:35:07 -0700
In article <[EMAIL PROTECTED]>,
Ken Lamquist <[EMAIL PROTECTED]> wrote:
> The encryption times of the AES finalists differed significantly, as
> you can see from the following table. Rijndael is well ahead of the
> others, which in my view makes it the leading candidate.
>
> time area transistors
> Rijndael 288.8 46.36 1029,046
> Serpent 632.6 23.27 345,483
[...]
Is this the right metric? If you have extra area, won't you typically
be able to add extra encryption units? I don't have enough experience to
know whether you can, but if you can indeed add extra encryption engines,
Rijndael's lead here will evaporate, so it seems like a rather important
question to ask before relying on those numbers too heavily.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: NSA hardware evaluation of AES finalists
Date: 21 May 2000 13:37:59 -0700
In article <[EMAIL PROTECTED]>,
Ken Lamquist <[EMAIL PROTECTED]> wrote:
> I now turn to implementation cost for the various finalists. The
> following table gives information on minimal size implementations. [...]
> I am not sure how important this metric is.
I'm not sure, either, but the local FPGA guru I know claims that it
is an important issue for implementations on reconfigurable hardware.
See also Nick Weaver's paper in AES3 for more analysis on this topic.
------------------------------
Subject: pentium timings
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 21 May 2000 13:51:51 -0700
Anyone interested in timing their code in cycles on a pentium
class computer (i.e k6, 586, ppro, MII, etc...) can use the code
I developped (well it's not my idea, I just put it together
nicely) here
http://www.tomstdenis.com/timer.zip
It requires nasm+djgpp to build, but a nasm compiled copy of the
include assembler file is included, so all you really need is
djgpp.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: tea in x86 assembler
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 21 May 2000 14:01:17 -0700
Getting way bored here... You can fetch a copy of xTEA in x86
assembler. It runs fairly slowly, but again the algorithm is
none to fast.
http://www.tomstdenis.com/teaasm.zip
On my k6-2 it fetches 720 cycles/block either way, or 90
cycles/byte. Which is 5.71 times slower then RC5 at 12 rounds
(see http://www.tomstdenis.com/rc5asm.zip).
Feel free to use teaasm, or tell me about optimizations I could
try. However please do not use the rc5 code for anything except
educational use.
Thanks,
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Blowfish Claims ... something not right
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 21 May 2000 14:11:48 -0700
According to [1] Blowfish on a pentium pro takes 9 cycles per
round. I would really like to see that code that runs in 9
cycles, that does three xors, 1 add and 5 lookups.
Somehow either the guy is a genius, or he is lying.
Tom
[1] http://www.counterpane.com/speed.html
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Plain simple (?) question
Date: Sun, 21 May 2000 23:41:02 +0200
Alain CULOS wrote:
> Anyone here knows which encoding algorithm/implementation uses only those
> printable ascii characters except lowercase letters ?
> What about something that contains a left quote and a right quote (that could
> pass, there are ascii equivalents), but now, what about left double quote and
> right double quote, this ain't ascii ??? The whole lot of the rest is ascii.
You don't have to bother about the code problem. Your
PC is set to a certain language, say, French. Anything
you can type in on the keyboard will be stored as 8 bit
byte, which is fine for block ciphers or stream ciphers,
according to the national standard of the code. If your
partner has a PC that is set to the same language, he
doesn't have any problem to read or print you message.
For diverse international languages, you might need
however the Unicode and the software for displaying
them.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: pentium timings
Date: Sun, 21 May 2000 23:43:57 +0200
tomstd wrote:
> Anyone interested in timing their code in cycles on a pentium
> class computer (i.e k6, 586, ppro, MII, etc...) can use the code
> I developped (well it's not my idea, I just put it together
> nicely) here
A question of curiosity: How do you get the time to sufficient accuracy?
On a computer, e.g. PC, there are other tasks running concurrently.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Recording on magnetic cards
Date: Sun, 21 May 2000 23:47:11 +0200
Troed wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> >a chip. BTW, why do you think that it is 'necessary' to
> >secretly hide the presence of a chip? The normal telephone
>
> Why _not_ when the chip isn't supposed to ever be in contact with
> anything?
One acts normally in economical ways. What isn't needed is not done.
Why should the designer take the trouble to hide the chip? Could you
think of a reason? If your message has no secret, do you bother
to encrypt it?
M. K. Shen
------------------------------
Date: Sun, 21 May 2000 14:48:46 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Reasonably secure OTP passing
Not to mention the poor cipher-clerk. ANY transmission-error, human
goof-up or what-have-you ("[**]it happens") and the two parties have no
choice but to start over.
Furthermore, "a chain is as strong as its WEAKEST link." One of the
vulnerabilities of the OTP is certainly the problem of distributing the
pads securely. But, there is another problem too...
To avoid having a lot of exposure to the pad-distribution process, the
natural tendency is to distribute really huge pads. Well, WHAT IF one
of those pads is either stolen, or simply lost? What if our harried spy
somehow leaves the CD where his cat can play with it? Either you have
-lost- a huge chunk of your bandwidth which must now be laboriously
replaced ... or, in the case of a stolen (or covertly duplicated) pad
... you have -exposed- a huge number of messages to interception! The
human-beings who use OTPs will be relucant to put themselves through the
onerous task of replacing yet-another-pad and resynchronizing with the
sender, if they even know that a theft did take place.
The synchronization-problem is not to be taken lightly either. Pad
segments must never be re-used, and the sender must be perfectly aligned
with the receiver.
If I could snatch a message and successfully fiddle with the alignment
information you need to decode it, "well, maybe I can't read it, but now
YOU can't read it either! Heehee!" Actually a crippling problem.
>Mok-Kong Shen wrote:
>[...] Using further a superencipherment
> with another algorithm as you indicated in the post certainly
> would render the stuff more tough for the analyst.
>
> M. K. Shen
------------------------------
From: "Kasper Pedersen" <[EMAIL PROTECTED]>
Subject: Re: Blowfish Claims ... something not right
Date: Sun, 21 May 2000 22:06:22 GMT
"tomstd" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> According to [1] Blowfish on a pentium pro takes 9 cycles per
> round. I would really like to see that code that runs in 9
> cycles, that does three xors, 1 add and 5 lookups.
>
> Somehow either the guy is a genius, or he is lying.
Nope. 9 clocks means 18 execution opportunities on the pentium-1. It _just_
fits in 9
clocks. I tried, and it really works.
on the K6/k6-2/-3 and P2/3 it's slightly slower because of the architecture
(they sacrificed something to get higher clock frequencies)
Mine runs at 11 clocks/round on the K6-2, 13 on the P2, 12 on the P3.
I didn't have a P2/P3 to develop on, so it might be possible to squeeze a
bit more.
The Athlon does it in 25% less cycles than the P3, which translates to a 33%
advantage.
/Kasper
(mail kasper at traceroute dot dk to receive proof)
------------------------------
From: "Kasper Pedersen" <[EMAIL PROTECTED]>
Subject: Re: Blowfish Claims ... something not right
Date: Sun, 21 May 2000 22:06:23 GMT
"tomstd" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> According to [1] Blowfish on a pentium pro takes 9 cycles per
> round. I would really like to see that code that runs in 9
> cycles, that does three xors, 1 add and 5 lookups.
>
> Somehow either the guy is a genius, or he is lying.
Nope. 9 clocks means 18 execution opportunities on the pentium-1. It _just_
fits in 9
clocks. I tried, and it really works.
on the K6/k6-2/-3 and P2/3 it's slightly slower because of the architecture
(they sacrificed something to get higher clock frequencies)
Mine runs at 11 clocks/round on the K6-2, 13 on the P2, 12 on the P3.
I didn't have a P2/P3 to develop on, so it might be possible to squeeze a
bit more.
The Athlon does it in 25% less cycles than the P3, which translates to a 33%
advantage.
If you try running the old P-1 code on a 'modern' cpu, you get less than
half that performance. It was optimized for the Pentium 2-pipe architecture,
not the architecture they use now.
/Kasper
(mail kasper at traceroute dot dk to receive proof)
------------------------------
** 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
******************************
