(fwd) Russians Break RSA?

[tcmay@netcom.com (Timothy C. May)]

Friends, 

I just grabbed this of the ClariNet news feed on Netcom...I'm not
supposed to forward anything from this service (so don't tell Brad
Templeton!), but this appeared to be too important not to pass on as
quickly as possible.

Apparently those rumors that the Russians, always topnotch
mathematicians, had developed public key crypto in the 1950s or early
60s are true--my hero Kolmogorov developed this when he was technical
director at Kryptogorodok, the secret city of Soviet cryptographers
hidden in the Urals (and first visited by an outsider, Stephen
Wolfram, only a couple of years ago).

Here's the report on a news conference announcing the cracking of
their Kolmogorov system, which is equivalent to our own RSA. I haven't
had a chance to talk to John Markoff, who was at the press conference,
to get his comments.

--Tim

> Xref: netcom.com clari.world.europe.eastern:2783
> clari.news.hot.ussr:3792
> clari.
> news.trouble:3258 clari.science.crypto
> Path: netcom.com!bass!clarinews
> Approved: doug@clarinet.com
> From: clarinews@clarinet.com (AP)
> Newsgroups:
> clari.world.europe.eastern,clari.news.hot.ussr,clari.news.trouble,clari.sc
> ience.crypto  
> Distribution: clari.apo
> Subject: Russian Mathematicians Announce Breakthrough
> Keywords: Europe Cryptography RSA
> Copyright: 1994 by The Associated Press, R
> Message-ID: <russia-cryptoUR7f0_4ME@clarinet.com>
> Date: Fri, 1 Apr 94 10:40:19 PST
> Expires: Mon, 18 Apr 94 12:40:19 PDT
> ACategory: international
> Slugword: Russia-Crypto
> Priority: regular
> ANPA: Wc: 116/0; Id: V0255; Src: ap; Sel: -----; Adate: 03-14-N/A
> Codes: APO-1103
>                                                                          
>      
>         MOSCOW (AP) -- At a press conference held minutes ago in a
> crowded hall, Russian mathematicians announced that a breakthrough had
> been made nearly a decade ago in the arcane branch of mathematics
> known as "cryptography," the science of making messages that are
> unreadable to others.
>         Leonid Vladwylski, Director of the prestigious Moscow Academy
> of Sciences, called the press conference yesterday, after rumors began
> circulating that noted Russian-American reporter John Markoff was in
> Russia to interview academicians at the previously secret city of
> Soviet cryptographers, Kryptogorodok. The existence of Kryptogorodok,
> sister city to Akademogorodok, Magnetogorsk, and to the rocket cities
> of Kazhakstan, had been shrouded in secrecy since its establishment in
> 1954 by Chief of Secret Police L. Beria. Its first scientific
> director, A.  Kolmogorov, developed in 1960 what is called in the West
> "public key cryptography." The existence of Kryptogorodok was unknown
> to the West until 1991, when Stephen Wolfram disclosed its existence.
>         American cryptographers initially scoffed at the rumors that
> the Russians had developed public-key cryptography as early as 1960,
> some 15 years prior to the first American discovery. After interviews
> last year at Kryptogorodok, noted American cryptographers Professor
> D. Denning and D. Bowdark admitted that it did seem to be
> confirmed. Professor Denning was quoted at the time saying that she
> did not think this meant the Russians could actually break the
> Kolmogorov system, known in the West as RSA, because she had spent
> more than a full weekend trying to do this and had not
> succeeded. "Believe me, RSA is still unbreakable," she said in her
> evaluation report.
>         Russia's top mathematicians set out to break Kolmogorov's new
> coding system. This required them to determine that "P = NP" (see
> accompanying article). Details are to be published next month in the
> journal "Doklady.Krypto," but a few details are emerging.
>         The Kolmogorov system is broken by computing the prime numbers
> which form what is called the modulus. This is done by randomly
> guessing the constituent primes and then detonating all of the
> stockpiled nuclear weapons in the former Soviet Union for each "wrong
> guess." In the Many Worlds Interpretation of quantum mechanics,
> invented in 1949 by Lev Landau (and later, independently by Everett
> and Wheeler in the U.S.), all possible outcomes of a quantum
> experiment are realized.
>          As Academician Leonid Vladwylski explained, "In all the
> universes in which we guessed the wrong factors, we were destroyed
> completely. But since we are obviously here, talking to you at this
> press conference, in this universe we have an unbroken record of
> successfully factoring even the largest of imaginable numbers. Since
> we are so optimistic about this method, we say the computation runs in
> "Nondeterministic Pollyanna Time." Allow me to demonstrate..."
>          
> [Press Conference will be continued if the experiment is a success.]
> 
> MOSCOW (AP), ITAR-Tass, 1 April 1994
>  
>                                        
> 


-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."