Cryptography-Digest Digest #283, Volume #9 Thu, 25 Mar 99 12:13:03 EST
Contents:
Re: Papers on Security and Cryptography (Mok-Kong Shen)
Re: DIE HARD and Crypto Grade RNGs. (Coen Visser)
Re: Live from the Second AES Conference (William hugh Murray)
Re: compare RSA and D-Hellman ([EMAIL PROTECTED])
Re: PKI on LINUX (Casey Sybrandy)
RSA Cryptography Today FAQ (1/1) ([EMAIL PROTECTED])
Re: Securid Card (William hugh Murray)
Re: compare RSA and D-Hellman (DJohn37050)
Re: Random Walk (R. Knauer)
Re: Hard problems? (Patrick Juola)
Communications and Multimedia Security '99 (CMS'99)
Re: GOOD PRIME GENERATOR (GPG) ([EMAIL PROTECTED])
Re: Crytpo Gurus - Please comment on this sceneario (Sundial Services)
Re: Hard problems? ([EMAIL PROTECTED])
Re: Random Walk (Patrick Juola)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.security,comp.security.misc
Subject: Re: Papers on Security and Cryptography
Date: Thu, 25 Mar 1999 12:47:40 +0100
Jim Press wrote:
>
> you'll find electronic copies of various papers I've had published at one
> time or another at:
> http://home.freeuk.net/jpress
I tried to access a few in the section cryptography, but none
was available.
M. K. Shen
=========================
http://www.stud.uni-muenchen.de/~mok-kong.shen/ Updated: 12 Mar 99
(Origin site of WEAK2-EX, WEAK3-EX and WEAK4-EX)
------------------------------
From: [EMAIL PROTECTED] (Coen Visser)
Subject: Re: DIE HARD and Crypto Grade RNGs.
Date: 18 Mar 1999 15:59:01 GMT
[EMAIL PROTECTED] (Patrick Juola) writes:
>Secondly, we *can* measure Kolmogorov complexity to arbitrary degrees
>of precision for some types of strings.
Could you explain this. I thought that the Kolmogorov complexity
was semi-computable, you can approximate it only from above. So you
will never know how close you are. This is something different than
"measuring to an arbitrary degree".
Regards,
Coen Visser
------------------------------
From: William hugh Murray <[EMAIL PROTECTED]>
Subject: Re: Live from the Second AES Conference
Date: Thu, 25 Mar 1999 13:15:16 GMT
This is a multi-part message in MIME format.
==============4173CEEBCCBEC601D61C0D35
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
DJohn37050 wrote:
>
> Yes, I mention AB encryption (or even more) as Super AES in my paper as a
> possibility for the paranoid that want to spend the MIPS.
> Don Johnson
Of course, the value of super-encryption, even 3DES, assumes that
encryption is the weak link in one's security. Since that is almost
never the case, why bother? I ask this as a serious question. It seems
to me that the entire AES effort spends incredible amounts of treasure
on the easy part of the security problem.
What am I missing?
==============4173CEEBCCBEC601D61C0D35
Content-Type: text/x-vcard; charset=us-ascii;
name="whmurray.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for William hugh Murray
Content-Disposition: attachment;
filename="whmurray.vcf"
begin:vcard
n:Murray;William Hugh
tel;fax:800-690-7952
tel;home:203-966-4769
tel;work:203-966-4769
x-mozilla-html:FALSE
adr:;;;;;;
version:2.1
email;internet:[EMAIL PROTECTED]
fn:William Hugh Murray
end:vcard
==============4173CEEBCCBEC601D61C0D35==
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: compare RSA and D-Hellman
Date: Thu, 25 Mar 1999 11:48:21 GMT
so let me see if I understand:
A -> large prime number
x,y -> large private numbers (not prime)
g -> small random number?
Is that right? Can 'a' be static?
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Casey Sybrandy <[EMAIL PROTECTED]>
Subject: Re: PKI on LINUX
Date: Thu, 25 Mar 1999 07:15:48 -0500
==============CF45B0085DB6E59A3FF7A614
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Try this link, there's some stuff on it, though I don't know if it has what your
looking for.
Replay Associates > Red Hat Crypto
Greylord
[EMAIL PROTECTED] wrote:
> Hi everybody,
>
> I would like to know whether there is Public Key Infrastructure related
> toolkit available for LINUX like the Microsoft Crypto API available on
> Windows platforms. I would also like to know whether they are available
> whether they are available for free.
>
> I looked up the sites www.kernel.org and www.linux.org, but they do not have
> any information on this.
>
> Any help on this would be appreciated.
>
> Regards
>
> Shantanu
>
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
==============CF45B0085DB6E59A3FF7A614
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
Try this link, there's some stuff on it, though I don't know if it has
what your looking for.
<br> <a href="http://replay.com/redhat/">Replay Associates > Red Hat
Crypto</a>
<p>Greylord
<p>[EMAIL PROTECTED] wrote:
<blockquote TYPE=CITE>Hi everybody,
<p>I would like to know whether there is Public Key Infrastructure related
<br>toolkit available for LINUX like the Microsoft Crypto API available
on
<br>Windows platforms. I would also like to know whether they are available
<br>whether they are available for free.
<p>I looked up the sites www.kernel.org and www.linux.org, but they do
not have
<br>any information on this.
<p>Any help on this would be appreciated.
<p>Regards
<p>Shantanu
<p>-----------== Posted via Deja News, The Discussion Network ==----------
<br><a
href="http://www.dejanews.com/">http://www.dejanews.com/</a>
Search, Read, Discuss, or Start Your Own</blockquote>
</html>
==============CF45B0085DB6E59A3FF7A614==
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To:
talk.politics.crypto,alt.security.ripem,sci.answers,talk.answers,alt.answers,news.answers
Subject: RSA Cryptography Today FAQ (1/1)
Date: 25 Mar 1999 14:03:06 GMT
Reply-To: [EMAIL PROTECTED]
Archive-name: cryptography-faq/rsa/part1
Last-modified: 1997/05/21
An old version of the RSA Labs' publication "Answers to Frequently Asked
Questions about Today's Cryptography" used to be posted here until May
1997. These postings were not sponsored or updated by RSA Labs, and
for some time we were unable to stop them. While we hope the information
in our FAQ is useful, the version that was being posted here was quite
outdated. The latest version of the FAQ is more complete and up-to-date.
Unfortunately, our FAQ is no longer available in ASCII due to its
mathematical content. Please visit our website at
http://www.rsa.com/rsalabs/ to view the new version of the FAQ with your
browser or download it in the Adobe Acrobat (.pdf) format.
RSA Labs FAQ Editor
[EMAIL PROTECTED]
------------------------------
From: William hugh Murray <[EMAIL PROTECTED]>
Subject: Re: Securid Card
Date: Thu, 25 Mar 1999 13:19:35 GMT
This is a multi-part message in MIME format.
==============5485A29FDE62AC7FB2A04B43
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Steve Matthews wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Hi,
> Thanks for your informative posting.
> Am I correct in assuming SDI als now produce a 'soft' version of the
> token card (softID?) which
> can reside on Client machines.. if so how does this differ (if at all
> )from the token card implementation.
Among other differences, it has code in it to resist arbitrary copying.
>
> The company I work for included SDI/Ace Server support within our PPP
> RAS product.. (as a NAS talking to the Server)
> It seems to work well although the take up in the UK market sector has
> seemed to be a little slow from my (possibly) limited experience. I
> have only come across one or two large (v. security conscious)
> multinationals who actually use it.
>
> r's
> Steve
>
> - --
> _________________________________________
> PGP Key ID: 0x95E1EB05
>
> 'Flair is a term used by those that have never ridden'
> -Miguel Indurain
> _________________________________________
>
> -----BEGIN PGP SIGNATURE-----
> Version: PGPfreeware 6.0.2i
>
> iQA/AwUBNvlpqqVIZcSV4esFEQJXtACfSSGO+iXrnRHy6qHdJg9c3WKbeKYAn32m
> HSgwcw0qfZZwBDe1iKuXdVCq
> =kt/2
> -----END PGP SIGNATURE-----
==============5485A29FDE62AC7FB2A04B43
Content-Type: text/x-vcard; charset=us-ascii;
name="whmurray.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for William hugh Murray
Content-Disposition: attachment;
filename="whmurray.vcf"
begin:vcard
n:Murray;William Hugh
tel;fax:800-690-7952
tel;home:203-966-4769
tel;work:203-966-4769
x-mozilla-html:FALSE
adr:;;;;;;
version:2.1
email;internet:[EMAIL PROTECTED]
fn:William Hugh Murray
end:vcard
==============5485A29FDE62AC7FB2A04B43==
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: compare RSA and D-Hellman
Date: 25 Mar 1999 14:05:01 GMT
ANSI X9.42 or IEEE P1363 discuss DH and also security considerations for same.
X9.42 is a draft available by attending an ANSI X9F1 meeting. IEEE P1363 is
available on the web. Just search on "IEEE P1363". There are many
considerations. The field order p should be generated by a canonically random
process to thwart an attack by Dan Gordon, for example.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Thu, 25 Mar 1999 14:24:49 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 25 Mar 1999 06:13:19 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>Experts who have successfully applied to such matters as
>cracking high-grade cryptosystems the very tests you claim
>are worthless have tried repeatedly to tell you how things
>actually work.
I have never claimed that statistical methods are not useful for many
applications. I have claimed is that statistical tests cannot be used
to characterize a process that generates finite sequences as truly
random or not truly random.
BTW, it is interesting to note that many of those cryptosystems you
refer to above were believed to be truly random by their inventors,
based on statistical tests. Otherwise that would not have used them.
>But you prefer to draw untenable conclusions
>about a field you do not work in by attributing your own
>misinterpetations to the authors of books you have just read.
I am not drawing any untenable conclusions. I am merely repeating what
I have read. And I have not misinterpreted anything either. I have
posted most of the material here on sci.crypt for all to see. I will
repost some of it below, and you can go thru it item for item and pick
it apart if you want.
>You claimed you were standing on the shoulders of giants,
>but actually you're tripping over their feet.
You should never flatter your self a comedian. That was really not
funny at all.
>I don't hope to persuade R. Knauer, but I do hope others
>have been sufficiently warned that they will investigate
>further before acting on the basis of his notions.
I don't care whether you persuade me or not, and neither does anyone
else here. This isn't a debate club, but a discussion forum. Let
people continue to wallow in their ignorance for all I care. Without
stupid people, there can be no smart people.
I have presented the comments of acknowledged experts (and I repeat
some of them here again), so people can judge for themselves. The
books that I have cited are available in any major library or can be
obtained from interlibrary loan, just like I got them. There is no
excuse for anyone who is really interested in learning the truth about
randomness not to gain access to that truth.
Here are some of the comments I have posted before:
+++++
"Explorations In Quantum Computing" by Colin Williams and Scott
Clearwater", chapter 7 entitled "True Randomness":
[emphasis theirs]
"Today our best description of Nature is in terms of quantum physics.
Quantum physics, as we currently understand it, relies heavily on the
concept of randomness."
"... a classical computer can only *pretend* to generate a random
number whereas a quantum computer can *actually* generate a random
number."
"... there is no such thing as *a* random number. It only makes sense
to talk about processes for generating sequences of random numbers."
"... we are faced with the question of whether a particular sequence
of numbers has the *appearance* of being random. Fortunately, there
are statistical tests that can answer this question."
"The art in creating computer programs that simulate the generation of
true random numbers is to devise algorithmic methods that generate
sequences of numbers that pass both the distribution test and
correlation checks."
"As we show, even when random number generators pass such statistical
tests, the sequence of numbers it generates may still not be random
enough to serve as an approximation to a true random process."
==========
William Feller, "An Introduction To Probability Theory and Its
Applications", 3rd ed.
>From p. 67:
"We shall encounter theoretical conclusions which not only are
unexpected but actually come as a shock to intuition and common sense.
They will reveal that commonly accepted notions concerning chance
fluctuations are without foundation and that the implications of the
law of large numbers are widely misconstrued. For example, in various
applications it is assumed that observations on an individual
coin-tossing game during a long time interval will yield the same
statistical characteristics as the observation of the results of a
huge number of independent games at one given instant. This is not so.
Indeed, using a currently popular jargon we reach the conclusion that
in a population of normal coins the majority is necessarily
maladjusted."
>From p. 71:
"Refined models [of coin-tossing and its relation to stochastic
processes] take into account that the changes and their probabilities
vary from trial to trial, but even the simple coin-tossing model
leads to surprising, indeed shocking, results. They are of practical
importance because they show that, contrary to accepted views, the
laws governing a prolonged series of individual observations will show
patterns and averages far removed from those derived for a whole
population. In other words, currently popular psychological tests
would lead one to say that in a population of "normal" coins most
individual coins are "maladjusted".
+++++
The conclusion one can reach from those statements is inescapable -
statistical tests cannot be used to characterize processes that
generate finite sequences as either truly random or not truly random.
The best you can hope for is that statistical tests will uncover a
property called "pseudorandomness" - the *appearance* of randomness -
which is not the same as true randomness. No conclusions can be drawn
from the property of pseudorandomness regarding the actual true
randomness or non-true-randomness of a process. At best it serves as a
diagnostic guide to alert you to possible problems with the generation
process. I cannot be used to claim that the process is correct or not
in terms of finite true random number generation.
Bob Knauer
"The important thing is to stop lying to yourself. A man who lies
to himself, and believes his own lies, becomes unable to recognize
the truth, and he ends up losing respect for himself as well as for
others. When he has no respect for anyone, he yields to his impulses,
indulges in the lowest forms of pleasure, and behaves in the end like
an animal, in satisfying his vices."
--Dostoevsky (The Brothers Karamazov)
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Hard problems?
Date: 25 Mar 1999 08:52:08 -0500
In article <7dcovm$pvo$[EMAIL PROTECTED]>,
Doggmatic <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
>> > I've seen NP-complete problems, but what's an analogy which describes
>PSPACE,
>> > PSPACE-complete, or EXPTIME problems? Assume I know little to nothing about
>> > number theory, information theory or complexity theory, other than those
>> > terms.
>>
>> The generic PSPACE-complete problem is satisfyability of quantified boolean
>> formulae.
>
>This one sounds interesting ... what is it? I thought the boolean
>satisfyability problem was NP-complete.
The difference is in the quantification.
For example,
x != y is satisfiable, and an instance of boolean SAT.
For all x : For all y : x != y is not, and an instance of QBF.
You can see that this is solvable in polynomial space (just cycle
through all possible variable assignments); it will also "obviously"
take exponential time if you use the naive algorithm. It's also
rather obviously NP-hard -- just put an existential qualifier
in front of an unquantified formula.
However, it doesn't look to be NP-complete because there's no way
to confirm a statement that you've guessed to be true short of the
exponential confirmation.
-kitten
------------------------------
From: CMS'99 <[EMAIL PROTECTED]>
Subject: Communications and Multimedia Security '99
Date: Thu, 25 Mar 1999 15:35:09 +0100
NEW DEADLINE FOR THE CMS'99 CONFERENCE:
April 2nd, 1999
The call for papers can be found at
http://www.esat.kuleuven.ac.be/cosic/cms99/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: GOOD PRIME GENERATOR (GPG)
Date: Thu, 25 Mar 1999 15:14:57 GMT
In article <7dda0p$8fv$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Note: I posted this at sci.math yesterday. Today I found out that someone
> named 'torres' has discovered this algorithm before me, last year --
No. Torres discovered nothing. His exposition was gibberish and much of
what he 'invented' did not find primes at all.
Sieve algorithms are over 2000 years old. They are hardly new.
Why don't people READ THE LITERATURE?
Two minutes with any decent book on primes (e.g. Ribenboim's) would
let you know that sieve methods are not new.
You method calls for calculating the product of all primes up to some bound.
This product will be quite large. In fact, it will not be polynomially
bounded. Sieve algorithms are polynomially bounded. Your method will be
hopeless slow compared to them.
> actually, I suspect none of us came first then. I didn't know, so I had named
> the algorithm independently.
Did you bother to check?
It seems that people today have forgotten how to use a library. Or a Web
search engine.
The very first thing one should do before trying to invent a new computer
algorithm is to SEE WHAT HAS ALREADY BEEN DONE.
> Below my prime generator. Actually it's a prime candidate generator. It
> generates PHI(G) candidates btw. 0 and G-1 in practically linear time,
> if G = product of first n primes. There can't be any other candidates in
> the interval examined.
Note that G ~ e^n and Phi(G) ~ e^(-gamma) * e^n
>
> Before ditching my algorithm completely, please take the time to try it
> out. For instance, find all twin primes up to 2310 using only pen and
> paper. It works quite well; you find 135 candidates in no time, and then
> you have to check those manually, for instance using a table of primes
> (yes, you have to cheat).
In other words, your algorithm only tosses out some of the composites
and then one must test the remaining elements for primality.
This isn't terribly useful. Especially since Pritchard's variation of the
Sieve of Eratosthenes finds all the primes and nothing but the primes up to
n (for given n) in sub-linear time (in n).
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
Date: Thu, 25 Mar 1999 08:13:02 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Crytpo Gurus - Please comment on this sceneario
sb5309 wrote:
>
> I write this so as to learn something from your responses; if it is old
> story, please don't flame me; I am a novice.
> (I sent this two days earlier, but I did not see it in the group; so I
> try again)
>
> Consider this scenario :
>
> Two persons are engaged to type, using computer keyboards, to produce a
> series of numbers from 0 to 255. They are told that they should make
> them random. These two series are later joined together to form a long
> series.
>
> My comment
> ----------
> I don't really think that these two series will be random. Chance is
> each series has its own bias, ie. biasness in one series is different
> from the other.
>
> Can this be used in OTP ? My initial feeling is YES. As described by
> David Kahn in "Codebreakers" (I quote this from the book "Decrypted
> Secrets - Methods & Maxim in Cryptography" by F. L. Bauer), that the
> Baudot code prepared by typists in WWII contained biases. For example, a
> typist would typically place its left-hand small finger at 1 and the
> thumb at 5, and the right-hand small finger at 6 and the thumb at 0. The
> numbers so produced indicate that the digits from 1 to 5 would normally
> form a number; so was 6 to 0. In other words, numbers like 10293, 28375
> which required typing with fingers from each hand were not often
> created. Numbers with triple and more similar digits were very rare.
> Yet, as noted by David Kahn, the numbers did not have enough pattern for
> crypto-attack.
[ My right-hand is going to get very tired in that position ... ]
I am certainly no "crypto guru," but I do suspect that "unpredictable"
does not mean "random." I may type at a keyboard and the numbers I'd
produce would be unpredictable but because of biases like the ones
described they would not be random.
A popcorn-machine like is used in lotteries is probably random, as long
as the balls are precisely the same. Natural phenomenon like cosmic
rays are random. Anything produced by a computer algorithm is not.
Dice-rolls are close, if a machine (not your hand) is used to bobble and
release the dice.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Hard problems?
Date: Thu, 25 Mar 1999 15:27:18 GMT
In article <7dcp4b$q8l$[EMAIL PROTECTED]>,
Doggmatic <[EMAIL PROTECTED]> wrote:
> In article <7cofoi$gl3$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
stuff deleted...
> > > Hmmm ... my original question is poorly worded. I'm looking for an actual
> > > example of a problem of one of those types.
> >
> > The equivalence problem for semi-extended regular expressions requires
> > both exponential time and space.
> >
> > See:
> >
> > Aho, Hopcroft & Ullman
> > The Design and Analysis of Computer Algorithms
> > Chapters 10,11,12
>
> The book doesn't exist online anywhere, and it appears to be kinda old.
It is superb. I highly recommend it.
>but is there anyone willing to explain the
> "problem for semi-extended regular expressions?"
I assume you know what a regular expression is.
If R1 and R2 are regular expressions (defined over some language),
then an extended regular expression consists of the set (R1+R2) (R1*R2),
(R1^*) and (R2^*). If complementation is not allowed, then we have a
semi-extension.
The problem asks: Given two different semi-extended expression defined over
some language, do they represent the same set?
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Random Walk
Date: 25 Mar 1999 10:09:28 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On Thu, 25 Mar 1999 06:13:19 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
>wrote:
>
>>Experts who have successfully applied to such matters as
>>cracking high-grade cryptosystems the very tests you claim
>>are worthless have tried repeatedly to tell you how things
>>actually work.
>
>I have never claimed that statistical methods are not useful for many
>applications. I have claimed is that statistical tests cannot be used
>to characterize a process that generates finite sequences as truly
>random or not truly random.
>
>BTW, it is interesting to note that many of those cryptosystems you
>refer to above were believed to be truly random by their inventors,
>based on statistical tests. Otherwise that would not have used them.
I suspect that you are incorrect in this assertion; any key-based
cypher where the key material is smaller than the plaintext to
be protected is rather obviously not "truly random" in the sense
needed by the OTP proofs. This doesn't mean that a cryptographer
won't use a key-based system; the number of key-based block and
stream cyphers out there, designed by those self-same professionals,
indicates otherwise.
You're making a vast oversimplification of the entire field -- to
wit, either something is provable beyond a doubt. If this is
the world-view you use, then, yes, any cryptographic method that
isn't an OTP is ``worthless'' and there's no way to confirm that
a given OTP or OTP generation system is actually secure. On the
other hand, a cypher for which attacks are known *MAY* be secure
enough by virtue of the work factor.
It's a gamble. If you're completely risk-averse, then you won't
accept *any* degree of uncertainty. But this approach verges
on the pathological; in practice, I can evaluate the risk of a
new and heretofore unknown attack to be sufficiently small
that I accept it. Hey, I occasionally cross streets against the
light, too. Hasn't hurt me yet.
-kitten
------------------------------
** 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
******************************
