Cryptography-Digest Digest #57, Volume #12 Sun, 18 Jun 00 19:13:00 EDT
Contents:
Re: Observer 4/6/2000: "Your privacy ends here" (JimD)
Re: On using compression as proper means of encryption (Mok-Kong Shen)
Re: Q: Equally like bit-flips in a Gray code? (Mok-Kong Shen)
Re: Private key encryption that maintain length of plain text? ("Benny Nissen")
Re: XOR versur MOD (tomstd)
Re: XOR versur MOD (Mok-Kong Shen)
Re: AWFUL PUN (was: Why the golden ratio?) (Jeremy Boden)
Re: AWFUL PUN (was: Why the golden ratio?) ([EMAIL PROTECTED])
Re: XOR versur MOD (tomstd)
Re: small subgroups in Blum Blum Shub (Bryan Olson)
Re: Extending LFSR...... (Joaquim Southby)
Re: Weight of Digital Signatures (John Bailey)
Re: XOR versur MOD (Simon Johnson)
Re: LSFR (Joaquim Southby)
Re: On using compression as proper means of encryption (Guy Macon)
Re: Extending LFSR...... (tomstd)
Re: Q: Equally like bit-flips in a Gray code? (Guy Macon)
Re: Small compression/encryption problem (Guy Macon)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (JimD)
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.security.scramdisk,uk.telecom
Subject: Re: Observer 4/6/2000: "Your privacy ends here"
Date: Sun, 18 Jun 2000 17:21:47 GMT
Reply-To: JimD
On Fri, 16 Jun 2000 12:03:48 +0100, "Darren Rhodes" <[EMAIL PROTECTED]>
wrote:
>I tried to access the Shayler web site listed below but could not. This was
>said to be due to an HTTP error 403 - Forbidden.
>Has anyone had a similar experience?
>Is this due to my ISP Globalnet?
Ask Globalnet. If you don't get a satisfactory answer,
ditch them. (And post your results here, of course).
--
Jim Dunnett.
g4rga at thersgb.net
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On using compression as proper means of encryption
Date: Sun, 18 Jun 2000 20:40:36 +0200
"John A. Malley" wrote:
> I recommend Mojdeh Mohtashemi's Master's Thesis "On the Cryptanalysis of
> Huffman Codes."
> She provides some general results on the difficulty of the
> cryptanalysis.
>
> http://theory.lcs.mit.edu/~cis/theses/mohtashemi-masters.ps
As far as I understand, M. Motashemi's MIT thesis dealt with
the normal (not adaptive) Huffman compression algorithm and
considered means of identifying the form/structure of the
coding tree used through checking the decompressed results
obtained from all possible coding trees by examining how
well the frequencies of such results correspond to (are
compatible with) the ordering of frequencies implied by the
form/structure of the respective coding trees. It was shown
that the analysis could be very hard, if the source
frequency distribution is nearly flat and particularly when
the tree is large, which is a result that certainly also
well conforms to one's intuitive expectations. BTW, it is
to be noted that, as mentioned in the thesis, the actual
identification of the mapping of the symbols to the nodes
of the coding tree, which is a task that the analyst has to
perform additionally, was not considered.
In our scheme, after initialization, the internal frequency
table has nothing to do with the actual frequency
distribution of the plaintext at all. This and the fact that
we are using an adaptive Huffman, i.e. with a non-constant
table, evidently renders the prospect of success of the
analyst more sombre than that discussed in the thesis.
My proposal to dynamically inject random bits into the
output stream further significantly drives any location of
the groups of bits (that together form proper output symbols
of the adaptive Huffman algorithm) far into the realm of
guesswork of the opponent.
As previously pointed out, pathological cases of input, e.g.
a file of all zeros, can be taken care of through a
frequency flattening step. Since a PRNG is already used in
our scheme, it is simplest and natural to do this through
combining the plaintext with random bit sequences from the
PRNG (xor or modular addition).
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Equally like bit-flips in a Gray code?
Date: Sun, 18 Jun 2000 20:49:01 +0200
M Joonas Pihlaja wrote:
> I'm trying to find a Gray code in which each bit is 'equally
> likely' to change between adjacent code words. Well, more likely
> than in the the usual (ix+1)^(ix>>1) code at least. That changes
> the lower k bits before it gets to bit k.
I doubt that you would get a solution. My pessimistic guess is based
on the general fact that if one puts too many constraints to an
optimazation
problem then one is likely to get nowhere in practice.
M. K. Shen
------------------------------
From: "Benny Nissen" <[EMAIL PROTECTED]>
Subject: Re: Private key encryption that maintain length of plain text?
Date: Sun, 18 Jun 2000 18:46:49 GMT
"tomstd" <[EMAIL PROTECTED]> skrev i en meddelelse
news:[EMAIL PROTECTED]...
> "World Online" <[EMAIL PROTECTED]> wrote:
> >Hi
> >
> >I am pretty new to asymetric encryption, so it may be a stupid
> question!
> >I have a special application in mind where I operate with very
> small (in
> >byte length) plain text documents and I would also like to keep
> the
> >encrypted document as small as possible. I have made some test
> applications
> >with RSA and I see that the encrypted documents (private key)
> with a modulus
> >size of 512 bits get to become twice the size of the plain text
> document
> >(increase with bigger modulus sizes).
> >
> >Are there any public key encryption algorithems that maintain
> the same size
> >encrypted as decrypted (as with most block cifers).
> >
> >The plain text document will be known, and also the public key
> will be
> >known. Then a test will see if the encrypted version match the
> plain text
> >version.
>
> Not really (from your perspective). Most asymmetric methods are
> based on number theoretic problems (factoring, discrete
> logarithm) and are only secure if large numbers (fields, curves,
> etc..) are used.
>
> In reality however, with a 1024-bit RSA key (for example) your
> plaintext and ciphertext are always 1024 bits, no more no less.
> So in this sense it never expands.
>
> I can see if you want to encrypt only 20 bytes with a 1024-bit
> key this could be viewed as an expansion but theoretically it
> isn't.
>
> IOW you can't get small block sizes using current methods
> without sacrificing security.
>
> Tom
>
Thanks for the info.
Benny
------------------------------
Subject: Re: XOR versur MOD
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 18 Jun 2000 12:36:03 -0700
[EMAIL PROTECTED] (Mack) wrote:
>Simon Johnson wrote:
>>Security wise there is no difference.
>>
>>It has been pointed out that XOR is the addition of bits at the
>>same level of significance mod 2 anyway, it must therefore be
of
>>equal security to addition mod n. However XOR is self inverse,
>>so is simpler to use.
>>
>>Got questions? Get answers over the phone at Keen.com.
>>Up to 100 minutes free!
>>http://www.keen.com
>>
>>
>
>addition modulo greater than two may have different
>security than XOR (addition modulo 2). Just
>depends on the cipher. DES with addition modulo 32
>is weaker than with XOR (someone wrote a paper
>back in the 80s). RC5 is probably stronger with addition
>modulo word size than with XOR (haven't seen an
>analysis just a gut feeling). The main difference
>between the two is at the hardware level.
>XOR is easier to implement.
RC5 is not more secure because of the use of addition (although
the alternating add/xor does make rotations secure) it's more
secure because of the rotations.
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: XOR versur MOD
Date: Sun, 18 Jun 2000 22:41:08 +0200
Simon Johnson wrote:
> equal security to addition mod n. However XOR is self inverse,
> so is simpler to use.
How much more simplicity is there really? (The inverse of addition is
simply subtraction).
M. K. Shen
------------------------------
From: Jeremy Boden <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: AWFUL PUN (was: Why the golden ratio?)
Date: Sun, 18 Jun 2000 14:23:43 +0100
In article <[EMAIL PROTECTED]>, G. A.
Edgar <[EMAIL PROTECTED]> writes
>>> it is due to Srinavasa Ramanujan...
>>
>> >Oh, dear: that should be Srinivasa Ramanujan.
>
>There are no vowels in Sanscrit, so we cannot criticize you for this.
Not so; there are 2 vowels in Sanscrit.
--
Jeremy Boden
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: AWFUL PUN (was: Why the golden ratio?)
Date: 18 Jun 2000 21:30:40 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Jeremy Boden) wrote:
> Not so; there are 2 vowels in Sanscrit.
Not so, there are 2 versions of a, i, u, r, l plus e, ai, o and au.
(l and r are classed as semi-vowels). 14 in total.
See: Sanscrit-English Dictionary by Monier-Williams.
Keith
http://www.cix.co.uk/~klockstone
------------------------
'Unwise a grave for Arthur'
-- The Black Book of Carmarthen
------------------------------
Subject: Re: XOR versur MOD
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 18 Jun 2000 14:54:24 -0700
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
>Simon Johnson wrote:
>
>> equal security to addition mod n. However XOR is self inverse,
>> so is simpler to use.
>
>How much more simplicity is there really? (The inverse of
addition is
>simply subtraction).
I think he meant that you can just use the same routine to
decrypt/encrypt.
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Date: Sun, 18 Jun 2000 21:50:35 GMT
Terry Ritter wrote:
> anon wrote:
> >Take a look at:
> >http://x61.deja.com/[ST_rn=ps]/getdoc.xp?AN=572282072
>
[...]
> Oddly for useless advice, the last 2/3 of the BB&S published article
> concerns just this issue. [...]
That is not how to read a scientific or mathematical
paper. To draw conclusions, one must understand the
math not count the words.
I presented the same mathematical argument as Anon in:
http://x68.deja.com/[ST_rn=ps]/getdoc.xp?AN=494536680
and asked:
| Is anything wrong with the following argument? It shows
| that under the assumption that factoring Blum integers is
| hard, short cycles are of no concern.
To which Ritter replied:
: I am not qualified to judge the argument about the
: probability of short cycles, so I assume it is
: correct. What I would call wrong is what that means: [...]
[...]
> >It would be a miracle if we could get agreement on this issue though.
> >Every time it comes up, the falsehoods fly.
>
> Then I suggest that you follow the discussion and point out those
> falsehoods in detail.
I think the most important misconception to correct is
the notion that the reason the standard references, such as
/Handbook of Applied Cryptography/ do not state that one
should apply the cycle-length filter from the BBS paper
is out of laziness or ignorance. That is of course not
the case. The authors of HAC were not limited to judging
results by volume of text.
[...]
> Instead, the discussion here is about the concept of "proof" itself:
> I claim that if it is *POSSIBLE* to select a short cycle, it should be
> self-evident that any *proof* of security must be false. The
> alternative is a clear logic error -- an actual reasoning fault.
The beauty of probability is that it enables us to
reason with mathematical certainty even as chance
plays upon the subjects of our reasoning.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Joaquim Southby <[EMAIL PROTECTED]>
Subject: Re: Extending LFSR......
Date: 18 Jun 2000 22:02:49 GMT
In article <[EMAIL PROTECTED]> tomstd,
[EMAIL PROTECTED] writes:
>>There might be some confusion in how terms are used. For a
>maximal
>>period LFSR, the polynomial formed from the tap sequence plus 1
>is a
>>primitive polynomial. The degree of the polynomial is the
>length of the
>>shift register. For the polynomial you gave, the shift
>register is 4
>>bits long, so the degree of the polynomial is 4.
>
>That isn't right because you really have
>
>x^4 + x^2 + x + 1 = 1x^4 + 0x^3 + 1x^2 + 1x^1 + 1x^0 or 10111
>which is a five bit digit. A 4 bit LFSR must have a modulus of
>degree 4 but a primitive element of degree 3.
>
Read what I said again: "...the polynomial formed from the tap sequence
PLUS 1..." An LFSR with a tap sequence of 30, 5, 3, 1 translates to a
characteristic polynomial mod 2 of x^30 + x^5 + x^3 +x + 1. A tap
sequence of 4,3 on a 4 bit LFSR yields x^4 + x^3 +1. The degree of the
first polynomial is 30; that of the second is 4.
In the example you gave, the polynomial x^4 + x^2 + x + 1 produces a tap
sequence of 4,2,1 in a 4 bit LFSR. (That tap sequence produces a
poorly-behaved LFSR, but that's another discussion.) The taps for the
feedback function are taken from the first, second and fourth bits.
I'm not sure what you're getting at by collecting the coefficients of the
characteristic polynomial and calling it a "five bit digit". That
"digit" simply transmits the information of what bits to use as taps;
furthermore, the last bit is entirely superfluous -- a primitive
polynomial mod 2 will always have that bit set.
Again, I don't know how you are using the term "modulus" or "primitive
element" in respect to an LFSR, so I can't directly answer the second
statement.
------------------------------
From: [EMAIL PROTECTED] (John Bailey)
Subject: Re: Weight of Digital Signatures
Date: Sun, 18 Jun 2000 22:14:13 GMT
On Sat, 17 Jun 2000 19:52:13 GMT, Greg <[EMAIL PROTECTED]> wrote:
>
>
> WASHINGTON, June 16 -- The Senate voted unanimously
> today to approve a bill that catapults electronic
> commerce to a new level by allowing consumers and
> businesses to sign contracts online and know that
> their e-signature is just as binding as one in ink.
This was a direct quote from the NY Times but it seems to be wrong.
http://search3.nytimes.com/search/daily/bin/fastweb?getdoc+cyber-lib+cyber-lib+11700+2+wAAA+signature
What passed in the Senate on Friday was agreement on the conference
report regarding Senate 761, the bill in question. The bill itself
has yet to be passed.
quoting the results of a query to
http://rs9.loc.gov/cgi-bin/bdquery/z?d106:SN00761:@@@S
(quote)
Senate agreed to conference report by Yea-Nay Vote. 87 - 0. Record
Vote Number: 133.
(end quote)
http://rs9.loc.gov/cgi-bin/bdquery/z?d106:s.00761: will yield
information about the bill, its rationale, and the line-up of
supporters.
John
------------------------------
Subject: Re: XOR versur MOD
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Sun, 18 Jun 2000 15:13:54 -0700
>How much more simplicity is there really? (The inverse of
>addition is
>simply subtraction).
In additon mod n, two operators are required for encryption and
decryption
i.e. a=(b+k) mod n (requires the knowledge of the operator '+')
b=(a-k) mod n (requires the knowledge of the operator '-')
So we need two operators to encrypt and decrypt.
With XOR:
a = b XOR K
b = a XOR K
Which requires the knowledge of one operator for both encryption
and decryption.
So, to answer your question, XOR is exactly one
operator 'simpler' than addition and subtraction mod n. :P
>M. K. Shen
>
>
>
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: Joaquim Southby <[EMAIL PROTECTED]>
Subject: Re: LSFR
Date: 18 Jun 2000 22:26:00 GMT
In article <[EMAIL PROTECTED]> Simon Johnson,
[EMAIL PROTECTED] writes:
>Looking at a basic LSFR, they don't look all too secure. The
>reason i say this is the whole key is spat out for the first n
>clocks, where n is the size in bits of the Register?
>
>Why is this secure?
>
An LFSR on its own is not that secure. There have been some papers
showing that if 2n bits of an n bit LFSR are known, the whole register
can be reconstructed. However, if you combine LFSR's in some fashion
such as a Gollmann cascade (use at least 20 registers) or a bilateral
stop and go generator, their security is greatly strengthened. Using
dense feedback polynomials also helps to enhance the security.
As for the key being seen, it's the nature of a maximal length shift
register that every number in its non-zero state space will appear in its
output during its period. It's sometimes more comforting to think of the
key as the initialization vector.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: On using compression as proper means of encryption
Date: 18 Jun 2000 18:34:21 EDT
Mok-Kong Shen wrote:
>
>As previously pointed out, pathological cases of input, e.g.
>a file of all zeros, can be taken care of through a
>frequency flattening step. Since a PRNG is already used in
>our scheme, it is simplest and natural to do this through
>combining the plaintext with random bit sequences from the
>PRNG (xor or modular addition).
>
Wouldn't that stop the compression step from compressing?
------------------------------
Subject: Re: Extending LFSR......
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 18 Jun 2000 15:42:43 -0700
Joaquim Southby <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]> tomstd,
>[EMAIL PROTECTED] writes:
>>>There might be some confusion in how terms are used. For a
>>maximal
>>>period LFSR, the polynomial formed from the tap sequence plus
1
>>is a
>>>primitive polynomial. The degree of the polynomial is the
>>length of the
>>>shift register. For the polynomial you gave, the shift
>>register is 4
>>>bits long, so the degree of the polynomial is 4.
>>
>>That isn't right because you really have
>>
>>x^4 + x^2 + x + 1 = 1x^4 + 0x^3 + 1x^2 + 1x^1 + 1x^0 or 10111
>>which is a five bit digit. A 4 bit LFSR must have a modulus of
>>degree 4 but a primitive element of degree 3.
>>
>Read what I said again: "...the polynomial formed from the tap
sequence
>PLUS 1..." An LFSR with a tap sequence of 30, 5, 3, 1
translates to a
>characteristic polynomial mod 2 of x^30 + x^5 + x^3 +x + 1. A
tap
>sequence of 4,3 on a 4 bit LFSR yields x^4 + x^3 +1. The
degree of the
>first polynomial is 30; that of the second is 4.
>
>In the example you gave, the polynomial x^4 + x^2 + x + 1
produces a tap
>sequence of 4,2,1 in a 4 bit LFSR. (That tap sequence produces
a
>poorly-behaved LFSR, but that's another discussion.) The taps
for the
>feedback function are taken from the first, second and fourth
bits.
>
>I'm not sure what you're getting at by collecting the
coefficients of the
>characteristic polynomial and calling it a "five bit digit".
That
>"digit" simply transmits the information of what bits to use as
taps;
>furthermore, the last bit is entirely superfluous -- a primitive
>polynomial mod 2 will always have that bit set.
>
>Again, I don't know how you are using the term "modulus"
or "primitive
>element" in respect to an LFSR, so I can't directly answer the
second
>statement.
That's just it my friend. a LFSR is not a magical tap sequence
thingy... it's MULTIPLICATION IN A GALOIS FIELD!!!!
Similar in style to a Linear Congruetial Generator ax + c
where 'c' is zero.
My question is what is the modulus... I think it's just x^(n+1)
+ 1, so the modulus for the 4 bit LFSR is x^5 + 1 (but that
isn't primitive) or something like that.
If you look at the code that does a GF style LFSR and look at
actual GF multiplication you will find a starting relationship.
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Q: Equally like bit-flips in a Gray code?
Date: 18 Jun 2000 18:44:55 EDT
M Joonas Pihlaja wrote:
>I hope this is the appropriate forum for this type of question.
>
>Hi,
>
>I'm trying to find a Gray code in which each bit is 'equally
>likely' to change between adjacent code words. Well, more likely
>than in the the usual (ix+1)^(ix>>1) code at least. That changes
>the lower k bits before it gets to bit k.
>
>I need to uniformly sample the key space of a cipher and was
>going to use a Sobolev sequence, but noticed that a Gray code
>would allow for some optimisations.
Here is how to get as close as you can get for a 0 to 9 code.
[1] Some random bit sequence = 0
[2] Flip a random bit.
Result = 1
[3] Flip a random bit.
Discard and repeat if result is already in use.
Result = 2
(Repeat until you reach 9)
I doubt that this will be good enough for you.
Making a gray code for 0 to 15 (or any other encoding where the
total number of codes is a power of 2) might suit you better.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Crossposted-To: comp.compression
Subject: Re: Small compression/encryption problem
Date: 18 Jun 2000 18:54:40 EDT
Rickman wrote:
>
>Richard John Cavell wrote:
>>
>> A set of data needs to be encoded and transferred in a nonsecure manner to
>> an operator, who will type the encrypted data into a computer program
>> manually. The operator (who has no particular skill in programming) must
>> be unable to easily decipher what the data is. Errors in
>> typing/transferring the data must be made impossible or very unlikely.
>>
>> The data (which is actually a multiple choice exam):
>>
>> A twenty-character alphanumeric string, which may contain punctuation.
>> Alpha characters are far more likely.
>>
>> Either twenty or forty values of 1, 2, 3, 4. The value 4 is significantly
>> less likely to appear than any of the first 3.
>>
>> My solution:
>>
>> Encode the string by mapping all the available alphanumeric characters
>> against random others, then exchanging, rotating the key by one for each
>> successive character.
>>
>> Encode each answer as a 2-bit value. Squash them together and break the
>> resulting code up into base-32 values. Encode the values as alphanumeric
>> (36 possible characters, so leave 0/O and 1/I out of the possbilities).
>>
>> Lastly, a simple checksum of all the data encoded as 2
>> hexadecimal characters.
>>
>> Does anyone have a better idea?
>
>What you suggest could do the job well. But I can give you what should
>be a simpler approach. Take your input data (uncompressed text string of
>any form) and compress it by any of the conventional and redily
>available means. PKZIP will do nicely. Generate a bit pattern using a
>LFSR or other simple pseudo random number generator. XOR the compressed
>data with the bit pattern. This is your compressed, encrypted data. You
>may need to group it into 6 bit characters which are mapped to 64
>printable ascii characters. I would bet that with a little searching on
>the web for the random bit stream generator, you could reduce your
>programming effort to almost nothing.
>
>This may not provide NSA level security, but it will be more than useful
>enough for your application and you don't need to do a lot of coding.
This looks like a near ideal solution. I wouldn't go for 64 characters
on the basis of making things easy for the typist. I would use 16,
(specifically abcdefghjkprstuv) presented in groups of 4 characters.
------------------------------
** 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
******************************
