Mật mã hoá bằng phép nhân (st)

English | Vietnamese

Rules

Main Forum

Portal

Member Listing

Statistics

Search

Reading Room
[Register]

Login [ | https ]

Forum Index

Thủ thuật reverse engineering

Mật mã hoá bằng phép nhân (st)

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 20:32:45 (+0700) \| #1 \| 236148

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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).

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 20:37:52 (+0700) \| #2 \| 236149

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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.

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 20:42:30 (+0700) \| #3 \| 236150

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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]

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 20:45:57 (+0700) \| #4 \| 236151

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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.

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 20:48:12 (+0700) \| #5 \| 236152

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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.

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 20:51:28 (+0700) \| #6 \| 236153

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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ế.

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 20:54:35 (+0700) \| #7 \| 236154

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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)

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 20:56:34 (+0700) \| #8 \| 236155

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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)

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 20:59:17 (+0700) \| #9 \| 236156

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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.

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:00:58 (+0700) \| #10 \| 236157

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:02:00 (+0700) \| #11 \| 236158

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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.

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:03:53 (+0700) \| #12 \| 236159

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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ã.

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:08:10 (+0700) \| #13 \| 236160

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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;
}

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:10:18 (+0700) \| #14 \| 236162

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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ố.

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:16:12 (+0700) \| #15 \| 236163

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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.

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:17:50 (+0700) \| #16 \| 236164

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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]

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:19:42 (+0700) \| #17 \| 236166

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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.

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:21:38 (+0700) \| #18 \| 236167

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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]

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:23:33 (+0700) \| #19 \| 236168

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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.

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:28:02 (+0700) \| #20 \| 236171

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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]

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:30:05 (+0700) \| #21 \| 236173

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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.

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:31:30 (+0700) \| #22 \| 236174

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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);
}

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:33:17 (+0700) \| #23 \| 236175

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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;
    }
}

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:35:58 (+0700) \| #24 \| 236176

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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.

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 21:37:59 (+0700) \| #25 \| 236177

alice
Elite Member

Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline

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---

Như hà nghịch lỗ lai xâm phạm
如何逆虜來侵犯

[Article] Mật mã hoá bằng phép nhân (st)	25/04/2011 22:13:20 (+0700) \| #26 \| 236179

StarGhost
Elite Member

Joined: 29/03/2005 20:34:22
Messages: 662
Location: The Queen
Offline

@Alice: cám ơn bài viết của bạn. Mình không làm về crypto nhưng cũng có một chút hứng thú, vài hôm nữa đọc xong bài viết này sẽ vào thảo luận.

Thân mến.

Mind your thought.

[Article] Mật mã hoá bằng phép nhân (st)	27/04/2011 00:50:19 (+0700) \| #27 \| 236266

mrro
Administrator

Joined: 27/12/2001 05:07:00
Messages: 745
Offline

@alice: cảm ơn bạn đã gửi bài này. mình đã đọc hai lần và có chỗ thắc mắc sau đây nhờ alice hoặc bạn nào theo dõi bài này giải đáp giùm.

alice viết rằng:

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õ.

đây đúng là vấn đề của tất cả các mật mã cụm và người ta giải quyết bằng cách thiết lập ra các chế độ hoạt động khác nhau (mà LRW mà alice đưa ra ở phần cuối cũng là một trong số đó). theo mình đọc và hiểu thì thuật toán mã hoá bằng phép nhân được mô tả ở đây bao gồm của một mật mã cụm (có thể nắn) và một chế độ hoạt động cho mật mã cụm này. nếu đúng là như thế thì đây là một điểm rất lạ, bởi lẽ trước giờ mình chỉ thấy mật mã cụm và chế độ hoạt động được thiết kế tách biệt nhau, đây là lần đầu tiên mình thấy một thuật toán mã hoá hướng đến giải quyết cả hai vấn đề này cùng một lúc.

nhìn kỹ thì thấy mật mã cụm nhận vào X, (Z, U) và T. bộ đôi (Z, U) đóng vai trò là khoá như chúng ta vẫn thấy trong các mật mã cụm thông thường. nghĩa là nếu bỏ T ra, thì mật mã cụm mà alice mô tả chính là một mật mã cụm thông thường như AES hay DES. điểm khác biệt ở đây là nắn T:

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]

việc thêm nắn T này vào theo mình thấy chính là việc xác định chế độ hoạt động cho mật mã cụm ở trên. vấn đề là các nắn T(j) được xác định hoàn toàn tất dịnh dựa vào khoá nắn. điều này làm mình không thấy rõ thuật toán mã hoá bằng phép nhân an toàn trước tấn công chọn bản rõ (chosen plaintext attack). có lẽ do mình không thấy có yếu tố ngẫu nhiên nào được trộn vào bản rõ trong quá trình lập mã. bây giờ giả sử mình mã hoá một bản rõ m (bao gồm n cụm) i lần, thì mặc dù các cụm sẽ được mã hoá khác nhau (nhờ nắn T), nhưng theo mình thấy là i bản mã thu được sẽ giống nhau.

-m

http://tinsang.net

TetCon 2013 http://tetcon.org

Làm an toàn thông tin thì học gì?/hvaonline/posts/list/42133.html

[Article] Mật mã hoá bằng phép nhân (st)	27/04/2011 05:06:00 (+0700) \| #28 \| 236267

StarGhost
Elite Member

Joined: 29/03/2005 20:34:22
Messages: 662
Location: The Queen
Offline

@mrro: mình xin có ý kiến về hai thắc mắc rất thú vị của bạn:
1. Mình cho rằng lý do các thuật toán mã hoá cụm trước đây không bao gồm chế độ hoạt động vào trong thiết kế của chúng là vì:
- Định nghĩa thường thấy của thuật toán mã hoá là E(K,P) = C, trong đó K là khoá bí mật, P là bản rõ, C là bản mã. Việc sử dụng một định nghĩa thuần tuý rất quan trọng không những trong giao tiếp trao đổi giữa các khoa học gia, mà còn trong việc mô hình hoá một cách toán học các thuật toán mã hoá, ví dụ như liên quan đến key-space, ciphertext-space, ánh xạ, v.v...
- Việc chia tách rõ rệt các chức năng làm trong sáng hơn quá trình mã hoá, dẫn đến dễ dàng tìm hiểu, phân tích và chứng minh các tính năng liên quan đến thuật toán.
- Việc chia tách rõ rệt các chức năng làm tổng quát hoá thuật toán mã hoá, khiến cho nó có thể được dùng trong nhiều trường hợp hơn.
- Và chắc là còn các lí do khác mà mình chưa để ý tới. smilie

2. Theo như mình hiểu thì có lẽ khoá nắn ở đây có khả năng hoạt động giống như một IV trong các chế độ hoạt động như CBC hay CFB. Tuy nhiên, để phân tích về độ an toàn của nó thì có lẽ là khó khăn hơn nhiều, vì việc sử dụng nó đã được trộn lẫn vào trong quá trình mã hoá. Và mình có cảm tưởng làm như vậy giống như kiểu "security by obscurity".

Mind your thought.

[Article] Mật mã hoá bằng phép nhân (st)	27/04/2011 08:01:59 (+0700) \| #29 \| 236273

WinDak
Researcher

Joined: 27/01/2002 11:15:00
Messages: 223
Offline

mrro wrote:

việc thêm nắn T này vào theo mình thấy chính là việc xác định chế độ hoạt động cho mật mã cụm ở trên. vấn đề là các nắn T(j) được xác định hoàn toàn tất dịnh dựa vào khoá nắn. điều này làm mình không thấy rõ thuật toán mã hoá bằng phép nhân an toàn trước tấn công chọn bản rõ (chosen plaintext attack). có lẽ do mình không thấy có yếu tố ngẫu nhiên nào được trộn vào bản rõ trong quá trình lập mã. bây giờ giả sử mình mã hoá một bản rõ m (bao gồm n cụm) i lần, thì mặc dù các cụm sẽ được mã hoá khác nhau (nhờ nắn T), nhưng theo mình thấy là i bản mã thu được sẽ giống nhau.
-m

Em chưa hiểu rõ lắm về kết luận của anh mrro. Anh nói mã hoá m i lần nghĩa là:

1) E[0]=P; for j=1..i : E[j]=E(k,E[j-1])

hay

2) for j=1..i: E[j] = E(k,P) ?

nếu 1) thì em thấy chắc chắn E[i] != E[j] for all i,j không phải bàn cãi
nếu 2) thì E[i] = E[j] for all i,j là chuyện bình thường đối với bất kỳ Encryption nào ?

-- w~ --

[Article] Mật mã hoá bằng phép nhân (st)	27/04/2011 10:25:25 (+0700) \| #30 \| 236282

mrro
Administrator

Joined: 27/12/2001 05:07:00
Messages: 745
Offline

@StarGhost: các ý kiến của bạn về việc phân chia giữa mật mã cụm và chế độ hoạt động mình thấy rất hợp lý.

mình cũng nghĩ nắn T được dùng như IV, nhưng mà trong phần cuối alice có viết thế này (đoạn tô màu vàng là do mình tô):

alice wrote:

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.

--->: nếu mình không nhầm thì hàm ý của đoạn này là T(0) (và nghĩa là toàn bộ T) sẽ được xác định bởi Z. mình thấy chỗ này khác với bài báo giới thiệu LRW, trong đó người ta có nói là T thật ra đóng vai trò như IV và vì thế có thể lấy những giá trị không cần phải là bí mật nhưng đương nhiên là phải đảm bảo vai trò của một IV, ví dụ như ngẫu nhiên, duy nhất và không thể đoán trước.

@Windak: àh ý của anh là ý thứ hai đó. bây giờ giả sử bản rõ chỉ chứa một trong hai giá trị:

Code:

x = chiến đấu
y = đầu hàng

và giả sử em không đổi khoá. lúc này nếu lần mã hoá nào cũng cho kết quả giống nhau, thì ở trận chiến thứ nhất, có thể đối phương sẽ không biết bản rõ của em là gì, nhưng sang đến trận chiến thứ hai thì chỉ cần quan sát bản mã em gửi ra là đối phương có thể biết được em muốn đánh hay muốn hoà rồi.

một ví dụ gần gũi hơn là bầu cử. giả sử chỉ có hai ứng viên, nghĩa là bản rõ của em chỉ là một trong hai giá trị {0, 1}. lúc này nếu mã hoá luôn cho kết quả giống nhau, thì có mã hoá cũng như không.

tình huống tương tự cũng có thể xảy ra với việc đấu thầu. chẳng hạn như bên kêu mời thầu gửi khoá công khai của họ cho các bên tham gia đấu thầu. các bên này sẽ mã hoá con số dự thầu của họ và gửi lại cho bên mời thầu. con số dự thầu này chắc chắn nằm trong một khoảng nào đó, và nếu mã hoá là tất định thì một người có thể dễ dàng đoán được con số dự thầu của các đối thủ.

nói cách khác, câu hỏi là: làm sao có thể dùng lại khoá nhiều lần mà vẫn an toàn? (vì nếu mà chỉ dùng khoá được một lần rồi phải đổi, thì thôi dùng one time pad luôn cho nó sướng smilie

. muốn như thế, thì điều kiện cần là mỗi lần mã hoá, dẫu cùng khoá, cùng bản rõ, kết quả phải là những bản mã khác nhau hoàn toàn.

đương nhiên các mật mã cụm như AES hay DES không làm được việc đó. thành ra người ta mới xây dựng ra các chế độ hoạt động cho các mật mã cụm này và chính các chế độ hoạt động mới đảm bảo được tính xác suất của các thuật toán mã hoá.

sự phân tách rõ ràng này, như StarGhost nói, giúp ích rất nhiều trong việc tìm hiểu, phân tích và chứng minh tính bảo mật của các thuật toán mã hoá. chẳng hạn như mặc dù không thể chứng minh AES hay DES là an toàn (secure pseudo random permutation), nhưng có thể chứng minh được các chế độ hoạt động CBC hay CTR là an toàn với một số điều kiện và giả thuyết nhất định.

-m

http://tinsang.net

TetCon 2013 http://tetcon.org

Làm an toàn thông tin thì học gì?/hvaonline/posts/list/42133.html

Go to:

Users currently in here
1 Anonymous