Cryptography-Digest Digest #849, Volume #11 Wed, 24 May 00 06:13:00 EDT
Contents:
Re: Observation of Matsui's Sboxes (Mark Wooding)
Re: Introduction to zero knowledge proofs? (Volker Hetzer)
Re: Patent busting for AES usage (Mark Wooding)
Re: Patent busting for AES usage (Mark Wooding)
Re: More on Pi and randomness (David C. Ullrich)
Schnorr patent and DSA (James Moore)
Re: Crypto patentability (Mok-Kong Shen)
Re: Yet another block cipher: Storin (Mok-Kong Shen)
Re: Encryption within newsgroup postings (Volker Hetzer)
Re: Crypto patentability (Mok-Kong Shen)
Re: Schnorr patent and DSA (Mok-Kong Shen)
Re: safer style sboxes (Mark Wooding)
Smooth numbers (Eric Hambuch)
Re: Musings... which is better in the end, a patent, or a brand? (Mok-Kong Shen)
Re: pentium timings (Greg)
Re: Another possible 3DES mode. (Mok-Kong Shen)
Re: Another possible 3DES mode. (Mark Wooding)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Observation of Matsui's Sboxes
Date: 24 May 2000 08:14:29 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> Algebraically the sboxes are explained as:
>
> S(x) = x^-1 mod p
>
> The first immediate observation is that
>
> S(0) = 0, S(1) = 1, for all p
Note that Rijndael uses a function similar to this. However, the
inversion is followed by an affine transformation over GF(2). Have you
analysed this construction?
[Interesting stuff snipped.]
-- [mdw]
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Introduction to zero knowledge proofs?
Date: Wed, 24 May 2000 08:27:15 +0000
Anton Stiglic wrote:
> http://crypto.CS.McGill.CA/~crepeau/CS647/
> http://theory.lcs.mit.edu/~oded/
> Also, Stinson's book (Cryptography, theory and practice)
> has some examples of Zero-Knowledge proofs...
Thanks a lot!
Btw, could we put this into the FAQ?
Greetings!
Volker
--
I believe that children are our future --- nasty, brutish, and short.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Patent busting for AES usage
Date: 24 May 2000 08:16:11 GMT
tomstd <[EMAIL PROTECTED]> wrote:
[snip]
It's traditional to make some contribution of your own when posting a
message to Usenet. ;-) (Yes, I know people occasionally have finger
trouble.)
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Patent busting for AES usage
Date: 24 May 2000 08:22:33 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> Similarly with using a hash in counter mode. That's why it must be
> non-invertible, or very difficult (i.e large symmetric key). Using a
> good hash (md5, sha-1, tiger, etc...) in counter mode like
What's MD5 doing in a list of good hashes?
> B[i] = H(B[i - 1] || i || key)
>
> Is much simpler, and it's secure iff the hash is secure and the
> key is random (and sufficiently large, say >100 bits).
Can you prove this assertion? ;-)
I'd be happier if the key were at the beginning, so as to provide,
effectively, a secret IV, as in HMAC. Of course, if everything fits
into one block it doesn't matter much, I suppose.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (David C. Ullrich)
Crossposted-To: sci.math
Subject: Re: More on Pi and randomness
Date: Sat, 20 May 2000 18:50:36 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 20 May 2000 09:17:07 +0100, Richard Heathfield
<[EMAIL PROTECTED]> 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?
>
>
>pi = sum (values of n from 0 to infinity) of (4/(8n+1) - 2/(8n+4) -
>1/(8n+5) - 1/(8n+6)) * (1/16)^n
Could be, I suppose.
>In other words, the nth hexit has the value (4/(8n+1) - 2/(8n+4) -
>1/(8n+5) - 1/(8n+6)).
Huh? That's not "in other words" at all! For this
to be the same as the the coefficients 4/(8n+1) - 2/(8n+4)
- 1/(8n+5) - 1/(8n+6) would have to be integers between
0 and 15. They're not.
>Source: "The Joy of Pi".
That's a source for the first statement(?), not
for your "in other words" part (I hope).
>I tried substituting in the first couple of n,
>and it didn't seem to make much sense, but that's probably because I'm
>not a mathematician.
>
>
>--
>
>Richard Heathfield
>
>"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
>
>C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
>37 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (60
>to go)
------------------------------
From: James Moore <[EMAIL PROTECTED]>
Subject: Schnorr patent and DSA
Date: Wed, 24 May 2000 03:46:11 -0500
Reply-To: [EMAIL PROTECTED]
Was the question of DSA being covered by the Schnorr patent ever
resolved? Authoritative references would be appreciated.
The issue was probably beaten to death way back in 1994-95... I'm
still tryin' to get caught up :) Following is a passage from a CSL
Bulletin on NIST's website (http://csrc.nist.gov/nistbul/csl94-11.txt)
that summarizes the question. My understanding is that all of the
patents in question have expired except the Schnorr patent.
======================================================================
Patent Issues
On July 27, 1993, NIST obtained U.S. Patent 5,231,688 which describes
the DSA, the algorithm which authenticates the integrity of signed
data and the identity of the signer. NIST is also seeking foreign
patents. The DSA patent and any foreign counterparts that may issue
are available for use without any written permission from or any
payment of royalties to the U.S. government.
During the comment period, one of the issues raised was whether the
DSS would infringe privately held patents. In particular, Public Key
Partners (PKP), a patent licensing company in Sunnyvale, California,
asserted that four of its U.S. patents (4,200,770, 4,218,582,
4,405,829 and 4,424,414), which relate to public key cryptographic
systems and methods, cover DSS. U.S. Patents 4,200,770, 4,405,829 and
4,424,414 are owned by Stanford University and U.S. Patent 4,218,582
is owned by Massachusetts Institute of Technology (MIT). Similarly,
Claus P. Schnorr of the Goethe University in Frankfurt, Germany
maintained that the DSS would infringe his U.S. Patent 4,995,082 on a
method for verifying signatures in a data exchange system. The
Schnorr patent was subsequently assigned to PKP. There are foreign
counterpart patents or applications to some of these U.S. patents.
NIST reviewed all of the asserted patents and concluded that none of
them would be infringed by DSS. Extra protections will be written
into the PKI pilot project that will prevent an organization or
individual from suing anyone except the government for patent
infringement in the course of the project. The PKI pilot project will
contain an "Authorization and Consent" clause under which the
government assumes liability for any patent infringement resulting
from the performance of the project, including use by private parties
when communicating with the U.S. government.
The Stanford and MIT patents were developed under funding from the
National Science Foundation (NSF) under which the Government received
a "nonexclusive, nontransferable, paid-up license to make, use, and
sell the invention throughout the world by or on behalf of the
Government of the United States and states and domestic municipal
governments." The Government has other rights in the Stanford patents
under Stanford's Institutional Patent Agreement with NSF. There is no
record of any Government license under the Schnorr patent.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Crypto patentability
Date: Wed, 24 May 2000 11:16:19 +0200
Paul Pires wrote:
> Now wait a minute here. I have listened to a lot of talk on patents from
> this group. You guys are real smart but I don't think you're up to
> re-inventing the patent.
> Patent laws and the patent process don't impact or effect your area of
> concern. Here is a bolder statement: This process works beautifully, and it
> is not the process's fault that the output of the process is quite often
> execrable. The patent examiner cannot process the patent on it's merits and
> you guys should be the first ones to recognize why. Invention like
> randomness is defined by negatives and only time and the market can tell
> whether it's any good. What is done with Patents is that the bar is set and
> you have to hurdle it cleanly to get a patent. That does not mean that you
> have something of value if you do.
What do you mean by ''Patent laws and the patent process don't impact
or effect [our] area of concern''??? If I design an algorithm using rotation,
which I 'really' have many times used in my programs (in other fields)
since decades, and a certain firm claims that I am imfringing its
patent rights, do you mean that that does NOT concern me??? If we
recognize (I am not sure that many of us can do that well, I myself
at least not fully) "The patent examiner cannot process the patent on
it's merits'', is that THE reason that we should close our eyes about what
is being practiced in the patent offices in matters of crypto??
> How long do you think that patents have been a part of our legal system?
> It goes way back to old English law. This is not some new social program
> that isn't working. This is the culmination of hundreds of years of use. My
Mmh. Sentencing to death has been practiced since before man could
write anything. Yet in most democratic countries of the world that has
been eliminated from laws today.
> Prior art is the big issue. The Patent must not be anticipated by any
> prior art. Most folks think that means previous patents. It does not. Any
> publication or offer for public sale is prior art. The examiner can only
> search and review what he can find and what the applicant supplies (he's
> legally obligated to fully disclose any he knows of). The patent grant isn't
> home free, any prior art found can invalidate an Issued patent. If you think
> this stuff was done before, find the publication or sale and link it to a
> date.
> You folks have been doing the single most important thing all along.
> This is a public forum where issues described here become the very prior art
> that will keep a bad patent from being enforced. It won't keep it from being
> issued. I said the process was beautiful, not omnipotent.
What are you actually suggesting here to us?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Yet another block cipher: Storin
Date: Wed, 24 May 2000 11:16:28 +0200
Manuel Pancorbo wrote:
> Well, I have a "recipe" for you. Try it, perhaps you find it usefull.
> Build a matrix 'G' this way:
>
> 2a + 1 � A � B � C
> 0 � 2b + 1 � D � E
> 0 � 0 � 2c + 1 � F
> 0 � 0 � 0 � 2d + 1
>
> where {A, B, C, D, E, F} are 24-bit key-dependent numbers and {a, b, c, d} are
>23-bit key-dependent numbers; so, you will need 24*6+23*4 = 236 key bits.
> You can find the inverse of G easily this way:
Obtaining invertible matrices from triangular matrices is well-known
in linear algebra.
M. K. Shen
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Encryption within newsgroup postings
Date: Wed, 24 May 2000 09:16:48 +0000
Dave Jones wrote:
> Posting:
> Xuk yffi wfubsq ptiua bleow lfm fefea pl kyv ezpc!
>
> Ncldm chla meeo rujo efeh acy uofjf
> jysh umiym kqc pwsj let tt hodk nee
> fjelk ailkn daltd sjs mlmjp ifujb big ueiub eotpev ymwk
No idea. Tried it with different offsets, but nothing
looked good.
Greetings!
Volker
--
I believe that children are our future --- nasty, brutish, and short.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Crypto patentability
Date: Wed, 24 May 2000 11:34:23 +0200
Anders Thulin wrote:
> If, as you say,
>
> > discussed such that (hopefully) ''the patent system, both in the
> > US and elsewhere,'' would be ''either massively overhauled or
> > scrapped entirely''.
>
> it seems reasonable to ensure that people knowledgeable about
> the patent system would participate as well, as this does not only
> refer to patents on crypto inventions, ut the entire patent system.
While I used the quoted sentence, I don't agree that the patent system
should be ''scrapped entirely''. The quotation is sort of 'rhetorical'.
Elsewhere I have repeatedly emphasized the necessity of public
reviews, however.
> > The
> > Hitachi claims are menacing AES. Anyone designing encryption
> > algorithms is potentially facing the same risk. So the present
> > situation of patents need be clarified and understood and we
> > should attempt, if possible, to get the patent system reformed
> > for our interest
>
> Provided, of course, that the claims are likely to be valid.
> That seems to be the first point to settle. And as that kind of
> discussion is definitely a patent problem rather than a crypto problem,
> using sci.crypt seems to be less efficient than, say, comp.patents.
The point is that people of our group understand well what is involved.
This is not likely to be so in the other group. Note that, in another thread
that I initiated, it took a few postings to render the matter of Hitachi's
claims more or less (yet not fully) comprehensible.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Schnorr patent and DSA
Date: Wed, 24 May 2000 11:41:30 +0200
James Moore wrote:
> Was the question of DSA being covered by the Schnorr patent ever
> resolved? Authoritative references would be appreciated.
>
> The issue was probably beaten to death way back in 1994-95... I'm
> still tryin' to get caught up :) Following is a passage from a CSL
I don't know but I don't have the impression of the matter having been
beaten to deat way back in 1994-45. I remember reading Schnorr
massively defending his patent claims in a mailing list and that was a
couple of years later than 1995.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: safer style sboxes
Date: 24 May 2000 09:34:20 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> And haven't found one that is ideally non-linear. Which makes me ask,
> how come ciphers like SAFER or E2 (uses x^255 right?) can get away with
> that?
Because they have good diffusion layers.
If you can demonstrate that any n-round characteristic must have k
S-boxes active, and the best characteristic through the S-box has
probability (or bias) p_max, then your best n-round characteristic has
probability (or bias) p_max^k.
So, basically, if you design your diffusion layer right, then you can
get much better resistance to cryptanalysis than if you merely diddled
with the S-boxes for a while. And you can do that with relatively
lacklustre S-boxes.
The Rijndael paper comments that, if anyone's worried about the S-box
(an inversion in GF(2^8) followed by an affine transformation over
GF(2)) having `back doors' in it, it can be replaced by another, and it
doesn't actually need to have wonderful properties for the cipher to
remain secure.
Does anyone have any analysis of Rijndael which actually depends
strongly on the S-box used?
-- [mdw]
------------------------------
From: Eric Hambuch <[EMAIL PROTECTED]>
Subject: Smooth numbers
Date: Wed, 24 May 2000 11:46:57 +0200
Does anybody know the number of primes n, where n-1 is "smooth" (n has
only small prime factors p_i of size O(log n)) ?
Any hints (or better proofs and references) are welcome !
Eric
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Musings... which is better in the end, a patent, or a brand?
Date: Wed, 24 May 2000 11:57:30 +0200
Sundial Services wrote:
> Maybe the money that's being poured into trying to patent algorithms,
> and defend those patents against all comers -- is ultimately just being
> thrown to the lawyers like so many pearls. (Ahem...) Maybe those folks
> are "winning the battle but losing the war by failing to participate in
> it while it's being fought."
You can't change that state of affairs. This is analogous to
competition in armaments. If one country builds H-bombs and
intercontinental missiles, the others must try, if possible, to do the
same.
M. K. Shen
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: pentium timings
Date: Wed, 24 May 2000 09:53:22 GMT
> True I don't know all the details, but I am going on what I see.
Imperical research is not what I would call the best approach
to designing software.
> Hmm, well I get consistant results in win98 and pure dos.
So what?
> So magic or not it works.
You mean it "appears" to work as you imagine it does. It "appears"
to fit your explanation of what you think is going on internally
with the operating system. BTW, just what do you think is going
on inside the Windows 98 OS anyway?
> Also I can tell if it gets slower simply
> because the time increases. I don't think there is anything
> else to effect it.
We know how you THINK that. You have made that clear to us. What
we want to know is how do you KNOW that?
--
There is only one gun law on the books- the second amendment.
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Another possible 3DES mode.
Date: Wed, 24 May 2000 12:10:26 +0200
zapzing wrote:
> In this implementation three keys are used.
> But I was thinking, what if a key expansion
> algorithm was used and each individual DES
> encryption had its own unique key. For example
> if the enlarged block consisted of 32 bytes,
> then there would be 12 DES encryptions to
> encrypt the large block. What if each of those
> 12 encryptions had its own key?
I proposed sometime back in this group to use variable keys
for block ciphers, i.e. different keys for different blocks (or sets
of blocks, should that be more preferable). That obviates a certain
number of much researched and published techniques of attack
that rely on the availability of large amounts of materials processed
with the same key.
M. K. Shen
=============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Another possible 3DES mode.
Date: 24 May 2000 10:07:04 GMT
zapzing <[EMAIL PROTECTED]> wrote:
> This is an expansion of an idea that was in the sci.crypt FAQ. In the
> faq, the following idea was suggested as a way of accomplishing 3DES
> on an enlarged block:
>
> F(x)=Tran(E(k1,Tran(E(k2,Tran(E(k3,Tran(x)))))))
The final unkeyed transformation layer isn't actually useful, and may as
well be discarded. While we're being incompatible, we might as well
throw away DES's initial and final permutations too.
This is just an SP network, using DES (or some other block cipher) to
provide the effect of large keyed substition tables.
Note that if your two (remaining) permutations are actually inverses of
each other, and the cipher is a Feistel network or something similar
which only needs a key schedule change to decrypt, you end up being able
to use the same code for encryption and decryption, just with different
key schedules. In fact, a simple matrix transposition is all I think
you need, and that's its own inverse. You should get full avalanche
after two rounds with a byte-level transpose and 8 or fewer 64-bit block
ciphers in parallel.
> Of course noone would want to memorize 56x12=672 bits, so we would use
> a key expansion algorithm to get 672 bits from, say, 160 bits (or so).
>
> Of course the security would depend on the key expansion
> algorithm. Perhaps BBS could be used for that, since speed would not
> be an issue for the key expansion algorithm.
Who generates the modulus? Finding good moduli for BBS actually appears
to be nontrivial. And the security of the system depends on the factors
being unknown, so if you used a shared modulus you'd have to trust
whoever generated it to destroy the factors afterwards.
Why not just use a hash function? Something like the SEAL table-
initialization function ought to be easily sufficient.
-- [mdw]
------------------------------
** 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
******************************
