Cryptography-Digest Digest #974, Volume #9 Tue, 3 Aug 99 00:13:03 EDT
Contents:
Re: PC Encrypt ([EMAIL PROTECTED])
Re: Is breaking RSA NP-Complete ? (David A Molnar)
Re: Intel 810 chipset security ([EMAIL PROTECTED])
Re: With all the talk about random... ("rosi")
Re: With all the talk about random... ("rosi")
Re: [Q] Why is pub key cert. secure & free from spoofing? ([EMAIL PROTECTED])
Re: How to write REALLY PORTABLE code dealing with bits (Was: How Big is a Byte?)
(O. Y. Realmink)
Re: Virtual Matrix Encryption (David A Molnar)
Prime number. (Teh Yong Wei)
Re: the defintion of Entropy ("Trevor L. Jackson; III")
Re: How to keep crypto DLLs Secure? ("Douglas A. Gwyn")
curing stutter by tradifional chinese medicine ("daniao")
Re: (Game) 80-digits Factoring Challenge ("Greg Keogh")
Re: Help please (WWI/WWII ciphers) ("Douglas A. Gwyn")
Re: With all the talk about random... ("Douglas A. Gwyn")
Re: the defintion of Entropy ("Douglas A. Gwyn")
Re: the defintion of Entropy ("Douglas A. Gwyn")
Re: Cryptanalysis of R250
Re: the defintion of Entropy ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: PC Encrypt
Date: Tue, 03 Aug 1999 00:13:11 GMT
In article <7o579h$c35$[EMAIL PROTECTED]>,
Greg <[EMAIL PROTECTED]> wrote:
> Don't take this wrong, but how many have heard of it?
Also there is no list of what algorithms it uses or how it makes the
private keys (PRNG). It's closed source so unless something changes I
would say it's snake oil.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: 3 Aug 1999 00:17:56 GMT
Greg <[EMAIL PROTECTED]> wrote:
[complaint about people "bash"ing each other]
Still, the original question of "has any cryptosystem been
based on an NP-complete problem?" is certainly of relevance to sci.crypt,
and indeed should be aired. Especially since it seems to be a particularly
slippery area of cryptography, because just because the underlying problem
is NP-complete does not mean that breaking a cryptosystem based on it will
be.
For knapsack cryptosystems, the underlying problem is certainly NP-hard.
Unfortunately, many (most?) knapsack cryptosystems are "break"-able in a
very practical sense. By this I mean attacks exist which recover encrypted
messages in reasonable time for the security parameters which might be
used in practice.
Bob Silverman mentioned the Chor-Rivest knapsack system;
a paper detailing its analysis appeared in CRYPTO '98 and is
available at :
http://www.dmi.ens.fr/~vaudenay/pub.html#Vau98h
The paper catalogs several past approaches to attacking the system and
then details an attack of its own. As far as I can tell, the attack is not
fully general in the sense that it requires a parameter "h" (where
computations take place in GF(p^h), p prime ) to have a factor greater
than or equal to sqrt(h + 1/4) + 1/2. Even so, the author shows how the
new attack can recover messages under parameters which were seriously
suggested in practice.
Also of interest might be the "previous work" and bibliography sections,
which have references to previous knapsack systems and their analysis.
There's also an article on "The Rise and Fall of Knapsack Cryptosystems"
which I don't have with me now, but which may be worth seeking.
Anyway, the knapsack systems have been held up as an example of why
"average-case complexity" is important. Knapsacks are NP-hard to solve in
the worst case, but this does not translate into being NP-hard to solve
for most or even many instances. Especially not the instances created by
producing a public/private key pair for a cryptosystem, since they may
require special structure.
(I think this also explains why Anton Stiglic was able to come up with
references on how knapsack crypto is "easy", even if the knapsack problem
in general is hard.)
So if we could find a problem which was NP-hard on average, for *almost
all instances*, then we could safely use it for crypto, right? Maybe.
As I understand it, this is the motivation behind the recent Ajtai-Dwork
cryptosystem (also mentioned by Bob Silverman). Ajtai found a class of
lattices which is NP-hard on average in some technical sense with respect
to the problem of finding short independent vectors. Then he and Dwork
proposed a public key system based on this problem.
The Ajtai-Dwork system is detailed at
ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1996/TR96-065/index.html#R01
Unfortunately, there's a practical attack (as in, it was implemented and
it works) on the system which also appeared at CRYPTO '98.
Analysis of Ajtai-Dwork :
ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1998/TR98-010/index.html#R01
I haven't made my way through all of this paper yet, only enough to notice
that they claim their results make the answer "Is breaking Ajtai-Dwork
NP-hard?" likely to be "NO", even though the underlying problem may be
NP-hard on average. Rather than relying on the previous sentence, looking
at the paper is encouraged, especially for settling theoretical questions.
I also just found a summary of recent results on lattices at
ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1999/TR99-006/index.html
by Jin-Yi Cai. It covers the Ajtai-Dwork system along with background on
lattice approximation problems, so will probably be a good thing to read.
It also mentions a new lattice-based cryptosystem which is "to appear".
Finally, there's another lattice cryptosystem, at
ftp://theory.lcs.mit.edu/pub/people/oded/pkcs.ps
which will be analysed at CRYPTO '99. At least, a paper claiming to
analyse it is on the list of accepted papers.
Those are the only two approaches I know anything about. I know
I've probably overlooked something promising...
Thanks,
-David Molnar
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Intel 810 chipset security
Date: Mon, 02 Aug 1999 21:07:18 -0400
lol, most of that does not apply to me anyway. I am running UNIX on my home
PC.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: With all the talk about random...
Date: Mon, 2 Aug 1999 21:04:14 -0400
Robert C. Paulsen, Jr. wrote in message <[EMAIL PROTECTED]>...
>[EMAIL PROTECTED] wrote:
>>
[... etc. ...]
>(page 146 in my 1992 paperback edition from MIT Press.)
>
>>
>> I am no phyisic person so if some of my facts are off please note. But
>> the idea still remains. Nothing is truly random.
>>
>
>Yes it is.
If you really mean "Yes, there is", please try my this little serious
joke:
YOU ARE BOTH RIGHT!
BTW, Mr R. F. is, in my opinion, right in his EXACT sense.
--- (My Signature)
>
>--
>____________________________________________________________________
>Robert Paulsen http://paulsen.home.texas.net
>If my return address contains "ZAP." please remove it. Sorry for the
>inconvenience but the unsolicited email is getting out of control.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: With all the talk about random...
Date: Mon, 2 Aug 1999 21:13:16 -0400
Jim Felling wrote in message <[EMAIL PROTECTED]>...
>
[... etc. ...]
>
>Even things bound by a set of rules, can still exhibit random behavior.
>Just because a system is constrained, does not mean that within that
>constraint it is random.(bad example: a six sided die will generate numbers
>1-6, just because it will never roll a 10 or a 14, does not reduce its
>randomness within the range it generates)
>
This metaphor is, IMO, not exact or perfect, but somewhat closer.
--- (My Signature)
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: [Q] Why is pub key cert. secure & free from spoofing?
Date: Tue, 03 Aug 1999 02:07:41 GMT
Jerome Mrozak <[EMAIL PROTECTED]> wrote:
> I'm a rank newbie, passing thru security issues for the 1st time.
I've
> been exposed to the public key method, and an explanation showing
> host-spoofing:
>
> A --> Spy --> B,
>
> where B believes the public key it received is from A when it is
really
> from Spy.
>
> My text claims that use of a public key certificate authority (CA)
will
> keep the spy at bay. My question is: if the Spy can insert itself
> between A & B, why not between A & CA, or B & CA?
The "policy statement" of a CA is devoted primarily to
answering the A & CA question. The B & CA problem is
often moved upstream by using a higher level CA. At
the top, we use "well known" public keys. When you get
a copy of Netscape or Lotus notes, it includes some
top-level CA public keys. If you think the distribution
may have been altered, you can take steps on several
levels to check.
--Bryan
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (O. Y. Realmink)
Crossposted-To: alt.comp.lang.learn.c-c++,comp.lang.c++,microsoft.public.vc.language
Subject: Re: How to write REALLY PORTABLE code dealing with bits (Was: How Big is a
Byte?)
Date: Tue, 03 Aug 1999 02:13:33 GMT
Martin Ambuhl <[EMAIL PROTECTED]> wrote:
>Next time you get involved in a thread, stay awake. There have been
>numerous uses of "octet" in this thread.
Yeah right, and I have a Pentium with 64 megaoctets of ram and a 7
gigaoctet hard drive. Give me a break, huh?
--
"O. Y. Realmink" better known as [EMAIL PROTECTED]
0 1 23456789 <- Use this key to decode my email address.
Fun & Free - http://www.5X5poker.com/
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Virtual Matrix Encryption
Date: 3 Aug 1999 02:25:31 GMT
Patrick Juola <[EMAIL PROTECTED]> wrote:
> In article <7ns555$ajj$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>>Just out of curiosity, which algorithms in PGP haven't been proven
>>secure?
> All of them.
> -kitten
Oh foo. Beat me to it.
At least until we see PGP based on info-theoretic security. Which reminds
me, what else is there in the way of info-theoretic primitives besides the
one-time pad and "Privacy Amplification" ?
-David Molnar
------------------------------
From: Teh Yong Wei <[EMAIL PROTECTED]>
Subject: Prime number.
Date: Tue, 03 Aug 1999 10:15:52 +0800
I have writing a simulation of elliptic curve cryptography. Can anybody
tell me that what is the best algorithm to generate random prime number
and why? Then, what is the most efficient way to prove that it is really
a prime number?
Thank you.
------------------------------
Date: Mon, 02 Aug 1999 15:51:28 -0400
From: "Trevor L. Jackson; III" <[EMAIL PROTECTED]>
Subject: Re: the defintion of Entropy
[EMAIL PROTECTED] wrote:
> In article <[EMAIL PROTECTED]>,
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> > [EMAIL PROTECTED] wrote:
> > > If the period of the output is infinit then it's truly random and
> the
> > > entropy in bits is inifite as well. Simple as that.
> >
> > Nope. Consider 0101101110111101111101111110...
> > This has "infinite period" but is very far from random.
> >
>
> Then you are going to say the entropy of a 63-bit LFSR is 2^63 - 1 bits
> and I will say you are wrong. Your sequence can be represented with a
> few bits. A truly random source is independant and infinite in
> length.
No. "True Randomness" (soon to be a sequel to "True Lies") does not
require infinite length. A single bit can be "truly random". The
following bits from the same source do not influence the quality of
randomness of the first bit.
> Maybe I forgot to mention that... oh well.
>
> Tom
> --
> PGP key is at:
> 'http://mypage.goplay.com/tomstdenis/key.pgp'.
> Free PRNG C++ lib:
> 'http://mypage.goplay.com/tomstdenis/prng.html'.
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: How to keep crypto DLLs Secure?
Date: Tue, 03 Aug 1999 03:16:15 GMT
[EMAIL PROTECTED] wrote:
> Basically any software can be infected by worms or viruses.
You assume several things, including:
(1) The network uses insecure protocols.
(2) The OS uses insecure mechanisms.
While those are true of Windows on old-IP,
they would be much less so for something
like Plan 9 on IL (a cryptographically
authenticated protocol).
Some day it will be "obvious" to everyone how
stupid we were to place so much reliance on
such shitty systems and protocols.
------------------------------
From: "daniao" <[EMAIL PROTECTED]>
Crossposted-To:
sci.engr.joining.welding,sci.engr.lighting,sci.engr.manufacturing,sci.engr.marine.hydrodynamics,sci.engr.mech,sci.engr.metallurgy,sci.engr.micromachining,sci.engr.mining,sci.engr.safety,sci.engr.semiconductors,sci.engr.surveying,sci.
Subject: curing stutter by tradifional chinese medicine
Date: 3 Aug 1999 02:45:40 GMT
stutter is a kind of disease which brings a lot suffering.
Some stutterer can't afferd the suffering and commitfed
suicide.So far,there is no effective teratment to cure the
diseasein the world.
Some experts regard the disease as psychosis.But the
treatment of psychotherapy has no effect This makes the
stuttere lose their confidence.
In order to cure this disease,the medical workers all over
the world manage to find an effective tveatment.But it is
very difficult.
There is a stutterer in Dalian,china,who found an effective
treatment and resfored to normal enfively.
After ten years' studying and practising.I found that
stutter can be cured by traditional clinese medicine
science.The patients can vetrieve their abicify of speaking.
This has been evideut by the clinical experience.
Affer I found the disease cause and the effective treatment
in 1995,the study couldn't get further improvement because
there is no news releasing ways and enough moneg.Now.I give
the information tlwough Internet.I hope for your help to make
my study bring benefit to mankind.
I'm willing to prove that stutter can be cured with the
medical workers all over the world.
~{VPR)9%?K?Z3T2!~}
~{?Z3T2!JGJ9HK7G3#M4?`5D2!#,2"GRD\8x?Z3T2!HKTl3I<+4s5DImPDIK:&#,~}
~{SP5D?Z3T2!HKRr2;?0HLJ\?Z3T2!6xSPGaIz5D!#5+JG6TSZ?Z3T2!5DVNAFD?G0~}
~{H+J@=gH4C;SPR;VV0l7(#,D\H7J5SPP'!#~}
~{J@=gIOR;P)9z<R5D?Z3T2!QP>?HKT1TxHON*?Z3T2!JGPD@m[50-#,5+>-9}~}
~{R;6NJ1<dPD@mAF7(;r=ZED7(VNAF:s#,5+2;<{P'9{;rU_6<SP7484#,J9?Z3T2!~}
~{HKJ'H%VNAF5DPEPD!#~}
~{5+JG?Z3T2!H48x?Z3T2!HK4x@4<+4s5DIz;n[50-#,KyRTH+J@=g5DR=Q'9$~}
~{WwU_:M?Z3T2!HKR;V1FsM<UR5=R;VV0l7(?IRT8yVN?Z3T#,5+JGR;V1C;SP3I9&!#~}
~{TZVP9z5D4sA,SPR;N;?Z3T2!HK#,VUSZUR5=AKR;VV?IRT8yVN?Z3T#,2"GR~}
~{2;847"5D0l7(AK!#~}
~{1>HKTZ>-9}J.<8Dj5DQP>?:MJ5QiVUSZUR5=SCVPR)395WVN:C?Z3T#,J9?Z~}
~{3T2!HK4o5=U}3#HK5D=2;nD\A&#,UbR;5cTZAY42J5QiJ1R2H7J5<{5=AK:\:C5D~}
~{P'9{!#5+JG1>HKJGRT8vHKQP>?N*Vw#,KdH;WT~}95~{DjRT@4RQ>-3I9&5DQP>?3v?Z~}
~{3T5D2!2!Rr:MVPR)VN2!0l7(#,5+JGR;#,C;SPPBNE7"2<G~5@#,6~C;SPWJ=p<L~}
~{PxQP>?#,KyRTR;V14&SZM#6YW4L,!#OVTZ#,TZMxIO7"2<UbR;O{O"#,O#M{5C5=~}
~{MxIO5DEsSQ0oVz#,RT1c=+NR5DQP>?3I9{Tl8#SZHK@`!#~}
~{1>HKT8Rb:MJ@=g8w9z5DR=Q'9$SCU_R;M,@4V$Cw#,?Z3T2!JG?IRT8yVN5D!#~}
------------------------------
From: "Greg Keogh" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: (Game) 80-digits Factoring Challenge
Date: Tue, 3 Aug 1999 13:19:58 +1000
Hi Alwyn,
RE:
> I used to like Mathematica, but I have retired my large body of code
written for
> it, and stop using it. The reasons are:
> 1) They do not tell you what algorithms they use internally. I could
> occasionally get the answer by e-mail, but not always.
I'm not sure how much detail you want, but in the Mathematica Book 3.0 by
Wolfram there are some fascinating overviews of how they cruch out the
various results. Fascinating reading for an maths hobbyist like myself, but
probably not enough detail for a pro.
> 2) Version 2.2 crashes under Windows 95, and Wolfram refused to
provide a
> fix. They said to buy version 3.0. Even Microsoft does not compel you to
upgrade
> application software with OS versions. For years I kept a Windows 3.1
partition
> just to run Mathematica.
I rarely get 'crashes' in Student version 2.2.2, but I do get lots of
'Kernel out of memory' type errors, probably due to the 16-bit code
limitations I guess. I'd like to imagine that these sorts of errors are rare
in the latest versions.
I have a related complaint to what you've mentioned in item 2. I'd just love
to play with Mathematica 3.0 (and 4.0 is apparently out now!), but I'm
stopped dead by the PRICE!
I just looked up the latest pricing for V4.0 on the web site, and a single
licence of Mathematica 4.0 in Australia is about $1800. For that price I
could fly me and the missus to Fiji for a week of luxury holiday. Sheesh! No
wonder people pirate software.
Cheers,
Greg Keogh
Melbourne Australia
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Help please (WWI/WWII ciphers)
Date: Tue, 03 Aug 1999 03:24:28 GMT
Mike Blais wrote:
> We have a package (newsletter) that has a code hidden in it, and our
> only hint was that it was a code stolen from the Germans in the war
> (don't know which war). Unless the code is actually hidden in the
> text this is what we believe is the code:
> 223,172,926 paragraph 2 section (b)
> and a page later
> 89,254,167 section (b) paragraph (iii)
> So what I have is this 223 172 926 89 254 167 and the answer key
> is like this
> ---- ------- ---------- --- ----
Quite often, codes like this are "book codes", where the plain text
are words found in some large book (yours sounds like a legal code)
and the code text are the "coordinates" of the words, typically
page number and word-within-the-page (but in your case, possibly
starting the numbering at the indicated paragraph). Unless you
have a *lot* of code, your only hope is to find the book that was
used and guess a sensible coordinate scheme that yields good text.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: With all the talk about random...
Date: Tue, 03 Aug 1999 03:54:27 GMT
"Trevor L. Jackson; III" wrote:
> This claim amounts to assuming the universe is newtonian.
There are quantum phenomena, but you don't need to invoke them to
explain the randomness of dice rolling. They would appear to be
random even if the universe *were* Newtonian.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: the defintion of Entropy
Date: Tue, 03 Aug 1999 03:33:31 GMT
[EMAIL PROTECTED] wrote:
> The period of the output is infinite however (otherwise it's not
> truly random).
What makes you think that "period" is well-defined for more than
a negligible subset of infinitely long bit sequences?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: the defintion of Entropy
Date: Tue, 03 Aug 1999 03:29:27 GMT
[EMAIL PROTECTED] wrote:
> Then you are going to say the entropy of a 63-bit LFSR is 2^63 - 1
> bits and I will say you are wrong. Your sequence can be represented
> with a few bits. A truly random source is independant and infinite
> in length.
First, I would say no such thing!
Second, you're trying to reinvent Chaitin's algorithmic complexity
theory, poorly.
Third, we have a decent definition of "random variable" but *not*
of "random number", and there is a very good reason why.
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Cryptanalysis of R250
Date: 3 Aug 99 03:13:33 GMT
The Evil Anti-Rick ([EMAIL PROTECTED]) wrote:
: Does anyone have any cryptanalysis information on the R250 PRNG
: algorithm and/or cryptanalysis information of byte-wise XOR stream
: ciphers?
: An an exercise, I wrote a simple XOR stream-cipher using R250 as the
: RNG. That was the easy part. I looked through all my old textbooks for the
: equations needed to break such a cipher and came up empty-handed. I recall
: that it seemed pretty straight-forward, and it was presented as an acedemic
: exercise for first-year crypto students.
Since you wrote a program to carry out encryption with R250, you are
familiar with what that algorithm is. I am not familiar with the name, and
hence I could not tell you anything about cryptanalyzing it. Thus, it
would have been useful if you described R250 in your post, or at least
gave an indication as to what class of pseudorandom-number generator it
belongs to.
One common class of pseudo-random number generators is the
mixed-congruential PRNG, used for random-number functions in many
programming environments. For cryptographic purposes, linear-feedback
shift registers are more common.
Both of these PRNGs are linear; hence, if one has some known plaintext (or
a probable word) knowing part of the generated sequence allows determining
the rest of the sequence; there is information in the open literature
about this, and Bruce Schneier's book, Applied Cryptography, contains a
number of useful references.
John Savard
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: the defintion of Entropy
Date: Tue, 03 Aug 1999 03:31:13 GMT
"Tony T. Warnock" wrote:
> ... all k-bit combinations occur with the proper frequency.
I don't know what you mean by "proper frequency", but almost all
(in a measure-theoretic sense) k-bit combinations do not occur at
all in the sequence I gave the first several bits of.
------------------------------
** 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
******************************
