MẬt mã khóA ĐỐi xứng lý thuyết cơ bản của Shannon

Tạo khóa con

Giả sử khóa chính có độ dài T bytes (1 ≤ T ≤ 128). Trong RC2 có dự trù sẵn một thủ tục cho phép làm giảm độ phức tạp của khóa đối với mã thám. Thủ tục này được sử dụng trong trường hợp sản phẩm được dành để xuất khẩu. Ở đây chúng ta sẽ không xem xét thủ tục này. Việc tạo khóa con được thực hiện bằng cách sao chép khóa chính (T bytes) vào mảng L (128 bytes). Sau đó giá trị mảng L được thay đổi với sự trợ giúp của mảng giả ngẫu nhiên P[0..255], mỗi phần tử P[i] có kích thước 1 bytes. Mảng P được sinh ra bằng cách sử dụng các chữ số thập phân của số π. Phép biến đổi này có thể được mô tả như sau:

Khi i chạy từ T đến 127 thực hiện:

L[i] = P[L[i-1] + L[i-T]]

L[128-T] = P[L[128-T]]

Khi i chạy từ 127-T về 0 thực hiện L[i]=P[L[i+1] L[i+T]]

Khối bản tin đầu vào 64 bít được biểu diễn dưới dạng 4 từ 16 bits: R[0], R[1], R[2], R[3] và kết quả đầu ra được ghi vào chính các từ này. Thuật toán RC2 chứa 18 vòng, 16 vòng “xáo trộn” (mixing round) và và 2 vòng “nghiền nát” (mashing round), chúng ta đi tìm hiểu hai vòng này dành cho quá trình mã hóa.

Vòng Mixing round hình thành từ 4 thủ tục con MIX transformation, thủ tục MIX transformation, thủ tục này miêu tả ở hình 7.18.

Hình 7.18. Thủ tục MIX - transformation

Vòng mixing round có thể biểu diễn dưới dạng công thức sau:

R[0] = R[0] + K[j] + (R[3] ^ R[2]) + (NOT(R[3]) ^ R[1])

R[0] = R[0] <<< 1

j=j+1
R[1] = R[1] + K[j] + (R[0] ^ R[3]) + (NOT (R[0]) ^ R[2])

R[1] = R[1] <<< 2
j=j+1
R[2] = R[2] + K[j] + (R[2] ^ R[0]) + (NOT (R[1]) ^ R[3])
R[2] = R[2] <<< 3
j=j+2
R[3] = R[3] + K[j] + (R[2] ^ R[1]) + (NOT (R[2]) ^ R[0])
R[3] = R[3] <<< 5
j=j+3

Mashing round.

4 từ R[0], R[1], R[2], R[3] được biến đổi bằng cách cộng với khóa con, ở đây việc chọn khóa con K[j] phụ thuộc vào giá trị biến đổi dữ liệu:

R[0] = R[0] + K[R[3] & 63];
R[1] = R[1] + K[R[0] & 63];
R[2] = R[2] + K[R[1] & 63];
R[3] = R[3] + K[R[2] & 63];

Quá trình mã hóa

Sau khi định nghĩa mixing round và mashing round, ta đã có thể mô tả quá trình mã hóa của RC2. Nó bao gồm các bước sau đây (trong dấu ngoặc là giá trị của j sau khi thực hiện các chu kỳ tương ứng):

1. 
   giá trị cho j=0.
   
2. 
   Thực hiện 5 mixing rounds (j=20).
   
3. 
   Thực hiện 1 mashing round.
   
4. 
   Thực hiện 6 mixing rounds (j=44).
   
5. 
   Thực hiện 1 mashing round.
   
6. 
   Thực hiện 5 mixing rounds (j=64).
   

Quá trình giải mã thực hiện giống như quá trình mã hóa, nhưng các phép toán trong quá trình giải mã thì ngược với quá trình mã hóa. Tức là 2 vòng Mixing round và Mashing round được viết lại như sau:

Vòng mixing round có thể biểu diễn dưới dạng công thức sau:

R[3] = R[3] - K[j] - (R[2] ^ R[1]) - (NOT (R[2]) ^ R[0])
j=j-1

R[2] = R[2] >>>3

R[2] = R[2] - K[j] - (R[2] ^ R[0]) - (NOT (R[1]) ^ R[3])
j=j-1

R[1] = R[1] >>> 2

j=j-1

R[0] = R[0] - K[j] - (R[3] ^ R[2]) - (NOT(R[3]) ^ R[1])

j=j-1;

Mashing round.

4 từ R[0], R[1], R[2], R[3] trong quá trình giải mã thực hiện như sau:

R[2] = R[2] - K[R[1] & 63];

R[1] = R[1] - K[R[0] & 63];

R[0] = R[0] - K[R[3] & 63];

Quб trмnh giải mг cũng tiến hаnh trong 18 vтng như sau.

1. Gán giá trị cho j=63.

2. Thực hiện 5 mixing rounds (j=43).

3. Thực hiện 1 mashing round.

4. Thực hiện 6 mixing rounds (j=19).

5. Thực hiện 1 mashing round.

6. Thực hiện 5 mixing rounds (j=0).

Chú ý: các phép toán trong 2 vòng Mixing round và Mashing round đều thực hiện theo modulo.

3. 
   Hệ mật mã khối RC5
   

Trong RC5 quy định một thủ tục phức tạp để tạo t khóa con từ khóa chính K, mỗi khóa con có kích thước w bít. Mỗi chu kỳ sử dụng 2 khóa con. Ngoài ra còn có 2 khóa con được sử dụng trong một phép biến đổi không thuộc bất kỳ chu kỳ nào. Như thế, số lượng khóa con cần tạo là t=2r+2. Các khóa con được lưu trong mảng t phần tử: S[0], S[1], ..., S[t-1], kích thước của mỗi phần tử phụ thuộc vào kích thước khối dữ liệu chọn. Sơ đồ sinh khóa con được miêu tả ở hình 7.19.

Hình 7.19. Quá trình sinh khóa con của RC5

Cụ thể tính ra như sau, các giá trị của ,ở dạng hexa:

w163264B7E1B7E15163B7E151628AED2A6B9E379E3779B99E3779B97F4A7C15Thuật toбn khởi tạo mảng S cу thể biểu diễn như sau:

S[0] = P_w

Với i từ 1 đến t-1 thì thực hiện: S[i] = (S[i-1] + Q_w) (mod )

Bước 2

Khóa chính được lưu trong mảng K[0..b-1] gồm b phần tử, mỗi phần tử có kích thước 1 byte. Biến đổi mảng K thành mảng L[0..c-1] gồm c phần tử, mỗi phần tử có kích thước w bít, giá trị ban đầu của mỗi phần tử bằng 0. Nếu b chia hết w thì c = b/w; nếu b không chia hết w thì c = b/w + 1. Phép biến đổi từ K sang L chỉ đơn giản là sao chép các byte của mảng K sang mảng L theo đúng thứ tự trong K. Trong trường hợp b không chia hết w thì có một số bits bên phải của L sẽ giữ nguyên bằng 0.

Thực hiện một thủ tục “xáo trộn” để kết hợp giá trị mảng L với giá trị khởi tạo của mảng S nhằm xác định giá trị cuối cùng cho mảng khóa con S. Để đạt được điều này cần duyệt 3 lần mảng lớn nhất trong hai mảng L, S:

i = j = X = Y = 0

do 3×max(t,c) times

S[i] = (S[i] + X + Y) <<< 3; X = S[i]; i = (i+1) mod t

L[j] = (L[j] + X + Y) <<< (X+Y); Y=L[j]; j = (j+1) mod c

end

Tác giả RC5 Ron Rivest khẳng định rằng thủ tục sinh khóa con mang tính chất của hàm một chiều – rất khó có thể xác định khóa K khi biết mảng S.

Thuật toán mã hóa được thể hiện trên hình 7.20.a. Mỗi thanh ghi A, B có độ dài bằng w bít. Khối tin trước hết được đưa vào 2 thanh ghi này. Để phân biệt phần trái và phần phải của đầu ra ở chu kỳ thứ i ta sử dụng ký hiệu LE_i và RE_i.

Hình 7.20. Sơ đồ miêu tả quá trình mã hóa và giải mã RC5

Thuật toán

LE₀ = (A + S[0]) (mod );

LE_i = (((LE_i-1 RE_i-1) <<< RE_i-1) + S[2×i]) ]) (mod );

RE_i = (((RE_i-1 LE_i) <<< LE_i) + S[2×i + 1]) ]) (mod );

End

Quá trình giải mã

Từ thuật toán mã hóa có thể dễ dàng suy ra thuật toán giải mã. Sơ đồ thuật toán giải mã được thể hiệnt trên hình 7.20.b). Đầu tiên, 2 từ của khối mã được gán cho 2 biến là LD_r và RD_r – kích thước mỗi biến là 1 từ (w bits). Phần trái và phần phải của của đầu vào ở chu kỳ thứ i ký hiệu là LDi và RD_i, i=1..r.

Thuật toán

For i=r downto r do

begin

RD_i-1 = ((RD_i – S[2×i + 1] >>> LD_i) LD_i) ]) (mod );

LD_i-1 = ((LD_i – S[2×i] >>> RD_i-1) RD_i-1) ]) (mod );

end
B=(RD₀–S[1]) ]) (mod );
A = (LD₀ – S[0]) ]) (mod );

Ưu điểm của RC5

RC5 có 2 ưu điểm nổi bật là:

1. 
   Thực toán đơn giản
   
2. 
   Phép quay là phép biến đổi phi tuyến tính duy nhất trong RC5. Ron Rivest khẳng định rằng việc số bits trong các phép quay phụ thuộc vào giá trị của bản thân khối dữ liệu được xử lý sẽ gây khó khăn rất lớn cho việc thám RC5 bằng phương pháp thám tuyến tính, cũng như thám vi phân.
   

Kết quả nghiкn cứu khả năng tấn cфng RC5 bằng thбm tuyến tнnh (Linear Cryptanalysis) cho thấy RC5 tỏ ra an toаn khi số chu kỳ khфng nhỏ hơn 6. Rivest khuyến cбo sử dụng RC5 với số chu kỳ khфng nhỏ hơn 12, tốt nhất lа 16.

3. 
   Hệ mật mã khối IDEA
   

“Chuẩn mã hóa dữ liệu quốc tế” (IDEA – International Data Encryption Algorithm) là một hệ mật thuộc nhóm mã khối. Nó được xây dựng bởi hai thành viên của Viện công nghệ Thụy Điển là Xuejla Lai và James Massey. Phiên bản đầu tiên được công bố trong [LAI90] vào năm 1990 dưới cái tên PES (Proposed Encryption Standard). Ngay năm sau (1991), sau khi Biham và Shamir công bố phương pháp mã thám mới là “thám vi phân” thì các tác giả đã cải biên thuật toán PES để chống lại phương pháp thám mã đó. Bản cải biên được đặt tên là IPES (Improved PES) và được đổi thành IDEA vào năm 1992. IDEA được mô tả chi tiết trong các ấn phẩm [LAI91] và [LAI92].

IDEA mã hóa và giải mã theo từng khối 64 bits. Khóa có chiều dài 128 bít. Thực hiện trong 9 vòng.

Như đã nói ở trên chiều dài khóa trong IDEA là 128 bits. Nhưng bản thân thuật toán IDEA lại sử dụng đến 52 khóa con với kích thước mỗi khóa là 16 bits. Như vậy cần có một thủ tục để sinh 52 khóa con này từ khóa mẹ 128 bits. Thủ tục thực hiện như sau:

1. Gán i=0

2. 128 bít khóa ban đầu K[1..128] được chia thành 8 phần, mỗi phần 16 bits. Bằng cách đó ta có được 8 khóa con: k_1+i=K[1..16], k_2+i=K[17..32], ..., k_6+i=K[81..96], k_7+i=K[97..112], k_8+i=K[113..128].

3. Dịch K sang trái 25 bít,

4. Nếu chưa sinh đủ 52 khóa con thì i=i+8, quay lại bước 2.

IDEA thực hiện 9 vòng mã, 8 vòng giống nhau, 1 vòng có cấu trúc như hình 7.21.
Hình 7.21. Sơ đồ miêu tả IDEA

Vòng thứ 9 của IDEA có cấu trúc được miêu tả trên hình 7.22.

Quá trình mã hóa được viết dưới dạng thuật toán sau:

Khi i chạy từ 1 đến 8 thực hiện các biến đổi sau:

Đầu ra lа 64 bнt bản mг

Thuật toбn quб trмnh giải mг giống quб trмnh mг hуa, chỉ khбc lа phải dщng phйp biến đổi khуa con. Mа cụ thể lа cбc khуa được dщng trong phйp cộng module 2¹⁶ phải được chuyển thаnh phần tử đối của chъng, cтn cбc khуa được dщng trong phйp nhвn module 2¹⁶+1 thм phải chuyển thаnh phẩn tử nghịch đảo tương ứng.

Mг hуaGiải mгSố tt vтngCбc khуa conTương ứng vớiCбc khуa conTương ứng với1K[1..96]2K[97..128;26..89]3K[90..128;1..25;51..82]4K[83..128;1..50]5K[76..128;1..43]6K[44..75;101..128;1..36]7K[37..100;126..128;1..29]8K[30..125]9K[23..86]

3. 
   Hệ mật mã khối MARS
   

Đầu vào thuật toán là khối 128 bít, chia ra làm 4 nhánh, mỗi nhánh 32 bít. Thuật hiện 32 vòng mã. Quá trình mã gồm 6 giai đoạn sau:

1. 
   Cộng khуa
   
2. 
   8 vтng trộn tới
   
3. 
   8 vтng mг tới
   
4. 
   8 vтng mг lщi
   
5. 
   8 vтng trộn lщi
   
6. 
   Trừ khуa.
   

Hình 7.23. Sơ đồ thuật toán MARS

Giai đoạn trộn tới có 8 vòng, biểu diễn bởi hình 7.24.

Hình 7.24 Sơ đồ trộn tới

Giai đoạn trọn lùi cũng có 8 vòng, được cho như hình 7.25.

Hình 7.25. Sơ đồ trộn lùi

Các S0 và S1 là các hàm hoán đổi, tham số của nó là một số x có độ lớn là 1 byte, với sự hổ trợ của bảng S-boxes gồm 512 phần tử, thực hiện như sau S0 lа thкm vаo 1 bнt 0 vаo đầu của x, tức lа y=S-boxes[0 & x ], cтn hаm S1 thм thкm vаo đầu x bнt 1, tức lа hаm S1 thực hiện như sau: y=S-boxes[1 & x]. Cбch chọn x được đưa ra như sau, từ nhбnh nguồn (nhбnh chọn cбc byte) cу 4 byte b₀, b₁, b₂, b₃ theo thứ tự b₀ lа byte thấp nhất, đến b₃ lа byte cao nhất. b₀, b₂ lаm tham số cho S0 cтn b₁ vа b₃ lаm tham số cho S1.

Giai đoạn mг tới cу 8 vтng, vа mг lщi cу 8 vтng, 2 giai đoạn nаy thể hiện như hмnh vẻ 7.26.

Hình 7.26. Sơ đồ giai đoạn mã tới và mã lùi

Hàm mở rộng E được cho như hình 7.27.

Hình 7.27. Sơ đồ miêu tả hàm mở rộng F

S đơn giản là phép thay thế 9 bít cuối cùng của nhánh thứ hai (nhánh out2) qua bảng S-boxes để thu được 32 bít.

E-function (input: in, key1,key2)

1. 
   // we use three temporary variables, L, M, R
   
2. 
   2. M=in+key1 //add first key word
   
3. 
   R=(in<<<13) key2 //multiply by end key word, which must be odd
   
4. 
   i= lowest 9 bits of M
   
5. 
   L=S[i] //S-box lookup
   
6. 
   R=R<<<5
   
7. 
   r=lowest 5 bits of R //these bits specify rotation amount
   
8. 
   M=M<<st data-dependent rotation
   
9. 
   L=LR
   
10. 
    R=R<<<5
    
11. 
    L=LR
    
12. 
    r=lowest 5 bits of R // these bits specify rotation amount
    
13. 
    L=L<<st data-dependent rotation
    
14. 
    output (L, M, R)
    

1. 
   Hai bнt thấp nhất của một từ trong khуa sử dụng đối với phйp nhвn cу giб trị lа 1.
   
2. 
   Khфng cу từ nаo trong khуa chứa liкn tiếp 10 bнt 0 hay 10 bнt 1.
   

1. Ban đầu, nội dung khóa gốc được chép vào một mảng tạm T[] (có độ dài là 15 từ), tiếp theo là số n và cuối cùng là các số 0. Nghĩa là:

[0.. T n－1]=k[0..n－1],T[n]=n,T[n+1..14] = 0

2. Sau đó, các bước dưới đây được thực hiện lặp lại bốn lần tương ứng với j=0,1,2,3. Mỗi lần lặp sẽ tính giá trị của 10 từ kế tiếp trong khóa mở rộng:

a) Mảng T[] được biến đổi sử dụng công thức tuyến tính sau:

for i = 0 to 14

T[i]=T[i]((T[i－7mod15]T[i－2mod15])<<<3)(4i+ j)

b) Kế đến, mảng T[] sẽ được biến đổi qua bốn chu kỳ của mạng Feistel loại 1:

T[i]=(T[i] + S-box[9 bit thấp của T[i–1 mod 15]]) <<< 9, với i = 0, 1, …, 14.

c) Sau đó, lấy 10 từ trong mảng T[], sắp xếp lại rồi đưa vào thành 10 từ kế tiếp của mảng khóa mở rộng K[]:

K[10j + i] = T[4i mod 15], i = 0,1,…,9

3. Cuối cùng, xét 16 từ dùng cho phép nhân trong mã hóa (bao gồm các từ K[5], K[7], …, K[35]) và biến đổi chúng để có hai đặc tính nêu trên. Cần lưu ý là khả năng từ được chọn lựa ngẫu nhiên không thỏa đặc tính thứ hai (tức là từ có 10 bit liên tiếp bằng 0 hoặc bằng 1) là khoảng 1/41. Mỗi từ K[5], K[7], K[9]…, K[35] được xử lý như sau:

a) Ghi nhận hai bit thấp nhất của K[i] bằng cách đặt j=K[i]^3. Sau đó, xây dựng từ w dựa trên K[i] bằng cách thay thế hai bit thấp nhất của K[i] bằng giá trị 1, tức là w=K[i]v3.

b) Xây dựng một mặt nạ M của các bit trong w thuộc một dãy gồm 10 (hoặc nhiều hơn) bit 0 hoặc 1 liên tiếp. Ta có M_l = 1 nếu và chỉ nếu w_l thuộc một dãy 10 bit 0 hoặc 1 liên tục. Sau đó đặt lại 0 cho các bit 1 trong M tương ứng với điểm cuối của đường chạy các bit 0 hoặc 1 liên tục trong w, cũng làm như vậy đối với 2 bit thấp nhất và 1 bit cao nhất của M. Như vậy, bit thứ i của M được đặt lại giá trị 0 nếu i < 2, hoặc i = 31 , hoặc nếu bit thứ i của w khác bit thứ (i +1) hoặc bit thứ (i －1).

c) Tiếp theo, sử dụng một bảng B (gồm bốn từ) cố định để “sửa w”. Bốn phần tử trong B được chọn sao cho mỗi phần tử (cũng như các giá trị xoay chu kỳ khác được xây dựng từ phần tử này) không chứa bảy bit 0 hoặc mười bit 1 liên tiếp nhau. Cụ thể, các tác giả sử dụng bảng B[] = {0xa4a8d57b, 0x5b5d193b, 0xc8a8309b, 0x73f9a978}, (đây là các phần tử thứ 265 đến 268 trong S–box). Lý do chọn các phần tử này là chỉ có 14 mẫu 8 bit xuất hiện hai lần trong các phần tử này và không có mẫu nào xuất hiện nhiều hơn hai lần.

Sử dụng hai bit j (ở bước (a)) để chọn một phần tử trong B và sử dụng năm bit thấp nhất của K[i–1] để quay giá trị của phần tử được chọn này, tức là:

p = B[j] <<< (5 bit thấp nhất của K[i–1])

d) Cuối cùng, thực hiện XOR mẫu p với w sử dụng mặt nạ M và lưu kết quả trong K[i]:

K[i]=w(p^M)

Do hai bit thấp nhất của M là 0 nên hai bit thấp nhất của K[i] sẽ là 1 (do những bit này trong w là 1). Ngoài ra, việc chọn giá trị của mảng B bảo đảm rằng K[i] không chứa dãy mười bit 0 hoặc 1 liên tục.

Lưu ý rằng thủ tục này không chỉ đảm bảo rằng các từ K[5], K[7], K[9]…, K[35] có hai đặc tính nêu trên mà còn giữ được tính chất “ngẫu nhiên” của các từ này, tức là không có bất kỳ một giá trị của từ đơn nào có xác suất lớn hơn trong sự phân bố đồng. Sử dụng phương pháp vét cạn, có thể kiểm chứng được rằng không có mẫu 20 bit nào xuất hiện trong các từ này với xác xuất lớn hơn 1.23 x 2^–20. Tương tự, không có mẫu 10 bit nào xuất hiện với xác suất lớn hơn 1.06 x 2^–10. Các yếu tố này được sử dụng trong việc phân tích thuật toán.