Cryptography-Digest Digest #788, Volume #9 Sun, 27 Jun 99 19:13:03 EDT
Contents:
Re: one time pad (S.T.L.)
Re: Des keys (Jim Gillogly)
Re: The One-Time Pad Paradox (John Savard)
Re: one time pad (David A Molnar)
Re: A few questions on RSA (David A Molnar)
Re: Moores Law (a bit off topic) (John Savard)
Re: Moore's Trend (John Savard)
Re: VIC cipher now described on web site (John Savard)
Re: Tough crypt question: how to break AT&T's monopoly??? ([EMAIL PROTECTED])
Re: The One-Time Pad Paradox ([EMAIL PROTECTED])
Re: DES-NULL attack ([EMAIL PROTECTED])
Re: Tough crypt question: how to break AT&T's monopoly??? (Bill Unruh)
Hamming Weight ([EMAIL PROTECTED])
Re: New version of free disk encryption product for NT (with Scramdisk support)
([EMAIL PROTECTED])
Re: The One-Time Pad Paradox ("Robert C. Paulsen, Jr.")
Re: OTP is it really ugly to use or not? ([EMAIL PROTECTED])
Re: one time pad (Jerry Coffin)
Re: A few questions on RSA encryption (Jerry Coffin)
Re: Bytes of "truly random" data for PRNG seed. ([EMAIL PROTECTED])
Re: Hamming Weight (Tom Knight)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: one time pad
Date: 27 Jun 1999 19:26:22 GMT
<<If your ship is an SSBN and you want to send "DEFCON I", the OTP might
be useful.>>
I don't argue with that, but the plain vanilla method is not useful if you want
to hide the very existence of the message. Imagine that Charlie is everywhere,
and one day he hears a very powerful radio signal with 64 bits contained in it
broadcast to every American submarine in the world. I don't know about you, but
if I were Charlie I would suspect that something big is about to go down.
However, if American Headquarters *regularly* broadcasts "ALL = OK" (using up
64 bits of the submarines' OTP pads every time they do that), Charlie will see
a regular broadcast of gibberish. The time that "DEFCON I" is broadcast will
then look no different to Charlie. Of course, OTP pad synchrony actually seems
to be highly important here.
-*---*-------
S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^3021377 - 1 is PRIME!
Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
E-mail block is gone. It will return if I'm bombed again. I don't care, it's
an easy fix. Address is correct as is. The courtesy of giving correct E-mail
addresses makes up for having to delete junk which gets through anyway. Join
the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
.sig is shorter and contains 3379 bits of entropy up to the next line's end:
-*---*-------
Card-holding member of the Dark Legion of Cantorians, the Great SRian
Conspiracy, the Triple-Sigma Club, and the Union of Quantum Mechanics
Avid watcher of "World's Most Terrifying Causality Violations", "World's
Scariest Warp Accidents", and "When Tidal Forces Attack: Caught on Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #3: Thou Shalt Conserve Baryon Number.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Des keys
Date: Sun, 27 Jun 1999 12:48:06 -0700
fungus wrote:
> [EMAIL PROTECTED] wrote:
> > Just wondering... With a better key schedule and longer key DES could
> > have been slightly more secure (i.e probably ok for another 10 years).
> >
>
> Tne NSA wanted to be able to crack it in the '70s, remember...
An NSA guy at one of the Santa Barbara Crypto meetings told me (not
off-the record or classified or anything) that their horizon was
about 15 years: that they were willing to take the risk of putting
out an algorithm that they wouldn't be able to read if it were turned
against them for that long. This (he said) was the planning factor
both for DES and SKIPJACK. The 80-bit SKIPJACK cipher was supposed
to give them about the same blackout period if it were leaked, which
would put its safe life expectancy at around 2008, counting from
the Clipper I roll-out. This is a more aggressive development cycle
than envisioned by the SKIPJACK Committee, which estimated 30 years
beyond DES based (apparently) on Moore's uh, uh, ueber-den-Daumen
WAG of 18 months per binary order of magnitude.
I don't have an independent assessment of his credibility, but
he told me this with a straight face and I am quite sure that
if it were a real policy he would be in a position to know
about it. It is a priori credible that they'd be willing to
accept <some> period of illegibility, because the NSA has two
missions that are in some conflict: one is to read everybody
else's mail, and the other is to protect US communications.
It's a tough balancing act.
--
Jim Gillogly
Hevensday, 4 Afterlithe S.R. 1999, 19:30
12.19.6.5.12, 3 Eb 20 Zotz, Fourth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: The One-Time Pad Paradox
Date: Sun, 27 Jun 1999 20:29:32 GMT
[EMAIL PROTECTED] (S.T.L.) wrote, in part:
>Moral of this story: You were absolutely correct that munging a one-time-pad
>spoils its perfection. "Null keys" or "similar plaintext producing keys" don't
>change that, and in my eyes aren't a paradox because of the existence of
>"completely different plaintexts".
I know you disagree, but I think that we must also take into account
that we don't live in a perfect world, and an adversary may not know
that we're using the one-time-pad for our messages.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: 27 Jun 1999 20:10:36 GMT
[EMAIL PROTECTED] wrote:
> No. This issue may belong in the FAQ. The secure channel may have
By the way, is there a project underway to update the crypt
cabal FAQ ? I remember seeing some discussion of this, but
wasn't following it closely enough.
Thanks,
-David Molnar
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: A few questions on RSA
Date: 27 Jun 1999 20:02:50 GMT
Gilad Maayan <[EMAIL PROTECTED]> wrote:
B
>>This would work, except that e and d are defined to be
>>inverses of each other. Inverses are reasonable to compute. :-\
> Wait, so why is it that you can't compute the secret key from the
> public key? If they're inverses of each other, it stands to reason
> that it would work the other way around. And, of course, it doesn't,
> since public keys are freely published.
i
I'm sorry, you're right. I screwed up and thought that you
were tossing in p and q as well -- the public and private
keys are inverses of each other __mod phi(n)__. Recovering
phi(n) from n alone is as hard as factoring (to see why, set
up the equations n = pq, phi(n) = p-1 q -1 and use the
substitution + quadratic formula).
iYou're right, the choice of which is the "public key" and
which is the "private key" doesn't seem to matter for this (except
perhaps in the sense that you have unbalanced size keys).
> And one more thing - excuse my ignorance, but as you might have
> guessed I'm new to this field - what exactly is an LCG?
A linear congruential generator is a "random" number
generator which looks like this :
Consider x_0, x_1, x_2, ... x_n as the outputs of the
generator.
x_0 = some seed mod n
x_i = a * x_(i-1) + b mod n
where a and b are constants which define the generator.
"Linear" because that's the equation of a line, and
"congruential" because of the mod n.
These are predictable from their output, even without knowing
a, b, or n. Even if you have only a few bits of the output.
Terry Ritter gave a bibliography in another thread of
refrences which show how to go about doing such predictions.
Don't ever use linear congruential generators = "LCGs" for
cryptography.
e I hope you'll forgive me for going to so much detail.
No, not at all. Detail is good. It's when people don't
give details that I can't understand what the heck is going
on. Makes life very difficult.
Even if this level of detail means I have no excuse for
making mistakes.
Thanks,
-David Molnar
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Moores Law (a bit off topic)
Date: Sun, 27 Jun 1999 20:35:05 GMT
[EMAIL PROTECTED] wrote, in part:
>Where could I read about Moores law? I will check the search engines
>but some urls may help.
I suppose you _could_ try
http://www.intel.com/
Essentially, during a large portion of the era of integrated circuits,
the maximum number of gates on a chip has doubled every eighteen
months. This is Moores' law, named after an engineer at Intel.
It is an observation of how microprocessors have been improving.
Doubtless, they will continue to do so for some time, but eventually
the technology will mature, and this will stop.
But whether that will happen soon, or not for some time, and whether
when that happens available computing power will stop increasing, or
whether integrated circuits will then, or shortly thereafter, be
replaced by some revolutionary new technology producing even greater
levels of computing power -
are all things nobody really knows. Any opinion I might offer would be
mere speculation.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Moore's Trend
Date: Sun, 27 Jun 1999 20:39:57 GMT
[EMAIL PROTECTED] wrote, in part:
>I think 128-bit keys will be secure for more then a century or two.
>Note that they never said 56 bit keys were safe. Even when they
>proposed DES they thought the key was too small.
Well, when DES was proposed, the people proposing it claimed that 56
bits was good enough; _others_, but yes, at that time, said the key
length was adequate. However, the most prominent objectors recommended
that we encrypt everything in RSA instead of using a conventional
cipher with a bigger key...
And there's no way of knowing that it will take a century before
quantum computers become practical.
Can anything, short of the OTP, resist a quantum computer? Is anyone
out there wrestling with this question (I'm trying to, but I confess I
don't quite have the equipment to grapple with it...).
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: VIC cipher now described on web site
Date: Sun, 27 Jun 1999 20:43:07 GMT
Uri Blumenthal <[EMAIL PROTECTED]> wrote, in part:
>Actually, it seems that you don't even need a threat of Siberia
>to teach a man to add correctly single-digit numbers! (:-)
I'll have to agree. After all, although I did have some initial
errors, which I corrected, in setting up the web page in question, I
didn't write a computer program to do the arithmetic involved...
and am I not human? (with apologies to Sojourner Truth, of course...)
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Tough crypt question: how to break AT&T's monopoly???
Date: Sun, 27 Jun 1999 20:41:25 GMT
In article <[EMAIL PROTECTED]>,
fungus <[EMAIL PROTECTED]> wrote:
> Could sending this as an e-mail attachment be classed as an "export"?
In the states yes, but unless your service provider told the
authorities they could never use it against you.
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: The One-Time Pad Paradox
Date: Sun, 27 Jun 1999 20:52:02 GMT
So you are saying that a random key might not be random? Makes no
sense. Ok lets assume a key of all zero (or all 1, or all the
same...). This will be easily identifiable.
However for truly random keys this is about as probable as putting your
hand thru your desk (which is possible, just not probable).
The OTP is a silly cipher, and I don't know why people discuss it.
The OTP is just like saying, I will give the message in secret and
share the key over the medium. If you have a secure medium, what's the
point? Well you can send messages at later dates, however OTPs have no
key agility, so if the key becomes compromised (or exhausted) then you
are stuck.
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: DES-NULL attack
Date: Sun, 27 Jun 1999 20:47:37 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Yes it does. The size of the key space is _defined_ to be 2^keybits,
> sometimes modified by subtracting a few known-weak keys.
>
So 18374686479671623680 is a small number?
> If you have the same number of key bits you have the same keyspace.
If
> you have "close to" the number of key bits you have "close to" the
same
> keyspace. "Close to" in an exponential space.
>
Close to might not mean much. Consider a 80 and 81 bit key. There are
1208925819614629174706176 80-bit keys
2417851639229258349412352 81-bit keys
If you think about that from a key selection point of view that's quite
large. Each bit doubles the number of keys.
If you have weak keys adding one bit may not help much. Which is why
one hopes to define a flat key space and complete permutations* (where
each key selctions from one of the many 2^n! possible permutations).
Tom
* Most ciphers are complete because they are reversible. What i was
trying to allude to is that each key defines a new set of permutations
sharing as little mappings as possible.
--
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] (Bill Unruh)
Subject: Re: Tough crypt question: how to break AT&T's monopoly???
Date: 27 Jun 1999 21:47:53 GMT
In <[EMAIL PROTECTED]> fungus <[EMAIL PROTECTED]>
writes:
]"S.T.L." wrote:
]>
]> Therefore a sort of mini-decryptor program needs to be attached
]> to the cyphertext, just as self-extracting ZIP files have a
]> mini-extractor attached to the cyphertext.
]>
]Could sending this as an e-mail attachment be classed as an "export"?
Yes, it almost certainly would be.
------------------------------
From: [EMAIL PROTECTED]
Subject: Hamming Weight
Date: Sun, 27 Jun 1999 22:03:11 GMT
What is a Hamming Weight and how does one calculate it?
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New version of free disk encryption product for NT (with Scramdisk
support)
Date: Sun, 27 Jun 1999 21:58:26 GMT
Not to be a pain, but can we have a link please?
In article <7l5ho0$poi$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Announcing the latest version of my free disk encryption product,
> previously called Caveo now called E4M (Encryption for the Masses),
and
> available from www.e4m.net, with complete source code!
>
> This version includes the following features:
>
> * Support for Scramdisk file hosted volumes using all of Scramdisks
> ciphers except the 'summer' cipher.
> * Support for Pkcs-5 key setting via either HMAC-MD5 or HMAC-SHA1.
> The Pkcs-5 code is self testing, and tests itself against HMAC
> and Pkcs-5 test vectors.
> * Support for new ciphers including IDEA, 3 key triple-DES, CAST
and
> Blowfish.
> * A new command line tool 'voltest' has been provided which dumps
the
> headers (E4M only) of a particular volume, and tests the
particular
> volumes sector encryption, optionally you can display individual
> sectors with this tool.
> * Support for changing volume passwords has been added.
> * The user interface for mounting a volume has been rewritten to be
> more user friendly.
> * Passwords can now be cached in the driver (and cleared at the
users
> request).
> * The History information is now more robust, the history operates
a
> MRU list of the last 8 volumes mounted.
> * The mount program now shows the full path name of a mounted
volume
> when a mounted drive letter is selected.
> * Support for MDCSHA is now not available for new volumes. Only SFS
> uses this cipher.
> * Some of the cursor handling in the format wizard has been cleaned
> up, the wizard now correctly displays the hour glass cursor at
> the correct times.
> * The FAT formatting code has been rewritten to drop the GPL�d
code,
> this means this product no longer ships under the GNU GPL.
> * The format GUI now shows the user what�s going on with the random
> code. Random bytes, and the selected key bytes are displayed to
> the user.
> * The documentation system now uses SDF which allows different
> document formats to be used such as Windows hlp, and html.
>
> Paul Le Roux
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
>
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Robert C. Paulsen, Jr." <[EMAIL PROTECTED]>
Subject: Re: The One-Time Pad Paradox
Date: Sun, 27 Jun 1999 17:19:27 -0500
[EMAIL PROTECTED] wrote:
>
> So you are saying that a random key might not be random? Makes no
> sense. Ok lets assume a key of all zero (or all 1, or all the
> same...). This will be easily identifiable.
>
> However for truly random keys this is about as probable as putting your
> hand thru your desk (which is possible, just not probable).
>
> The OTP is a silly cipher, and I don't know why people discuss it.
Please read _Between_Silk_and_Cyanide_ by Leo Marks.
--
____________________________________________________________________
Robert Paulsen http://paulsen.home.texas.net
If my return address contains "ZAP." please remove it. Sorry for the
inconvenience but the unsolicited email is getting out of control.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: OTP is it really ugly to use or not?
Date: Sun, 27 Jun 1999 22:29:32 GMT
"RandAlthor" <[EMAIL PROTECTED]> wrote:
> It was just his last sentence that I disagree with.
>
> The processing is very significant. You are trying to decrypt, but now
have
> to do a decrypt of the Non OTP and then the OTP to get any
verification that
> you are on the right track. Since you can't crack the OTP, it makes
the OTP
> ambigous enough to be virtually unusable to anyone without the
authority.
Perhaps I was unclear. What's insignificant is the
processing added by the encrypted pad, versus a system
that applies the cipher to the plaintext directly.
The scheme is a form of randomized encryption, which may
add security depending on the cipher. If the adversary
is given an encrypted version of the pad, the system is
no properly an OTP.
--Bryan
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: one time pad
Date: Sun, 27 Jun 1999 11:04:31 -0600
In article <7l37o8$5du$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
> > IMO, this isn't really proving much anything: for the most part,
> > OTP isn't practical to start with. Proving that a real
> > implementation can only approximate it doesn't mean a
> > lot because nearly anything that's practical is KNOWN
> > to only be an approximation to start with.
>
> I would disagree. Elliptical curve crypto is not an approximation,
> unless you say that a particular implementation "might" have a bug that
> weakens it.
Sorry -- I was thinking specifically of things that attempted to be
implementations of OTP. I.e. they start with some source of more or
less random numbers, and combine them in a stream with the plaintext
to produce the ciphertext.
Right now, we don't know any way of predicting when a radioactive atom
will decay -- as far as we know, it's entirely random. On a
reasonable-sized statistical sample, we can predict with reasonable
accuracy how many will decay in a particular length of time, but still
have no idea about predicting when an individual one will decay.
I believe Terry Ritter's point was that even though the problem
appears intractable right now (and has for some time) there's no way
to prove that nobody will ever be able to do so more accurately than
we can now. It's barely possible that at some point we'll know enough
more about radioactive decay to able to view it as entirely
deterministic. Personally, I doubt it, but you never know...
> So the question in my mind becomes: Is it safer to try to approximate
> a theoritical OTP as much as possible or rely on a math problem that:
[ could be open to solution soon ]
Even if we start with the assumption that we can implement an OTP in a
way that really matches the spec, so it's truly unbreakable, we're
left with the more fundamental problem that it's not useful in most
common situations anyway -- it still has a key that's just as large as
the text being encrypted, rendering it worthless in the average
situation.
We have quite a few symmetric ciphers that as far as we know at the
present time aren't breakable. Even if we assume that they're
entirely secure, they're still not useful if what you really need is a
public-key style cryptography.
Public-key cryptography makes the most assumptions of any of these: it
basically starts with something that's assumed to be much easier to do
than to undo. In the case of RSA, people have been studying prime
numbers, and methods of factoring for centuries, and it's still a
fairly difficult problem. Personally, I think it's pretty safe to
assume that a huge breakthrough that'll render RSA in general useless
simply isn't going to happen, but I'll openly admit that it's
theoretically possible.
Ultimately, it comes down to a simple situation: first and foremost,
you have to pick a form of cryptography that'll do the basic things
you want to do -- if you need something like public-key cryptography,
the (at least theoretically) superior security of an OTP doesn't mean
much. Even if you could guarantee its security, it still just
wouldn't do what you want. Once you've picked out a general form of
encryption that's able to do the general sorts of things you need to
do, you can try to pick the specific algorithm in that genre that
you're convinced has the best chance of remaining secure for the
period of time you need. Here things may get more complex -- the
typical example is public-key cryptography, which you're typically
going to have to combine with some symmetric cipher in real use.
Finally, once you choose an algorithm you have to look at protocols
surrounding the algorithm, and ensure they're well designed to produce
a product that doesn't have obvious breaks other than to break the
encryption algorithms themselves.
My observation has been that while Terry has a good basic point, it's
NOT particularly relevant to a lot of practical use: if you look
around at products that use encryption, and ways they've been broken,
it quickly becomes apparent that breaking the fundamental algorithms
is just about the last thing to worry about.
Just for example, if you decided to write a browser with a high level
of security, and (for whatever crazy reason) decided to use single DES
as its form of encryption, but implemented it extremely well, your
browser using DES would almost certainly provide FAR better security
than Netscape Navigator, Internet Explorer, etc., even though (at
least in domestic versions) they use algorithms with much larger keys
and much lower chances of anybody breaking them than DES.
In the end, trying to talk about whether it's better to use public-
key, symmetric or OTP cryptography is mostly a pointless gesture.
Each does different sorts of things. Believing that an algorithm
provides a high level of security is pointless if it simply won't do
the sorts of things you want or need to get done.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: A few questions on RSA encryption
Date: Sun, 27 Jun 1999 11:41:51 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> 1. Yes, it is possible to keep a modulus secret, and share it only
> with the intended receiver, as in secret key cryptology. You would
> have some key-management issues to deal with, but if you wanted to,
> you could.
Sure you could, but what's the point? As private-key cryptography,
they're terrible designs. RSA requires a huge key and it runs
ridiculously slowly. DH has exactly the same problems. ECC doesn't
have the problem with key size, but retains the speed problem (in
fact, I believe it's generally even slower than RSA or DH, though I'm
not sure of this).
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Bytes of "truly random" data for PRNG seed.
Date: Sun, 27 Jun 1999 22:06:50 GMT
[EMAIL PROTECTED] (Terry Ritter) wrote:
> Again, from my article:
>
> "Because an x^2 mod N generator generally defines multiple cycles with
> various numbers of states, the initial value x[0] must be specially
> selected to be sure that it is not on a short cycle (p. 377).
[...]
> I am aware by private communication of work investigating the
> probability of short cycles. This is also very complex, and I am
> unaware of formal publication. The implication is that we can avoid
> cycle length checks at low risk, but I think that is almost a step
> beyond what I would call "proven" strength: Admittedly, any cipher
> can be solved by guessing the key, which implies that we accept a tiny
> probability of weakness in ciphers. But it seems a little different
> if we, by our own choice, have selected a short cycle for our
> opponents to exploit, while still maintaining the delusion that our
> generator is "proven" secure.
Is anything wrong with the following argument? It shows
that under the assumption that factoring Blum integers is
hard, short cycles are of no concern.
The logic is that finding a cycle is as hard as finding a
factor. I'll show this constructively - here's an
algorithm to factor Blum integers:
def cycleFactor(n):
while 1:
a0 = randLong(3, n)
if jacobi(a0, n) == -1: break
a1 = a0 * a0 % n
prev = a1
x = a1 * a1 % n
while x != a1:
prev = x
x = x * x % n
return gcd(n, abs(prev - a0))
The function randLong(a, b) returns a random integer in
[a,b). The functions jacobi(), gcd(), and abs() are
Jacobi symbol, greatest common divisor and absolute value
respectively. (This is actual Python code.)
The first while loop will exit quickly, since about
half the candidates will satisfy the test. The second
must exit, since a1 is a quadratic residue mod n and
the function f(x) = x * x mod n, where n is a Blum
integer, is a permutation on the quadratic residues
modulo n.
When the second while loop exits, a0 and prev will both
be square roots of a1, and will have opposite Jacobi
symbols. They must be congruent mod p and not congruent
mod q, or the other way around. Thus the gcd show will
return a factor of n.
The run time of the algorithm is the time for the BBS
generator with a random seed to cycle. Finding cycles
is therefore as hard as factoring.
Finally, a couple points to put the issue in context:
We should always remember that the proof of security of
BBS generator is only a "relative" proof; it depends on
the intractability of factoring (Blum) integers. One
would certainly be correct to assert that the BBS
generator has _not_ been proven secure in the open
literature.
The post that started this thread was, as I understood
it, concerned with sources of randomness for use as
seeds. The BBS generator, like any PRNG, requires seed
material, and thus is not a reasonable solution to the
problem posed.
--Bryan
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Tom Knight <[EMAIL PROTECTED]>
Subject: Re: Hamming Weight
Date: 27 Jun 1999 16:36:44 -0400
[EMAIL PROTECTED] writes:
> What is a Hamming Weight and how does one calculate it?
It is measured by counting the number of "1" bits on in a collection
of bits.
In England it is, of course, measured in stones.
The Hamming *distance* is the count of the number of bits different
between a pair of words.
------------------------------
** 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
******************************
