Cryptography-Digest Digest #330, Volume #10 Wed, 29 Sep 99 14:13:02 EDT
Contents:
Re: Please review proposed rebuttal... (Don Leclair)
Re: Cryptic manuscript... Help (Matthew Harley)
Re: Please review proposed rebuttal... (Bob Silverman)
Re: want URL for Applied CryptoGraphy Book online (Keith A Monahan)
newbie ecc (Tom St Denis)
Re: msg for Dave Scott (JPeschel)
Re: How good is java.security.SecureRandom ? (Mikael Fiil)
Re: ECDL and distinguished points (jerome)
Re: Electronic envelopes (Mok-Kong Shen)
Re: newbie ecc (Alex)
Re: Compress before Encryption (SCOTT19U.ZIP_GUY)
Re: Electronic envelopes (Anton Stiglic)
Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers (Medical
Electronics Lab)
Re: RSA Variation (Medical Electronics Lab)
Re: ECDL and distinguished points (Medical Electronics Lab)
Re: IBM's security chip (Built on the motherboard)! (John Savard)
Re: Electronic envelopes ("Richard Parker")
----------------------------------------------------------------------------
From: Don Leclair <[EMAIL PROTECTED]>
Subject: Re: Please review proposed rebuttal...
Date: Wed, 29 Sep 1999 14:48:53 GMT
Hi,
> One needs a very large Cray-class machine
> to deal with the matrix. (fairly big bucks,
> i.e. $5-10 Million)
Question:
I understand that the block Lanczos algorithm is now the optimal method
for the matrix step but can structured Gaussian elimination still be
useful for reducing the initial matrix to a more reasonable size?
I have an idea, that I would be happy to share, for a distributed
implementation of structured Gaussian elimination. I only have a
partial implementation at the moment but my initial calculations
indicate indicate that it would scale up well (but not quite linearly)
and would have modest data transfer requirements.
Don Leclair
[EMAIL PROTECTED]
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Matthew Harley <[EMAIL PROTECTED]>
Subject: Re: Cryptic manuscript... Help
Date: Wed, 29 Sep 1999 13:26:00 +0100
Reply-To: [EMAIL PROTECTED]
Computer Technician wrote:
>
> > Hi All,
>
> I've been trying to think of the name of a manuscript that I'd seen in the
> past, and can't for the life of me remember what it was called. So I thought
> I'd try here any help would be greatly appreciated. It was done in a coded
> language and was from early times. I believe it started with a V....and
> written in a weird text. I know a lot of people were trying to decode it. It
> also had a lot of illustrations in the margines... like plants and other
> things. If anyone can help with I would be most gracious. Thank you,
Could it be the Voynich manuscript?
http://www2.micro-net.com/~ixohoxi/voy/voynich.htm
Matt Harley
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Please review proposed rebuttal...
Date: Wed, 29 Sep 1999 15:51:09 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Richard D. Latham) wrote:
> Bob Silverman <[EMAIL PROTECTED]> writes:
>
>
<snip>
And I would consider
> > RSA Security as a 'reasonable sized' organization.
> >
>
> A very interesting practical point.
>
> It doesn't appear that the current best-known approach to ECDL
> requires access to a "limited resource" of this class. Doesn't this
> call into question the assertions of (mumble mumble) that ECDL is
> "more secure" than RSA.
I've said this repeatedly.
>
> As a untutored layman, I had thought that most people considered this
> "large machine" requirement at the end of the factoring process, which
> apparently isn't amenable to a distributed effort, to be the "real
> ceiling" in attacking RSA.
I would say the opposite is true. Most people ignore
(or are unaware of) this bottleneck.
>
> I mean, I'll have twice as many MIPs at my disposal in 18 months or
> so, just by standing around and doing nothing ... I'm not ever likely
> to have a Cray-class machine lying around idle.
Yep!
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: want URL for Applied CryptoGraphy Book online
Date: 29 Sep 1999 14:42:02 GMT
Well I don't believe there is an online version of Applied Cryptography.
I believe, however, there is a Dr. Dobb's collection on CDROM for purchase
of around US$100 which includes (amongst a few others) Applied Crypto. A CD
certainly is lighter.
I would hope, as Handbook of Applied Cryptgraphy did, that other publishers
will take the same steps in putting their books online. One can hope,
anyways. :)
Keith
Anandamoy Roychowdhury ([EMAIL PROTECTED]) wrote:
: I already possess a copy of the book ... but it is not the easiest book to
: carry around , so i would really appreciate it if someone could post the
: URL for the Applied Cryptography book
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: newbie ecc
Date: Wed, 29 Sep 1999 16:08:50 GMT
Here's a question that might set me right, what are elliptic curves? From a
math stand point I see them defined as a variation of a cubic. But is there
any criteria to it?
Also if I said ECDLP (discrete log) how does that change from in the field
of integers (or is cyclic ring of integers a better term??)?. Do the
primitive operations + and * change?
If you are wondering I want to learn about EC and DisceteLogarithms kinda
seperately... so I am still looking I found a couple papers on the DLP and
IFP but not much on EC.
Thanks for those who have helped...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: msg for Dave Scott
Date: 29 Sep 1999 16:16:29 GMT
Tom St Denis [EMAIL PROTECTED] writes:
>Sorry about that but really I have never seen it in any programs. Ok let me
>rephrase if I give you
>
>bfaqaaa2q2IpYXBMmmaaaauaaaaqF43{QqmvUThKIkZ7aa65z
>
>will you be able to read it faster then say brute force?
Not a message, that short, as Gwyn explained to you.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Mikael Fiil <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.java.security
Subject: Re: How good is java.security.SecureRandom ?
Date: Wed, 29 Sep 1999 18:24:53 +0200
This is a multi-part message in MIME format.
==============57DC458A1BBAA91ED8DC34D7
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Hey
You may take a look here:
http://www.counterpane.com/yarrow.html
These guys have a lot of information on security, which also includes
random numbers
Mikael Fiil
Stanley Chow wrote:
> We are doing some Java code and need a good random number generator.
> The documentation for the java.security.SecureRandom class seems to
> claim pretty good entropy for its seeding (it certianly takes long
> enough at it).
>
> Has anyone done/seen any evaluation of the cryptographic strength
> of the SecureRandom class? Any pointers are appreciated.
>
> --
> Stanley Chow phone: (613) 271-9446 Fax: (613) 271-9447
> VP Engineering email: [EMAIL PROTECTED]
> Cloakware Corp.
==============57DC458A1BBAA91ED8DC34D7
Content-Type: text/x-vcard; charset=us-ascii;
name="Mikael.Fiil.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for Mikael Fiil
Content-Disposition: attachment;
filename="Mikael.Fiil.vcf"
begin:vcard
n:Fiil;Mikael
tel;cell:+45 40 59 48 68
tel;work:+45 46 19 48 68
x-mozilla-html:TRUE
org:Mikael Fiil Data
adr:;;Elisevej 3, Dåstrup;Viby Sj.;;DK-4130;Denmark
version:2.1
email;internet:[EMAIL PROTECTED]
note:Homepage: www.netbizz.dk
x-mozilla-cpt:;-24208
fn:Mikael Fiil
end:vcard
==============57DC458A1BBAA91ED8DC34D7==
------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: Re: ECDL and distinguished points
Reply-To: [EMAIL PROTECTED]
Date: Wed, 29 Sep 1999 15:58:58 GMT
On 29 Sep 1999 13:43:08 GMT, John Sager wrote:
[snip]
> One could
>reduce it to, say, 5 minutes but the storage & comparison server has to
>have that much more storage capacity for all the extra points stored.
>Plus there is all that extra network traffic.
it was what i meant by 'big computer' (aka a lot of memory and
centralized so no network traffic). my question was badly posed.
let me retry: suppose i store all the points (instead of 1 in 2^30)
and try to match them.
1. am i right to think that the collisions are more probable ? if so, how
much more probable ?
2. this require more memory and increase the match time. but if we forget the
memory to consider only the time, is the tradeoff interesting ? i.e. the
time saved by a better collision probability is greater that the time
loosed by a bigger matching ?
>The particular method used is ideal for distribution. There may be
>non-distributed algorithms that are faster; I don't know. I would
>think that a rather different mathematical approach is required.
>Anyway, the 'big computer' which would do it in 40 days doesn't exist.
>(I would dare to speculate, not even at the NSA:)
:)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Electronic envelopes
Date: Wed, 29 Sep 1999 15:26:31 +0200
Richard Parker wrote:
>
> > In other words, can the amount of resources employed somehow be
> > audited (proved)?
>
> I'm afraid I don't really understand this question.
Is it the case that the notary doesn't have to run ANY computing
process between time 0 (when the envelope is deposited) and time
T (when the enveloped is opened) and only one very short-durated
computing process at time 0 and T? If yes, my question cited
above is moot.
Allow me an additional question: Could a person at the server
collaborate with the notary to decrypt the message before T or else
render a certain set of messages encrypted with the help of the server
to be earlier decryptable?
M. K. Shen
------------------------------
From: Alex <[EMAIL PROTECTED]>
Subject: Re: newbie ecc
Date: 29 Sep 1999 13:29:35 -0400
Hi, Tom.
> Also if I said ECDLP (discrete log) how does that change from in the
> field of integers (or is cyclic ring of integers a better term??)?.
> Do the primitive operations + and * change?
There are two groups associated to the finite field Z/pZ: the additive
group, and the multiplicative group. Diffie-Hellman relies only on
properties associated to the multiplicative group. Specifically, it
relies on the fact that the group operation is associative and the fact
that it can be hard to determine m if you are just given n^m mod p. So
I could send you n^a mod p, you could send me n^b mod p, and because
multiplication is associative, we would both get the same answer if I
compute (n^b)^a and you compute (n^a)^b. (I guess you must know this
stuff, since you've implemented DH. I just wanted to emphasize that the
addition operation on Z/pZ doesn't enter into it.)
In principle, you can do the same thing with any abstract group. You
need to choose the group carefully to get an effective cryptosystem,
though. In fact, in principle, all you need is an associative
operation, but the only cryptographically good ones found so far seem to
be group multiplication operations.
Usually the group operation on an elliptic curve is denoted by "+", but
this is to some extent an arbitrary choice. For the purposes of ECC, at
least, there is only one relevant operation.
> From a math stand point I see them defined as a variation of a
> cubic. But is there any criteria to it?
Criteria for what? The geometric procedure used to define the group
operation on an elliptic curve works on any irreducible plane cubic, I
think. You need to make sure the curve is smooth, or you get a much
simpler group structure. (I guess the DLP in this case is the same as
for over a finite field...) I understand that there are some elliptic
curves that you're best to avoid for cryptographic purposes, because of
their special group structure, but I don't know much about that.
> If you are wondering I want to learn about EC and DisceteLogarithms
> kinda seperately... so I am still looking I found a couple papers on
> the DLP and IFP but not much on EC.
I have not found a good introduction to the index calculus attack on the
web yet. I have bookmarks to Joseph Silverman's papers on the index and
xedni calculus attacks lying around somewhere, and I can dig them up if
you like. However, I believe those papers are very hard, and you would
need at least several week's study of basic elliptic curve theory before
you could fully understand their key ideas. For that purpose, a good
place to start might be Silverman's _Rational Points on Elliptic
Curves_, followed by portions of his _Arithmetic on Elliptic Curves_.
A dead-tree article about index calculus attacks was in the first volume
of the Lecture Notes in Computer Science publication about Algorithmic
Number Theory, I think.
I found a reference for baby-step giant-step on the web, but that's
almost useless for breaking cryptoschemes, I suppose.
Alex.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Compress before Encryption
Date: Wed, 29 Sep 1999 18:29:30 GMT
In article <[EMAIL PROTECTED]>, James Felling
<[EMAIL PROTECTED]> wrote:
>1-1 compression algoritims are rare because:
>
>1) they are comutationally more demanding than non 1-1 compression( catching
>special cases)
>2) they are not robust as to error detection -- a problem in a compressed
>file will not be detected until use of that data is attempted.--and as a user
>of compression products for archiving/ data transmission, I would rather have
>the ability to easily detect such errors.
Well if you use PKZIP what good does it do you to know that is an error.
If you are a follower of the crypto god if you look at page 226 (one of the
few good pages in the book) it shows a diagram of compression then encryption
and then the boxes for tranmisstion which handles error correction is done
after compression and encryption. This is where error correction should be on
a message not part of the compression or encryption scheme where it can
be used as a hook for someone breaking the encryption. Hell when I send a
message to my son it is compressed whitened and encrytped. The last thing
I do is expand it by pkzip and that gets sent in the email. Since the email
can handle zip files. I count on the transmission protocal to handle error
correction like it should. If it does catch the erroor it does not unzip
correctly when I get it. But it has been a few years since I got a file that
unzipped uncorrectly ( but it does happen) it this point I never have had a
proiblem running through the decryption and decompression.
>3) They are more demanding to program than non 1-1 compressions( those
>special cases again)
>4) Their efficiency in compressing data is not apreciably different than non
>1-1 methods.
Actually since the structural information is not added to the file
I belive that most LZ methods with a little thought can be converted
not sure about BWT methods. The resulting file should be shorter.
The example I give you is the adaptive huffman compression that I
modifed. My method is as short or shorter in every case. I think you
will see this in other methods. It is just that liitle thought has been
give to this. But the fact is if you convert a method to one to one you
are removing information that the non 1-1 method needlessly added
during its compression ( assuming you can make a 1-1 for that method)
if they are using the same technique. Or is this concept over your head.
>5) Generaly a 1-1 compressor will have a larger code footprint than a non 1-1
>compressor.
This may be true but since I can find no information on these methods
you are just spinning your wheels. How many one to one methods have you
looked at.
>
>So it becomes difficult to justify their writing/use except for special
>purpose applications.
>
>I can see some advantages to them for some crypto aplications, but in
>general, I feel that the payback does not justify the associated downsides.
Yes just what is the down side as far as using a version of compression
that is one to one before encryption. You say there are disadvantages
what are they? I personally think that giving an attacker information as to
the fact that a guessed key can be wrong is of great help to the attacker
what makes you think otherwise.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Electronic envelopes
Date: Wed, 29 Sep 1999 12:44:10 -0400
Mok-Kong Shen wrote:
> Anton Stiglic wrote:
> >
> > The sole fact that you use time is enough to say that
> > it can't work. Time is relative, you would need a trusted
> > central unit that would give you the exact time. If you have
> > a trusted central unit (authority) U, Alice and Bob could just
> > agree with U about the time U is to reveal the ciphertext to Bob.
> >
> > It isn't more complicated than that!
>
> Is Alice the depositor of the document in your scenario?
yes
> I guess
> yes. Probably I hadn't been very explicit. But the last sentence
> of my original post implies that the depositor is no longer
> available for anything connected to the matter after deposition of
> the envelope. In your scenario it could be that Alice is no longer
> alive at the predetermined time point of secret disclosure.
>
If you insist that Bob can no longer communicat with Alice, you could
just as well consider here as dead (but that would be sad for crypto..
:(
But that was not my point, my point is that time is relative to
something,
you have to define that something, then we could talk about possible
solutions.
>
> M. K. Shen
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers
Date: Wed, 29 Sep 1999 11:50:38 -0500
Bob Silverman wrote:
> The time to break 512-rsa is e^(1.92 (log n)^1/3 (loglog n)^2/3)
> which for n = 2^512 comes to about 1.6 x 10^19
>
> 97 bit DL is sqrt(pi/2 * 2^97) EC point additions ~ 5 x 10^14.
> Even if each point addition takes 10^3 operations, this is still
> less work.
>
> I know. Using actual numbers to dispute a claim is an unfair
> way to argue :-)
You're equating "time" with "ops". However, the real case shows that
1 op of RSA takes much less time than 1 op of ECC. The total cpu
cycles for the 512 bit RSA crack was ~8,000 MIPS-years and the
total cpu cycles for the 97 bit EC crack was ~16,000 MIPS-years.
You can argue that an RSA op is faster than an ECC op, this is
clear. Advantage RSA. But I'll argue that ECC is cheaper and
quicker for encryption *because* the key size is smaller for
the same level of security. And the empirical evidence proves
it out.
What's really going to be fun is to watch how the marketing
guys go after all this. Every application has different
requirements, and figuring out how to sell RSA vs ECC on each
one will be hard. I think ECC is going to gain while RSA
lags over the next 10 years, but I'm biased :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: RSA Variation
Date: Wed, 29 Sep 1999 11:56:36 -0500
Gary Partis wrote:
> We have inherited a sub-set of RSA in an embedded system.
>
> It essentially encrypts and decrypts using the exponentiation function
> only.
>
> What we do not have is an algorithm for generating keys - the standard
> algorithm does not work! :-(
>
> Has any one come across this subset before, and if so, do they have the
> algorithm for generating keys?
Do you have the source code at least? If you know the math,
figuring the key gen routine is easy. As long as you've got
source you can recreate any key you want and burn in your own.
If you don't have sources, it'll take a bunch more work to
reverse engineer the thing. But the real trick is to convert
all the code to the math it's doing, then from that figure out
the key gen operation, then change the write locations to
reflect your new keys.
Patience, persistence, truth,
Dr. mike
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: ECDL and distinguished points
Date: Wed, 29 Sep 1999 12:07:30 -0500
jerome wrote:
> it was what i meant by 'big computer' (aka a lot of memory and
> centralized so no network traffic). my question was badly posed.
> let me retry: suppose i store all the points (instead of 1 in 2^30)
> and try to match them.
That's a lot of storage!!
>
> 1. am i right to think that the collisions are more probable ? if so, how
> much more probable ?
No, we only need one collision. The estimate of 10^14 EC ops
doesn't change (for ECC2-97 for example).
> 2. this require more memory and increase the match time. but if we forget the
> memory to consider only the time, is the tradeoff interesting ? i.e. the
> time saved by a better collision probability is greater that the time
> loosed by a bigger matching ?
No, it's not really interesting. You're better off doing more
parallel searches for distingushed points and letting some central
computer do the comparisons for matching. A massively parallel
SIMD machine comes to mind :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: IBM's security chip (Built on the motherboard)!
Date: Wed, 29 Sep 1999 17:13:32 GMT
"Melih Abdulhayoglu" <[EMAIL PROTECTED]> wrote, in part:
>any more info pls!
Well, according to that article, it wasn't to be officially announced
till today, so maybe today there are details on the IBM site.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Richard Parker" <[EMAIL PROTECTED]>
Subject: Re: Electronic envelopes
Date: Wed, 29 Sep 1999 17:16:48 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Is it the case that the notary doesn't have to run ANY computing
> process between time 0 (when the envelope is deposited) and time
> T (when the enveloped is opened) and only one very short-durated
> computing process at time 0 and T?
Yes - actually, the notary does even less computing then that. The
notary does not have to do any cryptographic computation when each
envelope is deposited. The notary does, however, have to perform key
generation some time before he can begin to accept any envelopes to be
deposited.
> Allow me an additional question: Could a person at the server
> collaborate with the notary to decrypt the message before T or else
> render a certain set of messages encrypted with the help of the server
> to be earlier decryptable?
Yes, a malicious time server could collude with a malicious notary to
open Alice's envelope before the time she specified. If this is a
concern, use a threshold secret-sharing scheme in addition to the
time-release protocol.
-Richard
------------------------------
** 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
******************************
