Cryptography-Digest Digest #457, Volume #11 Fri, 31 Mar 00 18:13:01 EST
Contents:
Re: Coderpunks Query on Teledyne Crypto (Jim Reeds)
Re: Proof of Identity (Paul Rubin)
Re: Coderpunks Query on Teledyne Crypto (John Savard)
Re: Proof of Identity (mark carroll)
Re: LFSR's ("Trevor L. Jackson, III")
Re: LFSR's ("Trevor L. Jackson, III")
Re: LFSR's ("Trevor L. Jackson, III")
Re: Coderpunks Query on Teledyne Crypto (Jim Reeds)
Re: LFSR's ("Adam Durana")
Re: OAP-L3: Semester 1 / Class #1 All are invited. ("Trevor L. Jackson, III")
Re: LFSR's (Paul Koning)
----------------------------------------------------------------------------
From: Jim Reeds <[EMAIL PROTECTED]>
Subject: Re: Coderpunks Query on Teledyne Crypto
Date: Fri, 31 Mar 2000 21:04:03 GMT
Mok-Kong Shen wrote:
>
> Jim Reeds wrote:
> >
>
> > From personal communication with Teledyne people, & from
> > reading some Teledyne papers, I know what "orthomorphism"
> > means. A permutation f of the elements of a group
> > is an orthomorphism if the function g(x):=f(x)+x
...
>
> Do I understand correctly that x is a character of the input
> alphabet and f(x) is the corresponding character of the
> output alphabet? [...] could you please tell what are the essential
> advantages of the orthomorphism? ...
I've not looked at the patent, I don't know what the Teledyne
product is. A couple of years ago a Teledyne mathematician told
me he was working on orthomorphisms, and gave me copies of some
papers he had written. The algebraic definition stuck in my mind.
I don't know what the advantages of using orthomorphisms are,
neither in the Teledyne context nor otherwise. I'm not denying that
there might be advantages, I just don't know what they are.
Note that there is nothing stoping a linear function from being an
orthomorphism: if k is an element of GF(256), for instance, with
k not equal to 0 or 1, then f(x) := k*x is an orthomorphism.
Note that some groups don't have orthomorphisms. (Integers mod 10,
for instance.) I think the underlying formula for computation of
check digits on serial numbers on German paper currency is based
on an orthomorphism of the dihedral group D_5. But I don't think
the standard expositions of the checksum formula use the term
"orthomorphism."
--
Jim Reeds, AT&T Labs - Research
Shannon Laboratory, Room C229, Building 103
180 Park Avenue, Florham Park, NJ 07932-0971, USA
[EMAIL PROTECTED], phone: +1 973 360 8414, fax: +1 973 360 8178
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Proof of Identity
Date: 31 Mar 2000 21:23:40 GMT
In article <[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>One idea [while sitting in algebra] for proving that you were present at
>something [or wrote a book, etc] is to embed simple system of equations
>like
>
>11a + 3b - 9c = -927
>-5a - 11b + 7c = 1561
>..
>
>And not give the last equation. Of course the last solution will give
>out the values (a, b, c). The ability to give out the last eqn' or the
>set (a, b, c) proves that you wrote the first two equations. So that
>if you add those two lines to your document you can later prove you
>wrote.
>
>One major problem is that you can prove that only once. Then they can
>say they wrote it. Any thoughts?
It's worse than that. If a,b,c are known, you can write an equation.
If a,b,c are unknown, then why mess with equations? Just reveal a,b,c
and show how it's special (e.g. it's your social insurance number).
A crypto version of what you seem to be thinking of is you write down
the hash of something, H(x). Then prove later that you wrote it, by
revealing x.
>Question, is it possible to calc the gcd(x, y) mod a number? So that if
>I do 5x mod 11, can I tell if it's a multiple of 5? I don't think you
>can, just wondering.
No of course not. Try x=10 and x=21.
>[btw the solution to the above system is my Social Insurance Number [I
>was really bored in class]].
Tom I think you ought to start reading some real math books. Forget
about Bob's suggestion of Cohen's book on algebraic number theory, which
is a graduate text. But you might look at Koblitz's book I've mentioned.
Another suggestion (less cryptography specific) is "Concrete Mathematics"
by Knuth, Graham, and Patashnik. It will give you a good math background
for computer science.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Coderpunks Query on Teledyne Crypto
Date: Fri, 31 Mar 2000 21:32:58 GMT
Jim Reeds <[EMAIL PROTECTED]> wrote, in part:
>I think the underlying formula for computation of
>check digits on serial numbers on German paper currency is based
>on an orthomorphism of the dihedral group D_5.
While Social Security Numbers (and Social Insurance Numbers in Canada)
and many credit cards have check digits whose algorithms are public
knowledge, what on earth would the point be of a check digit on
currency except one whose derviation was kept secret?
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (mark carroll)
Subject: Re: Proof of Identity
Date: 31 Mar 2000 21:31:35 GMT
In article <[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>One idea [while sitting in algebra] for proving that you were present at
>something [or wrote a book, etc] is to embed simple system of equations
>like
>
>11a + 3b - 9c = -927
>-5a - 11b + 7c = 1561
>..
>
>And not give the last equation. Of course the last solution will give
>out the values (a, b, c). The ability to give out the last eqn' or the
>set (a, b, c) proves that you wrote the first two equations. So that
>if you add those two lines to your document you can later prove you
>wrote.
(snip)
a = 12, b = -92, c = 87?
Just an idea. It's not much of a proof that I wrote the first two
equations, though. (-:
It's an interesting idea. Some of your articles are well worth
reading. Thanks for posting.
-- Mark
------------------------------
Date: Fri, 31 Mar 2000 17:30:41 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: LFSR's
Pascal JUNOD wrote:
> Let be the irreducible polynom x^63 + x + 1 over GF(2).
> It describes a LFSR (linear feedback shift register), which is pretty
> easy to
> implement in software.
>
> Let's just speak about the period, not about the cryptographic security
> of the generated bits.
>
> The polynomial being irreducible, it produces a sequence of bits
> (normally the lsb of each states) with a period of 2^64 -1.
An irreducible polynomial is necessary but not sufficient for maximal period
(2^N-1). A primitive polynomials the requirement for max period. All
primitives are irreducible.
>
>
> Now, instead of taking the lsb, we could take bit #56 or #2 or any one
> of the 64
> bits of the internal state.
>
> All these possible sequences have a period of 2^64 - 1,or am I wrong ?
No, most of those periods are shorter than 2^64-1 because most of the
corresponding polynomials are not primitive.
>
>
> Now, if we output the whole internal state, we produce a sequence of
> 2^64 - 1
> values of 64 bits each, or 64*(2^64-1) bits. Am I right ?
Sort of. Each 64-bit output from such a generator contains 63 bits from the
previous output plus one new bit.
>
>
> What is the period of such a sequence, if we look at it as a _bit_
> sequence ?
2^64-1 if the corresponding polynomial is primitive. Each time the LFSR is
clocked it (logically) shifts out a single bit. After <period> clocks the
LFSR will contain the initial state, and the output sequence repeats.
You can arrange for N bits of "new" output on each clock. In that case you'll
have a sequence of 2^N-1 distinct N-bit outputs. The period will be 2^N-1,
after which the LFSR will be back in the original state and so start repeating
the sequence.
Since testing 2^64 states is tedious I suggest you experiment with 32-bit
registers. Here is pseudo-C code that will generate 31 "new" bits of output
on every iteration. A similar technique works for 63-bit values if your
compiler supports such a data type (e.g., long long or __int64).
static long seed = __LINE__;
extern long random( void )
{
assert( seed > 0 );
seed ^= ( seed & 7 ) << 28; // 30:2 LFSR
seed ^= seed >> 3;
return( seed );
}
If you want very long periods and very fast generation the 521/32 LFSR can be
implemented without shifts or rotates and works at memory speed on a 32-bit
machine because all of the data transfers are 32 bits wide.
------------------------------
Date: Fri, 31 Mar 2000 17:33:58 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: LFSR's
Tim Tyler wrote:
> Pascal JUNOD <[EMAIL PROTECTED]> wrote:
>
> : [...] irreducible polynom x^63 + x + 1 over GF(2) [...based LFSR]
>
> : Let's just speak about the period [...]
>
> : The polynomial being irreducible, it produces a sequence of bits
> : (normally the lsb of each states) with a period of 2^64 -1.
>
> : Now, instead of taking the lsb, we could take bit #56 or #2 or any one
> : of the 64 bits of the internal state.
>
> : All these possible sequences have a period of 2^64 - 1,or am I wrong ?
>
> You're right.
How do you figure this? Those polynomials are not all primitive.
>
>
> : Now, if we output the whole internal state, we produce a sequence of
> : 2^64 - 1 values of 64 bits each, or 64*(2^64-1) bits. Am I right ?
>
> Yes.
>
> : What is the period of such a sequence, if we look at it as a _bit_
> : sequence ?
>
> *Probably* n x (2^n - 1) = 64 x (2^64 - 1) in this case.
> In general, the chances of this period being attained are probably
> greatest when (2^n - 1) and n are prime.
> --
> __________ Hexagonal Engineering http://hex.org.uk/ [EMAIL PROTECTED]
> |im |yler Lotus Artificial Life http://alife.co.uk/ Be good,
> The Mandala Centre http://mandala.co.uk/ do good.
------------------------------
Date: Fri, 31 Mar 2000 17:36:34 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: LFSR's
Christof Paar wrote:
> On Fri, 31 Mar 2000, Tim Tyler wrote:
>
> > Pascal JUNOD <[EMAIL PROTECTED]> wrote:
> >
> > : [...] irreducible polynom x^63 + x + 1 over GF(2) [...based LFSR]
> >
> > : Let's just speak about the period [...]
> >
> > : The polynomial being irreducible, it produces a sequence of bits
> > : (normally the lsb of each states) with a period of 2^64 -1.
>
> Irreducibility is not sufficient. You want what's called a "primitive
> polynomial". All primitive polynomials are irreducible, though.
> Non-primitive but irreducible polynomials give you sequence shorter than
> 2^m-1. For example, x^4+x^3+x^2+x+1 is irreducible but generates an LFSR
> sequence of length 5, independent of the start vector. The primitve
> polynomial x^4+x+1 yields a maximum length sequence with period 15.
>
> Luckily, most tables in the coding/cryptography field contain primitive
> polynomials anyway.
>
> >
> > : Now, instead of taking the lsb, we could take bit #56 or #2 or any one
> > : of the 64 bits of the internal state.
> >
> > : All these possible sequences have a period of 2^64 - 1,or am I wrong ?
> >
> > You're right.
> >
> > : Now, if we output the whole internal state, we produce a sequence of
> > : 2^64 - 1 values of 64 bits each, or 64*(2^64-1) bits. Am I right ?
> >
> > Yes.
>
> Just a word of warning: Two subsequent 63 bits (if you choose 2^63+x+1,
> not 64) words are very similar, as they are essentially shifted versions
> of each other. The only difference is the MSB.
This is true of the classic implementation, but it is not hard to produce N
bits of output from each clock of the register, especially if the register
fits in a built-in data type, such as a 64-bit word.
------------------------------
From: Jim Reeds <[EMAIL PROTECTED]>
Subject: Re: Coderpunks Query on Teledyne Crypto
Date: Fri, 31 Mar 2000 22:22:39 GMT
John Savard wrote:
>
> Jim Reeds <[EMAIL PROTECTED]> wrote, in part:
> While Social Security Numbers (and Social Insurance Numbers in Canada)
> and many credit cards have check digits whose algorithms are public
> knowledge, what on earth would the point be of a check digit on
> currency except one whose derviation was kept secret?
I didn't say it was secret. The check digits on German paper
currency have the property that they detect all single-digit errors
and transpositions of adjacent digits, and (unlike the scheme
used by ISBN numbers, which requires occasional use of the extra-
digital symbol X) they are digits. This cannot be done with
simple mod 10 checksum equations, but can be done -- it turns out --
with orthomorphisms. (The ISBN check sum takes the mod 11 cop-out.)
The recipe is publicly known, but a bit complicated.
See the note by Joseph Gallian, ``Math on Money.'' {\it Math Horizons}
November 1995, pp. 10-11. (There are better references, but I am too
lazy to dig one out of my filing cabinet now.)
In the 1920's, 5-letter telegraphic code books used mod 25 or mod 27
check sum equations to protect the code words from single letter
"mutilation" and from transposition of adjacent letters, but neither
is as efficient (from the point of view of maximizing the number of
legal codewords) as the method used by the German currency numbers.
(The difficulty is that the equations 2x = 0 can have non zero solutions
mod 10 or mod 26.)
Jim Reeds, AT&T Labs - Research
Shannon Laboratory, Room C229, Building 103
180 Park Avenue, Florham Park, NJ 07932-0971, USA
[EMAIL PROTECTED], phone: +1 973 360 8414, fax: +1 973 360 8178
------------------------------
From: "Adam Durana" <[EMAIL PROTECTED]>
Subject: Re: LFSR's
Date: Fri, 31 Mar 2000 17:34:38 -0500
> Now, instead of taking the lsb, we could take bit #56 or #2 or any one
> of the 64
> bits of the internal state.
You could but I think that would complicate the process, programming wise
that is. The key word here is shift, shift right one bit, take xor of the
taps and put that value in the msb (since the msb is zero because of the
right shift), then you take the lsb. Now for example if you took the 5th
bit, you'd have to "pull" out that 5th bit, and shift over one place to the
right to fill that gap, take the xors of the taps and put it in the msb,
then take the 5th bit. So its easier to just take the lsb since with a 1
bit shift to the right that bit is droped.
> Now, if we output the whole internal state, we produce a sequence of
> 2^64 - 1
> values of 64 bits each, or 64*(2^64-1) bits. Am I right ?
Yes this is true, but each value would be the previous value shifted one bit
to the right with a new msb (from the xor of the taps). If you are trying
to generate 64bit words using an lfsrs I would suggest you run 64 lfsrs in
parallel. Something else you might want to look into are lfsrs in Galois
configuration, its in Applied Crypto.
- Adam
------------------------------
Date: Fri, 31 Mar 2000 17:44:12 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited.
Are you going to send him an invoice for the time you spent on his software or are
you going perform another analysis when he fixes the problem you've demonstrated?
Taneli Huuskonen wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> In <[EMAIL PROTECTED]> Anthony Stephen Szopa
> <[EMAIL PROTECTED]> writes:
>
> [...]
> >Introduction then we will proceed with Mr. Huuskonen's point about
> >the random number generator possibly having a weakness.
>
> Strike the "possibly" - it does have a weakness, and below you can
> find the code that I wrote to verify my own reasoning. You need to
> supply a routine that either directly computes the random digit at the
> given index or reads it from a file. It's the first function in the
> programme.
>
> Taneli Huuskonen
>
> #include <stdio.h>
> #include <stdlib.h>
>
> #define FAC10 3628800 /* 10! */
> #define BLOCKLEN 1000 /* can be
> #define NBLOCKS 100 /* 100 is enough
> #define UNKNOWN '?'
>
> /*
> * The known output of the PRNG is stored here.
> * New known values are added as they are found out.
> */
>
> char oap[ BLOCKLEN+NBLOCKS ][ BLOCKLEN ];
>
> /* The following function returns the ASCII code for the
> * (i * FAC10 + j)'th digit that is output by the PRNG
> * (beginning with the 0'th).
> * It is used both to initialize the known values in the array
> * and to check the results of the cracking algorithm.
> */
>
> char oapfun( unsigned i, unsigned j )
> {
> XXXXXX
> }
>
> /* The following function inserts NBLOCKS blocks of BLOCKLEN known
> * digits into the array oap, and fills the rest of the array
> * with the code for unknown values.
> */
>
> void init_oap( void )
> {
> unsigned i, j;
>
> for (i=0; i<NBLOCKS; i++) {
> for (j=0; j<BLOCKLEN; j++) {
> oap[ i ][ j ] = oapfun( i, j );
> }
> }
>
> for (i=NBLOCKS; i<NBLOCKS+BLOCKLEN; i++) {
> for (j=0; j<BLOCKLEN; j++) {
> oap[ i ][ j ] = UNKNOWN;
> }
> }
> }
>
> /* This function handles a single inference of the form
> * "The values at b1 * 10! + offset and b2 * 10! + offset
> * are the same."
> * It verifies its correctness and then checks whether this
> * piece of information yields a new known output digit.
> */
>
> void infer_oap( unsigned b1, unsigned b2, unsigned offset )
> {
> if (oapfun( b1, offset ) != oapfun( b2, offset )) {
> /* Wrong inference?? that's a fatal error! */
> fprintf(stderr, "BUG: b1=%u, b2=%u, o=%u\n", b1, b2, offset );
> exit( 1 );
> }
>
> /* The inference is correct - did we get any new information? */
> if ((oap[ b1 ][ offset ] == UNKNOWN) && (oap[ b2 ][ offset ] != UNKNOWN)) {
> oap[ b1 ][ offset ] = oap[ b2 ][ offset ];
> printf( "oap[ %5u ][ %5u ] = %c\n", b1, offset, oap[ b1 ][ offset ] );
> }
> }
>
> /* The name tells it all. */
>
> void crack_oap( )
> {
> unsigned i, j, k, l;
>
> for (i=10; i<BLOCKLEN; i++) {
> for (j=0; j<NBLOCKS-10; j++) {
> for (k=j+10; k<NBLOCKS; k+=10) {
> if (oap[ k ][ i ] == oap[ j ][ i ]) {
> for (l=10; l<=i; l+=10) {
> infer_oap( k+l, j+l, i-l );
> }
> }
> }
> }
> }
> }
>
> int main( )
> {
> init_oap( );
> crack_oap( );
>
> return 0;
> }
>
> -----BEGIN PGP SIGNATURE-----
> Version: PGPfreeware 5.0i for non-commercial use
> Charset: noconv
>
> iQA/AwUBOOToIl+t0CYLfLaVEQK5rQCfTmq96cayKhUE0mYiQP2TLGLpjDMAnRa9
> /QuIudgQ/LkBocp/QArLjfop
> =F1da
> -----END PGP SIGNATURE-----
> --
> I don't | All messages will be PGP signed, | Fight for your right to
> speak for | encrypted mail preferred. Keys: | use sealed envelopes.
> the Uni. | http://www.helsinki.fi/~huuskone/ | http://www.gilc.org/
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: LFSR's
Date: Fri, 31 Mar 2000 17:14:03 -0500
Pascal JUNOD wrote:
>
> Let be the irreducible polynom x^63 + x + 1 over GF(2).
> It describes a LFSR (linear feedback shift register), which is pretty
> easy to
> implement in software.
>
> Let's just speak about the period, not about the cryptographic security
> of the generated bits.
>
> The polynomial being irreducible, it produces a sequence of bits
> (normally the lsb of each states) with a period of 2^64 -1.
>
> Now, instead of taking the lsb, we could take bit #56 or #2 or any one
> of the 64
> bits of the internal state.
>
> All these possible sequences have a period of 2^64 - 1,or am I wrong ?
Right. But keep in mind that those sequences are simply shifted copies
of the same basic sequence: the sequence at bit #2 is simply one clock
offset from the sequence at bit #1.
> Now, if we output the whole internal state, we produce a sequence of
> 2^64 - 1
> values of 64 bits each, or 64*(2^64-1) bits. Am I right ?
No -- because the bits are not independent.
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
******************************
