Прикладная криптография что это
Русские Блоги
Резюме прикладной криптографии
Каталог статей
Резюме прикладной криптографии
1 Обзор
1.1 Три основные цели информационной безопасности
Сообщение может быть безопасно передано, то есть перехватчик не может прочитать отправленное сообщение.
Получатель сообщения должен иметь возможность убедиться, что сообщение не было изменено в процессе доставки; злоумышленник не может заменить законное сообщение фальшивым.
Это необходимо для обеспечения того, чтобы информация и информационные системы предоставляли услуги уполномоченным лицам в любое время, и во избежание злоупотреблений со стороны неуполномоченных лиц, но отказа в обслуживании уполномоченных лиц.
1.2 Безопасность данных основана на конфиденциальности ключа, а не на конфиденциальности алгоритма.
1.3 Криптография с открытым ключом делает возможной конфиденциальную связь без передачи ключа
1.4 Основные понятия криптографии
Криптология: наука об исследовании технологий безопасности информационных систем. Он состоит из двух веток:
Криптоанализ (Cryptanalysis), изучение и анализ знаний о взломе кодов или подделке.
Эти двое противостоят друг другу и продвигаются вперед, чтобы продвигать друг друга.
1.5 Классификация криптографических алгоритмов-I
По принципу зависимости конфиденциальности он делится на:
1.6 Классификация криптографических алгоритмов-II
По характеристикам ключа он делится на:
Симметричный шифр: это означает, что ключ шифрования и ключ дешифрования одинаковы или практически эквивалентны, то есть их легко вывести из одного в другой. Также называется алгоритмом секретного ключа или алгоритмом с одним ключом.
Шифр с симметричным ключом можно разделить на потоковый шифр и блочный шифр.
Асимметричный шифр: ключ шифрования и ключ дешифрования не одно и то же, и их сложно вывести из другого. Также известен как шифр с открытым ключом (шифр с открытым ключом).
2 Основы теории чисел
2.1 Coprime
Если наибольший общий делитель a и b равен 1, то a и b взаимно просты. (Примечание. (A, b) представляет собой наибольший общий делитель a, b)
a и b взаимно простые числа, a и b не обязательно являются простыми числами, например (9,4) = 1
2.2 Модульная работа
(1) Модульное дополнение
(a + b) mod m = ((a mod m) + (b mod m)) mod m
Пример: (11 + 15) mod 8 = ((11 mod 8) + (15 mod 8)) mod 8 = (3 + 7) mod 8 = 10 mod 8 = 2
(2) Модульное вычитание
(3) Модульное умножение
(a × b) mod m = ((a mod m) × (b mod m)) mod m
Пример: (7 × 9) mod 8 = ((7 mod 8) × (9 mod 8)) mod 8 = (7 × 1) mod 8 = 7 mod 8 = 7
2.3 Обратный элемент
(1) Аддитивный обратный элемент
Аддитивное обратное к x y число, удовлетворяющее x + y ≡ 0 mod m
Пример: 2 + 6 ≡ 0 mod 8, 6 и 2 являются аддитивными инверсиями по модулю 8 друг друга.
(2) Мультипликативный обратный элемент
Пример: 2 × 4 ≡ 1 mod 7, 2 и 4 являются взаимно по модулю 7 мультипликативным обратным элементом
a= bq + r, 0 C = M e ( m o d n ) C=M^e (mod n) C = M e ( m o d n )
Дешифрирование: M = C d ( m o d n ) M=C^d (mod n) M = C d ( m o d n )
7.7 Пример создания пары ключей RSA
7.8 Недостатки RSA
Из-за ограничений технологии генерации простых чисел создавать ключи проблематично.
Длина пакета слишком велика. Для обеспечения безопасности n должно быть не менее 600 битов, что делает стоимость вычислений очень высокой, особенно медленной скоростью; а с развитием технологии декомпозиции большого числа эта длина все еще увеличивается, что не способствует формату данных. Стандартизация
7.9 Атака разложения чисел, когда p и q близки
7.10 Выбор атаки с использованием открытого текста
8 Криптосистема Эль-Гамаля
Предложенная Эль-Гамалом [1984,1985], это двухключевая криптосистема, основанная на задаче дискретного логарифмирования, которая может использоваться как для шифрования, так и для подписи.
8.1 Этапы создания пары ключей Эль-Гамаля
8.2 Шаги шифрования и дешифрования Эль-Гамаля
8.3 Пример генерации пары ключей Эль-Гамаля
8.4 Пример шифрования и дешифрования Эль-Гамаля
9 обмен ключами Диффи-Хеллмана
Схема обмена ключами: позволяет двум пользователям безопасно установить секретное сообщение для последующего обмена данными.
Безопасность алгоритма зависит от: сложности вычисления дискретного логарифма на конечном поле
9.1 Этапы реализации схемы секретного ключа DH
9.2 Пример реализации схемы обмена секретным ключом DH
9.3 Сторонний метод атаки схемы секретного ключа DH
Почему сторонний метод атаки может быть успешным?
Вопрос в следующем: A и B общаются по незащищенному каналу, поэтому как обе стороны могут узнать, кто является другой стороной?
Можете ли вы разработать схему обмена ключами DH, которая может подтвердить идентичность взаимодействующих сторон? 
10 Цифровая подпись
10.1 Схема подписи RSA
10.2 Схема подписи ELG
11 Эксперимент 02
(1) Используйте программное обеспечение PGP, чтобы сгенерировать новую пару открытых / закрытых ключей и зарегистрировать их на сервере PGP.
Размышление: почему не сервер генерирует пару открытого / закрытого ключей единообразно, а клиент генерирует пару ключей? Где после регистрации хранится открытый / закрытый ключ? Нужны ли для закрытого ключа меры защиты?
1. Пара открытый ключ / закрытый ключ не контролируется никакими правительствами или организациями по стандартизации, что делает PGP широко известным и может удовлетворить потребности коммерциализации.
2. После регистрации на сервере открытый ключ сохраняется на сервере, а закрытый ключ хранится у пользователя.
3. Используйте пароль, чтобы зашифровать закрытый ключ для хранения, который легко запомнить и который также может защитить закрытый ключ.
(2) Пригласите других пользователей подписать открытые ключи друг друга.
Мышление: в чем значение этого шага? На что следует обратить внимание, прежде чем подписывать чужой открытый ключ?
1. Открытый ключ взаимной подписи используется для создания системы доверия, доверяющей открытому ключу другой стороны как законному открытому ключу указанного объекта.
2. Необходимо подтвердить, что подписанный открытый ключ является законным открытым ключом указанного лица. Возможные методы: физическое получение открытого ключа другой стороны, что является наиболее надежным методом, но имеет определенные ограничения; проверка открытого ключа по телефону; от обеих сторон Доверенная третья сторона получает открытый ключ другой стороны.
(3) Используйте формат кодирования ASCII для отправки собственного открытого ключа другим пользователям.
Размышление: какое значение это имеет для всей системы доверия PGP?
Отправляйте открытые ключи доверенным друзьям и получайте открытые ключи от доверенных друзей. Как правило, эти открытые ключи подписаны. Таким образом, пользователи могут решить, доверять ли окружающим контактам, и установить личностно-ориентированный подход. Модель доверия.
(4) Отправить зашифрованное и подписанное письмо
Размышляя: чей и какой ключ использовался для шифрования, чей и какой ключ использовался для подписи? Должно ли электронное письмо быть зашифровано и подписано одновременно? Длина электронного письма варьируется, но длина данных цифровой подписи кажется фиксированной. Почему?
1. Открытый ключ получателя используется для шифрования.
2. При подписании использовался закрытый ключ отправителя.
3. Электронное письмо не обязательно должно быть зашифровано и подписано одновременно.
4. Фактически, sign & verify использует хеш-функцию и технологию асимметричного шифрования, чтобы подтвердить, что источник файла и его содержимое не были изменены, а длина хеш-значения определяется различными хеш-функциями, общими хеш-значениями. В функции есть MD2, MD5, SHA-1, SHA-128, SHA-256, SHA-512.
(5) После получения зашифрованного и подписанного электронного письма от других, расшифруйте и проверьте правильность подписи.
Подумал: чей и какой ключ использовался для расшифровки; чей и какой ключ использовался для проверки подписи?
1. Для расшифровки используется закрытый ключ получателя.
2. При проверке подписи использовался открытый ключ отправителя.
Прикладная криптография. Как мы восстановили биткоины на 300 тысяч долларов
Поделюсь с вами одной историей. Около двадцати лет назад я получил степень по физике, но занимался реверс-инжинирингом и криптоанализом. Наша компания AccessData работала в конце 90-х и начале 2000-х. Тогда правительство США постепенно снимало ограничения на экспорт криптографии, однако парольная защита в большинстве программ по-прежнему оставалась довольно бесполезной. Мы брали офисные программы, я проводил реверс-инжиниринг и выяснял алгоритм шифрования, а потом ломал криптозащиту.
Это был нескончаемый поток интересных, но не особенно сложных математических головоломок. За всё время я написал около сорока взломщиков паролей. Мы продавали их домашним пользователям, системным администраторам, местным и федеральным правоохранительным органам. Мне пришлось несколько раз съездить в федеральный центр подготовки сотрудников правоохранительных органов в Глинко, чтобы объяснить ребятам из Секретной службы, ФБР и АТФ основы криптографии и как использовать наши продукты.
Особенно ярко мне запомнились два проекта. Первым был Microsoft Word 97. До его появления файлы шифровались с помощью XOR байтов открытого текста и 16-байтовой строки, которая выводилась из пароля. Самыми распространёнными байтами в файле Word обычно были 0x00, 0xFF или 0x20 (пробел), поэтому мы просто выбирали самый распространённый символ в каждом столбце и проверяли 3 16 вариантов. Восстановление ключа обычно происходило мгновенно, но чтобы людям не казалось, что они зря потратили деньги, мы вставили небольшую анимацию, похожую на голливудскую хакерскую сцену с множеством случайных символов, из которых постепенно проявляется правильный пароль.
Microsoft Word 97 всё изменил. Возможно, в MSDN и раскрывали формат шифрования, но наша маленькая фирма не могла позволить себе подписку. И не факт, что нам бы разрешили написать программу для взлома после получения информации. Чтобы разобраться, в SoftICE я поставил точку остановки сразу после ввода пароля, а затем медленно продвигался вверх по стеку, пока не нашёл алгоритм. Это было ещё до выхода IDA Pro, поэтому у меня на стене были приклеены десятки страниц распечаток с ассемблерным кодом, исчерченным красным маркером. Я был очень доволен, когда наконец во всём разобрался. В то время Microsoft было разрешено экспортировать только 40-битную криптографию, поэтому компания послушно реализовала строго разрешённую криптографию: они многократно хэшировали пароль в MD5 с помощью «соли» (случайно выбранных байтов из файла), чтобы получить 40-битный ключ, затем добавляли к нему соль и снова хэшировали. Проверка пароля на компьютерах того времени занимала примерно полсекунды. Нам пришлось задействовать атаку по словарю, потому что взломать пароль брутфорсом было практически невозможно. В итоге мы написали взломщик паролей для крупных компаний и агентств. Программа выполняла брутфорс 40-битного ключевого пространства, используя эти причудливые инструкции MMX на Pentium. Я слышал, что однажды она работала девять месяцев, прежде чем подобрала пароль.
Эли Бихам и Пол Кохер опубликовали описание атаки с известным открытым текстом (текст перед шифрованием), но в нашем случае известный открытый текст был заархивирован. Чтобы получить коды Хаффмана в начале сжатого файла, вам по сути нужен весь файл. Атака была практически бесполезной для правоохранительных органов.
PKZIP получает свои байты соли, выделяя память без её инициализации, так что там содержатся биты материалов из других запущенных программ или изображения, или документы, что угодно. Это прекрасно работало в Windows, но во многих системах Unix память инициализируется автоматически при выделении. InfoZIP выбирал байты соли с помощью функции rand языка Си. Он инициализировал состояние генератора случайных чисел, делая XOR временной метки на идентификаторе процесса, а затем генерировал десять байт на файл. В таком случае, зная временную метку и идентификатор процесса, можно было, теоретически, восстановить байты заголовка, что, в свою очередь, позволяло провести атаку Бихама и Кохера. Похоже, авторы InfoZIP знали об этой атаке, потому что пошли на шаг дальше — и зашифровали заголовок, используя пароль. Таким образом, у злоумышленника был только дважды зашифрованный открытый текст, и атака не сработала бы.
Я заметил это, поскольку пароль одинаковый в обоих проходах, первый байт потока одинаковый в каждом из них. Точно так же, как при двойном переключении выключателя света он остается там, где был в начале, при повторном XOR’е байта с одним и тем же байтом потока он остается нетронутым. Это позволило мне разработать очень мощную атаку только на шифротекст: получив пять зашифрованных файлов в архиве, я мог вывести внутреннее состояние функции rand без необходимости смотреть на метку времени или знать идентификатор процесса. Дальше я мог сгенерировать оригинальные незашифрованные заголовки. Поскольку всего несколько бит в каждой части шифра влияют на следующую часть, я также мог угадать несколько бит состояния и проверить, даёт ли расшифровка следующих байтов дважды тот ответ, который я ожидал. По мере продвижения вперёд мне приходилось угадывать всё меньше и меньше кусочков ключа. Каждый дополнительный файл также позволял исключить больше потенциальных материалов ключа; в то время это занимало несколько часов на одном десктопе. Я опубликовал статью об этом и получил возможность представить её в Японии на конференции Fast Software Encryption 2001.
Вскоре я ушёл из компании AccessData, в течение года работал в стартапе по нейросетям, провёл три года в обучении на степень магистра компьютерных наук в университете Окленда с Крисом Калудом, начал обучение на докторскую с математическим физиком Джоном Баэзом в Калифорнийском университете Риверсайда, шесть лет работал в команде по прикладной безопасности Google, закончил докторскую, а ещё через несколько лет стал техническим директором нового стартапа.
Примерно полгода назад я совершенно неожиданно получил сообщение в LinkedIn от одного русского парня. Он прочитал ту статью, которую я написал 19 лет назад, и хотел знать, будет ли атака работать на архиве, который содержит только два файла. Быстрый анализ показал, что это требует огромного количества вычислительных мощностей и денег. Поскольку есть только два файла, на каждом этапе подбора возникает гораздо больше ложных срабатываний. В конечном итоге получается 2 73 возможных ключей для тестирования, почти 10 секстиллионов. Я подсчитал, что большой кластер на GPU будет работать год, а его стоимость составит порядка 100 тысяч долларов. Он поразил меня, сказав, что согласен потратить столько денег, чтобы восстановить ключ.
Я потратил некоторое время, восстанавливая атаку, описанную в статье. К моему огорчению, там были некоторые хитрые детали, которые я упустил в статье, но я снова их проработал. А потом я обнаружил, что совершил ужасную ошибку, оценивая объём вычислений!
Я смутно помнил, что была проделана некоторая работа по криптоанализу TLCG через редукцию базиса решётки, поэтому откопал оригинальную статью. Так и было! Нужно было просто определить решётку с базисными векторами, заданными 2 32 и степенью константы из TLCG, а затем сделать редукцию базиса решетки. На уменьшенном базисе я мог бы восстановить исходное состояние из старших байтов простым перемножением матриц.
По крайней мере, такова идея. Нужно было пять байт, чтобы дойти до единственно правильного результата, и на тот момент атаки у меня было только четыре. Описанный в статье процесс редко давал правильный ответ. Однако я знал, что ответ должен быть близок к правильному, поэтому мог пробежаться по всем возможным значениям key1 и проверить разницу между реальным ответом и истинным. Разница всегда составляла один из 36 векторов! С помощью этой оптимизации я могу свести перебор всего к 36 вариантам вместо четырёх миллиардов. Мы всё ещё в деле.
Дальше мы столкнулись с проблемой передачи данных между машинами с GPU. Мой партнёр по бизнесу Нэш Фостер занимался реализацией в GPU. Он консультировал меня, насколько быстро выполняются различные операции, и писал большую часть вспомогательных структур для приложения с моим кодом для криптовзлома. Как получить эти петабайты ключей-кандидатов для тестирования на GPU? Они будут почти всё время простаивать, ворочая своими ядрами в ожидании работы. Мне пришло в голову, что на каждом этапе моей атаки проверяется много бит, а затем сохраняется только один из примерно 65 тыс. кандидатов. Если бы найти какой-то способ выводить эти биты на основе имеющейся информации, а не просто брутфорсить их, я бы сэкономил много работы и, что более важно, много сетевого трафика. Проблема здесь была в слишком сложных алгоритмах, представляющих смесь конечных полей с кольцами целых чисел, а они не очень хорошо сочетаются друг с другом.
Я подумал о других криптоаналитических атаках, которые мне известны. Одной из них была атака «встреча в середине» (meet-in-the-middle). Она казалась многообещающим кандидатом. Атака применяется к блочному шифру, когда он использует одну часть материала ключа для выполнения первой половины шифрования, а другую часть — для второй. Это относилось к шифру zip, но материал ключа намного перевешивал количество битов в середине. Затем мне пришло в голову, а что, если использовать линейность CRC32: если выполнить операцию XOR на двух выходах последнего CRC32, то результат будет независим от key2! Вместо того, чтобы вычислять промежуточное состояние шифра и хранить его в таблице, я бы вычислял XOR двух промежуточных состояний и хранил его вместо этого.
Я написал дифференциальную атаку «встреча в середине» и запустил её на своем ноутбуке. Этап, который раньше занимал несколько часов, теперь завершился всего за несколько секунд. Следующий этап, который мог занять неделю на GPU-ферме, завершился за несколько часов на одном мощном CPU. У меня не получалось оптимизировать третий этап атаки достаточно, чтобы это отразилось на общей скорости, но полностью отпала необходимость перемещать данные: мы просто вычисляли кандидатов для каждого GPU на компьютере с этими картами. Нэш написал код GPU, который работал с невероятной скоростью.
Атака продолжалась десять дней и закончилась неудачей.
Мы исправили ошибку, повторно запустили код и нашли правильный ключ в течение дня. Наш клиент был очень доволен и дал нам большой бонус за то, что мы так быстро нашли ключ и сэкономили ему столько денег сверх нашей первоначальной оценки.
Теперь я ищу работу. Если у вас есть интересные проблемы по техническому анализу или оптимизации, дайте знать.
Что такое криптография, и где она применяется?
Криптография — это наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним), целостности данных (невозможности незаметного изменения информации), аутентификации (проверки подлинности авторства или иных свойств объекта).
Изначально криптография изучала методы шифрования информации — обратимого преобразования открытого (исходного) текста на основе секретного алгоритма или ключа в шифрованный текст (шифротекст). Традиционная криптография образует раздел симметричных криптосистем, в которых зашифровывание и расшифровывание проводится с использованием одного и того же секретного ключа. Помимо этого раздела современная криптография включает в себя асимметричные криптосистемы, системы электронной цифровой подписи (ЭЦП), хеш-функции, управление ключами, получение скрытой информации, квантовую криптографию.
Криптография не занимается защитой от обмана, подкупа или шантажа законных абонентов, кражи ключей и других угроз информации, возникающих в защищённых системах передачи данных.
До 1975 года криптография представляла собой шифровальный метод с секретным ключом, который предоставлял доступ к расшифровке данных. Позже начался период ее современного развития и были разработаны методы криптографии с открытым ключом, которые может передаваться по открытым каналам связи и использоваться для проверки данных.
Современная прикладная криптография представляет собой науку образованную на стыке математики и информатики. Смежной наукой криптографии считается криптоанализ. Криптография и криптоанализ тесно взаимосвязаны между собой, только в последнем случае изучаются способы расшифровки сокрытой информации.
С модификацией до открытого ключа криптография получила более широкое распространение и стала применяться частными лицами и коммерческими организациями, а в 2009 году на ее основе была выпущена первая криптовалюта Биткоин. До этого времени она считалась прерогативой государственных органов правления.
Виды криптографии
В основе криптографических систем лежат различные виды криптографии. Всего различаю четыре основных криптографических примитива:
Возможности и сферы применения
Изначально криптография использовалась правительством для безопасного хранения или передачи документов. Современные же асимметричные алгоритмы шифрования получили более широкое применение в сфере IT-безопасности, а симметричные методы сейчас применяются преимущественно для предотвращения несанкционированного доступа к информации во время хранения.
В частности криптографические методы применяются для:
Криптография и блокчейн
В блокчейне криптография используется для защиты и обеспечения конфиденциальности личностей и персональных данных, поддержания высокой безопасности транзакций, надежной защиты всей системы и хранилища.
Хеш функции
Хэш-функции в блокчейне взаимосвязаны между собой, с их помощью достигается защита информации и необратимость транзакций. Каждый новый блок транзакций связан с хэшем предыдущего блока, который в свою очередь образован на основе хэша последнего блока, образованного до него. Таким образом каждый новый блок транзакции содержит в себе всю информацию о предыдущих блоках и не может быть подделан или изменен.
Для того, чтобы новый блок был добавлен в блокчейн цепь, сеть должна прийти к общему консенсусу и подобрать хэш нового блока. Для этого при помощи вычислительной техники майнеры предлагают множество “nonce” — вариантов значения функции. Первый майнер, который сумел путем случайного подбора сгенерировать хэш, подходящий для комбинации с предыдущими данными, подписывает им блок, который включается в цепь, и новый блок уже должен будет содержать информацию с ним.
Благодаря применению технологии хэширования в блокчейне все транзакции, которые были выполнены в системе, можно выразить одним хэшем нового блока. Метод хэширования делает практически невозможным взлом системы, а с добавлением каждого нового блока устойчивость блокчейна к атакам только увеличивается.
Цифровые подписи
В блокчейне задействован асимметричный метод криптографии на основе публичных и приватных ключей. Публичный ключ служит адресом хранения монет, секретный — паролем доступа к нему. Закрытый ключ основан на открытом ключе, но его невозможно вычислить математическим путем.
Криптография с открытым ключом
Современная криптография с открытым ключом используется в системе блокчейна для перевода монет.
Для чайников принцип криптографии на основе открытых ключей можно объяснить на примере транзакции. Допустим отправитель желает отправить 1 биткоин. Для этого ему необходимо отправить транзакцию, где будет указано, откуда нужно взять монету, и куда она будет направляться (публичный ключ получателя). Когда транзакция сформирована отправитель должен подписать ее своим секретным ключем. Далее узлы связи проверяют соответствие секретного ключа отправителя с его открытым ключом, с которым на текущий момент ассоциируется монета. Если условия соблюдены, то есть открытый и закрытый ключ отправителя взаимосвязаны, то отправленная монета начнет ассоциироваться с уже с открытым ключом получателя.
Заключение
Криптография является важной составляющей современного мира и необходима в первую очередь для сохранения персональных данных и важной информации. С момента появления она прошла множество модификаций и сейчас представляет собой систему безопасности, которая практически не может быть взломана. Переоценить ее возможности для человечества сложно. Современные методы криптографии применяются практически во всех отраслях, в которых присутствует необходимость безопасной передачи или хранения данных.