Cryptography-Digest Digest #816, Volume #9 Thu, 1 Jul 99 15:13:03 EDT
Contents:
Re: trapdoor one way functions ([EMAIL PROTECTED])
Re: "Silk to Cyanide" (Jim Gillogly)
Re: Quantum Computers (Mok-Kong Shen)
Re: The One-Time Pad Paradox ("Robert C. Paulsen, Jr.")
Re: Quantum Computers (Mok-Kong Shen)
Re: Quantum Computers ("Douglas A. Gwyn")
Re: Kryptos article (Jerry Coffin)
Re: two questions ("dlk")
Re: trapdoor one way functions ([EMAIL PROTECTED])
Re: Quantum Computers (Mok-Kong Shen)
Re: The One-Time Pad Paradox ("Douglas A. Gwyn")
Re: "Silk to Cyanide" (Jim Gillogly)
Re: Quantum Computers ("Douglas A. Gwyn")
Re: Can Anyone Help Me Crack A Simple Code? (Medical Electronics Lab)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: trapdoor one way functions
Date: Thu, 01 Jul 1999 16:12:53 GMT
Nicol So wrote:
> No. We don't know if one-way functions exist because... we simply
> don't. Knowing whether one-way functions exist, either in the
> affirmative or in the negative, would settle the P =? NP question, and
> it would be such a big news that even people who are only casually
> interested in the computer science would notice.
I don't think that's entirely right. Obviously if one-way
functions exist, then P!=NP. I don't think anyone has shown
that the non-existance of one-way functions would imply P=NP.
Thus knowing wether one-way functions exist is not known to
settle P ?= NP.
Anyone know different?
--Bryan
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: "Silk to Cyanide"
Date: Thu, 01 Jul 1999 10:19:46 -0700
Neil wrote:
> I am reading Leo Marks boob "Silk to Cyanide" in in a early chapter (4
> I think) he gives an example of colving a transposition cipher. I
> used the transposition key he provided as the answer and can't get the
> correct codetext when I try to encrypt the original plaintext.
>
> Can anyone help this newbie and tell me what I might be doing
> incorrectly??
I assume you're looking at the message in Chapter 5, where he's
demonstrating key recovery to Col. Ozanne.
Ciphertext of first of two messages given in depth:
CNAER SSNGE CONNR OSEEE ISOAO LNGCE EEEER ETDLS ZELTH SSNAV ANTEM
Key shown:
1 16 17 23 11 13 19 9 22 4 21 14 10 12 24 2 20 6 5 7 3 26 25 15 8 27 18
Plaintext of first message:
C O L O N E L O Z E A N N E S S I G N A L S A R E T H
E N E R V E C E N T R E S O F S O E E N D M E S S A G
E
A common way to get mixed up is to use the dual of the actual
transposition key. However, in this case the first column is
the same in either case, and the ciphertext must start CEE;
the actual ciphertext given starts CNA.
If the key were one longer, the CN would line up, but it
doesn't also work for the second message in depth. I think
we need to do the actual key recovery ourselves to see what
it should have been.
Either another key was used to encrypt it, or no key at all.
I'm guessing this was part of Marks' process of twitting
the good Colonel: he knew by this time Ozanne's eyes
would have glazed over and he would be looking for his exit
strategy from the tutorial, and would have taken Marks' word
for anything he cared to utter. This key translates to
ALLTHINGSBRIGHTANDBEAUTIFUL. I suspect we'd have better
luck comparing it to one of the rude verses composed by the
Coders of Grendon.
I'm finding the "Between Silk and Cyanide: A Codemaker's War"
enlightening and entertaining, by the way.
--
Jim Gillogly
8 Afterlithe S.R. 1999, 16:27
12.19.6.5.16, 7 Cib 4 Tzec, Eighth Lord of Night
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
Date: Thu, 01 Jul 1999 19:08:37 +0200
Douglas A. Gwyn wrote:
>
> Mok-Kong Shen wrote:
> > ... We can have the concept of infinity and work
> > with it in theory, but any number that one actually operates upon
> > must be finite, even if it can be extremely large.
>
> That's certainly not true, as witnessed by the fact that Cantor
> did work with infinities. In fact a lot of us work with infinities.
> There is even a (finite) representation for some kinds of infinity
> in most floating-point processor chips made today.
If you consider Cantor's infinities to be of practical instead of
theoretical value, i.e. having real-life applications, then your
first statement is certianly true. The 'infinity' in the floating
point standard is used, if I don't err, to enable computations to
continue (instead of abort as in the old days) and let the user know
that something unusual has happened, in case such continuations are
nonetheless sensible in the particular computer run. Not much sensible
informations can be obtained directly from such 'infinity' values
in the practical computations. If you know a counter-example in
pratice, I should appreciate very much to learn that.
M. K. Shen
M. K. Shen
------------------------------
From: "Robert C. Paulsen, Jr." <[EMAIL PROTECTED]>
Subject: Re: The One-Time Pad Paradox
Date: Thu, 01 Jul 1999 12:34:34 -0500
"Douglas A. Gwyn" wrote:
>
> "Robert C. Paulsen, Jr." wrote:
> > Although the chance of a OTP encrypting cleartext in a way that the
> > resulting ciphertext gives away the secret is vanishingly small it
> > is not impossible.
>
> You really need to consider what constitutes knowledge (on the part
> of the adversary). He does not learn anything whatsoever from a
> properly functioning OTP ciphertext that accidentally appears to
> tell him something. That's because there is no basis for taking
> the apparent text as plaintext. The actual odds are so great that
> any apparent text is *not* the actual message, that a rational
> adversary must reject *all* such "messages" (assuming he knows the
> OTP is working properly).
Lets take an example. Suppose we discover the cure for cancer. This
becomes very valuable information. We want to send this back to the head
office but know a rival company routinely intercepts our messages so we
request our signals department to encrypt the message.
Scenario 1: The signals department messes up and neglects to do the
encryption.
Scenario 2: The signals department uses a OTP to encrypt the message but
in a one-in-a-gazillion chance, the encrypted text describes, perhaps in
different words, our cure.
Can we say that scenario two didn't reveal the secret?
I know that the chance of scenario 2 is vanishingly small, but that
doesn't negate what John Savard said in his original message.
>
> This has nothing to do with G�del.
I said it was an *analogy*. The point being that a proof is a proof even
if it depends on a extreme case.
--
____________________________________________________________________
Robert Paulsen http://paulsen.home.texas.net
If my return address contains "ZAP." please remove it. Sorry for the
inconvenience but the unsolicited email is getting out of control.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
Date: Thu, 01 Jul 1999 19:37:52 +0200
Douglas A. Gwyn wrote:
>
> > Can anyone provide any additional insight.
>
> Sure; why don't you simply go read the QC literature?
There is recently published in the Springer Lecture Notes a proceedings
of a conference on quantum computing. It should reflect the state
of the art quite well.
M. K. Shen
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
Date: Thu, 01 Jul 1999 17:31:06 GMT
Mok-Kong Shen wrote:
> ... The 'infinity' in the floating
> point standard is used, if I don't err, to enable computations to
> continue (instead of abort as in the old days) and let the user know
> that something unusual has happened, in case such continuations are
> nonetheless sensible in the particular computer run. Not much
> sensible informations can be obtained directly from such 'infinity'
> values in the practical computations. If you know a counter-example
> in pratice, I should appreciate very much to learn that.
You seem to be thinking of NaNs (Not-a-Numbers), which allow a
computation to proceed even though it has become meaningless,
and a single test for NaNness performed after the computation.
IEEE/IEC floating point signed infinity representations allow
computations to produce *meaningful* numeric answers in many
computations, where otherwise, special tests and different code
branches would be required. For example:
quantity_seen := 0
money_spent := $10,000.00
money_per_each := money_spent / quantity_seen
next_years_budget := $1,000,000.00
expect_to_see := next_years_budget / money_per_each
This correctly reports that we expect to see zero whatevers
in return for budgeting $1,000,000.00, based on our trial run.
Note that the intermediate quantity money_per_each is infinite.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Kryptos article
Date: Thu, 1 Jul 1999 00:35:31 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> John Myre wrote:
> > Like, "I have found a truly wonderful break for Skipjack, but
> > the proof is too large to fit in the margin. - D. Coppersmith".
>
> That didn't seem to work very well for Fermat's "theorem".
It did in a way -- the proof may have taken a few hundred years, but
people DID keep working on it until it was found...
------------------------------
From: "dlk" <[EMAIL PROTECTED]>
Subject: Re: two questions
Date: Thu, 01 Jul 1999 06:40:20 GMT
[EMAIL PROTECTED] wrote in message <7lebea$u7q$[EMAIL PROTECTED]>...
><snip>
>
>Ooops. The max key size is still log2(256!) but the max period is
>2^1700 which is log2(256!) x 2^16. The max key size comes to 210 bytes
>or so. If the key is longer there will related shorter keys (i.e it
>would be possible to have a key of 50 bytes equal a key of 250 bytes...)
Now that'un I'll have to ponder awhile.... thanks for the mental food, there
Tom,
it'll make these midnite shifts go a little faster.
Dave Keever
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: trapdoor one way functions
Date: Thu, 01 Jul 1999 16:54:23 GMT
[EMAIL PROTECTED] wrote:
> Nicol So <[EMAIL PROTECTED]> wrote:
> > Are you sure exponentiation (defined over a suitable finite group)
is
> > trapdoor one-way, instead of just one-way? What kind of trapdoor
> > information would allow you to compute discrete log fast?
>
> The DLP and IFP are both trapdoor one-way. In the case of RSA you can
> find the private key by factoring the modulus and building the keys.
> If they work then voila. You would have to check out how they cracked
> RSA-140 and such cause I am not sure....
>
> DLP also has an inverse which is difficult to find. If it's defined
as
> g^x mod n (x < n, g = generator). Then there is some log(g^x mod n) /
> log(g) which is hard to find (hence the problem). I am not sure if
two
> different inputs will produce the same output (i.e two logs...) but I
> don't think there would be. Could someone comment?
You didn't understand Nicol's question, and it seems you
don't know what the terms mean. Neither DLP nor IFP look
like a trap-door one-way function. We can use IFP to
construct (what looks to be) a TDOWF, and IFP to construct
something similar.
In the case of RSA, the TDOWF is taking a modular root.
It seems to be hard without the trap-door information.
It's easy if we know the factors of the modulus.
In the case of discrete log, the sort-of-TDOWF is
something like:
For given g, p, y1,
f(x2, m) = (g^x2 mod p, m XOR g^(log y1 * x2) mod p)
The trap-door secret is the mod p log of y1. It's not
really a TDOWF since we can only recover m, not x2.
--Bryan
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
Date: Thu, 01 Jul 1999 19:53:01 +0200
Douglas A. Gwyn wrote:
>
> Mok-Kong Shen wrote:
> > ... The 'infinity' in the floating
> > point standard is used, if I don't err, to enable computations to
> > continue (instead of abort as in the old days) and let the user know
> > that something unusual has happened, in case such continuations are
> > nonetheless sensible in the particular computer run. Not much
> > sensible informations can be obtained directly from such 'infinity'
> > values in the practical computations. If you know a counter-example
> > in pratice, I should appreciate very much to learn that.
>
> You seem to be thinking of NaNs (Not-a-Numbers), which allow a
> computation to proceed even though it has become meaningless,
> and a single test for NaNness performed after the computation.
> IEEE/IEC floating point signed infinity representations allow
> computations to produce *meaningful* numeric answers in many
> computations, where otherwise, special tests and different code
> branches would be required. For example:
> quantity_seen := 0
> money_spent := $10,000.00
> money_per_each := money_spent / quantity_seen
> next_years_budget := $1,000,000.00
> expect_to_see := next_years_budget / money_per_each
> This correctly reports that we expect to see zero whatevers
> in return for budgeting $1,000,000.00, based on our trial run.
> Note that the intermediate quantity money_per_each is infinite.
Maybe I misunderstood. But this appears to be something very
curious for giving to the hands of a practical programmer. If
one wants to 'catch' the case that 'quantity_seen' never gets
out of its initial value 0, one should check that directly. A
programmer that stays away from the so-called tricks wouldn't
code as above, I believe.
M. K. Shen
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: The One-Time Pad Paradox
Date: Thu, 01 Jul 1999 18:00:09 GMT
"Robert C. Paulsen, Jr." wrote:
> Scenario 2: The signals department uses a OTP to encrypt the message but
> in a one-in-a-gazillion chance, the encrypted text describes, perhaps in
> different words, our cure.
> Can we say that scenario two didn't reveal the secret?
Yes, it does not reveal anything (other than surface characteristics
such as the fact that a message was sent, its length, etc.).
Why don't you ask the same kind of question about the much more
likely scenario:
Scenario 3: The account number of a billionaire's Swiss bank
account is disclosed.
If you understand the relevance, or more accurately, lack of
relevance, of the "message" supposedly revealed in scenario 3
to the actual plaintext message, then you should understand
the *same* relevance, i.e. lack of any, of the "message" of
scenario 2. Only once in a zillion times will such a coherent,
accidental message state something that is *true*; the rest of
the time, it will be asserting some falsehood or another.
(It will get the account number wrong almost all the time.)
If the adversary mistakenly thinks it is a plaintext "bust",
it will practically never work out to his advantage.
It is precisely because there is no causal relationship
between the actual message and the one supposedly seen in
the ciphertext, that no information is conveyed to the
interceptor.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: "Silk to Cyanide"
Date: Thu, 01 Jul 1999 11:10:58 -0700
Jim Gillogly wrote:
> I assume you're looking at the message in Chapter 5, where he's
> demonstrating key recovery to Col. Ozanne.
>
> Ciphertext of first of two messages given in depth:
> CNAER SSNGE CONNR OSEEE ISOAO LNGCE EEEER ETDLS ZELTH SSNAV ANTEM
>
> Key shown:
> 1 16 17 23 11 13 19 9 22 4 21 14 10 12 24 2 20 6 5 7 3 26 25 15 8 27 18
>
> Plaintext of first message:
> C O L O N E L O Z E A N N E S S I G N A L S A R E T H
> E N E R V E C E N T R E S O F S O E E N D M E S S A G
> E
>
> A common way to get mixed up is to use the dual of the actual
> transposition key. However, in this case the first column is
> the same in either case, and the ciphertext must start CEE;
> the actual ciphertext given starts CNA.
Woops. Right observation, but wrong system. Turns out this is double
transposition -- ironic, given the recent discussion. If we write out
the intermediate ciphertext from the above array we get:
CEESSLDETNEGEANESOENSNVEOEE
NERSONLEHGLCIOARZNORSFAESMT
A
Putting it back through the same transposition block a second
time, we get the ciphertext as advertised, starting CNA ER...
> for anything he cared to utter. This key translates to
> ALLTHINGSBRIGHTANDBEAUTIFUL. I suspect we'd have better
> luck comparing it to one of the rude verses composed by the
> Coders of Grendon.
I like my original wrong explanation better, though.
--
Jim Gillogly
8 Afterlithe S.R. 1999, 18:07
12.19.6.5.16, 7 Cib 4 Tzec, Eighth Lord of Night
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
Date: Thu, 01 Jul 1999 18:19:31 GMT
Mok-Kong Shen wrote:
> Maybe I misunderstood. But this appears to be something very
> curious for giving to the hands of a practical programmer. If
> one wants to 'catch' the case that 'quantity_seen' never gets
> out of its initial value 0, one should check that directly. A
> programmer that stays away from the so-called tricks wouldn't
> code as above, I believe.
For something like two decades now, there has been a very
active numerical programming community that wants precisely
this ability, namely to code a single formula without having
to insert such special-case tests (which slow down the
computation, are error-prone, and cause more work for the
programmer).
In complex analysis, the Riemann sphere is introduced (usually
in connection with rational functions), which treats the
"point at infinity" the same as any other point in the complex
plane. This unifies the treatment and eliminates the need for
special consideration of such things as:
What happens to f(z) = (1-z)/(1+z) when z is -1?
By allowing the "infinite" value to be treated consistently
with other values, a great simplification is achieved, and all
the formulas work *even in the "exceptional" cases*.
Now, IEEE/IEC f.p. is strange in that it tries to assign
*signs* to *distinct* values of infinity (also to distinct
values of zero), which makes sense in some contexts but not
in others. There have been great debates over the signedness
issue, but not over the wisdom of computing with infinities
(where appropriate). Mathematically, +0 and -0 are equal,
and there is but a *single* "point at infinity" in the
Riemann scheme, so whatever information the sign of zero or
infinity is supposed to convey, it is not arithmetic information.
One does need to keep in mind that the normal laws of
arithmetic need to be modified for infinities, and in
particular, infinity/infinity is indefinite, not 1.
The floating-point implementations are responsible for getting
such details right.
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Can Anyone Help Me Crack A Simple Code?
Date: Thu, 01 Jul 1999 12:58:18 -0500
mercury wrote:
> ***********************************************
> Design of the Black Box
>
> The electronics are of sub-miniature type on multi-
> layer circuit boards, which are very static-
> sensitive. There is a ten digit key pad for entering
> the codes. The key pad is integrated into one of
> the main boards. The Black Box has no RS232 port.
>
> So it is nearly impossible (with the equipment I
> have) to enter the codes any other way besides by
> hand with the key pad. It is not possible to try
> a large number of codes.
>
> The light bulbs have a built-in microchip. This
> chip configures the Black Box for whichever light
> bulb is being used. With the exception of this
> chip, the electronics are identical in all Black
> Boxes. (I MAY be able to retrieve the information
> off of this chip. I may have answered the question
> of where the algorithm is right here. I'll look
> into this further.) The lightbulbs are only
> installed or changed at the Black Box company.
How about some more detail here. Could you hook up
some wires to the keypad and let a computer try various
codes? Can you hook up the output to a computer and
see the results? A simple logic interface could probably
brute force this thing in a day or so. Are there only
decimal digits on the keypad or does it include a few
hex characters? Can the company reprogram it to accept
more dates or do you just buy new codes and it knows
what date it is?
Once you reverse engineer the electronics, the crypto
will be easy. How much is it costing to reverse engineer
this black box versus the cost of just buying new codes?
Patience, persistence, truth,
Dr. mike
fillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfiller
------------------------------
** 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
******************************
