Cryptography-Digest Digest #895, Volume #12 Wed, 11 Oct 00 09:13:00 EDT
Contents:
Re: On block encryption processing with intermediate permutations (Mok-Kong Shen)
Re: Why trust root CAs ? (Paul Rubin)
Re: Internet Security Question (Paul Rubin)
Re: FTL Computation (ca314159)
Re: A new paper claiming P=NP (Volker Hetzer)
EKE, RSA, and Compression? (John Savard)
Re: How Colossus helped crack Hitler's codes (Olivier Breard)
Re: A new paper claiming P=NP (Kent Paul Dolan)
Re: A new paper claiming P=NP (Kent Paul Dolan)
Re: A new paper claiming P=NP (Kent Paul Dolan)
Re: Modular Exponentiation ("bubba")
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block encryption processing with intermediate permutations
Date: Wed, 11 Oct 2000 12:26:41 +0200
Bryan Olson wrote:
>
> Mok-Kong Shen wrote:
> > Bryan Olson wrote:
> [...]
> > > I don't see how it could possibly be unclear what scheme
> > > my attack applies to. The modified scheme is not relevant
> > > to the questions at issue.
> >
> > Since I proposed my scheme, I naturally want it to be
> > useful, i.e. not being cracked. So, since you told the
> > way that prevents your attack to function, I modify it
> > accordingly so that it is immune to it. Why not, since
> > the modification is trivial??
>
> It only addresses the particular exploit, not the defect.
If I prove a theorem and there is a weakness, say, it depends
on the existence of a quantity p being prime and someone
points out that in a degenerate case p can be 1 and hence
the proof is invalid and I do a little modification such
that this case can be avoided and a prime p still can be
chosen, then my purpose of establishing the theorem is
achieved, isn't it?
>
> > > > So through this trivial modification (simply leaving out
> > > > one inter-round permutation, while maintaining the other
> > > > inter-round permutations as before) my scheme becomes
> > > > immune to your attack according to what is quoted from
> > > > you above exactly. Do you have anything to say to that
> > > > now??
> > >
> > > The FAQ says it well:
> > >
> > > If you don't have enough experience, then most likely
> > > any experts who look at your system will be able to find
> > > a flaw. If this happens, it's your responsibility to
> > > consider the flaw and learn from it, rather than just
> > > add one more layer of complication and come back for
> > > another round.
> >
> > It suffices for me that you apparently don't have anything
> > to say to what I wrote above now.
>
> The quote from the FAQ says something important.
Something important but not what YOU say. The following
in my signature is also important that you should read
and remember.
M. K. Shen
================================================================
Was sich ueberhaupt sagen laesst, | Whatever can be said
laesst sich klar sagen; | can be clearly said;
und wovon man nicht reden kann, | and silence must be kept
darueber muss man schweigen. | on what one cannot tell.
|
Ludwig Wittgenstein | (a translation)
(1889 - 1951)
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: 11 Oct 2000 03:10:50 -0700
[EMAIL PROTECTED] (Vernon Schryver) writes:
> In other words, since when is a DUNS number a proof of identity, honesty,
> financial stability, or anything else?
It takes more than a DUNS number to get a class 3 certificate, at
least from Verisign. You also have to control the phone number listed
for the company, i.e. they look up the number and call it. They don't
just believe the phone number you give them in the CSR.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Internet Security Question
Date: 11 Oct 2000 03:13:39 -0700
David Hopwood <[EMAIL PROTECTED]> writes:
> This is a bug in IE5 with SGC certificates. The last thing I heard was
> that Microsoft were refusing to fix it; they apparently don't think it's
> important because it is "just a user interface issue", which should tell
> you something about their attitude to security and correctness of software
> in general.
Do you think it's not fair to say it's a bug with the Verisign CA roots,
since the intermediate CA root is marked with capability bits that
the public root isn't marked as being able to grant?
------------------------------
From: ca314159 <[EMAIL PROTECTED]>
Crossposted-To: sci.astro,sci.physics.relativity,sci.math
Subject: Re: FTL Computation
Date: Wed, 11 Oct 2000 10:16:13 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> ca314159 wrote:
> >
> > In article <[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] wrote:
> > > ca314159 wrote:
> > > >
> > > > If the projection of a spot of light can virtually move FTL
> > > > then so too can the projected images of a slide rule's slides.
> > > > The computation 'in effect', takes place FTL.
> > > >
> > >
> > > But the time between when you move the slide and you see
> > > the projection is still the round trip light travel time
> > > to the thing you're projecting the slide onto.
> >
> > You're right; I/O is a bottleneck.
> > That's not my point though.
> >
>
> It's not an I/O limitation. It's a limitation on
> how fast you can transmit a message from point to
> point.
>
> > Whether you call this effect lighthouse, waterhose, headlight
> > or scissors... it can be used to do very interesting things.
> > I don't just think so, I know so.
> >
> > >
> > > The real limitation is how fast you can transmit information.
> > >
> >
> > First, one has to know what "information" is.
> > What's your definition ?
> >
>
> I want to transmit a signal from one observer to another. If I use
the
> lighthouse idea, I can send information from a sender to one observer
> at time t and then information to a second observer at t + dt
> where the spatial separation of the two receivers is dx
> and dx/dt > c. But I'm sending two different signals to two
> different receivers. The inforamtion goes from the sender
> to either receiver at c. The two receivers can't compare what
> they receive and deduce a message from it (other than
> on bit of information) until they can exchange observations
> about what they received.
This I agree with. It's the same problem in quantum
teleportation where the classical channel is needed
to verify the instantaneous teleportation.
>
> Information is a stream of bits going from a sender to
> a single receiver. If you send one bit to one receiver
> and another to a different receiver, they need to
> communicate with each other to figure out what the two
> bits are and the information is not travelling faster than
> c.
Definitely. Velocities/speeds are considered relative
to _inertial_ reference frames. One cannot do FTL this
way. Non-inertial reference frames must be used; to cheat.
>
> The lighthouse effect can be used to do exactly what
> SR predicts it to do. And you can't use it to do
> FTL computation because it's spraying different parts
> of the computation over events need to communicate themselves
> to complete the computation.
>
> John Anderson
>
You haven't defined information yet.
Consider how QM uses virtual wavefunctions and
how I/O causes their unusual properties to collapse.
Wavefunctions are a 'cheat' just like FTL computation.
They do interesting things as long as you don't
look at or measure or communicate between them (decohere).
In the olympics, does the high-jumper jump the height
if his or her center of mass never goes over the bar ?
A virtual cheat has its uses.
In an earlier thread I gave you a link to a specific use
for the lighthouse effect. Do you remember ?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Wed, 11 Oct 2000 13:36:47 +0200
Bill Unruh wrote:
>
> In <[EMAIL PROTECTED]> glenn <[EMAIL PROTECTED]> writes:
>
> >Irrelevant question, but is there any way of converting a pdf file to
> >ps?
>
> pdf2ps
> Both are Unix programs available with many Linux distributions. They
> were apparently written by Adobe or adobe people,
That is unlikely. Those programs are shell scripts that come with
the ghostscript distribution. And no, they don't seem to reuse any
distiller code too because the results are sometimes different from
the acrobat distiller.
> so may well be
> available on other platforms.
They are, but because gs is.
> Alternatively, Acroread will produce a ps
> file from a pdf file ( just "print to file" as a postscript printer).
> xpdf will also do it.
Greetings!
Volker
--
The early bird gets the worm. If you want something else for
breakfast, get up later.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: EKE, RSA, and Compression?
Date: Wed, 11 Oct 2000 11:28:05 GMT
There have been some discussions in this newsgroup on how certain
forms of plaintext compression leave redundant information at the
beginning (a header byte, identifying which of several basic
compression algorithms, appropriate to different types of file) or at
the end (a 100...0 trailer to make a message come out even) of a file,
thereby making it possible, despite the fact that compression removes
the 'obvious' characteristics of plaintext, to perform a brute-force
search.
Since no known compression algorithm is anywhere near "perfect",
however, even once these easy characteristics are removed, a search
program could still test possible plaintexts by beginning
decompression, and seeing if the result makes sense.
Since the usual encryption algorithms use quite long keys, and are
resistant to known-plaintext attacks, concern about this sort of thing
is generally considered pointless.
But readers of this NG should be familiar with one case where concerns
of the same general kind as those raised by David A. Scott with
respect to general encryption _are_ generally recognized as valid.
I refer, of course, to EKE, or encrypted key exchange.
A short password is used to encipher a key, which, while it is the
"public" key for a public-key algorithm, is in fact kept secret.
Because the password _is_ short enough to be brute-force searched, a
condition on the valid use of EKE is that whatever the password is
used to encipher must have the appearance of a bunch of random bits.
And, of course, once a possible public key is found, one is still
faced with the task of cracking a public-key cipher, but now one has
to go through it for every possible password.
So in this case, ensuring that the plaintext has no distinguishing
features, but is just composed of essentially random bits, is
essential to the operation of the cipher.
Thus, while it would be very nice to force an attacker to factor an
RSA modulus for every possible password, even if one tried to turn
such a number into something more uniform (one way would be to combine
the number divided by 210 with its remainder, limited to only the
remainders possible for numbers not divisible by 2, 3, 5, or 7) there
really is no way known (aside, of course, from transmitting both
factors in the form of "the Nth prime number", which vitiates another
aspect of EKE) to compress an RSA modulus so that testing it for
plausibility is as hard as cracking RSA.
Thus, EKE is most useful when used with Diffie-Hellman; it can be used
on the public exponent in RSA, but that doesn't yield the full benefit
of privacy amplification.
Here, however, is something that is applicable both to EKE and general
compressed message encryption.
If two parties _do_ have the means of exchanging a large secret key,
but simply want to avoid using a relatively slow encryption algorithm
for the entire message, then they could encipher the "weak spots" of a
message using a more elaborate scheme.
Thus, the beginning and end of a compressed message, or of an RSA
modulus, could be enciphered using a relatively slow and elaborate
method, and the middle bits, which are essentially random, could be
enciphered by a more 'ordinary' method.
There is a qualitative difference between these two cases, of course;
the middle bits of an RSA modulus really do form a string of random
bits, while the middle bits of a compressed message don't - as noted
above, no known compression method really gets particularly close to
perfection.
And, of course, this isn't all that new an idea; splitting a message
in half and switching the halves, so that the beginning and ending of
the message are in the middle is a very old method of protecting
messages against the vulnerability caused by standardized headers and
signatures.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Olivier Breard <[EMAIL PROTECTED]>
Subject: Re: How Colossus helped crack Hitler's codes
Date: Wed, 11 Oct 2000 13:58:44 +0200
Thanks Frode, and thanks for your Web page full of crypto links !
Your site has always been a reference for me. There i found the details of
enigma behaviour.
i want to say that I loved the reading of Robert Harris ' 'Enigma' book.
Maybe not technical enough for cryptographers, but i think it is good in
showing us the whole atmosphere of Bletchley Park.
Arrrgggg, what a pity i can't easily visit BP !
i once read some papers from 'nautical brass' or something like that and
really enjoyed the story of U-Boats & ULTRA. Plenty of docs are available on
the Web. Thanks internet, thanks Web, (so thanks CERN ;=) ).
I want to explain to all of you, that my first, yet decisive, meeting with
crypto was in London National Museum of Science and Industry, where i stood
for about 1 hour in front of a curious typewriter, with some lamps on it...
That's how i discovered the Enigma. THE object, THE machine.
- A marvellous machine, even if it helped killing lots of people. The tool
for a world-wide invasion, but a great crypto idea... -
Since then, i just can't wait visiting England again, with only one
objective: NMSI and BP afterwards ! A crypto trip, that is.
Even if i am not easy at all with maths, i love the reading of crypto
papers, and stories gathered on the Net !
I don't know what you all think about 'paper&pencil' crypto, but it was much
more fun than pure math encryption, don't you think ? I take more pleasure
in reading about Vigenere, Playfair, Scytale, Enigma (-Even if there is lots
of math in it-) and others, than reading about public and private keys....
Just my humble opinion. You will reply that you can't achieve max security
with paper-cyphers, true but....
Thank you all, for giving life to this crypto newsgroup !!
A french crypto newbie. An Enigma fanatic /* Don't understand "fanatic" in
its primary meaning, though */,
Olivier.
------------------------------
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Reply-To: [EMAIL PROTECTED] (Kent Paul Dolan)
From: [EMAIL PROTECTED] (Kent Paul Dolan)
Date: Wed, 11 Oct 2000 12:07:47 GMT
David C. Ullrich <[EMAIL PROTECTED]> wrote:
> Rajarshi Ray <[EMAIL PROTECTED]> wrote:
>> "David C. Ullrich" wrote:
>> > On Mon, 09 Oct 2000 04:47:22 GMT, Rajarshi Ray
><[EMAIL PROTECTED]>
>> > wrote:
>>> [...]
>>> >Is it not possible to implement the presented algorithm and try it
>out
>>> >on examples to see the growth rate, just as a preliminary check?
>>> No. Suppose that a(n) is a sequence of integers and
>>> a(n) = 2^(2^(^n)) for all n less than 10^(10^10). Does a(n)
>>> have polynomial growth?
>> Well, I suppose it could be polynomially growing after 10^(10^10). Do
>> you mean to say that empirical testing wouldn't reveal its polynomial
>> behavior for n->oo, which is what we really mean by polynomial growth?
> Yes. (And it's not just a theoretical thing: It happens all the
>time that an algorithm that takes time O(n^2) is actually much
>faster than one that takes time O(n).)
There is a rather strong warning and object lesson against depending on
the behavior in the first few ten to the ten to the ten test cases ;-)
as a representation of asymptotic behavior found on the wonderfully
(though possibly or not sarcastically) named "Law of Small Numbers"
glossary page for the primes group; see:
http://www.utm.edu/research/primes/glossary/LawOfSmall.html
I keep this one around to toss at people to lazy to do the math and
convinced that computer programs or math algorithms or whatever can be
proved by exhaustive testing, a modern variant of black magic.
Cheers!
xanthian.
------------------------------
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Reply-To: [EMAIL PROTECTED] (Kent Paul Dolan)
From: [EMAIL PROTECTED] (Kent Paul Dolan)
Date: Wed, 11 Oct 2000 12:12:45 GMT
David Eppstein <[EMAIL PROTECTED]> wrote:
><[EMAIL PROTECTED]> wrote:
>> At the risk of playing clueless straight man here, let me point
>> out that if validating a proof is P, then finding a proof is
>> ipso facto NP, since you can guess the proof and then check
>> if your guess is correct in P time.
>There's an important technicality you're forgetting: the size of the proof
>might not be polynomial in the size of the original problem.
Okay, so you cheated and peeked at the proof of Fermet's "last" theorem.
;-)
Cheers!
xanthian.
===== random archival quality quote =====
"Thank God men cannot as yet fly and lay waste the sky as well as the
earth!" -- Henry David Thoreau (1817-1862)
-- quoted by Steve Koterski at eBay
--
Kent Paul Dolan.
<[EMAIL PROTECTED]> <[EMAIL PROTECTED]> <[EMAIL PROTECTED]>
------------------------------
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Reply-To: [EMAIL PROTECTED] (Kent Paul Dolan)
From: [EMAIL PROTECTED] (Kent Paul Dolan)
Date: Wed, 11 Oct 2000 12:23:44 GMT
Mark William Hopkins <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] (Jeremy Spinrad) writes:
>>I know that if I proved P = NP, I would be happy to do an enormous amount of
>>work to have it accepted; my reward would be very large for the work put in.
>I don't think you fully realise the seriousness of the understatement you
>just made. There is a $1,000,000 bounty out there for the first correct
>resolution to this issue.
Yeah, but on the Everett Dirkson metric, that lacks a trio or more of
zeros at the end to constitute "real money", and is at the 0.1 *
xanthian - total -sellout - to - the - suits - level in any case. Nice
for pocket change, though.
Cheers!
xanthian.
------------------------------
From: "bubba" <[EMAIL PROTECTED]>
Crossposted-To: comp.arch.fpga,comp.lang.vhdl
Subject: Re: Modular Exponentiation
Date: Wed, 11 Oct 2000 07:44:46 -0500
Here is one to look at:
ftp://ftp.rsasecurity.com/pub/pdfs/tr201.pdf
"Steve Su" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I'm trying to implement modular exponentiation on an FPGA (specifically
> targetting a Xilinx Virtex V300) as part of a hardware implementation of
> a public-key encryption system. I'm trying to find an area efficient
> implementation of modular exponentiation. I've come across several
> algorithms which should help make my design more efficient, including the
> square-and-multiply and Montgomery's multiplication algorithms.
>
> While both methods seem fairly straight-forward, there are some parts
> which aren't too clear to me. This may be because I lack a background in
> modular arithmetic.
>
> The thing that I need help with right now is the algorithm for Montgomery
> reduction of an integer. The algorithm I've found is:
>
> Given a prime M, and a radix R > M, m = bit-length of M
> MRED(T), T < RM, R=2^m, gcd(M,R) = 1
> U = TM' mod R
> t = (T + UM) / R
> IF t >= M RETURN t - M
> ELSE RETURN t
>
> t = TR' mod M
>
> One of the conditions for the reduction is that:
> RR' - MM' = 1
>
> What I want to know is, where does M' and R' come from? (i.e. How do I
> calculate M' and R'?) I've also noticed that some papers use R' while
> others use the notation R^-1. Is there a difference?
>
> I've tried looking at the Montgomery's paper, "Modular Multiplication
> without Trial Division" as well as other papers on Montgomery
> multiplication, but I haven't found anything particularly helpful.
>
> Also, is the use of Montgomery multiplication and the square and multiply
> algorithm the best (resource-wise) approach to use when attempting to
> implement modular exponentiation in hardware?
>
> If anyone could provide with some help on this, I would really appreciate
> it. Seeing someone's VHDL implementation would be nice, but I really want
> a good grasp of the fundamentals rather than just to copy code. If anyone
> could recommend any good resources (books, websites, papers, etc) on this
> stuff, that would be a great help.
>
> If you could e-mail any responses to me that would be terrific. Thanks in
> advance.
>
> -Steve
> [EMAIL PROTECTED]
>
>
>
>
------------------------------
** 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
******************************
