Cryptography-Digest Digest #899, Volume #12 Wed, 11 Oct 00 20:13:01 EDT
Contents:
Re: Dense feedback polynomials for LFSR (Terry Ritter)
Re: On block encryption processing with intermediate permutations (Mok-Kong Shen)
German Lorenz Code Machine ("David C. Barber")
Re: A new paper claiming P=NP (Mike Oliver)
Re: A new paper claiming P=NP (Mark William Hopkins)
Re: Why trust root CAs ? (Timothy M. Metzinger)
Want Free Encryption? ("George Peters")
Re: A new paper claiming P=NP (Mark William Hopkins)
Re: A new paper claiming P=NP (Mark William Hopkins)
Re: Dense feedback polynomials for LFSR (Tim Tyler)
Re: NSA quote on AES (Tim Tyler)
Re: A new paper claiming P=NP (Paul Rubin)
Rijndael test cases. ("ajd")
Re: working with huge numbers (Scott Contini)
Re: EKE, RSA, and Compression? (Mok-Kong Shen)
Re: working with huge numbers (Mok-Kong Shen)
Re: Does Rijndael look Linear or is it just me? ("Paulo S. L. M. Barreto")
Code Book Cipher Challenge Cracked (JPeschel)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Dense feedback polynomials for LFSR
Date: Wed, 11 Oct 2000 20:33:45 GMT
On Tue, 10 Oct 2000 20:53:10 GMT, in <8rvvji$p13$[EMAIL PROTECTED]>, in
sci.crypt zapzing <[EMAIL PROTECTED]> wrote:
>[...]
>On another note, it seems to me that making the
>polynomial itself a part of the key would
>greatly increase security, but that possibility
>is barely mentioned in his book.
>Do you have any info on that?
To the extent that LFSR's are used to begin the production of
confusion sequences for stream ciphers, I think most are in the GFSR
or Additive forms that deal with integer values for each shift
element. The values actually do not move, instead a pointer is
advanced around the queue to simulate shifting, and typically 32
random bits are produced at once. Generally speaking, the number of
operations involved in each such step is proportional to the number of
"taps." This argues for using few taps if possible, with trinomials
being the fastest we can get.
If we expand from trinomials, 9-nomials of substantial degree can
provide sufficient selection for keying. None of this is much good,
of course, if the opponents can somehow expose the linear sequence,
although the best attack I know of on Additive RNG's is cubic with
degree n, and I think I standardized on deg 9689 after first using deg
11,213. Of course, if we key the feedback polynomial, it then becomes
part of the key which must be transported, although that might just be
part of the initial installation, or just a particular binary version.
Around 1990 I built several stream ciphers based on large polynomial
generators (with the resulting sequence nonlinearized) for use with my
Dynamic Substitution combining technology. (The final incarnation is
described at:
http://www.io.com/~ritter/CLO2DESN.HTM
.) Several of the early versions supported fully arbitrary polys, but
that of course added overhead beyond even the larger number of taps.
Were I to re-do this today, I would probably support both trinomials
and 9-nomials.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block encryption processing with intermediate permutations
Date: Wed, 11 Oct 2000 22:59:19 +0200
John Myre wrote:
>
> Mok-Kong Shen wrote:
> <snip>
> > If I prove a theorem and there is a weakness, say, it depends
> > on the existence of a quantity p being prime and someone
> > points out that in a degenerate case p can be 1 and hence
> > the proof is invalid and I do a little modification such
> > that this case can be avoided and a prime p still can be
> > chosen, then my purpose of establishing the theorem is
> > achieved, isn't it?
> <snip>
>
> Of course not.
>
> There is no reason to suppose that the weakness pointed out
> is the only weakness. Do you also presume, when you fix a
> bug in a program, that you have now proven it correct?
I was asking in my orignal post for comments for the
very purpose of enabling me to know the weakness(es).
Now Bryan Olson claimed to have found an attack and
subsequently he said that under a certain condition
his attack doesn't work. So I modified my scheme to
make it immune to his attack. It could very well be
the case that there are other attacks that apply
to the original as well as to the modified scheme and
that there are even other attacks that didn't apply to
original scheme but apply to the modified scheme.
There are ALL kinds of possibilities. I just don't
yet know. (BTW, I suppose that you know that there
were even papers published in well-known scientific
journals that had been later found to be in error.)
What appears to be fairly certain is that his attack
no longer works, since he is by nature the 'authority'
of the method of attack that he himself has worked
out and consequently one can readily believe him if
he claims that his own attack doesn't work under the
modified condition.
If you or any readers like to further comment on my
scheme, I should naturally appreciate very much to have
that opportunity. But please (the word 'you' below
refers to a general reader):
(1) Don't claim that what I write is not science. If
you are really of that opinion, then there is no sense
to waste time to discuss the matter. Anyway, I wouldn't
join a dispute where I am of the opinion that the
stuff is nonsense, for I know that I have enough
opportunities to spend my time to do other things that
are more interesting and perhaps profitable for me than
dealing with nonsense. On the other side, I also don't
see any point of continuing a discourse with people
who downrightly claim that everything I say is nonsense.
(Would you in my place behave differently?)
(2) Please argue as objectively and as clearly and directly
as possible and be patient enough to give explanations,
even if I happen to pose questions whose answers were
already there but, possibly due to my lower IQ, are not
discernable by me without your aid.
I think that it is a clear fact that people in our group
have fairly different knowledge stands and orientations.
Some are experts, some are beginners. Some are certainly
much more intelligent than the others. One that is superior
should take consideration of that and act accordingly
with patience and good will such that a discussion can be
sensibly carried out with one that is inferior to the
satisfaction of all sides.
M. K. Shen
==========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: "David C. Barber" <[EMAIL PROTECTED]>
Subject: German Lorenz Code Machine
Date: Wed, 11 Oct 2000 14:28:48 -0700
Are there any good references to the Lorenz machine online?
If not, which books?
*David Barber*
------------------------------
From: Mike Oliver <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Wed, 11 Oct 2000 14:32:06 -0700
Reply-To: [EMAIL PROTECTED]
David Eppstein wrote:
>
> In article <8s2891$4ad$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> (Bill Unruh) wrote:
>
> > Actually this makes no sense. Proofs do not come in sequences of longer
> > and longer statements of the proof. Also if checking he proof is P, and
> > since cheching is a linear traversal at least of the parts of the proof,
> > then if the size is not P then the checking is not P. So, either way, I
> > do not understand your caveate.
>
> The definition of a problem being in NP is that every yes-instance has a
> witness *of polynomial size* which can be checked in polynomial time.
> Lots of problems in harder complexity classes have witnesses which can be
> checked in P, but the witnesses are too big.
Given T a consistent finite collection of axioms in a recursively-presented
language, T consistent, Q relatively interpretable in T. For any
theorem s of T, let f(s) be the length of its shortest proof. Now
let g(n) be the maximum value of f(s), where s ranges over all theorems
of T having n or fewer symbols.
Conjecture: g(n) grows faster than any primitive recursive function.
Can anyone prove or refute?
I'd be willing to extend the conjecture to r.e. collections of axioms,
except that somehow the sequence of states of the program producing
the axioms must be charged to the length of the proof. Otherwise
every theorem could be an axiom, so every theorem with n symbols
would have a proof with n+k symbols for some constant k.
------------------------------
From: [EMAIL PROTECTED] (Mark William Hopkins)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 11 Oct 2000 22:20:29 GMT
In article <[EMAIL PROTECTED]> "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
writes:
>> >Mark William Hopkins wrote:
>> >> Therefore, it should be fairly easy to spot the flaw in the paper. No
>> >> demo programs are needed.
>> >
>> >Hmmm. Assuming the conclusion. Useful technique that. ;-)
>>
>> No, actually it's: asserting the 'conclusion' and refuting the assumption.
>
>No.
>
>The argument I commented on assumed that P!=NP. Read it again.
You just repeated what I said. Asserting is the same as assuming.
But it's not the conclusion, since it wasn't arguing that P != NP, but
that the paper is wrong BECAUSE P != NP. I'm merely pointing that out.
So it's not assuming the conclusion.
Next time, it helps to ask before assuming the 'conclusion' is the
conclusion.
That's called assuming WHAT the conclusion is -- which is fallacious.
------------------------------
From: [EMAIL PROTECTED] (Timothy M. Metzinger)
Subject: Re: Why trust root CAs ?
Date: 11 Oct 2000 22:25:48 GMT
In article <8rvdak$7ja$[EMAIL PROTECTED]>, [EMAIL PROTECTED] writes:
>Before Verisign issues a business certificate, Verisign
>checks up on the legitamacy of the business, including checking up on
>articles of incorporation, DUNS numbers, and assorted other information
>that establishes the existence of a business. In essence, the
>certificate tell me, the consumer, that a site meets the minimum
>standards identified in Verisign's Certification Practices Statement.
Well unless Verisign is constantly auditing those businesses, all the
certificate tells you is that the business met the standards at the time the
cert was issued.
It does not, of course, verify that the business still meets those standards,
or that the business has adequately protected the private key, thus you may
STILL not be communicating with the business you think.
But it's as good as it gets short of you travelling to the business and doing
your business face-to-face.
Timothy Metzinger
Commercial Pilot - ASMEL - IA AOPA Project Pilot Mentor
'98 M20J - N1067W
Pipers, Cessnas, Tampicos, Tobagos, and Trinidads at FDK
------------------------------
From: "George Peters" <[EMAIL PROTECTED]>
Subject: Want Free Encryption?
Date: Wed, 11 Oct 2000 17:31:30 -0500
You can download an entire suite of encryption products with two file
systems, email/ftp/point to point comunications, source code and a key
management at
www.endecs.com/uenigma.exe . These are really great professional products
and well worth the download.
------------------------------
From: [EMAIL PROTECTED] (Mark William Hopkins)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 11 Oct 2000 22:36:24 GMT
In article <kZYE5.216$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Kent Paul Dolan)
writes:
>>I don't think you fully realise the seriousness of the understatement you
>>just made. There is a $1,000,000 bounty out there for the first correct
>>resolution to this issue.
>
>Yeah, but on the Everett Dirkson metric, that lacks a trio or more of
>zeros at the end to constitute "real money", and is at the 0.1 *
>xanthian - total -sellout - to - the - suits - level in any case. Nice
>for pocket change, though.
Yes, but pocket change enough to quit your job and have enough to live on
for the rest of your life -- just off the interest alone. There are
several other open problems at that Foundation up on the list too.
http://www.claymath.org/prize_problems
------------------------------
From: [EMAIL PROTECTED] (Mark William Hopkins)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 11 Oct 2000 22:43:48 GMT
>Such [meaning in this context: all] assumptions are not a valid form of
>argumentation.
Number 1: asserting a true statement is always valid. Two, assuming a
statement to draw a conclusion is also, always, a valid form a
argumentation.
Your mistake was calling the assumption the conclusion and then mis-calling
the argument asserting the [sic] conclusion.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Dense feedback polynomials for LFSR
Reply-To: [EMAIL PROTECTED]
Date: Wed, 11 Oct 2000 22:17:01 GMT
zapzing <[EMAIL PROTECTED]> wrote:
: On another note, it seems to me that making the
: polynomial itself a part of the key would
: greatly increase security, but that possibility
: is barely mentioned in his book.
: Do you have any info on that?
Using an LFSR alone is not at all secure. Using a key-dependent
polynomial with an unknown tap sequence isn't at all secure either - you
can figure it out from the output using the Berlekamp-Massey algorithm.
In both cases there's little or no security. Consequently, whether one is
an improvement over the other seems of marginal interest.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: NSA quote on AES
Reply-To: [EMAIL PROTECTED]
Date: Wed, 11 Oct 2000 22:27:21 GMT
Brian Gladman <[EMAIL PROTECTED]> wrote:
: "Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
:> Brian Gladman <[EMAIL PROTECTED]> wrote:
:> : The point at which cryptographic systems are broken by breaking the
:> : algorithms used are now in the past [...]
:>
:> I doubt this is true.
: I am not suggesting that this is true for all algorithms - clearly it won't
: be true if a bad choice of algorithm is made.
: I was making the assumption that the algorithm chosen is one of a number of
: well established modern algorithms such as, for example, the AES finalists.
In the case of the 5 AES finalists, I'd guess that at least one of them
has a publicly-known attack which is better than brute-force on the full
cypher within, say, 25 years.
An attack of practical use would be somewhat more suprising. Perhaps one
possibly-viable hope for this would be if quantum computers became a reality.
I don't know if that would qualify as "an attack on the algorithm".
It might enable the plaintext to be recovered from the cyphertext, though.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 11 Oct 2000 16:00:36 -0700
Anyway, getting away from the digression on what P and NP are and how
to convert postscript to pdf, there's a discussion thread on Slashdot
about this paper and it sounds like a false alarm. Someone over there
who seemed to know what he was doing started reading it, and found
enough mistakes in the first few pages that he didn't feel it necessary
to bother reading further.
------------------------------
From: "ajd" <[EMAIL PROTECTED]>
Subject: Rijndael test cases.
Date: Wed, 11 Oct 2000 13:07:16 +0100
Hi,
I've written a rijndael cipher in the last couple of days and I now want to
test it to see if it works. I've got the test vectors off the Rijndael web
page (http://www.esat.kuleuven.ac.be/~rijmen/rijndael/) but I'm not sure how
to use them. What is ECB, CBC, KAT, and the Monte Carlo Test.
Help would be much appreciated.
Thanks
ajd
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: working with huge numbers
Date: 11 Oct 2000 23:13:01 GMT
In article <8s1r1b$78v$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
>In article <8rua7p$ifh$[EMAIL PROTECTED]>,
> "DeSilva" <[EMAIL PROTECTED]> wrote:
>> I would like to implement some encryption into software, but have come
>> across the obvious problem of doing math on huge numbers. How to
>device two
>> 500 digit numbers with eachother..
>> Can anyone in here please explain to me how this is normally done?
>> Are the numbers converted into a new numeric system which is based on
>ex 256
>> in stead og 10 so each digit fits into a byte, or... how??
>
>See Knuth Vol 2 for a complete exposition on this topic.
>Basically, for moderately sized numbers you do it the same way you
>do on pencil & paper. Each number is stored using multiple words
>with a radix of perhaps 2^30 or 2^31.
>
It can also be done quite efficiently with radix 2^32.
Scott
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: EKE, RSA, and Compression?
Date: Thu, 12 Oct 2000 01:39:46 +0200
John Savard wrote:
>
[snip]
> And, of course, this isn't all that new an idea; splitting a message
> in half and switching the halves, so that the beginning and ending of
> the message are in the middle is a very old method of protecting
> messages against the vulnerability caused by standardized headers and
> signatures.
But on the general assumption that the opponent knows
the algorithm and hence in particular also this trick,
I don't think that we could claim that this really
functions.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: working with huge numbers
Date: Thu, 12 Oct 2000 01:56:24 +0200
DeSilva wrote:
>
> So can anyone direct me to an online source of info on how to do this?
> Quite frankly right now i dont want to sit and close read sourcecode in
> order to figure out how and why one specific implementation does this, i
> would much rather read some sort of tutorial on the subject... and right now
> i am not really interested in buying books on the subject.
I don't know situations in your country, but in Germany
one can normally get pretty all kinds of (popular) books
from public libraries and university libraries.
M. K. Shen
------------------------------
Date: Wed, 11 Oct 2000 21:14:48 -0200
From: "Paulo S. L. M. Barreto" <[EMAIL PROTECTED]>
Subject: Re: Does Rijndael look Linear or is it just me?
Albert Yang wrote:
>
> OK, AES is chosen, and so this might be considered by some to be water
> under the bridge, but I keep reading about the "Rijndael is just as safe
> as Serpent because brute force is still the fastest known method etc.."
>
> Yes, but to me, from the stuff I have read, and certainly N. Fergeson's
> article didn't help to deminish the bias...
>
> But informal survey, is it just me or does Rijndael look very linear and
> looks to come under some SERIOUS attack from linear crypto attacks in
> the not so distant future?? Especially now that almost 100% of the
> crypto community has only 1 target... I think there is a basis for the
> paranoia, don't you?
>
> Albert
Rijndael is an alternation of linear and nonlinear layers. In this
sense it's as "linear" as Serpent. As for (classical) linear attacks,
it's possible to prove (check the Rijndael documentation) that no linear
approximation over four rounds has input-output correlation larger than
2^{-150}, or 2^{-300} for 8 rounds; it's *very* unlikely that linear
attacks can be mounted for the whole cipher. Notice that the best
attacks known against reduced-round versions of Rijndael are
saturation/related key attacks attacks, not classical
differential/linear attacks.
The fact that Rijndael seems "linear" is due to the structure of the
linear layer, which is the composition of ShiftRow and MixColumn, and
also to the key addition, which is affine.
Cheers,
Paulo Barreto.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Code Book Cipher Challenge Cracked
Date: 12 Oct 2000 00:02:30 GMT
All 10 stages of Singh's Code Book Cipher Challenge
have been cracked.
See:
http://www.simonsingh.com/cipher.htm
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
** 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
******************************
