Messages posted by: alice

Hơn 1 năm rồi mới quay lại chủ đề cũ này. Bây giờ alice mới tìm được 1 cái đáng nói đây.

Giả sử a là một từ w bit, ta ký hiệu

¬a = a ^ 2↑(w-1)

Để ý rằng ¬a = a + 2↑(w-1) = a - 2↑(w-1).

Giả sử (a1, a2,...) là chuỗi nhiều từ w bit, ta ký hiệu

¬(a1, a2,...) = (¬a1, ¬a2,...)

Thuật toán mật mã hoá có một nhược điểm đáng lo ngại là

ENCRYPT(X, Z, T, U) = ENCRYPT(X, ¬Z, T, ¬U)

Việc fix nhược điểm trên là không dễ dàng.

Nhược điểm trên phát sinh từ thuật toán sinh chuỗi phần tử đơn vị u(0), u(1), u(2),...., u(63). Mọi u(k) được tính bằng một đa thức có dạng p(U) hoán vị trên vành số nguyên mod 2↑w. Có thể chứng minh rằng bất cứ đa thức p(U) nào hoán vị trên vành (khi được xem là một hàm) cũng đều có tính chất p(¬U) = ¬p(U). Tính chất này gây ra nhược điểm trên.

Bài phân tích của Ada ở trang web congdongcviet.com (phiên bản .PDF) có đưa ra vài lý do để khuyên rằng chuỗi phần tử đơn vị nên là một chuỗi số chẵn lẻ luân phiên, từ đó đưa ra 2 thuật toán để sinh chuỗi này. Cả 2 đều dựa trên các đa thức hoán vị trên vành. Cả 2 đều có nhược điểm trên.

Ngoài ra, dễ thấy rằng nếu gọi a' là nghịch đảo của a qua phép nhân "cải tiến" . hay (.) thì (¬a)' = ¬(a'). Do đó, thay thế 1 hay nhiều phép nhân "cải tiến" trong các hàm G bằng các phép chia "cải tiến" cũng không fix được nhược điểm trên.

Nhược điểm trên có thể đánh giá là nghiêm trọng như tính bù của mật mã DES, làm độ dài khoá hiệu dụng mất đi 1 bit.

Nếu được phân cấp bảo mật 10w bit thì có thể nói rằng, với nhược điểm trên, thuật toán mật mã hoá dựa trên phép nhân này đã bị bẻ gãy.

WinDak wrote:

"alice" wrote:

Theo alice biết, mọi tweak modes đều đòi hỏi tweak bí mật, còn tweakable ciphers thì có khi đòi hỏi có khi không. Tweak modes đòi hỏi tweak bí mật vì security proof cần giả thiết đó; nói đúng hơn thì xây dựng tweak công khai rất khó và tweak như thế rất phức tạp => kém hiệu quả

Mình có điều chưa hiểu chỗ này, alice nói tweak phải bí mật nhưng theo mình biết ít nhất ta cần T0 giống như IV là một phần của cipher text cho việc giải mã. Nếu không mỗi lần sử dụng T0 mới thì lại phải sử dụng trao đổi khoá để truyền T0 ? như vậy có phải là phản tác dụng của tweak hay các cipher mode ? same key nhưng kết quả khác nhau ?

Nếu nói tweak cần phải unpredictable, không đoán được dựa trên bất cứ kết quả nào sẽ hợp lí hơn ?

Ý WinDak hỏi là đối với mật mã alice đang đưa ra? Mật mã này gọi tham số T là tweak. Nhưng alice so sánh với cách dùng từ tweak phổ biến thì nghĩ rằng tweak là j (chỉ số block) có lẽ đúng hơn. j không cần phải unpredictable, và không thể unpredictable. Còn T thì nếu unpredictable thì tốt, nhưng nếu không thì alice cũng chưa thấy cách nào bẻ gãy được. Mật mã này tương tự như vài tweakable cipher khác, T được insert vào trong cipher theo một cách khá phức tạp, khác với tweak modes. Alice nghĩ rằng điều này là cần thiết bởi với một định nghĩa nhất định về unpredictablility thì T(j) vẫn là predictable ngay cả khi T(0) bí mật.

Về việc dùng lại khoá, theo spec đó, T(0) là một khoá và khi cần T(0) mới thì phải trao đổi khoá thôi. Điều này alice nghĩ cũng không phải là hạn chế gì ghê gớm. Thí dụ trong liên lạc, mỗi session mới đều nên đổi khoá mới, còn trong session thì không cần phải đổi khoá nào dù là T(0) bởi vì cứ mỗi j nó sẽ sinh ra một T(j) mới. Có thể sẽ tiện hơn nếu định dạng j gồm vài phần, j=(j1,j2,j3), trong đó j1 là session ID, j2 là packet ID, j3 là index của plain/cipher block trong packet. Khi đó không cần phải tốn thêm 4w bit để truyền j (vì j1, j2 được truyền trong overhead của protocol rồi, j3 thì người nhận đã biết). Và khi đó việc mất một số packet cũng không ngăn cản giải mã những packet nhận được tiếp theo.

Nếu T(0) công khai thì không cần phải trao đổi khoá mà có thể truyền bình thường cho người nhận. Nếu T(0) công khai (hoặc bị lộ), thú thực alice cũng chưa nhìn thấy cách nào có thể lợi dụng được nó để bẻ những khoá còn lại. Nhưng rõ ràng nếu T(0) công khai thì T(j) không còn unpredictable nữa theo bất cứ định nghĩa nào về "unpredictability". alice không phải là tác giả mật mã, cũng chưa tìm hiểu nó thấu đáo nên không thể nói gì hơn.

WinDak wrote:

"alice" wrote:

Bây giờ, trở lại vấn đề chính khiến alice quan tâm ở cipher này: cryptanalysis. Khảo sát sơ bộ 1 hàm G nhỏ (độ dài word =16 bit) cho thấy nó không giống như 1 random permutation. Cần khoảng 2 - 2.5 hàm G nối tiếp nhau mới đủ làm cho nó trở thành giống như random

Cái này mình thấy cũng chưa thể chứng minh được là yếu, vì ngay cả các block cipher mạnh nếu sử dụng ít vòng cũng không an toàn. Nhiều vòng yếu hợp lại vẫn có thể tạo thành cipher mạnh.

Nếu chỉ với kết quả trên thì đúng là chưa thể kết luận được gì. Nhưng WinDak đừng quên là cipher này có cấu trúc đồng nhất với Skipjack, chỉ khác hàm G. Impossible differential attack từ năm 1998 (đến nay vẫn là attack thành công nhất lên Skipjack) đã cho thấy Skipjack chỉ cần thiếu 1 vòng thôi là bị bẻ gãy. Theo đó alice suy luận rằng với hàm G như vậy, khả năng lớn là cipher này có độ bảo mật dưới 5w bit.

Chào các bạn. Cảm ơn mrro, StarGhost và WinDak đã tham gia thảo luận. Alice rất vui vì bài viết alice sưu tầm này được quan tâm. Nhưng thú thực là alice hơi ngạc nhiên vì các bạn thảo luận về mode of operation. Alice mong đợi những "mũi kiếm" phản biện chĩa vào hướng khác cơ -- hướng nào thì tạm gác lại để nói sau. Bây giờ là về vấn đề hiện đang được tranh luận, do mrro nêu ra đầu tiên:

Vì sao tweak lại không ngẫu nhiên, không thể đoán trước, như IV?
Vì sao tweak phải là bí mật mà không phải là công khai, như IV?
Tại sao mode lại gắn chặt với underlying cipher, mà không tổng quát để có thể áp dụng cho mọi cipher?

Về vấn đề này, thì alice lại nghĩ nó bình thường, không có gì đáng chú ý. Nhưng alice sẽ cố gắng nhìn theo con mắt của người quan tâm để giải thích, theo khả năng của alice.

1. Quá trình phát triển của tweakable block cipher có thể tạm chia thành 5 giai đoạn. Những năm 1950 là giai đoạn mã hoá bằng tay -- máy tính điện tử chưa có, hoặc có mà còn quá đắt, chỉ dùng cho cryptanalysis. Những năm 1960 là giai đoạn bắt đầu mã hoá bằng máy -- có block cipher chạy trên máy tính, chưa có ý niệm về mode. Những năm 1970, tạm gọi là giai đoạn GOST, block cipher đã hoàn thiện, modes được định nghĩa cho từng cipher và gắn chặt với cipher. Gamma mode của GOST là thí dụ. Những năm 1980, tạm gọi là giai đoạn DES, modes được thiết kế cho DES nhưng đem ra sử dụng cho cipher khác, tức là tách rời ra khỏi cipher. Những năm 1990, tạm gọi là giai đoạn tiền AES, bắt đầu những nghiên cứu để đưa spice, sau này gọi là tweak, vào mật mã dùng thay cho IV. Những năm 2000 trở lại đây, tạm gọi là thời kỳ hậu AES hay tiền SHA3, một mặt đúc kết các nghiên cứu dở dang của giai đoạn trước thành kết quả là một số tweak modes có tính chất tổng quát cho mọi cipher, mặt khác xây dựng các tweakable cipher, tức cipher chèn tweak vào theo một cách riêng -- tương tự như cách tiếp cận vấn đề của những năm 1970. LRW, XEX, XTS, Salsa / Cha Cha và Threefish / Skein là thí dụ.

2. Tweak giống như IV ở chỗ nó cũng là extra parameter. Tweak giống IV ở chỗ nó cũng nhắm tới các tiêu chí an toàn như là an toàn trước CPA (chosen plaintext attack) và trước CCA (chosen ciphertext attack). Các tiêu chí an toàn đối với tweakable cipher có thể với định nghĩa hơi khác hơn so với khi áp dụng lên IV-oriented modes nhưng về cơ bản là cũng thế. Tweak khác IV ở điểm là không đòi hỏi tính ngẫu nhiên. Tweak khác IV ở điểm là quá trình mã hoá nếu chỉ dùng tweak thì thôi thì hoàn toàn tất định. Và cuối cùng tweak còn khác IV ở chỗ là đòi hỏi tính bí mật trong một số trường hợp. Theo alice biết, mọi tweak modes đều đòi hỏi tweak bí mật, còn tweakable ciphers thì có khi đòi hỏi có khi không. Tweak modes đòi hỏi tweak bí mật vì security proof cần giả thiết đó; nói đúng hơn thì xây dựng tweak công khai rất khó và tweak như thế rất phức tạp => kém hiệu quả. Tweakable ciphers có khi đòi hỏi có khi không bởi vì không có security proof (đó là thường, có thì mới lạ). Người ta xây dựng tweakable ciphers bởi vì tweak modes trong nhiều ứng dụng là không đủ nhanh. Trong tweakable ciphers, tweak nhúng sâu vào cipher, gắn chặt vào cipher chứ không tổng quát bởi vì nếu tách rời ra thì không đủ mạnh.

3. Trong cryptanalysis thì khoá cũng là biến như plaintext và ciphertext, nghĩa là nó thay đổi. Nhiều phương pháp cryptanalysis có thể áp dụng cho cipher với khoá thay đổi. Những người thiết kế cipher rất chú trọng đến việc cipher của mình sẽ phản ứng như thế nào trước sự thay đổi của khoá. Cho nên tweak có hay không chỉ là hình thức mà thôi. Nếu cipher mạnh thì 1 khoá độc lập cũng là mạnh. Nếu nó yếu thì dù có 10 khoá độc lập cũng vẫn là yếu. Nên đối với cipher nhiều khoá thì thường là tất cả cùng đều sinh ra từ 1 khoá. NMAC / HMAC là thí dụ.

Bây giờ, trở lại vấn đề chính khiến alice quan tâm ở cipher này: cryptanalysis. Khảo sát sơ bộ 1 hàm G nhỏ (độ dài word =16 bit) cho thấy nó không giống như 1 random permutation. Cần khoảng 2 - 2.5 hàm G nối tiếp nhau mới đủ làm cho nó trở thành giống như random. Trong khi đó, đối với Skipjack cipher tiền thân của nó, hàm G ngoại trừ tính chất complementarity cố hữu ra thì rất giống 1 random permutation. Điều này khiến cho alice nghĩ rằng có thể bẻ gãy được, không nhiều thì ít.

Nhưng bẻ gãy cách nào thì mới phải bàn.

Mời các bạn tiếp tục thảo luận.

25. Lịch sử và tư liệu. Thuật toán này được phát triển bởi một nhóm tác giả người Việt sống ở nhiều nước trên thế giới, hiện đang trong quá trình công bố. Mình không phải là một tác giả, nhưng có giao tiếp thư từ với một tác giả nên được lí giải đôi điều về thiết kế. Nhờ những thông tin đó mà có bài viết này.

Nhằm tạo dễ dàng cho việc sử dụng rộng rãi, thuật toán không được đăng kí sáng chế, nghĩa là không được xem là thuộc sở hữu trí tuệ của cá nhân nào mà được xem là thuộc tri thức chung (public domain).

Việc sử dụng thuần túy các phép toán đại số không tương thích với nhau (phép nhân, phép cộng và phép xor) để xây dựng thuật toán mã hóa là một í tưởng được thực thi đầu tiên ở thuật toán IDEA, do Xuejia Lai (Trung Quốc) và James L. Massey (Mĩ / Thụy Sĩ) sáng chế và giới thiệu năm 1991. IDEA dùng nhóm nhân modulo 2↑w + 1, một nhóm có đúng 2↑w phần tử khi và chỉ khi 2↑w + 1 là một số nguyên tố. 2↑16 + 1 là một số nguyên tố, nhưng 2↑32 + 1 hay 2↑64 + 1 thì không. Điều đó đã giới hạn phạm vi ứng dụng cho IDEA ở những bộ vi xử lí 16 bit.

Tính không thể biểu diễn được bằng đa thức trên vành số nguyên modulo 2↑w (w > 3) của phép xor được Otokar Grosek (Slovakia), Mirka Miller (Slovakia/Úc) và Joe Ryan (Úc) chứng minh năm 2004.

Tính biểu diễn được của mọi hàm nhờ một bộ hàm cơ sở gồm có phép cộng, phép quay đi 1 bit và hằng số 1 đã được Dmitry Khovratovich (Nga/Luxembourg) và Ivica Nikolic (Serbia/Luxembourg) chứng minh năm 2009.

Tính chất nhóm của phép nhân cải tiến định nghĩa bởi a . b = ((2a+1)(2b+1) - 1)/2 = 2*a*b + a + b được các tác giả phát hiện ra một cách độc lập với nhau (nhưng không công bố) trong khoảng thời gian từ năm 1990 đến 1994. Tính chất này cũng được phát hiện ra một cách độc lập bởi John H. Meyers và công bố trên Usenet năm 1997.

Tiêu chuẩn cần và đủ cho tính hoán vị của các đa thức trên vành số nguyên mod 2↑w, bao gồm cả đa thức 2*a*b + (1 - 2*e)*(a - b + e) dùng trong thuật toán này, được Ronald L. Rivest (Mĩ) chứng minh và phát biểu năm 1999. Thuật toán RC6, do Rivest và các đồng nghiệp sáng chế và giới thiệu cùng năm đó, đã dùng một đa thức bậc 2 có dạng tương tự: (1+2*e)*e.

Việc "nắn" mật mã cụm bằng một tham số dễ dàng thay đổi, thường thay đổi theo số thứ tự cụm, và cũng thường lệ thuộc vào một khóa, được triển khai lần đầu tiên ở chế độ vận hành LRW do 3 người Mĩ Moses Liskov, Ronald L. Rivest và David Wagner sáng chế và công bố vào năm 2002.

Việc tăng cường tính bảo mật bằng một (hay vài) khóa phụ, có thể có giá trị sử dụng lâu dài hơn khóa chính, đã được thực thi từ nhiều thập kỉ ở nhiều mật mã quốc gia. Thuật toán GOST 28147 của Liên Xô cũ (và Nga bây giờ), được sáng chế vào khoảng năm 1970 và công bố vào năm 1994, ngoài khóa chính 256 bit còn khuyến cáo giữ bí mật 8 bảng thế song ánh trên 4 bit, tức là tương đương với 1 khóa phụ có độ dài 8*log2((2↑4)!) ≈ 354 bit.

Lưu đồ dữ liệu mã hóa cụm văn bản 4 từ bằng khóa 5 từ thuộc về thuật toán Skipjack, do cơ quan NSA (Mĩ) sáng chế trong khoảng thời gian từ năm 1987 đến năm 1993 và công bố vào năm 1998. Skipjack dùng một bảng thế 8 bit thành 8 bit áp dụng trên nửa từ và do đó, cũng chỉ hiệu quả ở các bộ vi xử lí 8 bit và 16 bit.

Thuật toán giới thiệu ở đây có thể thực hiện hiệu quả trên mọi bộ vi xử lí w bit, với w chẵn, chẳng hạn, 8 bit, 16 bit, 32 bit và 64 bit; w càng lớn thì mã hóa càng nhanh và độ bảo mật cũng càng cao.

Khả năng bảo mật của thuật toán này dựa trên khóa Z, còn các khóa T(0) và U chỉ nên được xem là củng cố tính bảo mật. (Nhắc lại rằng T(0) có được dùng hay không còn tùy theo chế độ vận hành.) Vì lẽ đó, các tác giả phân loại thuật toán ở độ bảo mật 5w bit, hơn là 10w bit. Điều này hẳn nhiên ảnh hưởng đến việc lựa chọn tham số trao đổi khóa (key exchange) và dẫn xuất khóa (key derivation). Ví dụ, để trao đổi khóa bằng phương pháp Diffie-Hellman trên nhóm các điểm của một đường cong elliptic xác định trên một trường số nguyên modulo p (p nguyên tố) thì nên chọn đường cong với số điểm là một số 10w bit. Khi dẫn xuất các khóa, nên chọn 5w bit ngẫu nhiên làm khóa Z, rồi từ Z dẫn xuất T(0) và U bằng một hàm băm mật mã (cryptographic hash function) có 10w bit trạng thái bên trong.

---HẾT---

24. Vấn đề thực thi cuối cùng mà mình đề cập là phép tính nghịch đảo theo phép nhân modulo 2↑w (modular multiplicative inverse) cần thiết để giải mã. Phép tính này có thời gian tính toán không phải là O(1) mà là O(w) nên mặc dù trong lí thuyết, phép tính này là dễ dàng nhưng trong thực hành thì vẫn còn được xem là phức tạp. Vì thế, khi lập trình, phép tính này không bao giờ được đưa vào hàm giải mã mà luôn luôn được đưa vào hàm bung khóa, nghĩa là các giá trị nghịch đảo để giải mã luôn luôn được tính sẵn.

Có hai cách tính.

Cách thứ nhất là dùng định lí Euler, là định lí nói rằng với mọi n nguyên dương và mọi a nguyên tố cùng nhau với n,

[indent]a↑φ(n) = 1 (mod n)[/indent]

trong đó φ(n) là số các số tự nhiên không lớn hơn n nguyên tố cùng nhau với n. Từ đó suy ra nghịch đảo của a là

[indent]1/a = a↑(φ(n)-1) (mod n)[/indent]

Trong thuật toán mật mã này, n = 2↑w, do vậy tập các số nguyên tố cùng nhau với n chính là tập các số tự nhiên lẻ, ta có

[indent]1/a = a↑(2↑(w-1)-1) (mod 2↑w)[/indent]

Chẳng hạn, với các từ 8 bit (w=8) thì 1/a = a↑127 = a * a * a * ... * a (mod 256), với 126 phép nhân (của ngôn ngữ C trên kiểu unsigned char). Nhưng tất nhiên, khi lập trình, ta không làm nhiều phép nhân như thế, mà chỉ dùng 6 phép bình phương và 6 phép nhân thôi:

[indent]a↑127 = a↑126 * a
= (a↑63)↑2 * a
= ((a↑31)↑2 * a)↑2 *a
= (((a↑15)↑2 *a)↑2 *a)↑2 *a
= ((((a↑7)↑2 *a)↑2 *a)↑2 *a)↑2 *a
= (((((a↑3)↑2 *a)↑2 *a)↑2 *a)↑2 *a)↑2 *a
= (((((a↑2 *a)↑2 *a)↑2 *a)↑2 *a)↑2 *a)↑2 *a[/indent]

Mình cẩn thận nêu mã nguồn tính nghịch đảo của một từ 32 bit và, nhắc lại một lần nữa, từ ấy phải là một số lẻ.

Code:

word inverse(word a)
{
word b = a;
for(int w=30; w; w--)
{
b *= b;
b *= a;
}
return b;
}

Cách thứ hai là dùng thuật toán Euclid mở rộng, tức là thuật toán không những tính được ước chung lớn nhất (UCLN) của a và b mà còn tính được một nghiệm nguyên của phương trình

[indent]ax + by = UCLN(a,b)[/indent]

Áp dụng vào thuật toán mật mã này, a là số (lẻ) cần nghịch đảo, b = 2↑w, (vậy UCLN(a,b) = 1), ẩn số x là nghịch đảo của a trong phép nhân modulo b, còn ẩn số y là nghịch đảo của b qua phép nhân modulo a.

Các chi tiết của phương pháp này có thể được tìm thấy trong sách giáo khoa số học phổ thông.

Cách thứ hai thường nhanh hơn cách thứ nhất. Nhưng cách thứ nhất có thời gian tính toán hằng (nó luôn mất w-2 phép bình phương và w-2 phép nhân) còn cách thứ hai có thời gian tính toán lệ thuộc vào giá trị của a, nên xét về bảo mật thì cách thứ nhất an toàn hơn.

Trong ngữ cảnh của thuật toán mã hóa này, phép nghịch đảo chỉ được dùng khi bung khóa để giải mã, một việc chỉ tốn rất ít thời gian so với bản thân việc giải mã một bản mã gồm nhiều cụm. Khi dùng cách thứ hai, thời gian thực hiện từng bước của phép nghịch đảo cũng chỉ tiết lộ một ít thông tin về khóa mà thôi. Do vậy mà trên cả hai phương diện hiệu quả và bảo mật, lựa chọn cách nào là không quan trọng lắm.

23. Còn đây là chương trình thử, dùng để kiểm nghiệm rằng cài đặt đã tối ưu hóa:

-- mã hóa chính xác, nghĩa là expandkey và crypt cho kết quả y hệt như hàm mã hóa chuẩn mực (encrypt), và

-- giải mã chính xác, nghĩa là expandkey, invertkey và icrypt khôi phục lại cụm rõ đã được mã hóa bởi expandkey và crypt.

Chương trình thử cũng minh họa cách dùng các hàm để mã hóa và giải mã 1 cụm.

Code:

void test()
{
int const nTimes = 100;
int const nRep = 100;
word X[4], Y[4], T[4], Z[5], M[64], N[64], iM[64], iN[64];
for(int i=0; i<5; i++)
Z[i] = random_word();
for(int i=0; i<4; i++)
T[i] = random_word();
word U = random_word();
// correctness of the optimized implementation
expandkey( M, N, Z, U );
for(int n=nTimes; n; n--)
{
for(int i=0; i<4; i++)
X[i] = random_word();
memcpy( Y, X, sizeof(X) );
for(int m=nRep; m; m--)
{
encrypt ( X, X, Z, T, U );
crypt ( Y, Y, T, M, N );
}
if( memcmp(Y,X,sizeof(X)) !=0 )
cout << "crypt: mã hóa sai!" << endl;
}
// invertibility of the optimized implementation
invertkey( iM, iN, M, N );
for(int n=nTimes; n; n--)
{
for(int i=0; i<4; i++)
X[i] = random_word();
memcpy( Y, X, sizeof(X) );
for(int m=nRep; m; m--)
{
crypt( Y, Y, T, M, N );
}
for(int m=nRep; m; m--)
{
icrypt( Y, Y, T, iM,iN );
}
if( memcmp(Y, X, sizeof(X)) !=0 )
cout << "icrypt không phải là hàm ngược của crypt!" << endl;
}
}

22. Dưới đây là hàm sinh thời biểu khóa giải mã và hàm giải mã.

Code:

void invertkey( word iM[64], word iN[64], word const M[64], word const N[64] )
{
// M, N, iM, iN must not overlap!
for(int k=0; k < 64; k++)
{
iM[k] = inverse( M[63-k] );
iN[k] = - N[63-k] * iM[k];
}
}
void icrypt( word X[4], word const Y[4], word const T[4], word const iM[64], word const iN[64] )
{
word Xrs[4], Trs[4];
Trs[0] = _rotl(T[3],16);
Trs[1] = _rotl(T[2],16);
Trs[2] = _rotl(T[1],16);
Trs[3] = _rotl(T[0],16);
Xrs[0] = _rotl(Y[3],16);
Xrs[1] = _rotl(Y[2],16);
Xrs[2] = _rotl(Y[1],16);
Xrs[3] = _rotl(Y[0],16);
crypt( Xrs, Xrs, Trs, iM, iN );
X[0] = _rotl(Xrs[3],16);
X[1] = _rotl(Xrs[2],16);
X[2] = _rotl(Xrs[1],16);
X[3] = _rotl(Xrs[0],16);
}

21. Ta kết hợp lại tất cả các kĩ thuật tối ưu hóa đã nêu bằng một mã nguồn C++ mới, viết cho trường hợp độ dài từ 32 bit.

Code:

void expandkey (word M[64], word N[64], word const Z[5], word U)
{
word z0=Z[0], z1=Z[1], z2=Z[2], z3=Z[3], z4=Z[4];
word u = U;
for( int k=0; k<64; k++ )
{
M[k] = 2*(z3 - u) + 1;
N[k] = (2*u - 1)*(z3 - u);
u += 2*U + 1;
word z=z0; z0=z1; z1=z2; z2=z3; z3=z4; z4=z;
}
}
static inline word G (word x, word t, word m0, word m1, word n0, word n1)
{
x *= m0;
x += n0;
x = _rotl(x,16);
x ^= t;
x *= m1;
x += n1;
x = _rotl(x,16);
return x;
}
void crypt(word Y[4], word const X[4], word const T[4], word const M[64], word const N[64])
{
// Step 1
word const g0 = G( X[0], T[0], M[0], M[1], N[0], N[1] );
// Step 2
word const g1 = G( X[1]^g0, T[1], M[2], M[3], N[2], N[3] );
// Step 3
word const g2 = G( X[2]^g1, T[2], M[4], M[5], N[4], N[5] );
// Step 4
word const g3 = G( X[3]^g2, T[3], M[6], M[7], N[6], N[7] );
// Step 5
word const g4 = G( g0^g3, T[0], M[8], M[9], N[8], N[9] );
// Step 6
word const g5 = G( g1^g4, T[1], M[10],M[11],N[10],N[11] );
word const g11= G( g4, T[3], M[22],M[23],N[22],N[23] );
// Step 7
word const g6 = G( g2^g5, T[2], M[12],M[13],N[12],N[13] );
word const g9 = G( g5, T[1], M[18],M[19],N[18],N[19] );
// Step 8
word const g7 = G( g3^g6, T[3], M[14],M[15],N[14],N[15] );
word const g10= G( g6, T[2], M[20],M[21],N[20],N[21] );
word const g13= G( g6^g9, T[1], M[26],M[27],N[26],N[27] );
// Step 9
word const g8 = G( g4^g7, T[0], M[16],M[17],N[16],N[17] );
word const g14= G( g4^g10, T[2], M[28],M[29],N[28],N[29] );
// Step 10
word const g12= G( g5^g8, T[0], M[24],M[25],N[24],N[25] );
word const g15= G( g5^g8^g11, T[3], M[30],M[31],N[30],N[31] );
// Step 11
word const g16= G( g6^g9^g12, T[0], M[32],M[33],N[32],N[33] );
// Step 12
word const g17= G( g4^g10^g13^g16, T[1], M[34],M[35],N[34],N[35] );
// Step 13
word const g18= G( g5^g8^g11^g14^g17, T[2], M[36],M[37],N[36],N[37] );
// Step 14
word const g19= G( g15^g18, T[3], M[38],M[39],N[38],N[39] );
// Step 15
word const g20= G( g16^g19, T[0], M[40],M[41],N[40],N[41] );
// Step 16
word const g21= G( g17^g20, T[1], M[42],M[43],N[42],N[43] );
word const g27= G( g20, T[3], M[54],M[55],N[54],N[55] );
// Step 17
word const g22= G( g18^g21, T[2], M[44],M[45],N[44],N[45] );
word const g25= G( g21, T[1], M[50],M[51],N[50],N[51] );
// Step 18
word const g23= G( g19^g22, T[3], M[46],M[47],N[46],N[47] );
word const g26= G( g22, T[2], M[52],M[53],N[52],N[53] );
word const g29= G( g22^g25, T[1], M[58],M[59],N[58],N[59] );
// Step 19
word const g24= G( g20^g23, T[0], M[48],M[49],N[48],N[49] );
word const g30= G( g20^g26, T[2], M[60],M[61],N[60],N[61] );
Y[1] = g20^g26^g29;
// Step 20
word const g28= G( g21^g24, T[0], M[56],M[57],N[56],N[57] );
word const g31= G( g21^g24^g27, T[3], M[62],M[63],N[62],N[63] );
Y[2] = g21^g24^g27^g30;
// Step 21
Y[0] = g22^g25^g28;
Y[3] = g31;
}

Trên một bộ vi xử lí x86_64, khi dịch ở chế độ 32 bit, mã nguồn trên mất khoảng 256 xung nhịp để mã hóa 1 cụm (16 byte), tức khoảng 16 xung nhịp để mã hóa 1 byte.

Khi chỉnh sửa lại một chút cho độ dài từ 64 bit và biên dịch ở chế độ 64 bit, với độ dài cụm tăng gấp đôi, tốc độ cũng sẽ tăng gấp đôi, tức còn khoảng 8 xung nhịp để mã hóa 1 byte. (Đây là ước lượng thô sơ. Thực tế, các bộ vi xử lí như AMD K8 và Intel Core 2 có thể mất đến 10-12 xung nhịp bởi vì phép nhân 64 bit chậm hơn phép nhân 32 bit, phép nhân 64 bit trên Intel chậm hơn trên AMD.)

Ngoài ra, ta còn có thể ghép song song 2 đoạn mã nguồn trên (một cách khéo léo) để mã hóa đồng thời 2 cụm, sẽ tiết kiệm được vài xung nhịp mỗi byte. Và cuối cùng, trên các bộ vi xử lý x86_64, ta còn có thể dùng các phép tính vector để mã hóa đồng thời 4 cụm, tiết kiệm vài xung nhịp mỗi byte nữa.

Để so sánh, một cài đặt đã tối ưu hóa của thuật toán mật mã AES (với 14 vòng cho khóa 256 bit) thường mất khoảng 24 xung nhịp để mã hóa 1 byte.

20. Lưu đồ dữ liệu ở Hình 3 cho một cái nhìn xuyên thấu hơn vào thuật toán, nhờ đó giúp dễ dàng cảm nhận được một số tính chất của thuật toán từ quan điểm phân tích mật mã. Ví dụ, nó có thể giúp ta lí giải được tại sao khóa Z lại có 5 từ mà không phải là 4 từ hay 6 từ. Nhưng ở đây, ta sẽ không quan tâm đến những tính chất như thế mà chỉ quan tâm đến khía cạnh thực thi, mà cụ thể là tính toán song song. Gọi g(k) là kết quả của hàm G ở vòng k, từ lưu đồ dữ liệu, dễ dàng suy ra được một qui trình thực hiện gồm 20 bước nối tiếp, như sau.

[indent] 1. Tính g(0)
2. Tính g(1)
3. Tính g(2)
4. Tính g(3)
5. Tính g(4)
6. Tính g(5), g(11) song song
7. Tính g(6), g(9) song song
8. Tính g(7), g(10), g(13) song song
9. Tính g(8), g(14) song song
10. Tính g(12), g(15) song song
11. Tính g(16)
12. Tính g(17)
13. Tính g(18)
14. Tính g(19)
15. Tính g(20)
16. Tính g(21), g(27) song song
17. Tính g(22), g(25) song song
18. Tính g(23), g(26), g(29) song song
19. Tính g(24), g(30) song song
20. Tính g(28), g(31) song song[/indent]

19. Khi thực hiện các thuật toán nói chung và mã hóa nói riêng, một kĩ thuật quan trọng mà chúng ta không thể bỏ qua là khai thác khả năng tính toán song song của bộ vi xử lí. Thuật toán mật mã giới thiệu ở đây hiển nhiên là cho phép dùng nhiều lõi (core) của bộ vi xử lí để mã hóa song song nhiều cụm. Nhưng liệu trong phạm vi 1 cụm, nó có cho phép thực hiện các phép tính song song bằng các đơn vị thi hành (execution unit) của 1 lõi hay không?

Để trả lời câu hỏi này, cách trực quan nhất là ta hãy xem lưu đồ dữ liệu. Lưu đồ vẽ trên Hình 2 là lưu đồ đã được "tháo xoắn", tức là đã lược đi tất cả các hoán vị vòng quanh để cho các luồng dữ liệu quan trọng được "duỗi thẳng" ra. Nhưng trong lưu đồ đó vẫn còn tiềm ẩn những luồng dữ liệu "xoắn" khác nữa mà để thấy rõ chúng, cần phải "tháo xoắn" ở một cấp độ cao hơn nữa (xem Hình 3).

Code:

X0 X1
\ \
\0 \1
G-----G
\
\
X2 X3 \
\ \ \
1 \2 \3 \4
G-----G-----G-----G
\ \ \
\ \ \
\ \ \
\ \ \
4 \5 \6 \7
G-----G-----G-----G
\ \ \
\ \ \
o o o
|\ |\ |\
7 | \8 | \9 | \10
G--|--G | G | G
| \ | \ |
| \| \|
o + +
|\ |\ |\
10 | \11 | \12 | \13
G | G | G | G
\ | \ | \ |
\| \| \|
+ + +
|\ |\ \
13 | \14 | \15 \16
G | G | G G
\ | \ | \
\| \| \
+ + \
\ \ \
16 \17 \18 \19
G-----G-----G-----G
\ \ \
\ \ \
\ \ \
\ \ \
19 \20 \21 \22
G-----G-----G-----G
\ \ \
\ \ \
\ o o
\ |\ |\
22 \23 | \24 | \25
G-----G--|--G | G
\ | \ |
\ | \|
o o +
|\ |\ |\
25 | \26 | \27 | \28
G | G | G | G
\ | \ | \ |
\| \| \|
+ + +
|\ |\ |\
28 | \29 | \30 | \31
G | G | G | G
\ | \ | \ |
\| \| \|
+ + +
\ \ \
31 \ \ \
G Y0 Y1 Y2
\
\Y3
Hình 3. Thuật toán mã hóa đầy đủ,
thu được bằng cách "tháo xoắn" Hình 2.

18. Ta đã biết rằng phép toán (o) dùng trong thuật toán thực chất chỉ đem đến độ phức tạp ngang với một phép nhân thông thường cùng với 1 phép đổi dấu trước và sau phép nhân. Nhưng trong mã nguồn, (o) tốn mất 8 phép tính. Như vậy cân nhắc hiệu quả và chi phí thì chúng ta đang bị "lỗ" to!

May thay, thực tế không phải như thế. Khi mã hóa nhiều cụm văn bản, phần lớn các phép tính đều có thể tính trước khi biết giá trị của cụm văn bản, sao cho toán tử (o) với văn bản thật sự có thể thực hiện được chỉ bằng 1 phép nhân và 1 phép cộng:

[indent]x (o) z = x * m + n[/indent]

Trong đó x là một từ văn bản, z là một từ của khóa, phép toán (o) được định nghĩa với một đơn vị u cố định nào đó, và

[indent]m = 2*(z - u) + 1

n = (2*u - 1)*(z - u)[/indent]

Để mã hóa, ta có thể tính sẵn 64 từ m và 64 từ n tương ứng cho 64 toán tử (o), lưu chúng trong các mảng M và N, và dùng 2 mảng này thay cho mảng K và L khi mã hóa. Chi phí bộ nhớ không thay đổi, nhưng chi phí tính toán thì giảm hẳn.

Để giải mã, chỉ cần để ý rằng

[indent](x * m + n) * 1/m - n/m = x[/indent]

Vậy, cũng như hàm CRYPT ở đoạn trên, hàm CRYPT (mới) ở đây cũng có thể dùng để giải mã, bằng thời biểu khóa lập sẵn với 1/m thế chỗ cho m và -n/m thế chỗ cho n. Lưu ý một lần nữa là toán tử "/" kí hiệu phép nhân với nghịch đảo của mẫu số (vốn dĩ luôn là 1 số lẻ) modulo 2↑w.

Gọi ME và NE là các hàm bung khóa (sao cho M = ME(Z,U), N = NE(Z,U)), ta có thể tóm tắt lại cách dùng phiên bản mới của CRYPT để mã hóa và giải mã như sau:

[indent]CRYPT( CRYPT(X,T,ME(Z,U),NE(Z,U))RS,TRS, 1/ME(Z,U)R, -NE(Z,U)R/ME(Z,U)R )RS = X

ENCRYPT(X,Z,T,U) = CRYPT(X,T,ME(Z,U),NE(Z,U))

DECRYPT(Y,Z,T,U) = CRYPT(YRS,TRS, 1/ME(Z,U)R, -NE(Z,U)R/ME(Z,U)R )RS[/indent]

17. Có một điều lí thú là thực hiện theo cách trên, CRYPT không những dùng để mã hóa mà còn có thể dùng để giải mã! Tính tương tự giữa mã hóa và giải mã không những có ích cho việc lập trình hiệu quả mà còn là rất thiết yếu để đảm bảo rằng việc tấn công vào mật mã theo hướng nào, bất kể là từ bản rõ đến bản mã, từ bản mã đến bản rõ, hay là từ bản rõ và bản mã vào giữa, cũng đều khó khăn như nhau.

Để cảm nhận sự thật này, trước hết hãy xem lưu đồ dữ liệu của thuật toán ở dạng đầy đủ, thu được từ việc ghép nối tiếp 32 lưu đồ vòng loại A (Hình 1A) và loại B (Hình 1B) sau đó "tháo xoắn", nghĩa là loại bỏ các hoán vị vòng quanh.

Code:

X3 X2 X1 X0
| | | |
| | | 0 G<-Z3,Z4,T0
| | +<---------o
| | 1 G<-Z0,Z1,T1|
| +<---------o |
| 2 G<-Z2,Z3,T2| |
+<---------o | |
3 G<-Z4,Z0,T3| | |
o------------------------------->+
| | | 4 G<-Z1,Z2,T0
| | +<---------o
| | 5 G<-Z3,Z4,T1|
| +<---------o |
| 6 G<-Z0,Z1,T2| |
+<---------o | |
7 G<-Z2,Z3,T3| | |
| ----------------------------o
| / | | |
o--/---------------------------->+
/ | | 8 G<-Z4,Z0,T0
/ | o--------->+
+ | 9 G<-Z1,Z2,T1|
| o--------->+ |
| 10 G<-Z3,Z4,T2| |
o--------->+ | |
11 G<-Z0,Z1,T3| | |
+<-------------------------------o
| | | 12 G<-Z2,Z3,T0
| | o--------->+
| | 13 G<-Z4,Z0,T1|
| o--------->+ |
| 14 G<-Z1,Z2,T2| |
o--------->+ | |
15 G<-Z3,Z4,T3| | |
| | | |
| | | 16 G<-Z0,Z1,T0
| | +<---------o
| | 17 G<-Z2,Z3,T1|
| +<---------o |
| 18 G<-Z4,Z0,T2| |
+<---------o | |
19 G<-Z1,Z2,T3| | |
o------------------------------->+
| | | 20 G<-Z3,Z4,T0
| | +<---------o
| | 21 G<-Z0,Z1,T1|
| +<---------o |
| 22 G<-Z2,Z3,T2| |
+<---------o | |
23 G<-Z4,Z0,T3| | |
| ----------------------------o
| / | | |
o--/---------------------------->+
/ | | 24 G<-Z1,Z2,T0
/ | o--------->+
+ | 25 G<-Z3,Z4,T1|
| o--------->+ |
| 26 G<-Z0,Z1,T2| |
o--------->+ | |
27 G<-Z2,Z3,T3| | |
+<-------------------------------o
| | | 28 G<-Z4,Z0,T0
| | o--------->+
| | 29 G<-Z1,Z2,T1|
| o--------->+ |
| 30 G<-Z3,Z4,T2| |
o--------->+ | |
31 G<-Z0,Z1,T3| | |
| | | |
Y3 Y2 Y1 Y0
Hình 2. Thuật toán mã hóa đầy đủ.

Sau đây, bên cạnh các toán tử đã định nghĩa trên 1 từ, ta sẽ dùng vài toán tử trên các toán hạng nhiều từ.

-- Toán tử R kí hiệu sự đảo ngược thứ tự từ của một số nhiều từ, và toán tử S kí hiệu sự hoán đổi nửa thấp với nửa cao của từng từ. Ví dụ, với từ 8 bit (w=8),

[indent]0x01234567 R = 0x67452301

0x01234567 S = 0x10325476

0x01234567 R S = 0x76543210[/indent]

Hiển nhiên S và R đều có tính tự nghịch, nghĩa là với mọi a ta luôn có a S S = a và a R R = a. Và cũng dễ thấy rằng S và R giao hoán, nghĩa là a R S = a S R với mọi a.

-- Các toán tử +, -, -x, ', / và 1/x kí hiệu áp dụng toán tử cùng tên định nghĩa cho từ lên từng từ tương ứng của các toán hạng. Ví dụ,

[indent](a, b, c,...)' = (a', b', c',...)

-(a, b, c,...) = (-a, -b, -c,...)

1/(a, b, c,...) = (1/a, 1/b, 1/c,...)

(a1, b1, c1,...) + (a2, b2, c2,...) = (a1+a2, b1+b2, c1+c2,...)

(a1, b1, c1,...) - (a2, b2, c2,...) = (a1-a2, b1-b2, c1-c2,...)

(a1, b1, c1,...) / (a2, b2, c2,...) = (a1/a2, b1/b2, c1/c2,...)[/indent]

Từ lưu đồ dữ liệu, dễ dàng suy được qui trình giải mã dùng CRYPT như sau.

1. Đem cụm mã Y đảo ngược thứ tự các từ và hoán đổi nửa thấp với nửa cao của từng từ, được Y1:

Code:

Y1 := Y R S

2. Đem nắn T đảo ngược thứ tự các từ và hoán đổi nửa thấp với nửa cao của từng từ, xem kết quả thu được như một nắn mới, đem bung nó ra, được C1:

Code:

C1 := TE(T R S)

3. Bung khóa đơn vị U, rồi đem kết quả thu được đảo ngược thứ tự các từ, được L1:

Code:

L1 := UE(U) R

4. Đảo ngược thứ tự các từ của khóa Z rồi bung nó ra, kết quả thu được đem lấy nghịch đảo của từng từ theo phép nhân (.) với đơn vị là từ tương ứng của L1, ta được K1:

Code:

K1 := (KE(Z R) - L1)' + L1

5. Dùng CRYPT, mã hóa Y1 với các khóa bung K1, C1 và L1, được X1:

Code:

X1 := CRYPT(Y1, K1, C1, L1)

6. Đảo ngược thứ tự các từ của X1 và hoán đổi nửa thấp với nửa cao của từng từ, sẽ khôi phục được cụm rõ ban đầu (X):

Code:

X := X1 R S

Để tóm tắt, ta nêu lại các hệ thức giữa hàm ENCRYPT, DECRYPT và CRYPT:

[indent]DECRYPT(ENCRYPT(X,Z,T,U),Z,T,U) = X

CRYPT( CRYPT(X,KE(Z),TE(T),UE(U))RS, (KE(ZR)-UE(U)R)'+UE(U)R, TE(TRS), UE(U)R )RS = X

ENCRYPT(X,Z,T,U) = CRYPT(X, KE(Z), TE(T), UE(U))

DECRYPT(Y,Z,T,U) = CRYPT(YRS, (KE(ZR)-UE(U)R)'+UE(U)R, TE(TRS), UE(U)R )RS[/indent]

Trong đó X, Y, Z, T, U là những giá trị bất kì với độ dài lần lượt 4w, 4w, 5w, 4w, w bit. Hệ thức thứ nhất chỉ đơn giản giới thiệu rằng ENCRYPT (mã hóa) và DECRYPT (giải mã) là hai hàm "ngược" của nhau. Hệ thức thứ ba và thứ tư cho phương pháp tính 2 hàm này.

16. Hướng dẫn thực hiện. Trong lập trình, một nguyên tắc tối ưu hóa mã nguồn sơ đẳng là kĩ thuật tính sẵn (precomputation): trước khi vào một vòng lặp, hãy tính sẵn mọi giá trị cần thiết ở bên ngoài vòng lặp. Lập trình mật mã cũng vậy thôi. Ta hãy xem lưu đồ dữ liệu.

Code:

2*U+1 t3(0) t1(0) x3(0) x1(0) z4(0) z2(0) z0(0)
| u(0) | t2(0) | t0(0) | x2(0) | x0(0) | z3(0) | z1(0) |
| | | | | | | | | | | | | | |
| | | | | | | | | +-+-+ | | | | |
| o---------------------------------->|] <|<-------o | | |
| | | | | | | | | | | | | | | |
o-->[+] | | | | | | | | | \ \ \ \ |
| | | | | o--------------->+ G | +-\---\---\---\-+
| u(1) | | | | | | | | | | \ \ \ \
| | | | | | | | | | | | z3(1) | z1(1) |
| o---------------------------------->|] <|<-------o z2(1) | z0(1)
| | | | | | | | | +-+-+ | | | | |
o-->[+] | | | | | | | | z4(1) | | | |
| | | | | | | | +<--o | | | | |
| | | | | | | | | | | | | | |
| | \ \ \ | \ \ \ | \ \ \ \ |
| | +-\---\---\-+ +-\---\---\-+ +-\---\---\---\-+
| | | \ \ \ | \ \ \ | \ \ \ \
| | | | | | | | | | | | | | |
| u(2) | t2(1) | t0(1) | x2(1) | x0(1) | z3(2) | z1(2) |
2*U+1 t3(1) t1(1) x3(1) x1(1) z4(2) z2(2) z0(2)
Hình 1A. Vòng 0 của thuật toán mã hóa.
2*U+1 t3(8) t1(8) x3(8) x1(8) z4(16) z2(16) z0(16)
| u(16) | t2(8) | t0(8) | x2(8) | x0(8) | z3(16)| z1(16)|
| | | | | | | | | | | | | | |
| | | | | | +<----------o | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | +-+-+ | | | | |
| o---------------------------------->|] <|<-------o | | |
| | | | | | | | | | | | | | | |
o-->[+] | | | | | | | | | \ \ \ \ |
| | | | | o--------------->+ G | +-\---\---\---\-+
| u(17) | | | | | | | | | | \ \ \ \
| | | | | | | | | | | | z3(17)| z1(17)|
| o---------------------------------->|] <|<-------o z2(17)|z0(17)
| | | | | | | | | +-+-+ | | | | |
o-->[+] | | | | | | | | z4(17)| | | |
| | \ \ \ | \ \ \ | \ \ \ \ |
| | +-\---\---\-+ +-\---\---\-+ +-\---\---\---\-+
| | | \ \ \ | \ \ \ | \ \ \ \
| | | | | | | | | | | | | | |
| u(18) | t2(9) | t0(9) | x2(9) | x0(9) | z3(18)| z1(18)|
2*U+1 t3(9) t1(9) x3(9) x1(9) z4(18) z2(18) z0(18)
Hình 1B. Vòng 8 của thuật toán mã hóa.

Cần tưởng tượng rằng hàm ENCRYPT được nằm trong một vòng lặp lớn: với một bộ khóa (Z, T và U) nhất định, ENCRYPT sẽ được gọi nhiều lần để mã hóa nhiều cụm rõ. Vậy thực chất những thứ có thể tính sẵn trước là những thông tin không lệ thuộc vào giá trị của cụm rõ mà chỉ lệ thuộc vào bộ khóa, cụ thể là (i) dãy các giá trị của thanh ghi z3 và z4 trong từng vòng, (ii) dãy các giá trị của thanh ghi u0 và u1 trong từng vòng, và (iii) dãy các giá trị của thanh ghi t0 trong từng vòng.

Đối với (i), ta tính sẵn dãy này trong một mảng K gồm 64 từ:

[indent]K = (Z3, Z4, Z0, Z1, Z2, Z3, Z4, Z0, Z1, Z2, ..., Z3, Z4, Z0, Z1, Z2, Z3, Z4, Z0, Z1)
trong đó Z4 Z3 Z2 Z1 Z0 = Z[/indent]

Đối với (ii), ta tính sẵn dãy này trong một mảng L gồm 64 từ:

[indent]L = (U, 3*U+1, 5*U+2, 7*U+3, ..., 127*U+63)[/indent]

Đối với (iii), ta tính sẵn dãy này trong một mảng C gồm 32 từ:

[indent]C = (T0, T1, T2, T3, T0, T1, T2, T3, ..., T0, T1, T2, T3)
trong đó T3 T2 T1 T0 = T[/indent]

Sau đó, ta loại bỏ các thanh ghi khóa, các thanh ghi nắn và cặp thanh ghi đơn vị cũng như các phép gán chúng để hoán vị vòng quanh và các phép cộng cập nhật chúng ra khỏi mã nguồn của ENCRYPT, ta được một phiên bản mới nhẹ hơn, gọi là CRYPT. Để mã hóa cụm X thành cụm Y, thay vì dùng

Code:

Y := ENCRYPT(X, Z, T, U)

ta sẽ dùng:

Code:

Y := CRYPT(X, K, C, L)

Trong đoạn này và các đoạn tiếp theo, tên hàm (toán học) được viết hoa để phân biệt với hàm của ngôn ngữ C. Chẳng hạn, ENCRYPT là một hàm toán học, còn encrypt là một hàm C thực hiện hàm toán học ấy.

Các mảng K, C, L được gọi là các thời biểu khóa (key schedule) hoặc khóa bung (expanded key), còn bản thân việc lập ra chúng gọi là lập thời biểu khóa (key scheduling) hoặc bung khóa (key expansion). Các hàm bung khóa tương ứng sẽ được kí hiệu lần lượt là KE, TE và UE, vậy

[indent]K = KE(Z)

L = UE(U)

C = TE(T)[/indent]

15. Mã nguồn trong đoạn trên là một cách thực hiện chuẩn mực, nhưng không phải là cách thực hiện nhanh nhất của thuật toán này. Chẳng hạn, ta thấy trong đó:

-- Phép toán (o) mất 8 phép tính (2 phép cộng, 2 phép trừ, 2 phép nhân, và 2 phép nhân với 2).

-- Hàm G mất 19 phép tính (2 phép (o), 2 phép S và 1 phép xor).

-- Mỗi vòng mất 40 phép tính (19 phép tính trong hàm G, 1 phép xor, 2 phép cộng cho thanh ghi đơn vị (u0,u1), và 16 phép gán để thực hiện các hoán vị vòng quanh, 1 phép "&" và 1 phép "++" trên chỉ số k, đó là còn chưa kể đến 2 phép nhảy có điều kiện trong các cấu trúc điều khiển for và if).

-- Hàm encrypt() mất 40*32 = 1280 phép tính. Như vậy ta mất khoảng 1280 xung nhịp để mã hóa 1 cụm trên một bộ vi xử lí hiện đại. (Thực ra, ước tính này là rất thô sơ. Trên một bộ vi xử lí hiện đại, một phép nhân vẫn mất vài xung nhịp, nhưng bù lại bộ vi xử lí có thể làm song song vài phép tính nếu những phép tính đó không lệ thuộc lẫn nhau.)

Những đoạn sau sẽ chỉ ra các phương thức tối ưu hóa, mà kết hợp lại sẽ giảm thời gian thực hiện xuống còn khoảng 256 xung nhịp, tức là nhanh hơn thực hiện chuẩn mực gấp 5 lần.

14. Nắn T được sinh ra từ số thứ tự của cụm và một khóa 4w bit, gọi là khóa nắn, theo cách giống hệt như các đơn vị được sinh ra từ số thứ tự vòng và khóa đơn vị. Cụ thể như sau.

Gọi T(j) là nắn dùng để mã hóa cụm thứ j. Đối với cụm đầu tiên (j=0), giá trị khóa nắn được dùng luôn làm nắn:

[indent]T(0) = khóa nắn[/indent]

Nắn cho cụm sau được tính từ nắn của cụm trước, theo công thức truy hồi:

[indent]T(j+1) = T(j) + 2*T(0) + 1[/indent]

Hoặc, nếu cần truy nhập ngẫu nhiên đến cụm thứ j, ta có thể tính trực tiếp:

[indent]T(j) = T(0) . j[/indent]

Trong các hệ thức trên, mọi phép tính đều được thực hiện modulo 2↑(4w), nói cách khác ta coi mọi toán hạng kể cả các hằng số 1 và 2 đều là những số có độ dài 4w bit. Số học 4w bit có thể thực hiện được bằng ngôn ngữ C, nhưng sẽ đạt hiệu quả cao hơn rất nhiều khi thực hiện bằng hợp ngữ. Có thể tham khảo mã nguồn, chẳng hạn, tại http://locklessinc.com/articles/256bit_arithmetic.

Công thức truy hồi hiệu quả hơn hẳn so với công thức trực tiếp. Khi thực hiện bằng hợp ngữ, nó chỉ mất 4 phép cộng từ đơn có carry, nghĩa là 4 xung nhịp của bộ vi xử lí. Vậy nên trong thực tiễn truy nhập ngẫu nhiên, ta vẫn nên áp dụng nó bất cứ khi nào có thể. Chẳng hạn, để mã hóa hay giải mã một sector trên ổ đĩa cứng (nơi mọi sector đều được mã hóa bằng cùng một khóa và các cụm dữ liệu được đánh số thứ tự từ đầu đến cuối ổ đĩa, hơn là từ đầu đến cuối sector), ta chỉ dùng công thức trực tiếp để tính nắn cho cụm dữ liệu đầu tiên của sector, còn các cụm kế tiếp thì dùng công thức truy hồi.

Việc có nắn hay không còn tùy theo mục đích và cách thức sử dụng mật mã. Để mã hóa một cách trực tiếp, như đã nói trước đây, việc nắn là tuyệt đối cần thiết. Để sinh một loạt số giả ngẫu nhiên độc lập với nhau ta có thể nắn hay không nắn, và nếu nắn thì sẽ tốt hơn vì dãy số sinh ra sẽ tuần hoàn với chu kì dài hơn nhiều (dài đến mức có thể xem là vô tận, không bao giờ lặp lại). Nhưng để sinh ra một loạt số giả ngẫu nhiên đôi một khác nhau thì ta không được phép nắn, nghĩa là xem T như một khóa bình thường, luôn giữ một giá trị nào đó không đổi trong suốt thời gian sinh loạt số.

13. Thuật toán hoàn chỉnh. Đoạn này nêu những sửa đổi thuật toán sơ khai để thuật toán trở thành hoàn chỉnh.

Ngoài cụm rõ (X) và cụm mã (Y) có độ dài 4w bit, khóa (Z) 5w bit, ta dùng thêm một nắn T dài 4w bit và một khóa đơn vị U dài w bit. Để mã hóa, nắn T được chia thành 4 đoạn dài w bit và nạp vào 4 thanh ghi nắn t0, t1, t2, t3 theo thứ tự từ thấp đến cao:

Code:

(t0,t1,t2,t3) := T

Sau mỗi vòng, tương tự như các thanh ghi văn bản và các thanh ghi khóa, các thanh ghi nắn cũng được hoán trị vòng quanh:

Code:

(t0,t1,t2,t3) := (t1,t2,t3,t0)

Hàm G được sửa lại, thay cho 2 phép o ta dùng 2 phép (o), phép toán thứ nhất có đơn vị là e0, phép toán thứ hai có đơn vị là e1. Và giữa hai nửa của G, một từ nắn (t) được trộn vào văn bản:

[indent]G(x, z0, z1, e0, e1, t) = (((x (o) z0)S ^ t) (o) z1)S[/indent]

Trong mỗi vòng, thanh ghi x0 được cập nhật bởi hàm G mới này:

Code:

x0 := G(x0, z3, z4, u(2*k), u(2*k+1), t0)

Trong đó k là số thứ tự vòng, vòng đầu tiên được đánh số thứ tự 0, và đơn vị u được cho bởi

[indent]u(k) = U . k[/indent]

nghĩa là có thể tính được u một cách tương đương bằng công thức truy hồi:

[indent]u(0) = U

u(k+1) = u(k) + 2*U + 1[/indent]

Để tổng hợp, ta viết lại bằng ngôn ngữ C++ toàn bộ thuật toán mã hóa hoàn chỉnh trên các từ 32 bit:

Code:

typedef uint32_t word;
// nếu trình biên dịch không biết kiểu uint32_t thì
// có thể thử unsigned __int32 hoặc unsigned int
static inline word S(word x) // hoán vị S,
{
return (x <<16) | (x >> 16);
}
static inline word o(word a, word b, word e) // toán tử (o)
{
return 2*a*b + (1 - 2*e)*(a - b + e);
}
static inline word G(word x, word z0, word z1, word u0, word u1, word t)
{
x = o(x,z0,u0);
x = S(x);
x ^= t;
x = o(x,z1,u1);
x = S(x);
return x;
}
void encrypt( word Y[4], word const X[4], word const Z[5], word const T[4], word U )
{
word
x0 = X[0], x1 = X[1], x2 = X[2], x3 = X[3],
z0 = Z[0], z1 = Z[1], z2 = Z[2], z3 = Z[3], z4 = Z[4],
t0 = T[0], t1 = T[1], t2 = T[2], t3 = T[3],
u0 = U,
u1 = u0 + 2*U + 1;
for(int k = 0; k < 32; k++)
{
// 8 <= k < 16 or 24 <= k < 32 iff bit3(k) == 1
if(k & 8) // vòng thuộc loại B
{
x3 ^= x0;
x0 = G(x0, z3, z4, u0, u1, t0);
}
else // vòng thuộc loại A
{
x0 = G(x0, z3, z4, u0, u1, t0);
x1 ^= x0;
}
word x = x0; x0 = x1; x1 = x2; x2 = x3; x3 = x;
word z = z0; z0 = z2; z2 = z4; z4 = z1; z1 = z3; z3 = z;
word t = t0; t0 = t1; t1 = t2; t2 = t3; t3 = t;
u0 = u1 + 2*U + 1;
u1 = u0 + 2*U + 1;
}
Y[0] = x0; Y[1] = x1; Y[2] = x2; Y[3] = x3;
}

12. Đa dạng hóa phép nhân cải tiến. Giả sử e là một số w bit cố định bất kì. Trên tập hợp các số w bit, ta định nghĩa hai phép toán mới, kí hiệu là (.) và (o), như sau.

[indent]a (.) b = (a-e).(b-e) + e
= 2*a*b + (1 - 2*e)*(a + b - e)

a (o) b = -((-a) (.) b)
= 2*a*b + (1 - 2*e)*(a - b + e)[/indent]

Do tính chất tự nghịch của phép đổi dấu ta cũng có 2 hệ thức khác có thể dùng làm định nghĩa một cách tương đương.

[indent]a (o) b = (a+e) o (b-e) - e

a (.) b = -((-a) (o) b)[/indent]

Có thể chứng minh được rằng trên tập hợp các số w bit, các đa thức 3 biến nằm ở vế phải của những hệ thức định nghĩa nói trên là những đa thức hoán vị, nghĩa là khi được xem như những hàm số của bất cứ biến nào khi cố định 2 biến còn lại ở giá trị bất kì, chúng sẽ là những song ánh.

Có thể dễ dàng chứng minh rằng giống như . phép toán (.) cũng có tính kết hợp, tính giao hoán, có phần tử đơn vị là e, và trên phép toán này mọi giá trị a đều có nghịch đảo, kí hiệu a('), với giá trị là

[indent]a(') = (a - e)' + e
= ((2*e - 1)*a - 2*e*(e-1)) / (2*(a-e) + 1)[/indent]

Nhờ đó mà ta có thể dùng (.) để mã hóa và giải mã

[indent]a (.) b (.) b(') = a[/indent]

Nhưng ta sẽ không dùng (.), mà dùng dạng cải biên của nó là (o), vốn dĩ không kết hợp hay giao hoán

[indent](a (o) b) (o) b(') = a[/indent]

Ở đây, có lẽ nên mở ngoặc chú thích rằng . và (.) trong toán học thường không được xem như các phép toán mới, mà chỉ là một cách biểu diễn khác của phép nhân các số lẻ modulo 2↑(w+1) mà thôi. Nói một cách hình thức, gọi Z(w) là tập các số nguyên modulo 2↑w và O(w) là tập các số nguyên lẻ modulo 2↑w thì đại số (O(w+1), *, 1/x, 1), đại số (Z(w), ., ', 0) và đại số (Z(w), (.), ('), e) là những nhóm đẳng cấu với nhau, nghĩa là tồn tại một song ánh, gọi là phép đẳng cấu, từ tập hợp này đến tập kia qua đó mọi phép toán trên những phần tử nào đó của nhóm này có thể thực hiện nhờ phép toán tương ứng trên những phần tử tương ứng của nhóm kia:

-- Phép đẳng cấu Z(w) -> Z(w) định nghĩa bởi x |-> x - e, nhờ đó đơn vị e ứng với đơn vị 0, giúp ta tính nghịch đảo (') nhờ phép nghịch đảo ', giúp ta thực hiện phép nhân (.) nhờ phép nhân .; và

-- Phép đẳng cấu Z(w) -> O(w+1) định nghĩa bởi x |-> 2*x + 1, nhờ đó đơn vị 0 ứng với đơn vị 1, giúp ta tính nghịch đảo ' nhờ nghịch đảo 1/x và giúp ta thực hiện phép nhân . nhờ phép nhân modulo 2↑w của ngôn ngữ C.

Nếu chọn cho (.) một đa thức định nghĩa tổng quát hơn một chút, ta còn có thể tạo ra những nhóm hoàn toàn khác, không đẳng cấu với (O(w+1), *, 1/x, 1). Ví dụ, ta có thể tạo ra nhóm cyclic, tức nhóm đẳng cấu với (Z(w), +, -x, 0). Tuy vậy, phép nhân trong những nhóm như thế tính toán phức tạp mà độ bảo mật không cao nên về mặt công nghệ là kém hiệu quả. Ta sẽ không quan tâm đến chúng.

Ta đã biết rằng phép toán o (mà có thể xem là một trường hợp riêng của (o), với e = 0) bảo toàn phần bù số học. Tính chất này cũng có ở phép toán (o), nhưng dĩ nhiên ở dạng tổng quát hơn:

[indent](1 - 2*e - a) (o) b = 1 - 2*e - (a (o) b)[/indent]

Nói cách khác, khi dùng cùng một khóa b mã hóa hai từ rõ a1, a2 có quan hệ a1 + a2 = 1-2*e thì thu được hai từ mã cũng có quan hệ này. Mối quan hệ (rất nguy hiểm cho người lập mã) này chỉ bị phá vỡ nhờ các phép hoán vị bit và phép xor được dùng xen kẽ trong mật mã.

11. Cả hai nhược điểm nói trên ở thuật toán sơ khai đều có thể khắc phục.

Để khắc phục nhược điểm thứ hai, ta sẽ đưa vào thuật toán một tham số nữa gọi là nắn (tweak). Đây là thuật ngữ để chỉ một tham số lệ thuộc vào vị trí cụm, hay nói cách khác, giá trị của nó biến đổi theo số thứ tự của từng cụm trong bản rõ. Hiển nhiên là khi giá trị cụm mã lệ thuộc cả vào số thứ tự của cụm thì hai cụm rõ dù có bằng nhau cũng mã hóa thành hai giá trị "độc lập" với nhau và nhờ đó, khắc phục được nhược điểm thứ hai.

Việc làm cho cụm mã lệ thuộc vào số thứ tự của cụm, hơn là vào giá trị của các cụm rõ hay cụm mã lân cận, sẽ tạo điều kiện hoàn toàn cho truy nhập ngẫu nhiên, nghĩa là không những ta có thể ứng dụng thuật toán này để mã hóa tệp tin lưu trữ hay mã hóa gói tin truyền qua mạng mà còn có thể ứng dụng nó vào các việc cao cấp hơn như mã hóa cơ sở dữ liệu hay mã hóa ổ đĩa cứng. Hơn nữa, khả năng truy nhập ngẫu nhiên cũng đồng nghĩa với khả năng mã hóa đồng thời nhiều cụm trên những kiến trúc hiện đại như máy tính đa xử lí, bộ vi xử lí đa lõi và bộ xử lí vector, để tăng tốc độ mã hóa lên nhiều lần.

Để khắc phục nhược điểm thứ nhất, ta sẽ đưa vào thuật toán một tham số nữa gọi là khóa đơn vị (unit key) điều khiển việc lựa chọn phần tử đơn vị cho từng phép toán o. Điều này nghe có vẻ hơi lạ bởi vì như ta biết ở trên, phần tử đơn vị là 0, một giá trị cố định. Nhưng việc này thật sự có thể làm được, bằng cách đa dạng hóa phép nhân (phép toán "." và phép toán "o" tương ứng), nghĩa là tổng quát hóa nó thành một họ các phép toán với những phần tử đơn vị là tham số mà ta có thể chọn một cách tùy thích. Cứ mỗi giá trị chọn cho phần tử đơn vị sẽ cho ta một dị bản mới của phép toán này. Khi mã hóa, 64 phép o trong thuật toán sẽ được chọn với 64 giá trị khác nhau của phần tử đơn vị, theo sự điều khiển của khóa đơn vị.

Một phép o bị mất tác dụng mã hóa khi từ khóa được dùng có giá trị bằng đơn vị. Dễ thấy rằng trong trường hợp xấu nhất, là khi mỗi từ trong 5 từ của khóa Z đều (chẳng may) được dùng trong một phép o với đơn vị bằng chính nó, thì cũng chỉ 5 phép o như thế bị vô hiệu và ta vẫn còn lại 59 phép o khác có tác dụng. Nhờ đó, nhược điểm thứ nhất được khắc phục.

10. Nhược điểm thứ hai của thuật toán sơ khai này, nói đúng ra thì là của mọi mật mã cụm, nằm ở tính chất cụm. Giá trị của cụm mã Y chỉ phụ thuộc vào giá trị của cụm mã X và khóa Z. Phương thức mã hóa chia bản rõ thành từng cụm rồi dùng khóa mã hóa từng cụm một cách độc lập với nhau trong kĩ thuật mật mã gọi là chế độ sổ mã điện tử (Electronic Code Book), viết tắt là ECB. Nếu dùng Z để mã hóa một bản rõ có những giá trị cụm nào đó xuất hiện nhiều lần thì những giá trị cụm mã tương ứng cũng xuất hiện nhiều lần ở vị trí tương ứng trong bản mã, dẫn đến tiết lộ một phần thông tin về bản rõ.

Ví dụ trực quan nhất là bản rõ và bản mã ECB của một tấm ảnh chim cánh cụt có thể tìm thấy ở nhiều địa chỉ trên mạng, chẳng hạn http://www.tegos.pt/en/know_more.html

9. Nhược điểm rõ rệt nhất của thuật toán sơ khai này nằm ở cách dùng phép nhân.

Phép toán o có tính chất là x o 0 = x với mọi x. Nếu một từ khóa trong một phép toán o nào đó trong thuật toán có giá trị bằng 0 thì o chỉ có tác dụng đơn thuần là sao chép mọi từ rõ trên đầu vào của nó thành từ mã ở đầu ra, nghĩa là khi đó nó hoàn toàn không mã hóa.

Hàm G(x, z0, z1), vốn dĩ dùng để mã hóa từ văn bản bằng 2 từ khóa, có 2 phép o mỗi phép có một hoán vị đi theo. Nhưng nếu cả hai từ khóa đều bằng 0 thì G cũng giống như o, hoàn toàn không mã hóa:

[indent]G(x, 0, 0) = x[/indent]

Thuật toán có cả thảy 64 phép toán o, mỗi phép dùng 1 từ của khóa Z vốn dĩ có 5 từ. Vậy mỗi từ của khóa Z được dùng một cách trực tiếp lặp đi lặp lại 12 đến 13 lần. Chỉ cần một từ khóa bằng 0 thì đã có 12 đến 13 phép toán o bị mất tác dụng mã hóa. Càng nhiều từ khóa bằng 0, tác dụng mã hóa của thuật toán càng yếu. Trong trường hợp xấu nhất, Z = 0, mọi phép o (và mọi phép S) đều mất tác dụng mà chỉ còn trơ lại các phép xor. Khi đó mỗi từ của cụm mã sẽ chỉ còn là một tổ hợp tuyến tính của các từ của cụm rõ, tức là một giá trị có dạng

[indent]Yi = a0 X0 ^ a1 X1 ^ a2 X2 ^ a3 X3[/indent]

Trong đó i = 0, 1, 2, 3, với Y = Y3 Y2 Y1 Y0 và X = X3 X2 X1 X0, và các hệ số a0, a1, a2, a3 nhận giá trị 0 hoặc 1.

Mật mã tuyến tính như thế sẽ bị giải trong nháy mắt: chỉ cần biết khoảng hơn 1 cặp giá trị (X,Y) thôi thì ta đã có thể lập được đầy đủ một hệ phương trình bậc 1 để tìm ra khóa Z rồi.

Tóm lại, thuật toán sơ khai này có nhược điểm thứ nhất là có những khóa yếu, tức là những giá trị khóa mà hễ được dùng sẽ cho phép phá khóa dễ dàng hơn hẳn.

8. Quá trình mã hóa thực sự là tiến hành 32 lần lặp đi lặp lại, thuật ngữ gọi là 32 vòng, một trong hai động tác mà ta sẽ gọi tên là A và B, theo thứ tự lần lượt là đầu tiên 8 vòng loại A, sau đó 8 vòng loại B, tiếp đó lại 8 vòng loại A, cuối cùng lại 8 vòng loại B. Mỗi vòng gồm hai bước nhỏ như sau.

1. Mã hóa 1 từ văn bản bằng 2 từ khóa và trộn từ này vào 1 từ văn bản khác

Ở vòng loại A, mã hóa x0 rồi trộn nó vào x1:

Code:

x0 := G(x0, z3, z4)
x1 := x1 ^ x0

Còn ở vòng loại B, trộn x0 vào x3 rồi mã hóa x0:

Code:

x3 := x3 ^ x0
x0 := G(x0, z3, z4)

2. Hoán vị vòng quanh các thanh ghi văn bản và các thanh ghi khóa

Trong cả hai loại vòng (A và B):

Code:

(x0,x1,x2,x3) := (x1,x2,x3,x0)
(z0,z1,z2,z3,z4) := (z2,z3,z4,z0,z1)

7. Phác thảo thuật toán. Đoạn này sẽ chỉ ra thuật toán mã hóa ở dạng sơ khai. Cuối đoạn này sẽ nêu ra vài nhược điểm của thuật toán sơ khai này. Việc khắc phục những nhược điểm đó bằng một thuật toán hoàn chỉnh sẽ được trình bày ở đoạn sau.

Ở đây và về sau, kí pháp xâu (hay còn gọi là kí pháp con số) chẳng hạn như x0 x1 x2... sẽ ngụ ý thứ tự từ cao đến thấp, nghĩa là nếu xâu ấy là một số nhiều phần thì x0 là phần cao nhất, x1 là phần thấp hơn kế tiếp, x2 là phần thấp hơn nữa, v.v.; kí pháp bộ (hay còn gọi là kí pháp vector) chẳng hạn như (x0,x1,x2,...) ngụ í thứ tự từ thấp đến cao, nghĩa là nếu (x0, x1, x2,...) là một số nhiều phần thì x0 sẽ chứa phần thấp nhất của số ấy, x1 phần cao hơn kế tiếp x0, và x2 là phần cao hơn kế tiếp x1, v.v. Hai kí pháp này là ngược nhau. Chẳng hạn, ta luôn có (a,b,c,d) = b c d a và 9876 543 21 0 = (0, 21, 543, 9876).

Phép nhân (o) và phép hoán vị hai nửa từ (S) kết hợp với nhau tạo ra sức mạnh bảo mật của thuật toán trong một hàm gọi là hàm G. Hàm G mã hóa một từ văn bản x bằng 2 từ khóa z0 và z1 bằng cách lặp liên tiếp 2 phép o, với một phép S đi theo sau từng phép o:

[indent]G(x, z0, z1) = ((x o z0)S o z1)S[/indent]

Để mã hóa, trước tiên cụm rõ X với độ dài 4w bit được chia thành 4 từ w bit và nạp vào 4 thanh ghi văn bản x0, x1, x2, x3:

Code:

(x0,x1,x2,x3) := X

Tương tự như vậy, khóa Z với độ dài 5w bit được chia thành 5 từ w bit và nạp vào 5 thanh ghi khóa z0, z1, z2, z3, z4:

Code:

(z0,z1,z2,z3,z4) := Z

Trong quá trình mã hóa, các thanh ghi văn bản và các thanh ghi khóa sẽ được biến đổi. Kết quả của quá trình mã hóa thực chất là giá trị cuối cùng của 4 thanh ghi văn bản, mà cụm mã Y với độ dài 4w được tạo thành từ đó:

Code:

Y := (x0,x1,x2,x3)

6. Trong một phép cộng hay phép nhân, giá trị bit 0 của toán hạng có ảnh hưởng không những đến giá trị bit 0 mà còn ảnh hưởng đến giá trị các bit 1, 2, 3,... của kết quả; nhưng bit 1 của toán hạng chỉ có thể ảnh hưởng đến bit 1, 2, 3,... mà không thể ảnh hưởng đến bit 0 của kết quả, còn bit 2 của toán hạng thì chỉ có thể ảnh hưởng đến bit 2, 3, 4,... mà không thể ảnh hưởng đến bit 0 và bit 1 của kết quả. Nói một cách tổng quát thì trong một phép cộng hay phép nhân, giá trị bit k của toán hạng chỉ ảnh hưởng đến giá trị bit k và các bit cao hơn k (nếu có) của kết quả. Như thế, bit càng thấp của toán hạng thì có ảnh hưởng đến càng nhiều bit của kết quả và bit càng cao của kết quả thì chịu ảnh hưởng của càng nhiều bit của toán hạng.

Một tiêu chí bắt buộc để mật mã có thể bảo mật là mỗi bit của cụm rõ phải có ảnh hưởng đến tất cả các bit của cụm mã (và hệ quả là mỗi bit của cụm mã phải lệ thuộc vào tất cả các bit của cụm rõ). Một mật mã chỉ sử dụng toàn các phép cộng, phép nhân và phép xor không thể đáp ứng tiêu chí này.

Do vậy, không có gì lạ khi trong những mật mã chỉ dùng thuần túy các phép tính luận lí và số học của máy không thể vắng mặt những phép hoán vị các bit của một từ, như các phép dịch ( >> và << ) và các phép quay (>>> và <<< ). Những hoán vị như thế có tác dụng đưa các bit cao ở đầu ra (kết quả) của 1 phép cộng hay 1 phép nhân xuống thấp trước khi dẫn đầu ra ấy đến đầu vào (toán hạng) của một phép cộng hay phép nhân nào đó tiếp theo.

Phép hoán vị sẽ dùng trong thuật toán mật mã giới thiệu ở đây là phép hoán đổi nửa thấp với nửa cao của một từ, nghĩa là phép quay một số w bit đi w/2 bit sang bên trái (hay bên phải), được kí hiệu là S theo lối hậu tố. Ví dụ, trên các từ 8 bit (w=8):

[indent]0x5A S = 0xA5[/indent]

Và trên các từ 32 bit (w=32):

[indent]0x1234ABCD S = 0xABCD1234[/indent]

Phép quay không phải chỉ đơn giản là một công cụ thực tiễn để "trộn đều" các bit ở mọi vị trí với nhau mà còn có một cơ sở lí thuyết vững chắc. Người ta đã chứng minh được rằng phép cộng và phép quay tạo thành một bộ hàm cơ sở đủ, nghĩa là ít ra trên lí thuyết, chúng có thể thực hiện bất kì hàm nào trên w bit. Trong khi đó, các bộ phép toán khác thiếu vắng phép quay hay phép cộng (hoặc phép nhân), như {xor, quay}, {cộng, xor}, {nhân, xor}, {cộng, nhân, xor},... đều không có được tính đủ như thế.

5. Thêm một phép đổi dấu toán hạng bên trái và một phép đổi dấu kết quả phép nhân cải tiến, ta sẽ định nghĩa được một phép toán mới, kí hiệu là o:

[indent]a o b = -((-a) . b)[/indent]

Dễ thấy rằng ta cũng có

[indent]a . b = -((-a) o b)[/indent]

Trên bộ vi xử lí, phép toán o này có thể tính được một cách nhanh chóng không kém gì phép nhân cải tiến ở trên:

[indent]a o b = 2*a*b + a - b[/indent]

Do sự đổi dấu, phép toán o không giao hoán, cũng không kết hợp. Nhưng giữa o và . có một quan hệ gần giống như tính kết hợp:

[indent](a o b) o c = a o (b . c)[/indent]

Vì thế o vẫn có phép toán ngược nhờ đó mà ta có thể dùng o để mã hóa và giải mã thông tin:

[indent](a o b) o b' = a[/indent]

Trong đó b' là nghịch đảo của b qua phép toán . đã định nghĩa ở trên.

Với a bất kì, giá trị 1 - a được gọi là phần bù số học của a. Tương tự như tính bù ở phép nhân cải tiến, qua phép toán o, phần bù số học được bảo toàn, nghĩa là với mọi a mọi b:

[indent](1-a) o b = 1 - (a o b)[/indent]

Cũng như tính bảo toàn phần bù luận lí, tính bảo toàn phần bù số học cũng là một tính chất không đáng mong muốn, nhưng o vẫn được xem là một phép toán thích hợp cho mật mã hơn . bởi vì ngoài việc nó không có tính kết hợp hay tính giao hoán, như ta sẽ thấy về sau, trong mật mã nó được dùng xen kẽ với các phép hoán vị bit và các phép xor, vốn dĩ là những phép toán bảo toàn phần bù luận lí nhưng không bảo toàn phần bù số học. Qua một hợp thành phức tạp các phép toán không tương thích với nhau như thế thì chắc là không một thuộc tính nào có thể bảo toàn.

Sự không tương thích giữa các phép toán không phải chỉ xét trên tính bảo toàn phần bù này nọ, mà xét trên rất nhiều phương diện khác nhau. Có thể dễ dàng thử nghiệm rằng, chẳng hạn, giữa phép o và phép xor không tồn tại những hệ thức đơn giản nào tương tự như tính phân phối của phép nhân với phép cộng. Hơn thế nữa, người ta đã chứng minh được rằng (trái với phép o) phép xor và phép quay không thể biểu diễn bằng một đa thức trên vành số nguyên modulo 2↑w, nghĩa là hai phép toán này không thể thực hiện được, cho dù chỉ trên lí thuyết, bằng các phép nhân và các phép cộng của ngôn ngữ C.

4. Phép nhân cải tiến nói trên đóng vai trò trung tâm trong thuật toán mật mã nên ở đây mình xin dừng lại một chút để nêu vài tính chất quan trọng của nó. Trước hết, tính kết hợp:

[indent](a . b) . c = a . (b . c)[/indent]

Chính nhờ tính kết hợp mà mình có thể thản nhiên viết a . b . c mà không cần phải viết rõ các dấu ngoặc để thể hiện trình tự thực hiện 2 phép tính nhân.

Thứ nữa, tính giao hoán:

[indent]a . b = b . a[/indent]

Ta đã biết rằng 1 là phần tử đơn vị của phép nhân trong ngôn ngữ C, nghĩa là với a bất kì:

[indent]1 * a = a = a * 1[/indent]

Từ đó, dễ thấy rằng, đối với phép nhân cải tiến thì phần tử đơn vị là 0:

[indent]0 . a = a = a . 0[/indent]

Ta đã biết rằng, đối với phép nhân trong ngôn ngữ C, mọi số lẻ đều có nghịch đảo. Sau vài biến đổi đơn giản, có thể chứng minh được rằng đối với phép nhân cải tiến, mọi a đều có nghịch đảo (tức là a' thỏa a . a' = 0) là

[indent]a' = - a / (2*a + 1)[/indent]

Nói cách khác, a' bằng số đối của a nhân với 1/(2*a+1), vốn dĩ tồn tại với mọi a. Và từ giờ về sau, ta sẽ chính thức sử dụng dấu nháy đơn ( ' ) để kí hiệu cho phép nghịch đảo này.

Mình đã nói chưa nhỉ? Tốt nhất vẫn nên nhắc lại lần nữa rằng phép nhân cải tiến này có phép toán ngược. Nhưng ta sẽ không đặt ra thêm một cái tên nữa, như là "phép chia cải tiến", cho phép toán ngược này. Và cũng không đặt ra thêm kí hiệu nào nữa. Muốn thực hiện phép toán ngược thì cứ nhân với nghịch đảo thôi:

[indent]a . b . b' = a[/indent]

Những ai đã tìm hiểu những thuật toán mật mã thực sự như là DES hẳn biết rõ một tính chất được gọi là tính bù (complementarity property):

[indent]DES(~x, ~y) = ~DES(x, y)[/indent]

Trong đó ~ là toán tử vay mượn từ ngôn ngữ C, chỉ phần bù luận lí (hay phủ định từng bit), và tính bù này thực chất là mã của phần bù bằng phần bù của mã. Hay nói cách khác, qua DES phần bù luận lí được bảo toàn.

Phép nhân cải tiến của ta cũng có một tính chất gần giống như tính bù, thể hiện như sau:

[indent](~a) . b = ~(a . b)[/indent]

Hệ thức này nói rằng qua phép nhân cải tiến, phần bù luận lí được bảo toàn. Trong thiết kế mật mã, mọi tính chất đại số nào không cần thiết (như tính kết hợp, tính giao hoán, tính bù,...) đều là không đáng mong muốn bởi vì có thể bị đối phương lợi dụng để thám mã. Đó là lí do khiến ta không thể sử dụng phép nhân cải tiến một cách trực tiếp, mà chỉ dùng nó như là phép toán trung tâm để xây dựng một phép toán khác thích hợp hơn.

3. Phức tạp hơn hẳn phép xor và phép cộng, trong khi thời gian thực hiện trên bộ vi xử lí chỉ ngang với 2 phép toán kia, phép nhân là một công cụ tuyệt vời để xây dựng các mật mã hiệu quả trên phần mềm. Nhưng việc không có phép toán ngược là một trở ngại: nếu mã hóa a bằng cách nhân a với khóa (vốn dĩ có thể có giá trị bất kì) thì có thể không tồn tại giá trị khóa nghịch đảo để giải mã.

Tuy vậy, đoạn trên đã gợi í một cách đơn giản để cải tiến phép nhân thành một phép toán mới có phép toán ngược, mà thực chất là phép nhân các số lẻ mod 2↑(w+1) biểu diễn dưới dạng các số bất kì (lẻ hay chẵn) mod 2↑w. Với hai số w bit bất kì a và b, tích cải tiến của a và b, kí hiệu bởi a . b, là một số w bit được định nghĩa như sau.

Nối thêm một bit với giá trị "1" vào tận cùng của a, được a1. Và cũng làm như thế với b, được b1.
Nhân a1 với b1 modulo 2↑(w+1), được c1.
Bỏ bớt bit tận cùng của c1 (vốn dĩ luôn có giá trị là "1"), được c. Giá trị c này chính là tích a . b cần tính.

Phép tính theo định nghĩa nói trên đòi hỏi số học (w+1) bit không có trên bộ vi xử lí, nên chỉ có tính lí thuyết. Nhưng từ định nghĩa đó, có thể chứng minh được công thức thực tế, hiệu quả để tính a . b bằng bộ vi xử lí, là

[indent]a . b = 2 * a * b + a + b[/indent]

hoặc

[indent]a . b = a * (2*b + 1) + b
= b * (2*a + 1) + a[/indent]

2. Các phép toán cần thiết. Mình sẽ dùng các ký hiệu phép toán ^ (xor), + (cộng), - (trừ), * (nhân) để chỉ các phép tính luận lí và số học tương ứng của ngôn ngữ C (mà thực chất chúng là phép tính của ngôn ngữ máy, ngôn ngữ "tự nhiên" của bộ vi xử lí). Cần nhấn mạnh rằng các phép cộng, trừ và nhân trong ngôn ngữ C khác với trong toán học thông thường ở chỗ chúng thực hiện trên các số nguyên modulo 2↑w (với w là độ dài từ máy, và ↑ kí hiệu nâng lên lũy thừa), nghĩa là chúng đều xác định trên một tập hữu hạn các giá trị biểu diễn được bằng w bit.

Phép cộng là một phép toán có phép toán ngược: với a, b bất kì, tồn tại duy nhất b' để

[indent]a + b + b' = a[/indent]

Ta đã biết rằng b' = - b (thường gọi là số đối của b). Vì thế ta nói phép toán ngược của phép cộng là phép trừ.

Tương tự, phép xor cũng có phép toán ngược: với a, b bất kì, tồn tại duy nhất b' để

[indent]a ^ b ^ b' = a[/indent]

Vì biết b' = b, ta nói phép toán ngược của xor chính là xor.

Khác với phép nhân thông thường, phép nhân modulo 2↑w như trong ngôn ngữ C không có phép toán ngược. Thật vậy, b' thỏa a * b * b' = a với mọi a chỉ tồn tại (và duy nhất) khi b và 2↑w nguyên tố cùng nhau, hay nói cách khác b phải là một số lẻ. Với số b như thế, b' gọi là số nghịch đảo của b và được kí hiệu là 1/b và ta cũng có thể viết a * b / b = a, tức là mặc nhiên xem phép toán / (chú ý: không phải là phép chia của ngôn ngữ C) như "phép toán" ngược của phép nhân. Nhưng cần nhớ rằng "phép toán" ngược này thật ra không phải là 1 phép toán bởi nó chỉ xác định với một số giá trị của b.

Không biết thuật toán này tên gì, alice tạm đặt tiêu đề như vậy.

MẬT MÃ HOÁ BẰNG PHÉP NHÂN (st)
Nguồn: Ada at congdongcviet.com

1.Nhân dịp ...xxx..., mình cũng xin đóng góp 1 thuật toán mật mã hóa hoàn chỉnh.

Nó là 1 mã cụm đối xứng với những đặc điểm như sau.

-- Là một mã hướng từ (word-oriented), nghĩa là chỉ làm việc trên các từ máy với một độ dài w (bit) thống nhất. Trong C các từ được thực hiện bằng các kiểu unsigned (char, short, long, long long...), tức là điển hình w = 8, 16, 32, 64,... Nó có độ dài cụm rõ và cụm mã là 4w bit, độ dài khóa là 5w bit, và còn có 2 khóa phụ nữa với dài tổng cộng 5w bit.

-- Không dùng các bảng thế (s-box) và thậm chí không dùng một hằng số bí ẩn (magic number) nào cả. Chỉ dùng thuần túy các phép tính luận lí & số học có sẵn của bộ vi xử lí, như phép cộng, nhân, xor và hoán vị trên từ.

Nhờ vậy, nó rất nhanh, rất minh bạch và rất dễ dàng lập trình để chạy trong thời gian hằng (constant time). Nên biết rằng các thuật toán mật mã dùng bảng thế hay hằng số bí ẩn (chẳng hạn như DES và AES) thường gây ra nghi ngờ rằng có thể chúng ẩn giấu những cửa sau (back door), tức là những công thức bí mật nào do tác giả cố tình cài vào thuật toán để giúp cho việc phá khóa dễ dàng. Các thuật toán như thế cũng thường dẫn đến thực hiện bằng chương trình dùng giá trị của dữ liệu làm chỉ số truy xuất mảng trong bộ nhớ RAM, mà do tác dụng của cache, sẽ có thời gian chạy biến thiên theo giá trị của dữ liệu. Vì thời gian chạy tiết lộ thông tin về dữ liệu, chương trình rất dễ bị tổn thương bởi các kĩ thuật thám mã đo thời gian (timing attacks).

louisnguyen27 wrote:

@Alice Nếu mã hoá như thế này chữ "THÙC" có tồn tại hay không???
Trong trường hợp người dùng gõ sai "THÙ C..." thành "THÙC ..." thì phản ứng như thế nào???
Phần này mình nhớ mang máng là nằm trong luận án cao học của đồng chí nào đó.

Alice nghĩ rằng khi phương pháp mã hoá đã "có thể mã hoá được mọi xâu ký tự" thì đối với nó không tồn tại xâu "sai" hay "đúng". Kể cả THÙC cũng mã hoá được. Nhưng không thể mã hoá như 1 chữ tiếng Việt bởi vì "huyền" là 1 thanh "bằng" còn "UC" là một vần "khép".

Mặt khác, Alice cho rằng không có gì ngăn cản người lập trình tích hợp mã hoá vào 1 giải thuật xử lý bàn phím của người dùng ngay từ trước khi tạo ra văn bản, hay 1 giải thuật xử lý văn bản trước khi mã hoá, để phát hiện sai sót và thông báo lỗi hay tự sửa lỗi.

huynhfxvn wrote:

Xác xuất các chữ được viết hoa trong một văn bản là nhỏ, nên cách nén trên vẫn tỏ ra hiệu quả. Các từ được viết hoa có thể được xử lý không cần mã hoá. Vì vậy phương pháp trên vẫn có thể sử dụng để hiện thị thông tin được.

Alice đồng ý với bạn về vấn đề xác suất. Nhưng alice nghĩ rằng viết hoa vẫn nên được mã hoá như bình thường. Còn các thông tin định dạng, kể cả phân biệt hoa/thường, được lưu và truyền riêng trong một stream có bandwidth nhỏ và chỉ được dùng khi cần hiển thị. Như thế, data có thể sẽ nhỏ hơn và các việc không cần hiển thị (chẳng hạn tìm kiếm) sẽ nhanh hơn.