Cryptography-Digest Digest #639, Volume #9 Wed, 2 Jun 99 14:13:02 EDT
Contents:
Re: The BRUCE SCHNEIER Tirade ([EMAIL PROTECTED])
New Computer & Printer for Dave Scott ("Gus James")
Re: random numbers in ml (John Savard)
One-Way hash functions (Giovanni Serafini)
Re: block ciphers vs stream ciphers (Scott Fluhrer)
Re: OTP Problems ([EMAIL PROTECTED])
Re: Using symmetric encryption for hashing (Aidan Skinner)
Re: Review of Scottu19 ("Tim Fowle")
Re: 8Bit encryption code. Just try and break it. - code3.ecr (0/1) (Michael J.
Fromberger)
Re: Oriental Language Based Enryption (Mok-Kong Shen)
Re: Oriental Language Based Enryption (SCOTT19U.ZIP_GUY)
Re: 8Bit encryption code. Just try and break it. - code3.ecr (0/1) (SCOTT19U.ZIP_GUY)
Re: ECM factoring question (Medical Electronics Lab)
----------------------------------------------------------------------------
Date: Tue, 01 Jun 1999 21:54:54 -0400
From: [EMAIL PROTECTED]
Crossposted-To: talk.politics.crypto,alt.privacy
Subject: Re: The BRUCE SCHNEIER Tirade
Patrick Juola wrote:
>
> In article <[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> >Consider, the NEC case though. My information is anecdotal only, but it
> >appears to be a reasonable threat. The coporate headquarters in
> >Boxboro, Massachsetts sutains a burglary in which five machines are
> >stolen. Two of the machines contain the just-completed five-year
> >strategic plan. The company has to scrap the plan and come up with a
> >new one. The cost was some period of time in which to proeuce the new
> >plan, and the disclosure of the interests and corporate priorities that
> >coul be obtained by reading betweent he lines of the original plan; such
> >interests and priorities not being easily changed. The burglary was
> >never solved AFAIK.
> >
> >If the machines had volatile images of an OTP and persistent images of
> >the encrypted information, the act of stealing the machines would have
> >wiped the keys due to lack of power. The information would have been
> >safe. An inadvertent power outage long enough to deplete any backup
> >power would be recoverable because the key could be retrieved from an
> >offsite vault.
>
> On the other hand, they could instead simply have volatile images of
> the actual data and an offsite backup.
Not quite the same. The key is static and an offsite backup of it is a
perfect image. The data is variable and an offsite backup of it is
stale.
Assume two kinds of iterruptions: operational glitches and hostile
actions. With volatile data both kinds of interruption cost you the
transactions made since the last backup. With a volatile key the
operational interruptions cost you only the time to restore the key from
offsite backup. The recent transation data is safe.
One principle we should maintain is that the security applied to
high-value information should not materially decrease _our_ access to
the information. Volatile data is not acceptable in many cases.
The technical term for this is fail-safe. Volatile data isn't.
------------------------------
From: "Gus James" <[EMAIL PROTECTED]>
Subject: New Computer & Printer for Dave Scott
Date: Wed, 02 Jun 1999 16:06:11 GMT
Would anyone in this newsgroup be willing to donate a Pentium-class 300Mhz
computer and an inkjet printer to David A. Scott? I believe that if he was
not hampered by the primitive hardware he works on, he could perhaps improve
the legibility of his code. It would certainly inspire him to make the next
leap forward, and perhaps produce something that could be analyzed by the
likes of Schneier, Ritter, Onions, Redburn, Shen, Olson, Savard, and even the
17 year old Tom St. Denis, etc...
You know, he could be the next Ron Rivest. Six hundred dollars is not too
much to spend on the future of cryptography.
Gus James
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: comp.sys.cbm
Subject: Re: random numbers in ml
Date: Wed, 02 Jun 1999 16:10:56 GMT
[EMAIL PROTECTED] (Matthew Montchalin) wrote, in part:
>Using the MAS-128 symbolic assembler for the C-128,
Do you mean the computer manufactured by Commodore, with the ability
to execute both 6502 instructions (with Commodore-64 compatibility)
and Z-80 instructions (running CP/M), with 128 K of RAM?
Let's see if I can make sense out of your algorithm.
In pseudocode inspired by C, it would be something like:
byte random(void)
static byte seed[5]
static byte temp1, temp2
byte i,j
i = seed[0] xor temp1
temp1 = i >> 1
i = seed[0] + temp1
seed[0] = temp1 + i <<< 1
i = seed[1] xor temp2
temp2 = i >>> 1
i = seed[1] + temp2
seed[1] = temp2 + i <<< 1
i = seed[0]
for j = 0 to 3
seed[j] = seed[j+1]
next j
seed[4] = i
return i
but if rol does a nine-bit rotate, including the carry bit, then your
actual routine would be somewhat different.
>Lines 260 through 290 were inspired by the routine that Jim Butterfield
>posted a couple months ago.
And you mean the Jim Butterfield who wrote a lot of programs for the
PET and other Commodore computers? I'm pleasantly surprised to hear he
is still active.
>The bias, regardless of seeding (assuming at least minimal
>seeding, as given above, in seeds 1 and 2), is towards bytes with an equal
>distribution of 0's and 1's, which is a good thing.
For some applications, bias is never a good thing. Quasi-random
numbers, with a more even distribution than that of random numbers
(which pseudorandom numbers strive to imitate) are a valid field of
study, but they can't just be plugged in everywhere where pseudorandom
numbers are desired.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: Giovanni Serafini <[EMAIL PROTECTED]>
Subject: One-Way hash functions
Date: Wed, 02 Jun 1999 18:32:35 +0200
Hi! I'm new here and I need to program a one-way hash function like MD5,
but with an output of only 64 bit; I know it's easy to break, but for my
needs it's good; my question: where can I find information about one-way
hash functions with 64 bit output? (eventually with C-Code).
Thanks.
Giovanni
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: block ciphers vs stream ciphers
Date: Wed, 02 Jun 1999 16:40:47 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>DJohn37050 wrote:
>> There are 2 well-studied modes of operation of a block cipher (OFB
>> and CFB) that create a stream cipher. Going in the other direction
>> is more problematic.
>
>No, it is easy to use a stream cipher in block mode, and unlike the
>converse case, no security is lost in doing so.
>
I haven't heard this before. Could you give an outline of how this is
done, or possibly a reference?
--
poncho
------------------------------
Date: Tue, 01 Jun 1999 22:04:46 -0400
From: [EMAIL PROTECTED]
Subject: Re: OTP Problems
Matthias Bruestle wrote:
>
> Mahlzeit
>
> [EMAIL PROTECTED] wrote:
> > Matthias Bruestle wrote:
> > > [EMAIL PROTECTED] wrote:
> > > > A case in point. I'm pretty impressed with the specs of the iButton
> > > > device. The current (initial) version stores about 2^10 bits in a
> > > > physical device that is reasonably easy to deal with, yet is probably
> > > > secure against anything less than "national technical means". Certainly
> > >
> > > I doubt it can withstand a skillfull student. (See papers of Kuhn&Anderson)
>
> > Can you provide a pointer to a repository containing the referenced
> > papers?
>
> About attacks on smart cards:
> http://www.cl.cam.ac.uk/~mgk25/sc99-tamper.pdf
> http://www.cl.cam.ac.uk/~mgk25/tamper.html
> http://www.cl.cam.ac.uk/~mgk25/tamper2.pdf
>
> About data retention in RAM, which is probably relevant for the iButton:
> http://www.cs.auckland.ac.nz/~pgut001/pubs/secure_del.html
>
I'm familiar with the above references. None of them have a signifigant
bearing on the design of the iButton. Look for yourself:
www.iButton.com
------------------------------
From: [EMAIL PROTECTED] (Aidan Skinner)
Subject: Re: Using symmetric encryption for hashing
Date: 2 Jun 1999 00:12:36 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 01 Jun 1999 20:58:33 GMT, SCOTT19U.ZIP_GUY
<[EMAIL PROTECTED]> wrote:
> I agree it is easy to find a set that hashes to the same thing. If this is
>important for what the hash is to be used for then you are
>correct. But if one
And this is what hashes are generally used for as far as cryptography
goes. Specifically for signing messages.
>is hashing for other reasons then this is not important. And I still think
Yes, if you just want something that isn't necessarily one-way, but
has a low collision rate then you *could* use this method, but then
why not use a hash specifically designed for this?
- Aidan
--
http://www.skinner.demon.co.uk/aidan/
Horses for courses, tac-nukes to be sure.
------------------------------
From: "Tim Fowle" <[EMAIL PROTECTED]>
Subject: Re: Review of Scottu19
Date: Wed, 02 Jun 1999 15:12:04 +0100
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote in article
<7im5qr$14am$[EMAIL PROTECTED]>...
> In article <7ilkki$932$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Thomas Pornin)
wrote:
> >According to SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]>:
>
> If your so dam nonincomperence then show me. You are making statements
> you can't back up. You just irragantly think C is hot shit and it is fine
but
> only as a tool.
Apart from the spelling and grammar Thomas has clearly stated that C is not
"hot shit", its not meant to be!
Its a standardized language that when written correctly will compile on
almost any computer, and produce the same results!
I have read getting close to several hundred articles from Scott before and
not bothered to reply but in this instance I think Thomas has a very valid
point.
Standards are there so people can be SURE of there meaning and always
interpret the correctly.
How many algorithms in common use do you know of that haven't got a
standard, portable, compliant ANSI C version available??
>
> >
> Good we need people like you protecting our secrets. You can even help
> the spin doctors save Renos ass by using your logic to prove nothing of
value
> was given to the chinese. Maybe your limited brain is incapable of
following
> logic in other than some narrow way in which you use C but other people
> might have a higher IQ and then would be capable to understanf what was
done,
What if he is using a different compiler?? one that doesn't support options
you have used in your code.
HOW is he meant to understand it? If he needs your compiler then don't
call it and ANSI C and then we are back to the first point:
How many algorithms in common use do you know of that haven't got a
standard, portable, compliant ANSI C version available??
>
> I guess your in the Hamilion crowd of being to dumb to understand if not
> spoon feed to you so you attack it with out any basis other than saying
it
> is not in a form your low IQ brain can follow so there for it is weak.
Well I
> am sure Bruce and the Crypto Gods would agree with you However they
> can't break it. Sorry you keep thinking I am God. To set the record
straight
> one more time. " I AM NOT GOD" though at one time thought about becoming
> a morman since many departments on base I use to work it was the only way
> to get a head. They even think they are going to be GODS it was an
atttactive
> lure but like I said before I am not god at kissing ass or chasing
carrots.
> (no offense inteded to mormans I may even join when that temporary band
on
> multiple marridges is lefted)
>
>
We are not trying to be spoon fed, we simply want a standard for
comparison. YOU are trying to promote your software, its up to you to make
it compatible.
If not, why are you here? why do you post? why bother???
I have yet to see a good word about you on this group and I can understand
why with this attitude. People would love it if you have the ultimate
encryption system, but the onus is on YOU to prove it and a BASIC step is
to make an implementation that is useable on different systems!
finally
IT IS UP TO YOU TO PROVE YOUR SOFTWARE!! Till that day NO-ONE will bother
testing it and it will NEVER be considered "safe"
open your eyes and grow up.. please
ttfn
Tim Fowle
------------------------------
From: Michael J. Fromberger <[EMAIL PROTECTED]>
Subject: Re: 8Bit encryption code. Just try and break it. - code3.ecr (0/1)
Date: 2 Jun 1999 13:58:55 GMT
In <[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>Michael J. Fromberger wrote:
>>
>> Cryptography is no place for secrecy ... an ironic axiom, to be sure,
>> but true.
>Do you believ thn that the United States would be better off in terms
>of communication security if the NSA/CIA/FBI/DIA/TLA published all of
>their working methods?
>I think not.
Well, you're certainly entitled to your opinion. :)
My essential point is that you cannot simply create ciphers and
protocols in a vacuum, and expect them to be strong. An organization
such as the NSA circumvents this problem slightly, by retaining a
large staff of well-trained cryptographers and cryptanalysts. This,
one could reasonably argue, gives them the ability to simulate the
analysis, testing, and review that happens in the more open academic
community -- except that it is self-contained.
The original discussion, as you recall, was about the release of
source code for cryptographic software -- not government algorithms.
If you are truly concerned with the strength and security of a piece
of software, it would be the height of folly to trust a piece of
random code whose source you weren't even allowed to analyze...not
only the encryption algorithms, but how they're employed, how keys and
data are handled and stored, and so forth.
If you have a cryptosystem that is strong even when its details are
known, then keeping it a secret will only make it MORE difficult to
break, not less. But since there is not currently any known method
for proving a cryptosystem's strength, this is a virtually pointless
theorem. Anyone who is truly concerned with security needs to be able
to see how the internals of their encryption system -- software or
hardware -- are put together.
The most common response to this is to argue: "But most people don't
have the knowledge necessary to review all the source code themselves,
so how could this help them anyway?" And sure, that's true.
But if the details are available to the cryptographic community at
large, someone who does not have the requisite technical knowledge can
at least take advantage of the expertise of well-respected
cryptographers and cryptanalysts. If the details are obscured, you
have to trust the person who wrote the code, when she assures you it's
secure. If we could all truly trust each other, we wouldn't NEED
cryptography.
And so, I continue to assert that there should be no black boxes in
cryptography.
Cheers,
-M
--
Michael J. Fromberger Software Engineer, Thayer School of Engineering
sting <at> linguist.dartmouth.edu http://www.dartmouth.edu/~sting/
Mp/8iFe3es7ycyzY8saI8mJI+TMcPxaY+4JFcOf+ximcYBCdQ87W0Sla7NDY9JGVWRe5dz8/
Remove clothing if you wish to reply to this message via e-mail.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Oriental Language Based Enryption
Date: Wed, 02 Jun 1999 17:08:47 +0200
Patrick Juola wrote:
> Who does the translation? You're more or less making the assumption
> that the translator makes no changes at all to the phrasing or
> informativeness. In many cases this isn't even *possible*; there's
> no word in Japanese for 'brother', for instance. Older brother, yes.
> Younger brother, yes. But there's no word for 'brother of unspecified
> age.' Similar examples abound of lexical holes, as well as various
> syntactic holes -- it's very difficult to write a sentence without an
> (explicit) agent in English, very easy in Italian, which leads to lots
> of overspecification of agency in the translation process. And so forth.
Who does the translation is entirely open. It could be the writer
of the message himself (namely if he has an official language and
wants to take advantage of another language in encryption -- taking
for granted that there being such advantage); normally it is a trained
translator (a person payed for his work) in the situation appropriate
to the issue here. Why do you think that such translations are
unconditionlly bad? Documents presented to the court and international
agreements, contracts are often translated. Sure, if you have in
one case a person good in literature translate something written by
one having only little education and in another case the other way
round, you would very probably see the impact of the quality of the
translator. Note, however, that in the first case the quality of the
document very likely improves. It is well known that certain special
words in every language are difficult to be simply (i.e. 'directly',
one for one) translated into other languages. Most bad words (curses)
are of that category. As I said, however, we are considering here only
very normal everyday messages for conveying certain news, informations
and certainly nothing like poems, etc.
I know too little about Japanese to verify what you said about
'brother', but perhaps I may tell you that in Chinese (from which
Japanese adopt quite a number of 'words') a 'word' in the proper
sense can consist of more than one ideographs (somewhat like in German
where one can joint two nouns without separating space to form one
compound). Your statement could apply to Chinese if you were to
idendify one 'word' always with only one ideograph, which you shouldn't.
In fact 'brother' (general sense) in Chinese consists of two ideographs
which can also be used singly (as words), the first meaning 'elder
brother' the second meaning 'younger brother'. Thus I suspect that
your claim could be the result of such misinterpretation. There are
fine points peculiar to each language. For example, if I say in German
that I am going to meet my friend (Freund) then it is clear that's a
boy not a girl friend. In other languages 'friend' can be ambigious
in this respect. But I really wonder such stuffs, however interesting
they might be to linguists, are so extremely important to the issue at
hand, namely employing another language as an intermediary in the
chain of processes to transmit some confidential practical
(non-literary, mundane in style) informations from one place to the
other.
>
> You also have to distinguish between the case where the original message
> is written in one language and *translated*, probably by a second person,
> into the second language and the case where you simply write in the 'target'
> language to begin with. Although I'm delighted to hear that you're equally
> fluent in several languages, I submit that *for this reason* you're not a
> good person to look at the informativeness question when you're translating
> your own work -- you're not translating, but rewriting.
I repeated said that it is assumed that the translator is a sufficiently
good one (in his profession/position) for the purpose being discussed.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Oriental Language Based Enryption
Date: Wed, 02 Jun 1999 17:43:09 GMT
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Patrick Juola wrote:
>
>> Who does the translation? You're more or less making the assumption
>> that the translator makes no changes at all to the phrasing or
>> informativeness. In many cases this isn't even *possible*; there's
>> no word in Japanese for 'brother', for instance. Older brother, yes.
>> Younger brother, yes. But there's no word for 'brother of unspecified
>> age.' Similar examples abound of lexical holes, as well as various
>> syntactic holes -- it's very difficult to write a sentence without an
>> (explicit) agent in English, very easy in Italian, which leads to lots
>> of overspecification of agency in the translation process. And so forth.
>
>Who does the translation is entirely open. It could be the writer
>of the message himself (namely if he has an official language and
>wants to take advantage of another language in encryption -- taking
>for granted that there being such advantage); normally it is a trained
>translator (a person payed for his work) in the situation appropriate
>to the issue here. Why do you think that such translations are
>unconditionlly bad? Documents presented to the court and international
>agreements, contracts are often translated. Sure, if you have in
>one case a person good in literature translate something written by
>one having only little education and in another case the other way
>round, you would very probably see the impact of the quality of the
>translator. Note, however, that in the first case the quality of the
>document very likely improves. It is well known that certain special
>words in every language are difficult to be simply (i.e. 'directly',
>one for one) translated into other languages. Most bad words (curses)
>are of that category. As I said, however, we are considering here only
>very normal everyday messages for conveying certain news, informations
>and certainly nothing like poems, etc.
>
>I know too little about Japanese to verify what you said about
>'brother', but perhaps I may tell you that in Chinese (from which
>Japanese adopt quite a number of 'words') a 'word' in the proper
>sense can consist of more than one ideographs (somewhat like in German
>where one can joint two nouns without separating space to form one
>compound). Your statement could apply to Chinese if you were to
>idendify one 'word' always with only one ideograph, which you shouldn't.
>In fact 'brother' (general sense) in Chinese consists of two ideographs
>which can also be used singly (as words), the first meaning 'elder
>brother' the second meaning 'younger brother'. Thus I suspect that
>your claim could be the result of such misinterpretation. There are
>fine points peculiar to each language. For example, if I say in German
>that I am going to meet my friend (Freund) then it is clear that's a
>boy not a girl friend. In other languages 'friend' can be ambigious
>in this respect. But I really wonder such stuffs, however interesting
>they might be to linguists, are so extremely important to the issue at
>hand, namely employing another language as an intermediary in the
>chain of processes to transmit some confidential practical
>(non-literary, mundane in style) informations from one place to the
>other.
>
>>
>> You also have to distinguish between the case where the original message
>> is written in one language and *translated*, probably by a second person,
>> into the second language and the case where you simply write in the 'target'
>> language to begin with. Although I'm delighted to hear that you're equally
>> fluent in several languages, I submit that *for this reason* you're not a
>> good person to look at the informativeness question when you're translating
>> your own work -- you're not translating, but rewriting.
>
>I repeated said that it is assumed that the translator is a sufficiently
>good one (in his profession/position) for the purpose being discussed.
>
>M. K. Shen
It would be fun to play a game like kids use to play but with lagnuges.
get ten people in a circle let A write in english a message to B and let
B pass only the note he translated. Do this with several language pairs
and finally end up back at A in english. I wonder if the final document has
any resemblance to the original english message and I wonder if it is longer
in length.
I am sure this as been done but not aware of the results.
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: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: 8Bit encryption code. Just try and break it. - code3.ecr (0/1)
Date: Wed, 02 Jun 1999 18:03:40 GMT
In article <7j3dav$73p$[EMAIL PROTECTED]>, Michael J. Fromberger
<[EMAIL PROTECTED]> wrote:
>In <[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>
>>Michael J. Fromberger wrote:
>>>
>>> Cryptography is no place for secrecy ... an ironic axiom, to be sure,
>>> but true.
>
>>Do you believ thn that the United States would be better off in terms
>>of communication security if the NSA/CIA/FBI/DIA/TLA published all of
>>their working methods?
>
>>I think not.
>
>Well, you're certainly entitled to your opinion. :)
>
>My essential point is that you cannot simply create ciphers and
>protocols in a vacuum, and expect them to be strong. An organization
>such as the NSA circumvents this problem slightly, by retaining a
>large staff of well-trained cryptographers and cryptanalysts. This,
>one could reasonably argue, gives them the ability to simulate the
>analysis, testing, and review that happens in the more open academic
>community -- except that it is self-contained.
>
>The original discussion, as you recall, was about the release of
>source code for cryptographic software -- not government algorithms.
>If you are truly concerned with the strength and security of a piece
>of software, it would be the height of folly to trust a piece of
>random code whose source you weren't even allowed to analyze...not
>only the encryption algorithms, but how they're employed, how keys and
>data are handled and stored, and so forth.
>
>If you have a cryptosystem that is strong even when its details are
>known, then keeping it a secret will only make it MORE difficult to
>break, not less. But since there is not currently any known method
>for proving a cryptosystem's strength, this is a virtually pointless
>theorem. Anyone who is truly concerned with security needs to be able
>to see how the internals of their encryption system -- software or
>hardware -- are put together.
>
>The most common response to this is to argue: "But most people don't
>have the knowledge necessary to review all the source code themselves,
>so how could this help them anyway?" And sure, that's true.
>
>But if the details are available to the cryptographic community at
>large, someone who does not have the requisite technical knowledge can
>at least take advantage of the expertise of well-respected
>cryptographers and cryptanalysts. If the details are obscured, you
>have to trust the person who wrote the code, when she assures you it's
>secure. If we could all truly trust each other, we wouldn't NEED
>cryptography.
>
Nice rambling argument. But my problem is I have a method where all
the source code is present and I am under the impression from some of
the comments that well-respected cryptographers and cryptoanalysts lack
the ability to follow the code. Even though with the highly commented source
code there is a PC executable that any one even a crypto person could run
>And so, I continue to assert that there should be no black boxes in
>cryptography.
>
>Cheers,
>-M
>
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: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: ECM factoring question
Date: Wed, 02 Jun 1999 12:20:52 -0500
Logic wrote:
>
> When doing elliptic curve factorization, we choose an initial point P on the
> curve. We then calculate the "multiples" of P recursively by performing the
> group operation on it with a sequence of primes under the chosen bound B.
> As I understand it, in practice, this sequence is the sorted list of prime
> powers less than B, where the prime itself replaces each of its powers in
> the list, e.g. 2,3,2,5,7,2,3,11 and so on.
So you calculate p1 = 2P, p2 = 3p1, p3 = 2p2, ...
in that order?
> In practice, we rarely find a factor in one trial of ECM (unfortunately).
> Normally we are forced to calculate the multiples of P through the entire
> sequence. Suppose we instead calculated the multiples of P by each prime
> until we exceeded B, e.g. 2,2, ... ,2^x<=B, 3,3, ... , 3^y<=B, ...
> Under the assumption that most trials of ECM yield no factors, could we not
> gain a slight increase in speed by somehow taking advantage of the fact that
> we are calculating the same multiple several times (at least for the smaller
> primes)? Would this make the code simpler as well?
>
> I suppose there are times we would not want to do this, in which case we could
> use the traditional sequence. But in the right circumstances, could this
> sequence be faster/simpler?
Do you know the order of P (=k say)? If so, you can compute x^m mod k
for all the m's you need much faster than computing x^m*P. To make this
go fast, you can precompute 2^j*P for all j<ceil(log_2(k)), then
just sum the jth entry for each bit set in x^m mod k.
This would allow you to trade off space for time, you store lots of
2^j*P, then just do elliptic curve sums from then on. Do your x^m mod k
to find out which bits are set using integer math, not EC math.
Should speed things up quite a bit.
Patience, persistence, truth,
Dr. mike
------------------------------
** 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
******************************
