Cryptography-Digest Digest #272, Volume #13 Mon, 4 Dec 00 22:13:00 EST
Contents:
Re: Q: Discrete transforms in practice (Mok-Kong Shen)
Re: Q: Discrete transforms in practice (Mok-Kong Shen)
Re: Revised cipher (Mok-Kong Shen)
Re: On mutation of crypto algorithms (Mok-Kong Shen)
Re: Newbie ("Michael")
Re: Newbie ("Michael")
Re: keysize for equivalent security for symmetric and asymmetric (Peter Fairbrother)
Re: Q: Discrete transforms in practice ("Matt Timmermans")
Re: Q: Discrete transforms in practice ("Matt Timmermans")
Re: Pentium 4 and modular exponential (Jason Stratos Papadopoulos)
Re: Q: Discrete transforms in practice ("Matt Timmermans")
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Discrete transforms in practice
Date: Tue, 05 Dec 2000 01:11:33 +0100
Matt Timmermans wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > I don't have your experience but from general knowledge of
> > numerical computations the finite precision of computer
> > must, beginning at certain extent (size of problem etc.),
> > be an issue, if there is rounding in the computations at
> > all.
>
> As long as ((a+b)-b) = a (i.e., you aren't using floating point), then
> Rounding isn't a problem -- any volume-preserving linear transform, like DCT
> or DFT (properly normalized), can be decomposed into a sequence of "lifting
> steps" or "shears", where some coefficients are offset by linear
> combinations of the _other_ coefficients. Each of these steps can be simply
> inverted by reversing the sign of the calculated offsets. It works a lot
> like a Feistel cipher.
>
> As the number of input coefficients increases, however, the maximum absolute
> value of the output coefficients gets larger.
Sorry for my poor knowledge in actual computations of DFT.
The formulae for DFT I see from books is a sum of terms
where a multiplication with a complex exponential function
(equivalent to sine and cosine) is done. How can one avoid
using floating point numbers, since the values involved
cannot in general be obtained absolutely exactly? What is
the trick used to enable pure integer arithmetics to be
performed? Do then the results thus obtained really
correspond to the ones defined in the field of signal
processing? Could you refer me to literatures?
> > So I guess your claim of always invertibility of
> > discrete Fourier transforms has to be relativated, unless
> > you use a package with arbitrarily large precision to
> > adapt to the actual need of the sequences being processed.
>
> It's invertible on integers. To completely implement integer math, you need
> a bignum package. It's not necessary in most real situations, however,
> because the input size is bounded.
How about a sequence of, say, 10000 bits?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Discrete transforms in practice
Date: Tue, 05 Dec 2000 01:11:17 +0100
Tom St Denis wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > What I know till now of applications of discrete transforms
> > is that PHT has been employed in some block ciphers. As is
> > commonly the case, these transforms are only applied to a
> > small number of bits (i.e. within the block). I like to know
> > (because I am curious about the issue) whether in actual
> > practice people have tried to apply discrete transforms to
> > larger number of groups, perhaps to 20 blocks or even the
> > entire message, as an independent processing step.
>
> Well the PHT is merely a matrix, nothing magical. In your case you
> could look at Twofish/Square/Rijndael for their use of MDS matrices
> which are different types of transforms.
All transforms are well-known. There isn't any magic.
What is employed in the said algorithms is a Hill type
of transformation, i.e. multiplication by an invertible
matrix, and is in general not connected to orthogonal
functions. I am presently interested however in the Fourier-
related transformations.
> > One doesn't need 'infinite' bits for DFT. One certainly
> > needs a flexible software to provide arbitrarily high
> > precision for being able to transform sequences of
> > arbitrary length. Once the precision is high enough such
> > that the inverse transform, after rounding, gives the
> > original bit sequence, that will be o.k. This I think is
> > clear, though I don't know how the situation really is in
> > practice, i.e. whether the needed precision, though finite,
> > is too large to be affordable economically. The Hadamard
> > transform is anyway without rounding errors and thus
> > without the problem of precision. But that doesn't
> > automatically mean it is good for practical use. That's
> > why I posted the article to ask people questions.
>
> That simply is not true. Because things like the DCT/DST/DFT involve
> irrational values they cannot be represented with a finite piece of
> information as easily as other numbers. Your package would have to
> recognize them and could never resolve the correct answer in "binary"
> form. i.e It would have to recognize that 0.707... is 1/2^.5..
One knows from numerical computations with real-valued
numbers that one can generally get more precisions with
more precise computations, i.e. with more mantisa and
exponent part in the representation of the numbers on
computers. Now a Fourier transform is in theory exactly
invertible, i.e. if, as you said, one employs 'infinite'
precision. But, as one uses increasingly higher precision,
one approaches the exact values more and more. Thus, if
the true results are integer values (which in the present
case for the inverse transform is the case), there is
certain finite precision such that (with it or with higher
precision) the values become very near to these integer
values and hence, by rounding, will lead to the true
values. This is essentially the same as in case one does
a multiplication of a matrix with a vector (both with
integer values) using real-valued arithmetics and later
compute the inverse of the matrix and again does a
multiplication. Due to rounding errors in the real-valued
arithmetics, the result will not be exact in general,
whatever (finite) precision is employed, but with
sufficient precision one gets such good (approximate)
values that these, upon rounding, give the original values
of the vector. (I am excluding the issue of ill-conditions
of matrices here.)
Note: Matt Timmermans claimed in a follow-up that one could
even use integer arithmetics for DFT. I am questioning
him about that.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Revised cipher
Date: Tue, 05 Dec 2000 01:11:39 +0100
Benjamin Goldberg wrote:
>
> Mok-Kong Shen wrote:
> >
> > Benjamin Goldberg wrote:
> > >
> > > Mok-Kong Shen wrote:
> > > >
> > > > It is in my view extremely remarkable that the authors
> > > > of Rijndael have succeeded to realize a fairly simple and
> > > > very strong block cipher. (Of the four components in its
> > > > rounds, three are key-independent and 'clean', while the
> > > > remaining one is simply an addition of the round key.)
> > >
> > > What do you mean 'clean'? While I'll admit that I think that the
> > > RowShift is simple, as is the ByteSub step, I don't think that the
> > > ColMix is simple at all.
> >
> > By 'clean' I mean it doesn't have things like DES, where
> > one doesn't clearly know where the S-boxes come from (the
> > issue of possible backdoor). MixColumn uses a Hill matrix
> > (applied in Galois field) of a very special (in my opinion
> > simple) form.
>
> Ahh, so you're complaining that I didn't explain where/how I chose my
> polys, and that they are thus not 'clean', not that the operation
> *using* them is not good.
>
> Might I ask... how was the Hill matrix chosen? Does it say that in the
> Rijndael paper? I don't have the paper in front of me. I know the
> criteria for the choice of the polynomial for the Galois field was
> described, but why was that particular Hill matrix chosen?
I was not (implicitly) saying that yours is not clean, but
only stressing that the cleaness of Rijndael has already
helped to enable it to gain future user acceptance (prior
to your cipher -- which may be superior, I don't know --
comes to the scene).
Rijndael's author doesn't mention Hill and gets to the
matrix in a way described in their paper. But in essence
this is a matrix transformation by an invertible matrix
and hence is what Hill did in the cipher named after him,
though Hill in his paper worked in Z_n, not in Galois field.
>
> > > > Independent of Rijndael's status as the future standard of
> > > > encryption, this fact inevitably means an essential barrier
> > > > to users' acceptance of alternative future algorithms. For
> > > > they would ask themselves: Why complicated, if simple
> > > > stuffs will do? (I subjectively consider your use of LFSR
> > > > to be not simple.)
> > >
> > > Although my *explanation* of how I use the LFSR is [overly?]
> > > complicated, what I actually do is not. There is probably a way of
> > > saying it more simply than I did.
> > >
> > > Hmm. For each of the 8 rows (which are 16 bits each), raise it to
> > > the power of 32, under GF(2**16), with a different poly for each
> > > row?
> > >
> > > How about: For each of the 8 rows, replace it with x**32 % p, where
> > > p is a different order-16 poly for each row?
>
> Actually, this is sort of an error... what I meant was replace the row
> with x * 2**32 % p.
>
> > > Or even more simple: Do a linear transformation on each rows.
> > > Can't state anything simpler than that.
> > >
> > > I'd like to see you describe the MixColumn operation of AES in so
> > > simple a manner.
> >
> > You have to derive a number of polynomials. This (in my
> > subjective view) is more complicated than setting up a
> > Hill matrix (the general requirement is only that the
> > matrix be invertible).
>
> Finding primitive polynomials is indeed difficult, but only if you don't
> already have a program for doing so. I do. You can download one from
> the net.
>
> I had the program print out all order-16 polys, using the 'permute'
> method. This printed them in order from smallest number of taps to
> largest number of taps. There were 12 maximally dense polys. Six of
> them were the reverse of the other 6. I used half of the 12, then chose
> 2 of the reversed polys at random.
>
> As to 'setting up a Hill matrix' ... Finding an invertable 4x4 matrix is
> not necessarily an easy task, especially considering that the
> multiplications and additions are in GF(2^8). I will assume that two of
> the criteria that Rijndael's authors used was that the elements of the
> encryption matrix have only a few bits, and that those bits be as close
> to the right of the byte as possible, but what *other* criteria (if any)
> were used? There were surely a fair of 'suitable' matrices, why that
> one? Was it randomly chosen?
>
> Not that I'm not claiming there's a backdoor in Rijndael, but rather
> that the choice of constants used in Rijndael is by no means as simple,
> straightforward, and 'clear' as you (Mok) are claiming.
Finding an invertible matrix is very easy. One way is to do
a multiplication of two triangular matrices. This comes from
the well-known technique of LU-decomposition of a
non-singular matrix. The diagonal elements of L are 1, the
diagonal elements of R have to be invertible, which in case
of GF simply means exclusion of 0. All other elements can be
arbitrary. Since both matrices are non-singular, their
product is also not singular. Now an arbitrary Hill matrix
may not necessarily be very good for the purpose of the
encryption algorithm. The matrix chosen in Rijndael is
presumably a good one, though. (That's the art of design,
if it is the case.) Anyway, the set of coefficients in the
rows in Rijndael is the same, which can be considered to
contribute to some simplicity in my view.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On mutation of crypto algorithms
Date: Tue, 05 Dec 2000 01:11:47 +0100
Tom St Denis wrote:
>
> The C(x) transform is not only a "hill transform" (whatever that is)
> but also a "MDS transform". You can't change it to a 2x2 unless you
> maintain MDS properties. Otherwise the cipher gets weakers quite a bit.
>
> My suggestion is to resize the Rijndael structure by removing columns
> not rows.
So you claim that there doesn't exist a 2*2 MDS transform.
Could you please elaborate that a bit? What is the exact
definition of a MDS transform? Thanks.
M. K. Shen
------------------------------
From: "Michael" <[EMAIL PROTECTED]>
Subject: Re: Newbie
Date: Tue, 05 Dec 2000 00:14:47 GMT
Thank you very much for your informative reply.
It is all too often in niche' groups that outsiders are ridiculed.
I freely admit I don't have a clue. But I do have and interest and have
made some effort.
I will check out the web links right away and I will get _The Codebreakers_
.
Thanks again.
Michael
"M.S. Bob" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Michael wrote:
> >
> > I am confused. Isn't it paramount to keep the algorithm secret?
>
> It has not been the suggested practice to design and analysis ciphers
> based on such an assumption since 1883.
>
> Kerchkhoff's Principle: The security of the crypto-system must not
> depend on keeping secret the crypto-algorithm. The security depends only
> on keeping secret the key.
>
> This advice is best followed, as it is based on historical observation,
> that many "secret systems" collapse under any unanticipated scrutiny.
> Under estimating the ability of the opponent has caused many failures in
> historic crypto-systems.
>
> I strongly recommend you read either _The Code Book_ by Simon Singh
> (easy reading) or _The Codebreakers_ by David Kahn ('the' crypto history
> reference) so that you don't have to repeatedly invent old broken
> ciphers. You will also see just how far the opponent can go to 'fiddle'
> with or investigate your crypto-system. The history is pretty
> interesting, and I am not normally interested in historic books.
>
> To get a feel for the "real-world" I suggest you read several essays:
>
> Why Cryptosystems Fail by Ross Anderson
> http://www.cl.cam.ac.uk/users/rja14/wcf.html
>
> Why Cryptography Is Harder Than It Looks by Bruce Schneier
> http://www.counterpane.com/whycrypto.html
>
> Security Pitfalls in Cryptography by Bruce Schneier
> http://www.counterpane.com/pitfalls.html
>
> Memo to the Amateur Cipher Designer by Bruce Schneier
> http://www.counterpane.com/crypto-gram-9810.html#cipherdesign
>
------------------------------
From: "Michael" <[EMAIL PROTECTED]>
Subject: Re: Newbie
Date: Tue, 05 Dec 2000 00:19:41 GMT
You make a valid point.
Thanks,
Michael
"Scott Craver" <[EMAIL PROTECTED]> wrote in message
news:90couc$e6g$[EMAIL PROTECTED]...
> Michael <[EMAIL PROTECTED]> wrote:
> >
> >In your worst case scenario, someone has to be there waiting to take
> >advantage of it.
> >I don't think that is reality (in this real world scenario.)
> >I do understand what you are saying.
>
> Hi,
>
> Allow me to provide you with an illustrative real-world
> example. Recently, the recording industry has been
> developing a system called SDMI (secure digital music
> initiative,) in which secret messages are embedded in
> the music on Compact Discs. The idea is that your
> CD player/MP3 player at home will have a program in it
> that will find and decrypt those messages, and
> could refuse to play or record music on the basis of
> the hidden message. The main goal, I guess, is to
> keep people from making unauthorized copies of music.
>
> But notice! All these devices have to know how to
> extract the hidden messages. These devices are like
> your friends, with whom you share your algorithm.
> The industry can't use a changing secret key or
> password, because all MP3 players will have to be
> able to extract the hidden data from all music clips.
> So it's just the algorithm, and it must be kept secret.
>
> We analyzed their system as part of a challenge, in
> which they wouldn't describe to anyone the algorithm,
> of course. Yet hackers were able to determine quite
> a bit about some of the methods involved. In one
> case (I swear, the technical report is on its way)
> an elaborate method of hiding data could be seen clear
> as a bell by computing a plain old freq. response.
> The method was so unique that it only took a short
> search to find the ====> US PATENT <==== belonging to
> the company, describing it in relative detail. Um, oops.
>
> It is more realistic to expect an algorithm to be
> compromised, or even reverse-engineered by good
> cryptanalysis, than it is to rely on security through
> obscurity.
> -S
>
>
>
>
------------------------------
Subject: Re: keysize for equivalent security for symmetric and asymmetric
From: Peter Fairbrother <[EMAIL PROTECTED]>
Date: Tue, 05 Dec 2000 01:22:50 +0000
in article 90b3mt$9d3$[EMAIL PROTECTED], Bob Silverman at [EMAIL PROTECTED]
wrote on 2/12/00 3:15 pm:
> In article <[EMAIL PROTECTED]>,
> "Trevor L. Jackson, III" <[EMAIL PROTECTED]> wrote:
>> Kenneth Almquist wrote:
> <snip>
>
>> I suspect this conclusion is false. Since, in theory, a QC enjoys a
> square
>> root advantage over classical architectures a 256-bit key attacked by
> a QC
>> would be as a 128-bit key attacked by a classical computer. I'd
> expect a
>> search of a 2^128 space to be trivial for a classical computer in 2100
>
> Fortunately, no one cares what you expect. I suggest you do
> the arithmetic to see exactly how fast a computer would need
> to be to break a 128-bit key in reasonable time.
If Moore's law holds (double in 18 months) it will take until 2119. Advances
in medical science might allow us to live that long.
(2^10 processor machine checking 2^20 keys per processor per second now,
2^18 seconds (a year) to execute, requires 2^79 improvement in computers,
takes 118.5 years)
Peter
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Q: Discrete transforms in practice
Date: Tue, 05 Dec 2000 01:38:01 GMT
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:90grc9$erg$[EMAIL PROTECTED]...
> If you used a "float" or "double" then it's not invertible. Just
> appears to invert most arguments with little loss in visual quality.
No floats... but that's in a branch of this thread...
> I used a FFT like network and it's at
>
> http://www.geocities.com/tomstdenis/
>
> Also you should look up Terry Ritters balanced diffusion networks since
> they are similar.
Ah. I'm familiar with Terry's work there (nifty). Thanks for the link.
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Q: Discrete transforms in practice
Date: Tue, 05 Dec 2000 02:28:02 GMT
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:90h870$qd2$[EMAIL PROTECTED]...
>
> It's the terms of the DCT/DFT/DST matrices that make "exact" values
> impossible. It's not the input itself that causes the problem.
There's no such thing as an exact DCT, and I wouldn't claim to have invented
one. Mine is still inexact, but invertible.
> Aha, linear integer matrices (i.e elements from Z or Q) are always
> invertable. However, as I stated most other popular computer related
> transforms (DCT is used in millions of computers worldwide) are not
> bounded to the set of integers.
Right, but I mean a _real_ DCT, i.e., JPEG-compatible. I used scaled fixed
point coefficients in the matrix and integer inputs/outputs.
> N.B older implementations of the DCT/IDCT use scaled fixed point
> arithmetic which means they are bounded to a fixed size input. They
> are not lossless however.
>
> N.B.2 newer versions use scaled MMX routines (I think) and are not
> lossless either.
True, but you can make them lossless. For example, try this small transform:
a'=sqrt(.5)*(a+b)
b'=sqrt(.5)*(a-b)
I could write it like this (assume the float->integer conversions round to
nearest):
void transform(int &a, int &b)
{
double r=sqrt(.5);
int newa=(int)( r*(a+b) );
int newb=(int)( r*(a-b) );
a=newa;b=newb;
return;
}
That's not invertible, but I can make it invertible by writing it like this:
void transform(int &a,int &b)
{
double r=sqrt(.5);
double k=(1.0-r)/r;
b-=(int)( k*a )
a+=(int)( r*b )
b-=(int)( k*a );
b=-b;
return;
}
If you expand it out assuming infinite precision (and if I haven't made an
error), then you'll see that it's the same transform, but with different
rounding errors. This isn't the fastest way to implement the transform, of
course, but it's trivial to write an exact inverse:
void Itransform(int &a,int &b)
{
double r=sqrt(.5);
double k=(1.0-r)/r;
b=-b;
b+=(int)( k*a );
a-=(int)( r*b );
b+=(int)( k*a );
return;
}
You can do the same thing for the DCT or FFT.
Note: If I were doing this in the same sort of way as the JPEG stuff, I
would have written it like this:
void transform(int &a,int &b)
{
a+=b;
b-=(int)(0.5*a);
b=-b;
}
This is much faster, but leaves the coefficients badly scaled. I took care
of that as part of the quantization step.
------------------------------
From: Jason Stratos Papadopoulos <[EMAIL PROTECTED]>
Subject: Re: Pentium 4 and modular exponential
Date: 5 Dec 2000 02:33:36 GMT
Paul Rubin <[EMAIL PROTECTED]> wrote:
: Jason Stratos Papadopoulos <[EMAIL PROTECTED]> writes:
:> Analog Devices' DSP chips now have 32-bit multiply-accumulates into
:> an 80-bit register. The 21160 DSP has two separate execution units that
:> can each do a 32-bit multiply-accumulate every clock.
: Woo hoo! What clock speed does it run at, and how much does it cost?
: Sounds like it's *built* for modexp.
All the models I've seen top out at 100MHz. As for prices, given that it
has two execution units, 768k of internal SRAM and huge paired 64-bit
internal buses, do you really blame chip vendors for a price of "CALL"?
ADI apparently has recently come out with a much cheaper version of the
21160 (the 21161) with much less internal memory. I have no idea what
*those* cost, either.
www.analog.com
jasonp
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Q: Discrete transforms in practice
Date: Tue, 05 Dec 2000 02:53:56 GMT
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Sorry for my poor knowledge in actual computations of DFT.
> The formulae for DFT I see from books is a sum of terms
> where a multiplication with a complex exponential function
> (equivalent to sine and cosine) is done. How can one avoid
> using floating point numbers, since the values involved
> cannot in general be obtained absolutely exactly? What is
> the trick used to enable pure integer arithmetics to be
> performed? Do then the results thus obtained really
> correspond to the ones defined in the field of signal
> processing? Could you refer me to literatures?
You'll want to see the reply I just made to Tom, where I give an example of
the necessary trick. Essentially the same trick has recently become popular
for implementing invertable wavelet transforms, where they call it
"lifting". A google search on "wavelets lifting" gives lots of good results.
You will especially want to look at section 3 of this paper:
http://cm.bell-labs.com/who/wim/papers/integer.pdf
> > It's invertible on integers. To completely implement integer math, you
need
> > a bignum package. It's not necessary in most real situations, however,
> > because the input size is bounded.
>
> How about a sequence of, say, 10000 bits?
If you have 1000 10-bit integer samples, you can do the whole thing using
32-bit math. Your result will be more than 10000 bits, though, because some
of your output coefficients could be > 1024.
If you want to map 10000 bits -> 10000 bits, the closest thing to a Fourier
transform that you can use is a "number theoretic transform" (NTT). A
google search on this gives lots of good results too, and I seem to remember
a good description in "Numerical Recipes in C".
An NTT is like an FFT, but it uses coefficients in a finite field instead of
integer or real coefficients.
The complex exponential has no meaning with those kinds of numbers of
course, but the only important thing about e^2pii/N is that it's a primitive
Nth root of 1. When you do an NTT, you choose a field for your coefficients
that also has a primitive Nth root of 1, and the powers of this element take
the place of the complex exponential in the FFT.
Apart from any cryptographic use you might have for it, the NTT is
interesting primarily because it supports the convolution theorem, and so
you can use it to do _very_ big multiplications in NlogN time using all
integer math. (It's quite beautiful -- see Numerical recipes in C).
------------------------------
** 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
******************************
