Mã hóa Stream Cipher

Mã hóa Stream Cipher

Rate this post

Là một nhánh của mật mã khoá bí mật khi mà khoá mật mã và văn bản nguồn được coi như là những dòng bit được XOR tuần tự với nhau. Ở đây cũng khảo sát hai đại diện tiêu biểu là máy tạo dòng khoá tuyến tính và máy chạy và dừng luân phiên.

Các bài viết liên quan:

Stream cipher là gì?

Mật mã dòng (Stream cipher) thuộc mật mã khoá bí mật, đối xứng. Ý tưởng của thuật toán mã hoá theo dòng là bản nguồn sẽ được phân rã thành các bit; từng bit này sẽ được mã hoá bằng mỗi bit khoá để cho kết quả là một bit mã. Việc mã hoá bit được thực hiện bằng hàm logic XOR. Hàm XOR có bản chân trị như sau:

ABC = A XOR B
000
011
101
110

Cũng có thể coi C là kết quả của phép cộng theo modulo 2 các giá trị A và B:

  • C = (A + B) mod 2. Quá trình mã hoá và giải mã được thể hiện với sơ đồ như sau:
Mã hóa Stream Cipher

Trong đó pi là các bit nguồn, zi là các bit khoá và ci là các bit mã.

Có thể thấy quá trình mã hoá và giải mã là hoàn toàn giống nhau. Thật vậy, quá trình mã hoá là: c = (p + z) mod 2.

Do đó: (c + z) mod 2 = (p + z +z) = (p + (z + z)) = (p + 0) = p (hai bit giống nhau khi cộng với nhau theo mod 2 sẽ cho kết quả 0).

Để cho thuận tiện, từ nay đến cuối nếu không có giải thích khác đi thì ta sẽ hiểu phép “+” chính là phép cộng theo modulo 2.

Như vậy quá trình mã hoá của mật mã dòng hết sức đơn giản. Bên cạnh đó, dòng khoá có độ dài bằng dòng bit nguồn. Do đó, dòng khoá phải được sinh ra bởi một máy tạo dòng từ một từ khoá ngắn ban đầu. Và máy tạo dòng sẽ quyết định đến độ an toàn của toàn bộ thuật toán mã hoá.

Stream key(dòng khóa)

Dòng khóa mã hoá {zi} sẽ được sinh ra từ một khóa ban đầu K . Cần phải tạo dòng khóa {zi} sao cho các bit của chúng không phụ thuộc lẫn nhau để tránh kẻ thám mã phát hiện ra quy luật. Nói cách khác, các zi phải được tạo ra một cách hoàn toàn ngẫu nhiên. Sơ đồ quá trình tạo khoá và mã hoá có dạng như sau:

Mã hóa Stream Cipher

Quy trình tạo khoá, trên thực tế, có thể độc lập hoặc phụ thuộc vào kết quả mã hoá. Ở đây chúng ta sẽ xem xét một số đại diện các máy tạo khoá độc lập với quá trình mã hoá.

Thuật toán A5(tạo khóa tuyến tính)

Máy tạo dòng khóa tuyến tính (Linear Feedback Shift Registers) – LFSR-3 có sơ đồ như sau:

Mã hóa Stream Cipher

Cấu tạo và nguyên tắc hoạt động: Máy gồm ba hộp K0, K1, K2, được kết nối với nhau như trên. Tại mỗi thời điểm, trong mỗi hộp có một bit.

Khởi tạo:

Có ba bit z0, z1, z2 trong các hộp tương ứng. Máy hoạt động theo từng xung (clock). Tại mỗi xung, các bit sẽ dịch chuyển sang hộp bên phải.

Bít ở hộp K0 sẽ xuất ra ngoài; bit ở hộp K1 sẽ chuyển sang hộp K0; bit ở hộp K2 sẽ chuyển sang hộp K1. Các bit ở hộp K0 và K1, theo sơ đồ, sẽ XOR với nhau và ghi kết quả vào hộp K2. Quá trình này cứ chạy liên tục và ta sẽ nhận được dòng bit đầu ra {zi} để dùng làm khoá mã hoá.

Yêu cầu của dòng khoá mã hoá {zi} là các bit của chúng phải thật  ngẫu nhiên với nhau. Nhưng trên thực tế, điều đó khó có thể thực hiện. Ta sẽ khảo sát ví dụ của máy LFSR-3 trên. Với đầu vào là các bit z0 = 1, z1 = 0, z2 = 0, kết quả chạy của máy sẽ có dạng như sau:

K 2K 1K 0
001
100
010
101
110
111
011
001

Dòng bit khoá thu được là: 1001011100101

Nếu ta gọi mỗi dòng của bảng là một trạng thái của máy thì tổng số trạng thái khác nhau có thể có là 23 = 8.

Do đó, các trạng thái này sẽ lặp lại sau không quá 8 lần thực hiện (8 xung). Hơn nữa, việc chuyển từ một trạng thái này sang trạng thái khác là hoàn toàn xác định, vì vậy dòng bit khoá sẽ lặp lại.

Trong trường hợp cụ thể trên thì dòng bit khoá sẽ có dạng: (1001011). Số phần tử của dòng bit là 7 và được gọi là chu kỳ. Ta có thể thấy là chu kỳ này luôn không lớn hơn 8. Từ đó có thể nhận xét, nếu muốn các bit của dòng khoá càng ngẫu nhiên thì chu kỳ càng cần phải lớn, tương ứng với số hộp càng phải nhiều.

Máy LFSR-3 này có thể biểu diễn như sau:

[3, 1 + x + x3, (z0, z1, z2) = (1, 0, 0)]. Trong đó số 3 là số hộp chứa các bit, biểu thức 1 + x + x3 là cấu trúc của máy và (z0, z1, z2) = (1, 0, 0) là giá trị các bit ban đầu. Biểu diễn ngắn gọn hơn: [3, 1 + x + x3, (1, 0, 0)].

Đối với dòng khoá sinh ra là {zi} thì zi+3 = (zi+1 + zi) mod 2, với i = 0, 1, 2,….

Máy tổng quát LFSR-m có công thức: [m, C0 + C1x +…+ Cm-1xm-1 + xm, (z0, z1,…, zm-1)] và được biểu diễn trực quan như sau:

Mã hóa Stream Cipher
  • Với z0, z1,…, zm-1 là các giá trị khởi tạo ban đầu;
  • C0, C1,…, Cm-1 Î {0,1} là các hệ số phản hồi;
  • Nếu hệ số Ci = 0 thì mạch mở, ngược lại Ci = 1 thì mạch đóng;
  • Công thức tính bit: zi+m =  với i = 0, 1, 2,…

Máy chạy và dừng luân phiên

Để nâng cao độ an toàn của máy tạo dòng khoá, người ta kết hợp ba máy tạo dòng khoá tuyến tính, tạo thành một máy chạy và dừng luân phiên (Anternating stop-and-go generator):

Mã hóa Stream Cipher

Máy chạy và dừng luân phiên G được cấu trúc từ 3 máy tạo dòng tuyến tính A, B và C.

Các máy A, B, C tạo ra các dòng bit riêng rẽ, không phụ thuộc vào nhau. Hoạt động của máy G dựa trên xung (clock).

Theo sơ đồ, nếu trong một xung nào đó máy A xuất ra bit 1 thì máy B sẽ làm việc và sinh ra bit mới còn máy C không sinh bit.

Bit mới của máy B sẽ XOR với  bit cũ của máy C để có bit kết quả xuất ra ngoài. Trường hợp ngược lại, trong một xung mà máy A xuất ra bit 0 thì bit cũ của máy B sẽ XOR với bit mới của máy C để tạo thành bit của luồng khoá.

Như vậy, máy A có chức năng điều khiển hoạt động của các máy B và C. Còn các bit kết quả sẽ do các bit của máy B và C XOR lại với nhau mà tạo thành.

Giả sử đầu ra của các máy tương ứng là A: {a0, a1,…}; B: {b0, b1,…} và C: {c0, c1,…}; dòng khóa nhận được là Z: {z0, z1,…}. Đặt b-1 = c-1 = 0 và giả sử dòng bit máy A có giá trị: {100100110} thì các bit của dòng khoá Z sẽ được tính như trong hình sau:

AKhở i taọ100100110
B(1)b-1b0  b1  b2b3 
C(0)c-1 c0c1 c2c3  c4
Z z0z1z2z3z4z5z6z7z8

Ở đây, z0 = b0 + c-1, z1 = b0 + c0,…

Đặt t(n) =  . Ta thấy t(n) chính là số bit 1 trong dãy {a0, a1,…an} đó cũng đồng thời là số lần máy B chạy; do đó, tại xung thứ n + 1, máy B sẽ xuất ra bit bt(n)-1.

Tương tự, n + 1 – t(n) chính là số bit 0 trong dãy trên; do đó, tại xung thứ n + 1, máy C sẽ xuất ra bit cn-t(n).

Như vậy, ta có công thức tính bit thứ n + 1 của dòng khoá: zn = bt(n)-1 + cn t(n).

Tóm lại: zn = bt(n)-1 + cn – t(n) với t(n) = .

Thuật toán RC4(Rivest Cipher 4)

Trong mật mã học, RC4 (Rivest Cipher 4 còn được gọi là ARC4 hoặc ARCFOUR) là một mật mã dòng. Ưu điểm của RC4 chính là đơn giản, dễ hiện thực trong phần mềm, tốc độ mã hóa cao. Tuy nhiên RC4 ngày nay được coi là hệ mã có nhiều lỗ hổng và không an toàn. Trong ngày nay RC4 không còn được an toàn và vào năm 2015 một số cơ quan về mật mã đã khuyến cáo RC4 có thể bị tấn công trong giao thức TLS, IETF đã xuất bản RFC 7465 để cấm sử dụng RC4 trong TLS, Microsoft và Molliza cũng đã đưa ra những khuyến cáo tương tự về RC4

RC4 là stream cipher với độ dài key không cố định (tùy người dùng) với đơn vị thao tác trên byte(8bit). Dựa trên thuật toán hoán vị ngẫu nhiên với chu kỳ lặp lại của mã lên đến , mỗi byte của dữ liệu sẽ được thao tác từ 8 đến 16 toán tử để ra thành chuỗi mã hóa cho nên thời gian vận hành nhanh, dễ thực hiện trong các phần mềm.

Mã hóa Stream Cipher

Để hiểu được thuật toán RC4 ta tìm hiểu các giai đoạn thực hiện của thuật toán RC4 gồm 3 giai đoạn chính là giai đoạn khởi tạo, giai đoạn hoán vị Key-scheduling Algorithm(KSA), và giai đoạn Pseudo-Random Generation Algorithm(PRGA)

Giai đoạn khởi tao S(Inittial Vector-IV) mọi phần tử của S(256 bytes) sẽ được gán giá trị mặc định tăng dần từ 0 đến 255.

Ví dụ: S[0] = 0; S[1] = 1; S[2] = 2,…S[256] = 255

Bên cạnh đó ở giai đoạn này T cũng được tạo ra từ khóa bí mật với cách thức tạo khóa như sau:

  • Nếu khóa bí mật có độ lớn là 256 bytes thì T là khóa bí mật
  • Nếu khóa bí mật có độ lớn nhỏ hơn 256 bytes thì khóa bí mật sẽ viết liền lặp lại cho đến khi đủ 256 bytes.

Giai đoạn KSA Vector S và vector T sau khi được khởi tạo được đưa vào hàm hoán vị KSA với hàm KSA được định nghĩa như sau:

Tiến hành lặp với mỗi giá trị i có giá trị từ 0 à 255

Mỗi vòng lặp thực hiện 2 bước sau:

  • Bước 1: gán j = ( j+ S[i] + T[j] ) mod 256
  • Bước 2: tiến hành hoán vị S[i] và S[j]

Sau khi vector S hoán vị xong sẽ tiếp tục được đưa vào giai đoạn hoán vị PRGA để phát sinh thành dòng key với kích thước bất kỳ. Với hàm PRGA được định nghĩa như sau:

Tiến hành lặp cho đến khi dừng sinh key

Mỗi vòng lặp thực hiện các bước sau:

  • Gán i = ( i +1) mod 256
  • Gán j = ( j + S[i] ) mod 256
  • Hoán vị giá trị S[i] và S[j]
  • Gán giá trị t = ( S[i] + S[j] ) mod 256
  • Xuất ra giá trị k = S[t]
  • Tiếp tục vòng lặp cho đến khi dừng sinh key

Mỗi khóa k được XOR với byte tiếp theo của plaintext để tạo thành ciphertext (để giải mật mã ta XOR byte tiếp theo của cipher text với khóa k)

Sự an toàn của hệ mã RC4 phụ thuộc vào sự an toàn của 2 giai đoạn KSA và PRGA. Rất nhiều nghiên cứu để làm cho thuật toán RC4 an toàn hơn và có khả năng chống lại các cuộc tấn công.

Tuy nhiên đến ngày nay thuật toán RC4 được khuyến cáo không nên sử dụng vì rất nhiều các lỗ hổng được tìm thấy ở trong hai giai đoạn KSA và PRGA.

Như đề cập ở trên thuật toán RC4 ngày nay không còn bảo mật và các byte đầu tiên tiết lộ thông tin về khóa. Điều này có thể được cải thiện bằng loại bỏ một số byte ban đầu của key stream. Một số thuật toán sinh ra để cải thiện RC4 như Spritz, RC4A, VMPC, RC4 +,…

One-time pad(OTP)

Các One-time pad (OTP) là một mật mã không thể phá vỡ về mặt lý thuyết. Tuy nhiên, trong thực tế, đây là mật mã khó có khả năng sử dụng được vì nó yêu cầu khóa bí mật chia sẻ trước ít nhất có cùng độ dài với tin nhắn. Tạo các khóa thực sự ngẫu nhiên và chia sẻ khóa bí mật một cách an toàn là vấn đề khó trong thực tế.

Thuật toán One-time pad(OTP) là một mật mã Vigenère thõa mãn các điều kiện sau:

  • Khóa bí mật có độ lớn bằng đúng độ lớn của dữ liệu khóa
  • Khóa bí mật được tạo một cách ngẫu nhiên thật sự
  • Khóa chỉ sử dụng một lần và không sử dụng cho lần mã hóa khác
  • Khóa bí mật phải được giữ bí mật

OTP được đưa ra lần đầu vào năm 1982 bởi Frank Miller và sau đó được phát minh lại vào năm 1917 dựa trên mô hình mã hóa Vigenère sử dụng phép cộng modulo.

Năm 1919 một phiên bản khác của OTP mã hóa Vernam được phát minh bởi Gilbert S Vernam và sử dụng phép toán XOR thay vì cộng modulo như thuật toán Vigenère

Leave a Reply