кодирование текста в base64
SGVsbG8gd29ybGQh или история base64
Краткая предыстория
Вообще, все началось давно. Настолько давно, что вряд ли остались свидетели holy wars тех дней, когда решалось — сколько же бит должно быть в байте.
Это сейчас нам кажется само собой разумеющимся, что 1 байт = 8 бит, что в байте можно закодировать 256 различных значений. Но когда-то было совсем не так. История помнит и семибитные кодировки, и шестибитные, и даже более экзотические системы (например — ЭВМ «Сетунь», которая использовала троичную логику, то есть один троичный бит — трит мог иметь три, а не два значения, для нее было справедливо соотношение 1 трайт = 6 тритам). Но если оставить в стороне всякую экзотику, то мэйнстримом все-таки были кодировки, в которых 6, 7 или 8 бит в байте.
Шестибитная кодировка (например — BCD) позволяла закодировать в одном байте 64 различных значения, что, как казалось, было вполне достаточно для кодирования алфавитно-цифровых символов, а «лишний» седьмой бит расширял кодировку уже до 128 символов.
Однако скоро восьмибитный байт стал общепринятым.
Проблема восьмого бита
Утверждение восьмибитных кодировок как стандарта де-факто принесло много проблем. К этому моменту уже существовала определенная инфраструктура, использующая именно семибитные кодировки, и holy wars разгорелись с новой силой.
До нас они дошли в виде проблем с «обрезанием восьмого бита» в системе электронной почты. Утверждение восьмибитного байта дало 256 различных значений для одного байта, что, в свою очередь позволило уместить в одной кодовой таблице и общепринятые символы (цифры, знаки препинания, латиницу) и символы, скажем кириллицы. Казалось бы — сплошное удобство, текст можно набирать хоть русскими буквами, хоть английскими, а если нужно — и для немецких умлаутов место найдется!
Но, как всегда, дьявол крылся в деталях. Уже накопленный и работающий хард-н-софт зачастую был приспособлен для кодировок семибитных, что приводило к разнообразным проблемам.
Например, почтовый сервер при передаче письма мог совершенно спокойно обнулить старшие биты в каждом байте сообщения, что не могло не привести к проблемам, зачастую информация просто катастрофически терялась.
Для временного решения этой проблемы было предложено несколько вариантов. Одним из них стала кодировка «КОИ-8». Решение, нужно признать, весьма элегантное — в этой кодировке русские буквы располагались по порядку латинских и отличались от них ровно на тот самый старший бит. Таким образом при обрезании этого бита русская «А» превращалась в латинскую «A», «Б» — в «B» и так далее, сообщение просто транслитерировалось и его все-таки можно было прочитать. Правда, и тут не обошлось без скелета в шкафу — сортировка в русском алфавитном порядке в «КОИ» становилась кошмаром…
А что было делать другим языкам, народам и кодировкам? А бинарные данные? Все равно кодировки с транслитерацией не решали фундаментальную проблему — потерю восьмого бита, потерю части информации. Так родилась кодировка (а точнее — алгоритм) Base64.
Алгоритм Base64
Идея base64 проста — обратимое кодирование, с возможностью восстановления, которое переводит все символы восьмибитной кодовой таблицы в символы, гарантированно сохраняющиеся при передаче данных в любых сетях и между любыми устройствами.
В основе алгоритма лежит сведение трех восьмерок битов (24) к четырем шестеркам (тоже 24) и представление этих шестерок в виде символов ASCII. Таким образом получается обратимое шифрование, единственным недостатком которого будет увеличивающийся при кодировании размер — в соотношении 4:3.
Пример:
Возьмем текст русский текст «АБВГД». В двоичной форме в кодировке Windows-1251 мы получим 5 байтов:
11000000
11000001
11000010
11000011
11000100
(00000000) — лишний нулевой байт нужен, чтобы общее число бит делилось на 6
Разделим эти биты на группы по 6:
110000
001100
000111
000010
110000
111100
010000
000000
Берем массив символов «ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/» и получившиеся числа переводим в эти символы, используя их, как индексы массива, получаем «wMHCw8Q». Остается только добавить в конце один символ «=», как указание на один лишний нулевой байт, который мы добавляли на первом шаге и получить окончательный результат:
«АБВГД»: base64 = «wMHCw8Q=»
Обратное преобразование не менее легко, попробуйте, например, расшифровать то, что вынесено в заголовок этой статьи.
Применение
Алгоритм base64 и по сей день применяется там, где нет возможности гарантировать бережного обращения с вашей информацией — например при кодировании вложений электронной почты. В PGP алгоритм base64 используется для кодирования бинарных данных.
Можно представить себе и другие применения base64 — например при сохранении в базу данных, если заранее неизвестно окружение (ох уж эти magic_qoutes в PHP!) и нет необходимости в индексации и поиске по тексту, можно воспользоваться base64.
base64 вполне может использоваться для получения хэшей, например по алгоритму md5, как средство против табличного подбора хэша, если данные, например пароль пользователя в системе, предварительно будут преобразованы в base64.
ZBase32, Base32 и Base64 алгоритмы кодирования
Многие используют Base64 кодирование, реже Base32 и еще реже ZBase32 (вы знаете о таком?), но не все понимают их алгоритмы. В статье я описываю достоинства, недостатки данных кодировок, а также рассказываю о их реализации.
Не так давно у меня возникла необходимость использовать кодированные данные в адресе http-ссылки. Как известно, стандарт http подразумевает регистронезависимые url-адреса и любой прокси-сервер или браузер мог испортить данные в случае использования регистрочувствительного кодирования.
Плюсы и минусы
Base64
Позволяет кодировать информацию, представленную набором байтов, используя всего 64 символа: A-Z, a-z, 0-9, /, +. В конце кодированной последовательности может содержаться несколько спецсимволов (обычно “=”).
Base32
Использует только 32 символа: A-Z (или a-z), 2-7. Может содержать в конце кодированной последовательности несколько спецсимволов (по аналогии с base64).
ZBase32
Описание алгоритма ZBase32 кодирования
Позволю себе при описании алгоритма показывать выкладки на C# для большего понимания.
Итак, имеем 32-х символьный алфавит следующего содержания:
На входе массив байтов (естественно, по 8 бит каждый), который хотелось бы перевести в символы из алфавита.
Алфавит представляет собой строку из 32-х элементов, а это означает, что каждый из его символов кодируется числом от 0 до 31 (индексы символов в строке). Как известно, любое число от 0 до 31 в бинарной системе счисления можно записать, используя 5 битов байта. Из этого следует, что если представить исходный набор байтов как единый массив битов и разбить его на кусочки по 5 битов (см. рисунок ниже), то мы получим набор координат символов из алфавита. Вот, собственно, и все.
Алгоритмы Base32 и Base64 аналогичны ZBase32, только разные алфавиты (по составу в случае с Base32, по составу и размеру в случае Base64) и размеру “отщипываемых” кусочков бит (6 бит для Base64).
Итак, я предлагаю перед тем, как начать разбиение исходных данных на кусочки по 5 бит, подготовить место куда будет записываться результат. Чтобы не задумываться об индексах в статических массивах, давайте использовать StringBuilder.
При инициализации сразу задаем размер результирующей строки (чтобы не тратить время на расширение в процессе работы алгоритма).
Теперь осталось пробежать по исходному массиву байтов и разделить его на 5-и битовые кусочки. Для удобства я предлагаю работать с группой по 5 байтов, так как это 40 бит — число, кратное длине “кусочков”. Но не забываем, что исходные данные никто для нас не подгонял, поэтому учитываем возможность недостачи.
Так как мы работаем с группой из 5 байтов, нам нужен буфер, где будет формироваться сплошной набор битов (всего 40 бит). Заведем переменную типа ulong (64 бита в нашем распоряжении) и поместим туда текущую партию байтов.
И заключительный этап — это “отщипывание” из того, что получилось, кусочков по 5 бит и формирование результата.
Возможно, в последнем примере кода с первого взгляда не все понятно, но если вы немного сосредоточитесь, то все станет на свои места.
Процесс декодирования происходит аналогично процессу кодирования, только в обратном направлении.
Вы можете посмотреть полную реализацию ZBase32Encoder.
Мануал по методу кодирования base 16/32/64.
История появления кодировки.
Кодировка base берет свое начало еще с тех времен, когда не было определено сколько бит должно содержаться в одном байте. Сейчас всем известно, что в одном байте содержится 8 бит и с помощью него можно закодировать 256 различных значений, но так было не всегда.
Раньше были популярны кодировки, содержащие 6, 7 или 8 бит в байте. Таким образом, 6 бит позвояло закодировать в одном байте 64 различных значения, а 7-ми битная кодировка 128 значений. Казалось бы, что этого достаточно для того, чтобы закодировать буквенно-цифровой алфавит. Но вскоре была принята кодировка, содержащая 8 бит в одном байте.
Такая кодировка привнесла много проблем. В первую очередь, эти проблемы были связаны с оборудованием, которое уже работало на других кодировках, где байт содержал 6 или 7 бит. Но помимо этого была проблема обрезания 8-го бита в системах электронной почты, т.к. весь сфот был заточен под 7-ми или 6-ти битную кодировку. Как пример, 7-ми битная кодировка могла спокойно обнулить каждый 8-ой бит, что приводило к потери данных.
Тут на помощь пришел base 64. Идея base64 проста — обратимое кодирование, с возможностью восстановления, которое переводит все символы восьмибитной кодовой таблицы в символы, гарантированно сохраняющиеся при передаче данных в любых сетях и между любыми устройствами. В основе алгоритма лежит сведение трех восьмерок битов (24) к четырем шестеркам (тоже 24) и представление этих шестерок в виде символов ASCII. Таким образом получается обратимое шифрование, единственным недостатком которого будет увеличивающийся при кодировании размер — в соотношении 4:3.
Ниже приведена схема смещения битов в base 64
Пример:
Возьмем русский текст «АБВГД». В двоичной форме в кодировке Windows-1251 мы получим 5 байтов: 11000000 11000001 11000010
11000011 11000100 (00000000) — лишний нулевой байт нужен, чтобы общее число бит делилось на 6
Разделим эти биты на группы по 6: 110000 001100 000111 000010
110000 111100 010000 000000
Берем массив символов «ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/» и получившиеся числа переводим в эти символы, используя их, как индексы массива, получаем «wMHCw8Q». Остается только добавить в конце один символ «=», как указание на один лишний нулевой байт, который мы добавляли на первом шаге и получить окончательный результат: «АБВГД»: base64 = «wMHCw8Q=» Возможно и обратное преобразование.
Base 16
Base 32
Base 32 использует 32 символа: A-Z (или a-z), 2-7. Может содержать в конце кодированной последовательности несколько спецсимволов (по аналогии с base64). В данном алгоритме преобразования нам необходимо будет разделять двоичные значения на группы по 5 бит.
Основные отличия кодировок
Base64
Позволяет кодировать информацию, представленную набором байтов, используя всего 64 символа: A-Z, a-z, 0-9, /, +. В конце кодированной последовательности может содержаться несколько спецсимволов (обычно “=”).
Преимущества: Позволяет представить последовательность любых байтов в печатных символах. В сравнении с другими Base-кодировками дает результат, который составляет только 133.(3)% от длины исходных данных.
Недостатки: Регистрозависимая кодировка.
Base32
Использует только 32 символа: A-Z (или a-z), 2-7. Может содержать в конце кодированной последовательности несколько спецсимволов (по аналогии с base64).
Преимущества: Последовательность любых байтов переводит в печатные символы. Регистронезависимая кодировка. Не используются цифры, слишком похожие на буквы (например, 0 похож на О, 1 на l).
Недостатки: Кодированные данные составляют 160% от исходных.
Как закодировать/декодировать base?
В основном в заданиях по ctf вам будет попадаться base 64. Его легко определить, т.к. на конце будет знак «=». Например, мы кодировали строку «АБВГД» в base 64 и у нас получился результат «wMHCw8Q=». Как мы видим, здесь присутсвует знак «=», который говорит нам о том, что строка зашифрована в base 64.
Итак, как же ее декодировать? Все очень просто. Base 16, 32, 64 легко декодировать онлайн-сервисами. Т.е. вбиваете в гугле подобный запрос:»base 64 online decoder» и вам будет выдан большой перечнь ссылок на онлайн декодеры. Берем первый попавшийся, разве что для уточнения стоит воспользоваться сразу несколькимим онлайн декодерами.
Процесс кодирования почти ничем не отличается, разве, что вам нужно вбить в запросе не «decode», а «encrypt». Бывает, что нужно обращать внимание на то, какой кодировкой вы пользуетесь. В русскоязычной версии ОС «Windows» обычно используется кодировка windows-1251.
Практика
Задание 1:
Взгляните на эту строку:
ZmxhZ2lzVzBXdGhpc2lzQkFTRTY0Cg==
На конце мы видим «=», причем двойное, что сразу наводит на мысль, что это base 64. Воспользуемся онлайн-декодером.
Задание 2:
Посмотрим на эту строку:
MZWGCZ33MJQXGZJTGJ6Q
На конце мы не видим знака «=». На base 16 тоже не похоже, тогда попробуем base 32.
Снова воспользуемся онлайн-декодером.
И вот наш флаг: flag
Задание 3:
Была получена такая строка: 666C61677B48656C6C6F2C20576F726C64217D
Здесь нет ни знака «=», алфавит ограниченный. Похоже на base 16 или просто hex.
Как и прежде, пользуемся онлайн-декодером.
Отлично, у нас есть флаг, но это же задание можно было решить и через hex декодер.
Кодирование и декодирование в формате Base64
Документация
Кодирование Base64 широко используется в случаях, когда требуется перекодировать двоичные данные для передачи по каналу приспособленному для передачи текстовых данных. Это делается с целью защиты двоичных данных от любых возможных повреждений при передаче. Base64 широко используется во многих приложениях, включая электронную почту (MIME), и при сохранении больших объёмов данных в XML.
В языке JavaScript существуют две функции, для кодирования и декодирования данных в/из формат Base64 соответственно:
Функция atob() декодирует Base64-кодированную строку. В противоположность ей, функция btoa() создаёт Base64 кодированную ASCII строку из «строки» бинарных данных.
Tools
Related Topics
The «Unicode Problem»
Since DOMString s are 16-bit-encoded strings, in most browsers calling window.btoa on a Unicode string will cause a Character Out Of Range exception if a character exceeds the range of a 8-bit byte (0x00
0xFF). There are two possible methods to solve this problem:
Here are the two possible methods.
Solution #1 – escaping the string before encoding it
To decode the Base64-encoded value back into a String:
Unibabel implements common conversions using this strategy.
Solution #2 – rewrite the DOMs atob() and btoa() using JavaScript’s TypedArray s and UTF-8
Use a TextEncoder polyfill such as TextEncoding (also includes legacy windows, mac, and ISO encodings), TextEncoderLite, combined with a Buffer and a Base64 implementation such as base64-js.
When a native TextEncoder implementation is not available, the most light-weight solution would be to use TextEncoderLite with base64-js. Use the browser implementation when you can.
The following function implements such a strategy. It assumes base64-js imported as
Абсурдно быстрое кодирование и декодирование base64
Об авторе: Дэниель Лемир — профессор компьютерных наук в Университете Квебека (Канада). Его исследования затрагивают производительность программного обеспечения и инженерию данных
Компьютеры хранят данные как поток бит. Как изображения, аудио- или видеофайлы, так и бинарные файлы могут содержать практически любую последовательность бит.
Однако мы часто используем текстовые форматы; например, веб-страницы и электронные письма должны быть в текстовом формате. Как же мы отправляем изображения по электронной почте? Как внедряем картинки на веб-страницы? Один из вариантов — поставить ссылку на реальный бинарный файл. Другой типичный подход — встроить бинарный файл непосредственно в тело письма или веб-страницы с помощью base64. Base64 — это просто стандартный текстовый формат, который можно использовать для кодирования любых бинарных данных. Если быть точным, то код base64 — всегда валидный текст ASCII (и поэтому также валидный UTF-8). Каждый байт кода base64 содержит 6 бит данных. То есть мы «теряем» примерно 2 бита на байт. Поэтому эквивалент base64 бинарного файла будет примерно на 33% больше. На практике такое увеличение размера редко становится проблемой. Насколько я знаю, приложения к электронным письмам почти всегда кодируются в base64.
При написании HTML я нашёл удобным внедрять изображения напрямую в HTML-код с помощью схемы data URI. Например, в недавней статье я таким образом закодировал файл PNG. Крупнейшие веб-сайты вроде Google постоянно используют эту схему. Небольшим недостатком становится то, что веб-страницы чуть увеличиваются в размере (что очевидно) и нельзя воспользоваться преимуществами кэширования изображений. Но зато браузер экономит один сетевой запрос.
Если вы веб-разработчик, то можете использовать Web Storage для создания базы данных для вашего приложения на клиентской стороне. Эта клиентская БД будет хранить изображения и произвольные данные, но они все должны быть закодированы в base64.
Большинство движков баз данных поддерживают бинарные данные, но некоторые требуют в какой-то момент кодирования в base64: это MongoDB, Elasticsearch, Amazon SimpleDB и Amazon DynamoDB. Вероятно, и какие-то ещё.
Base64 повсеместно используется в криптографии для обмена ключами. Форма base64 также используется для передачи произвольных данных в составе URI.
К счастью, кодирование и декодирование base64 происходят быстро. Хотя есть случаи, когда недостаточная скорость может стать проблемой. Мэтт Крейн и Джимми Лин обнаружили медленное декодирование бинарных атрибутов base64 в Amazon DynamoDB.
Насколько быстро вы можете декодировать данные base64? На последнем процессоре Intel это требует примерно двух циклов на байт (из кэша) при использовании быстрого декодера вроде того, что встроен в браузер Chrome. Этот быстрый декодер, в основном, занят обращениями к таблице. Это намного медленнее, чем копирование данных в кэше (что занимает менее 0,05 циклов на байт).
Это лучшее, что можно получить?
Несколько лет назад Альфред Клопп показал, что можно добиться гораздо лучшего результата при использовании векторных инструкций. Войцех Мула, я сам и несколько коллег (в том числе Говард и Курц) решили серьёзно пересмотреть проблему. Мула открыл веб-страничку, посвящённую этой теме.
Мы обнаружили, что можно ускорить обработку в 10 раз и использовать всего около 0,2 циклов на байт на последних процессорах Intel при использовании векторных инструкций. Это по-прежнему больше, чем копирование, но намного меньше лимита, способного когда-либо стать самым узким местом системы. Должен обратить внимание, что в эти 0,2 цикла на байт входит обработка ошибок: декодер должен декодировать и проверять входные данные (например, если найдены недопустимые символы, то декодирование отменяется).
Код для нашего исследования доступен, так что можете воспроизвести результаты. Наша статья опубликована на arXiv и принята для публикации в веб-версии ACM Transactions.
Насколько я понимаю, наши хорошие результаты интегрированы в библиотеку base64 Кломпа.