Cryptography-Digest Digest #316, Volume #13 Tue, 12 Dec 00 17:13:00 EST
Contents:
Re: On using larger substitutions (Mok-Kong Shen)
Re: Sr. Cryptographer/mathematician (David A Molnar)
Re: On using larger substitutions (Simon Johnson)
Re: Sr. Cryptographer/mathematician ("M.S. Bob")
Re: Is brute for the only way? (Terry Neckar)
Re: important programming languages (Paul Schlyter)
Re: 64bit CRC (Paul Schlyter)
Re: PGP Symmetric Algo ("Sam Simpson")
Re: important programming languages ("Sam Simpson")
Re: important programming languages (Herman Rubin)
Re: Is brute for the only way? (Paul Rubin)
Re: Software PRNG.. (Paul Crowley)
Re: Request: A Compiled Rijndael DLL Pretty Please :) (David Schwartz)
Re: YAPRNG (David Wagner)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On using larger substitutions
Date: Tue, 12 Dec 2000 20:25:22 +0100
Tom St Denis wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > A general 16-bit substitution table is commonly considered
> > impractical because of the large storage space required,
> > not to say using a number of such tables. On the other
> > hand, the technique of Playfair offers extremely compact
> > storage, though with the trade-off of realizing only very
> > special substitutions. One could help a bit through using
> > a version employing two matrices. Further one could
> > concatenate several Playfairs. In situations where one
> > could be satisfied with the quality of such substitutions,
> > the following scheme, which requires some more storage but
> > is more flexible and straightforward to code, may be of
> > interest:
> >
> > One generates four 8-bit substitution tables. The two
> > bytes of the given 16 bits are first transformed by the
> > first two tables respectively. The result is circularly
> > shifted 4 bits and the remaining two substitution tables
> > are applied in the same manner.
>
> This is vulnerable to differential cryptanalysis very easily if you are
> not carefull. Again I would look for 4bit->4bit differences that state
> in the same word after the rotate of four bits. That way the number of
> active sboxes is minimized.
>
> A better idea is todo a MDS where the substitution is done on the
> input. This way the diffusion is optimal and is less vulnerable to
> differential cryptanalysis.
Do you want to dynamically choose from the different
candidate MDS matrices, since the substitution is to
be a variable one? In the scheme described the 8-bit
substitution tables can be arbitrarily generated via random
permutations and all techniques involved are primitive (no
knowledge of GF required). As said, the underlying goal is
simplicity rather than achieving an S-box of superb quality.
M. K. Shen
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Sr. Cryptographer/mathematician
Date: 12 Dec 2000 19:04:50 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
>> >> - Number theory
>> >> - Numerical analysis
>>
>> > These two are the same!
>>
>> Again, not even remotely close.
> How do they differ? Number theory is the analysis of fields, rings,
> structures and the relationship between different groups, etc.
> Numerical analysis is...?
Computing with error. Analysing roundoff errors in floating point,
better and more "numerically stable" algorithms for matrix algebra
with real and complex matrices, root-finding, and so on.
Really, not that close. Some cryptographers also happen to be interested
in numerical analysis, but that seems stem more from general algorithmic
interest than from deep connections between the two fields.
As far as I know, anyway.
-David
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: On using larger substitutions
Date: Tue, 12 Dec 2000 19:30:36 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> A general 16-bit substitution table is commonly considered
> impractical because of the large storage space required,
> not to say using a number of such tables.
You could generate two 8-bit s-boxes and pass divide a 16-bit word up
into two chunks and pass it through the two s-boxes, then contatenate
the two results.
To be 100% certain of how the s-boxes work together, i would suggest
combining the two 8-bit s-boxes into a 16x16 then testing that. Then
when you present your algorithm, in a paper, you would then just
publish the two 8x8 s-boxes.
This would use less memory, and would have the same characterstics as
the tested and presumably optimal 16x16.
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "M.S. Bob" <[EMAIL PROTECTED]>
Subject: Re: Sr. Cryptographer/mathematician
Date: Tue, 12 Dec 2000 19:54:15 +0000
Tom St Denis wrote:
> >
> > >> - Computaional complexity theory
> >
> > > "Computational" also referred to "Combinatorics"
> >
> > Ummmmm..... no, not even close.
>
> Well something dealing with complexity is normally a combinatoric
> thing... well from what I have seen, sorry.
>
> > >> - Number theory
> > >> - Numerical analysis
> >
> > > These two are the same!
> >
> > Again, not even remotely close.
>
> How do they differ? Number theory is the analysis of fields, rings,
> structures and the relationship between different groups, etc.
> Numerical analysis is...?
"There are more things in heaven and earth, Horatio,
Than are dreamt of in your philosophy."
-Hamlet
You have a very limited insight into mathematics, and your are
repeatedly are mistaken in thinking you have a better grasp of
mathematics than you do, and unfortunately expressing this misguided
grasp in this forum. You fail to comprehend the size of the realm of
mathematics.
You really should study more mathematics. Go to Carleton, UOttawa,
Waterloo, or something.
To the matter at hand...
You have managed to totally bungle your description of number theory.
This is not a textbook description of number theory, but here I go...
Number theory is the study of the properties of usually the whole
numbers, and rational numbers (fractions).
Numerical analysis is the study of computing numerical data.
Your incorrect description of number theory is closer to algebra.
Number theory is considered a "pure" math area, whereas numerical
analysis is an applied area. Number theory is typically limited to W, N,
Z, and Q domains while numerical analysis may use floating point numbers
in its calculations, and is far more likely to be satisfied with an
approximation.
You might find <http://www.math.niu.edu/~rusin/known-math/index/> a
useful guide to explain some of the differences between the various
branches of mathematics.
------------------------------
From: Terry Neckar <[EMAIL PROTECTED]>
Subject: Re: Is brute for the only way?
Date: Tue, 12 Dec 2000 20:21:52 GMT
Sorry, but I took engineering calculus almost 30 years ago, and really
don't understand what you mean. Can you give me an example.
Thanks,
Terry
Simon Johnson wrote:
> In article <[EMAIL PROTECTED]>,
> Terry Neckar <[EMAIL PROTECTED]> wrote:
> > Without doing a brute force program, does anyone know of a reverse
> > algorithm for the following?
> >
> > If I know what the ending value of answer is, how can I quickly solve
> > for the value of key?
> >
> > ----------------------------------------------
> > answer = 1;
> >
> > for(x=0; x<5432; x++)
> > answer = (answer * key) % 27218753;
> >
> > ----------------------------------------------
> >
> > Thanks,
> > Terry
> >
> >
> Yes, factor the modulo: 27218753 into its primes, then express the
> problem as:
>
> answer = (answer * (key^5432)) % 2721873
>
> Then, you should be able to solve for the key using the euclidean
> algorithm.
>
> Yours,
> Simon
> --
> Hi, i'm the signuture virus,
> help me spread by copying me into Signiture File
>
> Sent via Deja.com
> http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: important programming languages
Date: 12 Dec 2000 20:50:40 +0100
In article <[EMAIL PROTECTED]>,
JCA <[EMAIL PROTECTED]> wrote:
> Paul Schlyter wrote:
>
>> In article <[EMAIL PROTECTED]>,
>> JCA <[EMAIL PROTECTED]> wrote:
>>
>>> Bob Silverman wrote:
>>>
>>>> There is really only one language that matters for encryption:
>>>>
>>>> assembler.
>>>
>>> You can say that again. It is true that compilers are getting
>>> better and better, but for a number of cryptographic operations
>>> good, hand-coded assembly language at the right place buys
>>> you one order of magnitude in performance. The gains are most
>>> noticeable for newer architectures, for which compilers are not
>>> yet so hot.
>>
>> Perhaps one should then say:
>>
>> There is really only one language that matters for encryption:
>>
>> hardware.
>>
>> because hardware implementations will buy you another order of
>> magnitude in performance.
>
> But you don't want to go hardware (or even assembly language)
> all the way, but only for those critical operations for which it makes
> a difference.
If someone pays me, or of I can afford it + have the time myself,
I wouldn't mind at all! Assembly language in cooperation with hardware
is quite fun!
> In addition, once you have done your hardware implementation
> that's the best you will get from that particular implementation,
> whereas software ones have more potential.
Don't be so sure about that. A hardware implementation (i.e. the way
you interconnect a set of chips) can be "ported" to a faster chipset
to be run at a faster clockspeed.
I wonder if we'll ever see a "hardware compiler" which compiles e.g.
a C program into not assembly language but a hardware implementation
executing the operations specified by the program. On some
operations (in particular floating-point math) it would of course be
most sensible to add a processor to the implementation and feed it
with machine code, but for other operations (in particular bit
twiddling) an implementation directly in hardware will be superior.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: 64bit CRC
Date: 12 Dec 2000 20:51:18 +0100
In article <[EMAIL PROTECTED]>,
Mihai Preda <[EMAIL PROTECTED]> wrote:
> I need two independent 32bit fingerprints for a message. I think CRC
> would be a good choice (I don't need security).
> Now, what should I prefer:
> a) compute two 32bit CRCs(with different polynomials)
> b) compute one 64bit CRC, and use the lower and higher order 32bits as
> the two fingerprints.
You could also choose
c) compute two 32-bit CRC's using the same polynomial, but one of
them scanning your data "backwards", or "from the middle out towards
the ends", or in any other order you wish.
> In either case, could you direct me to some available source code
> implementing this? (or, where can I get good 32bit or 64bit
> polynomials?)
32-bit CRC code in C is avialable at e.g. http://www.snippets.org
I'v enever seen a 64-bit CRC implementation, but once you get a good
64-bit polynomial it ought to be straightforward to extend a 32-bit
implementation to 64 bits.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: PGP Symmetric Algo
Date: Tue, 12 Dec 2000 20:30:39 -0000
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:915k88$ke1$[EMAIL PROTECTED]...
> In article <915g9s$pit$[EMAIL PROTECTED]>,
> "ink" <[EMAIL PROTECTED]> wrote:
> >
> > "Tom St Denis" dropped into the real world with a crash and
> proclaimed...
> > > In article <90qt48$ia6$[EMAIL PROTECTED]>,
> > > [EMAIL PROTECTED] wrote:
> > > > Hi,
> > > >
> > > > Which is the best symmetric algorithm to use with PGP out of CAST,
> > > IDEA
> > > > and TripleDES ? Or maybe i should ask what positive/negative
> points
> > > have
> > > > each of these algorithms ?
> > >
> > > Stupid question.
> >
> > Tom, as much as I admire you for your abilities and knowledge and like
> > reading your posts, but with all due respect, there's no such thing as
> > a stupid question. There's only stupid answers. Please don't conclude
> > from your knowledge to that of others.
>
> My abilities? I am no more then a the average avid amateur.
I'd dispute this, you seem to have a very natural talent for the maths
involved as well as a great deal of enthusiasm...If you can keep the
interest I'm sure you'll go far.
> And
> forgive me for answering like that but truly that question gets asked
> about three times a week.
That's why NG's have FAQs. If the question is in the FAQ, then we can
politely point the person posing the question to the FAQ. If the FAQ
doesn't answer the question, and it's on topic, then the question (and the
answer) can be added to the FAQ.
Thousands of other newgroups manage this kind of thing, but this group of
intellectuals and academics can't? ;))))
Seriously, I thought someone was taking ownership of a FAQ for this group?
Regards,
Sam
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: important programming languages
Date: Tue, 12 Dec 2000 20:36:25 -0000
"Bob Silverman" <[EMAIL PROTECTED]> wrote in message
news:912pvb$b52$[EMAIL PROTECTED]...
> In article <912jps$5vr$[EMAIL PROTECTED]>,
> Tuomas Pellonpera <[EMAIL PROTECTED]> wrote:
> > Hi!
> >
> > I found out that at the end of last February there was a rather
> lengthy
> > (50 articles or so) discussion about 'the best programming language
> for
> > encryption'.
>
> And the discussion was nonsensical and irrelevent. Just as it is
> now.
>
> >However, as some questions remained unanswered to me, and
> > as I have just joined this group, I dare pose them now.
> >
> > To begin with, I got interested in programming thanks to Eric S.
> > Raymond's aricle 'How to become a hacker' (= wizard programmer). He
> > recommends these languages: C/C++, Python, Perl, Java and LISP. As my
> > main area of interest is cryptography, I have tried to select
> languages
> > that would offer a steady basis for writing and developing encryption
> > programs (last February's discussion on the subject helped me). They
> are
> > (not in order of importance):
> > 1. C
> > 2. Java
> > 3. Perl
> > 4. Assembler
> >
> > My questions are:
> > 1.) Would you agree that these language are, not the only right and
> best
> > ones, but ones that offer a solid background for encryption?
>
> This entire discussion is "wrong-headed". Allow me to quote a
> colleague: "It is possible to write Fortran in any language".
>
> There is really only one language that matters for encryption:
>
> assembler.
One assumes all of the encryption algorithms in all of the RSA packages are
implemented in assembler for all of the possible CPUs? I know this isn't
the case for most open source packages.....Or does the good Dr Gladman have
a point, per chance? ;)
Rgds,
Sam
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: important programming languages
Date: 12 Dec 2000 15:56:38 -0500
In article <9138ks$o9q$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
>In article <gK8Z5.11982$I5.124606@stones>,
> "Brian Gladman" <[EMAIL PROTECTED]> wrote:
>> "Bob Silverman" <[EMAIL PROTECTED]> wrote in message
>> news:912pvb$b52$[EMAIL PROTECTED]...
>> > In article <912jps$5vr$[EMAIL PROTECTED]>,
>> > Tuomas Pellonpera <[EMAIL PROTECTED]> wrote:
>> [snip]
>> > This entire discussion is "wrong-headed". Allow me to quote a
>> > colleague: "It is possible to write Fortran in any language".
>> > There is really only one language that matters for encryption:
>> > assembler.
>> I am inclined to agree that this discussion is not very useful but
>your
>> answer is wrong here for a number of reasons. Most importantly, until
>the
>> requirements are known it is simply not possible to decide on the best
>> language
>A minor nitpick. I did not say that assembler was "best". I was
>very careful to avoid using that word. I did say that assembler
>was the only choice that *mattered*. It matters when you need speed.
>If you don't need speed then the choice of language really does not
>matter.
There are other situations where it matters. Some languages
make some procedures almost impossible to even state. Some
of the limitations are deliberately put in to "protect people
for their own good".
Let the programmer have access to the full power of the
machine, often in ways which the language people cannot
come close to understanding.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Is brute for the only way?
Date: 12 Dec 2000 13:13:31 -0800
Terry Neckar <[EMAIL PROTECTED]> writes:
> Sorry, but I took engineering calculus almost 30 years ago, and really
> don't understand what you mean. Can you give me an example.
It's a bit complicated to explain in a newsgroup message. I suggest
you get an introductory book on number theory, e.g. "A course in
number theory and cryptography" by Neal Koblitz. Look up the
Euclid's extended GCD algorithm and Euler's phi function.
This stuff goes back to the 17th century. You don't need a PhD to
understand it, but the amount of math you'll need to pick up to make
much sense of the answer is about equal to learning some topic in
engineering calculus, like integration by parts or something like
that. You can probably pick up what you need in a few hours, but not
in a few minutes.
Basically: notice 2721873 = 3 * 7 * 11 * 11783. Use the factorization
to compute phi(2721873) = 2*6*10*11782 = 1413840. Use Euclid's
algorithm to figure out y = 5432^(-1) mod 1413840 (I don't feel like
doing that right now). Then (answer^y) mod 2721873 should be the key,
unless I messed up somewhere. To understand why that works, you need
to read up on those algorithms.
Notice you need the factors of 2721873 to compute the phi function.
If instead of 2721873 you picked a very large number (say 500 digits) that
was the product of two 250-digit unknown factors, there'd be no known way
to get the key. That is the RSA cryptography system, which is probably
what you were thinking of in your example.
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Software PRNG..
Date: Tue, 12 Dec 2000 21:20:09 GMT
Jorgen Hedlund wrote:
>
> Are there any (good) software PRNG's on the net, that is also free?
Assuming you want a keyed cryptographic PRNG, yes, OpenSSL contains
several. RC4 is probably the fastest, though it is slightly biased.
Rijndael in counter mode could provide another. http://www.openssl.org/
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Request: A Compiled Rijndael DLL Pretty Please :)
Date: Tue, 12 Dec 2000 13:17:03 -0800
Tom St Denis wrote:
> Well you could take the current Rijndael C source strap a DLLMain on it
> and make your own DLL. I could do it in about 30 mins if nobody else
> has one handy let me know.
The only reason it would take 30 minutes is because Visual C++ takes 10
minutes just to fire up.
DS
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: YAPRNG
Date: 12 Dec 2000 21:42:03 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Richard Heathfield wrote:
>Consider two PRNGs, [...] I'll call them R1() and R2().
>Each has a big ol' period. [...] [... Then you xor them ...]
A large period is not sufficient for security. For instance, a simple
counter has a huge period, but will not be secure when used with your
framework.
Thus, your framework is not sufficient for security. The details matter.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
