Cryptography-Digest Digest #667, Volume #13 Sat, 10 Feb 01 01:13:01 EST
Contents:
Re: relative key strength private vs public key (Bob Silverman)
Re: CipherText patent still pending (Bryan Olson)
Re: Factoring (and not the Philippino :) ("Michael Brown")
Re: ideas of D.Chaum about digital cash and whether tax offices are delighted ?
(zapzing)
Re: Phillo's alg is faster than index calculus (Bryan Olson)
Re: Factoring (and not the Philippino :) (David Wagner)
Re: Shortening ElGamal encryption (David Wagner)
Re: NPC ("rosi")
Re: What do you do with broken crypto hardware? ("rosi")
Re: NPC ("rosi")
Re: NPC ("rosi")
Re: NPC ("rosi")
Re: NPC ("Scott Fluhrer")
----------------------------------------------------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: relative key strength private vs public key
Date: Sat, 10 Feb 2001 01:59:07 GMT
In article <[EMAIL PROTECTED]>,
Steve Portly <[EMAIL PROTECTED]> wrote:
<snip>
> > It is better to simply say "product of two primes".
>
> Good food for thought. Assuming a sieving technique is being
employed to
> factor composite prospects whether they be the product of two primes
or
> more, I don't see a big jump in the difficulty when you increase the
number
> of primes used in the composite?
Huh? How did we get from a discussion about terminology into one
involving factoring via sieve of Eratosthenes????
I wanted to know the rationale behind your definition of
"prime number composite".
>Since I am
> limited by the constraints of C++ to word128 values my keys would
You are inventing terminology again. What are "word128" values?
Do you mean that C++ constrains longs or long longs to a max of
128 bits? If so, this is irrelevent, since all public key
algorithms are coded using multi-precision arithmetic anyway.
>need to be less than 10000 bits in size.
Why? A multi-precision number could be 1 billion bits in size;
even using C++.
10000 bits is massive overkill for any current system anyway.
In a practical sense therefore using
> composites with many primes would be silly since the constituent
primes
Where did I ever suggest doing this????
> I would have no knowledge of keys larger than 10000 bits in size
since such
> a key would exceed a word128 receiving field on my desktop computer.
Noone uses keys this size.
> Key size recommendations for public keys increase over the years with
the
> increasing factoring ability of available hardware. 128 bit public
keys
> were considered adequate at one time.
More mis-information. Where did you get this? At one time
128 DIGITS was considered safe, but NEVER 128 bits.
> > > > 2) How do you propose to do away with needing them?
> > >
> > > Sometime in the future perhaps they will remove the prime
requirement
> > from
> > > ECC.
> >
> > Which prime requirement is that? The requirment that the public
> > base point have prime, or near prime order? This can never be
> > eliminated, otherwise one would have a "small subgroup" attack.
>
> The curve arithmetic is performed modulo p, where p is either a large
prime
> number or large power of two.
This is the field over which the curve is defined. This information
is PUBLIC. The security of ECC crypto does not depend in any way
on this prime being secret.
If a table of large primes representing all
> possible base points used by ECC
You are babbling. primes do not represent base points.
You seem to have a FUNDAMENTAL lack of knowledge about how these
systems work. May I suggest that you actually STUDY them?
> were ever developed some time in the future
> it would shorten the time it takes to break current keys.
Once again: more nonsense. The base point is ALSO public.
The private key in EC crypto is a random integer. It has nothing
whatsoever to do with prime numbers.
> The only point to be made is that "safe" key strength is relative. A
secure
> prime
I tried patiently to explain that there is NO SUCH THING as a
"secure prime". Why do you continue to use this terminology?
> > Why do you believe that easily finding primes
> > would make it hard for consumer owned machines?? What has one got
to
> > do with the other?
>
> Perhaps I am being short sighted. Consumer owned desktop machines in
the
> future will probably be able to handle larger keys in Word256 sized
fields.
They can handle ANY size key **today**, up to the address space limit
of the machine.
> I was thinking that since sieving primes becomes increasingly easier
You are again inventing terminolgy. What do you mean by
"sieving primes"??? Why do you say it becomes easier? I will
give a hint: finding primes near n takes time O((log n)^4).
This INCREASES as n increases.
at
> some point in the future the ability of a consumer owned desktop
machine to
> create a "safe" prime might be in jeopardy.
This sentence "isn't even wrong". It is nonsense.
Go and study this subject. We might then have common ground to
discuss it. You notions seem so "wrong-headed" (no flame meant)
that it is hard to discern what you mean. I'm not sure that
even you know what you mean.
--
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/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: CipherText patent still pending
Date: Sat, 10 Feb 2001 02:04:23 GMT
Mok-Kong Shen wrote:
> The quote in question was the following:
>
> Experts teaching writing say to write every day. I've never
> heard an expert cryptologist recommend cipher design as an
> exercise.
>
> There is very good reason to stress the importance of
> analysis. A student should well do exercises in analysis
> before going to design. But that doesn't mean that the
> teacher does not give the student design excercises at a
> later stage to do, if he is to do his teaching job properly.
> That's why I considered the above quoted to be misleading
> and argued against correspondingly.
The quote is easy to refute if wrong; just look through the
crypto textbooks, or course syllabi. I don't see the point
of arguing against an observation with only conjecture and
opinion.
> I am not sure it is clear that cipher design is easy.
I'm convinced it's very hard to do well. I recall spending
many hours trying to convince you of the same.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Re: Factoring (and not the Philippino :)
Date: Sat, 10 Feb 2001 15:56:38 +1300
"John Savard" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Sat, 10 Feb 2001 13:57:02 +1300, "Michael Brown"
> <[EMAIL PROTECTED]> wrote, in part:
>
> >Correct, but you break the number into two smaller peices (by selecting
> >where the bits are different and doing the algebra like thing) then do a
> >primality test on the two numbers and repeat if necessary (try it, and
> >you'll se what I mean :)
>
> My point is that since the two smaller pieces aren't always _unique_,
> why should - and how could - a method like yours work at all?
I would guess, because I have mainly focussed on factoring composites (for
obvious reasons :) and haven't tried factorisations of non-composites except
one I accidentally did, that the algebra would show that a1=b1, a2=b2 etc,
but I really don't know. I'll give it a go when I have some spare time (or
you can if you want :)
>
> Of course you can repeat a method that splits a number into two
> factors if non-prime to obtain a complete factorization, as you note.
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
Thanks for your ideas,
Michael
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.cypherpunks
Subject: Re: ideas of D.Chaum about digital cash and whether tax offices are delighted
?
Date: Sat, 10 Feb 2001 02:52:51 GMT
In article <[EMAIL PROTECTED]>,
"Thomas J. Boschloo" <[EMAIL PROTECTED]> wrote:
> Reply-to: <boschloo<at>multiweb<dot>nl>
>
> -----BEGIN PGP SIGNED MESSAGE-----
>
> Ariel Burbaickij wrote:
> >
> > E.g . In many countires tax offices must be informed of facts of
purchaes
> > worth some amount ,
> > considered serious . So cash is surely frawned upon in such
countires
>
> Another problem with anonymous cash is that combined with anonymous
> publishing, it will not be possible to stop commercial child porn. I
> would give up the former in favor of the later, although I would most
> likely give up the ability of stopping child porn in favor of both
> (Child porn should just be given away for free at police web sites
with
> a dramatic story attached and links to self-help forums. That way
no-one
> could make any money on Child porn anymore. Saturate the market, don't
> create an artificial scarcity of the 'product', which drives up the
> price and the risk child pornographers are willing to take).
>
> I feel no desire to see child porn myself, just to make clear that
there
> is no hidden agenda here,
> Thomas
This whole thing about child porn is
so crassly insincere. If they were
really concerned about children they
would do something about poverty and
sweatshops. They don't care a whit
about children. They just want to
shut down the Internet, and they are
willing to use any excuse to do it.
--
Void where prohibited by law.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Phillo's alg is faster than index calculus
Date: Sat, 10 Feb 2001 02:55:39 GMT
[EMAIL PROTECTED] wrote:
> How about RSA? m^e = c mod pq, c^d = m mod pq
> The message m won't be a generator.
> Then c and m may have small cycles.
A variant of Pollard Rho still blows your method
away. It works in time proportional to the shorter
of the mod p or mod q cycle length, times some
polylogarithmic term.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Factoring (and not the Philippino :)
Date: 10 Feb 2001 04:46:50 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Douglas A. Gwyn wrote:
>Is it a theorem that knowing (N,e,d) allows a fast
>recovery of p and q?
Yes. It should be in the standard crypto texts.
(It's a very easy exercise when N is a product of two
primes; it's a more interesting problem for general N.)
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Shortening ElGamal encryption
Date: 10 Feb 2001 05:00:11 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Your suggestion was:
To encrypt M, send (t, M * g^{x_s x_r t}), where x_s is the
sender's private key and x_r is the receiver's private key.
This is insecure against known-plaintext attacks.
In particular, suppose I have a single known plaintext M along with
its encryption (t, M * g^{x_s x_r t}). This reveals g^{x_r x_s}.
Then, if I see any further ciphertexts from s to r, I can decrypt
them myself without the help of the receiver.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: NPC
Date: Sat, 10 Feb 2001 01:18:31 -0500
Peter Shugalev wrote in message <95tsj8$3ql$[EMAIL PROTECTED]>...
> I think someone tried to prove that either discrete log or factoring
>problem is NPC (not just NP). I'd like to see some results of these
>attempts.
>
David Molnar may have a few good pointers.
>And if they are *not* NPC. Do you know any attempt to create a public key
>algorithm based on the problem that is known to be NPC?
>
>
It very much depends on what is meant by 'based on'. Merkle-Hellman is
one "based on" an NPc problem, but one can still very well argue if it
really
is or is not NPc (not just "based on" NPc).
Even if it (MH) is not, empirical results do not conclude. It could be
that a very
successful solving algorithm only shows a bit of 'fatigue' beyond 53 zillion
bits.
Maybe, there is a proof that it is not, but I do not know.
However, the problem of P ?= NP does not fit cryptography as some would
like it to be. P = NP does not imply in a practical sense that practical
solutions
exist for all the problems in NP. I think we have to remember that those are
'theoretical' gauges. It is the rates of growth that are of interest.
Whether a
particular cipher, with whatever key size, is secure is at a slightly
different level
of interest. If the best algorithm for a crypto problem is of complexity
n^1000000
(base 2^10000), but say n^3 for encryption and decryption, P = NP can smell
a bit differently. (But for heaven's sake, do not interprete that as I have
one such
problem. I do not) I do not know for sure, but there is a sense that when we
are
talking about P = NP, some substitute that for NP = LOP (low order), such as
O(n^6). It may be true that all NP problems are of complexity bounded by
O(n^3).
That is more philosophical than mathematical, IMHO. On the other hand, even
if
P != NP, it is a problem that is virtually everywhere 'hard' that is of
interest.
Anyway, if you ask: Can there be a crypto problem (one that posed by a
concrete cipher system) that is at least as hard as an NPc problem and
virtually 'everywhere hard', the answer is a likely YES.
--- (My Signature)
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: What do you do with broken crypto hardware?
Date: Sat, 10 Feb 2001 01:14:51 -0500
Not a hw person, so forgive me for the ignorance. I am just curious.
How was the secret in the hw in the first place? By the manufacturer?
The customer has the equipment as part of the shipment of the product
with which the secret is burned in? Can it be re-burned? If it can and
the customer has the equipment, this is not a problem, or is it? If it is
beyond repair, there is no problem (I mean, it should not be a problem
one struggles with).
I am not sure, but if re-burning is possible, there seems a security
problem. Should crypto hw (that holds secrets) be tamper-proof?
Should such devices be read-only? Why allow any repair?
What is meant by 'modularization'? I think, although implcit, Paul was
talking about modularized hw pieces already. The level to which one can
modularize is high. I tend to believe that intermediate results of a crypto
function can not be exposed. One perhaps can modularize to (P)RNG,
or cryptor level, but I doubt any lower than that.
Therefore, I agree with most people. Let the return route be from the
black-hole. But if anybody can clarify a bit, I would be very appreciative.
The following may make a bit of sense (as it is not hw related). Paul
raised a very good point. My opinion is this:
If one faces such a dilemma (should one risk the secret being
exposed to the manufacturer, and possibly to the whole world),
there is a fundamental design flaw.
To be clearer, I am talking about forward and backward secrecy
(the version by Ross Anderson).
--- (My Signature)
Steve Roberts wrote in message <[EMAIL PROTECTED]>...
>I would essentially agree. The parts of the unit that hold or may
>have held crypto materials must be physically destroyed with the
>proper witnesses present. Floppies go into the shredder and I have
>known a bank that sent someone trotting along to SimsMetal to toss
>hard disk platters (already physically damaged) into their crusher.
>
>I know of a governmental institution that had similar problems. I
>believe their broken stuff was first of all broken some more, then
>encased in reinforced concrete and dropped into the ocean halfway
>along a voyage of some sort. Destroying magnetic tapes were a real
>problem - I suggested a sort of schoolboy bomb that would melt the
>matrix into a sort of goo.
>
>Secure hardware in dodgy locations (liable to get captured in war etc)
>can have its own chemical/explosive kit installed - for example a
>little explosive charge on each VLSI chip - you might not have time to
>whop it with a sledgehammer. (And when they come over the wall, the
>guy hitting things with the sledgehammer will be the focus of
>interest).
>
>Steve
>
>
>>In my bank IT Security experience (not Citibank), a faulty unit would
either
>>be compacted along with a junk car body, or industrial incineration,
>>witnessed by myself or other relevant bank person.
>>
>>Lyal
>>
>>Paul Rubin wrote in message <[EMAIL PROTECTED]>...
>>>[EMAIL PROTECTED] (Peter Gutmann) writes:
>>>> In addition, erasing the cell doesn't necessarily mean the data is
>>>> really gone. If you're really concerned I'd physically destroy the
>>>> memory, and if you're really paranoid and worried about big-budget
>>>> attackers, the crypto device it fed as well.
>>>
>>>I'm wondering what normal policy is in high security commercial
>>>organizations, e.g. What Would Citibank Do? In practice I don't think
>>>we're that paranoid. We're just trying to identify and follow best
>>>industry practices for this type of operation.
>>
>>
>
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: NPC
Date: Sat, 10 Feb 2001 01:21:36 -0500
Benjamin Goldberg wrote in message <[EMAIL PROTECTED]>...
>Peter Shugalev wrote:
>>
>
>The knapsack problem is NP complete, but the most of the PKE systems
>which use it are broken due to lattice attacks (their method of
^^^^^
I do not think we are conclusive that 'it' is an NPc problem used.
>transforming a hard problem into a PKE system is flawed). The only
>knapsack-like system which isn't broken by lattice attack is NTRU.
I seem to understand that NTRU tried to stay away from the word
'knapsack'. Just a quite incomplete observation.
>
>I don't know of any other NPC problems which are used as ciphers. Maybe
>someone else does?
Again, I am a bit choosy here. I doubt if we are that keen on another as
of now. One NPc is, based on the current state of the art, quite good
enough.
(Can be wrong, but c stands for complete)
>
>--
>A solution in hand is worth two in the book.
>Who cares about birds and bushes?
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: NPC
Date: Sat, 10 Feb 2001 01:21:52 -0500
Scott Fluhrer wrote in message <95vvfp$q25$[EMAIL PROTECTED]>...
>
>Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> Peter Shugalev wrote:
>Actually, it is possible that P!=NP, and yet NP complete problems could be
>solved in subexponential/superpolynomial time. This would imply that all
NP
>problems could be solved in subexponential time.
>
Does it seem harder or easier to prove 'P!=NP' vs 'NP problems are
at most subexponetial in complexity'? Just curious.
>--
>poncho
>
>
>
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: NPC
Date: Sat, 10 Feb 2001 01:23:42 -0500
Peter Shugalev wrote in message <960eb5$pv1$[EMAIL PROTECTED]>...
>> > I think someone tried to prove that either discrete log or factoring
>> > problem is NPC (not just NP). I'd like to see some results of these
>> > attempts.
>> >
>> > And if they are *not* NPC. Do you know any attempt to create a public
>> > key algorithm based on the problem that is known to be NPC?
>>
>>
>> The knapsack problem is NP complete, but the most of the PKE systems
>> which use it are broken due to lattice attacks (their method of
>> transforming a hard problem into a PKE system is flawed). The only
>> knapsack-like system which isn't broken by lattice attack is NTRU.
>
>What does it mean "their method of transforming a hard problem into a PKE
>system is flawed"? Think about RSA: if you break RSA in a polynomial time
>you'll get a polynomial method of factoring. When I speak about the PKE
>based on the NPC problem I mean that breaking the PKE automatically solves
>the NPC problem. As far as I can see these flawed PKE systems might gone
>wrong in three ways:
>
>1. They are not really based on the NPC problem but on its subset. And that
>subset is solveable in polynomial time.
>
Choosy again. Subset is still a set of NPc problems?
Or NPc set is not a subset of NP (as currently viewed), but rather a
super set of NP
(as the wonderful hierarchy)?
>2. In general case the algorithm is exponential (or at least
>superpolynomial). But there is an algorithm that with high probabilty
solves
>the problem in polynomial time (but it doesn't work in 100% of possible
>cases).
>
This sounds right. But first that it has to be NPc.
>3. The algorithm is exponential. E.g. its complexity is A*exp(a*n) where n
>is key length. But A and a constants might be too small, so n should be too
>big to stop the attacker. And n is big enough to make the PKE inpractical.
>
Can this be that generalized? I am not sure, but I would not rule out
the
possibility that from that one (with the small A and a) you can build one
with big B and b. At least I have not seen a proof that one can not yet.
>So, what was wrong with knapsack-based PKE systems?
Do you mean MH or the knapsack problem itself as a basis for a
cryptosystem? For the former, the problem is it is broken and conjectured
(a convincing one) insecure for practical key sizes. For the latter,
nothing.
>
>
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: NPC
Date: Fri, 9 Feb 2001 22:02:07 -0800
rosi <[EMAIL PROTECTED]> wrote in message news:962jrv$cie$[EMAIL PROTECTED]...
> Scott Fluhrer wrote in message <95vvfp$q25$[EMAIL PROTECTED]>...
> >
> >Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
> >news:[EMAIL PROTECTED]...
> >> Peter Shugalev wrote:
> >Actually, it is possible that P!=NP, and yet NP complete problems could
be
> >solved in subexponential/superpolynomial time. This would imply that all
> NP
> >problems could be solved in subexponential time.
> >
>
> Does it seem harder or easier to prove 'P!=NP' vs 'NP problems are
> at most subexponetial in complexity'? Just curious.
Well, one simple proof that NP problems are subexponential would be to
demonstrate a subexponential algorithm for an NP complete problem (any one
will do). The only slight problem with this proof technique is finding such
an algorithm, but I will leave that as an exercise for the reader...
I don't know if we even have an idea what a proof of P!=NP would even look
like, so it would *seem* harder to prove...
--
poncho
------------------------------
** 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
******************************
