Cryptography-Digest Digest #544, Volume #14 Thu, 7 Jun 01 01:13:00 EDT
Contents:
Re: Best, Strongest Algorithm (gone from any reasonable topic) (JPeschel)
Re: OTP WAS BROKEN!!! (Gordon Burditt)
Re: Best, Strongest Algorithm (gone from any reasonable topic)
([EMAIL PROTECTED])
Re: Notion of perfect secrecy (SCOTT19U.ZIP_GUY)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (SCOTT19U.ZIP_GUY)
Re: Def'n of bijection ([EMAIL PROTECTED])
Re: OTP WAS BROKEN!!! ([EMAIL PROTECTED])
Re: Bow before your new master (John Fields)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (JPeschel)
Re: RSA's new Factoring Challenges: $200,000 prize. (my be repeat) ("Michael Brown")
Re: RSA's new Factoring Challenges: $200,000 prize. ("Michael Brown")
Re: Notion of perfect secrecy ("Neil Couture")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Date: 07 Jun 2001 02:25:48 GMT
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) writes, in part:
>You should read
>Shannon's article "Communication Theory of Secrecy Systems"
>it was in the Bell systems technical Journal.
Yes, I know the paper, have read it, and am re-reading it.
He talks about making the key as small as possible. I think we
can assume that means as long as the plaintext.
That doesn't mean that the size of the key and the size of the
pad need to be the same. Keys are taken from the pad.
When the pad is used up it's time to generate another pad
with more keys. Each key, so far as i can tell from Shannon, must
be the length of the plaintext.
Point me to where Shannon says that the length of the plaintext
must be kept secret.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (Gordon Burditt)
Subject: Re: OTP WAS BROKEN!!!
Date: 7 Jun 2001 02:28:54 GMT
>Why if you re-use the key twice, OTP becomes less secure?
If you re-use the key, it's NOT a OTP.
>I'm newbie and I want an answer with few samples.
Let us suppose that you can trick the opposition into sending
something that you know, encrypted with the OTP. Perhaps you even
get to select it. For example, your ambassador gives their ambassador
(at their embassy in your country) a long-winded proposed treaty
for extraditing spammers and emergency shutdown of open spam relays
by nuclear air attacks. They will relay it to their government
using the OTP via radio (so you can intercept it).
You know the text of the treaty will appear somewhere in one of
the messages sent in the next day or so. You can use this to create
a relatively limited list of pieces of possible keys.
Now, if the key is used ONCE, you have some of the keying material
which will never be used again. Whoop de doo! You already know
what was encrypted with that portion of the key; that was how you
computed it in the first place. This gives you no useful information
about other encrypted messages.
If the key is used MORE THAN ONCE, you can take the possible keys,
slide them along other messages, and compute possible plaintexts
from this. IF you get a sensible-looking plaintext, you now have
a much-better-than-random-guess probability that this is the correct
key, being re-used.
>I tried to solve the probleme, using the same key, I found (2*n)
>possible solutions for a ciphertext of bit-length equal to n.
>How is it possible to recover the plaintext?
Assume that the text of the treaty is 100Kbits, and that 10Mbits
of messages were sent in the time window when the treaty was likely
sent. Sliding the key along the text of messages sent yields 10M
- 100K possible keys. This is a heck of a lot less than the possible
values of keys used to send the treaty, 2**100K. Now, assuming
the key will be re-used the next day, and that 10Mbits of traffic
are sent then, you have (10M-100K)**2 combinations of possible keys
and places to start using them. This is less than 2**48, which is
a heck of a lot less than 2**100000.
Gordon L. Burditt
------------------------------
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
From: [EMAIL PROTECTED]
Date: 06 Jun 2001 22:40:09 -0400
"Tom St Denis" <[EMAIL PROTECTED]> writes:
> <[EMAIL PROTECTED]> wrote in message
>> Tim Tyler <[EMAIL PROTECTED]> writes:
>>>
>>> ...but why only consider the possible messages of size 2^n? This is
>>> a tiny subset of the messages that could have been transmitted.
>>
>> Right! That's why ``perfect secrecy'' is only attainable if the ciphertext
>> is longer than *any* possible plaintext. All messages must have infinite
>> length.
>
> You're a loon.
That's not nice! Anyway, your sarcasm detector must be busted.
Len.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Notion of perfect secrecy
Date: 7 Jun 2001 02:27:20 GMT
[EMAIL PROTECTED] (Tom St Denis) wrote in
<kmBT6.47362$[EMAIL PROTECTED]>:
>Ok this has gone on too long.
>
>Typically what you guys are missing is that the length of the message is
>not the secret. It's the contents of the message.
<crap sniped>
>At any rate if the length is important just pad the message. Make the
>message fit to be a multiple of say 64 bytes or something.
DUH??? GEE WHIZ length may mean something so pad to make it
match longest message for "perfect security" READ SHANNON YOU IDOIT
you can't have it both ways little BOY.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: 7 Jun 2001 02:42:27 GMT
[EMAIL PROTECTED] (JPeschel) wrote in
<[EMAIL PROTECTED]>:
>[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) writes, in part:
>
>>You should read
>>Shannon's article "Communication Theory of Secrecy Systems"
>>it was in the Bell systems technical Journal.
>
>Yes, I know the paper, have read it, and am re-reading it.
>
>He talks about making the key as small as possible. I think we
>can assume that means as long as the plaintext.
>
>That doesn't mean that the size of the key and the size of the
>pad need to be the same. Keys are taken from the pad.
>When the pad is used up it's time to generate another pad
>with more keys. Each key, so far as i can tell from Shannon, must
>be the length of the plaintext.
>
>Point me to where Shannon says that the length of the plaintext
>must be kept secret.
>
Joe do you really need your hand held? I read the whole thing
I think you're a big boy and can read it yourself. Especail his
dsicussion about "perfect secrecy".
I was reading the original jpg images. Are you saying you have
a text file. Since I thought it was only recently released and
is in jpeg format. Several images.
Look especailly at the figures of how different systems arranged
you'll see the that if you stop at the various message lengths
you have defined several different residue classes. that are
really nothing but a subset. For perfect encryption you can't
break it up into seperate residue classes.
While you at it since you have text note the comment "if the key is
small the system simple errors don't progate... Guess what the
system can't be to secure. Kind of matches the current trens to
build small fast cipher in CTR mode. My guess is if Shannon knew
anything the AES stuff is not to secure.
You really need a large key, A trasducer ( bijective compressor )
to reduce redunacncy, A large work factor , and a progateing
error mode. GEE WHIZ.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
Subject: Re: Def'n of bijection
From: [EMAIL PROTECTED]
Date: 06 Jun 2001 23:13:18 -0400
Tim Tyler <[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] wrote:
>: Um, it's a mathematical term, Tim. A statement is vacuously true when
>: it cannot possibly be false. In other words, the statement contains
>: no information.
>
> I guess you think Fermat's Last Theorem is vacuous, then. It's negation
> is known to be an impossiblity, after all.
No. Read it again: ``vacuously true'' is a mathematical term. It can be
looked up.
Fermat's last theorem is only known to be true after a lengthy proof. That
``probabilities can't be any less than zero'' is vacuously true, because
there is by definition no such thing as a negative probability.
(One might quibble that the statement is ``trivial'' rather than
``vacuously true''. Strictly speaking, ``vacuously true'' refers to
the case that an implication is true because its premise is always
false. ``I always succeed when I try'' would be vacuously true if I've
never tried. Or perhaps, ``I marry every girl I date.'' But most
trivial statements can be rephrased such that they become vacuously
true.)
>: Sigh. If no compression is performed, then the likelihood of false
>: positive decryptions is for most practical purposes zero.
>
> Um, plaintext: 129 bits. Key 128 bits. What on earth can you possibly
> be talking about?
You can't assume that |ciphertext| ~= |key|. If such an assumption were
justified, then you would be an idiot for not using a one-time pad. (And
note that |ciphertext| includes all ciphertext produced with the given
key. It is not restricted to some single message.)
> Compression takes plausible messages and moves them (and perhaps lots of
> other stuff) into smaller-numbered bins, while moing other files the other
> way.
Sure. But do you have the faintest freaking clue how many possible
binary files there are of size less or equal to, say, this post?
About 2^20088. What fraction of them are ``plausible messages''? And
what fraction of them have preimages under BICOM which are ``plausible
messages''?
Is one number significantly larger than the other? By how much? Using
*any* even vaguely reasonable definition of ``plausible messages''?
Hint: ``A nawful lot, I'm sure'' is *not* an answer.
> That's not "the most one can say". I've repeatedly said a lot more -
> and I'm correct in doing so.
Post the proof, and all mouths will be stopped.
Len.
--
You are whining about resource use on the scale of pennies a year.
You are ignoring resources that cost ten thousand times as much.
-- Dan Bernstein
------------------------------
Subject: Re: OTP WAS BROKEN!!!
From: [EMAIL PROTECTED]
Date: 06 Jun 2001 23:16:11 -0400
[EMAIL PROTECTED] (Gordon Burditt) writes:
>>
>> Why if you re-use the key twice, OTP becomes less secure?
>
> Let us suppose that you can trick the opposition into sending something
> that you know, encrypted with the OTP...If the key is used MORE THAN
> ONCE, you can take the possible keys...
True. But note that you don't need any known plaintext to attach a reused
OTP. If you XOR the two messages, the OTP will cancel. What remains is the
XOR of two messages--and it's easy to recover both messages if you have
their XOR.
Len.
--
Don't blame me for the BIND company's decision to stick to obsolete
replication protocols. The rsync+openssh combination is not a secret.
-- Dan Bernstein
------------------------------
From: John Fields <[EMAIL PROTECTED]>
Crossposted-To:
alt.drugs.pot,sci.electronics.design,sci.electronics.repair,sci.environment
Subject: Re: Bow before your new master
Date: Wed, 06 Jun 2001 22:14:57 -0500
Brent Korn Hohler wrote:
Please, Oh please, notice me.
---
At first I was reluctant to reply to your ugly post, but it seems
you need to be taught a lesson about the beauty which exists in
this world.
Resistance, Brent. Voltage, current, inductance, capacitance,
resonance, imaginary quantities, (what's the square root of -1)?
Did you ever stop to think about that whenever you flush your
toilet epsilon rules while its tank is filling? And while yours
is draining? I didn't think so.
---
John Fields Austin Instruments, Inc.
El Presidente Austin, Republic of Texas
"I speak for my company" http://www.austininstruments.com
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Date: 07 Jun 2001 04:11:53 GMT
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) writes, in part:
[EMAIL PROTECTED] (JPeschel) wrote in
<[EMAIL PROTECTED]>:
>>Point me to where Shannon says that the length of the plaintext
>>must be kept secret.
>Joe do you really need your hand held? I read the whole thing
>I think you're a big boy and can read it yourself.
Save your bullshit, Dave. If you can point me to where Shannon says
the length of the plaintext must be kept secret, do it.
Quit fucking around. :-)
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: RSA's new Factoring Challenges: $200,000 prize. (my be repeat)
Date: Thu, 7 Jun 2001 16:31:58 +1200
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote in message
news:e6S0lFt7AHA.266@cpmsnbbsa07...
>
> "Michael Brown" <[EMAIL PROTECTED]> wrote in message
> news:BHwT6.583$[EMAIL PROTECTED]...
> > It's not really a mathematical method,
>
> Can it be run on a computer? Yes? Then it's math.
Uhh, how is Notepad mathematical? :)
> > so I can't describe it in mathematical
> > terms.
>
> If you can't then you simply don't have enough understanding of math to
> express it yet (see above). What you might try is writing explicit
> directions on how it is done in general, from there formalize then into
> statements of DO x, DO y, if W>Z ...... It won't be in a perfect form but it
> should be close enough that it can be understood, the firmer and less open
> to interpretation each statement is the better.
I posted this on 4th of June, but posts seem to drop off the server quite
quickly, so here it is again:
<BEGIN REPEAT>
Anyhow, here's my ideas on implementation of the algorithm on a computer with
more RAM than it knows what to do with (ps: I'm presuming that computer has
registers or equivilent big enough to access its address space):
1) Set up the array of boxes (called Boxes from now on). Each box has the
following properties:
Value : (byte) 4 sets of 2 bits (0 = zero, 1 = one, 2 = unknown, 3 = invalid),
each representing A, B, O, and C
ABox, BBox, OBox, CBox : indixes into the array (this one) of boxes, where ABox
is the box attached to A etc. Each of
these could be a dword.
BoxPart : (byte) 4 sets of 2 bits (0 = A, 1 = B, 2 = O, 3 = C) where the Part of
The time taken for each box would be the same regardless of how many boxes there
were.
2) A lookup table (called Lookup from now on) would have to be already set up.
This would have translations from things such as (in the form A-B-O-C) 0-?-?-?
to 0-?-?-0 so would be the "box filling" part of the process.
3) The values for the O of the bottom row of boxes would be set, and these boxes
pushed onto a stack that contains boxes that need to be updated.
4)
<PSEUDOCODE>
CurBox := GetNextBox;
OldVal := Boxes[CurBox];
Boxes[CurBox] := LookUp[Boxes[CurBox]];
</PSEUDOCODE>
If the any of the lower two bits of (OldVal xor Boxes[CurBox]) are set then set
the corresponding bit (from ABOx and lower 2 bits of BoxPart) to the correct
value (sorry this is rather vauge, but the pseudocode is downright horrible).
Push the destination box onto the box stack.
Ditto for B, O, and C.
<<< Note: There may be a little bit of confused text around here as I had to
stop for about 24 hours ... sleep, school, homework etc>>>
5) Do the bit at the top of the horozontal boxes (HBoxes hehehehe ... oh dear, I
really need to get out of the sci.crypt newsgroup =P ), where you check to see
if an and bm are one and C is zero (hence am != bm). If so then substitute into
the boxes further on. Again, this could be computed in a lookup table before
hand (since we're not too worried about RAM anymore).
6) Repeat 4 & 5 until you can't go any further. Take the information from the
(er, just one more time?) HBoxes and put it into the product table to determine
A and B.
Steps 4 and 5 are entirely constant per box (maximum of doing a box 4 times) and
with the lookup table, step 5 should be linear as well). Step 2 is also constant
also, with the lookup table not changing. Step 3 is of course linear. Step 6 is
quadratic and step 1 is cubic (or constant per box).
All put together, the overall pattern will be a fairly constant number of
operations per box, and since the number of boxes is cubic, the factoring time
should be cubic.
I'm not sure if this is coherent enough to answer your question, but I hope it
is.
<END REPEAT>
Is this closer to an algorithm?
> > However, if you could elaborate a bit more on "gibberish", I will try to
> > be more exact. And also, what is the correct definition of an algorithm?
> Would
> > method be a better word to use?
<SNIP>
> Gibberish
> is something that isn't defined well enough to be considered either a method
> or an algorithm.
I actually meant if he could be a bit more precise on which parts were
gibberish, but thanks for the definition also :)
> Joe
Thanks,
Michael
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Re: RSA's new Factoring Challenges: $200,000 prize.
Date: Thu, 7 Jun 2001 16:49:10 +1200
"Sergei Lewis" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Michael Brown wrote:
> > > I concur. What I wonder, not having studied this algorithm yet,
> > > is the rate of growth of work-per-box as the problem size is
> > > increased.
> > With a decent implementation of the algorithm (see below), the number of
> > operations per box should remain much the same (actual number of
instructions
> > depends on instruction set).
>
> Hm. I was bored over the weekend so wrote a quick hack to naively
> implement the space-hungry reverse adder logic part of Michael's
> algorithm. It's on http://members.tripod.co.uk/Folken/f.c
Looks good. I'm mainly a Pascal programmer, but I can read most C :)
> To sum up my understanding of the whole thing:
>
> You need O (((log n)^2)/2) space. For RSA, that's in the megabytes
> rather than the gigabytes unless I'm missing something obvious ^^;;
Next post answered this one ...
> You end up with boxes of the form
> ?
> 0 ?
> 1
> which can't be reduced further trivially, one per bit set in the product
> you are factoring.
I hadn't actually noticed this but that's probably because I'm substituting in
a2=1, b2=0 quite early on due to laziness :)
> You can set one bit arbitrarily for exactly one of these, since you know
> the two factors are different and exactly one bit is set; this on its
> own doesn't help resolve all of them.
Correct.
> Deductions of the form "bit x cannot be set in both factors because of
> box y", "bit x must be set in both factors because of box y", and "bit x
> must be set in neither factor because of box y" can be used to resolve
> these, as Michael's page describes, but you need some really nasty hairy
> logic to do this.
Dead right. This is where I get stuck too :)
> If I feel like playing again sometime, I might try my
> hand at some ^^;;
I noticed that you were doing the deductions programatically. Your way's a lot
clearer than using a lookup table, where the information is all hidden as to
what is happening. However, the lookup table would be a lot faster (which
doesn't really matter at the moment, though).
> If I understand correctly, it is Michael's assertion that such
> deductions, in combination with the one bit of information you may set
> arbitrarily without loss of generality, are enough to deduce the
> factors.
Yep.
> There are at most 8*(((log n)^2)/2)+2(log n) bits of information
> required for the algorithm to operate. The algorithm works in multiple
> passes, interleaving the reverse adder logic with deductions about the
> factors as described above.
Correct. This may be what your equation is representing, but the range of boxes
is from (where n is the number of bits in the product) a minimum of (n/2)^3 -
(n/2)^2 - (n/2) to a maximum of (n-1)^3 - (n-1)^2 - (n-1). This is the range
from having two primes of equal length to having one huge prime multiplied by a
tiny one.
> Since the algorithm halts as a result of a pass that does not set at
> least one bit of information, this is also an upper bound on the number
> of operations performed.
*nods*
> Hope all that helps someone ^^;; if I've misunderstood something,
> Michael, please correct me ^-^
This summarises the algorithm very well. Mind if I use it on the site as a
summary page?
> --
> Sergei Lewis - http://members.tripod.co.uk/~Folken
> "I'm not falling - this is how I fly.."
Thanks,
Michael
------------------------------
From: "Neil Couture" <[EMAIL PROTECTED]>
Subject: Re: Notion of perfect secrecy
Date: Thu, 7 Jun 2001 00:39:15 -0700
Reply-To: "Neil Couture" <[EMAIL PROTECTED]>
I Agree with Tom,
what the length 'n' tell us is just that any message of that lenght
( assuming no compression whatsoever ) could have been encrypted
in that cypher text of lenght 'n'.
Maybe i read Shannon wrong but as I understand a key of lenght n is enough
for encrypting
a msg of lenght n. that's it.
Neil
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (Tom St Denis) wrote in
> <kmBT6.47362$[EMAIL PROTECTED]>:
>
> >Ok this has gone on too long.
> >
> >Typically what you guys are missing is that the length of the message is
> >not the secret. It's the contents of the message.
>
> <crap sniped>
>
> >At any rate if the length is important just pad the message. Make the
> >message fit to be a multiple of say 64 bytes or something.
>
> DUH??? GEE WHIZ length may mean something so pad to make it
> match longest message for "perfect security" READ SHANNON YOU IDOIT
> you can't have it both ways little BOY.
>
>
>
> David A. Scott
> --
> SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
> http://www.jim.com/jamesd/Kong/scott19u.zip
> My website http://members.nbci.com/ecil/index.htm
> My crypto code http://radiusnet.net/crypto/archive/scott/
> MY Compression Page http://members.nbci.com/ecil/compress.htm
> **NOTE FOR EMAIL drop the roman "five" ***
> Disclaimer:I am in no way responsible for any of the statements
> made in the above text. For all I know I might be drugged or
> something..
> No I'm not paranoid. You all think I'm paranoid, don't you!
>
------------------------------
** 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
******************************
