모두의 dream
Base64 본문
* 공부용으로 열심히 구글링을하며 정리한 내용으로 틀린 내용이 존재할 수 있습니다.
base64, 자주 보고 자주 써본 인코딩 방식이지만 어디에 쓰는지, 어떤 방식인지는 알아본적이 없었다. base64 관련 워게임 문제를 푼 뒤 확실히 정리해보기로 결심했다.
Base64
64개의 ASCII 영역의 문자들로 이루어진 테이블을 이용하여 이진데이터 (binary)를 특정 문자열로 변경하는 것.
1. base64 인코딩 과정.
(1)입력한 8bit 데이터를 6bit 크기로 표현한다.
(2)6bit로 표현한 데이터를 base64 table을 이용하여 문자로 바꿔준다.
2. base64 인코딩 예시.
(1) abc라는 글자를 인코딩한다.
내가 입력한 abc 3글자는 6bit로 나눠지면서 4글자가 된다. (24bit -> 6 × 4)
입력한 글자가 6글자면 8개, 9글자면 12개가 된다.
즉, 입력한 글자가 3n개씩 늘어날수록 인코딩되는 글자는 3n+n개가 된다.
(2) 만약 입력한 문자의 개수가 3의 배수가 아니라면?
남은 자리는 모두 패딩처리 (0으로 채워줌) 하고 이를 '=' 으로 표현한다.
입력한 글자가 1개일때는 'YQ==' 으로 인코딩 된다.
만약 입력한 글자가 2개라면 위와 동일하게 패딩처리 (0으로 채워줌) 하고 '='으로 표현한다.
입력한 글자가 2개일때는 'YWI=' 으로 인코딩 된다.
결국 글자의 개수가 3n+1개 일 떄는 '=' 이 한개, 3n+2개 일 떄는 '=' 이 두 개 붙는다.
3. base64의 사용 목적
주로 이진데이터 (바이너리 데이터)의 손실을 막기 위한 목적으로 사용한다. (호환성)
예시. Baseball 이라는 바이너리 데이터가 존재한다.
이 데이터를 데이터베이스에 저장한다.
데이터베이스는 Notepad(메모장) 이라고 가정한다.
(ANSI, Unicoe, UTF-8 형식만 지원하는 DB라고 가정)
만약 나중에 데이터베이스에서 다시 데이터를 읽어온다면 아래와 같이 문제가 발생하게 된다.
이를 만약 base64 형태로 변환한 후 저장을 하게 된다면?
정상적으로 데이터를 불러올 수 있게된다.
4. Base64 충돌
예시.
현재 a 라는 문자 한 개만 넣은 상태이다.
인코딩된 문자열은 'YQ=='.
인코딩된 문자열을 디코딩 해보면...
위와 같이 정상적으로 디코딩된다.
하지만 패딩처리 과정에서 무작위로 값을 대입하게 된다면?
인코딩된 문자열은 'YQ==' 과 다른 'Yf==' 이 된다.
하지만 디코딩을 진행하면 놀랍게도 a 라는 문자가 똑같이 나오게 된다.
또다른 예시로 ab를 입력한 후 나온 'YWI==' 값을 디코딩 해보면...
위와 같이 정상적으로 ab 문자가 디코딩 된다.
그런데 또다시 패딩을 무작위로 대입한다면?
인코딩된 값은 'YWL=' 으로 'YWI==' 과 다르지만,
위에서 본 ab라는 값이 동일하게 디코딩된다.
이것을 우리는 base64 충돌이라고 부른다.
5. Base64 알고리즘
(1) 인코딩
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
char table[65] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
char text[1024] = { 0, };
int tLength = 0, tIndex = 0, eIndex = 0, step = 0, rlength = 0;
printf_s("input text : ");
fgets(text, 1024, stdin); // 인코딩 할 문자열 입력
text[strlen(text) - 1] = '\0';
tLength = strlen(text); // 입력한 문자열 길이 저장
rlength = tLength + (5 - tLength % 5) % 5;
rlength = rlength * 8 / 5;
// 인코딩 결과 문자열 길이 (3글자 -> 4글자, 4글자 -> 8글자, 3n + n)
char* encoding = malloc(rlength); // rlength값 이용해서 최종 인코딩된 문자열 길이로 문자열포인터 선언 (동적할당)
while (tIndex < tLength)
{
// 입력한 글자를 3개씩 묶어서 2진수로 바꿔주는 과정
step = 0;
step = step << 0 | text[tIndex + 0];
step = step << 8 | text[tIndex + 1];
step = step << 8 | text[tIndex + 2];
// 8bit를 6bit로 짤라주는 과정
encoding[eIndex + 0] = table[(step >> 18) & 0x3F];
encoding[eIndex + 1] = table[(step >> 12) & 0x3F];
encoding[eIndex + 2] = table[(step >> 6) & 0x3F];
encoding[eIndex + 3] = table[(step >> 0) & 0x3F];
eIndex += 4; // 인코딩 문자 저장하는 문자열 가리키는 변수에 +4
tIndex += 3; // 인코딩할 문자 저장하는 문자열 가리키는 변수에 + 3
}
if (tLength % 3 == 2 || tLength == 2)
{
encoding[eIndex - 1] = 0x3D;
}
else if (tLength % 3 == 1 || tLength == 1)
{
encoding[eIndex - 1] = 0x3D;
encoding[eIndex - 2] = 0x3D;
}
printf("\nEncoding Results: ");
for (int i = 0; i < eIndex; i++)
{
printf("%c", encoding[i]);
}
printf("\n");
return 0;
}
(2) 디코딩
#include<stdio.h>
#include<string.h>
int main()
{
char table[256] = {
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, /* 00-0F */
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, /* 10-1F */
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,62,-1,-1,-1,63, /* 20-2F */
52,53,54,55,56,57,58,59,60,61,-1,-1,-1,0,-1,-1, /* 30-3F */
-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14, /* 40-4F */
15,16,17,18,19,20,21,22,23,24,25,-1,-1,-1,-1,-1, /* 50-5F */
-1,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40, /* 60-6F */
41,42,43,44,45,46,47,48,49,50,51,-1,-1,-1,-1,-1, /* 70-7F */
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, /* 80-8F */
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, /* 90-9F */
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, /* A0-AF */
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, /* B0-BF */
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, /* C0-CF */
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, /* D0-DF */
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, /* E0-EF */
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 /* F0-FF */
};
char text[400000] = { 0, };
char decoding[100000] = { 0, };
int tLength = 0, tIndex = 0, eIndex = 0, step = 0;
printf_s("input text : ");
fgets(text, 100000, stdin);
text[strlen(text) - 1] = '\0';
tLength = strlen(text);
while (tIndex < tLength)
{
step = 0;
step = step << 0 | table[text[tIndex + 0]];
step = step << 6 | table[text[tIndex + 1]];
step = step << 6 | table[text[tIndex + 2]];
step = step << 6 | table[text[tIndex + 3]];
decoding[eIndex + 0] = step >> 16;
decoding[eIndex + 1] = (step >> 8) & 0xFF;
decoding[eIndex + 2] = (step >> 0) & 0xFF;
eIndex += 3;
tIndex += 4;
}
printf("\ndecoding Results: ");
for (int i = 0; i < tIndex; i++)
{
printf("%c", decoding[i]);
}
printf("\n");
}디코딩 ex)
x -> A
A -> x
decoding_table[256] = {
}
6bit -> A
decoding_table[65] = x
인코딩된 문자 0 -> 48
decoding_table[48] = 52
256인 이유.
1byte->8bit로는 2^8제곱만큼 데이터를 표현할 수 있다.
글자뿐만 아니라 일반적인 바이너리 파일에서 FF와 같은 hex값이 존재할 경우 이 또한 base64 인코딩을 해야하므로 1byte가 표현할 수 있는 최대 갯수인 2^8인 256으로 테이블을 선언해준다.