Cryptography-Digest Digest #897, Volume #10 Thu, 13 Jan 00 15:13:01 EST
Contents:
Re: Random numbers generator (Tom St Denis)
Re: Questions about message digest functions (Tim Tyler)
Re: Truly random bistream (Tim Tyler)
Re: Why is EDI dead? Is S/MIME 'safe'? Who and why? ("Richard A. Schulman")
Re: Cryptography in Tom Clancy (Glenn Larsson)
Need some design suggestions for mass encryption (Albert Yang)
Re: LSFR (Mike Rosing)
Re: Random numbers generator (Tom St Denis)
Re: Triple-DES and NSA??? (John Savard)
Re: Why is EDI dead? Is S/MIME 'safe'? Who and why? (Michael
=?iso-8859-1?Q?Str=F6der?=)
Re: Thawte or Verisign SSL Certificate? ("Richard A. Schulman")
Re: Wagner et Al. (Paul Crowley)
Re: LSFR ("Trevor Jackson, III")
Re: AES & satellite example (John Savard)
Re: Need some design suggestions for mass encryption (John Savard)
Re: Intel 82802 Random Number Generator (Guy Macon)
Re: LSFR ("Trevor Jackson, III")
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Random numbers generator
Date: Thu, 13 Jan 2000 17:03:16 GMT
In article <85kq97$17c$[EMAIL PROTECTED]>,
"Simone Molendini" <[EMAIL PROTECTED]> wrote:
> Hi all,
>
> where can I find C code for a *good* random number generator?
>
> C rand() routine seems me to be a weak one: it has only a 32768 cycle
(it
> seems me).
I wrote a AlgA/AlgM mix that uses upto 64 byte seeds. It's all in C if
you want to see it just ask via [EMAIL PROTECTED]
Basically I take two Lagged Generators, plug em into a Algorithm M
[using a 8192 entry table] and output one byte [8 bits] at a time.
It's part of CB [the crypto api I am writting]. If anyone wants to
check out my Crypto Api [which has this RNG, four symmetric ciphers,
RSA functions, data compression, hashing and base64 routines] just
ask. It's not officially done but in the sake of science I will let
others see it early.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Questions about message digest functions
Reply-To: [EMAIL PROTECTED]
Date: Thu, 13 Jan 2000 17:11:32 GMT
[EMAIL PROTECTED] wrote:
: Tim Tyler wrote
:> [EMAIL PROTECTED] wrote:
:> : Tim Tyler wrote:
:> :> Recall that I calim that each hash value should occur
:> :> with as near-equal frequency as possible given the
:> :> target distribution of message files to be hashed.
:> :>
:> :> A classical pseudo-random function would produce something
:> :> more like a bell-shaped distribution.
:>
:> : First, to be have any meaning at all you have to
:> : say what random variable you think to have a
:> : bell-shaped distribution. [...]
:>
:> Domain: possible hash values corresponding to plausible messages;
:> Range: the frequency of the occurrences of each hash value.
: Ah - there's the problem.
: Given the function
: f(x) = number of messages m (of some limited
: length) such that x=hash(m)
: I agree a hash is bad if f(x) is bell-shaped.
: But you are simply wrong: it is _not_ expected to be
: bell-shaped for a random function. You can test it for
: small ranges. You'll find the graph is jagged but stays at
: roughly the same height.
This is a point mainly concerned with terminology.
First I need to say that I have been misleading - for which I am sorry.
I am imagining the domain to be sorted by hash frequency. I did not
say this explicitly - which is probably a cause of misunderstanding.
The curve may perhaps more accurately be described as a half-bell-shaped
curve.
A bell shaped curve does not /have/ to have a tail that extends to infinity.
A section of a bell-shaped curve is still properly described as a bell
shaped curve.
In practice, most bell-shaped curves *are* truncated. The description
refers to the shape, not how much of the infinite tail is actually
present.
Also - if it helps clarify things - only half a bell-shaped curve is
present. You can sort the domain to put the centre of the bell-shaped
curve in the middle of the domain if you're in the mood.
Given all this - which undoubtedly I should have made clearer - the
frequency distribution *is* expected to be a bell-shaped curve for a
random function.
Finding that the frequency graph is roughly the same height does
*not* demonstrate it approximates a linear function. In fact it
approximates a bell shaped curve, albeit with most of its ends
chopped off.
:> : Second for the meaningful statistics that we could use, it's the
:> : variance that indicates how nearly-equally frequent the digest
:> : are, not the shape.
:>
:> I generally agree. However, a near flat distribution is always
:> the ideal, and a bell-shaped distribution almost always fails to
:> be as good, pretty much regardless of the variance.
: Nonsense, probably deriving from not knowing what
: distributions are bell-shaped.
:-(
I think what I wrote is essentially correct. A near-flat distribution
/does/ seem to be the ideal distribution of hashes for any given set of
messages.
Hash frequencies should be as flat as possible for the expected messages
to best resist brute force. A PRF reaches this ideal, only once in a
blue moon, by pure chance. It approaches it, though, I agree, as message
size grows.
:> :> When the messages to be hashes are much longer than the hash, the
:> :> hashes will still follow a bell-shaped curve, rather than being a
:> :> near-flat distribution.
:>
:> : You lost me. You say the distribution function is
:> : bell-shaped for a random function, and flat for a
:> : function in which each digest has the same number
:> : of preimages? What random variable are talking
:> : about?
:>
:> I've varied this reply rather than repeat it verbatim:
:>
:> Domain: all possible hash values;
:> Range: the frequency of the occurrences of each hash value.
: The point of those questions was to bring up the
: misunderstanding. If you graph f(x) = frequency of digest
: value x, the graph is perfectly flat if each digest has the
: same number of pre-images,
Yes, it is.
: [...] but it is not bell-shaped for a random function.
Yes it is.
It sure as anything is not flat. You described it as "jagged" youself
above. If you consider the domain to be sorted by hash frequency, a
bell-shaped curve is what will result.
: Another graph we might draw to describe the distribution is
: g(x) = number of digests having x pre-images.
Yes. That wasn't the graph I meant to discuss, though.
However, my comments apply equally to it, if you replace any occurrences
of "a flat distribution" with, "a single narrow peak".
: Random functions have the distribution we want for a hash.
Not AFAICS. Not unless your messages are typically unboundedly large.
In all other cases (and perhaps even in that case) PRFs deviate from
the best hash distribution.
: As message size increases, the variance in the number of
: preimages vanishes in proportion to the mean.
"Shrinks" might be a better term than "vanishes" - but apart from
this quibble, I don't believe I've ever disputed this.
: For messages of arbitrary size, the graph you named looses its
: jaggedness; it becomes the flat line you want and not the
: bell you thought.
_Precisely_ the source of my objection. *Nobody* *ever* deals with
messages of arbirary size. The /vast/ majority of such messages take up
more bits of information than there are atoms in the visible universe.
When the distribution of messages is not totally unrestricted, so the
ideal distribution of hashes deviates from that of a PRF.
: Now look at the requirements for a cryptographic hash
: function. It maps a preimage of _any_ size to a fixed-size
: digest.
Not in the real world, it doesn't.
: Collisions and preimages are not limited to small sizes.
Indeed not - but there are a variety of practical curcumstances where
there is either some restriction on the message size, or the attacker
wants to fake a message of a given size because (for example) the
recipient knows the message size in advance because all the messages
are the same length.
A finite expected message size, and a fixed message size as constraints
both present circumstances where a PRF demonstrably fails to meet the
best distribution for hashes.
: Hash functions work with messages of arbitrary size [...]
No. Hash functions /never/ work with messages of arbitrary size.
Messages of arbitrary size exist only in mathematical never-never land.
Actual implementations of hashes *never* work with such an input set.
: [...] and for messages of arbitrary size the distribution induced
: by a random function is the ideal.
In fact, probably not.
Smaller messages are generally easier to compute the hash of than large
messages. This means if you want to maximise the work function required
to find *any* hash collision by brute force, you should make searching
smaller messages as unrewarding as possible - assuming rather
reasonably that comparing with previously compared hashes is cheaper than
calculating new ones. This - assuming it is accepted - immediately
demands deviations from the distribution predicted by a PRF.
The above assumes collision resistance is desirable. If it is /only/
needed that finding a message with the same hash as that of a target
message be difficult - rather than finding any two messages with the
same hash - a random function is ideal for the infinite set.
Anyway, this is not the set of messages I'm discussing. I don't see
much point in discussing targetting such a set of messages - since this
will never be the input set of any real hash.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
'Scuse me while I whip this out.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Truly random bistream
Reply-To: [EMAIL PROTECTED]
Date: Thu, 13 Jan 2000 17:24:56 GMT
Mike McCarty <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
: )I believe I recognised the existence of negative viscosity, and
: )/still/ claimed the absolute zero viscosity was an academic dream.
: )
: )There's no such thing as perfect conductivity (or zero resistance).
: Actually, there is. When the Cooper pairs form, they actually *cannot*
: be scattered.
Why isn't the universe full of Cooper pairs, then? Does the existence of
Cooper pairs equate directly with zero resistance? No.
: )Even if there /were/ (as usual) nobody would ever know if it had been
: )realised or not.
: This sentence means nothing to me.
Nobody can measure resistance with the accuracy required. It takes
time to measure resistance. The more accurate you want to be, the
longer you have to observe for. Without measurement, you can't
confirm the resistance of the entity in question to the satisfaction of
anyone else.
: )The universe just doesn't seem to like these absolutes people keep
: )claiming it can exhibit.
: Umm. Anthropormophism aside, *you* seem not to like it.
I don't. However, as far as I know, neither does the uncertainty
principle, and the other laws of physics - so I don't feel lonely ;-)
: )Electrons insist on materialising and dematerialising, protons decay right
: No one has ever observed electrons "materialising and dematerialising",
: no one has ever observed a proton to decay.
So therefore it doesn't happen? People have witnessed these things by
proxy. You might was well say speciation, viruses or black holes don't
exist, because nobody's ever seen them directly.
Here's something else that can happen: particles emitted from the Sun
samsh into your equipment playing havoc with it's ability to transmit
electrons, just before you certify it as having absolute zero resistance.
: )in the middle of your experiment, things from the environment get in the
: )way, and perfection remains elusive.
: Not so. What you wrote is perfectly incorrect.
You don't appear to have explained adequately how this is so.
If you want to make your point, I think you should try again.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
A man without a God is like a fish without a bicycle.
------------------------------
From: "Richard A. Schulman" <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc,alt.security.pgp
Subject: Re: Why is EDI dead? Is S/MIME 'safe'? Who and why?
Date: Thu, 13 Jan 2000 12:42:19 -0500
James Redfern writes:
>I can see major e-commerce sites evolving to a more structure
> global infrastructure and needing something like this, and maybe XML would
be
> the transport, but from the 'research' I have been able to do, I still
don't
> get a sense of large numbers involved, like with e-mail and even the
original
> hopes for EDI.
EDI applications should become cheaper and faster to build with the spread
of XML use. While, doubtless, there has been an excessive amount of hype
surrounding XML, it seems to me its most promising domain of application
will be EDI. The resulting productivity improvements will be important for
the continuing prosperity of the world economy.
Whether The Redfern Organization will turn my prognostication into a
successful IPO I will leave to your better judgment, but I always welcome
consultancy fees....
Hey, isn't this way off topic for these newsgroups?
--
Richard Schulman
(for email reply, remove the anti-spamming 'XYZ')
------------------------------
From: Glenn Larsson <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Cryptography in Tom Clancy
Date: Thu, 13 Jan 2000 18:37:43 +0100
Terje Elde wrote:
> I would not even think about bothering with it. The chances of
> successfully decrypting it is about the same chance as getting hit by
> lightning 42535295865117307932921825 at the same time your're falling out
> of bed.
I once heard a good saying:
-"If you're falling from the sky, you may as well try to fly"
/ichinin
------------------------------
From: Albert Yang <[EMAIL PROTECTED]>
Subject: Need some design suggestions for mass encryption
Date: Thu, 13 Jan 2000 18:13:05 GMT
Hey there crypto-heads, I need some help.
My company has commissioned me with a daunting task. We deal with
highly sensitive private information (phone, credit card #, addy, etc..)
and we want to save it on our DB encrypted. But there are certain
things that have to happen. For example, I'm allowed to share my phone
number or address with certain people, kind of like a group
phonebook... So I would need to allow them access at any time. Yes, I
know, sounds like a Public key deal, where I just encrypt with all the
public keys that I want to have access to my stuff. But I need to be
able to revoke access from certain people at any given time. So is
there any way to design this smartly, where I don't have to basically
decrypt, reencrypt with one less key, just to deny someone who use to be
on my access list? Also, Public key crypto is slow, I'm not sure this
is something that public crypto can do on the fly, fast enough. I would
need to use something that's really fast. So any suggestions are
welcome!
Thank you,
Albert
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: LSFR
Date: Thu, 13 Jan 2000 12:22:24 -0600
Michael Darling noralco wrote:
> The reason we are trying to use an LSFR is because it is extremely quick in
> logic terms and we hope to use
> it to provide a very high resolution timer. A normal binary counter suffers
> from delays caused by the propagation
> of carry bits. The LSFR wouldn't suffer from this problem.
>
> The cryptographic side of it is a side effect for us and we wish to just get
> the output from the device and convert
> it into its position in the sequence thus giving us the time stamp.
>
> Unfortunately none of us are professional mathematicians and our pure
> mathematics is a tad limited.
> What we really want is an algorithm we can follow and implement in code.
>
> If we were to store every output of the sequence in a dictionary and use it
> as a look up then in theory that works fine.
> However, assuming 64bit storage for each 49bit output (for efficiency in
> reading) then we are looking at around
> 4096 terabytes of storage space required. This is clearly impractical.
>
> So you see our problem. We need a quick solution to a problem that we had
> no idea was so complex :)
Oh, now I get it. I was confused by the term "time stamp" since
I'm so used to just writing down clock time :-) Every clock tick
is the lfsr output, and you want to know how many clock ticks
happened to get there. The discreet log papers mentioned are
what you need, have fun!
Patience, persistence, truth,
Dr. mike
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Random numbers generator
Date: Thu, 13 Jan 2000 18:32:37 GMT
In article
<[EMAIL PROTECTED]>,
Eric Lee Green <[EMAIL PROTECTED]> wrote:
> Simone Molendini wrote:
> >
> > Hi all,
> >
> > where can I find C code for a *good* random number generator?
> >
> > C rand() routine seems me to be a weak one: it has only a 32768
cycle (it
> > seems me).
>
> check out http://www.counterpane.com for the "Yarrow" PRNG for the
Win32 API.
>
> If you are on the Linux or FreeBSD platforms, simply fetch bytes from
> /dev/urandom (or /dev/random, if you need truly random numbers as vs.
a good
> PRNG). Because they have access to internal entropy events within the
kernel
> to continually seed and re-seed the generator, they produce better
results
> than user-mode PRNG's can produce. /dev/urandom has had some slight
criticism
> since it relies upon supposed properties of MD5 that are not
guaranteed, but
> in practice this is more of theoretical interest rather than being an
actual
> problem.
>
> If you are on other Unix platforms, I tossed together one using
TwoFish and
> MD5 that you can get at http://www.estinc.com/~eric . I'd do things
> differently nowdays, since this isn't the most efficient approach in
the
> world, but it does work and doesn't have the cycle problem.
I would argue this is a bad idea. Since dev/random is not portable. A
good RNG fed thru AlgM [or a hash] would be better. It's more portable.
Plus most RNG's [which are not secure] are easy to understand and show
off, and their secure addon is easy as well. If you try to make one
algorithm that is both that's more difficult.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: alt.privacy,alt.security
Subject: Re: Triple-DES and NSA???
Date: Thu, 13 Jan 2000 11:53:31 GMT
anonymous <[EMAIL PROTECTED]> wrote, in part:
>Did the NSA screw around with Triple-DES like they did with DES back in
>the 70s?
Triple DES is DES repeated three times. Thus, it couldn't have been
specifically altered by the NSA or anyone.
Unless there's a weakness in EDE Triple-DES as opposed to EEE...
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Michael =?iso-8859-1?Q?Str=F6der?= <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc,alt.security.pgp
Subject: Re: Why is EDI dead? Is S/MIME 'safe'? Who and why?
Date: Thu, 13 Jan 2000 20:03:03 +0100
"Richard A. Schulman" wrote:
>
> > What are the
> > security implications and will S/MIME be enough 'en-route'
> > protection?
>
> I can't comment on S/MIME, but XML can be encrypted using existing
> technologies.
Regard S/MIME (based on PKCS#7) as an encryption protocol. Besides
other aspects S/MIME defines a standard for formatting encrypted and
signed messages.
I would expect that people will use S/MIME to embedd XML data (as
MIME object) and that there might be DTDs which describes how to
embedd encrypted/signed data into XML.
Ciao, Michael.
------------------------------
From: "Richard A. Schulman" <[EMAIL PROTECTED]>
Subject: Re: Thawte or Verisign SSL Certificate?
Date: Thu, 13 Jan 2000 14:26:38 -0500
<[EMAIL PROTECTED]> wrote in message
news:84rjt6$6d3$[EMAIL PROTECTED]...
> 1) Is it necessary to pay a company such as Thawte or Verisign for a
> certificate? If so, which company's better?
Verisign now owns Thawte.
--
Richard Schulman
(for email reply, remove the anti-spamming 'XYZ')
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Wagner et Al.
Date: 13 Jan 2000 19:13:09 -0000
[EMAIL PROTECTED] (Guy Macon) writes:
> If someone has physical access to your computer (a requirement for
> the attack you listed), NT is exdactly the same level of security
> as UNIX, Linux. OS/2, DOS, Mac OS, etc. None. Not a bit. Nada.
> Don't even go there. That Dog won't hunt. NOT!! Null. Snowball's
> chance in Hell. Fat chance. Slim chance. Don't hold your breath.
Not strictly so. First, you can password-lock the BIOS into booting
from the HD and padlock the case shut, in which case you'll need a
pair of cutters to do the obvious attack, and you'll look a bit
conspicuous using them. Second, Linux (at least) offers you the
option of using encrypting filesystems, which means that even after
you reboot you can't get at or usefully modify any of the data stored.
--
__
\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
------------------------------
Date: Thu, 13 Jan 2000 14:33:04 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: LSFR
"Michael Darling noralco" wrote:
> Hi Trevor,
>
> Thanks for your reply.
>
> The reason we are trying to use an LSFR is because it is extremely quick in
> logic terms and we hope to use
> it to provide a very high resolution timer. A normal binary counter suffers
> from delays caused by the propagation
> of carry bits. The LSFR wouldn't suffer from this problem.
>
> The cryptographic side of it is a side effect for us and we wish to just get
> the output from the device and convert
> it into its position in the sequence thus giving us the time stamp.
>
> Unfortunately none of us are professional mathematicians and our pure
> mathematics is a tad limited.
> What we really want is an algorithm we can follow and implement in code.
>
> If we were to store every output of the sequence in a dictionary and use it
> as a look up then in theory that works fine.
> However, assuming 64bit storage for each 49bit output (for efficiency in
> reading) then we are looking at around
> 4096 terabytes of storage space required. This is clearly impractical.
Whoa! There's no need to store every sample in the dictionary. Only the
samples that are used are worth storing. Samples that are not used will never
be the subject of a reverse lookup, so they can be discarded.
>
>
> So you see our problem. We need a quick solution to a problem that we had
> no idea was so complex :)
Well, the additional info certainly helps constrain the search space ;-)
Have you looked at gray codes? They have no carry propagation because only a
single bit changes between states. And the transform from gray numbers to
normal numbers is quite simple in both directions.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: AES & satellite example
Date: Thu, 13 Jan 2000 12:32:14 GMT
"Roger Schlafly" <[EMAIL PROTECTED]> wrote, in part:
>So you are claiming that today's technology is such that we can
>design 5 ciphers and be certain that at least one of them is secure,
>but we cannot design one cipher and be certain it is secure?
>You might be right, but it seems like a peculiar position to me.
Well, what we could do is design 5 ciphers that are different from one
another.
Even though we couldn't be certain that even one of them is secure,
with any luck, if a crack for one of them is discovered, it might be
considered to be unlikely that within, say, 24 hours of that, cracks
for the other four ciphers will show up.
So having 5 ciphers available for rapid swapping gives at least an
interim alternative.
It isn't about getting certainty, but about improving the odds in the
absence of certainty.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Need some design suggestions for mass encryption
Date: Thu, 13 Jan 2000 12:27:58 GMT
Albert Yang <[EMAIL PROTECTED]> wrote, in part:
>My company has commissioned me with a daunting task. We deal with
>highly sensitive private information (phone, credit card #, addy, etc..)
>and we want to save it on our DB encrypted.
>But there are certain
>things that have to happen. For example, I'm allowed to share my phone
>number or address with certain people, kind of like a group
>phonebook... So I would need to allow them access at any time.
>Yes, I
>know, sounds like a Public key deal, where I just encrypt with all the
>public keys that I want to have access to my stuff. But I need to be
>able to revoke access from certain people at any given time. So is
>there any way to design this smartly, where I don't have to basically
>decrypt, reencrypt with one less key, just to deny someone who use to be
>on my access list?
You probably do have to decrypt and re-encrypt _something_ in order to
revoke access by people who can decrypt it themselves. It could just
be a key instead of all the data, although then the intermediate key
could be remembered.
>Also, Public key crypto is slow, I'm not sure this
>is something that public crypto can do on the fly, fast enough. I would
>need to use something that's really fast. So any suggestions are
>welcome!
If the information is stored on your database, one thing that could
happen is that the encryption could be supplementary to operating
system protections.
Does your database, with its highly sensitive information, have to
give that information (but in encrypted form) to anyone who asks for
it?
Of course, even using public-key encryption to allow people asking for
information to identify themselves, this is less secure then a case
where only those authorized for information have the key. So, if you
don't want a master key as part of the database, so that your company
can read all the records, but instead people store their data with
their own key, which they give out to selected people, then
re-encryption is needed. If in addition to this sharing, the main
computer does use all the information in the DB, then simply refusing
to give out the information when asked by the wrong people matches the
security which really exists.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Intel 82802 Random Number Generator
Date: 13 Jan 2000 14:30:45 EST
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Scott Nelson)
wrote:
>Note that we're also told that the low frequency varies
>10-20 clocks. Either it doesn't drift much between
>successive counts, the figure of 6 raw bits per 1
>processed bit is wrong, or there are some pretty
>severe flaws in the analysis. The more I look into
>this paper, the less confidence I have.
This is electrical engineering, a subject I know something about.
What you describe is the difference between a voltage to frequency
converter (VFC) and a phase locked loop (PLL). Intel uses a PLL
and PLLs have a sort of "intertia" which explains the 6 bits quite
nicely. The range of frequencies can be large, but it tends to hold
a frequency longer than you would expect.
------------------------------
Date: Thu, 13 Jan 2000 14:37:07 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: LSFR
"Michael Darling noralco" wrote:
> Hi Trevor,
>
> Thanks for your reply.
>
> The reason we are trying to use an LSFR is because it is extremely quick in
> logic terms and we hope to use
> it to provide a very high resolution timer. A normal binary counter suffers
> from delays caused by the propagation
> of carry bits. The LSFR wouldn't suffer from this problem.
>
> The cryptographic side of it is a side effect for us and we wish to just get
> the output from the device and convert
> it into its position in the sequence thus giving us the time stamp.
>
> Unfortunately none of us are professional mathematicians and our pure
> mathematics is a tad limited.
> What we really want is an algorithm we can follow and implement in code.
>
> If we were to store every output of the sequence in a dictionary and use it
> as a look up then in theory that works fine.
> However, assuming 64bit storage for each 49bit output (for efficiency in
> reading) then we are looking at around
> 4096 terabytes of storage space required. This is clearly impractical.
>
> So you see our problem. We need a quick solution to a problem that we had
> no idea was so complex :)
>
> Regards,
> Mike.
>
> Trevor Jackson, III <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Michael Darling wrote:
> >
> > > Because electronically it is very simple and very quick - which we need.
> > >
> > > > Why are you using an LFSR rather than a counter of some type? If you
> use
> > > a
> > > > black counter, one that toggles 1/2 the bits on each increment, you'll
> see
> > > the
> > > > same degree of volatility as a good LFSR implementation.
> > > >
> > > >
> >
> > If the LFSR is clocked by the process that samples it, and you are going
> to use
> > a "reasonable" number of such samples, say < 2^32, you can simply search
> the
> > small portion of the state space that was actually used.
> >
> > If the LFSR is clock independently you'll need to record the outputs used
> as
> > tuples {state, step#} in a dictionary.
> >
> > If you expect to use an "unreasonable" number of outputs, I suggest an
> alternate
> > arrangement. Use a simple counter to track time (step #), and run the
> counter
> > though a mixing function to scramble it. The 49/3 LFSR would be a
> suitable
> > mixing function if you iterate it 16 times or so.
> >
> > Given this arrangement you can find a time given an output by loading the
> LFSR
> > with the output and running it in reverse 16 times.
> >
> >
Afterthought: I believe the GPS systems uses a PRNG as a kind of time base.
They do this to avoid putting a ridiculously accurate clock in each receiver.
You might find something useful in the research behind their system.
Unfortunately I don't have any references at hand.
------------------------------
** 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
******************************
