Cryptography-Digest Digest #915, Volume #11 Fri, 2 Jun 00 00:13:00 EDT
Contents:
Re: Contest rule proposal ("Paul Pires")
Re: Finding primitive polynomials via the Berlekamp method? (Terry Ritter)
Dining Cryptographers implementation? (George Danezis)
Re: Is OTP unbreakable?/Station-Station (Joaquim Southby)
Re: Is it possible to use encryption to solve this problem? (John Savard)
Re: No-Key Encryption (John Savard)
Re: Contest rule proposal (tomstd)
Re: Self Shrinking LFSR (Forrest Johnson)
Re: No-Key Encryption (Benjamin Goldberg)
Re: Finding primitive polynomials via the Berlekamp method? (lordcow77)
Can we say addicted? (tomstd)
Re: Is it possible to use encryption to solve this problem? (Thierry Moreau)
Re: Tableaus Revisited, Again ("Douglas A. Gwyn")
Re: DVD encryption secure? -- any FAQ on it (David A. Wagner)
Re: Powers of s-boxes and other functions (David A. Wagner)
Re: Pollard's algorithm for computing discrete logs (Scott Contini)
----------------------------------------------------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Contest rule proposal
Date: Thu, 1 Jun 2000 17:17:24 -0700
<snip>
> This includes my newer cipher TC2 which I will formally present
> for the contest after my finals.
Well, do well on your finals but post your cipher or hack me off the
list. I'm getting paranoid about owning the last slot for life.
Paul
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Finding primitive polynomials via the Berlekamp method?
Date: Fri, 02 Jun 2000 00:34:56 GMT
On Thu, 01 Jun 2000 16:18:53 -0700, in
<[EMAIL PROTECTED]>, in sci.crypt lordcow77
<[EMAIL PROTECTED]> wrote:
>Errr, yes, that's exactly the method I described as the
>traditional way of finding primitive polynomials (ensuring that
>the residue of x^(p_i) mod p(x) for all factors p_i is not equal
>to one). Perhaps I was unclear:
No, perhaps *I* was unclear: A common way of finding primitives in
cryptography is to choose a Mersenne prime degree, which simplifies
the factoring somewhat (:-) and that may be the largest problem. In
this way I have found a mod 2 primitive of degree 11,213 and then used
that to make an Additive RNG with about 44KB of state.
>Berlekamp's Q-matrix algorithm
>can be used to factor univariate monic polynomials; it seems
>reasonable that some adaptation of this could be used to quickly
>screen for whether a particular polynomial was primitive or not
>(by computing the dimension of the null space of Q-I, since this
>is equal to the number of irreducible factors of p(x)).
I have not seen it done, so I do not have a reference for it. I do
have Berlekamp's "Algebraic Coding Theory," and whilst I have
approached it many times (when I was doing that stuff), I must say I
never got much out of it. Chapter 6 does give a poly factorization
algorithm which seems to use matrices (one of which is called Q), but
their size always scared me away. They look big. The advantage of
the usual way is that we hold just one poly variable, squaring it
repeatedly, and need not save each intermediate result.
Neither Blahut nor Clark and Cain reference a "Q-matrix algorithm,"
and even though Berlekamp-Massey is well known, presumably "Q-matrix"
is the factoring algorithm.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: George Danezis <[EMAIL PROTECTED]>
Subject: Dining Cryptographers implementation?
Date: Fri, 02 Jun 2000 00:55:23 +0000
Dear all,
Does anyone know of any publicaly available implementation of "Dining
Cryptographers" networks?
Yours,
George
------------------------------
From: Joaquim Southby <[EMAIL PROTECTED]>
Subject: Re: Is OTP unbreakable?/Station-Station
Date: 2 Jun 2000 00:57:19 GMT
In article <8h4u3c$[EMAIL PROTECTED]> Guy Macon,
[EMAIL PROTECTED] writes:
>Joaquim Southby wrote:
>
>>My estimates always assume that the adversaries are smarter, richer, and
>>better-looking than me.
>
>Smarter, maybe.
>
>Richer, almost certainly.
>
>But Better looking? Never!
>
My multitude of fans (OK, my mom and my dog) thank you.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Is it possible to use encryption to solve this problem?
Date: Fri, 02 Jun 2000 01:01:22 GMT
On Thu, 01 Jun 2000 05:07:14 GMT, [EMAIL PROTECTED] (Paul) wrote, in
part:
>We want to have an application that users can buy.
>We also can provide add-ons to the application.
>We want to be able to sell these add-ons over the Internet via a
>subscription service.
>However, we want to make sure that one user doesn't simply pay for the
>add-ons and then simply give them away to others, bypassing the
>subscription service.
>Now my question is, what is the best way to try to go about doing
>this? Could encryption technology help us? This doesn't seem to be
>strictly a cryptographical issue, but seems to be related to it. If
>cryptography isn't part of the solution, what might be?
Encryption can go _partway_ towards helping with this.
For example, you could give each user a copy of the application with a
unique serial number. Then, you could encrypt the add-ons so that they
could only be decrypted by a specific copy of the application.
The serial number could be generated randomly at the time of
installation, making it awkward to give away the program with the
serial number as opposed to a copy of the installation files.
But this doesn't prevent a user from giving away the add-ons by also
giving away his copy of the original application. The best encryption
can do by itself is enforce the attachment of the user's serial
number, or even the user's name, to a copy of the application: and
even that can be circumvented by a hacker who can disassemble the
code.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: No-Key Encryption
Date: Fri, 02 Jun 2000 01:03:46 GMT
On Thu, 01 Jun 2000 11:45:13 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>I am confused. Doesn't that mean the schemes of Sharmir and
>Massey-Omura etc. are all broken?
No, because exponentiation is not associative.
(2^3)^2 is 8 squared or 64.
2^(3^2) is 2 to the 9th power, or 512.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
Subject: Re: Contest rule proposal
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 01 Jun 2000 17:58:47 -0700
In article <V3DZ4.35270$v7.1734557@news-
west.usenetserver.com>, "Paul Pires" <[EMAIL PROTECTED]> wrote:
><snip>
>> This includes my newer cipher TC2 which I will formally
present
>> for the contest after my finals.
>
> Well, do well on your finals but post your cipher or hack
me off the
>list. I'm getting paranoid about owning the last slot for life.
I get tommorow off school (grads are out) so I will study hard
and be back full-fledge to the group in no time.
Tom
* 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: Forrest Johnson <[EMAIL PROTECTED]>
Subject: Re: Self Shrinking LFSR
Date: 2 Jun 2000 01:24:27 GMT
In article <[EMAIL PROTECTED]> Scott Nelson,
[EMAIL PROTECTED] writes:
>I don't know how Tom did it,
>but if you're interested in generating maximal length polys,
>you might want to look at my lfsr program. It's available at
>ftp://helsbreth.org/pub/helsbret/random/
>(both source and MSDOS executable)
>
Scott, I have a couple questions about your program (the comments,
actually -- my C programming is less than expert). You stated in the
preamble that irreducible polynomials are needed for maximal length
rather than primitive polynomials. I think it's the other way around.
(Ex. X^4 + x^3 +x^2 + x^1 + 1 is irreducible, but not primitive. It
also won't produce a maximum period in a 4-bit LFSR.) Also, from Shift
Register Sequences by Solomon Golomb: "...not all the irreducible
polynomials of degree r have maximum exponent. That is, they do not all
correspond to shift register sequences of length 2^r - 1."
You also stated that "Approximately 1/16 of the chosen polys are maximal
length". I might be tripping over the term "chosen", but there are 2048
max length polynomials (out of 65535 possible) for a 16 bit LFSR. Maybe
your program restricts the choice of polynomials to test to a subset of
that 65535 and that's where the 1/16 comes from.
Thanks for sharing the code. I created a brute force program that
actually emulates an LFSR up to 32 bits long with up to 32 taps. Source
code is at <http://homepage.mac.com/afj/lfsr.html>
If anyone just wants tap sequences, that site also has lists of all
maximal length tap sequences for registers up to 24 bits plus 2, 4, and 6
tap ML sequences for 25 to 32 bits. I'm working on a list of dense (half
the bits or more involved) sequences for the latter -- maybe a couple
more weeks.
I just posted the pages about a week ago, so any feedback on errors would
be appreciated.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Date: Fri, 02 Jun 2000 01:46:05 GMT
John Savard wrote:
>
> On Mon, 29 May 2000 23:03:12 GMT, Bryan Olson <[EMAIL PROTECTED]>
> wrote, in part:
>
> >Suppose we limit ourselves to the associative operation
> >case. Does there exist an associative operation "*" such
> >that the protocol illustrated above is secure? I don't
> >know.
>
> Such an operator at least seems very likely to be insecure, because of
> the following.
>
> The scheme requires that, for the operator used, the inverse operator
> exist, to allow the legitimate recipients to decipher their messages.
>
> Let us denote the operator by *, and the inverse operator /.
> 1) A sends M*A.
>
> 2) B replies with M*A*B
>
> 3) A calculates M*A*B/A, to obtain M*B, which is sent to B. This works
> if * is commutative, but it also works if * is exponentiation, since
> (M^A)^B equals (M^B)^A, as both equal M^(A*B). Note, though, that if *
> is exponentiation, M*A/M is not A.
>
> If * is commutative, the scheme is trivially breakable. If it is
> associative, it seems to at least have a property strongly resembling
> commutativity, but A*B could lose information about B instead.
>
> If * is associative, and M*A*B = M*B*A for any M,A,B, then the
> following procedure will find Q*A and Q*B for any Q, even if it
> doesn't find M:
>
> having intercepted M*A, M*A*B, M*B, evaluate Q*M*A*B, and divide it by
> M*A or by M*B.
What if we're using multiplication modulo 2^32, and we make sure that M
is even (and thus not invertable)? If A and B are chosen to be odd, and
greater than 1, they will have integer multiplicative inverses under the
modulo, and can be removed by the host that knows them, but someone who
wants to 'divide by' any multiple of M will be out of luck.
>
> If finding Q*A for any Q lets you find A, then you can find M; this
> seems to be a serious weakness for any associative operator.
>
> John Savard (teneerf <-)
> http://www.ecn.ab.ca/~jsavard/
------------------------------
Subject: Re: Finding primitive polynomials via the Berlekamp method?
From: lordcow77 <[EMAIL PROTECTED]>
Date: Thu, 01 Jun 2000 18:58:53 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Terry
Ritter) wrote:
>
>I have not seen it done, so I do not have a reference for it.
I do
>have Berlekamp's "Algebraic Coding Theory," and whilst I have
>approached it many times (when I was doing that stuff), I must
say I
>never got much out of it. Chapter 6 does give a poly
factorization
>algorithm which seems to use matrices (one of which is called
Q), but
>their size always scared me away. They look big. The
advantage of
>the usual way is that we hold just one poly variable, squaring
it
>repeatedly, and need not save each intermediate result.
>
But for a polynomial defined over an arbitrary finite field, we
might not neccesarily want to use coefficients in GF(2) or we
might not be able to efficiently factor the maximum cycle length
(p^n-1) in order to use the standard algorithm. It seems to be
that Berlekamp's algorithm would not require such a
factorization and could be implemented easily using traditional
linear algebra methods to determine the nullspace. Such methods
would be even more efficient over GF(2); moreover, the
dimensions of the matrix would not neccesarily be very large,
growing in size as n^2.
* 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: Can we say addicted?
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 01 Jun 2000 19:09:31 -0700
Hehehe I finished my bio work for the week so I decided to make
another cipher...
TC3 and TC2 are both on my website. I have yet to write a paper
for either, but the source is up for the taking.
I am so addicted to this....
http://www.tomstdenis.com
Tom
* 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: Thierry Moreau <[EMAIL PROTECTED]>
Subject: Re: Is it possible to use encryption to solve this problem?
Date: Thu, 01 Jun 2000 15:00:54 -0500
Paul wrote:
> We want to have an application that users can buy.
>
> We also can provide add-ons to the application.
>
> We want to be able to sell these add-ons over the Internet via a
> subscription service.
>
> However, we want to make sure that one user doesn't simply pay for the
> add-ons and then simply give them away to others, bypassing the
> subscription service.
>
> Now my question is, what is the best way to try to go about doing
> this? Could encryption technology help us? This doesn't seem to be
> strictly a cryptographical issue, but seems to be related to it. If
> cryptography isn't part of the solution, what might be?
>
> Paul
Here is a plan:
(1) Make the add-ons valuable. This is your source of continued revenues,
while it looks much easier to pay e.g. 5.99 monthly than 70.00 in one
payment. Indeed, this is seldom a cryptographic solution.
(2) When a subscriber decides to enroll, use our patented SAKEM
registration process that ensures at once that
a) new customers don't have to provide paiment information (credit card
number, ACH payment authorization) on the net,
b) yet a secret authentication key is securely assigned to each customer,
e.g. in an .ini file for the application,
c) requires no serial number or any kind personalization at the
distribution phase of the application, so it can be distributed easily
(e.g. in a download trial version, the upgrade to the production copy
being the initial add-on)
(3) When an add-on is requested, it is encrypted per subscriber (there is
an overhead, but you get money for each distributed copy of the add-on).
(4) To deter copying by paying customers, your package a limited time of
service calls with each add-on, and you request an identification
procedure based on the secret key stored in the .ini file in a simple
challenge-response protocol (service rep: "please open About dialog box
and enter '7523' in the challenge field and tell me the number poping as
a 'reply' ... O.K. Mr. Happy Customer, you'are authorized, what can I do
for you?) This way, a paying customer who sends the application with the
.ini file to a fiend will face the risk of losing rights to support
services.
This plan is an expected field of use for our SAKEM registration
procedure, which is deemed to become "leading edge" in many other fields
of uses where secure and efficient customer registration is important. As
of today, the SAKEM registration procedure is available as a license to
use a patented procedure plus "portable" C++ implementation. The
cryptographic aspects of the rest of the plan (encryption per (3) and
chellenge-response protocol per (4)) is a relatively small development
task.
- Thierry Moreau
CONNOTECH Experts-conseils Inc.
http://www.connotech.com
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Tableaus Revisited, Again
Date: Fri, 02 Jun 2000 03:29:22 GMT
Mok-Kong Shen wrote:
> A related issue is that the keys used in old times seem to be
> mostly unnecessarily short. I mean one could start from a
> relatively short key and generate (stretch into) a long one for
> use in accessing the substitution tables.
The key was short because it was supposed to be memorized.
In many cipher systems, the key was indeed used to generate
an intermediate alphabet or two and sometimes to permute in
other ways.
It is hardly fair to criticize historic innovations for not
taking a more modern view. We would not have developed our
more modern view without having gone through the historic
process.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: DVD encryption secure? -- any FAQ on it
Date: 1 Jun 2000 20:33:47 -0700
In article <8h6bim$ajg$[EMAIL PROTECTED]>,
Bryan Olson <[EMAIL PROTECTED]> wrote:
> Casper H.S. Dik
> > the disks are just a bunch
> > of bits; you can read them you can copy them
>
> Giving you a copy of a bunch of bits that will not play as a
> movie. And to even get those bits requires defeating part
> of the system.
Err, as far as I can see, that's just not true.
Did you mean something different?
Making bit-for-bit copies is exactly what the studios do when
they release DVD's; the result pretty clearly does play as a movie,
and I can't imagine the result will be any different when it's a
pirate wielding the equipment.
Sure, bit-for-bit copying requires special hardware, but so what?
That's also (roughly) true for piracy of CD's, and that clearly
hasn't made the problem go away. Actually, I'm told that the DVD
pressing process was specially designed so that CD-pressing equipment
could be used to press DVD's with little modifications. One
consequence is that criminals already in the CD-piracy business
may find it relatively straightforward to expand into DVD-piracy.
> So a well-funded operation can defeat the system.
Yes, bit-for-bit copying is likely to be the attack of choice
for mass piracy, IMHO. (Of course, that doesn't mean it's the
only attack.)
> The larger problem is the one I noted: consumer equipment
> will not _write_ the reserved areas. Modifying consumer
> drives to write exact copies of CSS encoded DVDs is hard
> enough that no such modifications are known to be available.
Yes, that's my understanding, too.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Powers of s-boxes and other functions
Date: 1 Jun 2000 20:37:37 -0700
In article <[EMAIL PROTECTED]>,
Jim Steuert <[EMAIL PROTECTED]> wrote:
> I have been able compose permutation polynomials,
> and thus form powers.of a permutation (which must be permutations).
Yes. Actually, what I said in my previous post was just a rough
summary. It turns out that, for technical reasons, the results
don't hold for permutations. But, I'm not sure quite what you mean
by a "hash" if you're willing to accept a permutation -- the definition
of a hash that I've seen says it shrinks down arbitrary-length inputs
to some smaller output, and thus can't be a permutation.
> My hope is that this we can find a large variety of functions via symbolic
> algebraic methods. Several modern crypto functions have algebraic
> description which may be useful for designing classes of these functions.
Yup. It's a fascinating problem!
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Pollard's algorithm for computing discrete logs
Date: 2 Jun 2000 04:09:50 GMT
In article <[EMAIL PROTECTED]>,
Mike Rosing <[EMAIL PROTECTED]> wrote:
>Jesper Stocholm wrote:
>>
>> I'm trying to implement Pollard's algorithm for discrete logs - but I
>> have a little problem:
>>
>> I have to partition the Group into 3 sections (S1, S2 and S3). However -
>> the book I use (Handbook of Applied Cryptography) just says,
>> that "some care must be exercised in selecting the partition" - which
>> doesn't help me much.
>>
>> How do I choose the right partition of the Group ?
>
>It's arbitrary. Just make each group about the same size. You can have
>more sections too, if you have 4, then the last 2 bits of a result can
>determine which group the result goes into.
>
>Patience, persistence, truth,
>Dr. mike
Also,
See "Speeding up Pollard's Rho Method for Computing Discrete Logarithms"
by Edlyn Teske.
She suggests using more than 3 sets, and suggests a better way of doing
the random walk than Pollard's original suggestion.
Scott
------------------------------
** 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
******************************
