Cryptography-Digest Digest #511, Volume #11 Fri, 7 Apr 00 21:13:01 EDT
Contents:
Making keys out of passwords??? ([EMAIL PROTECTED])
Re: Public|Private key cryptography? ("Trevor L. Jackson, III")
Re: Q: Petri nets (Darren New)
Re: GSM A5/1 Encryption (Paul Schlyter)
Re: Building a stream cipher? (newbie Question) ("Simon Johnson")
Re: Making keys out of passwords??? (Gordon Warren)
Building a stream cipher part 2. (Newbie question.) ("Simon Johnson")
Re: RC4 statistics (Qbarf)
Re: Public|Private key cryptography? (lordcow77)
Re: Is AES necessary? (Bruce Schneier)
(no subject) (john)
Re: GSM A5/1 Encryption ([EMAIL PROTECTED])
Test Vectors for Block Ciphers ([EMAIL PROTECTED])
Test Vectors for Block Ciphers ([EMAIL PROTECTED])
Re: Test Vectors for Block Ciphers (Paul Rubin)
Re: Public|Private key cryptography? (Jerry Coffin)
Re: Q: Petri nets ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Making keys out of passwords???
Date: Fri, 07 Apr 2000 22:00:08 GMT
I'm wanting to use either twofish or blowfish,
but I'm having trouble figuring out how to
convert an ascii password into a 128-bit key.
Can anyone give me some info on this?
I've heard that for DES a hash function was used
to do this, but I'm not sure I trust such a
function that I'd come up with (probably have
several passwords that would map to the same 128-
bit value). Does twofish have a standard
hashfunction or is there something built in to
use a password?
Thanks!
Jonathan Dinerstein
[EMAIL PROTECTED]
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Fri, 07 Apr 2000 18:24:34 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Public|Private key cryptography?
lordcow77 wrote:
> In article <[EMAIL PROTECTED]>, Tom St Denis
> <[EMAIL PROTECTED]> wrote:
> >And unless we make some 'quantum' leap [excuse the pun] in
> either they
> >will not be solvable. I cannot forsee in the near future [20
> years] any
> >computer with more then say a couple gigs of high speed ram.
>
> ASCI Red (Intel)? ASCI Blue Mountain(SGI)? ASCI Blue Pacific
> (IBM)? I know that each of these machines has multiple terabytes
> of memory. I believe that ASCI White (awarded to IBM) is
> scheduled for completion around summer or fall of this year and
> should have even more memory. Then we have the T3E installations
> throughout the world, with a potential memory capacity also in
> the terabyte range and memory I/O bandwidths sustainable in the
> hundreds of gigabytes range. By 2010, I would not be surprised
> to see ASCI machines with tens or even hundreds of terabytes of
> memory (and operating in the tens and hundreds teraflops range).
> Still not enough to factor a 1024-bit composite, but I wouldn't
> discount progress as much as you do.
Desktop machines won't be that far behind. In 1982 I bought a 5 Mhz machine
with 64K and a 5M disk.
In 1992 I bought a 50 Mhz machine with 64M and 5G disk.
In 1999 (early) I bought a 500 Mhz machine with 1G memory and 125G disk.
In ~2010 I expect to buy a 5+Ghz machine with 64G memory and ~100T disk.
In ~2020 I expect to be able to fit the entire Library of Congress (about 20T)
in "main memory", what ever main memory is then.
Of course by then netnews will be routinely delivering that much data to the
desktop every day. ;-)
On second though... :-( ... considering the expected dilution of content. Will
there be homeopathy applied to information?
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Q: Petri nets
Date: Fri, 07 Apr 2000 22:26:32 GMT
Mok-Kong Shen wrote:
> In computer science, a theory that has certain practical
> applications bears the name 'Petri nets'. Are these automata?
Yes.
There are one or more tokens in the machine at any time. There are two
kinds of nodes, which I'll call circles and gates, because I don't remember
the real names. ;-) A transition consists of finding a "gate" node with one
or more inputs from circles, and with at least one token in each circle that
feeds the gate, removing one token from each circle feeding the gate and
adding one to each circle that the gate in turn feeds. There's no stopping
in the gate.
However, a petri net can be reduced to a normal FSM in a way similar to
reducing a nondeterministic FSM to a deterministic one, so while it's a
convenient way of specifying things, I don't think it's of particular
interest outside of places (like network protocol design) that actually uses
FSMs non-theoretically.
--
Darren New / Senior MTS / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
There is no safety in disarming only the fearful.
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: GSM A5/1 Encryption
Date: 7 Apr 2000 22:52:13 +0200
In article <8ckuij$j7l$[EMAIL PROTECTED]>,
David A. Wagner <[EMAIL PROTECTED]> wrote:
> In article <8ck7mo$cdf$[EMAIL PROTECTED]>,
> Paul Schlyter <[EMAIL PROTECTED]> wrote:
>
>> If/when digital scanners get readily available, I would guess that
>> the GSM operators counter this by letting the frequencies hop more
>> often.
>
> I'm told the hopping sequence can be computed (by an eavesdropper) from
> publicly known information. If that is correct, hopping more frequently
> is unlikely to help too much.
>
>> Yes, this can probably be done -- by a knowledgeable dedicated
>> individual who have enough resources. But it's certainly beyond
>> the capabilities of the average guy who buys a scanner at Radio Shack
>> -- even when digital scanners become available.
>
> Ahh, that's exactly the point I was trying to make, too.
> I see that we are in violent agreement. :-)
I guess we are... :-)
>> IMO the techniques of time multiplexing and frequency hopping is a
>> more efficient protection against eavesdropping than the A5 encryption.
>
> That's only because A5 is not very good. If they had used a decent
> encryption algorithm (and there are plenty available), the story would
> be different.
Very true -- but as it is now, they might almost as well refrain from
encrypting the calls at all.
> The GSM industry had an opportunity to choose strong crypto over
> weak crypto, and IMHO, they chose wrong.
...and they try to cover this up by trying to keep these algorithms
secret....
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: Building a stream cipher? (newbie Question)
Date: Fri, 7 Apr 2000 22:43:55 -0700
Thanxs to all who replyed....
Douglas: i really should clean up my language shouldn't I. :)
I'll change my opening lines to:
How do you contruct a resonable stream cipher?
I wish to achieve this by producing a pesudo random stream of bytes, and
XORing it with the plain-text.
------------------------------
From: Gordon Warren <[EMAIL PROTECTED]>
Subject: Re: Making keys out of passwords???
Date: Fri, 07 Apr 2000 19:06:34 -0400
[EMAIL PROTECTED] wrote:
> I'm wanting to use either twofish or blowfish,
> but I'm having trouble figuring out how to
> convert an ascii password into a 128-bit key.
> Can anyone give me some info on this?
Use MD5 as a hash function and you'll get 128-bit output. Or use SHA1
(which'll give you 20 bytes) and take the first 16 bytes.
--
=============================================================
= Gordon Warren [EMAIL PROTECTED] =
= GPG Public key http://members.xoom.com/gwarren/gpg.pubkey =
= Home page http://members.xoom.com/gwarren/ =
=============================================================
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Building a stream cipher part 2. (Newbie question.)
Date: Fri, 7 Apr 2000 23:16:44 -0700
How's this for a stream cipher?
I have devised these steps looking at other algorithms, and thinking what
would be hard to find a pattern. (i hope i'm right)
Lets say i intialise an array, s(0 to 255), with the values of the array
equal to that of the arrays' index value e.g. s(i)=i
Then i perform the following calcualation on the text.
For i = 1 to len(key) {
a=sqr((ascii value of i'th letter of text)+a) mod 256
}
I then generate my stream of 'x' length using:
For i = 1 to x {
j=(j+a) mod 256 'i hope this co-dependency will mash things up a bit
a=sqr(j +s (a) + s(j)) mod 256
'from here onwards is 'stolen' from RC4.
swap s(j) & s(a) 'changes structure of the s-box.
output char = s((s(a) + s(j)) mod 256)
}
I suspect there are many faults in his algorithm. I'd be glad to here any
suggestions on how this could be improved.
------------------------------
From: Qbarf <[EMAIL PROTECTED]>
Subject: Re: RC4 statistics
Date: Fri, 07 Apr 2000 19:20:42 -0400
Just for fun I compiled the whole ARC4-10 state space and key mapping
(i.e. finding all the periodic state sequences or "strings", and seeing
how many keys are mapped to each one of them). You can then estimate
the probability of generating a very short periodic sequence, assuming
all keys are equally probable.
I need a *much* bigger computer for ARC4-256 though :)
N = 10 Nstate = 3.62880e+006
Nstrings = 49
State = 0 0 0 1 2 3 4 5 6 7 8 9 Cycle = 25743590
Keys = 716364546
State = 0 0 0 1 2 3 4 5 6 7 9 8 Cycle = 25743590
Keys = 715113740
State = 0 0 0 1 2 3 4 5 6 8 7 9 Cycle = 25743590
Keys = 717846240
State = 0 0 0 1 2 3 4 5 6 9 7 8 Cycle = 25743590
Keys = 717049017
State = 0 0 0 1 2 3 4 5 6 9 8 7 Cycle = 73727010
Keys = 2053184606
State = 0 0 0 1 2 3 4 5 7 6 8 9 Cycle = 25743590
Keys = 717292992
State = 0 0 0 1 2 3 4 5 7 6 9 8 Cycle = 25743590
Keys = 719062062
State = 0 0 0 1 2 3 4 5 8 9 6 7 Cycle = 7090280
Keys = 196256706
State = 0 0 0 1 2 3 4 5 9 7 6 8 Cycle = 25743590
Keys = 717666340
State = 0 0 0 1 2 3 4 6 5 7 9 8 Cycle = 5802990
Keys = 162644117
State = 0 0 0 1 2 3 4 6 7 8 9 5 Cycle = 25743590
Keys = 714980503
State = 0 0 0 1 2 3 4 6 8 5 7 9 Cycle = 25743590
Keys = 715509486
State = 0 0 0 1 2 3 4 6 8 9 5 7 Cycle = 25743590
Keys = 715944085
State = 0 0 0 1 2 3 4 7 8 6 9 5 Cycle = 5802990
Keys = 160113548
State = 0 0 0 1 2 3 4 8 7 5 9 6 Cycle = 7090280
Keys = 197655370
State = 0 0 0 1 2 3 4 8 7 6 9 5 Cycle = 266970
Keys = 7176007
State = 0 0 0 1 2 3 7 8 9 5 4 6 Cycle = 155590
Keys = 4210403
State = 0 0 0 1 2 3 9 5 4 8 6 7 Cycle = 26790
Keys = 733693
State = 0 0 0 1 2 3 9 5 8 4 6 7 Cycle = 116490
Keys = 3181724
State = 0 0 0 1 2 4 5 6 3 8 9 7 Cycle = 155590
Keys = 4276665
State = 0 0 0 1 2 4 5 6 7 9 3 8 Cycle = 155590
Keys = 4309208
State = 0 0 0 1 2 4 5 8 9 6 3 7 Cycle = 26790
Keys = 751434
State = 0 0 0 1 2 4 6 7 9 8 5 3 Cycle = 155590
Keys = 4186220
State = 0 0 0 1 2 4 6 8 3 7 9 5 Cycle = 155590
Keys = 4261383
State = 0 0 0 1 2 4 9 3 6 5 7 8 Cycle = 155590
Keys = 4313113
State = 0 0 0 1 2 5 3 7 8 6 9 4 Cycle = 160630
Keys = 4574174
State = 0 0 0 1 2 6 5 7 8 3 9 4 Cycle = 155590
Keys = 4339736
State = 0 0 0 1 2 6 7 3 9 4 8 5 Cycle = 155590
Keys = 4344699
State = 0 0 0 1 2 6 8 5 9 4 3 7 Cycle = 155590
Keys = 4323907
State = 0 0 0 1 3 2 4 7 6 8 5 9 Cycle = 155590
Keys = 4197872
State = 0 0 0 1 3 5 4 2 7 8 9 6 Cycle = 26790
Keys = 775155
State = 0 0 0 1 3 5 6 7 4 2 8 9 Cycle = 26790
Keys = 727024
State = 0 0 0 1 6 5 4 7 3 2 8 9 Cycle = 40890
Keys = 1163609
State = 0 0 0 1 7 5 2 6 4 9 8 3 Cycle = 26790
Keys = 772518
State = 0 0 0 2 4 5 8 6 7 1 9 3 Cycle = 1130
Keys = 31256
State = 0 0 0 3 6 8 7 9 1 5 4 2 Cycle = 1130
Keys = 37072
State = 0 0 0 3 8 6 9 1 5 2 7 4 Cycle = 4210
Keys = 99884
State = 0 0 0 4 5 1 8 7 9 6 2 3 Cycle = 2830
Keys = 126139
State = 0 0 0 4 8 3 9 2 5 6 1 7 Cycle = 4710
Keys = 112398
State = 0 0 0 5 8 6 9 4 3 7 1 2 Cycle = 1130
Keys = 31118
State = 0 0 0 5 8 7 3 6 2 9 4 1 Cycle = 1230
Keys = 53719
State = 0 0 0 7 2 4 6 9 1 5 8 3 Cycle = 1130
Keys = 26601
State = 0 0 0 7 3 1 2 5 6 4 9 8 Cycle = 260
Keys = 8536
State = 0 0 0 7 5 6 2 1 3 4 9 8 Cycle = 2470
Keys = 59480
State = 0 0 0 8 6 1 9 4 5 3 7 2 Cycle = 1990
Keys = 34423
State = 0 0 0 9 7 2 6 5 8 3 4 1 Cycle = 1670
Keys = 34690
State = 0 0 2 0 7 3 1 4 9 5 6 8 Cycle = 1130
Keys = 27782
State = 0 0 3 5 2 7 4 8 9 6 1 0 Cycle = 220
Keys = 4726
State = 0 0 3 7 5 2 0 9 6 1 4 8 Cycle = 260
Keys = 10274
Non reachable states = 3630220
------------------------------
Subject: Re: Public|Private key cryptography?
From: lordcow77 <[EMAIL PROTECTED]>
Date: Fri, 07 Apr 2000 16:38:06 -0700
In article <[EMAIL PROTECTED]>,
Jerry Coffin <[EMAIL PROTECTED]> wrote:
>I'll give my prediction for 20 years from now: if you look
carefully,
>you'll be able to find a machine with at least a 10 Ghz
processor and
>at least 2 Gig. of RAM in a dumpster behind a grade school even
>though it still works perfectly. It was donated to the school
when
>it was too old for the original owner to use it for real
business
>applications anymore. The school put it to use for a few
years, but
>it's now become so thoroughly obsolete that even a grade school
can't
>find a use for it anymore, so it's being thrown away even
though it
>still works just as well as it did when it was new.
>
I won't comment on the specifics of Jerry's prediction, but I
will add this additional data point. In 1983, I bought an Intel
80286 running at the then blazing speed of 10 Mhz. It could
address all of 16 MB of RAM, not that anybody could afford such
an insanely large amount of memory at the prices in those days.
These were the days when math coprocessors were not invented yet
and 16 bytes of cache was considered a lot. In 1992, my desktop
computer was an i486SX running at 25 Mhz. It's SpecINT 92
performance was about 10 and I don't think I ever had the
patience to run SpecFP under emulation. Bear in mind that Intel
processors have pretty much always been at the trailing end of
performance, although recently this has begun to change
slightly. The Alpha 21064 debuted in 1992 as well, and had a
SpecINT 92 of over 50. Today, I am typing this on a PIII 600 and
have a really nice Alpha in the room next door. There is more
memory in the cache of the Alpha than total RAM in the 286 that
I referred to previously. If the rate of improvement in
transistor density and clock speed continues, it is not at all
unreasonable to expect 10Ghz processors to be available in 10
years, commonplace in 15, and relegated to embedded
implementations in 25 to 30.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Is AES necessary?
Date: Fri, 07 Apr 2000 23:45:46 GMT
On Fri, 07 Apr 2000 11:00:55 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Now that we'll soon have an AES, I think it could be interesting
>to take a minute to look back and reflect whether AES is really
>necessary.
>
>I'll start by arguing for one side of the issue:
>
>3DES is currently yet strong enough. If that's too weak, we could
>use 5DES etc.
Basically, I agree. It only makes sense to use AES for applications
where:
the performance of triple-DES is just too slow
the gate count of triple-DES is just too large
the block size of triple-DES is just too small.
Triple-DES is still the conservative choice.
And forget about 5-DES. Triple-DES is fine for the forseeable future.
>We could employ some trivial variants of DES that enable expansion
>of the effective key space (e.g. permutation of the subkeys or
>the S-boxes).
No.
Bruce
**********************************************************************
Bruce Schneier, Counterpane Internet Security, Inc. Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: john <[EMAIL PROTECTED]>
Subject: (no subject)
Date: Fri, 07 Apr 2000 17:13:29 -0700
where is a good place to find the laws on crypto?
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: GSM A5/1 Encryption
Date: Sat, 08 Apr 2000 00:04:46 GMT
In article <8cj9me$ild$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
> In article <8cimfj$cod$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]>
wrote:
> > My question, is if you were to design a voice encryption system,
> > how would you go about overcomming this weekness and
> > susceptibility to attack (cf Silence Frames).
>
> I'd use a secure stream cipher, i.e., one that resists known- and
> chosen-plaintext attacks, like any decent modern cipher should.
> Then the silence frame stuff is irrelevant -- you just don't have
> to worry about it, period.
>
> It's only relevant in the case of A5/1 because A5/1 is, in modern
> terms, considered weak: A5/1 is susceptible to known-plaintext
attacks,
> so it cannot be considered strong by cryptographic standards.
> However, if one wants to evaluate the practical impact of the attacks,
> one has to inquire about the availability of known plaintext, and the
> point I was making is that silence frames may provide exactly the
> known plaintext required by the shortcut attacks on A5/1.
>
A Silent Frame is a Silent Frame regardless if the cipher is strong or
week, and will provide plaintext to the cryptoanalyst....My question
was, how to avoid that? ...code the Silent Frame with some random data
or what?
> All of these details come about only because the GSM folks failed to
> use a secure stream cipher.
>
This was done on purpose...there was a major argument between the
French, the Brits and the Germans on choosing an encryption algo for
GSM in the 80's. The Germans wanted a strong crypto, because at the
time they were exposed to the old Soviet Union flank...the Brits and the
French argued the opposite...and the A5 was the result (designed by the
French).
A European manufacturer has produced a prototype strong GSM cellphone
using DH and a 128 bit symmetric cipher...Just wondered why are they not
using a Stream cipher...why a block cipher...I would have thought the
former was more efficient....
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Test Vectors for Block Ciphers
Date: Sat, 08 Apr 2000 00:09:00 GMT
There are so many libraries and implementations of Block Ciphers (DES,
3DES, CAST, IDEA, Blowfish, TwoFish...RC4...etc)...
Are there any standrd set of Test vectors that one can use to evaluate
these libraries and test for correctness of implementation aglogorthms
and coding?
I am assuming that the answer is no, and that one has to write their own
Test Vectors....any info or previous work in this area would be
appreciated...It would be great to have a set of Universal Test vectors
for each cipher....
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Test Vectors for Block Ciphers
Date: Sat, 08 Apr 2000 00:08:42 GMT
There are so many libraries and implementations of Block Ciphers (DES,
3DES, CAST, IDEA, Blowfish, TwoFish...RC4...etc)...
Are there any standrd set of Test vectors that one can use to evaluate
these libraries and test for correctness of implementation aglogorthms
and coding?
I am assuming that the answer is no, and that one has to write their own
Test Vectors....any info or previous work in this area would be
appreciated...It would be great to have a set of Uiversal Test vectors
for each cipher....
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Test Vectors for Block Ciphers
Date: 8 Apr 2000 00:21:26 GMT
In article <8cltak$stl$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>There are so many libraries and implementations of Block Ciphers (DES,
>3DES, CAST, IDEA, Blowfish, TwoFish...RC4...etc)...
>
>Are there any standrd set of Test vectors that one can use to evaluate
>these libraries and test for correctness of implementation aglogorthms
>and coding?
Applied Cryptography has test vectors for most of these, as does
Peter Gutmann's cryptlib library. The DES specification (FIPS pub
176 or something like that) also has DES test vectors.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Public|Private key cryptography?
Date: Fri, 7 Apr 2000 18:28:30 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> If the rate of improvement in
> transistor density and clock speed continues, it is not at all
> unreasonable to expect 10Ghz processors to be available in 10
> years, commonplace in 15, and relegated to embedded
> implementations in 25 to 30.
I'd guess those numbers should be closer to 5, 10 and 15 (or so)
respectively. Even assuming the rate of improvement does slow
somewhat (which wouldn't really surprise me) you're still being
generous in the amount of time involved.
To give a somewhat different data point: Tom was talking about 20
years into the future. Perhaps it would be educational to consider
the specs of a fairly typical personal computer 20 years ago and
compare it to those of today.
20 years ago, the IBM PC hadn't been introduced yet. A typical
personal computer was something like a CP/M machine with an 8-bit
processor running at 1 or 2 MHz or so and typically took around 3
clock cycles to execute each instruction. It could address up to 64K
of memory, but most people didn't have quite that much -- most new
machines had 32 or 48K of memory, while older machines with only 8 or
16K were still pretty common.
Comparing that to a machine of today gives some fairly interesting
numbers: even a rather low-end new machine has at least a 32-bit CPU
running at a minimum of 500 MHz. It averages executing around two
instructions every cycle, and can do substantially more than that at
times. It can address several gigabytes of memory, though a typical
machine probably only has 128 to 256 MB or so.
Doing some division, that means an increase in CPU speed of at least
a couple thousand to one and an increase in memory size of five
thousand to one or so. The CPU speed is a bit harder to pin down:
modern CPUs (even RISCs) typically have much larger instruction sets,
so complex operations (e.g. multiplication and division) have
improved by a larger factor, while more elementary and/or memory
intensive operations have speed up by a factor only a few thousand.
OTOH, the larger addresability figures into this as well: an
application that needed more than tens of kilobytes of memory on the
older machine often had to swap to a slow floppy disk drive to manage
it. That slowed things by an ever larger factor than the difference
between the speed of cache vs. main memory on a current machine.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Q: Petri nets
Date: Sat, 08 Apr 2000 00:32:13 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]>
wrote:
>
> In computer science, a theory that has certain practical
> applications bears the name 'Petri nets'. Are these automata? If
> yes, why are they not treated at all in textbooks on automata
> (at least in the few books I have seen)? If not, what beasts are
> they from the view point of theory of automata? Can Petri nets do
> computations in the sense of automata (treated in the textbooks)?
> If yes, are they equivalent to TM or more powerful? Do Petri nets
> possess the potential of having some relevance to crypto much like
> the cellular automata?
>
You might want to look on the web for an intro
to Petri nets (PNs). IIRC, they are related to
concurrent automata and can be used to
combine finite automata with parallel
programs, process algebra terms, etc. A PN
can be extended with extra inhibitory arcs to
give it the power of a turing machine. PNs can
model discrete event dynamic systems and
might have some use related to crypto. PNs
can simulate finite asynchronous automata
and can be used to formally describe a cellular
automaton with many asynchronous mini-
steps of cells appearing within one
synchronous time phase of the whole
automaton.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
