Сам я об этом когда-то читал, и у меня просто открылись глаза на вещи, которые вроде бы всегда были понятны, но проходили мимо внимания. Возможно, у вас тоже откроются глаза.
Если мы хотим передать кому-то сообщение, чтобы никто посторонний не мог его прочитать, нужно это сообщение как-то зашифровать. Самый наивный способ – это заменить каждую букву какой-то другой буквой.
Конечно, в реальности используются гораздо более сложные алгоритмы шифрования, такие как SHA256. Не буду вдаваться в подробности, но у всех алгоритмов есть одно общее место – это пароль, или ключ. Имея ключ, мы можем расшифровать сообщение.
Ключ в случае SHA256 – это число длиной 256 бит. Оно, например, может выглядеть так:
40f7855ce9d2777d34a6e50a9a4a07158e5835a0680346960f2f787d35b41f0d
Здесь использована 16-ричная запись числа, и каждый символ – это 4 бита.
Очевидно, чем сложнее и длиннее пароль – тем сложнее его взломать. Как происходит собственно взлом?
Cамый наивный способ, он же "метод грубой силы": нужно просто перебрать все возможные пароли (ключи) по очереди и какой-то из них должен подойти.
На перебор, конечно, потребуется какое-то время. Если ключом является 256-битное число, значит, может потребоваться перебрать все возможные комбинации бит внутри него. Много ли это?
Есть такая притча. Иранский математик изобрёл игру в шахматы и показал её шаху. Шах был очень впечатлён и сказал математику – проси чего хочешь. Математик попросил заплатить ему за каждую клетку шахматной доски зёрнами пшеницы: за первую клетку дать одно зерно, за вторую клетку два, за третью четыре и так далее, удваивая количество зёрен за каждую клетку.
Шах засмеялся и сказал – ты чё тупишь, ты же мог попросить мешок золота! Но математик не захотел изменить свой выбор. Тогда шах приказал принести мешок пшеницы, и слуги начали отсчитывать зёрна...
А потом математику отрубили голову, чтобы не умничал.
Короче говоря, количество зёрен за всю шахматную доску достигло бы числа 2 в степени 64. Это порядка 18 миллиардов миллиардов.
А количество комбинаций из 256 бит – 2 в степени 256. Это настолько большое число, что даже масштабов Вселенной тут недостаточно.
Хорошо, понятно. То есть 256-битный пароль придётся подбирать очень долго.
Но тут-то и начинается самое интересное. 128 бит – это тоже весьма много. А 512 – ещё больше. Как создатели алгоритма решили, что 256 в самый раз? Ведь нужно это как-то обосновать. Если взять слишком мало бит, ключ будет не стойкий. А если слишком много – потребуется избыточная вычислительная мощность для работы с ключом.
Допустим, мы можем взять самый мощный компьютер и замерить его быстродействие. И создать ключ такой длины, чтобы на перебор требовалось, допустим, 1000 лет. Но мы не можем предсказать, какие компьютеры появятся, например, через 10 лет. Вдруг случится какой-то научный прорыв (или прилетят инопланетяне), и сделают компьютер, который работает в миллиард раз быстрей? Тогда все наши шифры станут уязвимы.
И посмотрите, как красиво это было решено. Хотя идея и лежит на поверхности, я до сих пор от неё в восторге.
Итак, нас интересует:
1. Сколько операций нужно, чтобы сгенерировать 1 пароль и проверить его?
Очевидно, чтобы сгенерировать пароль, да ещё и проверить его, нужно выполнить как минимум несколько операций, даже возможно сотни их (циклы, вычисления, запись-чтение памяти). Можно что-то оптимизировать, но чтобы не беспокоиться об этом, мы просто считаем, что генерация может быть предельно короткой. То есть состоять из ровно одной, самой простой операции. А самая простая операция – это изменение одного бита.
Давайте убедимся: меньше чем одна операция – это ноль операций, то есть ничего вообще не будет происходить. Меньше чем изменение одного бита – это ноль изменений, то есть опять-таки ничего не будет происходить. Мы получили гарантированный предел скорости генерации пароля.
2. За какое время выполняется одна операция?
Даже одна простейшая операция выполняется за какое-то время. И опять-таки в зависимости от устройства компьютера и его мощности это время может быть больше или меньше. Но мы не волнуемся об этом и просто берём самое маленькое время, которое вообще теоретически возможно. Это физическая величина – планковское время, и никакой процесс не может совершиться быстрее.
Итак, мы вообразили некий компьютер, который генерирует и проверяет 1 пароль за 1 операцию, совершаемую за планковское время. И вообще не волнует, что там изобретут, быстрее всё равно уже не будет никак. Сама Вселенная охраняет от этого.
И вот исходя именно из такого теоретического компьютера и строится расчёт длины ключа. В нашем случае 256 бит. И даже если их перебирать с придуманной нами немыслимой скоростью, всё равно на перебор уйдёт какое-то страшное количество лет.
Тем самым и обосновали количество бит в ключе.
Но есть и ещё кое-что. Если про количество и скорость операций было как-то понятно, то один нюанс я совсем упускал из виду.
3. Сколько нужно энергии?
На каждую операцию, то есть на каждое изменение одного-единственного бита требуется энергия. И мы уже должны догадаться, что нужно не считать реальную энергию, которая затрачивается в компьютерах, а сразу выбрать минимальный квант энергии. То есть компьютер будет не только абсолютно быстрый, но и абсолютно экономичный.
Так вот, чтобы перебрать 256 бит, потребуется топить этот компьютер целыми галактиками. Очевидно, что такие источники энергии нам недоступны даже в мечтах – и всё это ради того, чтобы подобрать всего один ключ! И даже если в ближайшие 10 лет изобретут какие-то чудовищно быстрые компьютеры, их всё равно будет нечем питать.
А если взламывать ключ не перебором?
Нужно понимать, что все вышеописанные расчёты дают гарантию защиты только от прямого перебора. Взлом ключа может происходить и более интеллектуально. В математических методах могут найти недоработку или закономерность, которую можно использовать. Скажем, раньше ключи были длиной 128 бит, но этого перестало хватать. Перешли на 256-битные ключи, и не редкость даже 512- и 1024-битные. Увеличенная длина ключа противодействует не только перебору, но и хитрым математическим методам.
Поэтому мы сейчас можем быть уверены, что наши ключи никто и никогда не подберёт перебором. Но какой-нибудь гениальный математик может доказать какую-нибудь сложную теорему, и тогда всё может измениться. Может, отрубить ему голову? :)