Cryptography-Digest Digest #843, Volume #9 Wed, 7 Jul 99 20:13:03 EDT
Contents:
Re: optimizations (for feedback PRNGs...) (Terje Mathisen)
Help With Key Algorithm For Software Unlock ("Steve")
Re: Quantum Computers ("rosi")
Re: Properties of Chain Addition? ([EMAIL PROTECTED])
Re: Summary of 2 threads on legal ways of exporting strong crypto ([EMAIL PROTECTED])
Re: Can Anyone Help Me Crack A Simple Code? ([EMAIL PROTECTED])
Re: optimizations (for feedback PRNGs...) ([EMAIL PROTECTED])
Re: Properties of Chain Addition? (John Savard)
Re: Help With Key Algorithm For Software Unlock (William Tanksley)
Re: I don't trust my sysadmin (Jerry Coffin)
Re: I don't trust my sysadmin ([EMAIL PROTECTED])
Impossible to decrypt files encrypted with attached program - encrypt.exe [0/1] (Bob)
Re: I don't trust my sysadmin (Scott Gifford)
Re: optimizations (for feedback PRNGs...) ([EMAIL PROTECTED])
Re: optimizations (for feedback PRNGs...) ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Subject: Re: optimizations (for feedback PRNGs...)
Date: Wed, 07 Jul 1999 23:57:14 +0200
[EMAIL PROTECTED] wrote:
>
> I was thinking about ways to optimize feedback Prngs such as parallel
> LFSRS or additive generators.. Basically the slow part is updating the
> counters (which must wrap at arbitrary points such as 55 and 52...).
That's not really a problem, see below.
>
> What I thought of was unrolling the PRNG completely so it will produce
> 55 or 52 (whatever the length is) outputs per call. This will unroll
> the loop and use immediate indexing instead of using counters. It
> would need instructions like
>
> ; ES:DI points to the buf to hold the PRNG output...
>
> ; state[y1]
> mov al,[BX + OFFSET state + 54]
This can be handled at very nearly the same speed with a simple unroll
by 4 or 8 loop, followed with a single iteration to handle the
(possibly) wrapping case.
Do a test up front to determine the number of non-wrapping operations,
and if >= unroll length, use the straigh-forward block.
> Some problems is that although this only requires four instructions
> (fairly efficient when compared to the index mode) it doesn't pair at
> all. It will require about 5 cycles per clocking (486/586 type
> computer). This is better when compared to about 15 cycles (using
> index mode), it also doesn't require branching. In my code (the C++
> code I posted) I used
I never found that code using DejaNews, if you'll email it to me I'll
take a look.
> x = x < (N-1) ? ++x : 0;
>
> Where N is the length of the register. This is really efficient on
> microcontrollers compared to
>
> x = (x + 1) % N
>
> Because it does not require a modulus operation. It is not too super
> on superscalar cpus as it requires a branch...
You can replace an operation like this by either jumping into am
unrolled block of non-wrapping code, usually you'll need two calls for
each side of the wrap point.
Much simpler is to just replace the increment operation with either a
table lookup, or with code like this:
x++;
int32 temp = (int32) x - N; // Will be negative unless no wrapping
needed!
temp >>= 31; // Turn temp into an all 1 or all 0 mask
x &= temp; // Wraps values >= N into 0
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
From: "Steve" <[EMAIL PROTECTED]>
Subject: Help With Key Algorithm For Software Unlock
Date: Wed, 7 Jul 1999 18:36:57 -0400
I've got the Schneier book "Applied Cryptography" and I'm trying to devise a
method for preventing unauthorized copies of my software to be made. Once
the user hits a usage metric, the software will stop until the user
registers. Upon registry the user will get a key. The key will be somehow
verified by the program and the user will be free to continue using it. If
the user moves the software to another box then it will immediately notice
that the key is not present in the windows registry and stop working.
I am thinking of using some form of signature algorithm for this but my
question is whether there is a standard method for doing this sort of thing.
If it is in "Applied Cryptography" then I'd love to know where.
Steve
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
Date: Mon, 5 Jul 1999 18:59:28 -0400
Beauty! Thanks
--- (My Signature)
Anti-Spam wrote in message <[EMAIL PROTECTED]>...
>Greg Ofiesh wrote:
>>
>> > If we use cryptosystems "orthogonal" or independent of those
>> > QC-acceptable algorithms attacks, then our cryptosystems are immune.
>> > QCs pose no threat if we are careful.
>>
>> So, would you say that either DLP or ECDLP problems are immune from
>> QCs? How about the idea that QCs once developed sufficiently can
>> perform massive parallel computations? Then does any algorithm appear
>> immune to a QC? Just want to get your feel on this.
>>
>> Sent via Deja.com http://www.deja.com/
>> Share what you know. Learn what you don't.
>
>As a follow-up to my original post, here's a snippet that explains well
>the situation we face with QC cryptanalysis, from "Explorations in
>Quantum Computing":
>
>"Quantum parallelism allows you to compute an exponential number of
>functional evaluations in the time it takes to do just one functional
>evaluation classically. Unfortunately, the laws of quantum mechanics
>make it impossible to extract more than one of these answers explicity.
>The problem is that although you can indeed calculate all the function
>values from the tape [book is making a comparison to a classical Turing
>Machine], you will only obtain one of the many outputs. Worst still, in
>the process, the information about all the other inputs is lost
>irretrievably. So the net effect is that you are no better off than had
>you used a classical Turing Machine. So, far a functional evaluation
>goes, the quantum computer is no better than a classical computer."
>
>Why then use QCs? QCs CAN calculate "certain joint properties of all of
>the answers without having to reveal any one answer explictly." The
>book gives an example.
>
>"Suppose there is a function f that can receive one of two inputs, 0 and
>1, and that we are interested in computing the XOR of both function
>values, that is f(0) XOR f(1). The result could be a decision as to
>whether to make some particular stock investment tomorrow based on
>today's closing prices. Now suppose that, classically, it takes 24 hours
>to evaluate each f. Thus if we are stuck with a single classical
>computer, we would never be able to compute the XOR operation in time to
>make the investment the next day. On the other hand, using quantum
>parallelism, Deutsch showed that half the time we would get the
>guaranteed correct value of f(0) XOR f(1). Thus the quantum computer
>would give us useful advice half the time and never give us wrong
>advice."
>
>(The Deutch reference is "Deutsch D. "Quantum Theory, the Church-Turing
>Principle, and the Universal Quantum Computer," Proceedings Royal
>Society London, Vol. A400 (1985) pp.97-117.)
>
>Note we are getting information about a joint property of f(0) and f(1),
>but we learn nothing about what f(0) is aside from f(1), or what f(1) is
>aside from f(0). Let f(0) XOR f(1) = X. Suppose we ran this
>hypothetical QC on this hypothetical problem and the answer is X = 1.
>Well, f(0) = 1 and f(1) = 0 results in X = 1. So does f(1) = 0 and f(1)
>= 1. We also know that they both cannot be zero and they both cannot be
>one. BUT, we cannot say for sure what the value of the functional
>evalution with 0 as input was, and we cannot say what the functional
>evaluation with 1 as input was. We can only know things about a joint
>property of these two functional evaluations.
>
>Shor's algorithm for factoring integers relies on this feature. We want
>to factor an integer n. The algorithm applies the same functional
>evaluation, f(a) = ( x exp a ) mod n, where x is a random integer
>coprime to n, to a large number of integers K less than n. It turns out
>that f(0), f(1), f(2),....f(K) is periodic. As we evalute a large
>number of arguments to f(a), we find that the results of f(a) begin to
>repeat with a period r. Well, the resulting end state of the quantum
>calculation (due to quantum interference) is a joint property of all of
>those simultaneous functional evaluations, and is an integer multiple of
>the period r. All of those individual evaluations of the f(a) function
>are related by this common period r, and that is the joint property of
>the myriad evalutions that comes out of the interference of all of the
>superimposed quantum states in the QC mapped to represent the f(a).
>
>If we can't find a way to answer our question in the form of a joint
>property of numerous valuations of a function f, then the QC cannot
>calculate and answer our question.
>
>If we can't find a way to map the result of a cryptanalysis of a
>ciphertext in the form of a joint property of numerous valuations of the
>cryptanalysis function crypt(ciphertext), then the QC cannot calculate
>the answer to the cryptanalysis question.
>
>There's the research area.
>
>[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.math
Subject: Re: Properties of Chain Addition?
Date: Wed, 07 Jul 1999 22:32:07 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> The VIC cipher used by Russian spies involved a technique for
> generating pseudorandom numbers known as "chain addition".
You mean lag fibonacci generators? They are not secure on their own
though.
> One starts with a number of a certain number of digits...
>
> such as 8492
With taps on 1 and 4 I get this sequence...
84920435592721302 etc... (mod 10 of course)
If you want to see some uses why not check out my mini C++ PRNG lib at
http://mypage.goplay.com/tomstdenis/prng.html
I have 6 generators there (5 of which use this type of PRNG). It's not
hard to make them secure as well...
I would be interested to see what you come up with. Is there anything
on your site to peek at?
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
Date: Wed, 07 Jul 1999 07:04:19 -0400
From: [EMAIL PROTECTED]
Crossposted-To: talk.politics.crypto
Subject: Re: Summary of 2 threads on legal ways of exporting strong crypto
Mok-Kong Shen wrote:
>
> [EMAIL PROTECTED] wrote:
> >
>
> > I think there is a case to be made for translated source code. By
> > translated I'm distinguishing encodings in pixels, capitalization, etc.,
> > i.e., syntactic mangling, from semantic transforms. The Bernstein case
> > is interesting because he claimed the source code itself was a form of
> > protected speech. We can come at it from a different direction and
> > reach the same haven: protected speech.
> >
> > Clearly it is possible to sanitize a module of source code into
> > specifications so that another writer, with no access to the original
> > code, can create new software (as opposed to *re*creating the original
> > software) with the same capabilities.
> >
> > Somewhere between sanitization as used in BIOS development and simple
> > encodings lie semantic translations. The fact that a semantic
> > translation of "C" can be mechanized should not weaken the fact that
> > translated source code is english text, and thus protected speech.
>
> Certainly you are VERY safe if you take the pain to describe your
> algorithm in plain English sentences. But our goal is to get as
> much convenience as possible for the author AND the readers who have
> to do the implementation.
>
> Very detailed descriptions which one could translate one-to-one
> to codes have already been done. If I don't err, RSA has recently
> published a RFC on BSAFE just in that way. Someone conjectured
> that there RSA has a mechanism for automatically converting that to
> C and reciprocally.
Exactly the point. The fact that true translation can be mechanized
does not detract tahat a true translation is an expression of ideas, and
thus protected speech.
>
> M. K. Shen
------------------------------
Date: Wed, 07 Jul 1999 07:06:55 -0400
From: [EMAIL PROTECTED]
Subject: Re: Can Anyone Help Me Crack A Simple Code?
Roger Carbol wrote:
>
> mercury <[EMAIL PROTECTED]> wrote:
>
> >So the designers of the Black Boxes come up with
> >a system. They make the Black Boxes dependant
> >on keys. In order to make a Black Box work, you
> >must buy a key from the Black Box company. When
> >you buy a key, you specify what color light the
> >Black Box has.
>
> How many different light colours are known?
An arbitrarily large number. How finely can you divide electromagnetic
frequencies? An infinite number if you accept colors like heat,
microwave, radio, x-ray, gamma.
The human eye can distinguish around 100,000 colors of visible light.
>
> >The key is only good for one specific color light
>
> Do you *really* know this, or is this merely what
> the BB company has told you? Have you tested
> off-colour keys on other boxes?
>
> >The key is date coded, so it must be used within
> > a certain amount of time.
>
> How much time?
>
> Is it possible to compromise the internal clock?
> That could simply your situation considerably.
>
> >The key will only make the light come on a certain
> > number of times. After that, the Black Box
> > Logs that the key has been used and will not
> > accept the same key again.
>
> How many times? Can this be compromised by
> removing internal power sources?
>
> >So companies must buy a certain number of keys
> >based on how much they plan on using the black box
> >within the amount of time the keys are good for.
>
> Couldn't they buy them on an ad-hoc basis, as needed?
> How long does it take the BB company to generate a
> key?
>
> >So it is nearly impossible (with the equipment I
> >have) to enter the codes any other way besides by
> >hand with the key pad. It is not possible to try
> >a large number of codes.
>
> I believe that there are robotic applications built
> specifically for this sort of attack, but they may
> be beyond your means.
>
> How long does it take the box to return a value once
> the key has been entered? Very fine analysis of the
> timing in response to various keys might be a mode of
> attack.
>
> >The light bulbs have a built-in microchip. This
> >chip configures the Black Box for whichever light
> >bulb is being used. With the exception of this
> >chip, the electronics are identical in all Black
> >Boxes. (I MAY be able to retrieve the information
> >off of this chip. I may have answered the question
> >of where the algorithm is right here. I'll look
> >into this further.) The lightbulbs are only
> >installed or changed at the Black Box company.
>
> It's more likely, in my opinion, that the bulb contains
> some information which is used as a partial key (in
> addition to the date information, apparently.)
>
> Good luck.
>
> .. Roger Carbol .. [EMAIL PROTECTED]
------------------------------
Date: Wed, 07 Jul 1999 07:00:16 -0400
From: [EMAIL PROTECTED]
Subject: Re: optimizations (for feedback PRNGs...)
There is no reason the size of the data storage must match the offset
between feeback points. So, using the 521/32 LFSR you can store 1024
words and update indexes without division or branching.
#define BUFFSIZE 1024 /* power of two */
int buffer[ BUFFSIZE ];
int tap1 = 521
, tap2 = 32
, fill = 0
;
/* Update a word of the LFSR
*/
buffer[ fill++ ] = buffer[ tap1++ ] ^ buffer[ tap2++ ];
fill &= BUFFSIZE-1; /* wrap buffer indexes */
tap1 &= BUFFSIZE-1;
tap2 &= BUFFSIZE-1;
Note: this is software engineering, not cryptography.
[EMAIL PROTECTED] wrote:
>
> I was thinking about ways to optimize feedback Prngs such as parallel
> LFSRS or additive generators.. Basically the slow part is updating the
> counters (which must wrap at arbitrary points such as 55 and 52...).
>
> What I thought of was unrolling the PRNG completely so it will produce
> 55 or 52 (whatever the length is) outputs per call. This will unroll
> the loop and use immediate indexing instead of using counters. It
> would need instructions like
>
> ; ES:DI points to the buf to hold the PRNG output...
>
> ; state[y1]
> mov al,[BX + OFFSET state + 54]
>
> ; state[x1] +=
> add [BX + OFFSET state + 18],AL
>
> ; get result
> MOV AL,[BX + OFFSET state + 18]
> STOSB
>
> ; repeat 54 more times (i.e use a macro for this :)
>
> Some problems is that although this only requires four instructions
> (fairly efficient when compared to the index mode) it doesn't pair at
> all. It will require about 5 cycles per clocking (486/586 type
> computer). This is better when compared to about 15 cycles (using
> index mode), it also doesn't require branching. In my code (the C++
> code I posted) I used
>
> x = x < (N-1) ? ++x : 0;
>
> Where N is the length of the register. This is really efficient on
> microcontrollers compared to
>
> x = (x + 1) % N
>
> Because it does not require a modulus operation. It is not too super
> on superscalar cpus as it requires a branch...
>
> Does anybody know more efficient means? Maybe unroll two PRNGs into
> the same code (chance for pairing)? But if they are not the same
> length the last outputs would slow down. It would have to be faster on
> average (i.e for large arrays). Another problem if they are not the
> same size is that if you run out of one PRNG first what todo? Discard
> values from the longer one?
>
> Any help?
>
> Thanks,
> Tom
> --
> PGP key is at:
> 'http://mypage.goplay.com/tomstdenis/key.pgp'.
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.math
Subject: Re: Properties of Chain Addition?
Date: Wed, 07 Jul 1999 22:50:35 GMT
[EMAIL PROTECTED] wrote, in part:
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (John Savard) wrote:
>> The VIC cipher used by Russian spies involved a technique for
>> generating pseudorandom numbers known as "chain addition".
>You mean lag fibonacci generators? They are not secure on their own
>though.
I'm not surprised; LFSRs aren't secure, and chain addition is just a
simple special case of that. But key schedules are often not secure
stream ciphers, and I'm using a MacLaren-Marsaglia construct to
further scramble the output in my block cipher.
There isn't too much on my site about pseudo-random numbers; there's a
bit on computer stream ciphers, but it mostly just notes some of the
techniques used to make LFSR-based devices secure, like using a
nonlinear function of several stages or several shift register
outputs, clocking them irregularly, and so on.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (William Tanksley)
Subject: Re: Help With Key Algorithm For Software Unlock
Reply-To: [EMAIL PROTECTED]
Date: Wed, 07 Jul 1999 22:55:03 GMT
On Wed, 7 Jul 1999 18:36:57 -0400, Steve wrote:
>I've got the Schneier book "Applied Cryptography" and I'm trying to devise a
>method for preventing unauthorized copies of my software to be made. Once
>the user hits a usage metric, the software will stop until the user
>registers. Upon registry the user will get a key. The key will be somehow
>verified by the program and the user will be free to continue using it. If
>the user moves the software to another box then it will immediately notice
>that the key is not present in the windows registry and stop working.
>I am thinking of using some form of signature algorithm for this but my
>question is whether there is a standard method for doing this sort of thing.
>If it is in "Applied Cryptography" then I'd love to know where.
There are several methods for doing this, but they're all trivial to break
(although they can take a lot of effort to figure out).
Please rethink this. You'll not be stopping the warez d00dz, and you will
be sending the message to your potential customers: "I don't trust you."
Your lack of trust will result in inconvenience to them.
I can't think of an appropriate occasion for this type of copy protection.
However, if you really think you've got one, there are ways. You'll want
to rely on hashes (like SHA or MD5), not encryption; read up on key
transfer as well. Use your knowledge of the registry (and other areas) to
gather the most information about the computer, and make the key depend on
that. Make keys only activate the software when used between certain
dates -- and search the file system to try to verify that the user is not
setting the clock back.
Finally, use your magic to make the crackers unable to write a patch which
simply jumps past all of those checks.
Or, alternately, make being your customer worth the money. Provide
support in the form of a listening ear, upgrades, and bugfixes. (You're
not expected to provide free tech support.) Even if your app isn't the
best, and even though people could get your app from warez sites, they'll
tend to buy it from you, because software writing is a service, and most
people shop for it that way, even if they're not aware of it.
>Steve
--
-William "Billy" Tanksley
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: I don't trust my sysadmin
Date: Wed, 7 Jul 1999 16:37:16 -0600
In article <7m0a8l$c1f$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> No, I'm simply distinguishing between B1 and the higher levels
> (B2-3); I do not believe that it's possible to retrofit *any* OS
> to achieve B2 security; according to the guidelines, B2 (and better)
> security has to be planned into the design from day 1. Simply
> taking code and putting in "a million bazillion ifdefs" -- even
> if they all worked -- doesn't fulfil the B2 guidelines. And
> part of the reason that the B2 guidelines are written that way is
> because the folks at the DoD &c. don't believe that a million
> bazillion ifdefs are an acceptable way to write secure, reliable
> code.
Trusted Xenix, from Trusted Information Systems, Inc., has been
certified at the B2 level. Data General has submitted a version of
DG/UX for evaluation at B2, but it's not presently on the list as
having been certified.
Quite a few UNIX systems have been certified at the B1 level,
including versions of Ultrix, HP/UX and Irix.
Re-checking the list today, I note that there is no longer any OS
listed at the A1 level -- it's almost embarrassing to note that the
one I mentioned was certified in 1984. The closest thing to a newer
version of the same system is from Wang, which has been evaluated at
B3.
Note that there's not necessarily any difference between B3 and A1 WRT
the security that's provided -- A1 requires verified design, which
means the OS design has to be done in a design verification language.
IIRC, the NSA has hinted (at least at times) that they'd like to add a
level above A, in which not only the design, but the implementation
would be verified as well. That might be a bit tough to manage
though: there's one Scheme system that's undergone formal
verification. TTBOMK, there's no such thing as a verified
implementation of anything like C, C++, Ada, or most of the other
languages in which you'd typically think of implementing an OS.
Anybody who wants to see what's been evaluated at what levels may want
to cruise to:
http://www.radium.ncsc.mil/tpep/epl/epl-by-class.html
------------------------------
Date: Wed, 07 Jul 1999 06:52:23 -0400
From: [EMAIL PROTECTED]
Subject: Re: I don't trust my sysadmin
Jerry Coffin wrote:
>
> In article <7lvjh7$bed$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> says...
>
> [ ... ]
>
> > You can buy more secure systems; I've never heard of an A1 system (the
> > highest level),
>
> I haven't checked in quite a while, but the last time I looked, there
> was only one OS on the A1 evaluated products list.
By this do you mean a product whose candidacy for A! certification has
been evaluated (presumably failing), or a product whose evaluation
affirmed an A1 rating?
Details would be nice.
>
> > but B2 and B3 *are* available. They just don't run
> > Unix. So you can get real, usable, security at the expense of an
> > operating system that no one knows and that's incompatible with everything.
>
> Actually, there is (or at least at one time was) one UNIX-based system
> that was on the B2 evaluated products list. As I understand it, they
> had to do quite a bit of work on the kernel to achieve that though --
> to the point that it's open to argument whether it was really UNIX
> anymore or not.
>
> There's one more point that hasn't been mentioned: according to the
> Orange book, an OS (or other product) is NOT rated for a particular
> security level -- only a particular installation can be rated for a
> security level. They do maintain a list of products that have been
> used in installations that have been rated for particular levels of
> security; if you want a secure installation, it's generally much
> easier to do if you start with products already on the list, but it's
> no guarantee by itself.
------------------------------
From: [EMAIL PROTECTED] (Bob)
Subject: Impossible to decrypt files encrypted with attached program - encrypt.exe
[0/1]
Date: Wed, 7 Jul 1999 19:03:20 -0500
Can anyone decrypt files encrypted with the attached program?
------------------------------
Subject: Re: I don't trust my sysadmin
From: Scott Gifford <[EMAIL PROTECTED]>
Date: 07 Jul 1999 20:13:53 -0400
[EMAIL PROTECTED] (Vernon Schryver) writes:
> In article <[EMAIL PROTECTED]>,
> Scott Gifford <[EMAIL PROTECTED]> wrote:
>
> > ...
> > We would handle this with our database by creating a procedure that
> >gathers only the data needed, then creating a user that is only
> >allowed to run that query. Then you can store that username and
> >password on the system, and if the sysadmin takes advantage of it, all
> >he can do is run the same query.. ....
>
> That assumes the sysadmin does not have the UNIX root password, NT system
> administration privileges or equivalent, or does not have the skill or
> interest to use them. If you can make such a strong assumption, why bother
> distrusting the sysadmin? In practice, trustworthy by reason of ignorance
> or incompetence about as good as trustworthy gets.
Actually, it assumes that the sysadmin for the system the query is
running from is not the same as the sysadmin for the system that
contains the database. The wording of the initial question implied to
me that this was the case. If this assumption is incorrect, then
you're right, it's hopeless.
======ScottG.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: optimizations (for feedback PRNGs...)
Date: Thu, 08 Jul 1999 00:04:18 GMT
In article <[EMAIL PROTECTED]>,
Terje Mathisen <[EMAIL PROTECTED]> wrote:
> This can be handled at very nearly the same speed with a simple unroll
> by 4 or 8 loop, followed with a single iteration to handle the
> (possibly) wrapping case.
But will deciding which routine to use be faster then just unrolling it
completely?
> Much simpler is to just replace the increment operation with either a
> table lookup, or with code like this:
>
> x++;
> int32 temp = (int32) x - N; // Will be negative unless no wrapping
> needed!
> temp >>= 31; // Turn temp into an all 1 or all 0 mask
> x &= temp; // Wraps values >= N into 0
>
That could work nicely.
The code is at
http://mypage.goplay.com/tomstdenis/prng.html
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: optimizations (for feedback PRNGs...)
Date: Thu, 08 Jul 1999 00:04:22 GMT
In article <[EMAIL PROTECTED]>,
Terje Mathisen <[EMAIL PROTECTED]> wrote:
> This can be handled at very nearly the same speed with a simple unroll
> by 4 or 8 loop, followed with a single iteration to handle the
> (possibly) wrapping case.
But will deciding which routine to use be faster then just unrolling it
completely?
> Much simpler is to just replace the increment operation with either a
> table lookup, or with code like this:
>
> x++;
> int32 temp = (int32) x - N; // Will be negative unless no wrapping
> needed!
> temp >>= 31; // Turn temp into an all 1 or all 0 mask
> x &= temp; // Wraps values >= N into 0
>
That could work nicely.
The code is at
http://mypage.goplay.com/tomstdenis/prng.html
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
** 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
******************************
