Cryptography-Digest Digest #375, Volume #13 Thu, 21 Dec 00 11:13:00 EST
Contents:
Re: All irreducible polys of degree 32 over GF(2) (Benjamin Goldberg)
Re: All irreducible polys of degree 32 over GF(2) (Benjamin Goldberg)
RE: Q: Result of an old thread? ("Manuel Pancorbo")
RE: Q: Result of an old thread? ("Manuel Pancorbo")
Re: Q: Result of an old thread? (Benjamin Goldberg)
Re: Q: Result of an old thread? (Benjamin Goldberg)
Re: Q: Result of an old thread? (Mok-Kong Shen)
Re: does CA need the proof of acceptance of key binding ? (Mok-Kong Shen)
Re: Steganography using text as carrier (Andre van Straaten)
Re: All irreducible polys of degree 32 over GF(2) ("Matt Timmermans")
Re: All irreducible polys of degree 32 over GF(2) ("Matt Timmermans")
Re: All irreducible polys of degree 32 over GF(2) ("Matt Timmermans")
Re: Unguessable sequence of unique integers? (Simon Johnson)
----------------------------------------------------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: All irreducible polys of degree 32 over GF(2)
Date: Thu, 21 Dec 2000 11:14:40 GMT
Matt Timmermans wrote:
>
[snip request for list of primitive order 32 GF(2)[x] polys]
>
> In case you're interested, it's for a program that will use CRT secret
> sharing to do "unsequenced" transmission over unreliable or
> distributed channels. For instance:
>
> You want a file that you can get from 30 different sources, so you
> tell them all to start transmitting parts to you. Each one repeatedly
> does the following:
>
> 1) Pick a polynomial at random from the above list
>
> 2) calculate the "CRC" of the file using the chosen polynomial
>
> 3) transmit the CRC and the polynomial to you.
[snip recieve from many protocol and multicast protocol]
Curiously, this method seems to be a way to have a secure unicast file
transmission without having a secure cipher or secure random number
generator -- provided that you do have a statistically good PRNG, like
Mersenne Twister.
The sender does the following:
MersenneTwister_state mt( seed );
polynomial x = 1, y, z;
do {
y = mt.next();
z = crc( file, y );
send( z ); // don't send y!!!!
x = lcm( x, y );
} while( x.bitlength() < file.length );
The recipient does the following:
MersenneTwister_state mt( seed );
vector<polynomial> a, b;
polynomial x = 1, y, z;
do {
y = mt.next();
z = recv();
a.insert(y); b.insert(z);
x = lcm( x, y );
} while( x.bitlength() < N );
file = CRT( a, b );
The fact that MT is not cryptographically secure does not significantly
harm the protocol, since it's contents are never sent in any retrievable
way.
Another advantage is that unlike a traditional stream cipher, if a bit
is flipped, the entire file becomes different. Talk about error
propogation!
Also, the same secret key can safely be used for more than one file,
although having an IV, used similar to how ciphersaber IVs are used,
would be a good idea (append it to the secret key, then continue
normally).
MT *can* use a seed larger than 32 bits. Just set the first element of
the state array to 0xFFFFFFFF, and copy your seed into the remaining
words of state.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: All irreducible polys of degree 32 over GF(2)
Date: Thu, 21 Dec 2000 11:29:37 GMT
Scott Contini wrote:
>
> In article <3xe06.8114$[EMAIL PROTECTED]>,
> Matt Timmermans <[EMAIL PROTECTED]> wrote:
> >Note first: I've been on vacation -- sorry to all those I couldn't
> >finish arguing with, and thanks to all those who finished my
> >arguments better than I would have.
> >
> >To business, then:
> >
> >I'm looking for a list of all irreducible polynomials of degree 32
> >with coefficients in GF(2). I've written a program to generate them,
> >but I'd rather not have my computer tied up for the week it would
> >take to generate them all. Does such a list exist elsewhere?
>
> To add to my previous reply, I just found that the number of
> irreducibles of degree 32 over GF(2) is 134215680.
> Details:
> http://www.theory.csc.uvic.ca/~cos/inf/neck/PolyInfo.html
>
>http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001037
>
> That's approx 2^27. Each one can be stored in one 4 byte word, so
> that makes the list length approx 512 megabytes. There certainly are
> tricks to reduce this memory (my guess is that you could make it 1/4th
> the size without too much difficulty), but you really are asking for a
> long list.
Another thing to note... If you are sending using only random
irreducible polynomials, not random polynomials, the maximum file length
that you can send is the size of that list (512 mb), and due to
collisions, it will take nearly forever to send a file approaching that
size. If you allow totally random polys (reducibles and irreducibles
both), there is a significantly larger maximum file size. Of course,
it's rather unlikely that anyone would be sending such gigantic files
over the net, but hey, ya never know.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: "Manuel Pancorbo" <[EMAIL PROTECTED]>
Subject: RE: Q: Result of an old thread?
Date: Tue, 19 Dec 2000 13:11:40 +0100
Chris Monico <[EMAIL PROTECTED]
>
> Thus, we need not find A (or B) to get the secret. It suffices to find
> _any_ invertible matrix Y such that YH=G.
>
If you work with matrices with integer coefficients modulo N, where N = pq
being {p,q} primes, the matrix Y is very hard to find, unless you have also
{p,q}.
This is because at some step you must perform single number inverse
operations modulo N, which is rather difficult without {p,q}.
I post this scheme in a subthread. Take a glance at it.
--
Manuel Pancorbo Castro
------------------------------
From: "Manuel Pancorbo" <[EMAIL PROTECTED]>
Subject: RE: Q: Result of an old thread?
Date: Tue, 19 Dec 2000 13:15:45 +0100
Walter Hofmann
>
> It still isn't secure: By comaring the (1-dimensional) image of SB
> (=image of S) and ASB you can find out how A operates on the image of
> S. This is enough to calculate S from AS.
>
Well, it is not enough. You will need to perform single number inverse
operations modulo N at some steps.
Otherwise, show how to compute the task without single number inverse
operations.
--
Manuel Pancorbo Castro
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Q: Result of an old thread?
Date: Thu, 21 Dec 2000 12:51:27 GMT
Manuel Pancorbo wrote:
>
> Chris Monico <[EMAIL PROTECTED]
>
> >
> > Thus, we need not find A (or B) to get the secret. It suffices to
> > find _any_ invertible matrix Y such that YH=G.
> >
>
> If you work with matrices with integer coefficients modulo N, where N
> = pq being {p,q} primes, the matrix Y is very hard to find, unless you
> have also {p,q}.
>
> This is because at some step you must perform single number inverse
> operations modulo N, which is rather difficult without {p,q}.
>
> I post this scheme in a subthread. Take a glance at it.
The problem with this method is that, unless I'm mistaken, both people
need to be using the same N, and thus the same (p,q). Since (p,q) needs
to remain secret, it obviously has to be transfered, in secret, from one
person to the other.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Q: Result of an old thread?
Date: Thu, 21 Dec 2000 13:17:14 GMT
Walter Hofmann wrote:
>
> On Mon, 18 Dec 2000 18:55:43 +0100, Manuel Pancorbo
> <[EMAIL PROTECTED]> wrote:
> >
> > Well, I propose a slightly different scheme.
> > Let's work with 2x2 matrix with integer coefficients modulo N.
> > Alice chooses 2 prime numbers {p,q} and builds the modulus N = pq.
> > She also
> > builds the S-matrix in this way
> > | p+m, m |
> > | p+m+q, m+q |
> > where "m" is the message. S is singular (det S = 0 mod N).
> >
> > She gets any non-singular matrix A and performs AS. "A" must
> > fullfil: mcd (N, det A) = 1 in order to get the inverse. Because
> > Alice knows {p,q} it is easy to obtain A^-1.
Actually, A can't just be *any* non-singular matrix. It also must
fulfil det A != 1, otherwise it is invertable to someone who only knows
N, not (p,q). Also, gcd is a standard term, mcd isn't -- g clearly
means greatest, just as l in lcm clearly means least... but m can mean
either minimum or maximum.
> > Alice sends {AS , N} to Bob.
> > Bob computes ASB and sends it to Alice. "B" must fullfil: det B = 1
> > mod N.
> > Under this conditions the inverse B^-1 is easily computable without
> > knowing {p,q}. It is also easy to build the B-matrix. For example
> > | 1+rs, 1+rst+r |
> > | s, st + 1 |
> > where {r,s,t} are random numbers < N, is a matrix with
> > determinant = 1 (mod N).
> > And the rest of the process is the same. Bob finally gets S and m.
> >
> > If you don't know {p,q} you can't perform the attack you described.
>
> You don't need p,q to do any of the computations above.
As Manuel Pancorbo commented in another reply to this, (p,q) are needed
to compute A^-1.
As to the epsilon-attack... Perhaps it's possible for (AS') to be chosen
so its determinant (mod N) is 1, in which case it's invertible.
However, choosing so this is true might not be possible.
> It still isn't secure: By comaring the (1-dimensional) image of SB
> (=image of S) and ASB you can find out how A operates on the image of
> S. This is enough to calculate S from AS.
What's the 1-dimensional image of a matrix?
Offhand, does anyone know if this key-exchange method can be turned into
a public key encryption system? It seems that it might be faster than
RSA, wouldn't it?
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Result of an old thread?
Date: Thu, 21 Dec 2000 14:44:11 +0100
Walter Hofmann wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> >Let me quote a previous follow-up of yours to be sure that
> >I understand you:
> >
> > So you can change the coefficiants of AS by a sufficiently
> > small epsilon>0 to get an invertible matrix, then you can
> > calculate (AS')^-1. Go on to calculate B'=(AS')^-1.ASB
> > then S(epsilon)=SB.B'^-1. In the limit epsilon->0 the
> > matrix S(epsilon) will converge to S as all operations
> > involved are continuous.
> >
> >You defined B'=(AS')^-1.ASB. But ASB is singular, so B'
> >can't be inverted. Or do you want to apply the epsilon to
> >ASB also?
>
> Now I see what you mean: You cannot invert B' here because I put
> another factor of S in it.
>
> It's probably the best to compute things the other way round, otherwise
> one would need two epsilons:
>
> Change ASB to ASB' which is within an epsilon of ASB.
>
> Then you can calculate
>
> B'^-1 = ASB'^-1 . AS
> S = SB . B'^-1
>
> and do the limit process as described above.
>
> Is this OK with you now?
I still think that your limit process is problematic,
for on a computer with fixed word size there is a certain
delta such that anything smaller than that will be
treated as zero (underflow), so the limiting process
can't be carried out in all situations. On the other
hand the argument of Jacob Jonnson that there is a good
probability of obtaining a non-singular matrix to solve
the problem does seem to be useful in general cases.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: does CA need the proof of acceptance of key binding ?
Date: Thu, 21 Dec 2000 15:39:49 +0100
Anne & Lynn Wheeler wrote:
>
> there are all sorts of boundary & discontinuity conditions.
......
[snip]
Dumb question: Is it that difficult/impractical for
a customer to deposit a public key at his bank and
be able to sign all kinds of stuffs, thus avoiding
the sort of problems discussed in this thread?
M. K. Shen
------------------------------
From: Andre van Straaten <[EMAIL PROTECTED]>
Subject: Re: Steganography using text as carrier
Date: 21 Dec 2000 08:43:12 -0600
[EMAIL PROTECTED] wrote:
>> There is a book:
>> Peter Wayner, Disappearing Cryptography, AP Professional, 1996,
>> which I bought at www.bookpool.com
>>
>> I've read only the first chapters about messaging via error-correcting
>> codes, but the main part is about generating and altering ASCII text.
> Thanks! This sounds exactly like what i have been looking for.
> was thinking of something along the following lines:
> assign a number (000 to 255) for each existing ascii character, as
> well as a number for , <space>, <tab>, <linebreak>,<paragraph>.
> assume a range of 000 to 300, (with many numbers not yet assigned, but
> with room for future assignment)
Apart from paragraph, all these characters as space, etc. are within
the 255 ASCII characters. So you stay with these. The can entirely
describe an ASCII file.
> compare any text (T) to any desired carrier text, (C) character to
> character, and the difference between the the character in (T) and the
> character in (C) can be represented by a number
> [using positive integers only, ~ e.g. if the character <d> in T is
> represented by 100, and the character <b> in C is represented by 98,
> the difference would be represented by the number 298 {300-100+98} not
> by the number 2]
> the offset between any text T and any carrier C, will be able to be
> expressed as a string of three digit integers, resulting in one very
> large integer , which can be expressed as an MPI.
Sorry, no clue what is an MPI. Without that, I have problems to
understand your idea at all.
> the relative sizes of T and C do not matter, as the difference
> between empty space in one and a corresponding character in the other,
> can still be expressed as a three digit integer.
> so,
> the algorithm would first convert T and C into strings of three digit
> integers,(compare sizes of T and C, and add the three digit integers
> representing empty space to make T and C of equal length), and then
> generate an MPI representing the offset.
> all that would remain to do is to 'hide' the string representing the
> MPI somewhere in C,
> ? by some type of 'marking' the characters in C,
> {this is the part i'm having trouble with, 8^) }
> as the text T can already be an encrypted ciphertext block, there is no
> need to encrypt the encoded MPI string.
> any type of innocent e-mail or existing spam that one receives,
> modifies with the mpi string, and forwards to someone else, could be
> used,
> [but agree with you, would prefer to use innocuous e-mail plaintext as
> carrier text].
> alternatively, if there is no way to effectively disguise the MPI
> within the carrier text, this method may be used as a form of
> cryptography [for text only] not dependent on keys and the underlying
> mathematical problems that their security is based on.
Well, in cryptography, a good ciphertext is like a suspicious box you
are unable to open.
Cryptanalysis tries to find anything special in the ciphertext which
gives further clues.
The only mathematical problem I see, is that someone has a solution
to a particular problem and doesn't publish it.
That's if someone had known the number pi in ancient times, and the
rest of the world didn't.
Steganography is to hide your plain- or ciphertext at all. It's like
camouflage. It's like crossing a border illegally. Being seen means
the end of the game.
The problem here is, how distrustfully is the adversary to distinguish
the hidden object from the environment.
A company which transmits a lot of information can easier add some
hidden information than a private person which starts suddenly
interchanging large texts of Shakespeare or other stuff which makes
no sense.
> all that would be necessary is the agreement (in advance) between Bob
> and Alice on the initial carrier text,
> e.g., a certain page of a specific text that both have access to.
This looks like that it's use is limited to occasional traffic. This
agreement in advance needs a separate algorithm or scheme, then?
> then Bob can type a long text of (pseudo)random keyboard characters,
> generate the MPI of the offset of this new text of gibberish characters
> and the agreed upon carrier text, send the MPI to Alice, with the
> understanding that the resultant gibberish text be used as the carrier
> text for further communications, and then periodically change the
> carrier texts in a similar manner.
To what extent the resulting text for mailing looks like gibberish?
> hope that i have articulated this clearly,
Unfortunately, I don't understand it for reasons, I stated above.
But it looks to me that it's not only an algorithm for steganography
but for encrypting, too.
Well, I'll wait for your response.
-- avs
Andre van Straaten
http://www.vanstraatensoft.com
The signs and the omens are everywhere
But too few see them - too few even care
(Lee Clayton - singer/songwriter, 1979)
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: All irreducible polys of degree 32 over GF(2)
Date: Thu, 21 Dec 2000 14:55:39 GMT
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Another thing to note... If you are sending using only random
> irreducible polynomials, not random polynomials, the maximum file length
> that you can send is the size of that list (512 mb), and due to
> collisions, it will take nearly forever to send a file approaching that
> size. If you allow totally random polys (reducibles and irreducibles
> both), there is a significantly larger maximum file size. Of course,
> it's rather unlikely that anyone would be sending such gigantic files
> over the net, but hey, ya never know.
I was actually thinking of using packets of at least 4K or so, i.e.,
Divide the file into 4096 equal-sized parts, packet P contains P and W mod
Poly(P), for each part W, where Poly(P) is the Pth irred polynomial.
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: All irreducible polys of degree 32 over GF(2)
Date: Thu, 21 Dec 2000 15:13:52 GMT
"Bryan Olson" <[EMAIL PROTECTED]> wrote in message
news:91sbq3$j7m$[EMAIL PROTECTED]...
> Sounds not-unreasonable. I gather that in practice you'd
> want to break the file into pieces of some maximum size.
> Then a source could send one polynomial and a list of CRC's
> using the same poly.
Yes.
> I think there's a similar method that is about equally
> computationally efficient (which is not very) and doesn't
> require the table of 32-bit primitive polynomials: Use the
> N 32-bit words of the file as the coefficients of a degree
> N-1 polynomial P(x) over GF(2^32). Each source picks a
> random 32-bit word w, and sends (w, P(w)). Given any N
> distinct points we can reconstruct the polynomial.
Although the complexity is the same, I like the CRT method, because the
overhead is much lower for the senders (calculating CRCs is fast), and I can
think of reasonable low-memory implementations.
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: All irreducible polys of degree 32 over GF(2)
Date: Thu, 21 Dec 2000 15:32:12 GMT
"David Wagner" <[EMAIL PROTECTED]> wrote in message
news:91sl0j$hoh$[EMAIL PROTECTED]...
> You don't need the full list to implement this. The sender can just
> pick a random irreducible polynomial and use it. Implementation:
> do { p = randompoly(); } while (!irreducible(p));
> send(crc(file, p));
Thanks, David.
This is a good idea, but I have a problem with it that you might be able to
help with -- I'm under the impression that all of the fast implementations
of irreducible(p) are probabilistic, and I don't want the senders to have to
do a whole bunch of trial divisions. Are there fast and exact tests?
> In fact, you don't even need the polynomials to be irreducible. If
> P_1,..,P_m denote the polynomials the receiver has learned the CRC's
> for, then you can use the Chinese remainder theorem to learn the value
> of the file modulo the least common multiple of P_1,..,P_m. Once this
> lcm has degree larger than the size of the file, you can uniquely
> determine the contents of the file, and this happens almost as quickly
> with random polynomials as with irreducibles.
This works too, but gets inefficient when you use a lot of polynomials,
because new ones will not increase the LCM by very much on average.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Unguessable sequence of unique integers?
Date: Thu, 21 Dec 2000 15:50:04 GMT
Yeah, your spot on.... What was i thinking?
(dont answer that :) )
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
** 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
******************************
