Cryptography-Digest Digest #13, Volume #10 Sat, 7 Aug 99 20:13:04 EDT
Contents:
Re: Is breaking RSA NP-Complete ? ("rosi")
Re: Pencil-and-paper compression algorithms [Re: Between Silk and Cyanide]
("NewsUser.2436")
Re: About Online Banking Security (Keith A Monahan)
Re: key lengths (Jerry Coffin)
challenge/competition revisited (Gabe Simon)
Cracking challenge ([EMAIL PROTECTED])
Re: What is "the best" file cryptography program out there? (Jerry Coffin)
Re: challenge/competition revisited (Jim Gillogly)
Re: AES finalists to be announced ([EMAIL PROTECTED])
Re: Is breaking RSA NP-Complete ? (Nicol So)
Re: Construction of permutation matrix (Nicol So)
----------------------------------------------------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: Sat, 7 Aug 1999 14:16:18 -0400
Hold it right there! (I take it as formal.)
--- (My Signature)
P.S.
Dear Safuat, thanks for the definitions and clarifications. As a matter
of fact, I have no preference. All given, including the ones quoted by
Bryan Olson, are in a larger sense acceptable to me. I just wonder if
we are playing Variantions on the Theme of Limbo.
To have an unacceptable 'simplification', and in small violation of
1. of yours, here is a notation of the hierarchy:
P(-hard)^x, where x is of the format nm where m is in
the format of (.k)* for n, k integers (Lots of coincidences
of course if we talk about complexity and not finding the
reducing function is not the same as there is no such.)
Also remember to use special numbering schemes so
that those temporarily having no definite place in the
hierarchy can be handled.
A couple of other things I can have questions on, but obvious
IMO to readers. And I said 'Hold it right there!"
======================
Safuat Hamdy wrote in message ...
>Nicol So <[EMAIL PROTECTED]> writes:
>
>> > > I have seen different definitions of NP-Hard. The definition I
prefer
>> > > is:
>> > >
>> > > A problem is NP-Hard if it is polynomial time reducible (in the sense
>> > > of Karp reducibility) to the hardest problem in NP.
>> >
>> > My impression (derived from a possibly too small set of samples) was
>> > that nowadays most people agree that NP-hardness is about
>> > Turing-reductions ... isn't that also the definition that Garey &
>> > Johnson seem to prefer?
>>
>> I could be wrong, but my impression is that people these days prefer
>> (polynomial-time) many-one reduction to (polynomial-time) Turing
>> reduction when dealing with NP-completeness. Do people have a different
>> preference when dealing with NP-hardness?
>
>Since complexity theory was one of my main subjects, I claim to have some
>knowledge about the terms used here. For reference I prefer Baclazar,
Diaz,
>Gabarro, Structural Comlexity, 2nd ed, 1994. This is much more up to date
>than most other books like Garey, Johnson or Hopcroft, Ullman.
>
>Some clarifications:
>
>Let C be any complexity class
>
>1. C-hard and C-complete by default refers to poly-time many-one reduction,
> whenever C is above P, while for P and NLOG (and all other classes above
> LOG) it refers to log-space many-one reduction. For two sets A and B we
> write A <= B, whenever A is many-one reducible to B. Note also,
> "reducible" means by default poly-time many-one reducible.
>
>2. When we really want to speak about Turing reducibility, we say C-T-hard
> and C-T-complete (of course, in certain contexts where there is no
> ambiguity, we can abbreviate this). For two sets A and B we write A
<=_T
> B, whenever A is Turing reducible to B. Note that Turing reducibility
> usually refers to poly-time Turing reducibility.
>
>3. Def: Some set A C-(T-)hard if and only if any set B from C is
> (Turing-)reducible to A. Moreover, if A itself is in C, then A is
> C-(T-)complete.
>
> These are the modern definitions for hard and complete, everything else
> is fuzz from the past.
>
>4. To remove any doubts: Def: Let A and B be sets over some alphabet S. A
> is poly-time many-one reducible to B, if and only if there exists a
> deterministic poly-time computable function f such that for any x from
> S^*, x is in A if and only if f(x) is in B; similar for space-bounded
> many-one reducibility, although here f additionally must not expand it's
> input too much (why? Well, we do want our reducibility to be
transitive,
> don't we?).
>
> Turing reducibility is somewhat more subtle for it requires the notion
of
> oracles (See Structural Complexity). But believe me that many-one
> reduciblity is the "natural" one, therefore it makes perfectly sense to
> make it the default reducibility.
>
>--
>
>S. Hamdy | All primes are odd except 2,
>[EMAIL PROTECTED] | which is the oddest of all.
> |
>unsolicited commercial e-mail | D.E. Knuth
>is strictly not welcome |
------------------------------
From: "NewsUser.2436" <[EMAIL PROTECTED]>
Subject: Re: Pencil-and-paper compression algorithms [Re: Between Silk and Cyanide]
Date: Sat, 7 Aug 1999 08:22:18 +0100
Reply-To: paul <[EMAIL PROTECTED]>
In article <[EMAIL PROTECTED]>, wtshaw
<[EMAIL PROTECTED]> writes
...
>There have been official and unoffical changes over the years, and I add a
>very few here for interests of completion. For efficiency's sake, lots of
>the longer strings could be replaced with unassigned shorter ones. I
>believe that the ACA list of some of them uses a few obsolete punctuation
>forms, changed since WWII.
>
>I hope I did not make a mistake in transcribing the list, but leave that
>possibility open.
>
>FIRST GROUP--2 to 5 TRITS (all possibilities)
>
>00 = blank or space -- trits only
...
Thanks - I'll have a play with them!
--
Paul newsuser.2436 @ G 4 I K J .demon.co.uk
Never argue with a fool, he may be doing the same.
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: About Online Banking Security
Date: 7 Aug 1999 13:12:36 GMT
Greg,
The difference is that everyone has access to the internet, has access to
equipment that internet traffic runs through, etc.
The ATM comm lines are somewhat proprietary, and although this might be
security through obscurity, there are simply alot more people familiar
with internet/ip/SSL than with ATM's.
I believe ATM's use X.25 networks, is this right?
Keith
Greg ([EMAIL PROTECTED]) wrote:
: > ATMs are for the most part secure devices
: > now (???).
: Would you say that 40 bit SSL over the internet is more insecure than
: ATM machine comm lines? If not, then what's the difference?
: --
: The US is not a democracy - US Constitution Article IV Section 4.
: Democracy is the male majority legalizing rape.
: UN Security Council is a Democracy. NO APPEALS! Welcome to the NWO.
: Criminals=Crime. Armies=Tyranny. The 2nd amendment is about tyranny.
: Sent via Deja.com http://www.deja.com/
: Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: key lengths
Date: Sat, 7 Aug 1999 12:41:05 -0600
In article <7oha35$ug2$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> > It's also worth noting that many of the better attacks typically
> > reduce the difficulty of an attack by a more or less fixed factor
> > compared to a brute-force attack on the same cipher.
> >
> Then the cipher has been broken.
Of course -- but how many ciphers have been in use for, say, 20 or 30
years and NOT been broken to at least some degree? The number is
vanishingly small. We can design algorithms to be resistant to known
breaks, and we can use some general principles we believe will make
them hard to break in general, but if we design an algorithm with the
expectation of using it for an extended period of time, we should plan
on the fact that eventually somebody's likely to break it to some
degree or other.
> However most iterative attacks are not practical making brute force
> still the only way.
Presumably here you're talking about things like differential and
linear cryptanalysis. Differential cryptanalysis is often practical
against designs that weren't designed to resist it -- just for
example, it was quite a practical attack on Lucifer. Obviously
anybody who knows what they're doing now is going to design their
algorithm to resist known attacks, but it's almost inevitable that
somebody's going to invent new attacks in the future.
> > This means that an attack that reduced the work involved by a factor
> > of, for example, 100, might be extremely damaging to a cipher with a
> > marginal key-size, but mean nothing against an otherwise similar
> > cipher with a larger key.
>
> I would rather have no attacks that are feasible then rely on huge keys.
So would anybody. Unfortunately, without knowing all the attacks
people are going to invent over the operational life of the cipher,
there's no way to know what attacks will be feasible.
> Well if you know what you are doing then you could design the key
> schedule along with the algorithm. If you design to avoid any
> characteristics your entire key should be effective.
What does this have to do with anything? Of course you design your
key schedule along with your algorithm, and of course you do what you
can to ensure that the entire key is effective. This applies
regardless of the size of key you use, so I'm completely lost as to
how it relates to key sizes at all.
> But key length generally doesn't say much about the actual strength of
> a cipher unless it's perfect.
Quite the contrary -- it tells you something about the degree to which
the cipher can be imperfect before an attack becomes practical.
------------------------------
From: [EMAIL PROTECTED] (Gabe Simon)
Subject: challenge/competition revisited
Date: 7 Aug 1999 20:54:10 GMT
Well, judging from the responses I got to my previous post (8/5/99) I
guess no site exists that contains what I had in mind. Let describe more
specifically what I was hoping for, and anyone who's interested could
maybe help me set it up.
The site would have two different sections: cyphertext with known
algorithms and just plain cyphertext. In each section, there would be a
range of difficulties ranging from absolute novice (simple
substitution,ceasar cypher's etc.) to advanced (DES, distributed.net
kinda shit), with everything in between. I am not talking about some
kind of coveted world competetion here... just something where interested
parties can go and have a crack at (no pun intended) breaking some
cyphers that are accesible to them. Another potential use for this site
would be for people to test new cryptosystems. If Alice designs a new
cryptosystem and she wants to see how secure it is, she can post it on a
special section of this site and let Billy and Carl have a go at it.
Again, I'd like to stress that I am just a novice, quite new to the
field, and I really don't have any expertise in the area, but after a few
days of searching the net/newsgroups for cryptanalysis challenges I found
it lacking. Please volunteer ideas if you have 'em. Thanks.
Gabe Simon
------------------------------
From: [EMAIL PROTECTED]
Subject: Cracking challenge
Date: Sat, 07 Aug 1999 20:50:32 GMT
Its been 4 day and Little Tom boy have NOT cracked fortom.cpt. He cant.
2 of you peoples has mailed me the good answer. Thanks yous for not
telling him.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: What is "the best" file cryptography program out there?
Date: Sat, 7 Aug 1999 12:41:07 -0600
In article <7ohakg$upm$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> 5Ghz computers will not be made any time soon, and when they are it
> won't be until another 10 years before the public sees them. You have
> to rememeber that a 5Ghz computer would take too much energy to run
> though.
The extremely expensive machines in the single digit GHz range that
won't make it to the public happened years ago. As it happens, I live
in Colorado Springs, the home of Cray Computer, Inc., before Seymour
got killed. I was lucky enough to get to go see one of the (three)
Cray 3's that got built, 7 or 8 years ago. Even at that time, they
ran at 1 GHz. If Seymour was still alive, and there was a market to
support it, I'm confident he'd be building machines that ran at around
10 GHz or so by now.
In machines closer to the consumer level, Samsung has been building
Alpha 21264 chips since the end of last year. By the end of this
year, they plan to ship 1 GHz chips. When they get their fabrication
tuned well, it should be able to run at around 2 GHz or so.
It's also worth nothing that Alphas tend to be substantially faster
than Intel chips at the same clock speed -- it depends somewhat on the
sorts of things you're doing, but figure around double the speed at
integer work and around quadruple at floating point work.
IOW, by the end of this year, anybody with a few thousand dollars to
spare will be able to buy a machine that's equivalent to approximately
a 2 GHz Intel chip. In another year or so after that, they'll be able
to buy the equivalent of a 4 GHz Intel chip.
To make a long story short, the kind of speed you're talking about is
a LOT less than 10 years off; three years would be a LOT closer to
reality.
> If we linearly scale a 200mhz machine (2^20 keys/sec) to a 5000mhz
> machine (2^24.64 keys/sec) it will still take 2^55.35 seconds to search
> an 80-bit key. That is 731,178,021 years avg per key. Throw a million
> at it and you are at 731.17 years.
Things rarely scale linearly, or anywhere close to it. Consider that
a 16-bit multiplication on a 486 takes 13 to 26 clock cycles.
The Pentium III using the streaming SIMD instructions can do four
multiplications with a single instruction, and can execute one of
these every cycle (and execute a couple of other instructions at the
same time as well).
IOW, with carefully optimized code, a Pentium III could be around 100
times as fast as a 486, even at exactly the same clock speed.
> But you are limited by such fundemental things. The fastest chip I
> have seen was 1.6Ghz even then it was liquid cooled and cost millions.
> I don't expect them to be publicly avail anytime soon for say 200
> dollars (same price for a decent intel chip).
I don't think a 1.6 GHz chip should cost millions at the present time.
In fact, it wouldn't surprise me if a current Alpha would run that
fast with liquid cooling, and they can be gotten for a few thousand
dollars. For that matter, if you didn't mind sorting through a few
chips, it wouldn't surprise me if you could find a few Intel (or
PowerPC) chips that would run at over a GHz -- keep in mind that to
maximize yields, Intel is VERY conservative in their chip ratings.
They've done demos for years of (carefully chosen) chips running at
two and three times the maximum currently available clock speeds.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: challenge/competition revisited
Date: Sat, 07 Aug 1999 22:57:32 +0000
Gabe Simon wrote:
> Well, judging from the responses I got to my previous post (8/5/99) I
> guess no site exists that contains what I had in mind. Let describe more
> specifically what I was hoping for, and anyone who's interested could
> maybe help me set it up.
While it's not on-line, it sounds like you're looking for something
like the American Cryptogram Association: about 100 ciphers every
two months of varying difficulty: simple substitution with or without
word divisions, Playfair and other classical systems, "unknowns", and
foreign language cryptograms. At $15/year it's quite a bargain ($5 extra
for the first year to cover initialization materials). Check the Crypto
Drop Box at http://www.und.nodak.edu/org/crypto/crypto/ for more
information, or if you can tell already it's what you want, send $20 to:
ACA Treasurer
1118 Via Palo Alto
Aptos, CA 95003
If you're outside North America, check the Crypto Drop Box for
postage to your country.
> The site would have two different sections: cyphertext with known
> algorithms and just plain cyphertext. In each section, there would be a
> range of difficulties ranging from absolute novice (simple
If you start such a web site, please post the info here.
--
Jim Gillogly
Trewesday, 15 Wedmath S.R. 1999, 22:50
12.19.6.7.13, 5 Ben 1 Yaxkin, Ninth Lord of Night
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: AES finalists to be announced
Date: Sat, 07 Aug 1999 23:06:37 GMT
In article <[EMAIL PROTECTED]>,
Volker Hetzer <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> >
> > I have been informed by NIST that the five or so AES finalists will
be
> > announced next Monday at 10 am. My Frog algorithm, as expected, will
> > not be one of them.
> What time zone?
I guess local California time, i.e. later than 10 am for most of the
rest of the world. By the way, NIST's site about AES is: aes.nist.gov
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: Sat, 07 Aug 1999 19:21:34 -0400
[EMAIL PROTECTED] wrote:
>
> I wrote:
> > NP-Hard is neither a subset nor superset of PSPACE.
>
> Ooops, another mistake. The question of whether
> NP-Hard contains PSPACE is still open. NP-Hard
> is a superset of PSPACE if and only if P=NP.
>
> Utterly trivial of course.
I guess my complexity theory is rustier than I thought it was. In the
definition of NP-hardness, there's no upper bound on how hard the
problems get--the sky is the limit. From your comment, it seems that
you had a simple argument in mind why the NP-hard problems include
PSPACE only if P = NP. Care to share it with the rest of us? Thanks.
Nicol
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Construction of permutation matrix
Date: Sat, 07 Aug 1999 18:57:26 -0400
wtshaw wrote:
>
> In article <[EMAIL PROTECTED]>, Nicol So
> <[EMAIL PROTECTED]> wrote:
>
> > [EMAIL PROTECTED] wrote:
> > >
> > > [Description of the familiar algorithm for permuting elements of an
> > > array, deleted]
> > >
> > > If you can extract fractions of bits and have log2(n!) bits of key this
> > > will be complete (all permutations are possible).
> >
> > You can extract a non-integral amount of bits by interpreting the bit
> > string as an arithmetically encoded string of symbols.
> >
> Whether something can be in bits or not is entirely irrelevant as any
> keylength can be expressed in unit of information unit, and permutations
> generally do not come out to even quantities in any of them. When ever
> someones speaks of fractions of bits, it is only a mind thing that looks
> good to those that falsely believe that bits are especially fundamental to
> everything.
A bit in this context is a measure of information. As such you are not
limited to having an integral number of bits. The unit bit is somewhat
special in this particular context because the seed is already
*represented* as a bit string. "Extracting" an integral number of bits
from a bitstring can be accomplished simply by taking prefix. To
extract a non-integral number of bits, you need to do something slightly
more complicated. What I did was to suggest one such method. I was not
suggesting that there is anything magical about 2 as the radix of a
number system.
Nicol
------------------------------
** 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
******************************
