Cryptography-Digest Digest #279, Volume #14 Tue, 1 May 01 16:13:01 EDT
Contents:
Re: GF(2^m) (Mike Rosing)
Re: Message mapping in EC. (Mike Rosing)
Re: Encryption and decryption in VHDL (Mike Rosing)
Re: Style of discussions ("Paul Pires")
Re: GCHQ Reorganization ? (John Savard)
Stretching and strengthening (Re: A practical idea to reinforce passwords) (Paul
Crowley)
Re: Censorship Threat at Information Hiding Workshop ("Paul Pires")
Re: DL blind signature (David Hopwood)
Re: SHA PRNG (Tim Tyler)
Re: SHA PRNG (Tim Tyler)
Re: GCHQ Reorganization ? [Spoiler] (Tim Tyler)
Re: Censorship Threat at Information Hiding Workshop ("Roger Schlafly")
Re: Mike Myers (Erwann ABALEA)
----------------------------------------------------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.arch.arithmetic
Subject: Re: GF(2^m)
Date: Tue, 01 May 2001 12:17:50 -0500
Tom St Denis wrote:
> Cool, that's what I thought. In polynomial basis a mult is a bunch of
> shifts and conditional xors isn't it?
Correct. An xor is addition of each coefficient. Because we set up each bit
to mean the coefficient of a specific power of "x", and we are adding in GF(2),
xor works. A shift left (in msb or big endian form) amounts to multiplication
by "x". So multiplying (x+1)*(x^2+1) we have 1*(101) ^ 101<<1 = 1111 =
x^3 + x^2 + x + 1. Multiply by x^k and you do a k fold shift.
> > No, you can have a normal basis in any field size. "Optimal" comes from
> having
> > the least number of terms to combine to form a multiply. ONB is a subset
> of NB.
>
> Lost me there... maybe I should re-read chapter 3 and 4. ...
Just 4 :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Message mapping in EC.
Date: Tue, 01 May 2001 12:32:19 -0500
Cristiano wrote:
> Could you do an example using small numbers (I don't understand "bit
> field")?
> Would you be so kind to tell me another way?
Suppose you've got 4 bit numbers. Then the "field size" is 4 bits. If you're
working in GF(2^n) you'd have a prime polynomial of the form x^4 + ... + 1, and
if you're working in GF(p) you'll have p = 11 or 13. If you want to embed the
number "3" = 0011 in binary on a curve, you first check to see if x=0011
satisfies the curve equation. If it does, you're done.
If it doesn't, you can change x to x=0111 and see if that point is on the curve.
If not, you can try x=1011. One of them is bound to be on the curve. So when
you get the data point, you clear the top bits and keep the data.
Normally field sizes range from 120 to 500 bits, with 160 being reasonably secure,
and 240 being very secure. You need 5 bits to make sure data will fit on the curve,
so that leaves plenty for raw data.
> Is there a practical way to fix this problem?
It's not a real problem, and the code fix is trivial: multiply by the cofactor
and check to see if you get the "point at infinity". If not, no problem!! If
so, you've found some interesting data :-)
> It seems that blind signature is more critical using EC rather than DL. Is
> there a way to implement it in a secure manner?
If you can do it in DL, you can do it in EC. Doing things in RSA with 2 primes
and then converting to EC can cause problems because there's only 1 prime in
EC (and DL, that's why they can be translated directly).
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Encryption and decryption in VHDL
Date: Tue, 01 May 2001 12:35:51 -0500
kris wrote:
>
> Newbie poster (sorry) :-)
>
> Does anybody have any recommendations for sites, or references
> for simple encryption of serial data in VHDL ? This would be for
> a serial bitstream, and would need some kind of shared key, and
> there woudl need to be a method for synchronising the two data
> streams.
>
> Does anyone have any experience of this ?
>
> Can anyone offer any advice ?
Check out this:
http://www.ece.wpi.edu/People/faculty/cxp.html
There's papers on Serpent in FPGA, I'm sure it was done in VHDL.
One of Christof's students is doing his defense on hyperelliptic curves
done in an FPGA. Should be lots of things for you to dig thru :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Style of discussions
Date: Tue, 1 May 2001 10:42:42 -0700
Bryan Olson <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
<snip>
> The harmful writers impersonate cryptologists without having
> bothered to seriously study cryptology. Their posts are
> stylistic imitations of scientific discourse, while their
> assertions are a jumble of the unjustified, the ill-defined,
> the irrelevant and the false.
This one was close enough to make me wonder. I'm glad
you didn't list specific examples, I might have been one.
I take it you feel that the major problem is the impersonation.
The "stylistic imitations".
There are different people here with different backgrounds,
skills and experiences. It's difficult to figure out where you fit
in, when to post when to listen. It's much harder for some than
for others. I think that those that are less experienced have a
role. Many times I have seen a newcomer ask a question and
recieve an answer to a different question or an answer that is
technically correct but so far from their understanding as to
be incomprehensible. I can relate. This happens to me all
the time.
Sometimes I use the advantage of my low status to try and give an
answer that the poster can "get". I'm not interested in proving what I
know or showing that I'm one bright whiz kid. Of course, it's not fun
to be drubbed when you get it wrong but that's a learning experience
too. Recently Doug Gwyn objected to one word in a post I made.
After the knee jerk defensiveness wore off I started thinking about it
and his preference made me look at things in a different light.
Sometimes the comments are crabby, impatient swats from the
better seats. An opportunity to find out that you are both stupid
and insignificant. Something to be learned there as well. I don't
think I know enough to impersonate a cryptologist but I guess
you could be talking to me.
What to do? This forum is like life in general except that the
behavior of the participants must be self-regulated. It is too
easy to be abusive, insulting, arrogant and aloof. If we all
agreed to reasonable rules of conduct, the "we" would be
those that don't need the rules. The trolls and terrible teens
wouldn't agree. If you see a problem, shoot off a note to the
offender. A freindly one. If they are amenable to reason, this
will work best. If they are not, nothing reasonable will work.
All you can do then is to try not to feed the animals.
Paul
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: GCHQ Reorganization ?
Date: Tue, 01 May 2001 17:50:51 GMT
On Tue, 1 May 2001 15:15:18 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote, in
part:
>See http://www.gchq.gov.uk/nap/ for more details.
So their web site wasn't designed by William Shakespeare, after all!
No, that seems to produce gibberish...
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Subject: Stretching and strengthening (Re: A practical idea to reinforce passwords)
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Tue, 01 May 2001 16:37:17 GMT
David Hopwood <[EMAIL PROTECTED]> writes:
> Harald Korneliussen wrote:
> > My idea is that upon selecting a password, X bits of
> > random data is added to the password. You are not
> > informed of what these bits are, nor does the computer
> > store them. The computer only stores how many bits
> > there are, and brute-forces them every time you enter
> > you password.
>
> This is called "key stretching", and is described in:
>
> J. Kelsey, B. Schneier, C. Hall, and D. Wagner
> "Secure Applications of Low-Entropy Keys,"
> 1997 Information Security Workshop (ISW'97), September 1997,
> pp. 121-134.
>
> It is a good idea; congratulations for re-inventing it.
>
> Another idea that achieves a similar effect by different means
> is "key strengthening", which is intentionally using a
> computationally expensive function to derive a key from the
> password. A good example of that is the bcrypt scheme described
> in:
>
> Niels Provos, David Mazières,
> "A Future-Adaptable Password Scheme,"
> Presented at USENIX '99.
> http://www.usenix.org/events/usenix99/provos.html
I'm afraid you have these two the wrong way around! Quoting from the
Kelsey et. al. paper, describing one proposed stretching scheme
The basic scheme works as follows:
X_0 = H(K_{short}, S)
For i = 1 to 2^t:
X_i = H(X_{i-1})
K_{long} = X_{2^t}
The discussion of related approaches in that paper makes it clear that
"strengthening" is the name for the technique under discussion of
adding extra bits to the hash which are discarded.
http://www.counterpane.com/low-entropy.html
cheers,
--
__ Paul Crowley
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
"Conservation of angular momentum makes the world go around" - John Clark
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Censorship Threat at Information Hiding Workshop
Date: Tue, 1 May 2001 11:01:52 -0700
Leonard R. Budney <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Darren New <[EMAIL PROTECTED]> writes:
>
> > Leonard R. Budney wrote:
> >> It is not deep to realize that people are entitled to enjoy the
> >> fruits of their labor, whether the labor is physical or intellectual.
> >> The "deep issues" revolve around exactly how to apply that in practice.
> >
> > If this is the case, do you believe copyrights and patents should be
> > limited in time?
>
> Yes.
>
> > If so, why?
>
> Because if copyrights were perpetual and assignable, then no protestant
> could ever buy a Bible without paying a royalty to the Pope. (In other
> words, there is also a rational need for the existence of a public
> domain.)
>
> The best scheme is a good question. Copyrights that outlive the original
> author seem manifestly wrong to me. Lifetime copyrights would actually
> be an *improvement* over the current system, and for example the Hobbit
> would now be in the public domain. As would all of Erle Stanley Gardner's
> fun little novels. But shorter than lifetime seems more appropriate to
> me. How long? The 1710 ruling still seems fair: about 14 years.
In deciding the term, it would be nice it it had some kind of "fairness" to
it but it also has to be practical. I don't think you can debate what a
fair term should be until the issue of commercial rights are settled.
One way, it is a term that is fair for recognition and creative control,
the other is one fair for commercial developement. These may be two
different terms. What will attract investment to pursue commercialization?
If it is a life term, it could be a real problem to find backers as anyone
can die tomorrow. There must be survivorship. These issues are hard
to take seriously if you don't believe that the purpose of these grants
is to establish a tangible asset which can be protected and valued. 14 to
20 years sounds about right to me. I have never understood why the term
and the renewal provisions are so different for copyright versus patent.
I suspect there were some vested interest in the the publishing industry
that had to be appeased. 56 years? that's absurd.
Paul
>
> Len.
>
> --
> I've seen servers run for several _years_ without a software upgrade.
> -- Dan Bernstein
------------------------------
Date: Tue, 01 May 2001 19:23:46 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Subject: Re: DL blind signature
=====BEGIN PGP SIGNED MESSAGE=====
Cristiano wrote:
> In many systems (or perhaps in all) for the blind signature based on DL,
> one must choose a prime q that divides p-1 (also p is prime) and then a
> generator in the moltiplicative group Zq*
That sounds wrong. Are you sure you're not confusing it with "a generator
of a subgroup of order q in Z*_p"? That is what Chaum-Pederson works in.
> (cfr Chaum-Pedersen from paper "Loyalty Program Scheme
> for Anonymous Payment Systems" by Arrianto Mukti Wibowo and Kwok Yan Lam).
>
> Doing some trials with small numbers, when I compute the public key y=g^a
> mod p (a is my private key) for all a<p, the distribution of y may be very
> bad; on the contrary, if I compute y=g^a mod q for all a<q, the distribution
> is as expected: I get all the elements in Zq* (g is a generator!).
> Why this "strange" set up?
>
> My implementation of the algorithm in the above paper at page 13
> (Chaum-Pedersen blind signature) doesn't work. The modulo for all the
> calculations is not shown. Is it always mod p or mod q?
Generally in discrete-log-based protocols (including Chaum-Pederson),
group operations are done mod p, and operations on integer exponents
are done mod q (the subgroup order).
If there is any confusion as to which is which, think of it this way:
In almost all DL-based protocols, it's not essential that the group is
Z*_p. It could just as well be any abstract group (written using
multiplicative notation). In the expression "a^x = b", a and b are group
elements, and b is an integer. Addition and subtraction are normally
only done on integers. Although the same notation is often used for
composition of two group elements and for multiplication of integers,
these are really separate operations; you can infer which is meant by
the fact that the type of both operands and the result must be either
all group elements, or all integers.
Of course, when the group is Z*_p, a group element is represented as an
integer, but that's just incidental - it's always possible to look at a
DL-based protocol and separate out the group elements from the integer
exponents. (Occasionally you may see a protocol that does something weird,
like adding an integer to a group element. Unless the designers give a
very good reason for doing that, it may indicate something wrong with
the protocol.)
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOu3/BTkCAxeYt5gVAQHXdAf+N7mFG/VNnHsVSb+kHgRV8MNnJuKbhkhq
xJjW2EM7k67v6bL7DSPyDCOsEVeWOIvJAeMq+pdklEvarPAMmOurV4KXgmuxuio0
Zfv2CyrV1L5zLQ3Xh6s3WQcpG9+uPWeh9lTQcDzTiC80fVOfs5JQZ2JLl38Lg5o7
ZB+U2OVmHMFPoxC0ELKd7VJGN0b/w2Ahi43CyUdHnrzBFMxsZmW7fa/uV2PSek4p
aXPCpa9WB/IiHhC1wl2vByYXVEZ7Alci14FpGxr4vdncQqfA1+3yY3NrWWYMCmyn
ya/EtWOASDhl2cnR0yOCvg3uJ1hYdYSt/pdIhXxiZEgyAbMb1zOxHQ==
=7g6a
=====END PGP SIGNATURE=====
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: SHA PRNG
Reply-To: [EMAIL PROTECTED]
Date: Tue, 1 May 2001 18:24:59 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
: Tom St Denis <[EMAIL PROTECTED]> wrote:
: : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
: :> Tom St Denis <[EMAIL PROTECTED]> wrote:
: :> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
: :> :> [...] State compromise inevitably reveals future output - but
: :> :> need not reveal past output.
: :>
: :> :> Hashing the internal state and feeding it back is one way to
: :> :> prevent state compromises giving information about earlier
: :> :> states of the PRNG.
: :>
: :> : You mean
: :>
: :> : output = Hi = HASH(R || H_i-1 || C)
: :>
: :> : Where R is the initial random seed, C a binary counter and H_0 is
: :> : HASH(R) ?
: :>
: :> That's an example of hashed feedback yes. [...]
: Anyway, that was the sort of thing I meant to refer to by
: "hashing the internal state and feeding it back".
However, looking at that particular construct, it doesn't exhibit
forward secrecy very well:
Imagine that one's opponent breaks in and steals C and R.
Now the idea is to prevent him from using this information to
gain information about (e.g.) keys generated before the break-in.
However, if he has one key, (H_early) from early in the system's usage,
he can reconstruct all the subsequent ones - and he can even do this if
he's uncertain about how many keys were generated between then and now -
not good.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: SHA PRNG
Reply-To: [EMAIL PROTECTED]
Date: Tue, 1 May 2001 18:42:23 GMT
Bryan Olson <[EMAIL PROTECTED]> wrote:
: You can avoid repeatedly hashing R. Here's a variation that
: also takes an optional input:
: output_i = HASH(i || state_i || input_i)
: state_i+1 = state_i ^ input_i ^ output_i
: I've used i for the equivalent of the binary counter that
: Tom called "C". I don't think a constant secret R is
: needed, though one could include it if worried about the
: hash function losing entropy.
: It has some nice properties: One hash computation (plus a
: few simple ops) yields an output of the full digest size. An
: exposed state doesn't expose previous outputs (even given
: the optional inputs). To predict states or outputs requires
: both the past state and all subsequent inputs (unlike the
: FIPS-186 key generator for which a past state and subsequent
: outputs reveals the current state.) [...]
If the input has limited entropy, then it looks like a state-following
attack would work - in which case prediction might still be possible
even after a large volume of total entropy input.
Anyway - in contrast to the other schemes discussed on this thread so far -
it looks like this one might actually exhibit forward secrecy - thanks.
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: GCHQ Reorganization ? [Spoiler]
Reply-To: [EMAIL PROTECTED]
Date: Tue, 1 May 2001 19:08:46 GMT
Jim Gillogly <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> GCHQ are indeed taking a nap:
:>
:> See http://www.gchq.gov.uk/nap/ for more details.
: I notice there's a Baconian cipher on the first line of that page
: in the roman/bold font that says "CHALLENGING".
Yes, you can read more about that at:
http://www.cl.cam.ac.uk/~mgk25/gchq-challenge.html
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: Censorship Threat at Information Hiding Workshop
Date: Tue, 01 May 2001 18:30:30 GMT
"Paul Pires" <[EMAIL PROTECTED]>
> is to establish a tangible asset which can be protected and valued. 14 to
> 20 years sounds about right to me. I have never understood why the term
> and the renewal provisions are so different for copyright versus patent.
> I suspect there were some vested interest in the the publishing industry
> that had to be appeased. 56 years? that's absurd.
Neither patents nor copyrights can be renewed. Patents expire 20 years
after the application date. Copyrights last for the life of the author, plus
70 years.
Every 20 years or so, when the Mickey Mouse copyright is about to
run out, Congress extends the copyright term for another 20 years.
The last extension was challenged in the courts (Eldred v. Reno), but
the courts have upheld the extension (so far). For more info, see:
http://eon.law.harvard.edu/openlaw/eldredvreno/
http://www.eagleforum.org/misc/briefs/index.html#disney
------------------------------
From: Erwann ABALEA <[EMAIL PROTECTED]>
Subject: Re: Mike Myers
Date: Tue, 1 May 2001 21:56:10 +0200
On Tue, 1 May 2001, NotMe wrote:
> Anyone knows where he now works?
>
> Reply in sci.crypt
VeriSign.
--
Erwann ABALEA
[EMAIL PROTECTED]
- RSA PGP Key ID: 0x2D0EABD5 -
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
