Cryptography-Digest Digest #235, Volume #13 Tue, 28 Nov 00 17:13:00 EST
Contents:
Re: Isomorphic Elliptic Curves (J. Rostand)
Re: hardware RNG's (Dan Oetting)
Re: Blowfish key input size ([EMAIL PROTECTED])
Re: Isomorphic Elliptic Curves (Mike Rosing)
Blum Blum Shub ("Michal Dobrowolski")
Re: Entropy paradox (Mok-Kong Shen)
Re: Q: Role of linguistics (Mok-Kong Shen)
Information lost in SQR(n) -- crypto use? (proton)
Re: P/w based authentication and key exchange ("Michael Scott")
Re: Blum Blum Shub (Tom St Denis)
Re: Information lost in SQR(n) -- crypto use? (Tom St Denis)
Re: Entropy paradox (Tom St Denis)
Re: Q: Role of linguistics (Tom St Denis)
Re: A Simple Voting Procedure (David Schwartz)
Re: A Simple Voting Procedure (David Schwartz)
Re: hardware RNG's (David Schwartz)
----------------------------------------------------------------------------
From: J. Rostand <[EMAIL PROTECTED]>
Subject: Re: Isomorphic Elliptic Curves
Date: Tue, 28 Nov 2000 17:30:36 GMT
In article <8vts3o$ut4$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> The usual definition of two elliptic curves being isomorphic requires
> that their solutions are isomorphic as projective varieties, which is
> basically what your second statement about 'invertible, rational
> transformation...' is.
Ok. What I understand now is the following.
Let C1 and C2 be 2 cubic curves in P(K) (the projective plane over the
field K). (C1 and C2 are 2 homogeneous polynomials of degree 3 in
K[X,Y,Z].) Suppose that C1 and C2 are non-singular in P(K). Then, the
elliptic curves defined by C1 and C2 are isomorphic if and only if (by
definition) there exists polynomials P1,P2,P3,Q1,Q2,Q3 over K such that
the function
R(X,Y,Z) := ( P1(X,Y,Z)/Q1(X,Y,Z) , P2(X,Y,Z)/Q2(X,Y,Z) ,
P3(X,Y,Z)/Q3(X,Y,Z) )
from P(K) onto P(K) is a bijection, its inverse is a rational function
and [ B=R(A) is a point of C2 if and only if A=R^-1(B) is a point of C1
].
Am I right?
Proposition:
If 2 elliptic curves are isomorphic, then they have the same group
structure. The reciprocal is false.
Is this right? If yes, is it easy to prove? Any counter example to the
reciprocal?
J. Rostand.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Dan Oetting <[EMAIL PROTECTED]>
Subject: Re: hardware RNG's
Date: Tue, 28 Nov 2000 10:48:59 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> David Schwartz <[EMAIL PROTECTED]> wrote:
> : David Schwartz wrote:
>
> :> Every statistician I've ever known has used 'random' to describe
> :> distributions that were had a mode and a standard deviation. Heck,
> :> even gaussian distributions are described as random with respect to
> :> the values of individual members of a set whose distribution is
> :> described as gaussian.
>
> : By the way, I can cite dozens of usages if you'd like, for example
> : http://www.wku.edu/~neal/statistics/poisson.html
>
> I can't see how that usefully qualifies - it appears to describe a
> variable for measuring stochastic phenomena. The only place "random"
> gets mentioned is in the name of the variable ("The Poisson Random
> Variable"). It can be applied to practically any stream of values.
> The name of the variable does not imply anything about the properties
> of the streams it might be used to measure.
>
> However, I'm sure "random" is used in the sense you describe sometimes.
>
> It doesn't seem to be used that way very often within cryptography.
> "Random" streams have the property of being hard to predict - and they
> pass tests for randomness. 5:1 biased streams do not appear to qualify.
> They don't fit Chaitin's notion of randomness, or Golombs, or any that I
> know of - short of the rather loose definition of not being completely
> predicatble.
Is radio-active decay a "random" event? Can we select a bead "at random"
from a pot containing 20% white and 80% black beads? If we have random
variations in the frequency domain do we not have random variations in
the time domain?
The term "random" has a generic meaning of being uncontrolled,
uncorrelated with other events. In statistics the term "random" has been
given the specific meaning of equal probability of each possible value.
Just because your statistics prof beat one definition into your head
doesn't mean that definition applies here.
In cryptography we use random numbers in various protocols. Ideally
these random numbers would meet the statistical definition of random.
But we recognize that the world is not perfect so we talk about the
entropy which is the number of bits of true randomness.
We also talk about sources of randomness. Since this is the real world,
random sources are not ideal and some are far from it. But by modeling
the random source we can compute the entropy that can be accumulated
from the source.
If you continue to insist that "random" can only have the definition
from statistics we will continue to beat it out of you.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Blowfish key input size
Date: Tue, 28 Nov 2000 17:57:03 GMT
In article <900bgl$ljg$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hello,
>
> I can't sleep thinking about why it is said that the input key of
> Blowfish (16 rounds) is up to 56 bytes. It seems that the limit is in
> 72 bytes (16 + 2) * 4...
>
> Please let me sleep again, thanks.
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
I don't know if this will be your sleeping pill but the document:
http://www.counterpane.com/bfsverlag.html
says:
"The 448 limit on the key size ensures that the every bit of every
subkey depends on every bit of the key. (Note that every bit of P15,
P16, P17, and P18 does not affect every bit of the ciphertext, and that
any S-box entry only has a .06 probability of affecting any single
ciphertext block.)"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Isomorphic Elliptic Curves
Date: Tue, 28 Nov 2000 12:24:10 -0600
"J. Rostand" wrote:
>
> Let C1 and C2 be 2 cubic curves in P(K) (the projective plane over the
> field K). (C1 and C2 are 2 homogeneous polynomials of degree 3 in
> K[X,Y,Z].) Suppose that C1 and C2 are non-singular in P(K). Then, the
> elliptic curves defined by C1 and C2 are isomorphic if and only if (by
> definition) there exists polynomials P1,P2,P3,Q1,Q2,Q3 over K such that
> the function
>
> R(X,Y,Z) := ( P1(X,Y,Z)/Q1(X,Y,Z) , P2(X,Y,Z)/Q2(X,Y,Z) ,
> P3(X,Y,Z)/Q3(X,Y,Z) )
>
> from P(K) onto P(K) is a bijection, its inverse is a rational function
> and [ B=R(A) is a point of C2 if and only if A=R^-1(B) is a point of C1
> ].
>
> Am I right?
Don't know. Where did you find this definition?
>
> Proposition:
> If 2 elliptic curves are isomorphic, then they have the same group
> structure. The reciprocal is false.
>
> Is this right? If yes, is it easy to prove? Any counter example to the
> reciprocal?
By reciprocal you mean "if 2 curves have the same group structure, then
they may not be isomorphic"? From the other posts I'd say it's the
other way around, if 2 curves are isomorphic they may not have the
same group structure, but if 2 curves have the same group structure
then they must be isomorphic.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] ("Michal Dobrowolski")
Subject: Blum Blum Shub
Date: 28 Nov 2000 20:26:52 +0100
This is a multi-part message in MIME format.
--====NOFNSLNUZQNH0FNQH470
Content-Type: multipart/alternative;
boundary="----=_NextPart_000_0028_01C05979.06657080"
Content-Disposition: inline
=======_NextPart_000_0028_01C05979.06657080
Content-Type: text/plain;
charset="iso-8859-2"
Content-Transfer-Encoding: quoted-printable
Hello everybody,
Can anybody tell me where can I find implemented in C Blul Blum Shub =
Random number generator, or just if U got it send it to me by mail. I =
need it of course just for my education.
Greetings :)))
Michal
=======_NextPart_000_0028_01C05979.06657080
Content-Type: text/html;
charset="iso-8859-2"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META content=3D"text/html; charset=3Diso-8859-2" =
http-equiv=3DContent-Type>
<META content=3D"MSHTML 5.00.2614.3500" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT face=3D"Arial CE" size=3D2>Hello everybody,</FONT></DIV>
<DIV><FONT face=3D"Arial CE" size=3D2>Can anybody tell me where can I =
find=20
implemented in C Blul Blum Shub Random number generator, or just if U =
got=20
it send it to me by mail. I need it of course just for my=20
education.</FONT></DIV>
<DIV><FONT face=3D"Arial CE" size=3D2>Greetings :)))</FONT></DIV>
<DIV><FONT face=3D"Arial CE" size=3D2>Michal</FONT></DIV></BODY></HTML>
=======_NextPart_000_0028_01C05979.06657080==
--====NOFNSLNUZQNH0FNQH470
Content-Type: text/plain; charset=US-ASCII
Content-Disposition: inline
Content-Transfer-Encoding: 7bit
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Prezentacja oferty i sprzedaz produktow Twojej firmy w Centrum e-biznesu
teraz za niecala zlotowke dziennie!
KLIKNIJ I ZAMOW http://www.getin.pl/centrum/es_logon.asp
--====NOFNSLNUZQNH0FNQH470--
--
Posted from [194.153.216.125]
via Mailgate.ORG Server - http://www.Mailgate.ORG
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Entropy paradox
Date: Tue, 28 Nov 2000 20:44:43 +0100
James Felling wrote:
>
[snip]
> You assume that there is an overage and then use that assumption to
> prove that entropy is added. Why is it that you claim this overage of
> randomness must exist?
If n of BBS is sufficiently large and the construction is
sound, one can generate a fairly large amount of output bits
that are practically unpredictable. That is, one inputs
into BBS a rather small amount of - also practically --
unpredictable bits and obtain as output a very large
amount of practically unpredictable bits. There could
perhaps be certain difference in 'quality' between these
two groups of bits, but as far as the user is concerned,
they are not. So, as long as the BBS cannot be brute-forced,
one has a huge gain in practically unpredictable bits. My
view is that this gain seems to come from 'nothing' (the
air), sort of via magic. That's what troubles me.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Role of linguistics
Date: Tue, 28 Nov 2000 20:44:38 +0100
Tom St Denis wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > If I don't err, in the old days knowldege of languages played
> > a non-trivial role in cryptanalysis. With modern cryptography,
> > which works at the fine level of bits, the significance of
> > linguistics to crypto seems to1 have disappeared completely.
> > Could someone confirm this? On the other hand, advances in
> > automatic language translations etc. suggest that automatic
> > analysis of sentences is nowadays without problems and perhaps
> > even certain degree of understanding of natural utterences is
> > feasible. If the domain of discourse is appropriately
> > restricted, wouldn't the limited number of sentence structures
> > together with default words and eventually in combination with
> > a code book be exploitable as a valuable means of preprocessing
> > (encoding) of the plaintext before its treatment by a proper
> > modern encryption algorithm? Or is this kind of computational
> > work too complicated and costly to merit any consideration for
> > practical crypto applications? Thanks.
>
> You're comparaison is inherantly flawed. Comparing a language to a bit
> is not exacting. A bit is just a finite piece of information whereas a
> language is a composition of bits. Perhaps comparing a language to
> ASCII, KANJI or EBDIC or something is more valid.
>
> However you are correct that "secret languages" are not used anymore
> since the advent of secret key algorithms...
I was not 'comparing' language to bits (though, as said,
modern algorithms work down to the level of bits) but just
noted that in the old days part of the analysts were
recruited from people having considerable expertise in
languages, for apparently linguistics was useful for
analysis of the historical schemes. There was no intention
of mine of considering 'secret languages', nor the ancient
languages. My question is then whether linguistics with
its involvement with compters today could be at least of
some (little) help to cryptography.
M. K. Shen
------------------------------
From: proton <[EMAIL PROTECTED]>
Subject: Information lost in SQR(n) -- crypto use?
Date: Tue, 28 Nov 2000 19:44:17 GMT
I've been thinking about the 1 bit of information that
is lost in sqr(n).
If n is negative the sign is obviously irrevocably lost.
Is this of any use in crypto? Has it been used in any
algorithms?
/proton
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: P/w based authentication and key exchange
Date: Tue, 28 Nov 2000 20:54:16 -0000
Its fun to try and develop such methods. What about this? Choose g and r as
"random" independent generators of prime order q|(p-1). Let s be the low
entropy mutual secret.
Alice A=g^a . r^s mod p
Bob B=g^b . r^s mod p
Swap A and B
Alice calculates key as (B/r^s)^a mod p = g^(xy) mod p
Bob calculates key as (A/r^s)^b mod p = g^(xy) mod p
Throw in a few hash functions and the odd random oracle, and does this work?
Note that if s=0, then this is just Diffie-Hellman.
Mike Scott
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Blum Blum Shub
Date: Tue, 28 Nov 2000 20:54:12 GMT
In article <002b01c05970$a8424b20$70664cd5@ppp>,
[EMAIL PROTECTED] ("Michal Dobrowolski") wrote:
> Hello everybody,
> Can anybody tell me where can I find implemented in C Blul Blum Shub =
> Random number generator, or just if U got it send it to me by mail.
I =
> need it of course just for my education.
> Greetings :)))
> Michal
Would you not learn more by coding your own copy?
Why not pick up a big int library (or if you have lots of time code
your own) such as MPI/MP/etc... and code your own. A rudimentary
implementation (simple prime generation, etc...) could be coded in C in
about 30mins...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Information lost in SQR(n) -- crypto use?
Date: Tue, 28 Nov 2000 20:51:49 GMT
In article <[EMAIL PROTECTED]>,
proton <[EMAIL PROTECTED]> wrote:
> I've been thinking about the 1 bit of information that
> is lost in sqr(n).
>
> If n is negative the sign is obviously irrevocably lost.
>
> Is this of any use in crypto? Has it been used in any
> algorithms?
In fact if you use Blum integers as a composite two bits are lost
(there are four roots, or is that *upto* four roots?).
And no it's not of any benefit. Ideally you want a one-to-one mapping
(such as discrete exponentiation when the generator is primitive).
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Entropy paradox
Date: Tue, 28 Nov 2000 20:58:47 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> James Felling wrote:
> >
> [snip]
> > You assume that there is an overage and then use that assumption to
> > prove that entropy is added. Why is it that you claim this overage
of
> > randomness must exist?
>
> If n of BBS is sufficiently large and the construction is
> sound, one can generate a fairly large amount of output bits
> that are practically unpredictable. That is, one inputs
> into BBS a rather small amount of - also practically --
> unpredictable bits and obtain as output a very large
> amount of practically unpredictable bits. There could
> perhaps be certain difference in 'quality' between these
> two groups of bits, but as far as the user is concerned,
> they are not. So, as long as the BBS cannot be brute-forced,
> one has a huge gain in practically unpredictable bits. My
> view is that this gain seems to come from 'nothing' (the
> air), sort of via magic. That's what troubles me.
The bits from the BBS generator are not "new" bits though. They are
not random, merely unpredictable to a third party. New bits would be
like injecting entropy into the state (i.e new modulus or a bigger one)
You have to realize the difference between output and state. The
entropy in the state (the system) does not change regardless of the
length of the output. So the output does not increase the entropy.
(hint: consider the output of a LFSR, does the output make the internal
state any more random?)
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Q: Role of linguistics
Date: Tue, 28 Nov 2000 20:55:37 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > >
> > > If I don't err, in the old days knowldege of languages played
> > > a non-trivial role in cryptanalysis. With modern cryptography,
> > > which works at the fine level of bits, the significance of
> > > linguistics to crypto seems to1 have disappeared completely.
> > > Could someone confirm this? On the other hand, advances in
> > > automatic language translations etc. suggest that automatic
> > > analysis of sentences is nowadays without problems and perhaps
> > > even certain degree of understanding of natural utterences is
> > > feasible. If the domain of discourse is appropriately
> > > restricted, wouldn't the limited number of sentence structures
> > > together with default words and eventually in combination with
> > > a code book be exploitable as a valuable means of preprocessing
> > > (encoding) of the plaintext before its treatment by a proper
> > > modern encryption algorithm? Or is this kind of computational
> > > work too complicated and costly to merit any consideration for
> > > practical crypto applications? Thanks.
> >
> > You're comparaison is inherantly flawed. Comparing a language to a
bit
> > is not exacting. A bit is just a finite piece of information
whereas a
> > language is a composition of bits. Perhaps comparing a language to
> > ASCII, KANJI or EBDIC or something is more valid.
> >
> > However you are correct that "secret languages" are not used anymore
> > since the advent of secret key algorithms...
>
> I was not 'comparing' language to bits (though, as said,
> modern algorithms work down to the level of bits) but just
> noted that in the old days part of the analysts were
> recruited from people having considerable expertise in
> languages, for apparently linguistics was useful for
> analysis of the historical schemes. There was no intention
> of mine of considering 'secret languages', nor the ancient
> languages. My question is then whether linguistics with
> its involvement with compters today could be at least of
> some (little) help to cryptography.'
I do not get what you are trying to say. Are you saying multilingual
cryptographers are more capable?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: A Simple Voting Procedure
Date: Tue, 28 Nov 2000 13:14:01 -0800
Benjamin Goldberg wrote:
> Hmm, I think you're misinterpreting me, slightly. Let's make up some
> names (as suggested by someone else) -- Snidely Whiplash (bad guy) and
> Dudly DoRight (good guy) are the candidates. A dozen people who support
> Snidely acquire the reciepts of a dozen other people's votes for Dudley.
Easy to do since the receipts are public.
> These SS folks (Snidely's Supporters) call in to the election office,
> and CLAIM that they voted for Snidely, but their reciepts, and the
> public listings, show them as having voted for Dudly.
If the receipt said they voted for Dudly, why would they have left the
polling office with receipts saying they voted for Snidely? You have the
right to have your vote cast and count correctly, but you don't have the
right to change your mind after the fact.
> Since the
> reciepts have nothing on them to say that the SS folks stole them, the
> election officals go and subtract 12 from the Dudly count and add 12 to
> the Snidely count.
Why would they do that? That's precisely equivalent to 1,000 Palm Beach
voters walking into the canvassing board and saying, "I voted for Bush
but now I want to change my vote to Gore". Presenting proof that they
voted for Bush doesn't help their case!
DS
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: A Simple Voting Procedure
Date: Tue, 28 Nov 2000 13:11:51 -0800
Benjamin Goldberg wrote:
> I don't think that will necessarily work:
> Consider using a voting machine like the one I mentioned in another
> thread. The vote (the position of the levers) doesn't count until you
> pull the Commit level, which also resets to their original position --
> at any time up until the commit lever is moved, the individual levers
> can be moved into any valid configuration you want, with no effect on
> the vote. If you photo yourself, in the both, with the levers in some
> particular configuration, there is NOTHING preventing you from moving
> them to an entirely different arrangement after the photo and before
> your pulling of the commit lever. Photoing the setup after the commit
> lever's been pulled is un-useful, because pulling it resets all the vote
> levers to their starting positions.
So you bring a video camera in with you. You are overanalyzing the
example and missing the point.
DS
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: hardware RNG's
Date: Tue, 28 Nov 2000 13:16:08 -0800
Dan Oetting wrote:
> If you continue to insist that "random" can only have the definition
> from statistics we will continue to beat it out of you.
And you'll note that those who use "random" even when they mean biased
are almost always careful to make clear what they mean. It's not that
it's impossible to use the word "random" in a confusing way. It's that
it _is_ possible to use "random" to describe a biased distribution in a
non-confusing way.
In fact, in the usage that sparked this thread, it was made explicitly
clear that the distribution was expected to be both correlated and
biased.
DS
------------------------------
** 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
******************************
