Cryptography-Digest Digest #893, Volume #12 Wed, 11 Oct 00 01:13:00 EDT
Contents:
Re: Rijndael implementations ("Paul Pires")
Re: FTL Computation ([EMAIL PROTECTED])
Re: Rijndael has a very good S-Box (Tom St Denis)
Re: FTL Computation ("Paul Lutus")
Re: Modular Exponentiation (Muzaffer Kal)
Re: A new paper claiming P=NP (Daniel A. Jimenez)
Re: The science of secrecy: Simple Substition cipher (UBCHI2)
Re: NSA quote on AES (Greggy)
Re: My view of election. (Greggy)
Re: AES Runner ups (Greggy)
Re: A new paper claiming P=NP (glenn)
Re: Why trust root CAs ? ("Lyalc")
Re: A new paper claiming P=NP (Mark Carroll)
Re: AES Runner ups (Jim Gillogly)
----------------------------------------------------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Rijndael implementations
Date: Tue, 10 Oct 2000 18:45:11 -0700
Jim Gillogly <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Paul Pires wrote:
> >
> > <snip>
> > >
http://www.btinternet.com/~brian.gladman/cryptography_technology/rijndael/in
> > > dex.html
> > >
> > > where I have just updated my own implementation (in C++). On the 200MHz
> > > Intel reference platform it offers around 70Mbits/second using large
tables
> > > but other options are provided as well.
> >
> > Hope you don't mind a dumb question. If a Megabyte is 1024^2 bits (1.048576
> > million
> > bytes) as opposed to1 million bytes, is a Mbit 1 million bits or something
else?
>
> Yes, 1 Mbit or Mb is 2^20 bits to an engineer. To a marketer it may be 10^6
bits,
> just as a MB may be 10^6 bytes, depending on what they need for their
marketing
> campaign.
>
> 70Mbits/sec is an excellent speed for a block cipher in software on a 200MHz
> PPro. Network throughput is usually measured in bits/s, and storage is
usually
> measured in bytes.
Thanks for the answer. I thought it was so but I hate to assume.
Seems quick to me. Doing my conversion.. (now that I know what it is) it looks
like
about 22.9 clocks per byte (in C++) compared to 16.1 for twofish (Highly
optimized
assembler?) if I remember right from the home page.
Thanks
Paul
> --
> Jim Gillogly
> Mersday, 20 Winterfilth S.R. 2000, 00:35
> 12.19.7.11.4, 7 Kan 7 Yax, Eighth Lord of Night
------------------------------
Date: Tue, 10 Oct 2000 21:50:07 -0700
From: [EMAIL PROTECTED]
Crossposted-To: sci.astro,sci.physics.relativity,sci.math
Subject: Re: FTL Computation
ca314159 wrote:
>
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > ca314159 wrote:
> > >
> > > If the projection of a spot of light can virtually move FTL
> > > then so too can the projected images of a slide rule's slides.
> > > The computation 'in effect', takes place FTL.
> > >
> >
> > But the time between when you move the slide and you see
> > the projection is still the round trip light travel time
> > to the thing you're projecting the slide onto.
>
> You're right; I/O is a bottleneck.
> That's not my point though.
>
It's not an I/O limitation. It's a limitation on
how fast you can transmit a message from point to
point.
> Whether you call this effect lighthouse, waterhose, headlight
> or scissors... it can be used to do very interesting things.
> I don't just think so, I know so.
>
> >
> > The real limitation is how fast you can transmit information.
> >
>
> First, one has to know what "information" is.
> What's your definition ?
>
I want to transmit a signal from one observer to another. If I use the
lighthouse idea, I can send information from a sender to one observer
at time t and then information to a second observer at t + dt
where the spatial separation of the two receivers is dx
and dx/dt > c. But I'm sending two different signals to two
different receivers. The inforamtion goes from the sender
to either receiver at c. The two receivers can't compare what
they receive and deduce a message from it (other than
on bit of information) until they can exchange observations
about what they received.
Information is a stream of bits going from a sender to
a single receiver. If you send one bit to one receiver
and another to a different receiver, they need to
communicate with each other to figure out what the two
bits are and the information is not travelling faster than
c.
The lighthouse effect can be used to do exactly what
SR predicts it to do. And you can't use it to do
FTL computation because it's spraying different parts
of the computation over events need to communicate themselves
to complete the computation.
John Anderson
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Rijndael has a very good S-Box
Date: Wed, 11 Oct 2000 01:45:26 GMT
In article <[EMAIL PROTECTED]>,
"Paulo S. L. M. Barreto" <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
> >
> > I am replying to all three of your posts...
> >
> > In article <[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] (John Savard) wrote:
> > > Using a small BASIC program, I searched for differential
> > > characteristics, and linear (well, affine? over GF(2^8), anyhow)
> > > approximations to the S-box.
> >
> > An affine linear approximation is something like y = a xor b xor 1.
> >
> > > The differential behavior of the Rijndael S-box is simply
astounding.
> >
> > Dude check out my website, I have code that makes "good" sboxes of
> > various sizes (odd or even bit sizes). The sbox is based on
> > multiplicative inversion in a GF. It was used by Matsui in Misty
and
> > by Tom St Denis in TC5.
> >
> > > If you consider S(i) xor S(i xor diff), for all 256 values of i,
this
> > > expression will often take on a value zero or two times instead of
> > > once, as is ideal...and may take on one value _four_ times.
> > >
> > > That's as strong as any differential characteristic of the S-box
gets.
> >
> > Technically there are 255 '4' in the xor-pair table and the rest is
> > zeros and twos. That's not the best an sbox could be in theory
though.
>
> Yes, it is. The differential uniformity of an S-box is determined by
> the maximal entry in its difference table, and over GF(2^8) there will
> *always* be at least one '4' entry there. Whether there are 255 or
any
> other count of occurrences of '4' is irrelevant for a byte-oriented
> cipher like Rijndael.
>
Actually that is wrong. If the sbox has one '4' and it can't be used
in an attack such as FF -> EF and nothing goes to FF with a prob of
4/256 then the attack is bounded by the 2/256 components as well.
> > > As for linear approximations, things are a bit better for the
> > > cryptanalyst, but not by much.
> > >
> > > S(i) is equal to a*i xor b (where the multiplication is done in
> > > GF(2^8)) as many as 13 times out of 256, where a=23 and b=163.
> > >
> > > The second best linear approximation *also* occurs for a=23, this
time
> > > with b=56; this one is true 11 times.
> > >
> > > For a=1 and a=23, there are multiple "approximations" that show
up,
> > > and most commonly they are true around 8 times.
> > >
> > > The approximation a=147 and b=99 is true 9 times, and the only
other
> > > value of b that gives an approximation true more than 4 times is
229,
> > > with a=147 b=229 true 5 times, so this approximation may have
less of
> > > a "noise level" to contend with.
> > >
> > > On the other hand, if the multiple approximations at either a=1 or
> > > a=23 can be made to work together, to provide a strong linear
> > > approximation - but with _partial information_, something might be
> > > done.
> >
> > All linear approximations are biased (affine/linear) by at most 16
> > times. So given for example (y0 = x0 xor x1 xor x7) that will hold
in
> > the sbox for at most 112/256 or 144/256 times. When the
approximation
> > deviates from 128/256 times it can be exploited.
>
> The linear behaviour of the x^{-1} mapping over GF(2^8) is optimal, as
> is the differential behaviour.
The differential behaviour is good, but not optimal.
> > Of course the inverse sbox has the same low xor-pair, all you did is
> > transpose the xor-pair matrix!
> >
> > In the case of Rijndael an affine transform is applied after the
sbox
> > lookup to help muddle the low non-linear order of the output.
>
> What do you mean by "non-linear order"? Your usage of this expression
> is certainly nonstandard. Rijndael's S-box has maximal nonlinear
order
> (namely, 7). Check the Handboook of Applied Cryptography for details
on
> this concept.
>
> The affine transform is applied to prevent interpolation attacks,
which
> -- in the case of the x^{-1} mapping -- are not based on this
mapping's
> nonlinear order but rather on its algebraic simplicity (the polynomial
> expansion has a single term; after the affine transform it has nine).
True, thanks for clearing that up.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Paul Lutus" <[EMAIL PROTECTED]>
Crossposted-To: sci.astro,sci.physics.relativity,sci.math
Subject: Re: FTL Computation
Date: Wed, 11 Oct 2000 02:03:40 GMT
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Paul Lutus wrote:
>
> > That is how it is a mixing of terms. But it can get worse -- the OP made
an
> > argument that relied on smoke, not physics. In a manner of speaking he
said
> > that, if he transmitted the word "dictionary," and if the receiver knew
how
> > to translate that token into an actual dictionary, the result would
exceed
> > the original communication channel's capacity, therefore presto -- FTL!
>
> This is incorrect because the amount of information transmitted does not
depend
> upon the later translation process.
I am not saying what is correct, I am simply reporting what the OP tried to
say. Clearly it is not correct, a point I made already.
--
Paul Lutus
www.arachnoid.com
------------------------------
From: Muzaffer Kal <[EMAIL PROTECTED]>
Crossposted-To: comp.arch.fpga,comp.lang.vhdl
Subject: Re: Modular Exponentiation
Date: 11 Oct 2000 02:05:58 GMT
Reply-To: [EMAIL PROTECTED]
Try the following paper. It has some implementation details too.
http://www.computer.org/tc/tc2000/t0170abs.htm
Muzaffer
www.dspia.com
------------------------------
From: [EMAIL PROTECTED] (Daniel A. Jimenez)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 10 Oct 2000 21:07:58 -0500
In article <oLNE5.6425$[EMAIL PROTECTED]>,
Timothy Chow <[EMAIL PROTECTED]> wrote:
>In article <8s08ek$f82$[EMAIL PROTECTED]>,
>David A Molnar <[EMAIL PROTECTED]> wrote:
>>Out of curiosity, is there a list of famous, but mistaken, "proofs" that
>>P = or != NP (or other complexity theory results) ? Papadimitriou's book
>>mentions a mistaken proof that integer linear programming was in P, and a
>>few months ago I saw a mistaken paper trying to show that NL != NP.
>
>I don't know of a list, but I think Edward Nelson claimed a proof of
>P != NP a couple of years ago. He got as far as planning a series of
>seminars where he would explain his proof before he found an error and
>withdrew the claim. However, I imagine that it's difficult to get a
>hold of his preprint, if indeed he ever produced one.
There was a paper by E.R. Swart and S.J. Gismondi being circulated a
few years ago showing P=NP; I think the proof had something to do with
the graph isomorphism problem, which isn't known to be NP-complete, but
they somehow generalized the algorithm to work for the TSP. As I recall,
a few weeks later one of the authors retracted the claim, saying the paper
shouldn't have been released because it wasn't ready yet.
--
Daniel Jimenez [EMAIL PROTECTED]
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
" " -- John Cage
------------------------------
From: [EMAIL PROTECTED] (UBCHI2)
Subject: Re: The science of secrecy: Simple Substition cipher
Date: 11 Oct 2000 02:50:02 GMT
That's a neat program thanx.
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: NSA quote on AES
Date: Wed, 11 Oct 2000 02:41:54 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> Greggy wrote:
> > > That has already been stated up front by NIST. AES is intended
> > > for use to secure sensitive-but-unclassified (SBU) information.
> > Well, that settles it for me. I won't be using it for any of
> > my "classified" information...
> > > An example would be competitive-procurement records.
> > But my classified information is like my SS# or credit card number.
> > The latter is used for my personal procurement over the internet.
So I
> > won't be procuring with AES it seems...
>
> You're being silly or obtuse. "Classified" for US governmental
> purposes is well defined (and based on potential impact on the
> national security). SBU means not having significant impact
> on national security, but still needing protection for other
> reasons, such as privacy.
>
pragmatic...
--
If I were a cop, I would refuse to go on any no knock raid.
But then, I am not a cop for basically the same reasons.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: My view of election.
Date: Wed, 11 Oct 2000 02:50:34 GMT
It is well known that the WNO wants the US military out of the way.
Get with it. Read www.devvy.com and learn what the hell is going on in
our country.
> I worked at a base and have talked to people since I have
> left. If you think we are safer after Clinton and want more
> of the same vote for Gore. He thinks things are great.
>
> But check out the link below
> http://www.opinionjournal.com/columnists/mhelprin/?id=65000400
> It is a fact since I retired most honest people I know
> who have been involved in this area agree, We are going down
> hill very fast. I am not sure that Bush even has an idea
> how bad it is. But think before you vote.
>
> If you think this is a poor topic to write about don't read it.
> I feel Gore will do more to keep crypto closed then Bush. If you
> feel defferent. Write a response why Gore would be better for us.
>
> David A. Scott
> --
> SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
> http://www.jim.com/jamesd/Kong/scott19u.zip
> Scott famous encryption website **now all allowed**
> http://members.xoom.com/ecil/index.htm
> Scott LATEST UPDATED source for scott*u.zip
> http://radiusnet.net/crypto/ then look for
> sub directory scott after pressing CRYPTO
> Scott famous Compression Page
> http://members.xoom.com/ecil/compress.htm
> **NOTE EMAIL address is for SPAMERS***
> I leave you with this final thought from President Bill Clinton:
>
--
If I were a cop, I would refuse to go on any no knock raid.
But then, I am not a cop for basically the same reasons.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: AES Runner ups
Date: Wed, 11 Oct 2000 02:57:58 GMT
In article <8ru7a6$ak5$[EMAIL PROTECTED]>,
Greggy <[EMAIL PROTECTED]> wrote:
> So if Rijndael is the winner, are there any runner ups that would take
> its place if a significant weakness were discovered soon?
>
> --
> If I were a cop, I would refuse to go on any no knock raid.
> But then, I am not a cop for basically the same reasons.
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
Let me rephrase - has the government stated any one of the other five
finalists would be their backup deployment strategy if a problem was
uncovered with Rijndael on some type of official level?
--
If I were a cop, I would refuse to go on any no knock raid.
But then, I am not a cop for basically the same reasons.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: glenn <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Wed, 11 Oct 2000 06:34:39 +0300
On 10 Oct 2000 21:24:34 GMT, [EMAIL PROTECTED] (Bill Unruh) wrote:
>In <[EMAIL PROTECTED]> Dima Pasechnik <[EMAIL PROTECTED]> writes:
>
>>Stas Busygin <[EMAIL PROTECTED]> writes:
>
>>> Paul Rubin wrote:
>>> >
>>> > Any chance of providing a pdf file? The .ps.zip and .ps.gz files are
>>> > hard to view in a browser.
>>> Sorry, not just now. I have a limited space on the web server.
>
>Just download the ps file and then use ps2pdf to change it to a pdf
>file.
Irrelevant question, but is there any way of converting a pdf file to
ps?
--
glenn
------------------------------
From: "Lyalc" <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: Wed, 11 Oct 2000 15:10:27 +1000
I agree - the 'attribute certificate" concept.
The cert binds a public key to an 'attribute", such as an account number
(Very bad for credit cards), an alias, or a logon userID.
Trouble is, they immediately become purpose specific;
an email signed with "account 123456789 at BankX" means nothing to me (or a
court), nor does a purchase order signed with "wclcos" (a User ID I have at
a non-Internet LAN).
The end effect - we have as many certificates as we have electronic
relationships - one each for the banker, butcher, baker, candlestick maker,
and one for every individual in our email address book.
As others have noted, CA + certificates are really only used today for SSL
server identification, and that's about the best available use for them for
the forseeable future.
Lyal
Daniel James wrote in message ...
>In article <SJrE5.24117$[EMAIL PROTECTED]>, Lyalc wrote:
>> Why does every sniffer and every server along the line need to see your
name
>> and address that is embodied in the certificate?
>>
>> Only you and the delivery agent need that information, yet certificates
give
>> it all away, every time the certificate is used. No ifs, no buts,
>> privacy=zero.
>
>Most of the certificates in use today associate a public key with an
identity
>that is expressed in terms of a person's name and address. X.509 rather
>presupposes that that's the sort of thing people will want to do when it
sets
>out the fields that can exist in a DName. It doesn't really have to be that
>way - a certificate needs /something/ to identify the owner, but that
>something doesn't have to contain a name and address as long as it's unique
to
>the certificate's owner (among certificates issued by that CA).
>
>If the whole message - including the sender's certificate - is encrypted
>(using the recipient's public key, which the sender believes he can trust
>because he obtained it from a certificate signed by ... etc.) the snooper
can
>gain nothing.
>
>Cheers,
> Daniel.
>
>
>
>
------------------------------
From: [EMAIL PROTECTED] (Mark Carroll)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 11 Oct 2000 04:34:35 GMT
In article <[EMAIL PROTECTED]>,
glenn <[EMAIL PROTECTED]> wrote:
(snip)
>Irrelevant question, but is there any way of converting a pdf file to
>ps?
Yes. acroread reads pdf and has a print-postscript-to-file option,
and my system appears to have:
pdf2ps - Aladdin Ghostscript PDF to PostScript translator
...installed.
-- Mark
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: AES Runner ups
Date: Wed, 11 Oct 2000 04:57:30 +0000
Greggy wrote:
> Let me rephrase - has the government stated any one of the other five
> finalists would be their backup deployment strategy if a problem was
> uncovered with Rijndael on some type of official level?
No, but they aren't worried about it -- if somebody <does> break AES,
3DES is still available.
--
Jim Gillogly
Mersday, 20 Winterfilth S.R. 2000, 04:56
12.19.7.11.4, 7 Kan 7 Yax, Eighth Lord of Night
------------------------------
** 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
******************************
