Cryptography-Digest Digest #597, Volume #11 Fri, 21 Apr 00 15:13:01 EDT
Contents:
Re: New version of MIRACL ("Dann Corbit")
Re: Q: NTRU's encryption algorithm (Diet NSA)
Re: New version of MIRACL (Tom St Denis)
Re: pollard-rho for polynomials (lordcow77)
Re: Q: NTRU's encryption algorithm (Diet NSA)
Re: pollard-rho for polynomials (Tom St Denis)
Re: $100 Code Challenge - I BROKE the code!!!!! Here's the plaintext as proof (Diet
NSA)
papers on stream ciphers (Tom St Denis)
Re: New version of MIRACL ("Dann Corbit")
Re: Number Theory Book (David A Molnar)
Re: New version of MIRACL (Tom St Denis)
Re: new Echelon article (Diet NSA)
Re: Problems with NTRU (Paul Koning)
----------------------------------------------------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Subject: Re: New version of MIRACL
Date: Fri, 21 Apr 2000 11:13:45 -0700
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Dann Corbit wrote:
> >
> > One of my favorite toys just got updated:
> > http://indigo.ie/~mscott/
> >
> > Definitely worth a look.
> > ;-)
>
> Not to steal the fame, but I like MPI better, and by all means for the
> others "try both :)".
I have not tried MPI. I would like to hear more about it.
Is it integer only, or does it have rational or floating point
approximations?
Is it portable to many platforms? (I play around on many different systems
and compilers so I need something very portable).
What sort of restrictions are there to the distribution? What is the
homepage URL?
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
Subject: Re: Q: NTRU's encryption algorithm
From: Diet NSA <[EMAIL PROTECTED]>
Date: Fri, 21 Apr 2000 11:15:13 -0700
In article <[EMAIL PROTECTED]>, John Myre
<[EMAIL PROTECTED]> wrote:
>to mean in the first place? AFAIK, "just a ring" means in fact
>an Abelian group plus a second operation. No?
>
A ring A is an Abelian group under addition (and is also an
A-A-bimodule).
"I feel like there's a constant Cuban Missile Crisis in my pants."
- President Clinton commenting on the Elian Gonzalez situation
=======================================================================
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: New version of MIRACL
Date: Fri, 21 Apr 2000 18:19:59 GMT
Dann Corbit wrote:
>
> "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> >
> >
> > Dann Corbit wrote:
> > >
> > > One of my favorite toys just got updated:
> > > http://indigo.ie/~mscott/
> > >
> > > Definitely worth a look.
> > > ;-)
> >
> > Not to steal the fame, but I like MPI better, and by all means for the
> > others "try both :)".
>
> I have not tried MPI. I would like to hear more about it.
> Is it integer only, or does it have rational or floating point
> approximations?
> Is it portable to many platforms? (I play around on many different systems
> and compilers so I need something very portable).
> What sort of restrictions are there to the distribution? What is the
> homepage URL?
It's a large int only, but it's quite well put together, it's by Michael
Frombeger and it is at:
http://linguist.dartmouth.edu/~sting/mpi/
It's very portable, simple to use and relatively small.
Tom
------------------------------
Subject: Re: pollard-rho for polynomials
From: lordcow77 <[EMAIL PROTECTED]>
Date: Fri, 21 Apr 2000 11:15:58 -0700
In article <[EMAIL PROTECTED]>, Tom St Denis
<[EMAIL PROTECTED]> wrote:
>
>A basis is something that can represent any element of
something...errr
>like in three-space you have the standard basis vector (1, 1,
1). Every
>point in three-space can be represented with it.
(1,1,1) does not form a basis for R^3. R^3 has dimension 3; no
single vector can form a basis for this space. A basis is a set
of vectors such that their linear combinations completely span a
given space AND no vector in the set can be formed as a linear
combination of the other vectors in the set.
>
>I figured (x + 1) would be the simplest such 'constant' or
>basis to add in each itteration.
Again, (x+1) is not a basis for any imaginably useful polynomial
space. Moreover, I am not even sure that (x+1) generates
adaquately smooth polynomials over any given reduction
polynomial. I don't have the time to look at this further, but
you might want to see how (x+1)^n splits for different values of
n over some trial polynomials.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: Q: NTRU's encryption algorithm
From: Diet NSA <[EMAIL PROTECTED]>
Date: Fri, 21 Apr 2000 11:30:18 -0700
In article <8dm6e7$o4i$[EMAIL PROTECTED]>, David A Molnar
<[EMAIL PROTECTED]> wrote:
>
>Does this last sentence have to mean "no better than using
Grover's
>algorithm"? It seems that as soon as you have a means of
"checking" your
>guess, you can use the algorithm to search for a preimage of a
given
>value in O(sqrt(n)) time. With a one-way function, it seems you
can
>check your guess g by evaluating f(g) and comparing against the
target
>value.
>
>
It's interesting that Grover's algorithm was proved to be
optimal, and it can have certain "bounds" due to a variety of
potential sources (such as the presence of noise or whether the
algorithm is searching for marked or unmarked items).
"Fortschritte der Physik" (or "Progress of Physics") vol. 46
(1998)#4-5 discusses the optimal efficiency of Grover's algorithm
as well as crypto problems that are "unsovable" even with a
quantum computer. (I don't know where these problems are in the
journal since I don't have a copy, but the Harvard U. libraries
might have a copy or, at least, they might be able to borrow
one).
"I feel like there's a constant Cuban Missile Crisis in my pants."
- President Clinton commenting on the Elian Gonzalez situation
=======================================================================
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: pollard-rho for polynomials
Date: Fri, 21 Apr 2000 18:43:48 GMT
lordcow77 wrote:
>
> In article <[EMAIL PROTECTED]>, Tom St Denis
> <[EMAIL PROTECTED]> wrote:
> >
> >A basis is something that can represent any element of
> something...errr
> >like in three-space you have the standard basis vector (1, 1,
> 1). Every
> >point in three-space can be represented with it.
>
> (1,1,1) does not form a basis for R^3. R^3 has dimension 3; no
> single vector can form a basis for this space. A basis is a set
> of vectors such that their linear combinations completely span a
> given space AND no vector in the set can be formed as a linear
> combination of the other vectors in the set.
duh. I should have said (0, 0, 1), (0, 1, 0) and (1, 0, 0).
>
> >
> >I figured (x + 1) would be the simplest such 'constant' or
> >basis to add in each itteration.
>
> Again, (x+1) is not a basis for any imaginably useful polynomial
> space. Moreover, I am not even sure that (x+1) generates
> adaquately smooth polynomials over any given reduction
> polynomial. I don't have the time to look at this further, but
> you might want to see how (x+1)^n splits for different values of
> n over some trial polynomials.
Sure, well I will try it out.
Tom
------------------------------
Subject: Re: $100 Code Challenge - I BROKE the code!!!!! Here's the plaintext as proof
From: Diet NSA <[EMAIL PROTECTED]>
Date: Fri, 21 Apr 2000 11:42:49 -0700
In article <[EMAIL PROTECTED]>, conman
<[EMAIL PROTECTED]> wrote:
>Dear Mummy, Please send more money, I've decided to take super
secret
>double- oh- seven spy classes at night. My income from bagging
>groceries at ZippyMart doesn't cover the weekly tuition. The
classes
>are really neato. They showed me how to use my free
glow-in-the-dark
>Turbo Ninja decoder ring to post encrypted challenges to
usenet.
>Nobody can figure out my special code. Life has suddenly
become very
>fulfilling. This is even better than having a girlfriend!
>
Why did someone write a plaintext about me ?-) Big Brother can
always find me, for I am the locus from which all
self-respecting women flee.
"I feel like there's a constant Cuban Missile Crisis in my pants."
- President Clinton commenting on the Elian Gonzalez situation
=======================================================================
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: papers on stream ciphers
Date: Fri, 21 Apr 2000 18:51:59 GMT
Howdy,
Looking for papers about stream ciphers. It seems block ciphers are the
norm lately...
Looking for prng/stream ciphers. Preferably not based on lfsrs....
Tom
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Subject: Re: New version of MIRACL
Date: Fri, 21 Apr 2000 11:54:14 -0700
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Dann Corbit wrote:
> >
> > "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > >
> > >
> > > Dann Corbit wrote:
> > > >
> > > > One of my favorite toys just got updated:
> > > > http://indigo.ie/~mscott/
> > > >
> > > > Definitely worth a look.
> > > > ;-)
> > >
> > > Not to steal the fame, but I like MPI better, and by all means for the
> > > others "try both :)".
> >
> > I have not tried MPI. I would like to hear more about it.
> > Is it integer only, or does it have rational or floating point
> > approximations?
> > Is it portable to many platforms? (I play around on many different
systems
> > and compilers so I need something very portable).
> > What sort of restrictions are there to the distribution? What is the
> > homepage URL?
>
> It's a large int only, but it's quite well put together, it's by Michael
> Frombeger and it is at:
> http://linguist.dartmouth.edu/~sting/mpi/
>
> It's very portable, simple to use and relatively small.
Tried it. Wants GCC and UNIX environments. Even withing GCC, several
non-portable assumptions are made:
bash-2.02$ make
The following targets can be built with this Makefile:
libmpi - arithmetic and prime testing library
tests - test drivers (requires MP_IOFUNC)
tools - command line tools
doc - manual pages for tools
clean - clean up objects and such
distclean - get ready for distribution
dist - distribution tarball
bash-2.02$ make libmpi
/usr/bin/perl make-logtab > logtab.h
/usr/bin/perl: not found
make: *** [logtab.h] Error 127
bash-2.02$ make tests
gcc -ansi -pedantic -Wall -O3 -c mpi.c
mpi.c: In function `s_mp_tovalue':
mpi.c:3488: warning: ANSI C forbids braced-groups within expressions
mpi.c: In function `s_mp_todigit':
mpi.c:3533: warning: ANSI C forbids braced-groups within expressions
mpi.c: In function `s_mp_outlen':
mpi.c:3550: `s_logv_2' undeclared (first use in this function)
mpi.c:3550: (Each undeclared identifier is reported only once
mpi.c:3550: for each function it appears in.)
mpi.c:3552: warning: control reaches end of non-void function
make: *** [mpi.o] Error 1
bash-2.02$ make tools
gcc -ansi -pedantic -Wall -O3 -c mpi.c
mpi.c: In function `s_mp_tovalue':
mpi.c:3488: warning: ANSI C forbids braced-groups within expressions
mpi.c: In function `s_mp_todigit':
mpi.c:3533: warning: ANSI C forbids braced-groups within expressions
mpi.c: In function `s_mp_outlen':
mpi.c:3550: `s_logv_2' undeclared (first use in this function)
mpi.c:3550: (Each undeclared identifier is reported only once
mpi.c:3550: for each function it appears in.)
mpi.c:3552: warning: control reaches end of non-void function
make: *** [mpi.o] Error 1
bash-2.02$ make doc
make: `doc' is up to date.
bash-2.02$
I fixed the path, and GNU's perl was unable to create the include file.
I changed the define to use log calls instead of a table, and it still fails
to compile.
Quite frankly, I don't think it holds a candle to MIRACL or FreeLip, for
that matter.
However, for whatever UNIX platform it was built on, I'm sure it does an
adequate job.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Number Theory Book
Date: 21 Apr 2000 18:59:22 GMT
Antoine Bruguier <[EMAIL PROTECTED]> wrote:
> Hi,
> I'm looking for a number theory book, explaining from the beginning. But
> I konw stuff like Zn is a field when n is prime, Fermat's theorem etc.
> Any suggestions ?
What exactly do you want to learn? and what's your background?
Do you want to learn just enough number theory so you can
understand why various crypto algorithms work? Then consider Koblitz _A
Course in Number Theory and Cryptography_. Koblitz covers the
"right" topics, and he includes things like running time for various
algorithms which many "pure" number theory books would not.
Background for Koblitz...strictly speaking you can read it knowing only
high school algebra. All the definitions are given, and the first few
chapters review such things as the definition of a group, what a finite
field is, and so on. Realistically, if you don't know that material
already, learning it from that discussion is slow going. You might want
to supplement with a text on abstract algebra.
If this sounds like too much for you, then you may want to look for
"friendlier" treatments of number theory. I don't have a favorite one
which is crypto-specific; an readable overview is the number theory
chapter in Schneier, but it is aimed more at the "what this is" rather
than "why it works." For a non-crypto-specific text, I kinda like Ore's
"Number Theory and Its History", but it doesn't have an explicit proof
of why RSA works the way some more recent books do.
Thanks,
-David
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: New version of MIRACL
Date: Fri, 21 Apr 2000 19:03:13 GMT
Dann Corbit wrote:
>
> "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> >
> >
> > Dann Corbit wrote:
> > >
> > > "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> > > news:[EMAIL PROTECTED]...
> > > >
> > > >
> > > > Dann Corbit wrote:
> > > > >
> > > > > One of my favorite toys just got updated:
> > > > > http://indigo.ie/~mscott/
> > > > >
> > > > > Definitely worth a look.
> > > > > ;-)
> > > >
> > > > Not to steal the fame, but I like MPI better, and by all means for the
> > > > others "try both :)".
> > >
> > > I have not tried MPI. I would like to hear more about it.
> > > Is it integer only, or does it have rational or floating point
> > > approximations?
> > > Is it portable to many platforms? (I play around on many different
> systems
> > > and compilers so I need something very portable).
> > > What sort of restrictions are there to the distribution? What is the
> > > homepage URL?
> >
> > It's a large int only, but it's quite well put together, it's by Michael
> > Frombeger and it is at:
> > http://linguist.dartmouth.edu/~sting/mpi/
> >
> > It's very portable, simple to use and relatively small.
>
> Tried it. Wants GCC and UNIX environments. Even withing GCC, several
> non-portable assumptions are made:
> bash-2.02$ make
>
> The following targets can be built with this Makefile:
>
> libmpi - arithmetic and prime testing library
> tests - test drivers (requires MP_IOFUNC)
> tools - command line tools
> doc - manual pages for tools
> clean - clean up objects and such
> distclean - get ready for distribution
> dist - distribution tarball
>
> bash-2.02$ make libmpi
> /usr/bin/perl make-logtab > logtab.h
> /usr/bin/perl: not found
> make: *** [logtab.h] Error 127
> bash-2.02$ make tests
> gcc -ansi -pedantic -Wall -O3 -c mpi.c
> mpi.c: In function `s_mp_tovalue':
> mpi.c:3488: warning: ANSI C forbids braced-groups within expressions
> mpi.c: In function `s_mp_todigit':
> mpi.c:3533: warning: ANSI C forbids braced-groups within expressions
> mpi.c: In function `s_mp_outlen':
> mpi.c:3550: `s_logv_2' undeclared (first use in this function)
> mpi.c:3550: (Each undeclared identifier is reported only once
> mpi.c:3550: for each function it appears in.)
> mpi.c:3552: warning: control reaches end of non-void function
> make: *** [mpi.o] Error 1
> bash-2.02$ make tools
> gcc -ansi -pedantic -Wall -O3 -c mpi.c
> mpi.c: In function `s_mp_tovalue':
> mpi.c:3488: warning: ANSI C forbids braced-groups within expressions
> mpi.c: In function `s_mp_todigit':
> mpi.c:3533: warning: ANSI C forbids braced-groups within expressions
> mpi.c: In function `s_mp_outlen':
> mpi.c:3550: `s_logv_2' undeclared (first use in this function)
> mpi.c:3550: (Each undeclared identifier is reported only once
> mpi.c:3550: for each function it appears in.)
> mpi.c:3552: warning: control reaches end of non-void function
> make: *** [mpi.o] Error 1
> bash-2.02$ make doc
> make: `doc' is up to date.
> bash-2.02$
>
> I fixed the path, and GNU's perl was unable to create the include file.
> I changed the define to use log calls instead of a table, and it still fails
> to compile.
>
> Quite frankly, I don't think it holds a candle to MIRACL or FreeLip, for
> that matter.
>
> However, for whatever UNIX platform it was built on, I'm sure it does an
> adequate job.
That's because you don't know how to use your tools. In three seconds I
can compile mpi.c to mpi.o with GCC. True you have to configure it (i.e
not use the logtab) but after that one minor change it works flawlessly
with me.
Tom
------------------------------
Subject: Re: new Echelon article
From: Diet NSA <[EMAIL PROTECTED]>
Crossposted-To:
alt.politics.org.cia,alt.politics.org.nsa,alt.journalism.print,alt.journalism.newspapers
Date: Fri, 21 Apr 2000 12:01:29 -0700
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>"We need to act now to minimize the risk to national security
and
>public safety, cut short the widespread use of encryption that
is
>inaccessible to law enforcement, spur the development of key
recovery,
>and assure that U.S. products retain their market dominance
>worldwide."
>
You might want to read this brief news story which mentions a
possible link between U.S. intel agencies, IBM, & Microsoft
regarding access to encrypted data:
http://www.theregister.co.uk/000412-000020.html
"I feel like there's a constant Cuban Missile Crisis in my pants."
- President Clinton commenting on the Elian Gonzalez situation
=======================================================================
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Problems with NTRU
Date: Fri, 21 Apr 2000 14:45:29 -0400
Tom St Denis wrote:
>
> I don't like the way NTRU presents themselves. Knocking RSA, ECC and
> Elgamal as bad, slow and insecure....
>
> Somethings fishy.
>
> Plus they push the idea that you should encrypt data directly with their
> algorithm instead of a hybrid-system. Is NTRU really that fast?
Someone else said here some time ago that NTRU actually does
have valid work, it's just hidden underneath amazingly bad
marketing. It's too bad they haven't fixed that yet.
Having someone go down for marketing snake oil is fine,
but going down for doing snake-oil style marketing on what
is actually a legitimate product would be rather a distressing
mistake!
paul
------------------------------
** 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
******************************
