из истории теории информации

[ded_maxim]

Наконец-то добрался до "Криптономикона" Стивенсона. Помню, ygam сетовал на многочисленные анахронизмы в книге -- типа, уже в 1941-м году идет речь о теории информации, информационных каналах и т.д., хотя первая работа Шеннона на эту тему вышла только в 1948-м году. На самом деле, все не так просто. Дело в том, что Шеннон интересовался вопросами передачи информации по каналам с помехами еще до начала войны и был подробно знаком с работой Хартли 1928-го года, где впервые появились термины вроде "rate of communication", "intersymbol interference", "capacity of a system to transmit information", как и, собственно, сама идея измерять количество информации логарифмом числа возможных сообщений. Вот что говорится в крайне познавательном обзоре S. Verdú, "Fifty Years of Shannon Theory," IEEE Trans. Information Theory, Special Commemorative Issue, vol. 44, no. 6, pp. 2057-2078, Oct. 1998 (PDF):

Probabilistic modeling of information sources has in fact a very long history as a result of its usefulness in cryptography. As early as 1380 and 1658, tables of frequencies of letters and pairs of letters, respectively, had been compiled for the purpose of decrypting secret messages. At the conclusion of his WWII work on cryptography, Shannon prepared a classified report where he included several of the notions (including entropy and the phrase “information theory”) pioneered in [his 1948 article]. However, Shannon had started his work on information theory (and, in particular, on probabilistic modeling of information sources) well before his involvement with cryptography. Having read Hartley’s paper in his undergraduate days, Shannon, as a twenty-two-year-old graduate student at MIT, came up with a ground-breaking abstraction of the communication process subject to a mean-square fidelity criterion. After writing his landmark Master’s thesis on the application of Boole’s algebra to switching circuits and his Ph.D. dissertation on population dynamics, Shannon returned to communication theory upon joining the Institute for Advanced Study at Princeton and, then, Bell Laboratories in 1941.

Так что в предположении, что Лоренс Уотерхауз, Алан Тьюринг и Рудольф фон Хакльхебер вполне могли встретиться с Шенноном в Принстоне и таким образом познакомиться с теоретико-информационными идеями уже в начале сороковых годов, в принципе сильных натяжек нет. Было бы намного интереснее, конечно, если б Стивенсон "вписал" и Шеннона в книгу качестве одного из персонажей, пусть даже второстепенного.

Comments

[ygam.livejournal.com]

Possibly. Of course no cryptanalysis-obfuscation unit existed; the Germans did not even consider the possibility that the Enigma was broken, and assumed that their submarines were sunk because of superior British radar.

[ded-maxim.livejournal.com]

Right. But as an information theorist I think that the whole idea of a cryptanalysis-obfuscation unit is rather cool. By the way, what was the name of that Peter Calcovoressi book, Top Secret Ultra? I think I will read it after I'm done with Cryptonomicon.

[ygam.livejournal.com]

Yes, Top Secret Ultra.

[ded-maxim.livejournal.com]

Sorry, I misspelled his name, it's Calvocoressi of course. Duke library has that book, so I will check it out.

[boriskogan.livejournal.com]

http://en.wikipedia.org/wiki/Ultra

"The Allies were seriously concerned with the prospect of the Axis command finding out that they had broken into the Enigma traffic. This was taken to the extreme that, for instance, though they knew from intercepts the whereabouts of U-boats lying in wait in mid-Atlantic, the U-boats often were not hunted unless a "cover story" could be arranged — a search plane might be "fortunate enough" to sight the U-boat, thus explaining the Allied attack. Ultra information was used to attack and sink many Afrika Korps supply ships bound for North Africa; but, as in the North Atlantic, every time such information was used, an "innocent" explanation had to be provided: often scout planes were sent on otherwise unnecessary missions, to ensure they were spotted by the Germans. The British were, it is said, more disciplined about such measures than the Americans, and this difference was a source of friction between them."

While I don't know if special operations were used to cover up the use of Ultra/Magic, it's quite possible. It's not too likely-most special operations in the sense that we think of them today were OSS liaison elements working with local resistance movements, Jedburghs, etc. As far as I know, anyway.

[boriskogan.livejournal.com]

http://en.wikipedia.org/wiki/Gardening_%28cryptanalysis%29

[ded-maxim.livejournal.com]

I was just about to say that this was a typical case of a chosen-plaintext attack, but the Wikipedia entry already says that. This seems like quite an obvious thing to do. What is much less likely is to attempt to manipulate statistical regularities on a large scale in order to effectively disguise what statisticians would call "large-deviation events". In other words, if the enemy were to conduct a statistical analysis of a bunch of events in order to conclude whether a given event was anomalous or not, the goal would be to make certain changes to the entire sample he would see in order to force him to accept certain events as normal. In fact, I am working right now on a project to develop statistical methodology for detecting anomalous contacts between some people in a group, and it's quite interesting to look at possible strategies for them to try and disguise the anomalous nature of their meeting.

[boriskogan.livejournal.com]

Yeah, I know it's a chosen-plaintext attack and not a counter-intelligence measure. Still, if the allies were smart enough to manipulate the Germans into revealing their crypto, why is it a stretch to say they might have been smart enough to manipulate them into not seeing that their crypto had been compromised?

If you don't mind me asking, who are you developing this methodology for? Who's the end-user?

[ded-maxim.livejournal.com]

The project is funded by DARPA, so the stated goal is effective surveillance, discovery of possible new locations of IED's given records of previously found ones, etc., but we're hoping also to have some applications to life sciences as well -- find anomalous patterns of biomarkers in the patient's blood, for instance.

[boriskogan.livejournal.com]

I'm gonna have to talk to you about another possible application of this next time I'm in NC, if you don't mind.

[ded-maxim.livejournal.com]

I'd love to. Drop me a note when you're in NC, and we'll have a few beers and talk about these things.

[ygam.livejournal.com]

Я вчера говорил об этом с этим человеком (http://www.linkedin.com/pub/oscar-zhuk/a/807/652); он не знает твоего имени.

[ded-maxim.livejournal.com]

Ну, я кагбе тоже не совсем в курсе, кто это такой.