Cryptography-Digest Digest #303, Volume #10 Thu, 23 Sep 99 16:13:03 EDT
Contents:
Re: EAR Relaxed? Really? ("Douglas A. Gwyn")
Re: factorisation of a 2 primes(short) product ("Michael Scott")
Re: msg for Dave Scott (Anton Stiglic)
Re: International crypto restrictions (Paul Koning)
Re: Schrodinger's Cat and *really* good compression ("Douglas A. Gwyn")
Re: Second "_NSAKey" ("Douglas A. Gwyn")
Re: frequency of prime numbers? (Patrick Juola)
Re: Okay "experts," how do you do it? ("Douglas A. Gwyn")
Re: low diffie-hellman exponent (Tom St Denis)
Re: frequency of prime numbers? ("Douglas A. Gwyn")
Re: frequency of prime numbers? (Patrick Juola)
Re: low diffie-hellman exponent (DJohn37050)
Re: International crypto restrictions (Scott Hardy)
Re: msg for Dave Scott ("Douglas A. Gwyn")
Re: msg for Dave Scott ("Douglas A. Gwyn")
Re: RSA weak? ("Douglas A. Gwyn")
Re: Mystery inc. (Beale cyphers) (Tim Tyler)
Re: some information theory (very long plus 72K attchmt) ("Douglas A. Gwyn")
Re: Mystery inc. (Beale cyphers) (Tim Tyler)
----------------------------------------------------------------------------
Crossposted-To: talk.politics.crypto
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: EAR Relaxed? Really?
Date: Thu, 23 Sep 1999 18:00:40 GMT
Greg wrote:
> In article
> <[EMAIL PROTECTED]>,
> Eric Lee Green <[EMAIL PROTECTED]> wrote:
> > Oh poop. You'd hear of it alright, because we would never
> > agree to put two back doors into our software....
> So you mean you would violate an NDA with the federal government
> that would expose their true intentions that they would desire
> to keep close to their chest? Do you really think they would
> let you do this without hell to pay? I don't.
The government would have to be even bigger fools than you credit
them for to try to prosecute such a case. Think of the publicity!
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: factorisation of a 2 primes(short) product
Date: Thu, 23 Sep 1999 18:58:03 +0100
Yep, 240 bits, that's about 72 decimal digits, and shouldn't take too long
using
ftp://ftp.compapp.dcu.ie/pub/crypto/factor.exe
from a Windows '95/'98/NT command prompt
--
Mike Scott
=========================================
Fastest is best. MIRACL multiprecision C/C++ library for big number
cryptography
ftp://ftp.compapp.dcu.ie/pub/crypto/miracl.zip
Jerry Coffin <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> says...
> > i try to factor numbers of 240 bits which are the product of 2 primes of
> > 120 bits and i want do that with the workstations i have (several
> > pentiumII/350). 2 questions:
> >
> > 1. is it possible ?
>
> It should be, though for only 240 bits, using more than one machine
> may be overkill.
>
> > 2. what are the algorithms to do that ?
>
> This is still small enough that a multiple polynomial quadratic sieve
> is _probably_ still going to be faster than a number field sieve.
> Probably the easiest way to handle it is to grab a copy of Miracl (for
> one example) which includes (among other things) a free factoring
> program as a demo. It should be able to factor a 240 bit number on
> one machine in less than a day.
>
> --
> Later,
> Jerry.
>
> The Universe is a figment of its own imagination.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Date: Thu, 23 Sep 1999 13:55:48 -0400
Tom St Denis wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > On Wed, 22 Sep 1999 12:09:57 GMT, Tom St Denis wrote:
> > >
> > >beaqaaamL6MNs6}utuaaaaiaaaa
> caaaaaaaaaaaaa
> > >aaaaaaaaaaaaaaaaaaaaaaaaa
> >
> > can you explain all these 'a' at the end and in the middle of the
> > cypher text ?
> >
>
> Why? You think they are clues to the message?
>
> At first I was going to say READ THE SOURCE, but I realize that's unfair.
> Some people work (unlike me), so I am going to say 'a' represents the 6-bit
> number zero and that the header contains some (size, and cipher id). The
> 'a's at the end is padding to avoid corrupting the end of the message.
Padding should be done before enciphering. And still then, something is not
right,
if you say that your headar contains a (correspondint to 0's) and the padding in
the end
is done with a's, you encrypted message would be just
W{dsG{jC4KzE3hoqb}tWYZ9qT2F
so what representation is it in? it's not base 16, nore binary, ???
How could your header, from what you say, is probably:
beaqaaamL6MNs6}utuaaaaiaaaa
be as long as your message?
This realy is a sign of bad encryption, like I sais, maybe you are mistaken some
pointeres or something. Did you commpare your result with some known
ciphertext?
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: International crypto restrictions
Date: Thu, 23 Sep 1999 11:56:34 -0400
Scott Hardy wrote:
>
> I was thinking of writing an algorithm using
> a 64-bit key which took a LOT of CPU time
> (probably a couple hundred mS on a fast PC)
> generating several KB of sboxes and subkeys
> from that 64-bit key, thinking that it would
> give a modicum of security to those who had to
> make do with short keys.
>
> I was then informed that Blowfish was only allowed
> to be exported from the US with a 32-bit, rather
> than 40-bit key, presumably because of its
> behaviour along these lines. So, my question is
> this: since I can code it outside of the US, is
> this a viable idea, or are there many other
> countries which limit algorithms based on subkey
> generation time?
Maybe there are such countries, but the US isn't
one of them. The story you heard about Blowfish
is complete nonsense.
paul
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Schrodinger's Cat and *really* good compression
Date: Thu, 23 Sep 1999 16:54:51 GMT
Mok-Kong Shen wrote:
> If I understood the discussions correctly the underlying issue here
> is that there is always substantial risk when one contrives a metaphor
> or analogy ...
But Schroedinger's cat is neither; it is a "thought experiment"
that one could readily *actually perform*. There is no analogy
being drawn, nor is it a metaphor for anything.
------------------------------
Crossposted-To: talk.politics.crypto
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Second "_NSAKey"
Date: Thu, 23 Sep 1999 17:00:55 GMT
Greg wrote:
> And finally, there is no explanation that can refute this one
> scenario. Not one.
Nonsense. Alternative explanations inconsistent with that
scenario have been suggested. Maybe you mean, *you* won't
give up that scenario no matter what.
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: frequency of prime numbers?
Date: 23 Sep 1999 14:08:44 -0400
In article <[EMAIL PROTECTED]>, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>Ellis Dees wrote:
>> 'This statement has no proof.'
>> True, but unprovable.
>
>(A) Assume that the statement is false.
>(B) We conclude (under that assumption) that it has a proof.
>(C) Only true statements have proofs (in any decent system).
>(D) Thus the statement is true.
>(E) (A) and (D) are contradictory, thus (A) is false. (PBC)
>(F) If the statement is definitely true or false,
> then that means that the statement must be true.
>
>(A)-(F) constitute an (informal) proof of the statement.
>But that contradicts the statement itself.
>
>The only really questionable step is in the "if" clause of
>(F): therefore the statement is neither definitely true nor
>definitely false.
>
>If you use fuzzy logic, you find it measures 0.5,
>where 0=definitely_false and 1=definitely_true.
>In fact, all Russell-like antinomies resolve like this
>using fuzzy logic.
You're committing a fallacy of equivocation all over the place;
specifically, you're confusing the notion of *informal* proof (of
which the demonstration above is an example) with the notion of
*formal* proof within a system. I could write a book on the number
of informal and questionable assumptions you make above, starting with
the consistency of informal reasoning. In fact, in a Goedellian sense,
you've just *proven* the inconsistency of "fuzzy logic" as you've
developed a "proof" of both A and not-A.
In point of fact, one of the main developments in Goedel's proof is
that it involves no "Russell-like antinomies" and everything is a
well-grounded statement in the formal system of interest. Fuzzy
logic doesn't resolve this -- it's merely, pace Godel, yet another
inconsistant system.
And, furthermore, you've got no basis for asserting, in particular,
that it measures 0.5; I can equally show that the statement "This
statement is 0.5 true" is contradictory in any formal system of
fuzzy logic.
-kitten
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Okay "experts," how do you do it?
Date: Thu, 23 Sep 1999 17:53:19 GMT
Sundial Services wrote:
> I think it would be a fascinating research-topic to see to what extent
> we could possibly replace the human cryptologist. And in what way.
It is an AI problem, similar to but harder than much of what AI
has been trying to achieve for decades now, with only limited
success. Heck, we still don't have good machine translation,
which is similar to decoding ciphertext but *not* designed to
be hard to do from ciphertext only.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: low diffie-hellman exponent
Date: Thu, 23 Sep 1999 18:06:54 GMT
In article <7sc8i4$[EMAIL PROTECTED]>,
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> In article <7s9i2f$ett$[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> >In peekboo 1.4 I used the output of sha for the exponent. Now I am wondering
> >is that a bad idea? The modulus is 2048 bits so I think solving it would be
> >a pain but what about specialized cases like mine?
>
> With DH, in general, if the attacker knows the private exponent is between 0
> and N, he can find it in O(sqrt(N)) time using the 'big step/little step'
> method. So, if you use a straight SHA image as the exponent, the attacker
> can reconstruct it with about 2**80 modular multiplications.
>
> You decide if that is that is an unacceptable crack (my opinion: only if you
> are extremely paranoid. But then, I think a 2048 bit DH modulus is massive
> overkill and shows you are already quite paranoid).
Thanks for the information. I figured if I were to make a new app why not
use a somewhat large modulus. I agree that even 768 moduli would be strong
but why put up with paranoid types? Plus it doesn't hurt it much. Takes
about 3 seconds to make a shared key...
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Date: Thu, 23 Sep 1999 17:30:23 GMT
David Hoyt wrote:
> Actually, Godel said ANY axiomatic language is EITHER incomplete
> OR inconsistent. Logic and math are axiomatic languages. Most
> of us hope that they are incomplete (some things are not
> provable), but it is possible that they are inconsistent.
> Until someone can prove the TRUE == FALSE, we won't know.
Actually, some systems have been proven consistent
(which in effect means there is some statement S such
that S can be derived but !S cannot be derived).
> ... Thus a scientist can believe in christian (or
> ojibwe) creationism, and evolution at the same time.
They can do that anyway; creationism has nothing to
do with logic.
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: frequency of prime numbers?
Date: 23 Sep 1999 13:57:48 -0400
In article <[EMAIL PROTECTED]>, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>"Trevor Jackson, III" wrote:
>> Douglas A. Gwyn wrote:
>> > Donald Welsh wrote:
>> > > I'd like to correct this misconception, if I may. Godel's theorem
>> > > does not say that "there are true statements that cannot be proved".
>> > > It says that there are unprovable statements. These statements are
>> > > neither true nor false.
>> > False unprovable statements are trivial. Goedel's result
>> > pertains to statements that are true, yet unprovable within
>> > the given axiomatic system.
>> Really. Do you have a trivial solution to the (false) statement "Turing
>> machine N halts?"
>
>What do you mean, "solution"? What is the *problem*?
>Obviously, if the axiomatic system is consistent,
>it cannot be used to prove any false statement,
>so all the false statements are unprovable.
That's a misuse of terminology -- a false statement may be *provably*
false, which is to say (in most systems) that I can prove the opposite
true. "There exists a highest prime number" is a provably false statement
in the system of PA.
>If the axiomatic system is rich enough to express
>the exact statement about Turing machine N, and
>that statement is false (which you *stipulate*),
>then so long as the system is consistent it cannot
>be used to prove that statement.
In this context, however, not only will you be unable to prove that
this machine halts (which we are assuming false), but you will also
be unable to prove that the TM does not halt, which we are assuming
true.
An unprovable false statement is simply a false statement which is not
provably so.
-kitten
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: low diffie-hellman exponent
Date: 23 Sep 1999 18:36:13 GMT
1024 bit DL is about 80 bits of security, 2048 is about 112 bits (3 key triple
DES) and 3072 is about 128 bits (low AES). This is according to NIST in DSA-2.
Don Johnson
------------------------------
From: Scott Hardy <[EMAIL PROTECTED]>
Subject: Re: International crypto restrictions
Date: Thu, 23 Sep 1999 19:27:00 GMT
In article
<[EMAIL PROTECTED]>,
Eric Lee Green <[EMAIL PROTECTED]> wrote:
> Scott Hardy wrote:
> > I was then informed that Blowfish was only allowed
> > to be exported from the US with a 32-bit, rather
> > than 40-bit key, presumably because of its
> > behaviour along these lines. So, my question is
> > this: since I can code it outside of the US, is
> > this a viable idea, or are there many other
> > countries which limit algorithms based on subkey
> > generation time?
>
> If you are a U.S. citizen then U.S. export law applies to you whether
> you are inside the country or outside of it, and "export" means that
the
> program ends up overseas. That is, if you are a U.S. citizen and write
> the program while physically located outside the country, you are
> considered to have exported it (illegally, since you don't have an
> export license presumably!).
>
> If you are not a U.S. citizen, you will have to obey a) the laws of
> whatever host country you are located in, and b) the laws of your own
> home country.
>
Well, the US part of it is sort of a non-issue in this case, since
I was intending to make it open-source freeware anyway. Information
tends to become free, without authors breaking any laws. My concern
was more whether non-US jurisdictions have been known to crack down
on algorithms which used allowably small keys but were hard to break.
But perhaps there is no clear answer yet -- if there were lots of
such algorithms out there to establish what various governments
would do about them, I wouldn't feel any need to code another. I
suppose I will just have to try it and see...
-- Scott
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Date: Thu, 23 Sep 1999 18:18:10 GMT
Tom St Denis wrote:
> Well you say you can break all encryption methods and systems. Prove it.
> beaqaaamL6MNs6}utuaaaaiaaaaW{dsG{jC4KzE3hoqb}tWYZ9qT2Fcaaaaaaaaaaaaa
> aaaaaaaaaaaaaaaaaaaaaaaaa
> That was a peekboo message using ...
(1) I don't recall David Scott saying any such thing.
(2) Even if he could, you gave him a *very* short challenge message.
Not being able to break it wouldn't prove anything.
(3) Doesn't the sci.crypt FAQ address this issue of unsolicited
challenges?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Date: Thu, 23 Sep 1999 18:21:31 GMT
Rick Braddam wrote:
> [Tom St Denis <[EMAIL PROTECTED]> wrote ...]
> I don't know that you _are_ a jerk, but you sure sound like one.
> Reminds me of when I was 17 years old and knew everything, had all
> the answers, and everything I made was of earth-shattering importance.
> Now I don't know anything, don't have any answers, and ...
Sounds like you got smarter as you got older. Or at least, wiser.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: RSA weak?
Date: Thu, 23 Sep 1999 19:22:47 GMT
Tom Cooper wrote:
> It follows that there is no useful choice of non-prime numbers that
> generate the original key in the same way. Tom.
Well, not in "the same way", but it doesn't rule out RSA
encryption with a particular key being equivalent to
some *different* encryption algorithm (possibly RSA-key
dependent) using some other key. In fact, we know how
to define such an equivalent mapping, but the obvious
definition is of no value for cryptanalysis. The open
question is, can there be some such equivalent system
+key that is easier to cryptanalyze than the RSA version?
And, is there a practical way of finding the equivalent
system without knowing the RSA key? (Even if there are
manageably many possibilities, that would suffice.)
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Mystery inc. (Beale cyphers)
Reply-To: [EMAIL PROTECTED]
Date: Thu, 23 Sep 1999 19:31:09 GMT
John Savard <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] (Curt Welch) wrote, in part:
:>As Jim already pointed out, you can't really prove a cypher is a hoax just
:>by analyzing the numbers. All good cyphers will look like ramdom numbers.
[...]
: There were two papers; one was decoded, and implied the second one was
: coded in the same general system.
Well, there were three ciphertexts - one cracked, two not, of which one
was described as identifying the location of the treasure.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Microsoft automatic tagline genera%y.o3704&5$ &�6 �73 ("&(patches #5 of.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: some information theory (very long plus 72K attchmt)
Date: Thu, 23 Sep 1999 19:15:40 GMT
Tom St Denis wrote:
> Compression is not to enhance the security of a system, I don't even use it
> in peekboo and you can't break it or even suggest a possible break.
> Compression is used to cut transmission times. Think of it. If your modem
> was a 1tbps connection and you had a 50tb hd would you are to compress
> anything?
Precompression *does* make cryptanalysis harder,
since it greatly complicates the mapping from the
source, which may have lots of known statistical
properties, to the interceptable message. For
example, ASCII source has every 8th bit 0, and
if it is an English-language document, there is
a statistical bias in the LSB, which could be
exploitable by certain cryptanalytic attacks.
After compression, such biases are no longer
present at the input to the encryptor, which
renders moot that encryptor vulnerability.
What "peekboo" does and whether or not D. Scott
can break "peekboo" have nothing to do with the
general issue.
Even on high-speed networks, we don't want to
waste bandwidth unnecessarily, but this actually
works in *favor* of precompressing for encryption,
which reduces bandwidth even though that is not
the primary goal. Data compression of course has
relevance independently of encryption, but that
in itself implies nothing about its relevance
*for* encryption.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Mystery inc. (Beale cyphers)
Reply-To: [EMAIL PROTECTED]
Date: Thu, 23 Sep 1999 19:46:44 GMT
Curt Welch <[EMAIL PROTECTED]> wrote:
: If you really wanted to make the matter public, you would have released the
: original Beale papers to the public as well. The fact that all we have
: is a published story is more support for the hoax theory. There is no type
: of physical evidence to back up the story. And if you really wanted to see
: the thing solved, releasing the physical evidence would have made the story
: much stronger.
Apparently there /is/ some independent evidence supporting certain parts
of the story. Simon Singh covers this evidence briefly in "The Code Book"
and concludes that the Beale cypher is probably genuine.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
This space intentionally left blank.
------------------------------
** 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
******************************
