Cryptography-Digest Digest #396, Volume #10 Mon, 11 Oct 99 17:13:03 EDT
Contents:
Re: Using PGP as a source of random numbers (Jim Dunnett)
Re: Ritter's paper (Tim Tyler)
Re: Ritter's paper (Tim Tyler)
Layperson Q: how long to crack 32-bit RSA? (Roy Pardee)
Re: user authentication (Thomas Wu)
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" ("John E.
Kuslich")
Re: on linear keyspaces (Tim Tyler)
Re: Layperson Q: how long to crack 32-bit RSA? (jerome)
Re: Ritter's paper ("Trevor Jackson, III")
Re: RSA-512: Weizmann Institute: London Times (Tim Tyler)
----------------------------------------------------------------------------
From: amadeus @0SPAM.netcomuk.co.uk (Jim Dunnett)
Subject: Re: Using PGP as a source of random numbers
Date: Mon, 11 Oct 1999 18:55:19 GMT
Reply-To: Jim Dunnett
On Sun, 10 Oct 1999 17:41:35 +0200, "Kasper Pedersen" <[EMAIL PROTECTED]>
wrote:
>
><amadeus @0SPAM.netcomuk.co.uk (Jim Dunnett)> wrote in message
>news:[EMAIL PROTECTED]...
>> On Sat, 09 Oct 1999 13:49:40 GMT, [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
>> wrote:
>>
>> > But it would be best ot get something based on some quantum effect like
>> >radioactive decay or some other quatum measurment for true randomness.
>>
>> Radio noise/static is also useful for this.
>
>Before I built a source, I used a soundcard and a radio (I just needed some
>bits, I don't fancy OTPs). Unfortunately, radios are band-limited on the LF
>side, and they have various other illnesses, seen from the number source
>standpoint.
You could probably overcome this by using the discriminator output
from a scanner rather than the earpiece output.
You'd have to make sure also that no outside radio frequencies
get into it. Disconnect the antenna and put a dummy load in its
place.
--
Regards, Jim. | The mad are all in God's keeping.
amadeus%netcomuk.co.uk |
dynastic%cwcom.net |
| Kipling, 1865 - 1936.
PGP Key: pgpkeys.mit.edu:11371 |
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Ritter's paper
Reply-To: [EMAIL PROTECTED]
Date: Mon, 11 Oct 1999 18:44:58 GMT
Patrick Juola <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
:>[EMAIL PROTECTED] wrote:
:>: Trevor Jackson, III ([EMAIL PROTECTED]) wrote:
:>: : wtshaw wrote:
:>: there is, I'm afraid, a sense in which it is valid to say we will "never
:>: know". The problem of establishing a lower bound on a cipher's strength
:>: is, I believe, fundamentally equivalent to the famous "halting problem".
:>
:>Turing's halting problem is often used to express hopelessness at finding
:>an answer - in much the same was as calling a problem NP.
: Not by anyone who actually knows what NP or the halting problems
: means.... All NP problems, for instance, are known to be
: solvable; the halting problem and its equivalents are known to
: *NOT* be solvable..
Both the Turing halting problem and calling a problem NP-complete
*are* fairly frequently invoked in conjunction with statements like
"so we may as well give up, then" - tiz a fact ;-)
As I mentioned if finding a lower limit on the strength of a *particular*
cypher were only as hard as determining if a *particular* program halts,
that would be wonderful!
John has subsequently clarified that he meant that, finding a lower limit
on the strength of a *particular* cypher is as hard as determining if
an *arbitrary* program halts - which is known to be an impossible problem.
Now, I'm still rather far from convinced that this analogy is a good one -
and think that for some simple cyphers you /may/ eventually actually be
able to prove minimum bounds for strength to everyone's satisfaction - but
at least it's now very clear what he meant.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Remember, to a computer, 1 + 1 = 10.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Ritter's paper
Reply-To: [EMAIL PROTECTED]
Date: Mon, 11 Oct 1999 19:15:33 GMT
Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
:> : Tim Tyler wrote:
:> :> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
:> :> Surely some generators are easier to crack than others... and some of them
:> :> are /extremely/ difficult to crack.
:> :>
:> :> I see no reason in principle why a PRNG-based cypher should be weak.
:>
:> : In practice true, but getting less so as time goes on. In theory false.
:>
:> Getting "less and less so as time goes on"? What support do you have for
:> this?
: In theory the initial state of a PRNG is completely determined by its
: output. Thus, given a sufficiently sophisticated algorithm, one can
: infer the initial state from the output.
Much the same is true of a block cypher. Given enough cyphertext, you can
establish how the cypher is scrambling the blocks.
If you consider the analogy between a "full period" PRNG (which cycles
through 2^N states and hits each state only once) and a block
cypher which maps each block of N bits to the successor of that
block as found in the PRNG output, it should be clear that there is
a type of equivalence between such systems.
: In the limit ones builds the "inverse machine", feeds it the output in
: reverse chronological order, and produces the initial state.
You talk as though this is actually feasible. I view such a task as
completely on par with any other aspect of cryptanalysis.
: As time goes on the sophistication of analytic algorithms increases
: whereas the sophistication any particular PRNG is constant. Yes, you can
: increase PRNG complexity, but it is not clear that that complexity makes
: the analytic task linearly harder.
This is true of all types of cypher, not just PRNG-based ones.
:> "In theory false"? How is a PRNG-based cypher any less secure than any
:> other type of cypher, in principle.
: PRNGs are not less secure than small-key ciphers. They all have unknown
: strength or strength relative to problems of unknown strength.
Hmm, that sounds a bit vague.
There are algorithms like Blum, Blum and Shub, where cracking them is
provably as hard as factoring large composite numbers.
I don't see why you need to compare them to small key cyphers. You can
make a PRNG-based cypher that's up there with the best of them.
:> :> Certain PRNG-based stream cyphers have one or two problems associated with
:> :> the fact that they make no attempt to "smear" the information present in
:> :> each letter spatially across a number of letters in the cyphertext - but
:> :> this is not a weakness of using random numbers per se.
:>
:> : The central point is that, in theory, any PRNG has a limited amount of
:> : state. As the PRNG operates it discloses that state. Once you have output
:> : >= state you can only have one possible state that generated that output.
:>
:> ...but how do you find out which one? *If* you have to search through the
:> whole period of the PRNG for the sequence, then this is directly analogous
:> to searching through the key-space of a block cypher.
: It depends on the structure of the RNG. For example, the
: Berklecamp-Massey algorithm works on FSR generators.
Yes, and frequency analysis works on monoalphabetic cyphers. There is
no general technique for cracking PRNGs. The task is in theory as hard
as pretty much any other difficult bit of cryptanalysis you care to
mention.
:> : Finding the initial state given the output can be difficult in practice,
:> : but it cannot be made impossible.
:>
:> Of course not. In the same sense that a brute force search through the
:> keyspace will "break" any cypher.
: No, we're discounting brute force, otherwise we'd all settle for long keys.
"No?" It can be made impossible??? ... or "No", not in the same /sense/?
Both cannot be made impossible - I don't see much of an issue.
: The target is an algorithmic attacks such as differential, linear,
: slide, etc.
Well, OK, the equivalent operation for other sorts of cypher would be
a known-plaintext attack employing cryptanalytic techniques.
A block-cypher /also/ has a finite complexity and a limited internal
state. It's typically possible to reverse-engineer these things - in much
the same way as a PRNG - given enough output and enough plaintext.
:> The point about a cryptographic RNG is that you can make it /very/ hard to
:> find short-cuts to kinding the key from the output. It's the same with
:> (e.g.) block cyphers - you can't make it impossible to find the key, but
:> you can make it very, very hard to locate it by methods more rapid than
:> searching the entire keyspace.
: How hard? To support your claim you need to show that there is a lower
: bound on the work factor to find the initial state. Do you know of such
: a case?
I'm not trying to *prove* it - I'm just saying in practice it can be
made very difficult. Certainly there are PRNGs out there with cash
prizes waiting for people who can crack them. If finding their
seeds were as simple as all that, no one would be foolish enough to
put up such stakes.
I can no more prove a minumum strength for a PRNG-based cypher than you
can for the alternative (less weak?) cypher of your choice.
:> Your posts seem to paint a black picture of PRNG-based cryptography.
: I used the word bleak.
:> Looking more closely, I see absolutely no evidence that they
:> are (in principle) any less secure than any other modern cypher.
: Agreed.
Perhaps I was misled by your describing PRNG-based cyphers as "weak".
If you meant that they are weak - but no more weak than any other form
of cryptography - then the point under debate seems to me to vanish.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Energizer bunny arrested! Charged with battery.
------------------------------
From: Roy Pardee <[EMAIL PROTECTED]>
Subject: Layperson Q: how long to crack 32-bit RSA?
Date: Mon, 11 Oct 1999 19:19:05 GMT
Greetings Folks,
Apologies if this is ill-posed or easily answered elsewhere--I searched
through the FAQ & past postings on deja.com, so far to no avail.
I've got a database app that I'd like to use for a multi-site medical
study. My app relies on microsoft Access 97 replication, which sends
32-bit RSA encrypted 'message files' via anonymous ftp. I have the
impression that 32-bits is very weak encryption, but would like to get
specifics if it's possible, on just how weak that is. Specifically, is
there easily obtained software available, to which I might feed one of
my encrypted message files for decryption? If so, would anyone care to
guess what sort of compute time that would take for say, a top-of-the-
line wintel PC?
I don't anticipate having any really motivated outside parties actually
trying to crack these things (& it's unclear to me what they'd do with
a message file even if they did crack it--it's not like they contain
the whole dbase) but I *do* have to make the case that this is safe
enough for medical data to six different Human Subject Research Review
committees, and so I would love it if I could point to some
authoritative source that said, e.g., that the problem is considered
trivial, but would still take 4 pentium III's three days to crack, or
some such...
Many thanks in advance!
-Roy
Roy Pardee
Research Analyst/Programmer
Center for Health Studies
Group Health Cooperative
[EMAIL PROTECTED]
*** Please note new phone number!***
(206) 442-4065
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: user authentication
Date: 11 Oct 1999 11:24:48 -0700
Bill Lynch <[EMAIL PROTECTED]> writes:
>
> I'm wondering if this simple type of user authentication scheme would be
> secure:
>
> The client requests to logon.
> The server acknowledges this and responds back with a random number.
> the client hashes their username, password and the random number
> together and sends the hash and username back to the server.
> the server looks up the client's password based on the username and then
> hashes the username, password and random number. if that hash matches
> the one from the client, the client is allowed a logon.
This protocol is susceptible to brute-force dictionary attacks against
the password and provides no secure key-exchange. A man-in-the-middle,
besides being able to attack the protocol and getting a valid response
for any challenge, could simply hijack a valid session and use it.
The "state-of-the-art" has advanced to the point where simple
password-based protocols now resist these attacks. Look at
SRP, EKE, SPEKE, and technologies like them - they deliver what
you're looking for.
http://srp.stanford.edu/srp/
http://www.integritysciences.com/
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
From: "John E. Kuslich" <[EMAIL PROTECTED]>
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks"
Date: Mon, 11 Oct 1999 12:47:44 -0700
Bravo. Well said.
The principles you have so clearly stated should be emphasized for any
encryption scheme based on software, especially PC based software.
The PC is not secure whether it is running DOS, Windows NT or Linux ar any
other OS you can imagine. It therefore stands to reason that any software
running on an insecure computer is also insecure.
Even the much touted one - time - pad is insecure on an insecure computer.
That is why the discussions about theoretical security of cryptosystems
based on prime number factoring or size of the keyspace consistently miss
the point. The medium is the message...
The medium is insecure, therefore the message is insecure.
A cryptographic system is like a boat made of layers of steel plate
covered by more layers of titanium plate covered by layers of more steel
armor plate. Just one little leak, just one little sea cock left open,
just one little iceberg, just one sailor beat up with one rubber hose can
scuttle the ship. The name Titanic comes to mind...
NSA has known this for decades. Even Sadam's cryptographers know this.
All valuable information will eventually become known. Cryptographic
algorithm theoretical security is irrelevant once the cryptographic system
is attacked by competent "cheaters". Once a truly leak- free hull is
developed, a competent agent will sink your ship in the middle of the
night by filling the hull from a garden hose as the confident crew sleeps.
Resistance is futile...
JK
http://www.crak.com
Bruce Schneier wrote:
> Inside Risks #112
>
> CACM vol. 42, no. 10, October 1999.
>
> Risks of Relying on Cryptography
> Bruce Schneier
>
> Cryptography is often treated as if it were magic security dust:
< snip >
>
> As our society becomes more
> reliant on a digital infrastructure, the process of security must be
> designed in from the beginning.
> **********************************************************************
> Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
> 101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
> Free crypto newsletter. See: http://www.counterpane.com
--
John E. Kuslich
Password Recovery Software
CRAK Software
http://www.crak.com
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: on linear keyspaces
Reply-To: [EMAIL PROTECTED]
Date: Mon, 11 Oct 1999 19:41:21 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: Tim Tyler <[EMAIL PROTECTED]> wrote:
:> No. /None/ of these are known to fulfill this requirement. If you
:> believe otherwise, I will not be convinced of the fact until you
:> demonstrate it in some manner.
: Ok hotshot, prove that you exist. I mean what I stated is assumed truth. go
: with it.
This "truth" is assumed only by you it seems. As far as I'm aware,
nobody else discounts the possibility of non-brute-force attacks on
modern cyphers.
:> No, no, I'm talking about attacks on the *cypher*.
:>
:> Many, many, cyphers have been broken by cryptanalysis, exploiting
:> features of the plaintext, using tools such as freqiency analysis.
: Uh, frequency analysis hardly works against block ciphers of 64-bits or
: 128-bits.
Cryptanalysis is not entirely confined to using traditional frequency
analysis - that's why I said "tools such as frequency analysis".
If you are looking at a block cypher of a signal stream that you /know/
has bit 7 set to zero, that gives you certain systematic information
about the cypher. It is possible to use such information to reduce the
quantity of work involved in breaking the cypher.
Your belief that brute force is the /only/ way to defeat modern cyphers
using cryptanalysis is liable to lead you severly astray. It may cause
you to overestimate the strength of the cyphers you use. Don't say you
haven't been warned.
:> Modern cyphers make this approach more difficult, but are still /far/
:> from making the best approach to breaking them an exhaustive search -
:> assuming you have sufficient cyphertext, etc.
:>
:> You seem to argue as though the science of cryptanalysis has been
:> reduced to mere brute force searching by modern cypher techniques.
:> This is very far from the case.
: Assuming you have enough plaintext... hehehe do you actually know how much
: plaintext you need to break des? try 2^50 bytes or so....
There are /no/ attacks on DES with less plaintext than 2^50 bytes?
Are you /sure/ about this? What is the source of your information?
I'm sorry - but I just don't believe you ;-(
: For RC5 at 12 rounds you need 2^53 blocks or 2^56 bytes.
Really? How do you know this? What is the source of your information
that there is no plaintext attack which requires less information?
: At anyrate most ciphers are presumed strong when the theory suggests that
: the only available models are so bad that they cannot reliable work.
Unfortunately, your argument depends on *more* than just the cyphers being
"presumed" strong on the basis of currently "available models".
You need them to be /so/ strong that the best attack is definitely a brute
force attack, by trying all the keys.
If a better attack exists, or even *might* exist, your *whole
argument* about compression being near-worthless no longer applies.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
No individual raindrop ever considers itself responsible for the flood.
------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: Re: Layperson Q: how long to crack 32-bit RSA?
Reply-To: [EMAIL PROTECTED]
Date: Mon, 11 Oct 1999 20:15:06 GMT
On Mon, 11 Oct 1999 19:19:05 GMT, Roy Pardee wrote:
>Greetings Folks,
>
>Apologies if this is ill-posed or easily answered elsewhere--I searched
>through the FAQ & past postings on deja.com, so far to no avail.
>
>I've got a database app that I'd like to use for a multi-site medical
>study. My app relies on microsoft Access 97 replication, which sends
>32-bit RSA encrypted 'message files' via anonymous ftp. I have the
>impression that 32-bits is very weak encryption, but would like to get
>specifics if it's possible, on just how weak that is. Specifically, is
>there easily obtained software available, to which I might feed one of
>my encrypted message files for decryption? If so, would anyone care to
>guess what sort of compute time that would take for say, a top-of-the-
>line wintel PC?
RSA 32bits is -very- weak. a student of highschool with no special knowledge
in mathematics can crack it in less than 5sec with a 486/33.
he may spend 10min to write the cracker which is around 10 lines long.
>I don't anticipate having any really motivated outside parties actually
>trying to crack these things (& it's unclear to me what they'd do with
>a message file even if they did crack it--it's not like they contain
>the whole dbase) but I *do* have to make the case that this is safe
>enough for medical data to six different Human Subject Research Review
>committees, and so I would love it if I could point to some
>authoritative source that said, e.g., that the problem is considered
>trivial, but would still take 4 pentium III's three days to crack, or
>some such...
It is indead trivial and require much less cpu to crack.
Using pgp, publically available, would be astronomically more secure.
------------------------------
Date: Mon, 11 Oct 1999 16:20:11 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Ritter's paper
Tim Tyler wrote:
> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
> :> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
> :> : Tim Tyler wrote:
> :> :> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
>
> :> :> Surely some generators are easier to crack than others... and some of them
> :> :> are /extremely/ difficult to crack.
> :> :>
> :> :> I see no reason in principle why a PRNG-based cypher should be weak.
> :>
> :> : In practice true, but getting less so as time goes on. In theory false.
> :>
> :> Getting "less and less so as time goes on"? What support do you have for
> :> this?
>
> : In theory the initial state of a PRNG is completely determined by its
> : output. Thus, given a sufficiently sophisticated algorithm, one can
> : infer the initial state from the output.
>
> Much the same is true of a block cypher. Given enough cyphertext, you can
> establish how the cypher is scrambling the blocks.
>
> If you consider the analogy between a "full period" PRNG (which cycles
> through 2^N states and hits each state only once) and a block
> cypher which maps each block of N bits to the successor of that
> block as found in the PRNG output, it should be clear that there is
> a type of equivalence between such systems.
Yes.
>
>
> : In the limit ones builds the "inverse machine", feeds it the output in
> : reverse chronological order, and produces the initial state.
>
> You talk as though this is actually feasible. I view such a task as
> completely on par with any other aspect of cryptanalysis.
It is feasible now in some cases. I expect the number of cases to increase as time
passes.
>
>
> : As time goes on the sophistication of analytic algorithms increases
> : whereas the sophistication any particular PRNG is constant. Yes, you can
> : increase PRNG complexity, but it is not clear that that complexity makes
> : the analytic task linearly harder.
>
> This is true of all types of cypher, not just PRNG-based ones.
>
> :> "In theory false"? How is a PRNG-based cypher any less secure than any
> :> other type of cypher, in principle.
>
> : PRNGs are not less secure than small-key ciphers. They all have unknown
> : strength or strength relative to problems of unknown strength.
>
> Hmm, that sounds a bit vague.
It means there are cihpers without proofs of strength and ciphers with proofs of
strength relative to other problems. BBS is the latter. We _think_ the best
possible factoring method for large composites leaves it as a hard problem. But we
have no proof. All we have is the fact of our lack of success at finding better
methods. That fact is suggestive, but nowhere near conclusive.
>
>
> There are algorithms like Blum, Blum and Shub, where cracking them is
> provably as hard as factoring large composite numbers.
>
> I don't see why you need to compare them to small key cyphers. You can
> make a PRNG-based cypher that's up there with the best of them.
I meant small-key as opposed to ciphers where the key size meets ot exceeds the size
of the message space (OTP).
>
>
> :> :> Certain PRNG-based stream cyphers have one or two problems associated with
> :> :> the fact that they make no attempt to "smear" the information present in
> :> :> each letter spatially across a number of letters in the cyphertext - but
> :> :> this is not a weakness of using random numbers per se.
> :>
> :> : The central point is that, in theory, any PRNG has a limited amount of
> :> : state. As the PRNG operates it discloses that state. Once you have output
> :> : >= state you can only have one possible state that generated that output.
> :>
> :> ...but how do you find out which one? *If* you have to search through the
> :> whole period of the PRNG for the sequence, then this is directly analogous
> :> to searching through the key-space of a block cypher.
>
> : It depends on the structure of the RNG. For example, the
> : Berklecamp-Massey algorithm works on FSR generators.
>
> Yes, and frequency analysis works on monoalphabetic cyphers. There is
> no general technique for cracking PRNGs. The task is in theory as hard
> as pretty much any other difficult bit of cryptanalysis you care to
> mention.
There is no single, generalized technique. But there are techniques that work very
well on specific designs.
> :> : Finding the initial state given the output can be difficult in practice,
> :> : but it cannot be made impossible.
> :>
> :> Of course not. In the same sense that a brute force search through the
> :> keyspace will "break" any cypher.
>
> : No, we're discounting brute force, otherwise we'd all settle for long keys.
>
> "No?" It can be made impossible??? ... or "No", not in the same /sense/?
Not in the same sense. There is no known method for showing that all attacks take
as much work as brute forcing the key space.
>
>
> Both cannot be made impossible - I don't see much of an issue.
>
> : The target is an algorithmic attacks such as differential, linear,
> : slide, etc.
>
> Well, OK, the equivalent operation for other sorts of cypher would be
> a known-plaintext attack employing cryptanalytic techniques.
>
> A block-cypher /also/ has a finite complexity and a limited internal
> state. It's typically possible to reverse-engineer these things - in much
> the same way as a PRNG - given enough output and enough plaintext.
Yes. My point is that there is no floor on how easy that might be.
>
>
> :> The point about a cryptographic RNG is that you can make it /very/ hard to
> :> find short-cuts to kinding the key from the output. It's the same with
> :> (e.g.) block cyphers - you can't make it impossible to find the key, but
> :> you can make it very, very hard to locate it by methods more rapid than
> :> searching the entire keyspace.
>
> : How hard? To support your claim you need to show that there is a lower
> : bound on the work factor to find the initial state. Do you know of such
> : a case?
>
> I'm not trying to *prove* it - I'm just saying in practice it can be
> made very difficult. Certainly there are PRNGs out there with cash
> prizes waiting for people who can crack them. If finding their
> seeds were as simple as all that, no one would be foolish enough to
> put up such stakes.
>
> I can no more prove a minumum strength for a PRNG-based cypher than you
> can for the alternative (less weak?) cypher of your choice.
>
> :> Your posts seem to paint a black picture of PRNG-based cryptography.
>
> : I used the word bleak.
>
> :> Looking more closely, I see absolutely no evidence that they
> :> are (in principle) any less secure than any other modern cypher.
>
> : Agreed.
>
> Perhaps I was misled by your describing PRNG-based cyphers as "weak".
>
> If you meant that they are weak - but no more weak than any other form
> of cryptography - then the point under debate seems to me to vanish.
Good.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: RSA-512: Weizmann Institute: London Times
Reply-To: [EMAIL PROTECTED]
Date: Mon, 11 Oct 1999 20:10:05 GMT
[EMAIL PROTECTED] wrote:
: ca314159 ([EMAIL PROTECTED]) wrote:
: : Douglas A. Gwyn wrote:
: : > What I want is more info on the supposed Weizmann device
: : > that cracks a 512-bit RSA key in 12us.
: : Twinkle could be called "special optical technology"
: : http://www.rsa.com/rsalabs/html/twinkle.html
: So Twinkle, hyped up on this site, and further garbled by the Sunday
: Times, is the source of this rumour.
12us? From the "Twinkle" site above:
``How long would a 512-bit modulus take with TWINKLE?
A 512-bit modulus would take 6 to 7 times as long for the sieving and
2 to 3 times the size of the factor bases as RSA-140. The size of the
matrix to be solved grows correspondingly, and the time to solve it
grows by a factor of about 8. Thus, 15 to 20 devices could do the
sieving in about 5-6 weeks. Doubling the number will cut sieving time
in half. The matrix would take another 4 weeks and about 2 Gbytes of
memory to solve. The total time would be 9-10 weeks.''
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
New regulations means new jobs for new regulators.
------------------------------
** 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
******************************
