Re: Size of RN vs USN (Was: Germany Still Loses BB...) [OFFTOPIC, BUT INTERESTING]

Brad Meyer napisal(a):
> On Thu, 05 Jan 2006 11:28:57 -0500, Rich Rostrom
> <rrostrom.21stcentury@xxxxxxx> wrote:
>
> >Brad Meyer <bradm110@xxxxxxxxx> wrote:
> >
> >>If it can be coded by a man made machine it can be decoded on
> >>a man made machine. Man's intellegence cannot invent a code that man's
> >>intellegence cannot break.
> >
> >That would be news to the cryptography world.
> >
> >"Public-key" encryption, which is the standard for all
> >modern cryptography, does exactly that.
>
> I does no such thing. It only makes it difficult to break, not
> impossible. You have fallen into the same trap the Germans did with
> Enigma and the IJN did with JN 25. They started out believing they had
> an "unbreakable" code that turned out to be nothing of the sort.
>
> >While it is _theoretically_ possible to break public-key
> >encryption, there are no proven algorithms for doing so
> >quickly . . .
>
> Thank you. Now, if it was a case for war to the knife, and some govt
> was going to throw a whole heap of money and expertise at the problem,
> how long do you suppose it would take to develop at least a working
> algorythm?

The problem is that for some class of problems it is _proven_ that no
algorithms exist which would solve these problems in polynomial time
(i.e.: time to solve the problem grows exponentially fast with the size
of the problem). Mathematical proofs have this nice property that no
amount of money thrown at them will make a true theorem turn into a
false theorem. And this class of problems is used in modern
cryptography.

So we're stuck with the exponential time. Can we do something about it?
Sure. We can build faster machines. In fact, we already beaten some
ciphers of these kind (like the old DES or the original RSA version).
Sometimes it takes a lot of machines working together, but modern
cryptoanalysis always assumes that the party trying to crack the code
has enourmous computational resources at its disposal (read: is as rich
as NSA). The wonderful thing about some of these ciphers is that they
are scalable: when the key lenght is so short that the enemy is capable
of breaking it in some acceptable time, you _double_ the key lenght.
The time required grows by many orders of magnitude. Back to square one
for the eavesdroppers.

Now, there is this hype about quantum computes. Yes, they _may_ work
some day and implement some new algorithms, like the Shor algorithm for
factoring a number in polynomial time. Last time I heard, they factored
15 (fifteen) with some huge machine working on trapped ions. The
problem is, there really aren't many algorithms for quantum computers
available. There are problems which do not have corresponding
polynomial-time quantum algorithms for solving them, like the elliptic
curves used in ATM cards. The quantum sword is double-sided, though. We
don't have quantum computers yet, but we have working prototypes of
quantum communication, which is going to make life pretty difficult for
the eavesdroppers. The question whether it will be useful on the
battlefied remains open.

>
> Public key encryption works because it is not cost effective to break
> them for what they contain, not because it is "crack proof".
>
> All this, of course, assumes that some govt hasn't already worked out
> the algorytms required and just has not advertised the fact.

Yes. However, it would be the first time in human history when some
government was able to hold some basic scientific discovery in secret
for some significant period. Scientist are like old ladies: they love
to chatter. Q.E.D.

.

Relevant Pages

  • Re: New 2 Cryptography
    ... Newsgroups: sci.crypt ... > cryptography and I thought I'd post here to ask a few questions. ... Also there is a question of licensing one or more algorithms, ... rounds of arithmetic operations, and you wind up with something that would ...
    (sci.crypt)
  • Re: Newbie question(s)...
    ... New algorithms may not have anything to ... While a knowledge of cryptography allows ... (although proving that the irrationality of the number is truly random ... if there were a way to deterministically produce a string of ...
    (sci.crypt)
  • Re: FlexiProvider: an open source cryptography provider for the JCA/JCE
    ... Mike Amling wrote: ... source cryptography service provider for the Java Cryptography ... It currently includes the following algorithms: ...
    (sci.crypt)
  • Re: Timings issue
    ... >> You mean to say that timings of implementations of cryptographic ... >>algorithms on different platforms are not relevant to cryptography? ... who build high speed code are also experts in how to design code that ...
    (sci.crypt)
  • Re: Quantum Computation
    ... >Also, note that complexity is a property of *problems*, not algorithms, ... Your last remark assumes that machines are being treated as black ... >which Quantum Computing is better than classical, ...
    (sci.physics.research)