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


Key-Expansion (input:k[], n; output: K[])



tải về 1.46 Mb.
trang4/5
Chuyển đổi dữ liệu30.08.2016
Kích1.46 Mb.
#28532
1   2   3   4   5

Key-Expansion (input:k[], n; output: K[])

  1. //n is the number of words in the key buffer k[], ()

  2. //K[] is the expanded key array, consisting of 40 words

  3. //T[] is a temporary array, consisting of 15 words

  4. //B[] is a fixed table of four words

  5. //Initialize B[]

  6. B[] = {0xa4a8d57b, 0x5b5d193b, 0xc8a8309b, 0x73f9a978}

  7. //Initialize T[] with key data

  8. T[0…n-1]=k[0…n-1], T[n]=n, T[n+1…14]=0

  9. //Four iterations, computing 10 words of K[] in each

  10. for j=0 to 4 do

  11. for i=0 to 14 do //Linear transformation

  12. T[i]=((T[i-7 mod 15]T[i-2 mod 15])<<<3) (4i+j)

  13. repeat four times //Four stirring rounds

  14. for i=0 to 14 do

  15. T[i]=(T[i]+S[low 9 bits of T[i-1 mod 15]]<<<9

  16. end –repeat

  17. for i=0 to 9 do //store next 10 words into K[]

  18. K[10j+i]=T[4i mod 15]

  19. end for

  20. //Modify multiplication keys

  21. for i=5,7,9,…,35 do

  22. j= least two bits of K[i]

  23. w=K[i] with both of the least two bits set to 1

  24. //Generate a bit - Mask M

  25. Ml= 1 iff wl belongs to a sequence of ten consecutive 0’s or 1’s in w

  26. and also and wl-1=wl=wl+1

  27. Select a pattern from the fixed table and rotate if

  28. r= least five bits of K[i-1] //Rotation amount

  29. p=B[j]<<

  30. // Modify K[i] with p under the control of the mask M

  31. K[i]=w(p^M)

  32. end for

MARS-encrypt(input: D[], K[])

Phase (I): Forward mixing – trộn tới

1. // First add subkeys to data

2. for i=0 i = 0 to 3 do

3. D[i]=D[i]+K[i]

4. // Then do eight rounds of forward mixing

5. for i=0 0 to 7 do // use D[0] ] to modify D[1],D[2],D[3]

6. // four S-box look-ups

7. D[1]=D[1]S0[low byte of D[0]]

8. D[1]=D[1]+S1[[ 2nd byte of D[0]]

9. D[2]=D[2]+S0[3rd byte of D[0]]

10.D[3]=D[3] S1[high byte of D[0]]

11.// and rotation of the source word to the right

12.D[0]=D[0]>>>24

13.// followed by additional mixing operations

14.if i=0 or i=4 then

15.D[0]=D[0]+D[1]// add D[1] ] back to the source word

16.if i=1 or i=5 then

17.D[0]=D[0]+D[1]// add D[1] ] back to the source word

18.// rotate D[] ] by one word to the right for next round

19.(D[3],D[2],D[1],D[0])(D[0],D[3],D[2],D[1])

20.end-for

Phase (II): Keyed transformation

21. // Do 16 rounds of keyed transformation

22. for i=0 to 15 do

23. (out1, out2, out3)=E-function(D[0],K[2i+4],K[2i+5])

24. D[0]=D[0]<<<13

25. D[2]=D[2]+out2

26. if i<8 then // first 8 rounds in forward mode

27. D[1]=D[1]+out1

28. D[3]=D[3] out3

29. else // last 8 rounds in backwards mode

30. D[3]=D[3]+out1

31. D[1]=D[1] out3

32. end-if

33. // rotate D[] by one word to the right for next round

34. (D[3],D[2],D[1],D[0])(D[0],D[3],D[2],D[1])

35. end-for



Phase (III): Backwards mixing –trộn lùi

36. // Do eight rounds of backwards mixing

37. for i=0 to 7 do

38. // additional mixing operations

39. if i=2 or i=6 then

40. D[0]=D[0]-D[3]3] // subtract D[3] from source word

41. if i=3 or i=7 then

42. D[0]=D[0]-D[1]1] // subtract D[1]] from source word

43. // four S-box look-ups

44. D[1]=D[1]S1[ low byte of D[0]]

45. D[2]=D[2] - S0[high byte of D[0]]

46. D[3]=D[3]- S1[ 3rd byte of D[0]]

47. D[3]=D[3]S0[2nd byte of D[0]]

48. // and rotation of the source word to the left

49. D[0]=D[0]<<<24

50. // rotate D[0] by one word to the right for next round

51. (D[3],D[2],D[1],D[0])(D[0],D[3],D[2],D[1])

52. end-for

53. // Then subtract subkeys from data

54. for i=0 to 3 do

55. D[i]=D[i]-K[36+i]

Quy trình giải mã là nghịch đảo của quy trình mã hóa. Mã giả cho quy trình giải mã của thuật toán MARS tương tự với mã giả của quy trình mã hóa của thuật toán:



MARS-derypt(input: D[], K[])

Phase (I): Forward mixing –trộn tới

1. // First add subkeys to data

2. for i=0 i = 0 to 3 do

3. D[i]=D[i]+K[36+i]

4. // Then do eight rounds of forward mixing

5. for i=7 to 0 do

6. //rotate D[] by one word to the left for this round

7. (D[3],D[2],D[1],D[0])(D[2],D[1],D[0],D[3])

8. //and rotate of the source word to the right

9. D[0]=D[0]>>>24

10.//four S-box look-ups

11.D[3]=D[3]S0[2nd byte of D[0]]

12.D[3]=D[3]+S1[3rd byte of D[0]]

13.D[2]=D[2]+S0[high byte of D[0]]

14.D[1]=D[1] S1[low byte of D[0]]

15.// followed by additional mixing operations

16.if i=2 or i=6 then

17.D[0]=D[0]+D[3]// add D[3]3] back to the source word

18.if i=3 or i=7 then

19.D[0]=D[0]+D[1]// add D[1]1] back to the source word

20.end-for

Phase (II): Keyed transformation

21. // Do 16 rounds of keyed transformation

22. for i=15 to 0 do

23. //rotate D[] by one word to the left for this round

24. (D[3],D[2],D[1],D[0])(D[2],D[1],D[0],D[3])

25. D[0]=D[0]>>>13

26. (out1, out2, out3)=E-function(D[0],K[2i+4],K[2i+5])

27. D[2]=D[2]-out2


28. if i<8 then // last 8 rounds in forward mode

29. D[1]=D[1]-out1

30. D[3]=D[3] out3

31. else // first 8 rounds in backwards mode

32. D[3]=D[3]-out1

33. D[1]=D[1] out3

34. end-if

35. end-for



Phase (III): Backwards mixing – trộn lùi

36. // Do eight rounds of backwards mixing

37. for i=7 to 0 do

38. // rotate D[] by one word the left for this round

39. (D[3],D[2],D[1],D[0])(D[2],D[1],D[0],D[3])

40. //additional mixing operations

41. if i=0 or i=4 then

42. D[0]=D[0]-D[3]1] // subtract D[3]1] from source word

43. if i=1 or i=5 then

44. D[0]=D[0]-D[1] //subtract D[1] from source word

45. //and rotation of the source word to the left

46. D[0]=D[0]<<<24

47. //four S-box look-ups

48. D[3]=D[3]S1[high byte of D[0]

49. D[2]=D[2]-S0[3rd byte of D[0]]

50. D[1]=D[1]-S1[2nd byte of D[0]

51. D[1]=D[1]S0[low byte of D[0]

52. end-for

53. // Then subtract subkeys from data

54. for i=0 to 3 do

55. D[i]=D[i]-K[i]


    1. Hệ mật RC6

Đặc điểm chung RC6: là thuật toán được phát triển từ RC5, được xây dựng dựa trên cấu trúc cơ sở Feistel. Nó có thể được thực hiện trên các biến thể khác nhau (kích thước khối dữ liệu đầu vào, kích thước khóa, số lượng vòng, trong cuộc thi AES thuật toán gồm 20 vòng, khóa có độ dài thay đổi được là 128 hoặc 192 hoặc 256 bít và khối mã có độ lớn là 128 bít), vì thế thuật toán rất mềm dẻo đối với tất cả các cấp độ của độ an toàn và sự hiệu quả. Thuật toán RC6 tương ứng với các tham số w/r/b, trong đó kích thước từ là w bit, quy trình mã hóa bao gồm r chu kỳ và tham số b xác định chiều dài mã khóa tính bằng byte. Trên thực tế, RC6 được xem như 2 quá trình mã hóa RC5 song song. RC6 bao gồm 20 vòng, tác giả của thuật toán đã xác nhận rằng với 16 vòng, thuật toán có thể tấn công với độ phức tạp 2119. Thuật toán có thể ít phù hợp trên một số nền nào đó vì trong thuật toán có sử dụng các toán tử dịch vòng trên 32 bít (có thể biến đổi) và các phép nhân số nguyên, nhưng khi các toán tử này được hỗ trợ, RC6 sẽ thực hiện nhanh hơn so với tất cả các thuật toán AES chung kết khác. Nhược điểm chính của RC6 liên quan đến số lượng vòng được sử dụng trong thuật toán.

Miêu t thuật toán. Thuật toán RC6-w/r/b thực hiện trên các đơn vị bốn từ w bít sử dụng 6 phép toán cơ bản và logarit cơ số 2 của w, ký hiệu là lgw.

a + b phép cộng số nguyên theo modulo 2w

a - b phép trừ số nguyên theo modulo 2w

ab phép XOR

a * b phép nhân số nguyên modulo 2w

a<<

a>>>b quay a sang phải b bít.

Sơ đồ thuật toán được cho như hình 7.28. Đầu vào là khối 4 từ w bít, thực hiện r vòng. Trong sơ đồ có một hàm f: f(x)=x(2x+1).


Hình 7.28. Sơ đồ thuật toán RC6



Quá trình sinh khóa: Thuật toán sử dụng khóa mật có chiều dài b bytes, ở đây . Từ khóa mật thực hiện mở rộng khуa thаnh 2r+4 từ (w bнt mỗi từ). 2r+4 từ nаy cуp vаo mảng S[0,...,2r+3]. Mảng nаy sử dụng cho quб trмnh mг hуa vа giải mг. Trong thủ tục mở rộng khуa sử dụng cбc hằng số Pw vа Qw như cбc “hằng số huyển bн”. Thủ tục mở rộng khуa được thực hiện như sau. b byte khуa mật sẽ cуp vаo mảng L[0,…,c-1] (gồm c từ w bнt), nếu thiếu thм thкm vаo cбc byte 0, sau đу thực hiện cбc phйp biến đổi để tạo ra khуa con để lưu vаo mảng S[]. Quб trмnh nаy được miкu tả bằng đoạn lệnh sau:

Key schedule của RC6–w/r/b

Input:

Khóa (gồm b byte) do người dùng cung cấp được đưa vào mảng L[0,…, c–1] (gồm c–từ)

r là số lượng chu kỳ

Output: Các khóa chu kỳ w bit S[0, …, 2r + 3]

Begin

S[0] = Pw



for i = 1 to 2r + 3

S[i] = S[i – 1] + Qw

A = B = i = j = 0

v = 3 × max{c; 2r + 4}



for s = 1 to v

A = S[i] = (S[i] + A + B) <<< 3

B = L[j] = (L[j] + A + B) <<< (A + B)

i = (i + 1) mod (2r + 4)

j = (j + 1) mod c

end for

End

Quy trình mã hóa và giải mã

RC6 làm việc với bốn từ w bit A, B, C, D chứa các dữ liệu đưa vào ban đầu cũng như dữ liệu mã hóa đưa ra cuối quy trình mã hóa. Quy trình mã hóa, giải mã được cho bởi đoạn miêu tả code giả sau:

Encryption/Decryption with RC6-w/r/b

Input: Plaintext stored in four w-bit input registers A, B, C & D

r is the number of rounds

w-bit round keys S[0, ... , 2r + 3]

Output: Ciphertext stored in A, B, C, D

// '''Encryption Procedure:'''

B = B + S[0]

D = D + S[1]

for i = 1 to r do

{

t = (B(2B + 1)) <<< lg w



u = (D(2D + 1)) <<< lg w

A = ((A ^ t) <<< u) + S[2i]

C = ((C ^ u) <<< t) + S[2i + 1]

}

A = A + S[2r + 2]



C = C + S[2r + 3]

// '''Decryption Procedure:'''

C = C - S[2r + 3]

A = A - S[2r + 2]

for i = r downto 1 do

{

(A, B, C, D) = (D, A, B, C)



u = (D.(2D + 1)) <<< lg w

t = (B.(2B + 1)) <<< lg w

C = ((C - S[2i + 1]) >>> t) ^ u

A = ((A - S[2i]) >>> u) ^ t

}

D = D - S[1]



B = B - S[0]

    1. Hệ mật mã khối Serpent

Đặc điểm chung: Serpent là thuật toán được thiết kế dựa trên cấu trúc cơ sở là mạng chuyển vị-thay thế (S-P Network). Các tác giả thiết kế thuật toán này hướng tới việc tuân thủ dựa trên các thiết kế đã có và coi trọng tính an toàn của thuật toán hơn là tính mới lạ và tốc độ của thuật toán. Trong mỗi vòng của thuật toán bao gồm 8 hộp S dựa trên các hộp S của mã DES, nó được thiết kế cho phép tất cả các toán tử có thể thực hiện song song. Thuật toán bao gồm 32 vòng. Các tác giả của thuật toán khẳng định rằng 16 vòng đã đảm bảo độ an toàn của thuật toán (32 vòng sẽ đảm bảo khả năng chống lại các kiểu tấn công trong tương lai). Điều này dễ ràng tạo cho thuật toán một sự an toàn cần thiết (Serpent được nhìn nhận là thuật toán an toàn nhất trong các thuật toán chung khảo AES), nhưng sự trả giá của nó là hiệu suất thấp của thuật toán so với tất cả các thuật toán chung khảo AES. Tuy nhiên, vì yêu cầu ít bộ nhớ khi thực hiện, vì vậy thuật toán rất thích hợp để thực hiện trên smart card (chính điều này giúp cho Serpent chiến thắng thuật toán CAST-256, mặc dù chúng có cùng hiệu năng và độ an toàn).

Miêu t thuật toán:

Quá trình mã hóa của Serpent được chia ra làm 3 giai đoạn sau:

1. Phép hoán vị đầu IP (initial permutation);

2. 32 chu kỳ, mỗi chu kỳ bao gồm một phép trộn khóa, một lượt duyệt qua 32 bảng S–box và một phép biến đổi tuyến tính (cho tất cả các chu kỳ trừ chu kỳ cuối). Ở chu kỳ cuối cùng, phép biến đổi tuyến tính này thay thế bằng một phép trộn khóa.

3. Phép hoán vị cuối FP (final permutation).Đây là phép hoán đổi nghịch của phép hoán đổi ban đầu IP.

Sơ đồ thuật toán mã hóa của Serpent được cho như hình 7.29.



Hình 7.29. Sơ đồ miêu tả qúa trình mã hóa của Sepent

ở đây Kr là khóa vòng 128 bít, mỗi vòng dùng 32 bảng Si giống nhau, với i=r mod 8, r là số thứ tự của vòng mã, 8 bảng DES, và biến đổi đầu và cuối xem phụ lục, còn phép biến đổi tiến tính được cho như hình sau với đầu vào 128 bít chia ra làm 4 nhánh làm đầu vào của biến đổi tuyến tính.

Quá trình giải mã của Serpent là biến đổi ngược của quá trình mã hóa, cũng có 32 vòng, và sơ đồ thuật toán được cho như hình 7.30:



Hình 7.30. Sơ đồ miêu tả qúa trình giải mã của Sepent



Hàm mở rộng khóa. Như chúng ta thấy quá trình mã hóa và giải mã cần đến 33 khóa con 128 bít (K0, …, K32). Các khóa này hình thành từ khóa mật bằng hàm mở rộng khóa. Hàm mở rộng được cho như sau. Khóa mật K ban đầu sẽ ghi ra thành 8 từ 32 bít (w-8, …, w-1), nếu khóa K không đủ thì ta them vào dãy bít 100…0 để cho đủ, mở rộng 8 từ này thành 132 khóa trung gian bằng công thức sau:

wi=(wi-8wi-5wi-3wi-1i)<<<11

ở đвy lа phần phвn số của tỉ số vаng hay dạng số hexa 0x9e3779b9. Bằng cбch tạo ra cбc khуa trung gian theo cфng thức trкn cho phйp cбc bнt khуa phвn đều ở cбc chu kỳ, trбnh được khуa yếu. Từ cбc khуa trung gian nаy hмnh thаnh nкn cбc khуa của chu kỳ, nhờ giъp đở của bảng thay thế S-box như sau:

K0=S-box3 (w0, w1, w2,w3)

K1= S-box2 (w4, w5, w6,w7)

K3= S-box1 (w8, w9, w10,w11)

K4= S-box0 (w12, w13, w14,w15)

K5= S-box7 (w16, w17, w18,w19)

….

K31= S-box4 (w124, w125, w126,w127)



K32= S-box3 (w128, w129, w130,w131)

S-boxi ở đây 32 bảng Si liên tiếp nhau, để thay thế 128 bít khóa trung gian thành khóa vòng.



    1. Hệ mật mã khối Twofish

Đặc điểm chung: là thuật toán được thiết kế dựa trên thuật toán Blowfish (được thiết kế dựa trên cấu trúc cơ sở là mạng Feistel). Twofish là thuật toán nhanh và không yêu cầu nhiều bộ nhớ khi thực hiện. Cấu trúc của thuật toán rất phức tạp và do đó rất khó phân tích (để đạt được sự mềm dẻo trong cấu trúc, các tác giả của thuật toán đã sử dụng một số “kỹ xảo - tricks”, sự an toàn của các kỹ thuật này không rõ ràng, vì vậy trong 5 thuật toán chung khảo AES, Twofish là thuật toán khó phân tích nhất), điều này làm cho nó giống như thuật toán MARS, nhưng nó có ưu điểm hơn là thiết kế được dựa trên một thuật toán đã được nghiên cứu và đã phổ biến. Twofish bao gồm 16 vòng, tính năng đặc biệt của nó là sử dụng các hộp S được tính toán trước phụ thuộc vào khóa, và sử dụng khóa theo thời gian biểu tương đối phức tạp. Trong thiết kế, thuật toán sử dụng 1 số thành phần của các thiết kế khác – ví dụ biến đổi PHT (Pseudo-Hadamard Transform) của họ mã SAFER. Trên hầu hết các nền phần mềm Twofish chậm hơn một chút so với Rijndael (với 128 bít khóa), nhưng có phần nhanh hơn đối với 256 bít khóa. Các tác giả của thuật toán đã đề cập đến việc tấn công thuật toán trên 6 vòng và tấn công liên quan đến khóa lên tới 10 vòng. Trên thực tế (đến năm 2005) không có kiểu tấn công nào lên thuật toán hiệu quả hơn kiểu tấn công “tìm khóa theo phương pháp vét cạn – brute force key search”.

Miêu t thuật toán. Sơ đồ thuật toán như hình vẻ 7.31. Ở đây, văn bản ban đầu đưa vào là bốn từ 32 bit A, B, C, D. Trước khi tham gia vào 16 vòng bốn từ này XOR với bốn từ khóa K0..3. Kế đến thực hiện tiếp 16 chu kỳ. Trong mỗi chu kỳ, hai từ A, B là dữ liệu vào của hàm g (đầu tiên từ B được quay trái 8 bit). Hàm g bao gồm bốn S–box (mỗi S–box là một byte) phụ thuộc khóa, theo sau là bước trộn tuyến tính dựa trên ma trận MDS. Kết hợp kết quả trả ra của hai hàm g thông qua biến đổi tựa Hadamard (PHT) rồi cộng thêm vào hai từ khóa (K2r+8 cho A và K2r+9 cho B ở chu kỳ r). Sau đó hai kết quả này XOR với hai từ C và D (trước khi xor từ D với B, từ D được quay trái 1 bit và sau khi XOR từ C với A, từ C được quay phải 1 bit). Kế đến hai từ A và C, B và D hoán đổi cho nhau để thực hiện chu kỳ kế tiếp. Sau khi thực hiện xong 16 chu kỳ, hoán chuyển trở lại hai từ A và C, B và D, cuối cùng thực hiện phép XOR bốn từ A, B, C, D với bốn từ khóa K4...7 cho ra bốn từ A’, B’, C’, D’ đã được mã hóa.

Hình 7.31. Sơ đồ thuật toán Twofish



Hàm F: Ở đây hàm F là phép hoán vị phụ thuộc khóa trên gía trị 64 bít. Hàm F nhận vào ba tham số, đó là hai từ dữ liệu vào R0 vа R1, vа số thứ tự r của chu kỳ dщng để chọn khуa con thнch hợp. R0 được đưa qua hаm g để tạo ra T0. R1 được quay sang trбi 8 bнt, sau đу được đưa qua hаm g để tạo ra T1. Tiếp theo lа T0 vа T1 được được kết hợp sử dụng PHT vа cộng thкm hai từ trong bảng khуa mở rộng, hаm F cу thể biểu diễn bằng chuỗi lệnh sau:

T0=g(R0)

T1=g(ROL(R1,8))

F0=(T0+T1+K2r+8)mod 232

F1=(T0+2T1+K2r+9)mod 232

(F0,F1) là kết quả của hàm F



Hàm g: Hàm g là trung tâm của thuật toán Twofish. Từ dữ liệu đâu vào X được chia thành 4 byte. Mỗi byte thực hiện thông qua S–box phụ thuộc khóa của chính mình. Mỗi S–box đưa 8 bit dữ liệu vào và đưa ra 8 bit kết quả. 4 byte kết quả được xem như một véc tơ có chiều dài bằng 4 trên GF(28) và véc tơ này nhân với ma trận MDS 4 ラ 4 (sử dụng trường GF(28) cho việc tính toán). Véc tơ kết quả Z được xem như một từ 32 bit và nó cũng là kết quả của hàm g.

, i=0,…,3

, i=0,…,3



Si lа cбc S-box phụ thuộc vаo khуa, ma trận MDS được cho ở dạng Hexa như sau:





S-box ph thuộc vào khóa: Mỗi S–box được định nghĩa với 2, 3 hoặc 4 byte của dữ liệu đầu vào của khóa phụ thuộc vào kích thước khóa. Điều này thực hiện như sau cho các khóa 128 bit, được miêu tả ở hình 7.32.

S0(x)=q1[q0[q0[x]S0,0]S1,0]

S1(x)=q0[q0[q1[x]S0,1]S1,1]

S2(x)=q1[q1[q0[x]S0,2]S1,2]

S3(x)=q0[q1[q1[x]S0,3]S1,3]

Hình 7.32. Sơ đồ miêu tả sinh S-Box



Каталог: 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




Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2024
được sử dụng cho việc quản lý

    Quê hương