Cryptography-Digest Digest #746, Volume #12 Fri, 22 Sep 00 10:13:01 EDT
Contents:
Re: Tying Up Loose Ends - Correction (Tim Tyler)
Re: Tying Up Loose Ends - Correction (Tim Tyler)
Re: Tying Up Loose Ends - Correction (Tim Tyler)
Re: State-of-the-art in integer factorization (Jeffrey Williams)
Re: State-of-the-art in integer factorization (David Blackman)
Re: Tying Up Loose Ends - Correction (Mok-Kong Shen)
Re: Again a topic of disappearing e-mail? (Mok-Kong Shen)
Re: PGP 6.5.8 source code published ("M.B�deker")
Re: RSA public exponent ([EMAIL PROTECTED])
Re: Tying Up Loose Ends - Correction (SCOTT19U.ZIP_GUY)
Re: t ("John A. Malley")
Re: Revilo P. Oliver: Cryptanalyst? (John Savard)
Re: IBM analysis secret. (John Savard)
Re: t (John Savard)
Re: t (John Savard)
Re: My e-mail to Jim Gillogly -- YO, JIM!!!!!!!!!!??? (I'm annoyed at you) ("Kevin
N. Stone")
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Tying Up Loose Ends - Correction
Reply-To: [EMAIL PROTECTED]
Date: Fri, 22 Sep 2000 11:11:05 GMT
John Savard <[EMAIL PROTECTED]> wrote:
: On Wed, 20 Sep 2000 15:03:10 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
:>An alternative - which I've not seen discussed on this forum - would be
:>to use an encryption device which is capable of encrypting variable length
:>bitstrings, and is not confined to multiples of 8 bits. I attribute this
:>idea to David Scott.
: No, don't.
: Actually, encrypting that way is the 'default' idea. [...]
Hrumph.
Variable length cyphers that can accomodate strings of an arbitrary number
of bits are not terribly common - unless you count XOR based stream
cyphers - which I don't regard favourably in the first place.
Cyphers that can deal with fractional bitstream lengths are even less
common - the only one that I know of is the Hasty Pudding cypher.
[http://www.cs.arizona.edu/~rcs/hpc/] I'm sure there are others, but they
are the exception - rather than the rule.
Anyway - since I seem to have been misinterpreted - I'd better state that
the idea of using such an encryption scheme to resolve the
Huffman/Arithmetic file ending problem is (AFAIK) David's idea.
I have no illusions that he invented the idea of using encryption schemes
which can cope with variable numbers of bits. This isn't the first time
I've cited the Hasty Pudding cypher as being able to deal with very fine
file-length graduations.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Tying Up Loose Ends - Correction
Reply-To: [EMAIL PROTECTED]
Date: Fri, 22 Sep 2000 11:31:08 GMT
John Savard <[EMAIL PROTECTED]> wrote:
: Tim Tyler <[EMAIL PROTECTED]> wrote, in part:
:>If you want to obscure the length of the file from your adversary, as
:>much random padding as you like can be used at this stage.
: False. If padding is added *after* encryption, one has to [...]
: indicate where the padding starts in the clear so that decryption will
: act on the right bits.
That's true. You have to distinguish the message from the padding in some
way - regardless of where you do it. Doing it inside encryption has
some problems of its own.
: If the padding is genuinely random, adding it before encryption won't
: cause a security problem:
I agree - though there are still some problems distinguishing the padding
from the data, unless we're still talking about padding <8 bits onto the
end of a Huffman file.
If there are any other problems in this area, they are with the premise.
: [...] and does avoid the kinds of problem I was concerned with - the
: teensy bit of redundancy left in by a scheme aimed precisely at getting
: the last little teensy bit out.
I would still like to see a Huffman scheme with this type of padding
implemented, so I can verify experimentally that it does flatten out
the redundancy exactly - since any theoretical argument for it doing
so is not yet clear to me.
I certainly agree that padding with random partial Huffman symbols is
better than padding with zeros - in terms of flattening out the frequency
distribution of the last byte.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Tying Up Loose Ends - Correction
Reply-To: [EMAIL PROTECTED]
Date: Fri, 22 Sep 2000 11:47:35 GMT
John Savard <[EMAIL PROTECTED]> wrote:
:TT wrote:
:>If you want to obscure the length of the file from your adversary, as
:>much random padding as you like can be used at this stage.
: False. If padding is added *after* encryption, one has to [...]
: indicate where the padding starts in the clear so that decryption will
: act on the right bits.
I wonder if someone can help me here. I don't yet have clear views in
this area.
I would like to be able to articulate the criteria that a good packing
scheme to be applied before encryption should have - assuming that a
good random stream is available to do the padding with.
It seems to me that the issue is non-trivial. I believe a packing scheme
should be able to transform an arbitrary message into an arbitrary padded
message, from which the recipient should be able to recover the original
message unabmiguously - without any shared secret being involved.
It should also minimise the number of decrypts that form "impossible"
messages that can't possibly represent a padded message - for the same
sorts of reasons that David likes compression not to allow keys to be
rejected.
I'm undecided about whether the padding should be added in one place,
or should be distributed around in the hope of preventing attckers from
matching known-probable plaintexts with message sections.
I'm inclined to think that unkeyed transformations designed to thwart
known partial plaintexts are mainly a separate issue from padding schemes
- if you want to apply an AONT to help prevent known plaintext attacks
that choice is available to you.
Has this problem been studied? Are there padding schemes that do better
than (say) prepending a self-terminating length field to the start of
the message? This results in many "impossible" padded messages :-<
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Jeffrey Williams <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: State-of-the-art in integer factorization
Date: Fri, 22 Sep 2000 07:14:06 -0500
Would the Montgomery paper happen to be available on-line? And if so, could
someone please post a pointer to it?
LL&P
Jeff Williams
Bob Silverman wrote:
> In article <[EMAIL PROTECTED]>,
> JCA <[EMAIL PROTECTED]> wrote:
> >
> > I've got Peter Montgomery's excellent survey on integer
> > factorization
> > algorithms. However, being as it is five years old now I was wondering
> > if there is something more up to date out there. Or, at the very
> least,
> > and
> > addendum to this paper.
>
> Nothing has been written. Improvements have been only incremental.
> (i.e. slightly faster machines, a few more percent squeezed from
> code, etc.). There hasn't been a new algorithm in 11 years.
>
> --
> Bob Silverman
> "You can lead a horse's ass to knowledge, but you can't make him think"
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: State-of-the-art in integer factorization
Date: Fri, 22 Sep 2000 23:19:12 +1100
Tom St Denis wrote:
> Not to mention that virtually all milestones in factoring were public
> endeavours [sp].
Virtually all of the public milestones in factoring were public
endeavours. We don't know anything about secret algorithms that we don't
know anything about :-)
Conspiracy theorists should be just a bit worried that public progress
in factoring algorithms ground to a halt at about the same time that
factoring became relevant to real world cryptography applications, and
therefore interesting to our favourite three letter acronyms.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Tying Up Loose Ends - Correction
Date: Fri, 22 Sep 2000 14:44:56 +0200
Tim Tyler wrote:
>
> SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
> : [EMAIL PROTECTED] (Benjamin Goldberg) wrote:
> :>SCOTT19U.ZIP_GUY wrote:
> :>> [EMAIL PROTECTED] (Mok-Kong Shen) wrote:
> :>> >Tim Tyler wrote:
> :>> >> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> :>> >> : If my message is over one hundred bytes, do you think
> :>> >> : that I need to care about wasting 5 bits?? [...]
> :>> >>
> :>> >> At worst, this can reduce the size of keyspace by a factor of 32.
> :>> >
> :>> >Sorry, I don't understand. What do you mean by 'keyspace'
> :>> >here? This is the message space. The message gets longer
> :>> >by 5 bits. There is no information in the above of how
> :>> >big the key is. [...]
> :>>
> :>> I thought we are talking about compressing then ecnrypting.
> :>> If you always add 5 zeros or any other fixed amount of bits
> :>> after a compressed string or any file for that matter which is
> :>> then encrypted. The attacker know what the last few bits are
> :>> and throws out keys that don't match. So if the last five bits
> :>> of a file are known then it means you reduce your key space by
> :>> 5 bits.
> :>
> :>Reducing the message space by x bits does *not* reduce the keyspace by x
> :>bits... How much the keyspace is reduced depends on the unicity
> :>distance.
>
> : There was nothing in the previous message to suggest what you
> : claimed. What was in the message was if you know what certain bits
> : are. Then that can reduce the key space.
>
> If one was *replacing* five bits at the end of the message by 0s,
> the effect would depend on the unicity distance [because those
> bits might have been known already].
No. Consider this: Encryption algorithm A encrypts, with
a key K, blocks of 64 bits and produces ciphertext of
same number of blocks of same lengths. Encryption
Algorithm B uses the key K to do the same and append
at the end 5 0's. Now the ciphertext of algorithm B
is longer than the ciphertext of algorithm A. Does
that matter excepting the transmissin cost? Where does
the 'keyspace' play a role here at all?
>
> That's not what David was talking about. David is discussing the
> effect of adding an additional section of known plaintext to the
> end of the file. This normally has the effect of decreasing the
> keyspace by almost exactly five bits - provided the effective
> keyspace doesn't go negative, of course.
No. He was criticizing my end-of-file symbol taking up
extra bits. That's why I argued that having 5 more bits
(assumed to be caused by employing end-of-file) does
not matter in practice, if the total message length
is 100 bytes (in fact in genreal much longer).
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Again a topic of disappearing e-mail?
Date: Fri, 22 Sep 2000 14:46:43 +0200
Runu Knips wrote:
>
> Pfft as if this is something noticeable. Using PGP and removing
> the email by hand has the same effect, doesn't it ?
I don't know either way. I only reproduced the stuff.
M. K. Shen
------------------------------
From: "M.B�deker" <[EMAIL PROTECTED]>
Subject: Re: PGP 6.5.8 source code published
Date: Fri, 22 Sep 2000 14:21:12 +0200
Reply-To: [EMAIL PROTECTED]
http://web.mit.edu/network/pgp.html
--
============================================
For replying delete _NOSPAM_ in the address!
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA public exponent
Date: 22 Sep 2000 08:57:59 -0400
Mark Wooding <[EMAIL PROTECTED]> wrote:
> No. Carmichael's lambda function gives an upper bound on the order of
> any element of Z_n as \lambda(n) = \lcm(p - 1, q - 1).
It is the least common multiple of the orders of elements in the
multiplicative group of Z_n (elements not relatively prime to n don't have
a multiplicative order). The order of every element divides this.
The order of every element in the multiplicative group of Z_n divides
phi(n) (the order of the group), but generally, this (which is a multiple
of lambda(n)) is larger than necessary in finding a multiple of all those
orders.
In a finite commutative group, there *is* an element whose order is the
least common multiple of the orders of the elements in the group.
So lambda(n) is a multiple of the orders of the elements and indeed there
is an element of order lambda.
If m and n are relatively prime,
phi(mn)=phi(m)*phi(n)
lambda(mn)=LEAST_COMMON_MULTIPLE(lambda(m),lambda(n))
For an ODD prime, p^n, lambda(p^n)=phi(p^n) since the multiplicative group
of Z_p^n is cyclic.
For 2^n,
lambda(2)=phi(2)=1
lambda(4)=phi(4)=2 (3 has multiplicative order 2)
for n>2, however, lambda(2^n)=phi(2^n)/2
(The multiplicative group of Z_8 is not cyclic, for example. It has order
4, but is not isomorphic to the abelian group Z_4, instead it is
isomorphic to the abelian group Z_2(+)Z_2)
(From the formulas for lambda(p^n) for primes, odd and the special case of
p=2, and the formula for lambda(mn) for m,n relatively prime, you can
find lambda(n) for any n.)
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Tying Up Loose Ends - Correction
Date: 22 Sep 2000 13:31:14 GMT
[EMAIL PROTECTED] (Mok-Kong Shen) wrote in
<[EMAIL PROTECTED]>:
>
>
>Tim Tyler wrote:
>>
>> SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
>> : [EMAIL PROTECTED] (Benjamin Goldberg) wrote:
>> :>SCOTT19U.ZIP_GUY wrote:
>> :>> [EMAIL PROTECTED] (Mok-Kong Shen) wrote:
>> :>> >Tim Tyler wrote:
>> :>> >> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>>
>> :>> >> : If my message is over one hundred bytes, do you think
>> :>> >> : that I need to care about wasting 5 bits?? [...]
>> :>> >>
>> :>> >> At worst, this can reduce the size of keyspace by a factor of
>> :>> >> 32.
>> :>> >
>> :>> >Sorry, I don't understand. What do you mean by 'keyspace'
>> :>> >here? This is the message space. The message gets longer
>> :>> >by 5 bits. There is no information in the above of how
>> :>> >big the key is. [...]
>> :>>
>> :>> I thought we are talking about compressing then ecnrypting.
>> :>> If you always add 5 zeros or any other fixed amount of bits
>> :>> after a compressed string or any file for that matter which is
>> :>> then encrypted. The attacker know what the last few bits are
>> :>> and throws out keys that don't match. So if the last five bits
>> :>> of a file are known then it means you reduce your key space by
>> :>> 5 bits.
>> :>
>> :>Reducing the message space by x bits does *not* reduce the keyspace
>> :>by x bits... How much the keyspace is reduced depends on the
>> :>unicity distance.
>>
>> : There was nothing in the previous message to suggest what you
>> : claimed. What was in the message was if you know what certain bits
>> : are. Then that can reduce the key space.
>>
>> If one was *replacing* five bits at the end of the message by 0s,
>> the effect would depend on the unicity distance [because those
>> bits might have been known already].
>
>No. Consider this: Encryption algorithm A encrypts, with
>a key K, blocks of 64 bits and produces ciphertext of
>same number of blocks of same lengths. Encryption
>Algorithm B uses the key K to do the same and append
>at the end 5 0's. Now the ciphertext of algorithm B
>is longer than the ciphertext of algorithm A. Does
>that matter excepting the transmissin cost? Where does
>the 'keyspace' play a role here at all?
>
Then algorithm B is not doing what Tim said and you are
just adding 5 bits after encryption.
>>
>> That's not what David was talking about. David is discussing the
>> effect of adding an additional section of known plaintext to the
>> end of the file. This normally has the effect of decreasing the
>> keyspace by almost exactly five bits - provided the effective
>> keyspace doesn't go negative, of course.
>
>No. He was criticizing my end-of-file symbol taking up
>extra bits. That's why I argued that having 5 more bits
>(assumed to be caused by employing end-of-file) does
>not matter in practice, if the total message length
>is 100 bytes (in fact in genreal much longer).
No I was also in this and other threads criticizing the
use of an EOF symbol in any huffman or arithmetic type of
compression as nothing more than a means to make the following
encryption weaher. Becasue it makes the effective key space
smaller.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: t
Date: Fri, 22 Sep 2000 06:53:57 -0700
Runu Knips wrote:
>
> lala wrote:
> >
> > t
>
> This NG is really surprising me... such a big thread about such
> a silly (aborted ?) posting...
We just witnessed the transformation of a practically meaningless test
post into a mental exercise that stretched our imaginations. Very
creative!
Nearly every thread in this group teaches something.
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Revilo P. Oliver: Cryptanalyst?
Date: Fri, 22 Sep 2000 13:34:54 GMT
On Fri, 22 Sep 2000 03:06:13 -0400, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote, in part:
>John Savard wrote:
>> However, the other day, I happened across a web site devoted to his
>> works. In his biography there, it was noted that during the war he
>> worked for a "highly secret cryptographic agency of the War
>> Department" during World War II.
>Whose War Department? It's clearly either a pseudonym or the result
>of parents' warped sense of humor; the main question is who wrote
>under that name (if a pseudonym it may have been more than one person).
>You can't believe everything you read on the Web; among other
>bibliographical information given for RPO is that he was a founder of
>the John Birch Society, which seems not to be true. It could be an
>elaborate hoax.
As I noted, I'd heard of Revilo P. Oliver long before I saw that web
site. Actually, his father bore the same name, so it's his
_grandparent's_ warped sense of humour that started the family
tradition.
The book "Language on Vacation" mentioned the unusual name.
And I've seen with my own eyes issues of the Reader's Digest which
contained his articles.
Of course, he wasn't _the_ founder of the John Birch Society, but he
may have been one of its early members.
So I'm quite confident that he was a real person. That in later life
he went too far to the right for the John Birch Society to be
comfortable with is...not surprising. It is a sad thing that has
happened before. Before I saw the abortion article, I noted with
horrified fascination another place where he criticized our society
for forgetting that one of the functions of religion is to unify our
society - and quite properly, societies discriminate against those
'fanatics' who take their exclusive religion so seriously as to refuse
to honor the national gods.
So the Romans had the right idea when they persecuted the early
Christians? It is in fact well known today that this was the reason
behind those persecutions ... a fact he avoids mentioning, so as not
to prejudice the reader against his argument.
It would be nice to think that these writings were the product of an
inherited warped sense of humour, of course.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: IBM analysis secret.
Date: Fri, 22 Sep 2000 13:38:09 GMT
On Thu, 21 Sep 2000 23:38:14 GMT, [EMAIL PROTECTED] wrote,
in part:
>I remember once reading about that IBM knew about differential analysis
>when analyzing DES 10 years before it was "discovered" by the science
>community, and kept it a secret for the count of the NSA.
>Now when I'm checking it up, it does not seen to be right at all.
>Have anyone a idea about what this wage memory was really about because
>I can't remember?
Actually, that's largely correct, except for the "10 years" part. That
was claimed concerning public-key cryptography, yet the GCHQ discovery
of it, under the name of 'non-secret encryption', was more like 5
years before the public discovery.
DES is highly resistant to differential cryptanalysis - and it was
designed with that attack in mind. (Its predecessor, LUCIFER, was not
so designed, and thus IBM mathematicians presumably discovered
differential cryptanalysis when analyzing it for weaknesses.) The
academic community only discovered differential cryptanalysis several
years after DES was adopted.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: t
Date: Fri, 22 Sep 2000 13:43:05 GMT
On Fri, 22 Sep 2000 02:39:46 -0400, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote, in part:
>Wrong, haven't you heard of "Polish notation"?
Ah, silly of me to be so provincial.
I just wouldn't have thought of using it in something designed to be
easy to understand. And, of course, if you had said
TNN
FN
it would have come to mind more quickly, since Reverse Polish Notation
is more familiar than the original Lukasiewicz format.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: t
Date: Fri, 22 Sep 2000 13:44:18 GMT
On Fri, 22 Sep 2000 09:21:30 +0200, Runu Knips
<[EMAIL PROTECTED]> wrote, in part:
>This NG is really surprising me... such a big thread about such
>a silly (aborted ?) posting...
True, but most of the thread is really about Douglas Gwyn's post,
which, unlike that one, was genuinely interesting.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Kevin N. Stone" <[EMAIL PROTECTED]>
Crossposted-To: rec.puzzles,alt.fan.harry-potter,jyu.ohjelmointi.coderpunks
Subject: Re: My e-mail to Jim Gillogly -- YO, JIM!!!!!!!!!!??? (I'm annoyed at you)
Date: Fri, 22 Sep 2000 14:56:15 +0100
Hi Dan,
How the devil have you been.
It's been a long time since I last saw you.
Has the rash cleared up yet?
:)
------------------------------
** 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
******************************
