Cryptography-Digest Digest #10, Volume #13 Thu, 26 Oct 00 21:13:01 EDT
Contents:
Re: Collision domain in crypt()? ([EMAIL PROTECTED])
Re: Collision domain in crypt()? (David Schwartz)
Re: On block encryption processing with intermediate permutations (Bryan Olson)
Re: Hardware RNGs (David Schwartz)
Re: Is OPT the only encryption system that can be proved secure? (Bryan Olson)
Symmetric cipher ("William A. McKee")
Re: Symmetric cipher (David Schwartz)
Re: Is OPT the only encryption system that can be proved secure? (Tim Tyler)
Re: Using DH (Gregory G Rose)
Re: Is OPT the only encryption system that can be proved secure? (John Savard)
Re: Is OPT the only encryption system that can be proved secure? (Tim Tyler)
Re: DATA PADDING FOR ENCRYPTION (Tim Tyler)
Re: Q: Computations in a Galois Field (Tom St Denis)
Re: Hardware RNGs (Tom St Denis)
Re: Rijndael and PGP (Tom St Denis)
Re: Is OPT the only encryption system that can be proved secure? (John Savard)
Re: DATA PADDING FOR ENCRYPTION (Tim Tyler)
Re: Is OPT the only encryption system that can be proved secure? (John Savard)
Re: Save RSA bandwidth (John Savard)
Re: Factoring Polynomials (Bob Silverman)
Re: My comments on AES (John Savard)
Re: My comments on AES (John Savard)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Collision domain in crypt()?
Date: Thu, 26 Oct 2000 22:58:25 GMT
>Actually, I tried hashing and taking the first 16
> chars and had several collisions, hence the request. :-/
Which algorithm did you use? Did it begin with SHA or was it MD5, or
Tiger, or RipeMD. If it was, please, I beg of you, publish the input
and their hashes, any collisions of those hashes would be of extreme
interest. If it wasn't one of those algorithms you might want to retry
with one of those algorithms, any of them should provide collision-free
operation for 4 million values.
Joe
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Collision domain in crypt()?
Date: Thu, 26 Oct 2000 16:14:35 -0700
[EMAIL PROTECTED] wrote:
>
> What's the collision domain in a standard (Solaris) crypt() function?
>
> I'm in need of a simple hash function for ~4 million items, with a digest of
> approx 10-14 chars; MD5 et al at 32 characters is simply overkill. Am I
> in the right ballpark?
MD5 creates a 128-bit hash, which is 16 characters. If you encounter
any collisions, post them and you will get instant fame as none are
known.
DS
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: On block encryption processing with intermediate permutations
Date: Thu, 26 Oct 2000 23:17:37 GMT
James Felling wrote:
> Now the only way I can see of this scheme working in an even remotely
> plausible way is by seperating the mixing from the feistel.
I'd separate out the permutations entirely. :)
> This is
> only accomplishable if the feistel is unballanced, or in the case of a
> balanced feistel, if the block is divided into an odd number of pieces
> by the permuataion. Otherwise this attack applies, as one can always
> find a set of properly formed blocks to peel off a 2 round pair.
> Unfortunately most cyphers use block sizes that are power of two bits
in
> size. This will limit the aplicability of this method. In addition
> such splitting will likely result in a substantial slowdown of the
> cypher. OTOH, in these cases, this attack fails, and I have trouble
> seeing an alternate line of attack. Brian?
Can I plead burn-out? I think there are many potential
problems, but I'm out of attacks. I would never have found
the line of current attack had I not been home with the flu,
bored out of my mind.
I think the approach is misguided, for reasons previously
stated. Furthermore, it solves no problem. What's wrong with
a conventional chaining mode, IV and a modern block-cipher?
True, we cannot prove security, but don't claim to solve that
one without theorem in hand. The reason sci.crypt is flooded
with techniques for symmetric encryption is not that the world
needs them; it's that they're easy to produce.
There may be interesting research questions on the value of
message-in-one-block encryption. There's no clear indication
whether it can be as (or more) efficient and secure, compared
to fixed-size block schemes. Several advocates of
variable-size blocks post here, but none of them seem
interested in cryptanalysis.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Hardware RNGs
Date: Thu, 26 Oct 2000 16:23:06 -0700
David Schwartz wrote:
>
> Tom St Denis wrote:
>
> > The problem is that virtually of the lsb's on my comp are zeroes, with
> > a few ones... In fact last time I counted the ratio was about 7 to 1.
> > This means you need to gather about 100,000 bits before you can safely
> > have about 160 bits (using SHA-1). However, the problem gets
> > worse...you must sample very slowly, otherwise the samples are
> > correlated... Thus sample at about 8khz. At 8khz it will take 12.5
> > seconds to gather enough inputs....
>
> If you are correct that one in every eight bits is a one and they are
> otherwise uncorrelated, you should need no more than 512 bits of input
> to get 160 bits of entropy. Two hundred milliseconds worth of data
> should be perfect.
If anyone cares, if a bit has a one in eight change of being a one and
a seven in eight chance of being a zero and are otherwise random, each
bit contains .5275 bits of entropy. Therefore you theoretically need 303
bits in to get 160 out. 512 should be more than enough.
DS
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Is OPT the only encryption system that can be proved secure?
Date: Thu, 26 Oct 2000 23:26:26 GMT
Terry Ritter wrote:
> The mathematically-proven OTP depends upon various assumptions which
> cannot be provably achieved in practice.
True.
> And proof based on
> unprovable assumptions is ultimately no proof at all.
Nonsense. Of course it's a proof. A huge mass of concerns
vanishes, and one only has to look at how well his system
fulfills the assumptions.
Do right triangles exist in practice? Is the Pythagorean
theorem "no theorem at all"? Is it useless to engineers?
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Reply-To: "William A. McKee" <[EMAIL PROTECTED]>
From: "William A. McKee" <[EMAIL PROTECTED]>
Subject: Symmetric cipher
Date: Thu, 26 Oct 2000 23:40:47 GMT
Excuse my ignorance but what exactly is a "symmetric" cipher?
TIA,
Will.
--
William A. McKee
[EMAIL PROTECTED]
Asia Communications Quebec Inc.
http://www.cjkware.com
"We're starfleet: weirdness is part of the job." - Janeway
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Symmetric cipher
Date: Thu, 26 Oct 2000 16:42:44 -0700
"William A. McKee" wrote:
>
> Excuse my ignorance but what exactly is a "symmetric" cipher?
A symmetric cipher is one in which the same key is used both for
decryption and for encryption. Since anyone who knew the key could
decrypt the communication, before a symmetric cipher can be used, some
means must be used for both sides (and nobody else) to know the same
key.
DS
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Is OPT the only encryption system that can be proved secure?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 26 Oct 2000 23:18:38 GMT
John Savard <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] (Terry Ritter) wrote, in part:
:>The mathematically-proven OTP depends upon various assumptions which
:>cannot be provably achieved in practice. And proof based on
:>unprovable assumptions is ultimately no proof at all.
: Although it is important to note that the OTP is subject to the
: bit-flipping attack, beyond this, I've tended to find this statement
: about the OTP as unhelpful, perhaps even annoying.
: But now I've finally figured out _why_ it bothers me.
: If we say that the OTP isn't "really" proven secure, because you can't
: prove that an eavesdropper hasn't somehow gotten hold of your key...
: then we _must_ say the same about all other cryptosystems.
This bothers you? What specifically is the problem with this conclusion.
The conclusion appears to me to be correct - I see no problem with an
inability to be completely confident of your security.
You can't be completely confident of anything else - I don't see why
security should have some exalted status.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ ILOVEYOU.
------------------------------
From: [EMAIL PROTECTED] (Gregory G Rose)
Subject: Re: Using DH
Date: 26 Oct 2000 16:52:00 -0700
In article <rqgJ5.160$[EMAIL PROTECTED]>,
George Gordon <[EMAIL PROTECTED]> wrote:
>In using DH, if you:
>
>a) create a random 160-bit key, then
>
>b) expand that to 2K+ bits using RC4 or something,
Drop this stage. It's perfectly secure to just use
the 160 bit random value as the secret half of the
D-H exchange.
>c) create a shared key using DH, then
>
>d) hash that to a 160-bit key using SHA1, and
>
>e) use that as your symmetric key.
>
>Is that OK??
Yes.
>Also, does anyone know where I can find some tested *safe* parameters
>for DH >1024-bits??
RFC 2412 is used in IPSec and has good D-H
parameters in it. Here's what they say for 1024
bit D-H:
The prime is 2^1024 - 2^960 - 1 + 2^64 * { [2^894 pi] + 129093 }.
Its decimal value is
179769313486231590770839156793787453197860296048756011706444
423684197180216158519368947833795864925541502180565485980503
646440548199239100050792877003355816639229553136239076508735
759914822574862575007425302077447712589550957937778424442426
617334727629299387668709205606050270810842907692932019128194
467627007
The primality of the number has been rigorously proven.
The representation of the group in OAKLEY is
Type of group: "MODP"
Size of field element (bits): 1024
Length (32 bit words): 32
Data (hex):
FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE65381
FFFFFFFF FFFFFFFF
Generator:
Data (hex): 2
(I believe that representation is MSB, MSW-first,
but you might want to either check the RFC or
verify it from the decimal representation.)
Greg.
--
Greg Rose INTERNET: [EMAIL PROTECTED]
QUALCOMM Australia VOICE: +61-2-9181 4851 FAX: +61-2-9181 5470
Suite 410, Birkenhead Point http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 B5 DF 66 95 89 68 1F C8 EF 29 FA 27 F2 2A 94 8F
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Is OPT the only encryption system that can be proved secure?
Date: Fri, 27 Oct 2000 00:06:12 GMT
On Thu, 26 Oct 2000 20:18:30 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>I doubt that I understand you. Is the main stress of the
>above sentence on 'secure algorithm' or on 'memerizable
>key' or on 'mental computation'? I don't see why mental
>computation is important. (Do you means e.g. bugs on the
>computer that could leak the key or computations to the
>opponent and hence much or all processing has to be done
>in the brain?)
Yes, that was what I meant. The idea is that _all three_ of those
conditions would have to be meant so that there was no contact with
the messy "real world" where software has bugs and so on.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Is OPT the only encryption system that can be proved secure?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 26 Oct 2000 23:28:47 GMT
[EMAIL PROTECTED] wrote:
: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
:> Actaully the only reason a OTP used in the correct way is secure
:> is becuase if one has cipher text there can be more than one possible
:> solution. Most real world ciphers are not secure in this sense take
:> PGP for example. It is not secure at all in this sense becasue of the
:> public key.
: Sorry....what are you talking about?
: Are you claiming that Public Key crypto is insecure?.
: If so, please explain why.
God (i.e. an entity with no work factor constraints) can look at some data
encrypted with a public key cryptosystem and extract the message (assuming
he has the public key).
He can't do this to a message encrypted with an ideal OTP (assuming he
doesn't have the OTP itself).
With public key systems, the information required to break the message is
publicly available - it just takes a lot of work to recover the message.
With an ideal OTP, no volume of work on the cyphertext will help recover
the message.
Security in an ideal OTP rests on information theoretic considersations.
Security in public key systems rests on unproven ideas about certain
mathematical operations being hard to perform quickly.
: WHat is scott19u? [...]
http://members.nbci.com/ecil/lnink1.htm
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ ILOVEYOU.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: DATA PADDING FOR ENCRYPTION
Reply-To: [EMAIL PROTECTED]
Date: Thu, 26 Oct 2000 23:44:47 GMT
Andrew Carol <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
:> Something simple like appending a 1 and padding with 0s to the end of the
:> block can allow up to 2^128 - 1 out of 2^128 keys to be rejected without
:> any further knowledge of the plaintext - possibly enough to reject all but
:> one message.
: They can't be rejected without TRYING THEM FIRST!
Well, OF COURSE NOT! ;-)
: If any kind of chaining mode is used then they can't use that last
: block until they get to that block.
You are mistaken - others have explained why.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Free gift.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Q: Computations in a Galois Field
Date: Fri, 27 Oct 2000 00:09:34 GMT
In article <8t9ptk$8lq$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Wagner) wrote:
> kihdip wrote:
> >Twofish and Rijndael (among others) use computations in a Galois
Field.
> >
> >Can any of you explain to me why the Galois Field is usefull.
(Advantages)
>
> It is used in Twofish and Rijndael as a fast and cheap way to get
diffusion.
> In software, it can be implemented efficiently as a lookup table. In
hardware,
> it can be implemented efficiently in a number of different ways (due
to the
> mathematical structure of GF(2^n)).
>
> Also, the mathematical structure of GF(2^n) allows you to build
diffusion
> structures with nice properties. For instance, Twofish uses it to
build a
> MDS matrix, which has some nice provable diffusion properties (see the
> Twofish paper for details).
not only that it can be used to create decorrelation modulues (i.e
random linear mappings) that are also ideal.
You can also combine things such as
F(x) = ax^-1 + b (in GF(2)^n)) and get an sbox with known DP and LP
maximums, but where the output is decorrelated (i.e hard to exploit the
xor-pair or linear-correlation tables).
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Hardware RNGs
Date: Fri, 27 Oct 2000 00:11:17 GMT
In article <[EMAIL PROTECTED]>,
David Schwartz <[EMAIL PROTECTED]> wrote:
>
> Tom St Denis wrote:
>
> > The problem is that virtually of the lsb's on my comp are zeroes,
with
> > a few ones... In fact last time I counted the ratio was about 7 to
1.
> > This means you need to gather about 100,000 bits before you can
safely
> > have about 160 bits (using SHA-1). However, the problem gets
> > worse...you must sample very slowly, otherwise the samples are
> > correlated... Thus sample at about 8khz. At 8khz it will take 12.5
> > seconds to gather enough inputs....
>
> If you are correct that one in every eight bits is a one and
they are
> otherwise uncorrelated, you should need no more than 512 bits of input
> to get 160 bits of entropy. Two hundred milliseconds worth of data
> should be perfect.
I wouldn't trust it either way. It's not meant to be a RNG....
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Rijndael and PGP
Date: Fri, 27 Oct 2000 00:10:23 GMT
In article <8ta35n$28l$[EMAIL PROTECTED]>,
"Michael Young" <[EMAIL PROTECTED]> wrote:
> Unlike Tom, the authors of the OpenPGP spec (RFC2440) did see value in
> offering the AES winner as an option (even before it was announced),
and
> put in placeholders for it.
>
> I'm in no position to say when, but I expect the major players
(PGP/NAI,
> GnuPG)
> to follow the OpenPGP spec. But maybe Tom has more pull with them
than I
> think.
> I guess I need to do more homework.
I have no pull whatsoever, I am just making a valid point.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Is OPT the only encryption system that can be proved secure?
Date: Fri, 27 Oct 2000 00:10:20 GMT
On Thu, 26 Oct 2000 23:18:38 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote, in
part:
>This bothers you? What specifically is the problem with this conclusion.
>The conclusion appears to me to be correct - I see no problem with an
>inability to be completely confident of your security.
I am bothered since it is presented as a counter to the proof that an
OTP is secure - specifically.
Because, even if messy real-world issues *do* impinge on the OTP - and
I have no problem with that in itself - the proof that the OTP has
information-theoretic security is still something valuable, and not to
be dismissed. Because that proof _distinguishes_ the OTP from other
cryptosystems; it shows that a level of security against *the
particular threat of* cryptanalysis - which is the only threat about
which we can say much mathematically - exists for the OTP but not for
other ciphers.
What bothers me isn't calling attention to the real world - it is the
claim that the real world makes a significant result, one of the few
pieces of knowledge we _do_ have, irrelevant.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: DATA PADDING FOR ENCRYPTION
Reply-To: [EMAIL PROTECTED]
Date: Thu, 26 Oct 2000 23:53:33 GMT
John Myre <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Something simple like appending a 1 and padding with 0s to the end of the
:> block can allow up to 2^128 - 1 out of 2^128 keys to be rejected without
:> any further knowledge of the plaintext - possibly enough to reject all but
:> one message.
: Nobody with any sense cares, and you know why.
I don't think this is true. I care - and I am not "without sense".
It is true that some people are prepared to trust security based on the
percieved difficulty of performing certain mathematical operations,
rather than security based on an information theoretical lack of ability
to determine whether keys are correct.
Even if the trust in their mathematical operations is well founded,
the ability to reject keys can still be useful - under some attack
models - since there are other ways beside cryptanalytic attacks for
key material to find its way into the hands of one's opponents.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ ILOVEYOU.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Is OPT the only encryption system that can be proved secure?
Date: Fri, 27 Oct 2000 00:21:35 GMT
On Thu, 26 Oct 2000 22:22:44 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote,
in part:
>The issue is that the
>OTP proof has implicit assumptions which easily can be overlooked.
>And even if we don't miss the assumptions, we may be unable to achieve
>them in practice.
The way I have percieved the phrasing of your comments on the
'provable security of the OTP', or the lack thereof, is that they
diminish the significance of the proof - enough to make it essentially
unimportant. That is what I object to, not that you remind people of
real-world concerns that indeed must not be forgotten.
>One such assumption is that the keying sequence is
>unpredictably random. Unfortunately, even though theoretical
>randomness is required, in practice, there is no way to prove that we
>have it.
Although one cannot prove that a physical random sequence is totally
without bias, that physical random number generators can be dependent
on initial conditions not likely to be accessible to an opponent _is_
clear.
Thus, thanks to chaos theory, I don't care if people believe in
quantum mechanics or not...to bring back memories of some rather silly
threads from times past.
>I'm not sure there even exists a good
>technique for accumulating a comprehensive list of the hidden
>assumptions upon which a "proof" depends.
I'm absolutely sure there _isn't_ if you want the proof to apply to
the real world in the sense you're looking for.
>For example: Where in the
>OTP proof do we find an explicit requirement for randomness, to say
>nothing of a description of the difficulties one might have in
>achieving that in practice?
The requirement for randomness _is_ an explicit condition of the OTP
proof. But the assumptions required to establish that a given physical
random number generator works, is not tampered with, is not
eavesdropped upon, and so on, would indeed be hard to compile.
But I think it is entirely legitimate to compartmentalize 'physical
security' and 'algorithmic security' into two separate boxes. If one
does not practice reductionism, one cannot make progress in learning
about the real world, one remains overwhelmed by its complexity. This
is a lesson learned in all the 'hard' sciences - since you have
expressed the desire that cryptography start becoming a science, why
expect cryptography to do things differently from every other science?
Thus, a proof that helps us understand what goes on in the
'algorithmic security' box is still valid and important despite the
fact that we also have a 'hardware security' box to address.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Save RSA bandwidth
Date: Fri, 27 Oct 2000 00:25:56 GMT
On 26 Oct 2000 14:10:44 GMT, [EMAIL PROTECTED]
(SCOTT19U.ZIP_GUY) wrote, in part:
>I feel this is so
>obvious I am sure other people have also thought of this.
I absolutely agree.
I've come up with _another_ idea, but I'm not sure if it really adds
me to the list of people who, along with the inventors of SPEKE, SRP,
and SNAKE, have found alternatives to EKE.
It is possible that this whole concept of iterated RSA is covered by
the EKE patent, even though it is different.
Let's say that I have 17 RSA public keys.
And with someone sending me a message, I share a secret - and that
secret leads them to use 8 of the first 16 keys in order, then the
17th and largest, in performing RSA encryption of the first part of
the message.
I'm not sure that this really provides any 'privacy amplification',
though, since all 17 moduli and encryption exponents are still public.
But it might provide some.
Still, performing nine RSA encryptions in sequence will generally be
considered too slow to be practical.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Factoring Polynomials
Date: Fri, 27 Oct 2000 00:26:57 GMT
In article <8t98g1$b3r$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> In article <8t83m9$fii$[EMAIL PROTECTED]>,
> Bob Silverman <[EMAIL PROTECTED]> wrote:
> > In article <8t7nr1$65g$[EMAIL PROTECTED]>,
> > Simon Johnson <[EMAIL PROTECTED]> wrote:
> > > Is factoring polynomials also an NP problem for large order
> > > polynomials just as factoring an integer is?
> >
> > You seem to have a bit of confusion. Both problems are trivially
> > in NP.
> >
> > You can not mean NP-Complete in place of NP, because factoring
> integers
> > is not known to be NP-Complete. Nor is it known to be in P.
> >
> > OTOH factoring polynimials is known to be in P (polynomial in the
> > degree; not in the size of the coefficients)
> >
> > What do you really mean here????
> Once again, my english is non-sensical. What i'm trying to establish
is
> that wether or not factoring a polynomial is NP or not.
Huh? I *already* answered this. I quote:
> > You seem to have a bit of confusion. Both problems are trivially
> > in NP.
Polynomial multiplication is easily seen to be doable in polynomial
time (in both the degree and coefficients). Therefore factoring
polynomials is trivially in NP. Given a (purported) factorization
you just multiply to verify the answer.
I have a suspicion that you are confused about the meaning of NP.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: My comments on AES
Date: Fri, 27 Oct 2000 00:29:01 GMT
On Tue, 24 Oct 2000 13:45:36 +0200, Volker Hetzer
<[EMAIL PROTECTED]> wrote, in part:
>It might be easier to design, but (if I understand you correctly) you
>just dump the responsibility of the key expansion at the door of the user.
>IMHO it's likely that any saved design time will result in a lot of weak keys.
I'm assuming that the key will not be so much larger that the user
will not fulfill the same obligations as with the key to a cipher with
a smaller key: full randomness of every bit in the key, either
physical, or by a secure hash function applied to a keyphrase of
sufficient entropy.
I didn't mean to do _without_ a key schedule, and just go to
independent subkeys. You are certainly correct that going that far
would be a serious mistake.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: My comments on AES
Date: Fri, 27 Oct 2000 00:33:54 GMT
On Thu, 26 Oct 2000 22:26:36 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote,
in part:
>Some people would say than an *attempt* at a break was just an
>"attack," and that only *success* in the attempt produces a "break."
>A cipher which has a "break" obviously is "broken" in one sense, but
>may still be usable and thus *not* "broken" in another, although that
>is a different issue.
Yes, and I also agree that for a cipher to have one weakness is not
proof of other weaknesses.
The mentality involved here is more that having a weakness says
something about the cipher's designer, and therefore makes the cipher
suspect as far as additional weaknesses are concerned. This can be
valid, under some circumstances, but it is blindly applied as a
blanket rule.
Thus, we get ciphers designed with the minimum possible key for the
desired level of security - which does ensure that the slightest
academic attack means that the desired level of security is not
achieved. I have no problems with good key schedules, but I do have a
problem with deliberately using fewer key bits.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.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
******************************
