Интересно, как много людей при упоминании «RSA Security» думают «компания, созданная и управляемая Райвистом, Шамиром и Адельманом»? Кто-то ведь поди ещё задаёт им вопросы «ребята, создатели RSA, как же так получилось, что ваша компания — эээ...?». Я вот, например, эти вопросы тоже не знал и, когда стало интересно, лазил в вики проверить, есть ли реально какая-то связь.


По ссылке про историю «RSA Security» написаны похожие вещи: компания не раз перепродавалась, криптографический бизнес сокращался, толковые инженеры и менеджеры из неё уходили, но какая-то остаточная репутация из-за того, что они очень давно на рынке, ещё была. И когда компания ослабла совсем, налетели птицы-падальщики (герб их помните?) и склевали полудохлый труп.


Что-то такое было, как вы писали, с алгебраическим криптоанализом, но, правда, вы позже писали и другое (цитату не нашёл) — что-то наподобие «прогресс в криптоанализе внутри АНБ может опережать на несколько лет то, что известно в открытом сообществе, но, как показывают примеры, даже то интересное, что недавно было обнаружено,^* по факту позже оказалось лишь ещё одной теоретической игрушкой, хотя когда-то на него возлагали надежды уровня "сейчас все шифры им переломаем"». Т.е. есть скептицизм по поводу того, что можно сильно оторваться от того, что уже известно в открытой науке.

История на многих примерах^** учит тому же: как правило, одно и то же приходит в голову не одному, а нескольким людям и почти одновременно, разница — пара лет, 5 лет, но не больше даже несмотря на то, что люди не знают друг друга и не читают работы коллег. Просто есть какой-то «общий фон совокупного понимания науки человечеством», и если прогресс превышает какой-то порог, достаточный для возникновения новых знаний, это увидит не один, а многие, кто внимательно к этому приглядывается. Уж, по крайней мере, в масштабах всего мира очень трудно найти что-то такое, что считалось бы трудным для всех, но лёгким для тех, кто «знает, как».

^*Тот же алгебраический криптоанализ, возможно, давно известный АНБ и лишь недавно ставший известным в открытом сообществе.
^**В том числе — история зарождения криптографии с открытым ключом.

Через несколько лет никто, кроме кучки специалистов которые ничего не решают, и не вспомнит об эпичном провале.

Ага, кто сейчас помнит о мегаутечке с серверов SecurID...

А о разборках RSA Security с Циммерманом и о том, что в немалой мере благодаря их стараниям он попал под следствие?

/comment75228:
Там всё ещё смешнее.

Сам бэкдор и защита от него были запатентованы ещё в 2005 году. Типа, хотите использовать депонирование секрета для дешифровки трафика — вот вам способ навязать константы. Хотите избежать использование констант — вот как сделать чистый вариант без бэкдора.

Подробнее об устройстве бэкдора.

Во вторых, НИСТ как бы умывает руки, это не его стандарт, а публикация-рекомендация, на основе стандарта ANSI и пр., куда он был внедрён ранее, а авторами алгоритма было АНБ. Причём АНБ не изобрело бэкдор, оно взяло готовый патент от гражданских криптографов и опубликовало от имени своих разработчиков. Хотя, не совсем ясно, про даты с патентом и начало продвижения этого стандарта от АНБ ещё в начале 2000-х.

RSA Security была в комитете по стандартизации ANSI и вроде как была в курсе и этого патента, и того, что в стандарт можно встроить бэкдор и после его принятия включила в свою программную библиотеку.

Наконец, ANSI и ISO, стандартизировали аналогичный алгоритм Микалли-Шнора. В нём, как в чисто ассиметричном, самом по себе нет ничего плохого, но в стандарт внесены необъяснимые константы, которые также могут содержать бэкдор, основанный на знании факторизации. Пока даже теоретически неясно как это может в точности работать, но злонамеренный выбор констант с большой вероятностью может давать такую возможность. Правда, этот стандарт нигде не применяется.

Ron Rivest, Adi Shamir and Leonard Adleman developed the RSA encryption algorithm in 1977. They founded RSA Data Security in 1982.

RSA Data Security (RSADS, ныне RSA Security, http://www.rsasecurity.com) – это американская компьютерная компания-разработчик, основанная в 1983 году авторами алгоритма RSA: Роном Райвестом, Ади Шамиром и Леном Адлманом.

К несчастью, последний бит каждого байта в ключе является битом четности, так что эффективная длина ключа составляет только 56 бит.

С помощью дифференциального криптоанализа и атаки на основе подобранного открытого текста можно найти ключ DES, используя 2⁴⁷ открытых текстов.

Линейный криптоанализ еще более эффективен против DES. Это схожая техника, однако другая, открытая Мицуру Мациу в 1993 году, с помощью которой можно провести против DES атаку на основе 2⁴³ известных открытых текстов.

Но с 3DES там посложнее будет (см. ту же ссылку).


Спасибо. Интересный разбор. Тут ещё в тему из википедии:

Berry Schoenmakers and Andrey Sidorenko publishes a Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, showing that emperically the output from Dual_EC_DRBG can be distinguised from random bits, concluding that Dual_EC_DRBG is insecure as a CSPRNG. (note that this is a separate problem from the backdoor)

NIST SP 800-90A is published, includes Dual_EC_DRBG with the defects pointed out by Kristian Gjøsteen and Berry Schoenmakers and Andrey Sidorenko not having been fixed.

Не буду показывать пальцем Боюсь спросить, родственники читателей pgpru.com случаем криптографией не подрабатывают? :)


Его описания даже в вики нет (но есть упоминания), хотя в интернете есть много страниц по теме.

Это вы про открытие Коблица-Миллера? :)

Нет, хотя это тоже интересное наблюдение. ☺ Я про ассоциативный ряд «Andrey Sidorenko (Dual_EC_DRBG) ↔ sentaus ↔ https://vk.com/id2610335».

Тут кто-то недавно активно ругался на соцсети... Хотя если кому-то «ничто человеческое не чуждо», то чего бояться удивляться?

He is also the inventor of Miller's Algorithm which is of fundamental use in pairing-based cryptography. © V. Miller

Такой молодой, а уже эпоним!

Бывает и такое, но чаще СВЧ излучение используют для борьбы с муз.центрами соседей. Должно быть несколько сложней чем просто открытая дверца микроволновки, но так же беспощадно. Впрочем, никаких инопланетян.

Так значит права была Наталья Половко, не всегда это чека и не всегда пси, но облучают!

In general, Complexity Theory is related to cryptography, where the letter is broadly defined as the study of systems that are easy to use but hard to abuse. Typically, such systems involve secrets, randomness, and interaction as well as a complexity gap between the ease of proper usage and the infeasibility of causing the system to deviate from its prescribed behavior. Thus, much of cryptography is based on complexity theoretic assumptions and its results are typically transofrmations of relatively simple computational primitives (e.g., one-way functions) into more complex cryptographic applications (e.g., secure encryption schemes).

In view of the central role of randomness in complexity theory (as evident, say, in the study of pseudorandomness, probabilistic proof systems, and cryptography), one may wonder as to whether the randomness needed for the various applications can be obtained in real-life. One specific question, which received a lot of attention, is the possibility of ``purifying'' randomness (or ``extracting good randomness from bad sources''). That is, can we use ``defected'' sources of randomness in order to implement almost perfect sources of randomness. The answer depends, of course, on the model of such defected sources. This study turned out to be related to complexity theory, where the most tight connection is between some type of randomness extractors and some type of pseudorandom generators.

Indeed, modern cryptography is strongly coupled with Complexity Theory (in contrast to "classical" cryptography, which is strongly related to information theory).

© Oded Goldreich, «Computational complexity, а conceptual perspective». Cambridge University Press, 2008. Введение и часть цитат доступы здесь. Замечательные эпиграфы из той же книги:

A good disguise should not reveal the person's height. © Shafi Goldwasser and Silvio Micali, 1982.

A good disguise should not allow a mother to distinguish her own children. © Shafi Goldwasser and Silvio Micali, 1982.

A world of a Gentleman is better than a proof, but since you are not a Gentleman — please provide a proof © Leonid A. Levin (1986).

Ещё там на глаза попались интересные теоремы (наверное, для специалистов они очевидны) о глубоких связях одних вещей с другими. Кажется (боюсь переврать), (a) существование односторонних (one-way) функций, (b) существование подписей, устойчивых к атакам с подобранным текстом, и (c) существование стойкой аутентификации(?) — эквивалентные друг другу утверждения.

Превосходная книжка, рекомендую. Годрайх как всегда на высоте. Очень интересно, глубоко, концептуально и доступно описано. Видно, что это «труд жизни» на сотни страниц, где выстрадано каждое слово. Тот случай, когда пишут так, чтобы потом можно было взять любую цитату из книги и сразу отлить её в граните.

---

Помимо Годрайха я посмотрел, что ещё сейчас хранят на своих полках большие люди, которые слишком много знают¹. Обнаружилось:

1. Китаев, Шень, Вялый. «Классические и квантовые вычисления». МЦНМО-ЧеРо, 1999.
2. Yves Vandriessche. «A foundation for quantum programming and its highly-parallel virtual execution». PhD thesis, VUB, 2012.
3. Robert Spalek. «Quantum algorithms, Lower Bounds, and Time-Space Tradeoffs». PhD thesis, Universiteit van Amsterdam, 2006.
4. Noson S. Yanofsky, Mirco A. Mannucci. «Quantum computing for computer scientists». Cambridge University Press, 2008.²
5. Philipp Kaye, Raymond Laflamme, Michele Mosca. «An introduction to Quantum Computing». Oxford University Press, 2010.
6. N. David Mermin. «Quantum computer science, an introduction». Cambridge University Press. 2007.
7. Willi-Hans Steeb, Yorick Hardy. «Problems and solutions in quantum computing and quantum information». World Scientific, 2006.
8. Sanjeev Arora, Boaz Barak. «Computational complexity, a modern approach». Cambridge University Press, 2009.

Сразу оговариваюсь, что я не проверял наличие этих книг хотя бы каком-то виде в сети. Помимо книги Голдрайха стоит отметить восьмую ссылку. Пожалуй, это самая современная книжка по теме. Её черновые версии доступны. Обратите внимание на подбор тем и топиков: они существенно отличаются от тех, что описаны в стандартных книжках. В частности, некоторые главы по ссылке:
Напоминаю, что это книга — не какая-нибудь «Cryptography», а «Computational complexity, a modern approach». Ну, чтоб прочувствовать.

Помимо вышупомянутых были обнаружены следующие две чисто классических (не содержащих информацию про квантовые вычисления) книжки:

1. Christos H. Papadimitriou. «Computational complexity». Addison-Wesley, 1994.
2. Michael Sipser. «Introduction to the theory of Computation». Cengage Learning, 2013.

Последняя содержит какие-то параграфы по (классической) криптографии.

P.S. Это так, в качестве грубого ориентира на предмет того, что стоило бы в наше время читать.


Термины time/space complexity из теории сложности соответствуют расходам на брутфорс по памяти и по количеству операций в современной криптографии?

---

¹Тут ранее кто-то уже интересовался ссылками на литературу.
²Цитата из книжки:

Computer science is no more about computers than astronomy is about telescopes © E.W. Dijkstra.

³Эпиграф к главе:

Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin. © John von Neumann, quoted by Knuth, 1981.