About

RSA Broken By The Russians? (UnReal)

Kolmogorov Cryptography System Possibly Cracked

    Apparently those rumors that the Russians, always top notch 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. 

       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

    Appendix

    First, it was Stephen Wolfram's actual suggestion, a couple of years ago after the USSR imploded, that we try to recruit mathematicians and programmers from what he surmised must exist: a secret city of Soviet cryptographers. It probably exists. We did it at Los Alamos, they did it with their rocket scientists and others (Akademogorodok exists), so why not put their version of NSA a bit off the beaten track? Note that our own NSA is within a stone's throw of the Baltimore-Washington Parkway. I wouldn't be surprised to learn that their experts were ensconced somewhere in the Urals.

    I tried to acknowledge Steve with my comments. By the way, so far as I know, no word has come out on whether he was right in this speculation. (Maybe some of the Russians he does in fact have working at Wolfram are these folks? Naw...)

    Second, Kolmogorov did basic work on information theory, probability, and statistics. One has to assume he had ties to the Soviet cryptography effort (about which little has been written about, so far). If anyone in Russia could have seen public key methods coming, he is a candidate. No evidence that he or any other Russian did, though.

    Third, my references to Denning and Sternlight were perhaps not riotously funny (though I didn't aim for a riotously funny tone). Especially in light of David Sternlight's excellent follow-up here... never let it be said that David lacks a sense of humor. The Denning reference was to her own comments about spending a weekend or so trying (and failing, not surprisingly) to crack the Skipjack algorithm. (Real ciphers often take years to break, as with the knapsack algorithm, recent crunching of DES, etc.).

    Fourth, the "Many Worlds" interpretation of quantum mechanics does exist, and leads to approaches such as I described. It's also a hypothetical way to ensure one's wealth: simply bet everything you own at 1000-to-1 odds and then commit suicide in all universes in which you lose. Not very convincing, I agree. Hans Moravec writes about this in his "Mind Children," 1987.

    Finally, I used the headers and format of a real article in the ClariNet system, then made modifications. Given that the Supreme Court has recently ruled in favor of "fair use" for satire, I hope my version of "2 Live Crew meets RSA" does not get my sued. (I could just kill myself in all realities in which Brad sues me.)

 
  Support This Site  

Cheap Blank
Minidiscs
in the UK
Digital-e-uk.com

Hosted by
Openweb Analysts Ltd
in the UK
OWAL.co.uk

Inspired By