Введение
Для некоторых изображений, статей или домашних страниц пользователей и т. д. необходимо создать URL-адрес, чтобы предоставить его внешнему миру.
При внешней публикации URL обычно"имя домена/путь/идентификатор ресурса",
Среди них путь является необязательным, например, при генерации короткой ссылки это может быть прямое «доменное имя/идентификатор ресурса».
Пример:
Формат URL-адреса самородков:
самородки.IM/пользователь/299912…
самородки.IM/post/684490…
Формат URL короткой книги:
Woohoo.Краткое описание.com/U/11's 3 раунда 06 Афан…
Woohoo.Краткое описание.com/afraid/3place 395's 8 ah...
Как устроена часть идентификатора ресурса в конце этих ссылок?
Точно знать нельзя, но можно предположить.
Идентификатор ресурса слепка, шестнадцатеричный код, 32 байта, если возможноUUID(убрать перегородку) илиMD5.
Будь то UUID или MD5, он случайный, поэтому не нужно беспокоиться о том, что его найдут.Поскольку диапазон значений составляет 128 бит, вероятность конфликта очень мала.
Идентификатор ресурса Jianshu, шестнадцатеричный код, 12 байт, то есть 48 бит, имеет диапазон значений более 200 триллионов, что достаточно для выделения и имеет хорошую читаемость.
Но диапазон значений 48 бит, в противном случае он принимает случайное значение, такое как UUID, иначе легко конфликтовать,
Следовательно, если предположить, что исходный идентификатор создан с помощью идентификатора сегмента или самоувеличивающегося идентификатора, вероятность самоувеличивающегося идентификатора относительно высока из-за более длинных значащих битов (количества битов), требуемых алгоритмом снежинки.
Однако, если ID автоинкрементируется, он будет показывать закономерность (предыдущие символы остаются неизменными), а другие могут делать несколько запросов подряд, вычислять шаг автоинкремента, а затем исчерпать все свои ресурсы.
Итак, после получения идентификатора роста и перед шестнадцатеричным кодированием может быть шифрование.
Итак, как сделать шифрование?
2. Зашифровать идентификатор
Результат шифрования должен соответствовать следующим пунктам:
1. Трудно угадать оригинальный ID;
2. Зашифрованный идентификатор и оригинальный идентификаторсопоставление один к одному, чтобы не повторяться;
3. Зашифруйте целочисленный идентификатор (64 бита, допустимые биты
- Пункт 1:
Доступны MD5, SHA, AES, DES и т. д.;
- Пункт 2:
Алгоритмы дайджеста, такие как MD5, не подходят, и разные исходные тексты могут вычислять один и тот же хэш;
Чтобы удовлетворить взаимно-однозначному отображению, функция должна быть обратимой.
- Пункт 3:
AES, DES тоже не устраивают.
Самый короткий результат шифрования AES составляет 16 байт.
DES шифрует исходный текст размером менее 8 байт, а зашифрованный текст составляет 8 байтов; при шифровании исходного текста в 8 байтов зашифрованный текст составляет 16 байтов.
Подводя итог, нам нужна функция, которая шифрует и расшифровывает значения типа Long, при этом шифротекст не будет «расширяться».
Давайте посмотрим, как это делает AES, и скопируем домашнее задание.
3. Алгоритм AES
Затем возьмите AES128 в качестве примера, чтобы увидеть шаги шифрования AES.
Некоторые картинки и тексты взяты из статьи"Подробный алгоритм кода - AES"а также"Описание алгоритма AES и реализация на языке C", вторгаться и удалять.
3.1 Общий процесс
Основная операция AES128 заключается в шифровании и дешифровании 16-байтового (128-битного) содержимого.
Если исходный текст длиннее 16 байт, он будет сгруппирован в группу по 16 байт.Если последняя группа меньше 16 байт, она будет дополнена до 16 байт.
AES128 проходит 10 раундов операций, из которых раунды 1-9 одинаковы, а раунд 10 немного отличается.
Каждый раунд операций включаетПодстановка байтов, сдвиг строки, обфускация столбца, добавление круглого ключаДождитесь четырех подопераций;
У каждой подоперации есть обратная операция, и исходный текст может быть расшифрован обратной операцией в обратном порядке.
3.2 Замена байтов (подбайты)
Подстановка байтов должна использовать блок S. Блок S имеет два массива с именами: SBOX, INV_SBOX.
S-бокс имеет следующие особенности:
Если y = SBOX[x], то x = INV_SBOX[y];
Или напишите иначе: x = INV_SBOX[SBOX[x]].
Например, простой S-блок 2-го порядка:
int[] s_box = new int[]{2, 0, 3, 1};
int[] inv_s_box = new int[]{1, 3, 0, 2};
for (int x = 0; x < s_box.length; x++) {
System.out.print(inv_s_box[s_box[x]] + " ");
}
System.out.println();
for (int x = 0; x < s_box.length; x++) {
System.out.print(s_box[inv_s_box[x]] + " ");
}
вывод:
0 1 2 3
0 1 2 3
S-блок AES имеет 8-й порядок (8 x 8), который занимает диапазон одного байта (0-255).Что касается того, как построить S-блок, эта статья не будет расширяться.
Операция замены байта:
for (int j = 0; j < 16; j++) {
state[j] = SBOX[state[j]];
}
Обратная замена байта:
for (int j = 0; j < 16; j++) {
state[j] = INV_S_BOX[state[j]];
}
Операция замены байта обеспечивает алгоритмупутаница.
Как и при запутывании кода, исходный текст изначально читаем, но после запутывания он становится нечитаемым;
Однако шаблон не меняется после обфускации, например, исходный метод foo() становится a() после обфускации, а все места, где foo() вызывается после обфускации, становятся a().
То есть статистические характеристики все еще существуют после замены байта.
3.3 ShiftRows
Смещение строк относительно просто, то есть используется 16-байтовая матрица с 4 строками и 4 столбцами,
Среди них строки 1, 2 и 3 сдвигаются влево (обратная операция сдвигается вправо) на 1, 2 и 3 байта соответственно.
3.4 Путаница с колонками (MixColumns)
Обфускация столбца — самая сложная из всех подопераций.
Подобно смещению строк, разделите 16 байтов на 4 строки и 4 столбца;
Разница в том, что запутывание столбцов работает с 4 байтами каждого столбца отдельно (и умножает влево матрицу 4x4).
Расшифровка также представляет собой матрицу умножения влево, а матрица расшифровки является обратной зашифрованной матрицей.
Код операции для столбца выглядит следующим образом:
static inline uint8_t mul2(uint8_t a) {
return (a & 0x80) ? ((a << 1) ^ 0x1b) : (a << 1);
}
/*
* 左乘置换矩阵
* [d0] [02 03 01 01] [b0]
* [d1] = [01 02 03 01] . [b1]
* [d2] [01 01 02 03] [b2]
* [d3] [03 01 01 02] [b3]
*/
void multiply(uint8_t *b, uint8_t *d) {
uint8_t t = b[0] ^ b[1] ^ b[2] ^ b[3];
// d0 = (b0 << 1) + (b1 << 1) + b1 + b2 + b3 = ((b0 + b1) << 1) - b0 + t
d[0] = mul2(b[0] ^ b[1]) ^ b[0] ^ t;
d[1] = mul2(b[1] ^ b[2]) ^ b[1] ^ t;
d[2] = mul2(b[2] ^ b[3]) ^ b[2] ^ t;
d[3] = mul2(b[3] ^ b[0]) ^ b[3] ^ t;
}
Операции с матрицами требуют сложения и умножения.Прямое целочисленное сложение и прямое целочисленное умножение компьютера может привести к переполнению, что приведет к потере информации и необратимости;
Поэтому AES представила "Полевая операция Галуа", а заинтересованные читатели могут прочитать статью "Работа в поле Галуа и реализация языка C"Узнать о.
Сдвиг строки и запутывание столбца вместе обеспечивают алгоритмудиффузионная способность.
Цель диффузии состоит в том, чтобы позволить одному числу в открытом тексте воздействовать на несколько чисел в зашифрованном тексте, чтобы статистические характеристики открытого текста исчезли в зашифрованном тексте.
Идеальная ситуация состоит в том, чтобы достичьЛавинный эффектЭффект:
Малейшее изменение на входе (например, изменение местами одного двоичного бита) также может привести к значительным изменениям на выходе (например, инвертирование половины битов на выходе).
Если есть только операция смешения столбцов, окончательный эффект заключается в том, что четыре группы [0,3], [4,7], [8,11], [12,15] расширяются соответственно;
С добавлением смещения строки можно достичь эффекта диффузии [0, 15] байтов (изменяется один байт открытого текста, а все 16 байтов зашифрованного текста изменяются случайным образом).
Конечно, для эффекта лавинного эффекта требуется несколько раундов операций, и одного раунда операций недостаточно.
3.5 Добавление ключа раунда (AddRoundKey)
Добавление круглого ключа является самой простой из операций с четырьмя словами, а именно 16 байтов соответственно.XOR с круглым ключом.
Ключ раунда рассчитывается на основе исходного ключа, и AES128 имеет в общей сложности 11 дополнений к ключу раунда.
В сочетании с работой ключа обеспечивается конфиденциальность алгоритма.
Если нет операции с ключом, это похоже на то, что дверь открыта, и независимо от того, насколько надежна защитная дверь, она бесполезна.
4. Целочисленная схема шифрования
AES является типичным шифром типа SP. Сетевая структура шифра типа SP очень ясна. S называется слоем путаницы (нелинейный слой), который в основном играет роль путаницы, а P называется слоем диффузии, которая в основном играет роль диффузии.
В алгоритме AES
1. Используйте поле S для выполнения операции замены байтов для достижения эффекта запутывания;
2. Распределить 4 байта в группе, выполнив матричные операции (MixColumns) в поле Галуа;
3. В то же время подгруппы MixColumns чередуются в сочетании со смещением строк, чтобы реализовать распространение всей группы;
4. Наконец, «ключ» подмешивается, чтобы реализовать конфиденциальность алгоритма.
Примечательно,
Размер пакета AES128 составляет 16 байт, что можно использовать как матрицу 4x4;
Операцию MixColumns можно рассматривать как умножение матрицы 4xN на левую часть матрицы 4x4.
Для 8-байтового целого числа мы также можем рассматривать его как матрицу 4x2 для операций MixColumns.
Следовательно, мы можем следовать структуре и работе AES для выполнения операций шифрования над значением типа Long:
public class LongEncoder {
private static final int ROUND = 8;
private static final byte[] S_BOX = {
99, 124, 119, 123, -14, 107, 111, -59
......
};
private static final byte[] KEY = {
-14, 40, 52, -119, -126, -47, 74, 73,
......
};
private static byte mul2(byte a) {
return (byte) (((a & 0x80) != 0) ? ((a << 1) ^ 0x1b) : (a << 1));
}
public static void mix_column(byte[] s, int i) {
byte t = (byte) (s[i] ^ s[1 + i] ^ s[2 + i] ^ s[3 + i]);
byte b0 = (byte) (mul2((byte) (s[i] ^ s[1 + i])) ^ s[i] ^ t);
byte b1 = (byte) (mul2((byte) (s[1 + i] ^ s[2 + i])) ^ s[1 + i] ^ t);
byte b2 = (byte) (mul2((byte) (s[2 + i] ^ s[3 + i])) ^ s[2 + i] ^ t);
byte b3 = (byte) (mul2((byte) (s[3 + i] ^ s[i])) ^ s[3 + i] ^ t);
s[i] = b0;
s[1 + i] = b1;
s[2 + i] = b2;
s[3 + i] = b3;
}
private static void shift_rows(byte[] state) {
byte t1 = state[7];
byte t0 = state[6];
state[7] = state[5];
state[6] = state[4];
state[5] = state[3];
state[4] = state[2];
state[3] = state[1];
state[2] = state[0];
state[1] = t1;
state[0] = t0;
}
public static long encode64(long value) {
byte[] state = long2Bytes(value);
for (int i = 0; i < ROUND; i++) {
for (int j = 0; j < 8; j++) {
int m = ((i << 3) + j);
// AddRoundKey and SubBytes
state[j] = S_BOX[(state[j] ^ KEY[m]) & 0xFF];
}
shift_rows(state);
mix_column(state, 0);
mix_column(state, 4);
}
for (int j = 0; j < 8; j++) {
state[j] ^= KEY[(ROUND << 3) + j];
}
return bytes2Long(state);
}
......
}
На самом деле длина (в байтах) ввода и вывода не обязательно должна быть кратна 4.
Например, для 6-байтового ввода это можно сделать так:
public static long encode48(long value) {
byte[] state = long2Bytes(value);
for (int i = 0; i < ROUND; i++) {
for (int j = 0; j < 6; j++) {
int m = ((i << 3) + j);
// AddRoundKey and SubBytes
state[j] = S_BOX[(state[j] ^ KEY[m]) & 0xFF];
}
// 对于48bit的输入而言，就不需要ShiftRows了
// 因为先后对[0,3], [2,5]进行MixColumns已经可以对整个输入扩散了
mix_column(state, 0);
mix_column(state, 2);
}
for (int j = 0; j < 6; j++) {
state[j] ^= KEY[(ROUND << 3) + j];
}
// 输出的Long，高位的两个字节没有变
// 所以如果输入时小于2^48的数值，则输出也是小于2^48的数组
return bytes2Long(state);
}
Затем преобразуйте зашифрованное значение в базовое, чтобы вывести идентификатор в виде строки:
private static final byte[] HEX_DIGITS = {
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'a', 'b', 'c', 'd', 'e', 'f'};
/**
* 小于2^48的long数值转十六进制字符串
* @param n long类型整数
* @return 12字节的字符串（十六进制）
*/
public static String long48ToHex(long n) {
if((n >>> 48) > 0){
throw new IllegalArgumentException(n + " is bigger than 2^48");
}
byte[] buf = new byte[12];
for (int i = 5; i >= 0; i--) {
int b = (int) n;
int index = i << 1;
buf[index] = HEX_DIGITS[(b >> 4) & 0xF];
buf[index + 1] = HEX_DIGITS[b & 0xF];
n = n >>> 8;
}
return new String(buf);
}
На данный момент мы завершили шифрование и кодирование целочисленного идентификатора.
Что касается генерации целочисленных идентификаторов, то в Интернете существует множество «схем генерации идентификаторов», и мы не будем их здесь раскрывать.
V. Резюме
Шифрование значения типа Long можно использовать не только для построения идентификатора ресурса, но и для других целей.
Например, статья, которую я написал некоторое время назад:«Поговорим об уникальных идентификаторах устройств», как сказано в тексте, необходимо вычислить еще один ID (как UDID) по ID первичного ключа и вернуть его клиенту.
Метод в этой статье может удовлетворить потребности.
Полный код выложен на github,
адрес:GitHub.com/no89757/Лон…
использованная литература
[1] блочный шифр
[2] Работа в поле Галуа и реализация языка C
[3] Подробное объяснение алгоритма кода — AES
[4] Описание алгоритма AES и реализация на языке C
[5] Лавинный эффект
[6] Говоря об уникальных идентификаторах устройств