Thực đơn
trang chủWindows 7

Des key cái gì. Thuật toán mã hóa DES và AES

  • Hướng dẫn

Xin chào %tên người dùng%!
Nhiều người biết rằng tiêu chuẩn mặc định trong lĩnh vực này mã hóa đối xứng trong một khoảng thời gian dàiđã được xem xét thuật toán DES. Cuộc tấn công thành công đầu tiên vào thuật toán không thể thành công này được xuất bản vào năm 1993, 16 năm sau khi nó được áp dụng làm tiêu chuẩn. Phương pháp mà tác giả gọi là phân tích mật mã tuyến tính, với sự có mặt của 247 cặp bản rõ/bản mã, có thể bẻ khóa được Chìa khóa bí mật Mật mã DES trong 2 43 phép toán.
Bên dưới phần cắt, tôi sẽ cố gắng phác thảo ngắn gọn những điểm chính của cuộc tấn công này.

Giải mã tuyến tính

Phân tích mật mã tuyến tính là một kiểu tấn công đặc biệt vào mật mã đối xứng, nhằm mục đích khôi phục khóa mã hóa không xác định từ khóa đã biết mở tin nhắn và các bản mã tương ứng của chúng.

TRONG trường hợp chung Một cuộc tấn công dựa trên phân tích mật mã tuyến tính sẽ đạt được các điều kiện sau. Kẻ tấn công có một lượng lớn các cặp bản rõ/bản mã thu được bằng cách sử dụng cùng một khóa mã hóa K. Mục tiêu của kẻ tấn công là khôi phục một phần hoặc toàn bộ khóa K.

Trước hết, kẻ tấn công kiểm tra mật mã và tìm ra cái gọi là tương tự thống kê, tức là phương trình loại sau, thực thi với xác suất P ≠ 1/2 đối với cặp văn bản công khai/riêng tư tùy ý và khóa cố định:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1) ,
trong đó Pn, Cn, Kn là các bit thứ n của văn bản, bản mã và khóa.
Khi tìm thấy phương trình như vậy, kẻ tấn công có thể khôi phục 1 bit thông tin chính bằng thuật toán sau

Thuật toán 1
Gọi T là số văn bản chứa bên trái phương trình (1) bằng 0 thì
Nếu T>N/2 thì N là số bản rõ đã biết.
Giả sử K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (khi P>1/2) hoặc 1 (khi P<1/2).
Nếu không thì
Giả sử K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (khi P>1/2) hoặc 0 (khi P<1/2).
Rõ ràng là sự thành công của thuật toán phụ thuộc trực tiếp vào giá trị của |P-1/2| và về số lượng cặp văn bản mở/đóng có sẵn N. Xác suất P của đẳng thức (1) khác 1/2 càng nhiều thì số lượng văn bản mở N cần thiết cho cuộc tấn công càng ít.

Có hai vấn đề cần giải quyết để cuộc tấn công thành công:

  • Làm thế nào để tìm một phương trình hiệu quả của dạng (1).
  • Cách sử dụng phương trình này để có được nhiều hơn một bit thông tin về khóa.
Hãy xem xét giải pháp cho những vấn đề này bằng cách sử dụng mật mã DES làm ví dụ.

Mô tả của DES

Nhưng trước tiên, hãy mô tả ngắn gọn cách hoạt động của thuật toán. Đã nói đủ về DES rồi. Bạn có thể tìm thấy mô tả đầy đủ về mật mã trên Wikipedia. Tuy nhiên, để giải thích sâu hơn về cuộc tấn công, chúng ta sẽ cần một số định nghĩa được giới thiệu trước một cách tốt nhất.

Vì vậy, DES là mật mã khối dựa trên mạng Feistel. Mật mã có kích thước khối là 64 bit và kích thước khóa là 56 bit. Hãy xem xét sơ đồ mã hóa của thuật toán DES.

Như có thể thấy trong hình, khi mã hóa văn bản, các thao tác sau được thực hiện:

  1. Hoán vị bit ban đầu. Ở giai đoạn này, các bit của khối đầu vào được xáo trộn theo một thứ tự nhất định.
  2. Sau đó, các bit hỗn hợp được chia thành hai nửa, được đưa vào đầu vào của hàm Feistel. Đối với DES tiêu chuẩn, mạng Feistel bao gồm 16 vòng, nhưng vẫn tồn tại các biến thể khác của thuật toán.
  3. Hai khối thu được ở vòng biến đổi cuối cùng được kết hợp và một hoán vị khác được thực hiện trên khối kết quả.

Trong mỗi vòng của mạng Feistel, 32 bit ít quan trọng nhất của thông báo được truyền qua hàm f:

Hãy xem các hoạt động được thực hiện ở giai đoạn này:

  1. Khối đầu vào được chuyển qua hàm mở rộng E, hàm này chuyển đổi khối 32 bit thành khối 48 bit.
  2. Khối kết quả được thêm vào khóa tròn K i .
  3. Kết quả của bước trước được chia thành 8 khối, mỗi khối 6 bit.
  4. Mỗi khối B i nhận được được chuyển qua hàm thay thế S-Box i, hàm này thay thế chuỗi 6 bit bằng khối 4 bit.
  5. Khối 32 bit thu được được chuyển qua hoán vị P và được trả về dưới dạng kết quả của hàm f.

Mối quan tâm lớn nhất của chúng tôi từ quan điểm giải mã mật mã là các khối S, được thiết kế để che giấu kết nối giữa dữ liệu đầu vào và đầu ra của hàm f. Để tấn công thành công DES, trước tiên chúng ta sẽ xây dựng các đối tượng thống kê tương tự cho từng hộp S, sau đó mở rộng chúng cho toàn bộ mật mã.

Phân tích khối S

Mỗi hộp S lấy một chuỗi 6 bit làm đầu vào và với mỗi chuỗi như vậy, một giá trị 4 bit cố định được trả về. Những thứ kia. có tổng cộng 64 tùy chọn đầu vào và đầu ra. Nhiệm vụ của chúng ta là chỉ ra mối quan hệ giữa dữ liệu đầu vào và đầu ra của khối S. Ví dụ: đối với hộp S thứ ba của mật mã DES, bit thứ 3 của chuỗi đầu vào bằng bit thứ 3 của chuỗi đầu ra trong 38 trên 64 trường hợp. Do đó, chúng tôi đã tìm thấy sự tương tự thống kê sau đây cho S thứ ba -hộp:
S 3 (x) = x, thỏa mãn với xác suất P=38/64.
Cả hai vế của phương trình biểu thị 1 bit thông tin. Do đó, nếu bên trái và bên phải độc lập với nhau thì phương trình sẽ phải thỏa mãn với xác suất là 1/2. Như vậy, chúng ta vừa chứng minh được mối quan hệ giữa đầu vào và đầu ra của hộp S thứ 3 của thuật toán DES.

Hãy xem xét cách chúng ta có thể tìm thấy sự tương tự thống kê của hộp S trong trường hợp chung.

Đối với hộp S S a , 1  α  63 và 1   15, giá trị NS a (α, β) mô tả số lần trong số 64 bit đầu vào XOR có thể có S a được xếp chồng lên các bit α bằng các bit đầu ra XOR được xếp chồng lên các bit α β, tức là:
trong đó ký hiệu là logic AND.
Các giá trị của α và β mà NS a (α, β) khác biệt nhất so với 32 mô tả sự tương tự thống kê hiệu quả nhất của hộp S a .

Chất tương tự hiệu quả nhất được tìm thấy trong hộp S thứ 5 của mật mã DES với α = 16 và β = 15 NS 5 (16, 15) = 12. Điều này có nghĩa là phương trình sau đúng: Z=Y ⊕ Y ⊕ Y ⊕ Y, trong đó Z là chuỗi đầu vào của hộp S và Y là chuỗi đầu ra.
Hoặc có tính đến thực tế là trong thuật toán DES, trước khi vào hộp S, dữ liệu được thêm modulo 2 bằng một phím tròn, tức là. Z = X ⊕ K ta có
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, trong đó X và Y là dữ liệu đầu vào và đầu ra của hàm f mà không tính đến các hoán vị.
Phương trình kết quả được thực hiện trên tất cả các vòng của thuật toán DES với cùng xác suất P=12/64.
Bảng sau đây hiển thị danh sách những cái hiệu quả, tức là. có độ lệch lớn nhất so với P=1/2, tương tự thống kê cho từng khối s của thuật toán DES.

Xây dựng các tương tự thống kê cho nhiều vòng DES

Bây giờ chúng ta hãy chỉ ra cách chúng ta có thể kết hợp các điểm tương tự thống kê của một số vòng DES và cuối cùng thu được một điểm tương tự thống kê cho toàn bộ mật mã.
Để làm điều này, hãy xem xét phiên bản ba vòng của thuật toán:

Hãy sử dụng phép tương tự thống kê hiệu quả của hộp s thứ 5 để tính các bit nhất định của giá trị X(2).
Chúng ta biết rằng với xác suất 12/64 đẳng thức đúng trong hàm f X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, trong đó X là bit đầu vào thứ hai của hộp S thứ 5, về cơ bản nó là bit thứ 26 của chuỗi thu được sau khi mở rộng các bit đầu vào. Bằng cách phân tích hàm mở rộng, chúng ta có thể xác định rằng bit thứ 26 được thay thế bằng bit thứ 17 của chuỗi X(1).
Tương tự, Y,..., Y thực chất là các bit thứ 17, 18, 19 và 20 của dãy thu được trước hoán vị P. Xét hoán vị P, ta thấy các bit Y,..., Y thực chất là các bit Y (1), Y(1), Y(1), Y(1).
Bit khóa K liên quan đến các phương trình là bit thứ 26 của khóa con vòng đầu tiên K1 và sau đó dữ liệu tương tự thống kê có dạng sau:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1.
Kể từ đây, X(1) ⊕ K1 = Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1)(2) với xác suất P=12/64.
Biết 3, 8, 14, 25 bit của chuỗi Y(1), bạn có thể tìm được 3, 8, 14, 25 bit của chuỗi X(2):
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) hoặc tính đến phương trình (2)
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 (3) với xác suất là 12/64.

Hãy tìm một biểu thức tương tự bằng cách sử dụng vòng cuối cùng. Lần này chúng ta có phương trình
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3).
Bởi vì
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
chúng tôi hiểu điều đó
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3(4) với xác suất là 12/64.

Đánh đồng vế phải của phương trình (3) và (4) ta thu được
CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 với xác suất (12/64) 2 +(1-12/64) 2.
Có tính đến thực tế là X(1) = PR và X(3) = CR, chúng ta thu được một kết quả tương tự về mặt thống kê
СL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5) ,
được thực hiện với xác suất (12/64) 2 + (1-12/64) 2 =0,7.
Tương tự thống kê được mô tả ở trên có thể được biểu diễn bằng đồ họa như sau (các bit trong hình được đánh số từ phải sang trái và bắt đầu từ 0):

Kẻ tấn công đã biết tất cả các bit ở vế trái của phương trình, vì vậy hắn có thể áp dụng Thuật toán 1 và tìm ra giá trị của K1 ⊕ K3. Hãy chỉ ra cách sử dụng phép tương tự thống kê này, bạn có thể mở không phải 1 mà là 12 bit của khóa mã hóa K.

Tấn công DES bằng bản rõ đã biết

Hãy để chúng tôi trình bày một phương pháp mà bạn có thể mở rộng cuộc tấn công và ngay lập tức thu được 6 bit của vòng kết nối đầu tiên.
Khi soạn phương trình (5), chúng ta đã tính đến thực tế là chúng ta không biết giá trị của F1(PR, K1). Do đó, chúng tôi đã sử dụng tín hiệu tương tự thống kê K1 ⊕ PR của nó.
Chúng ta hãy trả về giá trị F1(PR, K1) thay cho biểu thức K1 ⊕ PR và thu được phương trình sau:
СL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , sẽ được thực hiện với xác suất 12/64. Xác suất đã thay đổi vì chúng tôi chỉ để lại kết quả thống kê tương tự từ vòng thứ ba, tất cả các giá trị khác đều cố định.

Ở trên chúng ta đã xác định rằng giá trị của F1(PR, K1) bị ảnh hưởng bởi các bit đầu vào của hộp S thứ 5, cụ thể là các bit khóa K1 và các bit của khối PR. Hãy chỉ ra cách chỉ cần một tập hợp văn bản mở/đóng, bạn có thể khôi phục giá trị của K1. Để làm điều này, chúng tôi sẽ sử dụng Thuật toán 2.

Thuật toán 2
Gọi N là số cặp văn bản mở/đóng đã biết trước cuộc tấn công. Sau đó để mở key bạn cần thực hiện các bước sau.
Với (i=0; tôi<64; i++) do
{
Vì(j=0; j {
if(СL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) thì
T tôi =T tôi +1
}
}
Là một chuỗi có thể xảy ra K1, giá trị của i được lấy sao cho biểu thức |T i -N/2| có giá trị lớn nhất.

Với đủ số lượng bản rõ đã biết, thuật toán sẽ có xác suất cao trả về giá trị đúng của sáu bit của khóa con vòng đầu tiên K1. Điều này được giải thích là do nếu biến i không bằng K1 thì giá trị của hàm F1(PR j, K) sẽ là ngẫu nhiên và số phương trình cho giá trị i đó mà vế trái là bằng 0 sẽ có xu hướng N/2. Nếu đoán đúng khóa con thì phía bên trái sẽ bằng bit cố định K3 với xác suất là 12/64. Những thứ kia. sẽ có sự sai lệch đáng kể so với N/2.

Sau khi nhận được 6 bit của khóa con K1, bạn có thể mở 6 bit của khóa con K3 theo cách tương tự. Tất cả những gì bạn cần làm là thay thế C bằng P và K1 bằng K3 trong phương trình (6):
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1.
Thuật toán 2 sẽ trả về giá trị K3 chính xác vì quá trình giải mã của thuật toán DES giống hệt quá trình mã hóa, chỉ có dãy khóa bị đảo ngược. Vì vậy, ở vòng giải mã đầu tiên, khóa K3 được sử dụng và ở vòng giải mã cuối cùng, khóa K1 được sử dụng.

Sau khi nhận được 6 bit khóa con K1 và K3, kẻ tấn công sẽ khôi phục được 12 bit khóa chung của mật mã K, bởi vì các khóa tròn là hoán vị thông thường của khóa K. Số lượng bản rõ cần thiết để tấn công thành công phụ thuộc vào xác suất của sự tương tự thống kê. Để bẻ khóa DES 3 vòng 12 bit, 100 cặp văn bản công khai/riêng tư là đủ. Để mở 12 bit của khóa DES 16 vòng, cần khoảng 244 cặp văn bản. 44 bit còn lại của khóa được mở bằng cách sử dụng lực mạnh thông thường.

Thuật toán mã hóa đối xứng phổ biến nhất và được biết đến nhiều nhất là DES (Tiêu chuẩn mã hóa dữ liệu). Thuật toán được phát triển vào năm 1977 và được NIST (Viện Tiêu chuẩn và Công nghệ Quốc gia, Hoa Kỳ) áp dụng làm tiêu chuẩn vào năm 1980.

DES là mạng Feishtel cổ điển có hai nhánh. Dữ liệu được mã hóa theo khối 64 bit bằng khóa 56 bit. Thuật toán chuyển đổi đầu vào 64 bit thành đầu ra 64 bit qua nhiều vòng. Độ dài khóa là 56 bit. Quá trình mã hóa bao gồm bốn giai đoạn. Bước đầu tiên là hoán vị ban đầu (IP) của văn bản nguồn 64 bit (làm trắng), trong đó các bit được sắp xếp lại theo bảng tiêu chuẩn. Giai đoạn tiếp theo bao gồm 16 vòng có cùng chức năng, sử dụng các phép toán dịch chuyển và thay thế. Ở giai đoạn thứ ba, nửa bên trái và bên phải của đầu ra của lần lặp cuối cùng (thứ 16) được hoán đổi. Cuối cùng, giai đoạn thứ tư thực hiện hoán vị IP-1 của kết quả thu được ở giai đoạn thứ ba. Hoán vị IP-1 là nghịch đảo của hoán vị ban đầu.

Hình 4. thuật toán DES

Hình minh họa một phương pháp sử dụng khóa 56 bit. Ban đầu, khóa được cung cấp cho đầu vào của hàm hoán vị. Sau đó, với mỗi vòng trong số 16 vòng, khóa con K i là sự kết hợp của dịch chuyển vòng trái và hoán vị. Hàm hoán vị giống nhau cho mỗi vòng, nhưng các khóa con K i cho mỗi vòng là khác nhau do sự dịch chuyển lặp đi lặp lại của các bit khóa.

Hoán vị ban đầu và nghịch đảo của nó được xác định bởi một bảng tiêu chuẩn. Nếu M là 64 bit tùy ý thì X = IP(M) là 64 bit được sắp xếp lại. Nếu chúng ta áp dụng hàm hoán vị nghịch đảo Y = IP-1 (X) = IP-1 (IP(M)), chúng ta sẽ có được chuỗi bit ban đầu.

Mô tả của vòng des

Chúng ta hãy xem trình tự các phép biến đổi được sử dụng trong mỗi vòng.

Hình.5. Minh họa một vòng của thuật toán DES

Khối đầu vào 64 bit đi qua 16 vòng, với mỗi lần lặp lại tạo ra giá trị 64 bit trung gian. Bên trái và bên phải của mỗi giá trị trung gian được coi là các giá trị 32 bit riêng biệt, ký hiệu là L và R. Mỗi lần lặp có thể được mô tả như sau:

Ri = L i -1 F(R i -1 , K i)

Do đó, đầu ra của nửa bên trái L i bằng đầu vào của nửa bên phải R i-1. Đầu ra của nửa bên phải của R i là kết quả của việc áp dụng phép toán XOR cho L i-1 và hàm F phụ thuộc vào R i-1 và K i .

Hãy xem xét chức năng F chi tiết hơn. R i, được cung cấp cho đầu vào của hàm F, có độ dài 32 bit. Đầu tiên, R i được mở rộng thành 48 bit bằng cách sử dụng bảng chỉ định hoán vị cộng với phần mở rộng 16 bit. Việc mở rộng xảy ra như sau. 32 bit được chia thành các nhóm 4 bit và sau đó được mở rộng thành 6 bit bằng cách thêm các bit ngoài cùng từ hai nhóm liền kề. Ví dụ: nếu một phần của thông báo đầu vào

Efgh ijkl mnop . . .

thì kết quả của việc mở rộng là thông điệp

Defghi hijklm lmnopq. . .

Giá trị 48 bit thu được sau đó được XOR với khóa con 48 bit K i . Giá trị 48 bit kết quả sau đó được đưa vào hàm thay thế, tạo ra giá trị 32 bit.

Sự thay thế bao gồm 8 hộp S, mỗi hộp nhận 6 bit làm đầu vào và tạo ra 4 bit làm đầu ra. Những phép biến đổi này được xác định bởi các bảng đặc biệt. Bit đầu tiên và cuối cùng của giá trị đầu vào S-box xác định số hàng trong bảng, 4 bit ở giữa xác định số cột. Giao điểm của một hàng và một cột xác định đầu ra 4 bit. Ví dụ: nếu đầu vào là 011011 thì số hàng là 01 (hàng 1) và số cột là 1101 (cột 13). Giá trị ở hàng 1 và cột 13 là 5, tức là đầu ra là 0101.

Giá trị 32-bit thu được sau đó được xử lý bằng hoán vị P, mục đích là sắp xếp lại các bit càng nhiều càng tốt để trong vòng mã hóa tiếp theo, mỗi bit có thể được xử lý bởi một hộp S khác nhau.

Khóa cho một vòng riêng lẻ K i bao gồm 48 bit. Khóa K i thu được bằng thuật toán sau. Đối với khóa 56 bit được sử dụng làm đầu vào cho thuật toán, hoán vị trước tiên được thực hiện theo bảng Lựa chọn được phép 1 (PC-1). Khóa 56 bit thu được được chia thành hai phần 28 bit, ký hiệu lần lượt là C0 và D0. Tại mỗi vòng, C i và D i được dịch chuyển độc lập theo chu kỳ sang trái 1 hoặc 2 bit, tùy thuộc vào số vòng. Các giá trị kết quả là đầu vào cho vòng tiếp theo. Chúng cũng là đầu vào của Permuted Choice 2 (PC-2), tạo ra giá trị đầu ra 48 bit là đầu vào của hàm F(R i-1, K i).

Quá trình giải mã tương tự như quá trình mã hóa. Đầu vào của thuật toán là bản mã, nhưng các khóa K i được sử dụng theo thứ tự ngược lại. K 16 được sử dụng ở vòng đầu tiên, K 1 được sử dụng ở vòng cuối cùng. Đặt đầu ra của vòng mã hóa thứ i là L i ||R i . Khi đó đầu vào tương ứng của vòng giải mã thứ (16-i) sẽ là R i ||L i .

Sau vòng cuối cùng của quá trình giải mã, hai nửa đầu ra được hoán đổi sao cho đầu vào của hoán vị cuối cùng IP-1 là R 16 ||L 16 . Đầu ra của giai đoạn này là bản rõ.

Đã hơn 30 năm trôi qua kể từ khi thuật toán DES được áp dụng làm tiêu chuẩn mã hóa của Hoa Kỳ. DES là một thuật toán mã hóa có lịch sử phong phú và thú vị nhất.

Lịch sử hình thành thuật toán

Một trong những nhà mật mã học nổi tiếng nhất thế giới, Bruce Schneier, trong cuốn sách nổi tiếng “Mật mã ứng dụng” đã mô tả các vấn đề của người dùng các công cụ bảo mật thông tin vào đầu những năm 70. Thế kỷ XX (đương nhiên, chúng ta đang nói về những người dùng ở phía bên kia Bức màn sắt):

Không có một tiêu chuẩn được chấp nhận chung nào cho việc mã hóa dữ liệu cũng như không có các thuật toán bảo mật thông tin được sử dụng rộng rãi, do đó khả năng tương thích giữa các công cụ mã hóa phần mềm hoặc phần cứng khác nhau là không thể;

Hầu hết mọi công cụ mã hóa đều là một “hộp đen” với nội dung khá không rõ ràng: thuật toán mã hóa nào được sử dụng, độ mạnh của mật mã như thế nào, liệu nó có được triển khai chính xác hay không, liệu các khóa mã hóa có được tạo, lưu trữ và sử dụng đúng cách hay không, liệu công cụ đó có chứa nội dung không có giấy tờ hay không. các khả năng được các nhà phát triển chèn vào, v.v. - tất cả thông tin rất quan trọng này không thể tiếp cận được đối với đại đa số người mua quỹ mật mã.

Cục Tiêu chuẩn Quốc gia (NBS) của Hoa Kỳ quan tâm đến vấn đề này. Kết quả là vào năm 1973, cuộc thi mở đầu tiên dành cho tiêu chuẩn mã hóa đã được công bố. NBS sẵn sàng kiểm tra các thuật toán ứng viên đáp ứng các tiêu chí sau để chọn ra tiêu chuẩn:

Thuật toán phải mạnh về mặt mật mã;

Thuật toán phải nhanh;

Cấu trúc của thuật toán phải rõ ràng và chính xác;

Độ mạnh của mã hóa chỉ phụ thuộc vào khóa, bản thân thuật toán không được bí mật;

Thuật toán phải dễ dàng áp dụng cho nhiều mục đích khác nhau;

Thuật toán phải được thực hiện dễ dàng trong phần cứng bằng cách sử dụng các thành phần phần cứng hiện có.

Giả định rằng các tổ chức hoặc chuyên gia quan tâm sẽ gửi tới NBS thông số kỹ thuật chi tiết về các thuật toán đủ để triển khai, tức là không có bất kỳ “điểm mù” nào. Người ta cũng giả định rằng thuật toán sẽ được NBS chứng nhận để sử dụng chung và tất cả các hạn chế về bằng sáng chế và xuất khẩu sẽ bị loại bỏ khỏi thuật toán đó, do đó, tiêu chuẩn như vậy sẽ phải giải quyết tất cả các vấn đề về khả năng tương thích mã hóa. Ngoài ra, NBS còn đảm nhận chức năng chứng nhận các công cụ mã hóa - tức là “hộp đen” lẽ ra đã trở thành dĩ vãng.

Trên thực tế, chỉ có một thuật toán ứng cử viên duy nhất: đó là thuật toán mã hóa Lucifer do ShM phát triển. (xem phần 3.31). Trong suốt hai năm, thuật toán đã được cải tiến:

Đầu tiên, NBS cùng với Cơ quan An ninh Quốc gia (NSA, Cơ quan An ninh Quốc gia) của Hoa Kỳ đã tiến hành phân tích kỹ lưỡng thuật toán, dẫn đến sự sửa đổi khá đáng kể;

Thứ hai, những ý kiến, phê bình của tất cả các tổ chức, cá nhân quan tâm đều được xem xét.

Là kết quả của những nỗ lực chung của IBM, NBS và NSA, DES đã được xuất bản vào tháng 1 năm 1977 dưới dạng tiêu chuẩn của Hoa Kỳ (phiên bản mới nhất của tiêu chuẩn này có trong tài liệu) cho thuật toán mã hóa dữ liệu (ngoại trừ thông tin có độ nhạy cảm cao). Thuật toán DES đã được YuM cấp bằng sáng chế, nhưng trên thực tế, NBS đã nhận được giấy phép miễn phí và không giới hạn để sử dụng thuật toán này. Một tên thay thế nhưng ít được sử dụng hơn cho thuật toán là DEA (Thuật toán mã hóa dữ liệu).

Đặc điểm và cấu trúc chính của thuật toán

Thuật toán DES mã hóa thông tin trong các khối 64 bit bằng khóa mã hóa 64 bit chỉ sử dụng 56 bit (quy trình mở rộng khóa được mô tả chi tiết bên dưới).

Việc mã hóa thông tin được thực hiện như sau (Hình 3.56):

1. Hoán vị ban đầu được thực hiện trên khối dữ liệu 64 bit theo bảng. 3.16.

Bảng 3.16

Bảng được hiểu như sau: giá trị của bit đầu vào 58 (sau đây gọi là tất cả các bit được đánh số từ trái sang phải, bắt đầu từ 1) được đặt trong bit đầu ra 1, giá trị của bit 50 được đặt trong bit 2, v.v.



2. Kết quả của thao tác trước được chia thành 2 khối con 32 bit (mỗi khối

cơm. 3,56 được đánh dấu A 0 và B 0), trong đó 16 vòng được thực hiện

các phép biến đổi sau:

Như đã đề cập ở trên, trong số khóa mã hóa 64 bit, thuật toán DES chỉ sử dụng 56 bit. Mỗi bit thứ 8 sẽ bị loại bỏ và không được sử dụng theo bất kỳ cách nào trong thuật toán và việc sử dụng các bit còn lại của khóa mã hóa trong việc triển khai thuật toán DES không bị giới hạn bởi tiêu chuẩn. Quy trình trích xuất 56 bit quan trọng của khóa 64 bit trong Hình. 3.59 được ký hiệu là E. Ngoài việc trích xuất, quy trình này còn thực hiện việc sắp xếp lại các bit khóa theo Bảng. 3,19 và 3,20.


Bảng 3.19

Bảng 3.20


Kết quả của phép hoán vị tạo thành hai giá trị 28 bit C và D. Bảng 3.19 xác định việc lựa chọn các bit khóa cho C, bảng. 3,20 - cho D.

Sau đó, 16 vòng biến đổi được thực hiện, mỗi vòng mang lại một trong các phím tròn K t. Trong mỗi vòng của quy trình mở rộng khóa, các hành động sau được thực hiện:

1. Giá trị hiện tại của C và D dịch chuyển theo chu kỳ sang trái một số bit thay đổi P.Đối với các vòng 1, 2, 9 và 16 P= 1, trong các vòng còn lại, phép dịch theo chu kỳ 2 bit được thực hiện.

2. C và Dđược kết hợp thành giá trị 56 bit, áp dụng hoán vị nén CP, kết quả là khóa tròn 48 bit K (. Hoán vị nén được thực hiện theo Bảng 3.21.

Bảng 3.21

Khi giải mã dữ liệu, bạn có thể sử dụng quy trình mở rộng khóa tương tự nhưng áp dụng các phím tròn theo thứ tự ngược lại. Có một lựa chọn khác: trong mỗi vòng của thủ tục mở rộng khóa, thay vì dịch chuyển tuần hoàn sang trái, thực hiện dịch chuyển tuần hoàn sang phải n bit, trong đó rc' = 0 cho vòng đầu tiên, u' = 1 cho vòng 2, 9, 16 và n = 2 cho các vòng còn lại. Thủ tục mở rộng khóa này sẽ ngay lập tức cung cấp các khóa tròn cần thiết để giải mã.

Điều đáng nói là khả năng thực hiện mở rộng khóa “nhanh chóng” (đặc biệt nếu khả năng này tồn tại cả trong quá trình mã hóa và giải mã) được coi là một lợi thế của thuật toán mã hóa, vì trong trường hợp này, việc mở rộng khóa có thể được thực hiện song song với mã hóa. và không lãng phí bộ nhớ vào việc lưu trữ khóa của các vòng khác ngoài vòng hiện tại.

Chú thích: Một trong những hệ thống mật mã khóa riêng nổi tiếng nhất là DES – Tiêu chuẩn mã hóa dữ liệu. Hệ thống này là hệ thống đầu tiên nhận được trạng thái tiêu chuẩn nhà nước trong lĩnh vực mã hóa dữ liệu. Và mặc dù tiêu chuẩn cũ của Mỹ DES hiện đã mất đi vị thế chính thức nhưng thuật toán này vẫn đáng được quan tâm khi nghiên cứu về mật mã. Bài giảng này cũng giải thích DES kép là gì, một cuộc tấn công gặp trung gian và cách giảm thiểu nó. Bài giảng này cũng thảo luận ngắn gọn về tiêu chuẩn mới của Hoa Kỳ cho mật mã khối, thuật toán Rijndael.

Mục đích của bài giảng: giới thiệu cho sinh viên những thông tin cơ bản về thuật toán mã hóa DES.

Thông tin cơ bản

Một trong những hệ thống mật mã khóa riêng nổi tiếng nhất là DES – Tiêu chuẩn mã hóa dữ liệu. Hệ thống này là hệ thống đầu tiên nhận được trạng thái tiêu chuẩn nhà nước trong lĩnh vực mã hóa dữ liệu. Nó được phát triển bởi các chuyên gia của IBM và có hiệu lực ở Mỹ vào năm 1977. Thuật toán DESđược sử dụng rộng rãi để lưu trữ và truyền dữ liệu giữa các hệ thống máy tính khác nhau; trong hệ thống bưu chính, hệ thống vẽ điện tử và trao đổi điện tử thông tin thương mại. Tiêu chuẩn DESđã được triển khai cả về phần mềm và phần cứng. Các doanh nghiệp từ nhiều quốc gia khác nhau đã triển khai sản xuất hàng loạt thiết bị kỹ thuật số sử dụng DESđể mã hóa dữ liệu. Tất cả các thiết bị đều phải trải qua chứng nhận bắt buộc về việc tuân thủ tiêu chuẩn.

Mặc dù thực tế là hệ thống này chưa được coi là tiêu chuẩn của chính phủ trong một thời gian nhưng nó vẫn được sử dụng rộng rãi và đáng được chú ý khi nghiên cứu mật mã khối bằng khóa riêng.

Độ dài khóa trong thuật toán DES là 56 bit. Với thực tế này, cuộc tranh cãi chính liên quan đến khả năng DES chống lại các cuộc tấn công khác nhau. Như bạn đã biết, bất kỳ mật mã khối nào có khóa riêng đều có thể bị bẻ khóa bằng cách thử tất cả các tổ hợp khóa có thể. Với độ dài khóa 56 bit, có thể có 2 56 khóa khác nhau. Nếu một máy tính tìm kiếm qua 1.000.000 phím trong một giây (xấp xỉ bằng 2 20), thì sẽ mất 2 36 giây hoặc hơn hai nghìn năm một chút để tìm kiếm qua tất cả 2 56 phím, điều này tất nhiên là không thể chấp nhận được đối với những kẻ tấn công.

Tuy nhiên, có thể có các hệ thống máy tính đắt hơn và nhanh hơn Máy tính cá nhân. Ví dụ: nếu có thể kết hợp một triệu bộ xử lý để tính toán song song thì thời gian chọn khóa tối đa sẽ giảm xuống còn khoảng 18 giờ. Khoảng thời gian này không quá dài và một nhà giải mã được trang bị thiết bị đắt tiền như vậy có thể dễ dàng phá được dữ liệu được mã hóa DES trong một khoảng thời gian hợp lý.

Đồng thời, có thể lưu ý rằng hệ thống DES Nó có thể được sử dụng trong các ứng dụng vừa và nhỏ để mã hóa dữ liệu có giá trị nhỏ. Để mã hóa dữ liệu có tầm quan trọng quốc gia hoặc có giá trị thương mại quan trọng, hệ thống DES tất nhiên là không nên sử dụng vào lúc này. Năm 2001, sau một cuộc thi được công bố đặc biệt, một tiêu chuẩn mã khối mới đã được áp dụng ở Hoa Kỳ, được gọi là AES (Tiêu chuẩn mã hóa nâng cao), dựa trên mật mã Rijndael, được phát triển bởi các chuyên gia người Bỉ. Mật mã này sẽ được thảo luận ở cuối bài giảng.

Cài đặt chính DES: kích thước khối 64 bit, độ dài khóa 56 bit, số vòng – 16. DES là mạng Feishtel cổ điển có hai nhánh. Thuật toán chuyển đổi khối dữ liệu đầu vào 64 bit thành khối đầu ra 64 bit qua nhiều vòng. Tiêu chuẩn DESđược xây dựng trên việc sử dụng kết hợp hoán vị, thay thế và gamma. Dữ liệu được mã hóa phải ở dạng nhị phân.

Mã hóa

Cấu trúc chung DES thể hiện trong hình. 4.1. Quá trình mã hóa từng khối dữ liệu thô 64 bit có thể được chia thành ba giai đoạn:

  1. chuẩn bị ban đầu của khối dữ liệu;
  2. 16 vòng của “chu kỳ chính”;
  3. xử lý cuối cùng của một khối dữ liệu.

Ở giai đoạn đầu tiên nó được thực hiện hoán vị ban đầu Khối văn bản nguồn 64 bit, trong đó các bit được sắp xếp lại theo một cách cụ thể.

Ở giai đoạn tiếp theo (chính), khối được chia thành hai phần (nhánh), mỗi phần 32 bit. Nhánh bên phải được chuyển đổi bằng cách sử dụng một số hàm F và hàm tương ứng khóa một phần, được lấy từ khóa mã hóa chính bằng thuật toán chuyển đổi khóa đặc biệt. Sau đó dữ liệu được trao đổi giữa các nhánh trái và phải của khối. Điều này được lặp lại trong một chu kỳ 16 lần.

Cuối cùng, giai đoạn thứ ba sắp xếp lại kết quả thu được sau mười sáu bước của vòng lặp chính. Hoán vị này là nghịch đảo của hoán vị ban đầu.


Cơm. 4.1.

Chúng ta hãy xem xét kỹ hơn tất cả các giai đoạn chuyển đổi mật mã theo tiêu chuẩn DES.

Trong giai đoạn đầu tiên, khối dữ liệu nguồn 64 bit trải qua hoán vị ban đầu. Trong tài liệu, hoạt động này đôi khi được gọi là "làm trắng". Trong quá trình hoán vị ban đầu, các bit của khối dữ liệu được sắp xếp lại theo một cách nhất định. Hoạt động này thêm một số "hỗn loạn" vào tin nhắn gốc, làm giảm khả năng sử dụng phương pháp phân tích mật mã bằng phương pháp thống kê.

Đồng thời với hoán vị ban đầu của khối dữ liệu, hoán vị ban đầu của 56 bit của khóa được thực hiện. Từ hình. 4.1. Có thể thấy rằng trong mỗi vòng, khóa một phần 48 bit tương ứng K i được sử dụng. Khóa K i thu được bằng cách sử dụng một thuật toán cụ thể, sử dụng từng bit của khóa ban đầu nhiều lần. Trong mỗi vòng, khóa 56 bit được chia thành hai nửa 28 bit. Các nửa sau đó được dịch sang trái một hoặc hai bit tùy thuộc vào số tròn. Sau khi dịch chuyển, 48 trong số 56 bit được chọn theo một cách nhất định. Vì thao tác này không chỉ chọn một tập hợp con các bit mà còn thay đổi thứ tự của chúng nên thao tác này được gọi là “hoán vị nén”. Kết quả của nó là một tập hợp 48 bit. Trung bình, mỗi bit của khóa 56 bit ban đầu được sử dụng ở 14 trong số 16 khóa con, mặc dù không phải tất cả các bit đều được sử dụng cùng số lần.

Tiếp theo, chu trình chuyển đổi chính được thực hiện, được tổ chức bằng mạng Feishtel và bao gồm 16 vòng giống hệt nhau. Trong trường hợp này, trong mỗi vòng (Hình 4.2) sẽ thu được một giá trị 64-bit trung gian, sau đó được xử lý ở vòng tiếp theo.


Cơm. 4.2.

Nhánh trái và nhánh phải của mỗi giá trị trung gian được coi là các giá trị 32 bit riêng biệt, ký hiệu là L và R .

Đầu tiên, phía bên phải của khối R i được mở rộng thành 48 bit bằng cách sử dụng bảng xác định hoán vị cộng với việc mở rộng thêm 16 bit. Thao tác này khớp kích thước của nửa bên phải với kích thước của phím để thực hiện thao tác XOR. Ngoài ra, bằng cách thực hiện thao tác này, sự phụ thuộc của tất cả các bit của kết quả vào các bit của dữ liệu nguồn và khóa sẽ tăng nhanh hơn (điều này được gọi là “hiệu ứng tuyết lở”). Hiệu ứng tuyết lở càng mạnh khi sử dụng thuật toán mã hóa này hoặc thuật toán mã hóa khác thì càng tốt.

Sau khi thực hiện hoán vị mở rộng, giá trị 48 bit thu được được XOR với khóa con 48 bit K i. Sau đó, giá trị 48 bit kết quả được đưa vào đầu vào của khối thay thế S (từ tiếng Anh. Thay thế - thay thế), kết quảđó là giá trị 32 bit. Việc thay thế được thực hiện trong tám khối thay thế hoặc tám hộp S. Khi được thực thi, DES trông khá phức tạp trên giấy tờ, chưa nói đến việc triển khai phần mềm của nó! Xây dựng một chương trình hoạt động chính xác và tối ưu, hoàn toàn phù hợp với DES, có lẽ chỉ những lập trình viên có kinh nghiệm mới làm được. Một số khó khăn nảy sinh khi triển khai phần mềm, ví dụ như hoán vị ban đầu hoặc hoán vị khi mở rộng. Những khó khăn này liên quan đến những gì dự kiến ​​ban đầu sẽ được thực hiện DES chỉ phần cứng. Tất cả các hoạt động được sử dụng trong tiêu chuẩn đều được thực hiện dễ dàng bởi các đơn vị phần cứng và không phát sinh khó khăn khi triển khai. Tuy nhiên, một thời gian sau khi tiêu chuẩn được công bố, các nhà phát triển phần mềm đã quyết định không đứng yên mà tiến hành tạo ra các hệ thống mã hóa. Hơn nữa DESđã được triển khai cả về phần cứng và phần mềm.