Encoding: Base64 và Ascii85

Trong bài viết này, mình sẽ giới thiệu với mọi người về khái niệm Encoding, phân biệt nó với Encryption (Thứ mà nếu có điều kiện mình sẽ cùng chia sẻ trong những bài viết sau), sau đó đi qua 2 ví dụ với Base64 và Ascii85.

Ý định cơ bản của mình khi viết bài này là giới thiệu về phương pháp mã hoá Base64, hay nói đúng theo trên Wikipedia là về một nhóm encoding schemes na ná nhau gọi chung là Base64. Trong quá trình lựa chọn nội dung trình bày, mình quyết định đưa bài viết đi xa hơn mục đích ban đầu của nó một chút, xuất phát từ việc nhận ra Base64, vốn dĩ là một phương pháp Encoding lại thường xuyên bị nhầm thành Encryption.

Trong bài viết này, mình sẽ giới thiệu với mọi người về khái niệm Encoding, phân biệt nó với Encryption (Thứ mà nếu có điều kiện mình sẽ cùng chia sẻ trong những bài viết sau), sau đó đi qua 2 ví dụ với Base64 và Ascii85.

Ý định cơ bản của mình khi viết bài này là giới thiệu về phương pháp mã hoá Base64, hay nói đúng theo trên Wikipedia là về một nhóm encoding schemes na ná nhau gọi chung là Base64. Trong quá trình lựa chọn nội dung trình bày, mình quyết định đưa bài viết đi xa hơn mục đích ban đầu của nó một chút, xuất phát từ việc nhận ra Base64, vốn dĩ là một phương pháp Encoding lại thường xuyên bị nhầm thành Encryption.

Hãy xem chính xác thì Wikipedia nói gì về Base64:

Base64 is a group of similar binary-to-text encoding schemes that represent binary data in an ASCII string format by translating it into a radix-64 representation. The term Base64 originates from a specific MIME content transfer encoding.

Không phải lúc nào Wikipedia cũng đáng tin, nhưng hãy tin khi nó nói Base64 là một (đống) phương pháp Encoding, cụ thể là binary-to-text encoding. Bạn dịch từ này thế nào? Mã Hoá? Khốn thay còn một thuật ngữ khác có cách đọc (và ý nghĩa) khác hẳn mà cũng có thể dịch ra tiếng Việt là Mã Hoá: Encryption.

I. Encoding và Encryption.

Không chỉ người Việt bối rối với 2 từ Mã Hoá và Mã Hoá, các đồng chí Tây cũng bối rối với Encoding và Encryption luôn. Thỉnh thoảng mình thấy bọn hắn dùng encryption và encoding loạn hết cả lên, các thành viên của Stackoverflow cũng nhiều lần phải copy paste câu trả lời giải thích sự khác nhau giữa hai thuật ngữ này từ câu hỏi này sang câu hỏi khác, từ ngày tháng này qua ngày tháng khác. Có thể tìm thấy nhiều định nghĩa, so sánh rất dài về Encryption và Encoding, nhưng ngắn gọn, chúng khác biệt nhau một cách cơ bản về mục đích sử dụng.

Encryption là quá trình chuyển đổi giữ liệu nhằm mục đích tăng cường bảo mật, giữ bí mật thông tin, đảm bảo chỉ người có thẩm quyền mới có thể xem được.

Encoding là quá trình chuyển dữ liệu từ định dạng này sang một định dạng khác nhằm mục đích sử dụng dữ liệu trong các hệ thống khác nhau.

Encryption thường đi kèm với khái niệm key, biết thuật toán encrypt là gì mà không có key thì đừng hòng dịch ra được. Nhiều khi key để mã hoá và key để giải mã còn khác nhau (public/ private key), thành thử chính mình mã hoá mà mình cũng không dịch lại được luôn, phải để người nhận dùng private key dịch.

Encoding thì khác, mục đích nó sinh ra là để giúp các hệ thống khác nhau giao tiếp được với nhau, sử dụng thuật toán và bảng mã công khai. ASCII chính là một phương pháp encoding ánh xạ 1 chuỗi 7 bit nhị phân (sau này là 8 bit) thành 128 ký tự (với 8 bit thì là  256 ký tự).

Các phương pháp binary-to-text encoding thì tìm cách biểu diễn dữ liệu nhị phân dưới dạng một số ký tự trong bảng mã ASCII, thông thường nằm trong 95 ký tự có-thể-in (printable). Cụ thể với Base64 là sẽ chuyển những từng nhóm 6 bit nhị phân thành một trong số 64 ký tự được chọn trước từ bảng mã ASCII.

Việc chuyển đổi này là cần thiết nếu muốn truyền dữ liệu qua những giao thức cũ không chấp nhận binary data, ví dụ như email, hoặc khi ta muốn truyền những ký tự đặc biệt sang đầu bên kia, mà giao thức ta dùng không cho phép sử dụng ký tự ấy. Khi dữ liệu đã truyền hoàn toàn qua giao thức, đầu bên kia chỉ việc giải mã để nhận về dữ liệu ban đầu.

Trước những năm đầu 90, rất nhiều hệ thống hoặc giao thức giả định rằng mỗi ký tự biểu diễn bởi một số nguyên từ 0 đến 127, tức từ 7 bit (Thường encode bằng bảng ASCII 7 bit 128 ký tự). Bit cuối cùng còn lại trong byte được dùng làm meta data control bit trong giao thức, hoặc làm flag bit, hoặc dùng để đánh dấu xem số bit 1 trong 7 bit còn lại là chẵn hay lẻ giúp phát hiện byte lỗi.

Những hệ thống ngày nay thường là 8-bit clean, tức sử dụng 8 bit để mã hoá thành một ký tự, bằng cách chuyển những ký tự này thành từng byte binary data rồi dùng các mã hoá bằng phương pháp khác, ví dụ Base64 sử dụng 1 ký tự đại diện cho 6 bit, ta có thể truyền dữ liệu qua các hệ thống/ giao thức cũ hay thậm chí với những hệ thống mà 1 byte không bằng 8 bit.

II. Base64

Ý tưởng của Base64 tương đối đơn giản. Giả sử ta cần chuyển đổi các ký tự từ bảng mã ASCII 8 bit sang Base64, thay vì mã hoá 8 bit thành một ký tự (tổng cộng 28 = 256 ký tự có thể biểu diễn) ,  ta chỉ sử dụng 6 bit (tổng cộng 26 = 64 ký tự có thể biểu diễn). Vì bội chung nhỏ nhất của 6 và 8 là 24, với mỗi nhóm 3 ký tự 8 bit, sau chuyển đổi ta thu được 4 ký tự 6 bit. Số lượng ký tự sau mã hoá tăng 4/3 lần.

Cùng đến với ví dụ trên Wikipedia cho dễ hiểu:

Screen Shot 2016-10-18 at 12.23.29 AM

Với từ Man, mã ASCII lần lượt là 77, 97, 110. Biểu diễn dưới dạng nhị phân là 01001101, 01100001, 01101110. Nhóm thành từng nhóm 6 bit, ta có 010011, 010110, 000101, 101110, tương ứng với 19, 22, 5, 46 trong hệ thập phân. Đối chiếu với bảng mã Base64 thường dùng như hình bên dưới, kết quả thu được sau mã hoá là TWFu.

Bảng mã Base64 thông dụng:

Vì cứ mỗi nhóm 3 byte sẽ mã hoá thành 4 ký tự Base64, nếu số lượng byte đầu vào không chia hết cho 3, đồng nghĩa với, nhóm 3 byte cuối cùng sẽ chỉ có 1 hoặc 3 byte. Chúng ta cần thêm 1 hoặc 2 byte còn thiếu với giá trị 0 (ký tự NULL trong bảng mã ASCII) vào nhóm cuối để tiếp tục mã hoá.

Ví dụ:
Screen Shot 2016-10-18 at 12.57.07 AM Screen Shot 2016-10-18 at 12.57.21 AM

Để đánh dấu rằng những bit cuối cùng này không phải là bit của dữ liệu gốc, ta mã hoá chúng bằng ký tự =. Đây gọi là ký tự padding. Khi decode và gặp ký tự padding ở cuối đoạn mã hoá, ta biết rằng có một số lượng byte đã được thêm vào khi encode, bao nhiêu ký tự padding thì có bấy nhiêu byte được thêm. Sau khi decode, ta phải bỏ đi những byte đã thêm vào để thu được dữ liệu ban đầu.

Trên thực tế, nếu ta bỏ đi ký tự padding sau khi encode, tại thời điểm decode vẫn có thể xác định được có bao nhiêu byte đã được thêm vào dữ liệu gốc bằng cách lấy số ký tự Base64 chia cho 4. Nếu dư 3 thì đầu vào đã được thêm 1 byte, tương dự dư 2 thì đầu vào  đã thêm 2 byte. Mặc dù ký tự padding được sử dụng để xác định cụ thể sự sai lệch với dữ liệu ban đầu, việc encode và decode không padding vẫn có thể thực hiện bình thường. Một số chuẩn Base64 như UTF-7 không có ký tự padding.

Với các chuẩn Base64 khác nhau, sự phân biệt rõ ràng nhất thông thường là chúng sử dụng các ký tự khác nhau cho index thứ 62 và 63 trong bảng mã, cộng với quy định về ký tự sử dụng để biểu diễn padding. Ví dụ như chuẩn base64url sử dụng _- thay cho +/ thường thấy để thân thiện hơn với url.

Ngày nay, ngoài việc hỗ trợ giao tiếp giữa các giao thức, được sử dụng như một biên pháp truyền và lưu trữ dữ liệu an toàn, tránh xung đột, hoặc sử dụng trong một số trick như encode đoạn script cần thực hiện rồi decode phía victim

Ví dụ:

<?php
eval (base64_decode('encoded_shell_script'));
?>

nhằm qua mặt hệ thống, bypass các scanner và filter, một ứng dụng khá phổ biến khác của Base64 là Data URI Scheme.

Ví dụ về syntax của Data URI Scheme:

<img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAUA
AAAFCAYAAACNbyblAAAAHElEQVQI12P4//8/w38GIAXDIBKE0DHxgljNBAAO
9TXL0Y4OHwAAAABJRU5ErkJggg==" alt="Red dot" />

Bức ảnh dấu chấm màu đỏ trên được mã hoá bằng Base 64. Trong những trình duyệt hỗ trợ Data URI Scheme, đoạn mã Base64 trên sẽ được decode thành binary data và hiển thị như là một ảnh png. Mặc dù dung lượng đoạn mã Base64 lớn hơn size gốc 4/3 lần, gây rối source code và không thể cache, nhiều người vẫn dùng chúng thay thế cho những link ảnh trong các file HTML, CSS.

Lý do là vì chỉ với một lần load file HTML, CSS, tất cả ảnh đã được nhúng luôn trong code, không cần gửi request và pull về từng bức như trước. Vì số lượng request giảm đi, việc đỡ phải khởi tạo, quản lý, đỡ một đống HTTP Header phải đính thêm vào mỗi request giảm gánh cho browser và server khá nhiều, đặc biệt với những trang có nhiều static assets cần load.

II. Ascii85

Base64 chuyển đổi 3 byte thành 4 ký tự, để lưu trữ 4 ký tự này trong hệ thống 8 bit, chúng tiêu tốn của ta 4 byte, kích cỡ sau mã hoá là 4/3 dữ liệu gốc, tức tăng cỡ 1/3. Một đại diện khác trong số các binary-to-text encoding có lối sống tiết kiệm hơn, Ascii85, đôi khi được gọi là Base85, chỉ sử dụng 5 ký tự để biểu diễn 4 byte, size của encoded data chỉ tăng 1/4 so với ban đầu.

Ý tưởng khởi đầu của chúng ta (Thật ra là của Paul E. Rutter) là xây dựng một thuật toán chuyển đổi 4 byte thành 5 ký tự bằng cách chuyển đổi 32 bit nhị phân, có khả năng biểu diễn 232 = 4,294,967,296 giá trị khác nhau, sang một số có 5 chữ số của một hệ cơ số khác.

845 = 4,182,119,424 <  232 = 4,294,967,296 < 855 = 4,437,053,125

Dễ thấy để biểu diễn được toàn bộ 4 byte, tức biểu diễn tối thiểu 232 = 4,294,967,296 giá trị khác nhau bằng 5 ký tự, 85 là cơ số nhỏ nhất mà ta có thể lựa chọn, khi mà nó có thể biểu diễn 855 = 4,437,053,125 giá trị khả dụng.

Cùng nhảy vào một ví dụ lại từ Wikipedia nữa cho dễ thấm:

Screen Shot 2016-10-18 at 11.50.02 AM

Nếu đã quen với việc chuyển đổi cơ số, ví dụ trên khá là dễ hiểu. Việc ta vừa làm ở đây là biểu diễn các ký tự 8 bit dưới dạng nhị phân, rồi chuyển đổi 32 bit nhị phân ấy sang hệ đếm cơ số 85 thông qua trung gian là cơ số 10. Những số Base85 thu được lần lượt là 24, 73, 80, 78 và 61. Như đã làm với Base64, việc cần làm bây giờ là dùng những số này làm index, tra trong bảng mã của Ascii85 để tìm ra ký tự tương ứng. Với Ascii85, bảng mã được sử dụng ở đây là bảng mã ASCII tiêu chuẩn (chắc đây là lý do mà tên của nó là Ascii85 encoding), ta sử dụng 85 ký tự printable trong bảng mã ASCII từ vị trí thứ 33 (!) đến vị trí 117 (u). Lý do ta thấy ảnh trên +33 vào Base85 là vì vậy.

Tiếp tục là một tiết mục quen thuộc. Tương tự như với Base64, nếu số byte đầu vào của Ascii85 không chia hết cho 4 thì sao? Lại sử dụng zero byte làm padding thôi:

Screen Shot 2016-10-18 at 11.50.58 AM

Sau khi hoàn thành mã hoá, 3 ký tự padding YkO sẽ được loại ra khỏi output. Việc decode được thực hiện bằng cách thêm các ký tự u – ký tự lớn nhất Ascii85 có thể biểu diễn – vào dữ liệu cần decode:

Screen Shot 2016-10-18 at 11.51.09 AM

Không như Base64, padding trong Ascii85 là bắt buộc. Việc encode với giá trị thấp (zero byte) và decode với giá trị cao (u) giúp cho các bit có bậc cao được bảo toàn.

Để giảm thiểu dung lượng đi nữa, nhận ra việc các block toàn zero data xuất hiện khá thường xuyên, Ascii85 thực hiện thêm một bước replace block !!!!! ở output với ký tự z.

Dễ dàng nhận ra mặc dù Ascii85 cho output size nhỏ hơn, nhưng với thuật toán phức tạp hơn (Trên Codewars, bài implement Ascii85 Encoder – Decoder được xếp hạng 2 kyu trong khi Base64 chỉ là 3 kyu, nếu bạn nào có tham gia Codewars và chưa lên 1 kyu thì có thể thử kiếm điểm với 2 bài này khá dễ), tốc độ encode và decode sẽ bị hạn chế hơn Base64. Vì lý do đó, trong khi Base64 phủ sóng mạnh do tính đơn giản, Ascii85 ngày nay chỉ chủ yếu được ứng dụng làm filter trong PostScript và file PDF của Adobe.

Về cái tên Base85, tên này thường được dùng để chỉ version RFC 1924 của Ascii85, được giới thiệu như là  "A Compact Representation of IPv6 Addresses".

Dành cho những bạn nào chưa nhận ra, thuật toán Base64 thực chất cũng là việc chuyển đổi từng nhóm 3 byte từ hệ nhị phân sang hệ cơ số 64. May mắn thay 64 là luỹ thừa của 2 (64 = 26), việc chuyển đổi chỉ đơn giản là nhóm lại các bit theo 6-tuple . Một phương pháp khác trong họ binary-to-text encoding, Base16 có một tên gọi khác quen thuộc hơn là hexadecimal. Nó chuyển đổi dữ liệu gốc sang hệ cơ số 16 với bảng mã là các ký tự từ 0-9A-F.

III. Chốt

Hy vọng những gì vừa mình chia sẻ về Encoding có thể giúp ích gì cho các bạn chưa biết (chứ với bản thân mình thì mình chẳng thấy nó giúp được gì ngoài vài point trên Codewars). Nếu thấy chủ đề này thú vị và có hứng thú với họ hàng của nó là Encryption, xin hãy subscribe và trông chờ bài viết tiếp theo của mình, mặc dù sự trông chờ ấy có thể là vô vọng vì mình chưa có kế hoạch gì cho chủ đề tới cả.

Bài viết được hoàn thành với sự trợ giúp của Wikipedia và kiến thức bản thân, xin được miễn trừ trách nhiệm cá nhân nếu những sai sót trong bài gây ra hậu quả nghiêm trọng nào đó cho bản thân người đọc.