MẬt mã khóA ĐỐi xứng lý thuyết cơ bản của Shannon

tải về 1.46 Mb.

trang	5/5
Chuyển đổi dữ liệu	30.08.2016
Kích	1.46 Mb.
	#28532

1 2 3 4 5

Phép hoán vị q₀ và q₁: ở đây q₀ và q₁ là các phép hoán vị cố định trên các gía trị 8 bít. Nó được xây dựng từ 4 phép hoán vị 4 bнt khбc nhau. Nếu gọi x lа giб trị đầu vаo thм y lа giб trị đầu ra của hoбn vị được xбc định như sau:

a₀,b₀=[x/16], x mod 16

a₁=a₀b₀

b₁=a₀(b₀>>>1) 8a₀ mod 16

a₂,b₂=t₀[a₁], t₁[a₁]

a₃=a₂b₂

b₃=a₂(b₂>>>1) 8a₂ mod 16

a₄,b₄=t₂[a₃], t₃[b₃]

y=16b₄+a₄

ở đây t₀,t₁,t₂,t₃ là các S-box, được xác định khác nhau đối với q₀ và q₁. Trường hợp q₀ thì t₀,t₁,t₂,t₃ được cho như sau:

t₀=[817D6F320B59ECA4]

t₁=[ECB81235F4A6709D]

t₂=[BA5E6D90C8F32471]

t₃=[D7F4126E9B3085CA]

Trường hợp q₁ thì t₀,t₁,t₂,t₃ được cho như sau:

t₀=[28BDF76E31940AC5]

t₁=[1E2B4C376DA5F908]

t₂=[4C75169A0ED82B3F]

t₃=[B951C3DE647F208A]

Các giá trị S_i,j: Cách xác định giá trị của S_i,j qua các bước sau:

Đầu tiên ta định nghĩa k=N/64, với N là chiều dài khóa mật 128 hay 192 hay 256. Khóa M bao gồm 8k byte m₀,…,m_8k-1, các byte này biến đổi thành 2k từ 32 bít. Ta xбc định M_i như sau:

Từ M_i ta xбc định 2 vйc tơ cу chiều dаi k như sau:

M_e=(M₀,M₂,…,M_2k-2)

M_o=(M₁,M₃,…,M_2k-1)

Một vector gồm k từ 32 bit thứ 3 cũng được suy ra từ khóa bằng cách lấy ra từng nhóm gồm 8 byte trong khóa, xem nhóm các byte này là một vector trên GF(2⁸) và nhân vector này với ma trận 4×8 RS. Sau đó mỗi kết quả 4 byte được xem như một từ 32 bit. Những từ này kết hợp lại tạo thành vector thứ ba. Được xбc định như sau:

ở đвy RS được cho như sau:

Cбc giб trị của vйc tơ thứ 3 được tнnh như sau:

S=(S_k-1,S_k-2,…,S₀)

Hаm mở rộng khуa: Thuật toбn Twofish sử dụng 40 khуa con 32 bнt, cбc khуa con nаy hмnh thаnh từ khуa mật bằng hаm mở rộng khуa. Hаm nаy được xвy dựng trкn cơ sở thủ tục h, thủ tục nаy được biểu diễn như hмnh vẻ 7.33.

Hình 7.33. Quá trình sinh khóa con

Như ta thấy đối số đầu vào của h là X có độ lớn là 32 bít và một danh sách L=(L₀,…,L_k-1) mỗi phần tử cũng là 32 bít, và đầu ra là một số có độ lớn là 32 bít. Hаm h thực hiện qua k giai đoạn. Trong mỗi giai đoạn 4 byte, mỗi byte thực hiện thay thế qua S-box cố định vа XOR với một phần tử của danh sach L. Qua k giai đoạn, cбc byte thu được lại thực hiện tiếp phйp thay thế S-box nữa vа cuối cщng lа nhвn với ma trвn MDS như trong hаm g. Cụ thể lа ta chia cбc từ thаnh cб byte:

, i=0,…,k-1; j=0,1,2,3.

Sau đу lần lượt xбc định thay thế vа phйp toбn XOR.

Nếu k=4 thм:

Nếu chъng ta cу:

Trong cбc trường hợp cтn lại thм chъng ta cу:

y₀=q₁[q₀[q₀[y_2,0]l_1,0]l_0,0]

y₁=q₀[q₀[q₁[y_2,1]l_1,1]l_0,1]

y₂=q₁[q₁[q₀[y_2,2]l_1,2]l_0,2]

y₃=q₀[q₁[q₁[y_2,3]l_1,3]l_0,3]

Sauk hi tìm hiểu xong hàm h, ứng dụng hàm này để mở rộng khóa bằng dãy các phép tính sau:

Hằng số sử dụng để nhвn đфi cбc byte, i= 0, ..., 255, iρ gồm 4 byte bằng nhau, mỗi byte ứng với giб trị i. Бp dụng hаm h lкn cбc từ theo dạng nаy. Đối với A_i cбc giб trị byte lа 2i vа đối số thứ hai của h lа M_e. Tương tự Bi được tнnh toбn, sử dụng 2i + 1 như giб trị byte vа M_o như đối số thứ hai với một phйp quay thкm trкn 8 bit. Cбc giб trị A_i vа B_i tổ hợp thаnh một PHT (Pseudo–Hadamard Transform). Một trong hai kết quả nаy quay 9 bit nữa. Hai kết quả nаy tạo thаnh hai từ khуa mở rộng

Chuẩn mã khối AES

Lịch sử ra đời. Với rất nhiều nhược điểm đã được chỉ ra, thuật toán DES (được công nhận vào năm 1976 bởi NIST của Mỹ và có tên gọi chính thức là chuẩn FIPS PUB 46 vào năm 1977) đã gần như không còn được sử dụng trong các ứng dụng thực tiễn. Các nghiên cứu về khả năng ứng dụng của DES đã chỉ ra rằng, thuật toán DES đã không còn đáp ứng được các tiêu chuẩn cần thiết (độ an toàn, tính hiệu quả, tốc độ thực hiện, …) để có thể tiếp tục là chuẩn cho các ứng dụng trong thực tiễn. Để cố gắng khắc phục các nhược điểm đã chỉ ra của thuật toán DES, trên thực tế đã xuất hiện rất nhiều các thuật toán cải tiến dựa trên DES (như DES-X, G-DES, D_DES, T_DES) hoặc các thuật toán khác (như IDEA, RC5, Blowfish, …) nhằm khắc phục các nhược điểm hoặc thay thế thuật toán DES. Nhưng với các đòi hỏi ngày càng cao của các ứng dụng trong thực tiễn các thuật toán này đều đã chứng tỏ là không đạt chuẩn với các yêu cầu mới.

Trước tình hình đó, NIST đã mở ra một cuộc thi nhằm tìm kiếm thuật toán mới thay thế cho thuật toán DES (được gọi là AES – Advanced Encryption Standard [12-20]). Các yêu cầu cơ bản đối với các thuật toán AES là có tốc độ nhanh hơn so với DES, ít nhất có độ an toàn không kém T_DES và có khả năng thực hiện tối ưu trên cả phần cứng và phần mềm. Các thuật toán này phải thực hiện trên khối dữ liệu có độ dài 128 bít, và có khả năng làm việc với các khóa có độ dài khác nhau – 128, 192, và 256 bít, và cuộc thi đã chính thức công nhận thuật toán Rijndael là chuẩn mới (với độ dài khóa là 128 bít, và khuyến nghị sử dụng khóa 256 bít đối với các yêu cầu tối mật).

Kết quả qua so sánh thực hiện trên phần mềm và phần cứng, có 5 thuật toán vào vòng chung kết MARS, RC6, Rijndael, Serpent, Twofish, chúng ta đã xem 4 thuật toán trước. Ở đây chúng ta xem thuật toán được bầu làm chuẩn mới Rijndael.

Đặc điểm chung: là thuật toán được phát triển từ thuật toán Square, Nhà thiết kế: Vincent Rijmen và Joan Daemen. Mặc dù 2 tên AES và Rijndael vẫn thường được gọi thay thế cho nhau nhưng trên thực tế thì 2 thuật toán không hoàn toàn giống nhau. AES chỉ làm việc với khối dữ liệu 128 bít và khóa có độ dài 128 (có 10 vòng mã), 192 (có 12 vòng mã) hoặc 256 (có 14 vòng mã) bít trong khi Rijndael có thể làm việc với dữ liệu và khóa có độ dài bất kỳ là bội số của 32 bít nằm trong khoảng từ 128 tới 256 bít. Trong phần này chúng ta tìm hiểu về hệ mật AES.

Miêu tả thuật toán: Hầu hết các tính toán của AES được thực hiện trên trường hữu hạn. AES hoạt động trên các mảng của byte kích thước 44, được gọi là state (trạng thái).

Quy trình mã hóa Rijndael sử dụng bốn phép biến đổi chính:

1. AddRoundKey: cộng () mã khóa của chu kỳ vào trạng thái hiện hành. Độ dài của khóa của chu kỳ bằng với kích thước của trạng thái.

2. SubBytes: thay thế phi tuyến mỗi byte trong trạng thái hiện hành thông qua bảng thay thế (S-box).

3. MixColumns: trộn thông tin của từng cột trong trạng thái hiện hành. Mỗi cột được xử lý độc lập.

4. ShiftRows: dịch chuyển xoay vòng từng dòng của trạng thái hiện hành với di số khác nhau.

Quá trình mã hóa được thực hiện 3 ba giai đoạn sau:

1. Thực hiện thao tác AddRoundKey đầu tiên trước khi thực hiện các chu kỳ mã hóa.

2. Nr – 1 chu kỳ mã hóa bình thường: mỗi chu kỳ bao gồm bốn bước biến đổi liên tiếp nhau: SubBytes, ShiftRows, MixColumns, và AddRoundKey.

3. Thực hiện chu kỳ mã hóa cuối cùng: trong chu kỳ này thao tác MixColumns được bỏ qua.

Chúng ta đi tìm hiểu các lệnh biến đổi trong quá trình mã hóa.

+ SubstituteBytes – bước thay thế có tính phi tuyến, theo đó mỗi byte được thay thế bởi một byte có giá trị khác theo bảng tìm kiếm (lookup table) – gọi là hộp S. Như vậy, mỗi byte trong bảng được thay thế bởi một byte của hộp S (S-box). Hộp S được sinh ra từ hàm ngược (inverse function) trên GF(2⁸) để có được tính chất phi tuyến cao nhất. Để ngăn ngừa cuộc tấn công dựa trên các tính chất đại số đơn giản, hộp S-box này được tạo nên bằng cách kết hợp phép nghịch đảo với một phép biến đổi affine khả nghịch. Hộp S cũng được thiết kế để bảo đảm tính xáo trộn tốt nhất và được chọn để tránh các điểm bất động.

Hình 7.34. Trong bước SubstituteBytes, mỗi byte trong state được thay thế bởi một byte (phần tử 8 bít) của hộp S đóng vai trò là bảng tìm kiếm.

+ ShiftRows – bước chuyển dịch, theo đó mỗi hàng của state được dịch vòng một số bước nào đó. Đối với AES hàng đầu tiên không thay đổi. Các byte của hàng thứ 2 được dịch vòng đi 1byte về bên trái. Tượng tự, các byte của hàng thứ 3 và 4 được dịch vòng đi 2 và 3 byte tương ứng về phía trái. Bằng cách này mỗi cột của state ra của ShiftRows là sự kết hợp lại của các byte từ mỗi cột của state vào.

Hình 7.35. Trong bước ShiftRows, các byte trong mỗi hàng của state được dịch vòng về phía trái. Số lượng các bước dịch vòng là khác nhau ở mỗi hàng.
+ MixColumns – hoạt động trên các cột của state, thực hiện một biến đổi tuyến tính. Trong bước này 4 byte của mỗi cột của state được tổ hợp sử dụng một biến đổi tuyến tính ngược. Trong hàm MixColumns mỗi byte của lối vào sẽ ảnh hưởng lên tất cả 4 byte ở lối ra. Cùng với ShiftRows, MixColumns sẽ tạo ra tính khuếch tán (diffusion) của mã. Mỗi cột được xử lý như một đa thức trên GF(2⁸) và được nhân với một đa thức cố định c(x) = ‘03’x³ +’01’ x² + ‘01’x + ‘02’ theo modul (x⁴ + 1).

Hình 7.36. Trong MixColumns, mỗi cột của state được nhân với một đa thức cố định c(x) theo mod(x⁴ + 1).

Hàm Mixcolums(state) được thực hiện trên mỗi cột của ma trận state. Như vậy, đối với 4 cột của ma trận state, hàm Mixcolums(state) được thực hiện 4 lần.

+ AddRoundKey – mỗi byte của state được kết hợp với khóa vòng, mỗi khóa vòng được sinh ra từ khóa bí mật, khi sử dụng thời gian biểu của khóa (key schedule), mỗi khóa vòng có cùng kích thước với state.

Hình 7.37. Trong bước AddRoundKey, mỗi byte của state được kết hợp tương ứng với 1 byte của khóa vòng bằng sử dụng toán tử XOR.

Vòng cuối cùng, thay thế bước Mixcolumns bằng một giá trị AddRoundKey riêng biệt.

Quá trình giải mã: Quá trình này thực hiện các biến đổi ngược so với quá trình mã hóa. Nó thực hiện thông qua các bước sau:

1. Thực hiện thao tác AddRoundKey đầu tiên trước khi thực hiện các chu kỳ giải mã.

2. Nr －1 chu kỳ giải mã bình thường: mỗi chu kỳ bao gồm bốn bước biến đổi liên tiếp nhau: InvShiftRows, InvSubBytes, AddRoundKey, InvMixColumns.

3. Thực hiện chu kỳ giải mã cuối cùng. Trong chu kỳ này, thao tác InvMixColumns được bỏ qua.

Phép biến đổi InvSubBytes: Phép biến đổi ngược của thao tác SubBytes, ký hiệu là InvSubBytes, sự dụng bảng thay thế nghịch đảo của S-box trên GF(28), ký hiệu là S-box^-1.

Phép biến đổi InvShiftRows: InvShiftRows chính là phép biến đổi ngược của phép biến đổi ShiftRows. Dòng đầu tiên của trạng thái sẽ vẫn được giữ nguyên trong khác ba dòng cuối của trạng thái sẽ được dịch chuyển xoay vòng theo chiều ngược với phép biến đổi ShiftRows.

Phép biến đổi InvMixColumns: InvMixColumns là biến đổi ngược của phép biến đổi MixColumns. Mỗi cột của trạng thбi hiện hаnh được xem như đa thức s(x) bậc 4 cу cбc hệ số thuộc GF(2⁸) vа được nhвn với đa thức a^-1(x) lа nghịch đảo của đa thức a(x) (modulo M(x)) được sử dụng trong phйp biến đổi MixColumns.

a^-1(x) = {0b}x3 + {0d}x2 + {09}x + {0e}

Hаm mở rộng khуa:

Bảng khуa mở rộng lа mảng 1 chiều chứa cбc từ (cу độ dаi 4 byte), được kэ hiệu lа w[Nb*(Nr + 1)]. Hаm phбt sinh bảng khуa mở rộng phụ thuộc vаo giб trị Nk, tức lа phụ thuộc vаo độ dаi của mг khуa chнnh. Hаm mở rộng khуa được hổ trợ bởi hai hаm sau:

Hаm SubWord(W) thực hiện việc thay thế (sử dụng S-box) từng byte thаnh phần của từ 4 byte được đưa vаo vа trả kết quả về lа một từ bao gồm 4 byte kết quả sau khi thực hiệc việc thay thế.

Hаm RotWord(W) thực hiện việc dịch chuyển xoay vтng 4 byte thаnh phần (a, b, c, d) của từ được đưa vаo. Kết quả trả về của hаm RotWord lа một từ gồm 4 byte thаnh phần lа (b, c, d, a).

KeyExpansion(byte key[4 * Nk], word w[Nb * (Nr + 1)], Nk)

begin

i=0

while (i < Nk)

w[i] = word[key[4*i],key[4*i+1],

key[4*i+2],key[4*i+3]]

i = i + 1

end while

i = Nk

while (i < Nb * (Nr + 1))

word temp = w[i - 1]

if (i mod Nk = 0) then

temp = SubWord(RotWord(temp)) xor Rcon[i / Nk]

else

if (Nk = 8) and (i mod Nk = 4) then

temp = SubWord(temp)

end if

w[i] = w[i - Nk] xor temp

i = i + 1

end while

end

Các hằng số của mỗi chu kỳ hoàn toàn độc lập với giá trị Nk và được xác định bằng Rcon[i] = (RC[i], {00}, {00}, {00}) với RC[i] ∈ GF(2⁸) và thỏa:

RC[1]=1 ({01})

RC[i] =x ({02})•(RC[i-1]) = x⁽ⁱ^–¹⁾

Khóa của vòng thứ i được xác định bao gồm các từ (4 byte) có chỉ số từ Nb*i đến Nb*(i +1)－1 của bảng mã khóa mở rộng. Như vậy, mã khóa của chu kỳ thứ i bao gồm các phần tử w[Nb*i], w[Nb* i +1] ,…, w[Nb*(i+1)－1] . Các khóa vòng được miêu tả ở hình 7.38.

Hình 7.38. Miêu tả khóa vòng

Độ bền vững của thuật toбn:

Khắc phục được điểm yếu của khуa DES

Thбm mг vi sai (diffrential cryptanalysis): cбc tấn cфng vi sai lа cу thể nếu cу thể dự đoбn được sự sai khбc lan truyền trкn tất cả cбc vтng mа cу tỉ số lan truyền lớn hơn đбng kể 2^1-n, với n lа độ dаi của khối dữ liệu. Trong AES với 4 vтng đưa ra, tỉ số lan truyền khoảng 2^-150 vа với 8 vтng lа khoảng 2^-300. Vм vậy nу đủ nhỏ để chống lại thбm mг vi sai.

Thбm mг tuyến tнnh (linear cryptanalysis): với AES tương qua vаo ra qua 4 vтng vаo khoảng 2^-75 vа qua 8 vтng lа 2^-150. Vм vậy nу đủ nhỏ để chống lại thбm mг tuyến tнnh.

Ưu điểm vа hạn chế:

Ưu điểm:

Phương diện thực hiện:

AES cу thể được thực hiện để lаm việc tại tốc độ rất nhanh (đối với một thuật toбn mг khối) trкn bộ vi xử lэ Pentium (Pro).

AES cу thể được thực hiện trкn một Smart card với 1 số lượng nhỏ của chỉ thị (code), sử dụng нt RAM vа tiкu tốn нt chu kм thời gian.

Vтng biến đổi song song bởi thiết kế, đвy lа một ưu điểm quan trọng cho cбc bộ vi xử lэ song song vа dаnh cho phần cứng chuyкn dụng.

Trong thuật toбn khфng sử dụng cбc phйp toбn số học, nу khфng ảnh hưởng đến giới hạn trкn hoặc dưới của cấu trъc bộ vi xử lэ.

Tнnh đơn giản thực hiện:

Thuật toбn mг hoаn toаn “tự hỗ trợ”. Nу khфng sử dụng cбc thаnh phần của thuật toбn mг khбc.

Tнnh bн mật của thuật toбn khфng dựa trкn sự khфng rх rаng.

Thiết kế kнn của thuật toбn khфng cho phйp cу đủ cơ hội để che giấu một cửa sập.

Độ dаi của khối dữ liệu:

128 bнt lа phщ hợp với cбc yкu cầu hiện tại của cбc ứng dụng trong thực tế.

Khả năng mở rộng:

Khả năng sử dụng khуa với cбc độ dаi khуa 128, 192, 256 cho phйp thuật toбn đбp ứng được một phạm vi rộng về cбc mức độ bảo mật.

Giới hạn:

Phần giải mг нt phщ hợp để thực hiện trкn Smart card hơn phần mг hуa, nу yкu cầu nhiều chỉ thị vа số chu kм thực hiện nhiều???.

Trкn phần mềm: mг vа giải mг sử dụng cбc chỉ thị vа/hoặc cбc bảng khбc nhau.

Trкn phần cứng: giải mг chỉ sử dụng một phần mạch đг được thiết kế thực hiện cho mг hуa.

Các chế độ mật mã khối

Trong các phần vừa qua chúng ta trình bày các thuật toán mã khối. Rõ ràng để mã một bản tin/bản mã có độ dài lớn hơn kích thước khối của thuật tóan, thì chúng ta phân chia ra từng khối có kích thước với khối của thuật toán và tiến hành mã/giải mã theo thứ tự.

Đối với thuật toán mã khối thì nó làm việc với các chế độ khác nhau. Các chế độ này đảm bảo được các tính chất cần thiết của mã khối, ví dụ như tính ngẫu nhiên, khả năng san bằng bản tin ban đầu đến một kích thước bất kỳ (để chiều dài bản mã không có quan hệ với bản tin ban đầu), kiểm tra sự lan truyền của lỗi, tạo ra khóa chạy cho mã dòng…vv.

Tồn tại 5 chế độ: Chế độ mã thay thế (ECB - Electronic Code Book), Chế độ móc nối khối (CBC - Cipher Block Chaining), Chế độ hồi tiếp theo bản mã (CFB - Cipher Feedback), Chế độ hồi tiếp theo đầu ra (OFB - Output Feedback) và chế độ đếm (CRT-Counter). Để miêu tả các chế độ, chúng ta sử dụng các ký hiệu sau:

E(): thuật toán mã hóa tương ứng với mã khối.
D(): thuật toán giải mã tương ứng với mã khối.
n: kích thước khối tin ở dạng nhị phân.
-m các đoạn bản tin ban đầu, ở đây ta lưu ý:
Nếu như bản tin thứ m có độ dài ngắn hơn kích thước khối chuẩn thì ta thêm vào các bít để đạt kích thước chuẩn.
Trong một số chế độ kích thước của đoạn bản tin bằng n, nhưng trong một số chế độ khác có thể không vượt số n.
: m các đoạn bản mã, đây là kết quả ứng dụng các chế độ mã xác định.
LSB_u(B),MSB_v(B) tương ứng là u bít thấp, và v bít cao của khối B.
A||B là kệnh nối 2 khối A và B.

Chế độ mã thay thế (ECB - Electronic Code Book).

Một cách mã hóa (hay giải mã) đơn giản nhất là mã (giải mã) từng đoạn bản tin (bản mã), các đoạn này độc lập nhau với một khóa K. Chế độ ECB xác định như sau:

Mã hóa ở chế độ ECB: .

Giải mã ở chế độ ECB: .

ECB là chế độ đơn giản nhất của mã khối, nó thường được sử dụng khi cần truyền an toàn các thông tin có dung lượng nhỏ (ví dụ, mã hóa khóa). Chế độ này có nhược điểm là độ an toàn không cao, vì rằng đối thủ có thể dựng lại các bản mã từ các bản mã gốc. Nhưng khi hoạt động ở chế độ này, sơ đồ mã có khả năng dung lỗi chống lại lỗi của bản mã (chỗ các bit bị thay đổi) và lỗi đồng bộ hóa (chỗ các bit có thể được thêm vào hoặc mất đi). Ở chế độ này các thuật toán mã có thể hoạt động với tốc độ cao nhất (nó có khả năng mã hóa song song các khối dữ liệu).

Chế độ móc nối khối (CBC - Cipher Block Chaining).

Ở chế độ này bản tin cũng được chia thành các khối . Trước khi mã hóa, khối được cộng từng bit theo module 2 với khối mã C_i-1 vừa nhận được trước đó. Trong trường hợp i=1 thì C_i-1 = C₀ = IV là một hằng số, được gọi là véc tơ khởi tạo, nó là n bít ngẫu nhiên, véc tơ này như một khối mã, nên cũng không bắt buộc là bí mật. Như vậy, giá trị của khối mã C_i không chỉ phụ thuộc vào giá trị của khối rõ mà còn phụ thuộc vào giá trị của khối mã trước nó C_i-1. Đây cũng là lời giải thích cho tên gọi chế độ móc nối khối. Vì tính kết nối này nên kết quả của quá trình mã là một khối mã ngẫu nhiên, và nó bao gồm m+1 khối dữ liệu n bít. Chế độ này được miêu tả ở hình 7.39. Ở chế độ này được hiện bởi các lệnh sau:

Mã hóa ở chế độ CBC:

Đầu vào: IV, ;

Đầu ra: IV, ;

Giải mг ở chế độ CBC:

Đầu vаo: IV, ;

Đầu ra: IV, ;

Hình 7.39. Chế độ mã CBC

Chế độ CBC thường được sử dụng nhất của mг khối, nу thường được sử dụng khi truyền cбc khối dữ liệu hoặc dщng để xбc thực, vм sau khi giải mг, người nhận cу thể thực hiện lại quб trмnh mг hуa bản tin thu được (sử dụng cщng khуa K vа vector IV của người gửi), nếu khối C_N thu được sau mг hуa trщng với khối C_N trong bản mг nhận được từ phнa người gửi thм coi như bản mг khфng bị sai lệch trong quб trмnh gửi. Khi lаm việc ở chế độ nаy, cбc sơ đồ mг cу nguy cơ bị lộ thфng tin do kiểu tấn cфng “nghịch lэ ngаy sinh nhật”. Với khả năng chống lại lỗi bản mг thм một bit lỗi truyền sẽ chỉ ảnh hưởng đến việc giải mг của 2 khối tiếp sau. Chế độ nаy khфng cу khả năng chống lại lỗi đồng bộ hуa. Nhược điểm chнnh của cбc thuật toбn khi hoạt động ở chế độ nаy lа nу chỉ cho phйp hoạt động theo dтng liкn tiếp, mа khфng cу khả năng xử lэ song song cбc khối dữ liệu.

Chế độ hồi tiếp theo bản mг (CFB - Cipher Feedback).

Ở chế độ nаy thм bản tin đầu vаo cу kнch thước lа s, với , với sự tham gia của vйc tơ khởi tạo khối với kнch thước n bнt ngẫu nhiкn. Kết quả của quб trмnh mг quay trở về đầu vаo của thuật toбn mг khối, xem hмnh 7.40 Vйc tơ khởi tạo cũng đуng vai trт lа một khối bản mг nкn cũng khфng bắt buộc phải dữ bн mật. Chế độ nаy được thực hiện bởi cбc tập lệnh sau:

Mг hуa ở chế độ CFB:

Đầu vаo: IV, ;

Đầu ra: IV, ;

Giải mг ở chế độ CFB:

Đầu vаo: IV, ;

Đầu ra: IV, ;

Hình 7.40. Chế độ mã CFB

Chъng ta thấy rằng qъa trмnh mг hуa vа giải mг chỉ dщng hаm mг hуa, chнnh vм điều nаy nкn cу thể dщng bất kỳ hаm một chiều nаo. Chế độ CFB cũng giống như chế độ CBC, đoạn bản mг phụ thuộc vаo tất cả cбc đoạn bản tin ban đầu vа vйc tơ khởi tạo.

Chế độ CFB thường được sử dụng khi truyền cбc dтng dữ liệu hoặc dщng để xбc thực. Chế độ nаy cу khả năng khфi phục chống lại lỗi bản mг vа lỗi đồng bộ hуa sau khi truyền một số lượng nаo đу cбc khối dữ liệu.

Chế độ hồi tiếp theo đầu ra (OFB - Output Feedback).

Chế độ này khá giống với chế độ CFB, chỉ khác ở chổ là, kết quả khối quay lại đầu vào của thuật toán mã khối, xem hình 7.41. Ở chế độ này thì véc tơ khởi tạo cần phải n bít và là khối đầu vào. Nó được thể hiện bằng chuổi lệnh sau:

Mã hóa ở chế độ OFB:

Đầu vào: IV, ;

Đầu ra: IV, ;

Giải mг ở chế độ OFB:

Đầu vаo: IV, ;

Đầu ra: IV, ;

Hình 7.41. Chế độ OFB

Ở chế độ nаy thм quб trмnh mг hуa vа giải mг cũng chỉ dщng một hаm mг hуa, nкn cу thể dщng hаm một chiều bất kỳ cho hаm mг. Vа chъng ta thấy rằng kết quả chọn s bнt để cộng từng bнt theo modulo 2 với bản rх chỉ phụ thuộc vаo khуa, vа vйc tơ khởi tạo, nкn nếu biết được vị trн đoạn bản tin thм cу thể giải mг được mа khфng cần xйt đến cбc đoạn tin trước, đều nаy cу thể giъp cho chъng ta sữa lỗi nếu quб trмnh mг bị lỗi, vм thế ở chế độ nаy thường được sử dụng khi truyền dтng dữ liệu trкn cбc kкnh cу. Tuy nhiкn trong chế độ nаy OFB cần phải sử dụng một kкnh tнn hiệu phụ để định kỳ truyền cбc vйc tơ khởi tạo (IV – Initialization vector) từ bкn gửi đến bкn nhận để cу được khả năng tбi đồng bộ.

Chế độ đếm (CTR-Counter).

Chế độ CTR thì các giá trị của đếm sẽ quay về đầu vào tương ứng với thuật toán mã khối, đếm được khởi tạo lúc đầu. Chế độ này có thể biểu diễn bằng chuỗi lệnh sau:

Mã hóa ở chế độ đếm;

Đầu vаo: , ;

Đầu ra: , ;

Giải mг ở chế độ đếm

Đầu vаo: , ;

Đầu ra: , ;

Ở chế độ nаy thм cу ưu việt hơn cбc chế độ CFB vа OFB bởi vм chế độ nаy hoаn toаn đơn giản, vа cho phйp sử lэ song song.

Khi thực hiện cбc thuật toбn mг trong cбc ứng dụng vа dưới cбc điều kiện lаm việc cụ thể, thм người thiết kế phải nắm vững cбc khả năng hoạt động của thuật toбn ở cбc chế độ lаm việc cụ thể. Bởi vм trong cбc chế độ hoạt động nаy, cбc thuật toбn mг sẽ cу khả năng thực hiện cбc giải phбp mг khбc nhau, vа chъng sẽ nhận được cбc ưu điểm hoặc cбc nhược điểm tương ứng với chế độ hoạt động đу. Phвn tнch cбc chế độ lаm việc cụ thể của cбc sơ đồ mг khối ta cу thể thấy được cбc ưu nhược điểm của chъng như sau:

Trong chế độ khфng hồi tiếp, cбc khối dữ liệu cу thể được mг hуa một cбch độc lập với cбc khối khбc. Vм vậy trong chế độ nаy một số khối dữ liệu cу thể được thực hiện mг hуa song song. Cтn trong chế độ hồi tiếp, cбc sơ đồ mг khфng cу khả năng thực hiện mг hуa khối dữ liệu tiếp sau trừ khi khối dữ liệu trước nу đг được xử lэ xong. Vм vậy trong chế độ nаy cбc khối dữ liệu phải được mг hуa một cбch tuần tự. Tuy nhiкn ở chế độ giải mг cбc sơ đồ mг cу thể hoạt động xử lэ song song đối với cả chế độ hồi tiếp vа khфng hồi tiếp.

Dựa trкn cбc đбnh giб, ta thấy rằng việc mг hуa sẽ dữ liệu chủ yếu dựa trкn cбc chế độ hồi tiếp của mг khối như CBC vа CFB. Cтn với chế khфng độ hồi tiếp thường sử dụng chế độ ECB để mг hуa khуa phiкn trong quб trмnh phвn phối khуa.

Phвn tнch kiểm tra vа thống kк thuật toбn

Chúng ta đã biết để đánh giá hiệu quả của một hệ mật chúng ta cần quan tâm đến 4 đặc điểm: Độ bền vững, tốc độ mã, đơn giản khi thực hiện và giá thành thấp. Điều chúng ta quan tâm đầu tiên là độ bền vững của hệ mật. Khi chúng ta tạo ra một hệ mật mới làm thế nào để biết được nó bền vững hay không bền vững? Để trả lời câu hỏi này chúng ta có 2 phương pháp xác định: Phân tích hệ mật với các phương pháp tấn công, phân tích thống kê thuật toán. Vì các phương pháp tấn công chúng ta không thể lường hết các phương pháp mới và có nhiều thuật toán thám mã, nên cách hiệu quả để đánh giá hệ mật là phân tích và thống kê thuật toán.

Tiêu chí đánh giá tính chất “hiệu ứng thác lũ”

Để phân tích kết quả xử lý thống kê thuật toán mã khối tổ chức NESSIE (New European Schemes for Signatures, Integrity and Encryption) của Châu Âu đề xuất những tiêu chí sau đây:

Số lượng bít ở đầu ra bị thay đổi khi thay đổi một bít của véc tơ đầu vào.
Bậc biến đổi hoàn toàn.
Bậc hiệu ứng thác lũ.
Bậc ứng với hiệu ứng thác lũ chặc chẽ.

Đặt U⁽ⁱ⁾ = U

E_i – là một véc tơ nhị phân nhận được khi thay đổi một bít thứ i của véc tơ U. Lúc này véctơ nhị phân Y⁽ⁱ⁾ = F(U⁽ⁱ⁾)

F(U) được gọi là véctơ thác lũ theo thành phần i. Đối với một mã khối thì U = X║K. Để xem các tiêu chí, chúng ta giả sử U có chiều dài là n và Y có chiều dài là m.

Ở tiêu chí 2 và 4 chúng ta sử dụng ma trận phụ thuộc ║a_ij║_n×m, với:

Ma trận ║a_ij║_n×m cho chúng ta biết sự phụ thuộc của bít thứ j của véctơ đầu ra vào bít thứ i của véctơ đầu vào. Lúc này thì bậc biến đổi hoàn toàn được đánh giá qua công thức sau:

Còn bậc tương ứng với tiêu chí thác lũ chặc chẽ xác định theo công thức sau:

Với N = #U = #{U}.

Để nhận được đбnh giб một cбch chнnh xбc cần phải lựa chọn tất cả cбc giб trị của vйctơ U, thế nhưng vйctơ U cу kнch thước lớn thм khфng thể lựa chọn tất cả hết cбc giб trị của nу, để tнnh giб trị gần đъng chъng ta nкn dщng phương phбp Monte Carlo.

Ở tiкu chн 1 vа 3 chъng ta sử dụng ma trận khoảng cбch Hamming ║b_ij║_nЧm, với:

Số lượng bнt trung bмnh thay đổi khi thay đổi một bнt của vйctơ đầu vаo được đбnh giб theo cфng thức sau:

Cтn bậc hiệu ứng thбc lũ được xбc định theo cфng thức sau:

.

Đánh giá ảnh hưởng các bít của bản rõ đối với bản mã

Các tiêu chí đánh giá ảnh hưởng các bít của bản rõ đối với bản mã nhằm xem xét điểm yếu của thuật toán, các tiêu chí này có thể sử dụng phương pháp thám mã trên cơ sở lựa chọn bản rõ hoặc hay phương pháp thám mã vi sai. Trong trường hợp này véctơ thác lũ Y⁽ⁱ⁾ được hình thành theo véctơ đầu vào U = X║K и U⁽ⁱ⁾ = X⁽ⁱ⁾║K, где X⁽ⁱ⁾ = X E_i.

Trong số cбc tham số đưa ra cбc giб trị: q lа số lượng khуa được chọn, t lа số lượng bản tin được chọn thм N = qt. Việc lựa chọn q vа t phụ thuộc vаo giб trị của n vа m. Ma trận phụ thuộc ║a_ij║_nЧm vа ma trận khoảng cбch Hamming ║b_ij║_nЧm cу dạng sau:

Để tạo kết quả chính xác thì việc lựa chọn khóa và bản tin cần phải ngẫu nhiên.

Trong trường hợp này thì véctơ thác lũ Y⁽ⁱ⁾ được hình thành theo véctơ đầu vào U = X║K và U⁽ⁱ⁾ = X║K⁽ⁱ⁾, где K⁽ⁱ⁾ = K E_i. Trong các tiêu chí thì ma trận phụ thuộc ║a_ij║_n×m và ma trận khoảng cách Hamming║b_ij║_n×m có dạng sau:

Chъng ta cần chъ э rằng cбc tiкu chн đг xem xйt lа cфng cụ hiệu quả đối với việc xem xйt điểm yếu của thuật toбn, cũng như xem hiệu quả của cбch miкu tả khуa, vа qua đвy chъng ta biết được thuật toбn chъng ta nкn chọn số vтng lа bao nhiкu để đạt hiệu quả.

Chъ э: Ngoаi ra để thiết lập quan hệ giữa cбc mф hмnh lэ thuyết vа thực hаnh người ta cтn đưa ra tiкu chн ở đвy chъng ta khфng xem xйt.

Thám mã véc cạn khóa

Giả sử rằng kẻ gian có được một hoặc một số cặp (x,y). Gỉa sử rằng đối với một cặp (x,y) bất kỳ thì tồn tại một khóa k duy nhất thỏa mãn

. Chúng ta sắp xếp tập hợp không gian khóa và lần lượt kiểm tra các khóa từ tập khóa K xem sự thỏa mãn biểu thức

. Nếu như xem một lần kiểm tra khóa

là một lệnh thì việc véc cạn khóa cần #K lệnh, ở đây #K là số lượng phần tử của tập K. Giả sử rằng khóa k trong sơ đồ mã hóa được chọn ngẫu nhiên và khả năng như nhau từ tập K. Như vậy xác suất đoán được khóa k là

, và độ khó của phương pháp véc cạn sẽ bằng 1. Cho nên để đánh giá độ khó của phương pháp ta chọn kỳ vọng toán học của độ lớn ngẫu nhiên

, ở đây

là số phép thử trước thời điểm tìm được khóa sử dụng. Bởi vì

là độ lớn ngẫu nhiên phân bố đều, nên M(

Thuật toán véc cạn cho phép thực hiện song song, bời vì điều này nên có thể tăng tốc đáng kể quá trình tìm khóa. Có hai hướng trong quá trình tính toán khóa song song.

Một là, xây dựng dây chuyền. Cho thuật toán của biểu thức được biểu diễn dưới dạng dây chuyền cố định các lệnh .

Chọn N quá trình , sắp xếp theo thứ tự và cho quá trình thứ i hoàn thành 3 lệnh như nhau theo thời gian:

Nhận dữ liệu thứ (i-1) quá trình;
Hoàn thành lệnh ;
Chuyển dữ liệu cho quá trình thứ (i+1);

Như vậy dây chuyền gồm N quá trình được liên kết nối tiếp nhau làm việc song song, đồng bộ làm việc với tốc độ

là tốc độ hoàn thành 1 lệnh của quá trình.

Hướng thứ hai là tập khóa K được phân nhỏ ra thành các tập không giao nhau . Hệ thống gồm Q máy thực hiện việc lựa chọn khóa, máy thứ i thực hiện việc lựa chọn khóa từ tập . Hệ thống ngừng làm việc nếu như có một máy tìm được khóa. Điều phức tạp nhất của phương pháp là tổ chức phân chia tập khóa. Thế nhưng nếu tổ chức việc tìm kiếm khóa như vậy thì trong mỗi lần thí nghiệm thì một trong N quá trình sẽ trở nên ngẫu nhiên, thời gian thí nghiệm sẽ tăng nhưng tốc độ của sơ đồ lại tăng lên đáng kể. Số bước thí nghiệm thực hiện N quá trình trong trường hợp này là .

Việc thực hiện xử lý song song như vậy phải có các cách giải quyết khác nhau. Một trong các cách được ưu tiên đó là tạo ra virut máy tính để phân bố chương trình trong mạng nội bộ.Virut cần sử dụng chu kỳ dừng của máy tính để thực hiện việc tìm kiếm theo tập khóa. Sớm hay muộn thì một trong các máy nhiểm virut sẽ tìm được khóa cần tìm. Với sự lớn của công suất máy tính cũng như tốc độ lây lang virut thì khả năng thành công của phương pháp này ngày một tăng.

Thám mã bằng phương pháp thống kê

Mục đích của phương pháp thám mã thống kê là xử lý thuật toán nhằm tìm khóa chưa biết (hoặc một phần khóa)

. Chúng ta xem các nguyên tắc cơ bản và định nghĩa của phương pháp thống kê đối với mã khối.

Thực hiện phương pháp thám mã thống kê nhằm xác định khóa mật đối với mã khối cho phép nhận được đánh giá hiệu quả thuật toán hơn là phương pháp véc cạn khóa. Đầu vào là mốt số cặp (X_i,Y_i), i=1,…,N bản rõ và bản mã, bản mã thu được bằng cách ứng dụng ánh xạ F với khóa k. Các cặp như vậy được gọi là “tư liệu” và ký hiệu là M. Dung lượng của tư liệu tương ứng với số cặp (X_i,Y_i): . Giả sử rằng các bản rõ Xi, i=1,…,N được chọn ngẫu nhiên, đồng khả năng và độc lập từ không gian .

Quá trình thống kê phân loại là phần quan trọng nhất của phương pháp phân tích thống kê, quá trình này dùng để tìm các tham số chưa biết theo quan sát ngẫu nhiên. Hàm phân bố xác suất để quan sát phụ thuộc vào tham số mật này. Ý tưởng của quá trình thống kê phân loại thể hiện ở chổ, nếu như sự phận bố xác suất này mà khác nhau thì khi số lượng quan sát đủ lớn thì có thể xác định được định luật phân bố quan sát và từ đó có thể xác định tham số cần tìm.

Chúng ta ký hiệu tập hợp ở đó nhận giá trị của tham số chưa biết là .

Mỗi quá trình thống kê phân loại được xác định sự phân chia tất cả không gian quan sát M ra T phần không giao nhau: với . Vùng gọi là vùng chọn nghiệm. Đối với từng vùng M_i quá trình thống kê phân loại cũng xác định danh mục thứ thự s’ thành phần của tập hợp , lúc này với.

Để xác định thành phần chưa biết từ tập cần thực hiện các lệnh sau. Đầu tiên theo sự quan sát nhận được cần xác định số thứ tự vùng chọn nghiệm i(m). Sau đó lựa chọn lần lượt các tham số từ tập và kiểm tra xem giá trị của tham số thứ j (j=1…s’) có phải là cần tìm hay không.

Thám mã vi sai

Thám mã vi sai là một trong các phương pháp phân tích cơ bản và hiệu quả nhất đối với mã khối. Phương pháp mã vi sai đươc đưa ra năm 1990 bởi các nhà nhà toán học E. Biham và Shamir. Đây là phép tấn công với việc chọn bản rõ chọn lọc, để tìm ra khóa mật hay một phần khóa mật.

Định nghĩa: Cho cặp hai véc tơ X, X*

. Khoảng cách giữa hai véc tơ hay còn gọi là hiệu giữa hai véc tơ được xác định bằng lệnh XOR:

.

Định nghĩa: Vi sai của vòng mã thứ i được xác định bằng cặp véc tơ (

), sao cho cặp bản rõ (x,x’) có hiệu bằng

có thể đi qua i vòng mã, đầu ra là cặp bản mã (y,y’) với hiệu của chúng là

Xác suất vi sai của vòng mã thứ i- đó là xác suất có điều kiện, sao cho hiệu của cặp bản mã (y,y’) sau i vòng mã bằng với điều kiện là cặp bản rõ tương ứng (x, x’) có hiệu khoảng cách là , khi bản rõ x và các khóa k(1), k(2),…,k(i) sử dụng tương ứng trong các vòng 1,2,…,i là độc lập và đồng khả năng, có nghĩa là

lúc này xác suất phân bố vi sai đối với từng vòng là không đổi và không phụ thuộc vào vòng trước.

Giá trị vi sai ở đầu ra của vòng mã thứ i được sử dụng để tìm kiểm khóa con của vòng mã cuối cùng tức là vòng thứ i+1 bằng cách như sau:

Đối với từng cặp bản rõ –mã ta giả sử rằng giá trị vi sai đầu ra của vòng mã thứ i là . Tiếp theo để giá trị này và giá trị của cặp bản rõ –mã tìm được những giá trị có thể của khóa con trong vòng mã cuối i+1 cùng, tức là hình thành một số tập hợp khóa con mà nó thỏa mã điều kiện trên. Lúc này thì một phần trong các tập hợp là khóa đúng. Đối với tất cả tập hợp giá trị có thể của khóa vòng, chúng ta thiết lập bảng tần số xuất hiện của chúng. Tấn công sẽ thành công khi giá trị đúng của khóa vòng xuất hiện thường xuyên hơn các giá trị khác.

Trong trường hợp này có thể tính toán biểu thức tương quan giữa số lương cặp giá trị giả sử đúng và số lượng trung bình các phương án có thể của khóa vòng trong bảng tần số.

Biểu thức này được gọi là biểu thức tín hiệu – tiếng ồn S/N (Signal to noise). Nếu như kích thước bảng phương án của khóa vòng là , ở đây l là chiều dài của khóa vòng, còn số lượng trung bình các phương án là thì biểu thức S/N được viết:

(7.1)

Biểu thức (7.1) ảnh hưởng rất lớn lên số lượng cặp bản mã và rõ đúng mà số lượng này cần thiết để xác định một khóa vòng.

Thuật toán thám mã vi sai

Quá trình cơ bản của thuật toán thám mã vi sai r vòng mã sử dụng bản rõ chọn lọc, diễn ra như sau:

Đầu vào: thuật toán mã hóa, bản rõ chọn lọc và bản mã tương ứng.

Đầu ra: khóa.

1. Ở bước đầu tiên của tính toán chúng ta tìm tập hợp vi sai của cho vòng mã thứ , với, sao cho xác suất lớn nhất hoặc gần lớn nhất. Lúc này bản rõ X và tất cả khóa con đối với vòng mã là độc lập và đồng khả năng. Sắp xếp chúng theo thứ tự tăng dần của xác suất.

2. Đối với một bản rõ bất kỳ x chúng ta tính bản rõ x’ sao cho hiệu khaỏng cách giữa x và x’ bằng . Mã hóa bản rõ x và x’ trên khóa cần tìm và sau r vòng thu được cặp bản mã . Giả sử rằng đầu ra của vòng mã thứhiệu khoảng cách của các bản mã có xác suất lớn nhất:. Từ bộ bachúng ta tìm ra tất cả giá trị có thể của khóa.

3. Lặp lại bước 2 cho đến khi có một hoặc một số giá trị của khóa con к^(r) không ngừng xuất hiện thường xuyên các giá trị khác. Chúng ta xem khóa này hoặc một tập khóa này là nghiệm mã hóa đối với khóa của vòng mã cuối cùng.

4. Chúng ta lặp lại các bước từ 1-3 đối với vòng mã kề cuối, lúc này giá trị được tính bằng cách giải mã bản mã trên khóa tìm được. Chúng ta thực hiện tương tự để tìm ra các khóa vòng còn lại.

Hiệu quả của thuật toán phụ thuộc vào độ lớn và sự phân bố tập hữu hạn vi sai sau vòng mã, có nghĩa là biểu thức S/N. Xác suất vi sai càng nhỏ và càng phân bố đều giữa chúng thì càng khó xác định giá trị khóa .

Từ thuật toán chúng ta thấy rằng, điều kiện cần để thám mã vi sai r vòng mã thành công là tồn tại vi sai của vòng mã thứ (r-1), mà xác suât xuất hiện của chúng lớn hơn rất nhiều so với 2^－^m.

Điều này có nghĩa là, để phân tích khả năng thực hiện tấn công vi sai, cũng như đánh giá hiệu quả của phương pháp, cần phải biết được giá trị lớn nhất của xác suất vi sai sau một số vòng mã.

Xác suất lớn nhất của vi sai được sử dụng để xác định giới hạn dưới của độ phức tạp tấn công vi sai và có thể chứng tỏ rằng r vòng mã sẽ không bị tổn thương bởi phép tấn công này.

Đối với mật mã có vi sai không phụ thuộc vào sự lựa chọn bản rõ, nếu các khóa con của các chu kỳ độc lập nhau thì dãy các khoảng cách sau từng chu kỳ tạo thành chu trình Markob. Lúc này xác suất thu được vi sai của vòng thứ s được xác định:

P(y(s)=_s | x= )=.

Đối với cặp vi sai đã cho xác suất để thu được cặp này lớn hơn nhiều so với :

P(y(i)= | x= )=,

với m là kích thước của khối mã.

Độ phức tạp bẻ khóa của vòng thứ r mật mã là Q(r) được xác định bắng số lệnh mã sử dụng trong qúa trình tìm khóa:

Q(r)2/ (P_max - 1/(2^m-1)),

ở đây:

P_max=max( )max( )(P(y(r-1)= | x= )),

Trong số đó nếu P_max

1/(2^m-1), thì việc tấn công được xem là không thành công.

Thám mã tuyến tính

Ý tưởng của phương pháp tuyến tính lần đầu tiên được chuyên gia người Nhật M. Matsu đưa ra năm 1992. Phương pháp này được cho là một trong các phương pháp phân tích hiện đại và hiệu quả đối với mã khối. Phương pháp dựa trên tập bản rõ và bản mã tương ứng để tìm ra khóa mật.

Thám mã tuyến tính là một trường hợp của phương pháp thám mã thống kê tổng quát trên cơ sở sử dụng biểu thức sau:

, (7.2)

ở đây a, b  V_n, c  V_m, 0≤ t₁≤ t₂ ≤ r (ở đây cặp véc tơ (a, b) được gọi là đặc trưng tuyến tính) . Lệnh là tích vô hướng giữa hai véc tơ a và b cùng kích thước.Ở phương pháp thám mã tuyến tính chỉ sử dụng biểu thức kiểu (7.2), xác suất để thu được biểu thức này khác với ½ và có thể viết dưới dạng:

, (7.3)

ở đây .số ε gọi là ưu thế (deviation, bias).

Hiệu quả của phương pháp thám mã tuyến tính càng lớn nếu như trị tuyệt đối của ε càng lớn. Cho nên khi xây dựng một thuật toán cụ thể xác định khóa bằng phương pháp thám mã tuyến tính thì nhiệm vụ đặt ra là tìm các véc tơ a, b  V_n, c  V_m, để giá trị tuyệt đối của có thể lớn nhất: . Lúc này thì hiệu quả và độ khó của phương pháp được xá định bằng độ lớn đã cho |ε|, có nghĩa là để xây dựng các véc tơ a, b  V_n, c  V_m, cần biết đánh giá |ε| trong biểu thức (7.3).

Chúng ta xem một phương án đơn giản nhất (không phải hiệu quả nhất) của thám mã tuyến tính – đó là thuật toán xác định một bít khóa, được gọi là thuật toán 1 Masui. Thuật toán này sử dụng biểu thức (7.2) với t₁=0 và t₂=r, có nghĩa là biểu thức (7.2) được viết lại dưới dạng bản rõ và bản mã như sau:

ở đây cặp véc tơ (X_i, Y_i) là căp bản rõ và bản mã mà thám mã biết. Phương pháp thám mã vi sai tương ứng với phương án đã cho xác định tổ hợp tuyến tính các bít khóa. Tập hợp công sức được tính:

Quá trình phân loại thống kê phân chia tất cả không gian quan sát M ra hai phần M₀ và M₁ (: Đối với vùng M₀ tương ứng với , còn vùng M₁ ứng với . Thuật toán sử dụng nguyên tắc sự hợp lý cực đại: Nếu như và trong biểu thúc (7.3) hoặc và trong biểu thức (7.3) , thì thuật toán đưa ra giá trị , trong trường hợp ngược lại thì . Các bít khóa còn lại xác định theo phương pháp véc cạn.

Hệ mã dòng RC4

Thuật toán RC4.

Đây là một hệ mã dòng, với chiều dài khóa biến đổi, tác giả của nó là Ronald Rivest, được nêu ra năm 1987.

Hạt nhân của thuật toán là thủ tục tạo khóa dòng, xem hình 7.42, hàm này tạo dãy bít sau đó cộng với bản tin theo modulo 2 với bản rõ ta thu được bản mã, và khi giải mã thì cũng sinh ra mã dòng, rồi cộng với bản mã theo từng bít ta thu được bản rõ ban đầu. RC4 làm việc ở chế độ OFB. Gọi k là giá trị mã dòng được sinh. Việc sinh mã dòng được thực hiện trên cơ sỡ khối hoán đổi kích thước 8x8 : S[0],...S[255]. Khối hoán đổi là phép hoán vị các số 0,…, 255 phụ thuộc vào khóa, được thực hiện bởi các lệnh sau:

3. Hoán đổi giá trị của S[i] và S[j]

4. Tính tổng S[i] và S[j], gán cho t: t= (S[i] + S[j]) mod 256

5. k=S[t].

Hình .7.42. Sơ đồ tạo khóa dòng k

Trong quá trình sử dụng, bộ đếm i sẽ làm cho nội dung của khối S thay đổi chậm, còn bộ đếm j sẽ đảm bảo sự thay đổi này là ngẫu nhiên.

Byte k được tạo ra cộng với byte của bản rõ để tạo ra byte bản mã.

Một phần chính của thuật toán nữa là khởi tạo khối hoán đổi S, việc khởi tạo được thực hiện các bước sau:

Gán cho mỗi phần tử giá trị bằng chỉ số của nó: S[0]=0,…,S[255]=255.
Tạo một mảng key gồm 256 phần tử, mỗi phần tử có kích thước 1 byte. Điền đầy mảng key bằng các byte của khóa K, nếu mảng key chưa điền đầy thì lặp lại mốt số bye của khóa K.
Xбo trộn khối S:
i = 0..255
j = (j + S[i] + key[i]) mod 256
Hóan đổi giá trị: S[i] ↔ S[j]

Những ưu điểm chính của RC4
Thuật toán đơn giản. Ý nghĩa của từng bước rõ ràng, logic.
RC4 tỏ ra an toàn đối với cả 2 phương pháp thám cơ bản là thám tu‎yến tính và thám vi phân (chưa có công trình nào về thám RC4 được công bố) . Số trạng thái mà RC4 có thể có là 256!×256×256 » 2¹⁷⁰⁰.
Tốc độ mг đạt rất cao. Ví dụ so với DES thì RC4 nhanh gấp 10 lần.
Có thể khía quát thuật toán trên cơ sở từ có chiều dài lớn và kích thước khối hoán đổi lớn, ví dụ 16x16.

Mã dòng WAKE

Đây là thuật toán mã dòng, tác giả của WAKE là Devit Uyler. Ở đầu ra nhận được chuỗi từ 32 bнt. WAKE lаm việc ở chế độ CFB – từ trước của bản mг được dщng để tạo ra từ tiếp theo bằng chuỗi khуa.

Trong thuật toбn sử dụng khối hoбn đổi đặc biệt S gồm 256 từ 32 bнt. Ở đвy cбc bytes cao của từ lа hoбn đổi cбc số từ 0 đến 255, cтn 3 bytes thấp được chọn ngẫu nhiкn.

Ban đầu khối hoбn đổi được khởi tạo trкn cơ sở khуa. Sau đу 4 thanh ghi A, B, C vа D được khởi tạo bằng giб trị ban đầu, cũng phụ thuộc vаo khуa: . Từ tiếp theo của khуa dтng nhận được theo cфng thức .

Sau bước nаy thм giб trị của cбc thanh ghi bị thay đổi:

Với

Thuật toбn nаy cу tốc độ lớn mặc dầu nу khфng vững chắc với phйp tấn cфng theo phương phбp chọn bảng rх ban đầu.

Каталог: files -> FileMonHoc
FileMonHoc -> NGÂn hàng câu hỏi lập trình cơ BẢn nhóm câu hỏI 2 ĐIỂM
FileMonHoc -> CHƯƠng 2 giới thiệu về LÝ thuyết số
FileMonHoc -> CÁc hệ MẬt khoá CÔng khai kháC
FileMonHoc -> BỘ MÔn duyệt chủ nhiệm Bộ môn
FileMonHoc -> Khoa công nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam
FileMonHoc -> Chủ nhiệm Bộ môn Ngô Thành Long ĐỀ CƯƠng chi tiết bài giảNG
FileMonHoc -> Chủ nhiệm Bộ môn Phan Nguyên Hải ĐỀ CƯƠng chi tiết bài giảNG
FileMonHoc -> Khoa: CÔng nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam
FileMonHoc -> Khoa công nghệ thông tin bài giảng LẬp trình cơ BẢn biên soạn
FileMonHoc -> Khoa cntt cộng hòa xã HỘi chủ nghĩa việt nam

tải về 1.46 Mb.

Chia sẻ với bạn bè của bạn:

1 2 3 4 5

MẬt mã khóA ĐỐi xứng lý thuyết cơ bản của Shannon

Những ưu điểm chính của RC4