Cryptography-Digest Digest #796, Volume #9 Mon, 28 Jun 99 23:13:03 EDT
Contents:
Re: Interesting RSA question (Ed Yang)
Re: Interesting RSA question (S.T.L.)
Re: Why mirrors invert left-to-right (was: Kryptos article) (S.T.L.)
Why mirrors invert left-to-right (was: Kryptos article) (Nicol So)
Re: one time pad (Greg Ofiesh)
Re: one time pad ([EMAIL PROTECTED])
Re: The One-Time Pad Paradox (S.T.L.)
Re: one time pad ([EMAIL PROTECTED])
Re: one time pad (Jerry Coffin)
Re: Block Ciphers and Crpytanalysis (Uri Blumenthal)
----------------------------------------------------------------------------
From: Ed Yang <[EMAIL PROTECTED]>
Subject: Re: Interesting RSA question
Date: Mon, 28 Jun 1999 17:58:51 -1000
Gilad Maayan wrote:
>
> Thanks for your reply.
>
> About that padding - if it's completely random, you wouldn't be able
> to read the decrypted message, would you? I assume you'd have to have
> some sort of padding technique that would allow you to descramble the
> original message from the padding and read it, once decryption has
> taken place. Correct me if I'm wrong.
This is iuwe62382y8g28fy28cgcwyu8ff78g my answer.
The garbage87632487g238bf897y24u7h24fhcan easily be
discarded.
--
Oxygen : Love It Or Leave It !
------------------------------
From: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: Interesting RSA question
Date: 29 Jun 1999 01:09:25 GMT
<<Let's take the following unlikely scenario: You take a 20-bit
cyphertext, encrypt it with an RSA key (1024-bit modulus), and get a
roughly 1000-bit-long cyphertext. I've been made aware of the fact
that a cyphertext usually baloons to the size of the key, regardless
on the plaintext length.>>
It does, and 1000-bits is a reasonable estimate.
<<Now, say you want to go the opposite route: Take a random 1000-bit
long cyphertext, and decrypt it using the corresponding secret key, to
get a 20-bit number. Naturally, this won't be much more than a pretty
random 20-bit number, but it suits my purposes. >>
Okay. However... I'll hold on to my comment.
<<So, my question is: Knowing both public and secret key lengths, what
formula could be used to determine the exact length of the 1000-odd
random number from which you could obtain 20 bits through decryption?>>
Here's my comment: how many 1000-bit cyphertexts can decrypt to a 20-bit
number, given a keypair? RSA encryption doesn't lose information: one
ciphertext is paired with one plaintext. Therefore, there can be no more (at
the absolute upper limit!) than 2^20 such 1000bit cyphertexts. Compare THAT to
the 2^1000 possible 1000bit ciphertext. That's a 1 in 2^980 chance of it
happening. The real chance is even lower, by the way. Compare that to me seeing
a message encrypted with a symmetric cipher, me picking 128 bits out of thin
air, and finding that the 128 bits I picked are the right key to decode the
message! That probablitity is low: 1 in 2^128. However, that is 2^852 (if I
calculate right) times MORE likely than the scenario you proposed. Clearly,
finding a 1000bit cyphertext at random that decrypts to a 20-bit number is
RIDICULOUSLY unlikely.
For more fun, the half-life of a proton decaying is estimated to be 10^40
years, or thereabouts. (I'm using a higher estimate than the lower bound of
10^35 years or such.) So if you have a single proton and wait a year, its
chance of decaying is 1 in 10^40. If you wait one second, the chance of a decay
is about 10^7 more unlikely because a second is about 10^-7 of a year. So the
chance of a single proton decaying in a second is 1 in 10^47... I think. The
probablities for any one proton decaying is independent of the others. The
probablity of you watching SIX protons and they ALL decay in a second is
10^47*10^47*10^47*10^47*10^47*10^47 = 1 in 10^282. HOLY COW! However, the
chance of this happening is MUCH higher than the chance of finding a 1000bit
cyphertext at random that decrypts to a 20bit number, because that's a 1 in
10^295 chance.
Basically, I'm saying here that the chance of your scenario happening is
ridiculously unlikely, and I don't believe that it can be made more probable.
If I've goofed in my calculations or even my basic assumptions, tell me.
-*---*-------
S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^3021377 - 1 is PRIME!
Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
E-mail block is gone. It will return if I'm bombed again. I don't care, it's
an easy fix. Address is correct as is. The courtesy of giving correct E-mail
addresses makes up for having to delete junk which gets through anyway. Join
the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
.sig is shorter and contains 3379 bits of entropy up to the next line's end:
-*---*-------
Card-holding member of the Dark Legion of Cantorians, the Great SRian
Conspiracy, the Triple-Sigma Club, the Union of Quantum Mechanics, the
Holy Order of the Catenary, and People for Ethical Treatment of Digital
Tierran Organisms
Avid watcher of "World's Most Terrifying Causality Violations", "World's
Scariest Warp Accidents", "When Tidal Forces Attack: Caught on Tape",
and "When Kaons Decay: World's Most Amazing CP Symmetry Breaking Caught
On [Magnetic] Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #4: Thou Shalt Have Quantized Angular Momenta.
------------------------------
From: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: Why mirrors invert left-to-right (was: Kryptos article)
Date: 29 Jun 1999 01:29:41 GMT
<<It's not even a physics problem--it's a
philosophical one.>>
It's not even a philosophical (gag) problem. It's NOT a problem!
Mirrors invert FRONT-TO-BACK. When we imagine ourselves standing side-by-side
our mirror image, making our Fronts identical, then another direction MUST be
reversed. We like to think that L-R is reversed because we are bilaterally
symmetric. This is, because as someone else said, our left side resembles our
right side much more than our head resembles our feet. If, however, we were
simply C F Cl Br I atoms (if those exist), then we would have no problem - we
would understand the concept of chirality and not be confused by the front-back
switch.
Have fun and avoid philosophy at all costs.
-*---*-------
S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^3021377 - 1 is PRIME!
Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
E-mail block is gone. It will return if I'm bombed again. I don't care, it's
an easy fix. Address is correct as is. The courtesy of giving correct E-mail
addresses makes up for having to delete junk which gets through anyway. Join
the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
.sig is shorter and contains 3379 bits of entropy up to the next line's end:
-*---*-------
Card-holding member of the Dark Legion of Cantorians, the Great SRian
Conspiracy, the Triple-Sigma Club, the Union of Quantum Mechanics, the
Holy Order of the Catenary, and People for Ethical Treatment of Digital
Tierran Organisms
Avid watcher of "World's Most Terrifying Causality Violations", "World's
Scariest Warp Accidents", "When Tidal Forces Attack: Caught on Tape",
and "When Kaons Decay: World's Most Amazing CP Symmetry Breaking Caught
On [Magnetic] Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #4: Thou Shalt Have Quantized Angular Momenta.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Why mirrors invert left-to-right (was: Kryptos article)
Date: Mon, 28 Jun 1999 21:18:05 -0400
Lincoln Yeoh wrote:
>
> On Sat, 26 Jun 1999 03:49:50 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
> wrote:
>
> >Um, Jim, mirrors don't reverse in any particular direction.
> >Martin Gardner had a discussion of this in one of his books:
> >Why is your image in a flat mirror reversed left-to-right,
> >not top-to-bottom?
>
> Maybe it because your right hand looks like your left hand and your head
> doesn't look like your feet?
>
> They just mirror stuff, that's all, just like shadows in some ways.
It's deeper than that. Without spoiling the fun, I can tell you that
it's not an optics problem. It's not even a physics problem--it's a
philosophical one.
Consider this thought experiment: you stand in front of a mirror and
take a portrait of yourself with a Polaroid camera. The picture
basically captures what you see in the mirror. Then a friend of yours
moves into the position where the mirror was, and takes another picture
of you with another Polaroid camera.
Now compare the two pictures, they are (basically) inverted images of
each other *along the vertical axis*. Why does the inversion take place
along one of infinitely many possible axes? Einstein said there's no
preferred frame of reference in nature. Why does the inversion
"phenomenon" take place along a particular axis but not others?
Answering these questions is the real point of the puzzle.
Have fun.
Nicol
------------------------------
From: Greg Ofiesh <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Tue, 29 Jun 1999 01:43:34 GMT
> That's one of the last things I would bet on. The hypothesis that
quantum
> fluxuations are random is one of the weakest in science today; it's
not
> backed by any theory with any predictive value.
Thanks for the heads up.
> >...what is the definition of "most common situation" that
> >would make OTPs useless?
>
> Well, think about it. With computers
> responsible for communication, you
> usually don't have any more or less
> secure channels; you're stuck with
> electronic networks and human
> memory for passwords.
I have never considered using the Internet or any other communications
media to transfer a OTP to the other party. In my mind, OTP requires
sneaker net exclusively.
> But these aren't the most common or most
> general uses, simply the most
> prevalent among computer users.
Is that not what common means? The most prevalent? But I would say
that this is true. That OTP is no where near the use of commonly found
ciphers because its deployment prevents it from being used for the
common use we see today.
> >And why has anyone even come to believe that my (unstated) plans for
> >OTP use are common or average?
>
> Because you haven't said otherwise, and you asked our advice.
Is that not presumptuous? (please don't stone me!) I simply asked for
peoples' advice (and I thank everyone of you for helping me) on
deploying a OTP and I narrowed the focus for advice on three points
surrounding the presumption that random numbers had to be controlled to
avoid extreme patterns that could weaken the pad. Even in dealing with
these points the deployment or use cannot be inferred. (And I learned I
was wrong.)
> >... Look at the whole concept of Certifying
> >Authorities. The question that comes into
> >my mind is, "Who are they?
> >Can they become corrupt? Would I trust them
> >with my data?" So you can
> >see that in my mind, PKey is almost useless
> >just on that grounds alone.
>
> Key exchange is also useful, and that uses public key techniques.
Good point on your part (I assume it is true) and bad example on mine.
> >The discussion, as I see it, has to do with provable security...
> Generally speaking, security flaws come as part of the system, not the
> algorithm. If you use one of the standard, documented, and tested
ciphers
> you'll be clear up to the brute-force difficulty of your keys -- and
> endangered by every weakness in your system.
And with a OTP that approaches the theoretical OTP, that even begins to
eliminate the brute force difficulty, correct?
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
Date: Mon, 28 Jun 1999 09:52:10 -0400
From: [EMAIL PROTECTED]
Subject: Re: one time pad
Douglas A. Gwyn wrote:
>
> [EMAIL PROTECTED] wrote:
> > So, given that it is and will remain impossible to prove a negative,
> > that there are no weaknesses in a key generator, we can conclude that
> > there cannot be perfect cipher systems. LIke Godels proof of the
> > incompleteness of mathematical logics, we can now take this lack of
> > provability for granted.
>
> No, you might however conclude that that one line of argumentation
> is incapable of achieving a proof.
Are you implying that some other approach might yeild a rigorous proof
of key quality -- i.e., randomness?
------------------------------
From: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: The One-Time Pad Paradox
Date: 29 Jun 1999 01:25:12 GMT
I'm responding to different people here: they know who they are.
<<I disagree. While your statement is correct in a wold of perfect
implementations _and_ perfect operators, it is false in a very practical
sense.>>
Who says I need to be practical? This whole "null key" buisness is ridiculously
unlikely in the first place.
<< Given that I know something about the context of the message, I
can estimate its plausibility. I can compare that plausibility against
the possibility that an operator error transmitted the plaintext en
clair by accident. Since this is almost always going to come out in
favor of an operator error (for non-trival message length) over the
probability of accidentally creating a cipher text that is intelligible
at all, I'll make the right decision.>>
That is only IF it is operator error. If we go to the nasty, grimy, messy Real
World, and we allow the existence of operator error, then the Adversary is
going to almost ALWAYS be right in deducing that operator error has occurred.
Every once in a while, he will be fooled by an intelligble plaintext that is
not the real thing. Even less likely but still possible is the infamous "null
key" scenario. The Adversary has NO means of detecting the
not-the-real-plaintext scenario from the null-key scenario provided our RNG is
not at fault, but the Adversary will definitely almost always know when a fault
has occurred.
<<I suppose that there is indeed a bit paradox here. The analyst sees a
meaningful sentence. If he knows for sure that the sender uses
an OTP, then what you said sounds right, namely he doesn't surely
know whether it is the correct plaintext. What happens if he
doesn't know for sure that the sender uses an OTP? His best guess
will be that the sender possibly forgets to encrypt his message.
I think the paradox is to be explained away in the following way:
(1) The chance of an ideal OTP producing a string of all 0's of
any meaningful size is extremely negligibly small. (2) The chance
of one being able to create an ideal OTP in this real world is
also extremely negligibly small. (I personally would consider both
to be identically zero).>>
See previous comments about operator error and the Adversary's ability to
detect it: I believe they apply to your thoughts as well.
<<I like to take this opportunity to repeat an old question of mine
related to the inability in the OTP case of the analyst to decide
which is the correct message. If one doesn't have an ideal OTP
but only something fairly random and uses it to XOR with the true
message M_r together with n plausible messages M_1, M_2, ... M_n,
what is the chance (as a function of n?) of the analyst to obtain
the true message M_r?>>
You mean something like Gibberish XOR M_r XOR M_1 XOR M_2...? Well, it will be
a little harder than finding out Gibberish XOR M_r (which depends on the
strength of the gibberish, of course), because finding M_moo and M_cow is
not-so-difficult (I believe) when given M_moo XOR M_cow. I can't make any
definite statements, though.
-*---*-------
S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^3021377 - 1 is PRIME!
Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
E-mail block is gone. It will return if I'm bombed again. I don't care, it's
an easy fix. Address is correct as is. The courtesy of giving correct E-mail
addresses makes up for having to delete junk which gets through anyway. Join
the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
.sig is shorter and contains 3379 bits of entropy up to the next line's end:
-*---*-------
Card-holding member of the Dark Legion of Cantorians, the Great SRian
Conspiracy, the Triple-Sigma Club, the Union of Quantum Mechanics, the
Holy Order of the Catenary, and People for Ethical Treatment of Digital
Tierran Organisms
Avid watcher of "World's Most Terrifying Causality Violations", "World's
Scariest Warp Accidents", "When Tidal Forces Attack: Caught on Tape",
and "When Kaons Decay: World's Most Amazing CP Symmetry Breaking Caught
On [Magnetic] Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #4: Thou Shalt Have Quantized Angular Momenta.
------------------------------
Date: Mon, 28 Jun 1999 09:58:44 -0400
From: [EMAIL PROTECTED]
Subject: Re: one time pad
William Tanksley wrote:
>
> On Mon, 28 Jun 1999 03:38:51 -0400, [EMAIL PROTECTED] wrote:
> >William Tanksley wrote:
>
> >> On Sun, 27 Jun 1999 01:54:55 -0400, [EMAIL PROTECTED] wrote:
> >> >William Tanksley wrote:
>
> >> >> There is NO single stream of data coming out of an alleged RNG which would
> >> >> prove to me that it wasn't an RNG.
>
> >> >Well I have this special RNG that meets these criteria. It's quite
> >> >cheap. It is also sold under the name "zero ohm resistor", but for
> >> >today only, I'll make a special offer of $10.00 each.
>
> >> Did I mention that there's no single stream which can prove (or even
> >> suggest) to me that an alleged RNG is in fact a true RNG?
>
> >> Now, give me control and let me generate what I consider to be multiple
> >> streams (under my control), and let me see the generator's details, and
> >> let people who specialize in the details see them, and after a while I'll
> >> consider it suggested that the thing is an RNG.
>
> >The interesting issue isn't that you would decide, but how you would
> >decide. Do you use Karnak's Criteria (hold envelop to forehead)? Is
> >there anything in your decision process that does not fit into a DTM?
> >If it all fits in a DTM it can be completely automated.
>
> My primary point is negative, not positive -- a single stream tells me
> nothing. It doesn't tell an automaton anything, either.
In what sense does a single generator produce multiple streams?
>
> >If it can be automated it can run in real time. If it runs on the
> >output of your generator, how will you react if/when it complains?
>
> As I mentioned, the automaton can't run in real time with respect to the
> generator -- the automaton has to have control over the generator,
> including the ability to restart it in any and all ways possible (power
> cycle, etc).
>
> If the automaton says the generator produces suspicious streams, I'll
> throw the generator away. If it doesn't complain, then I'll consider the
> possibilty that the stream might be acceptable as a random sequence
> generator.
>
> I might actually use it as such if I cannot see patterns in it, and if
> other people (including those more skilled than I) produce similar
> results.
>
> There are some true RNGs out there which fit these requirements, although
> it's not certain that I'd want to use any of them for OTPs.
>
> --
> -William "Billy" Tanksley
> Utinam logica falsa tuam philosophiam totam suffodiant!
> :-: May faulty logic undermine your entire philosophy!
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: one time pad
Date: Mon, 28 Jun 1999 15:53:20 -0600
In article <7l8hfi$poi$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> The discussion, as I see it, has to do with provable security. In the
> end, I would use encryption ABC if that was absolutely the only one
> that could be proved uncrackable. My application is specialized and I
> can for the most part work with the requirements and restrictions of
> almost any cipher.
I don't think you can prove a real implementation of an OTP completely
unbreakable, but I think that if you do a good implementation, it's as
close as you're going to get. Nicely enough, just earlier today I saw
somebody has plans for a random-number generator based on radioactive
decay, which should work quite nicely for a OTP.
There may be no way to theoretically prove this is unbreakable, but I
don't think I'd hesitate at staking my life on its security...
------------------------------
From: Uri Blumenthal <[EMAIL PROTECTED]>
Subject: Re: Block Ciphers and Crpytanalysis
Date: Mon, 28 Jun 1999 23:02:39 -0400
Reply-To: [EMAIL PROTECTED]
JPeschel wrote:
> I've recently added my friend Fauzan Mirza's report, "Block Ciphers
> and Crpytanalysis" to my web page........
> You'll find it in the "Algorithms and Attacks" page........
> http://members.aol.com/jpeschel/index.htm
Thank you! This is a very good report. I enjoyed reading it and
recommend it to others.
--
Regards,
Uri
-=-=-==-=-=-
<Disclaimer>
------------------------------
** 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
******************************
