Nhược điểm chính của des. Thuật toán mã hóa DES và AES

phím đối xứng .

Đề xuất sửa đổi dự án của IBM, được gọi là Lucifer, đã được thông qua dưới dạng DES. DES đã được xuất bản ở dạng dự thảo vào năm Đăng ký liên bang vào tháng 3 năm 1975 như Tiêu chuẩn xử lý thông tin liên bang (FIPS – Tiêu chuẩn xử lý thông tin liên bang).

Khi xuất bản, bản phác thảo đã bị chỉ trích nặng nề vì hai lý do. Đầu tiên, có những lời chỉ trích về độ dài khóa nhỏ đáng ngờ (chỉ 56 bit), có thể khiến mật mã dễ bị tấn công vũ phu. Lý do thứ hai: các nhà phê bình lo ngại về một số thiết kế ẩn giấu trong cấu trúc bên trong của DES.

Họ nghi ngờ rằng một phần nào đó của cấu trúc (hộp S) có thể có lỗ hổng ẩn, điều này sẽ cho phép bạn giải mã tin nhắn mà không cần khóa. Các nhà thiết kế của IBM sau đó đã báo cáo rằng cấu trúc bên trong đã được sửa đổi để ngăn chặn việc phân tích mật mã.

DES cuối cùng đã được xuất bản dưới dạng FIPS 46 trong Sổ đăng ký Liên bang vào tháng 1 năm 1977. Tuy nhiên, FIPS tuyên bố DES là một tiêu chuẩn để sử dụng trong ứng dụng không chính thức. DES được sử dụng rộng rãi nhất khóa mật mã Với phím đối xứng, bắt đầu từ lần xuất bản của nó. NIST sau đó đã đề xuất tiêu chuẩn mới(FIPS 46-3), khuyến nghị sử dụng bộ ba DES (mật mã DES ba lần lặp lại) cho các ứng dụng trong tương lai. Như chúng ta sẽ thấy ở phần sau của bài giảng ngày 9-10, tiêu chuẩn AES mới hơn dự kiến ​​sẽ thay thế DES.

Các quy định chung

Như thể hiện trong hình. 8.1. DES - mật mã khối.

Cơm. 8.1.

Ở bên cạnh mã hóa DES chấp nhận 64-bit văn bản gốc và tạo ra bản mã 64 bit; Về mặt giải mã, DES lấy bản mã 64 bit và tạo ra bản rõ 64 bit. Cả hai bên đều sử dụng cùng một khóa 56 bit để mã hóa và giải mã.

8.2. cấu trúc DES

Trước tiên hãy xem xét mã hóa và sau đó là giải mã. Quá trình mã hóa bao gồm hai hoán vị (khối P) - được gọi là hoán vị bắt đầu và kết thúc - và mười sáu vòng Feistel. Mỗi vòng sử dụng một khóa 48 bit được tạo khác nhau. Thuật toán tạo sẽ được thảo luận sau trong bài giảng này. Hình 8.2 cho thấy các thành phần của mật mã DES ở phía mã hóa.

Hoán vị bắt đầu và kết thúc

Hình 8.3 cho thấy các hoán vị ban đầu và cuối cùng (khối P). Mỗi hoán vị lấy đầu vào 64 bit và sắp xếp lại các phần tử của nó theo một quy tắc nhất định. Chúng tôi chỉ hiển thị một số lượng nhỏ cổng đầu vào và cổng đầu ra tương ứng. Những hoán vị này là những hoán vị trực tiếp không có khóa, là những hoán vị nghịch đảo của nhau. Ví dụ: trong hoán vị ban đầu, bit thứ 58 của đầu vào sẽ chuyển sang bit đầu tiên của đầu ra. Tương tự, trong hoán vị cuối cùng, bit đầu vào đầu tiên sẽ chuyển sang bit đầu ra thứ 58. Nói cách khác, nếu không có vòng giữa hai hoán vị này, bit thứ 58 được cung cấp cho đầu vào của thiết bị hoán vị ban đầu sẽ được chuyển đến đầu ra thứ 58 bằng hoán vị cuối cùng.

Cơm. 8.2.

Cơm. 8.3.

Các quy tắc hoán vị cho hộp P này được thể hiện trong Bảng 8.1. Bảng có thể được biểu diễn dưới dạng mảng 64 phần tử. Lưu ý rằng chúng ta đã thảo luận về cách làm việc với bảng; giá trị của mỗi phần tử xác định số cổng đầu vào và số sê-ri (chỉ mục) của phần tử xác định số cổng đầu ra.

Bảng 8.1. Bảng hoán vị đầu và cuối

Hoán vị ban đầu								hoán vị hữu hạn
58	50	42	34	26	18	10	02	40	08	48	16	56	24	64	32
60	52	44	36	28	20	12	04	39	07	47	15	55	23	63	31
62	54	46	38	30	22	14	06	38	06	46	14	54	22	62	30
64	56	48	40	32	24	16	08	37	05	45	13	53	21	61	29
57	49	41	33	25	17	09	01	36	04	44	12	52	20	60	28
59	51	43	35	27	19	11	03	35	03	43	11	51	19	59	27
61	53	45	37	29	21	13	05	34	02	42	10	50	18	58	26
63	55	47	39	31	23	15	07	33	01	41	09	49	17	57	25

Hai hoán vị này không có ý nghĩa gì đối với mật mã trong

• 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 cho cặp văn bản công khai/riêng 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õ.

Thuật toán DES khá phù hợp cho cả việc mã hóa và xác thực dữ liệu. Nó cho phép đầu vào văn bản gốc 64 bit được chuyển đổi trực tiếp thành đầu ra văn bản mã hóa 64 bit, nhưng dữ liệu hiếm khi bị giới hạn ở 64 bit.

Để sử dụng thuật toán DES giải quyết nhiều vấn đề về mật mã, bốn chế độ hoạt động đã được phát triển:

· Sách mã điện tử ECB (Sách mã điện tử);

· nối các khối mật mã CBC (Chuỗi khối mật mã);

· Phản hồi văn bản mã hóa CFB (Cipher Feed Back);

· Phản hồi về đầu ra OFB (Output Feed Back).

Chế độ “Sổ mã điện tử”

Một tệp dài được chia thành các đoạn (khối) 64 bit 8 byte. Mỗi khối này được mã hóa độc lập bằng cách sử dụng cùng một khóa mã hóa (Hình 3.6).

Ưu điểm chính là dễ thực hiện. Nhược điểm: Khả năng chống chịu tương đối yếu trước các nhà giải mã lành nghề. Do tính chất cố định của mã hóa, với độ dài khối giới hạn là 64 bit, việc phân tích mật mã "từ điển" là có thể. Một khối có kích thước này có thể được lặp lại trong một tin nhắn do tính dư thừa cao trong văn bản ngôn ngữ tự nhiên.

Hình 3.6 – Sơ đồ thuật toán DES ở chế độ sổ mã điện tử

Điều này làm cho các khối văn bản gốc giống hệt nhau trong một tin nhắn được biểu diễn bằng các khối văn bản mã hóa giống hệt nhau, cung cấp cho người giải mã một số thông tin về nội dung của tin nhắn.

Chế độ "Xâu chuỗi khối mật mã"

Ở chế độ này, tệp nguồn M được chia thành các khối 64 bit: M = M 1 M 2 ...M n. Khối đầu tiên M 1 được thêm modulo 2 với vectơ IV ban đầu 64 bit, thay đổi hàng ngày và được giữ bí mật (Hình 3.7). Số tiền nhận được sau đó được mã hóa bằng khóa DES mà cả người gửi và người nhận thông tin đều biết. Mật mã 64 bit thu được C 1 được thêm modulo 2 với khối văn bản thứ hai, kết quả được mã hóa và thu được mật mã 64 bit thứ hai C 2, v.v. Quy trình được lặp lại cho đến khi tất cả các khối văn bản được xử lý.

Như vậy, với mọi i = 1…n (n là số khối), kết quả mã hóa C i được xác định như sau: C i =

DES (М i  C i –1), trong đó С 0 = IV là giá trị ban đầu của mật mã, bằng vectơ ban đầu (vectơ khởi tạo).

Rõ ràng, khối bản mã 64-bit cuối cùng là một hàm của khóa bí mật, vectơ hạt giống và mỗi bit

Hình 3.7 – Sơ đồ thuật toán DES trong chế độ chuỗi khối mật mã

bản rõ bất kể độ dài của nó. Khối bản mã này được gọi là mã xác thực tin nhắn (MAC).

Mã CAS có thể được xác minh dễ dàng bởi người nhận, người có khóa bí mật và vectơ hạt giống, bằng cách lặp lại quy trình do người gửi thực hiện. Tuy nhiên, người ngoài không thể tạo UAS được người nhận coi là chính hãng để thêm vào tin nhắn sai hoặc tách UAS khỏi tin nhắn thật để sử dụng với tin nhắn đã sửa đổi hoặc sai.

Ưu điểm của chế độ này là không cho phép tích lũy lỗi trong quá trình truyền.

Khối M i chỉ là hàm của C i –1 và C i . Vì vậy, một lỗi truyền tải sẽ dẫn đến việc chỉ mất đi hai khối văn bản nguồn.

Chế độ "Phản hồi của Cypher"

Ở chế độ này, kích thước khối có thể khác với 64 bit (Hình 3.8). Tệp cần mã hóa (giải mã) được đọc theo từng khối có độ dài k bit liên tiếp (k=1...64).

Khối đầu vào (thanh ghi dịch chuyển 64 bit) trước tiên chứa vectơ khởi tạo căn phải.

Giả sử rằng nhờ chia thành các khối, chúng ta nhận được n khối có độ dài k bit mỗi khối (phần còn lại được thêm vào bằng số 0 hoặc dấu cách). Sau đó, với bất kỳ khối bản mã i=1…n nào

С i = M i  P i –1 ,

trong đó P i–1 biểu thị k bit quan trọng nhất của khối được mã hóa trước đó.

Thanh ghi dịch được cập nhật bằng cách loại bỏ k bit cao nhất của nó và ghi C i vào thanh ghi. Việc khôi phục dữ liệu bị mã hóa cũng tương đối đơn giản: P i –1 và C i được tính theo cách tương tự và

М tôi = С tôi  Р tôi –1 .

Hình 3.8 – Sơ đồ thuật toán DES ở chế độ phản hồi bản mã

Chế độ phản hồi đầu ra

Chế độ này cũng sử dụng kích thước khối thay đổi và thanh ghi dịch chuyển được khởi tạo theo cách tương tự như trong chế độ CFB, cụ thể là khối đầu vào trước tiên chứa vectơ khởi tạo IV, được căn chỉnh sang phải (Hình 3.9). Trong trường hợp này, đối với mỗi phiên mã hóa dữ liệu, cần phải sử dụng trạng thái ban đầu mới của thanh ghi, trạng thái này phải được gửi qua kênh ở dạng văn bản rõ ràng.

M = M 1 M 2 ... M n.

Với mọi i = 1…n

C i = M i  P i ,

trong đó Р i là k bit cao nhất của phép toán DES (С i –1).

Sự khác biệt so với chế độ phản hồi bản mã là phương pháp cập nhật thanh ghi dịch.

Điều này được thực hiện bằng cách loại bỏ k bit cao nhất và thêm P i vào bên phải.

Hình 3.9 – Sơ đồ thuật toán DES ở chế độ phản hồi đầu ra

3.3. Các lĩnh vực ứng dụng của thuật toán DES

Mỗi chế độ được xem xét (ECB, CBC, CFB, OFB) đều có những ưu điểm và nhược điểm riêng, quyết định lĩnh vực ứng dụng của chúng.

Chế độ ECB rất phù hợp cho việc mã hóa khóa: chế độ CFB thường được dùng để mã hóa các ký tự riêng lẻ và chế độ OFB thường được sử dụng để mã hóa trong các hệ thống thông tin vệ tinh.

Chế độ CBC và CFB phù hợp để xác thực dữ liệu. Các chế độ này cho phép bạn sử dụng thuật toán DES để:

· mã hóa tương tác khi trao đổi dữ liệu giữa thiết bị đầu cuối và máy tính chủ;

· mã hóa khóa mật mã trong thực tiễn phân phối khóa tự động;

· mã hóa các tập tin, thư, dữ liệu vệ tinh và các nhiệm vụ thực tế khác.

Ban đầu, tiêu chuẩn DES được dùng để mã hóa và giải mã dữ liệu máy tính. Tuy nhiên, ứng dụng của nó đã được khái quát hóa để xác thực.

Trong các hệ thống xử lý dữ liệu tự động, con người không có cách nào xem xét dữ liệu để xác định liệu có bất kỳ thay đổi nào đã được thực hiện đối với dữ liệu đó hay không. Với lượng dữ liệu khổng lồ chảy qua các hệ thống xử lý hiện đại, việc duyệt web sẽ mất quá nhiều thời gian. Ngoài ra, sự dư thừa dữ liệu có thể không đủ để phát hiện lỗi. Ngay cả trong trường hợp có thể thực hiện đánh giá của con người, dữ liệu có thể bị thay đổi theo cách khiến con người rất khó phát hiện ra những thay đổi đó. Ví dụ: “làm” có thể được thay thế bằng “không”, “$1900” bằng “$9100”. Nếu không có thông tin bổ sung, người xem có thể dễ dàng nhầm dữ liệu đã thay đổi với dữ liệu chính hãng. Những mối nguy hiểm như vậy có thể tồn tại ngay cả khi sử dụng mã hóa dữ liệu. Vì vậy, mong muốn có một phương tiện tự động để phát hiện những thay đổi dữ liệu có chủ ý và vô ý.

Các mã phát hiện lỗi thông thường không phù hợp vì nếu biết thuật toán tạo mã, kẻ tấn công có thể tạo mã chính xác sau khi thực hiện các thay đổi đối với dữ liệu. Tuy nhiên, bằng cách sử dụng thuật toán DES, có thể tạo ra tổng kiểm tra mật mã có thể bảo vệ chống lại những thay đổi vô tình và cố ý nhưng trái phép đối với dữ liệu.

Quá trình này mô tả tiêu chuẩn xác thực dữ liệu máy tính (FIPS 113). Bản chất của tiêu chuẩn là dữ liệu được mã hóa ở chế độ phản hồi bản mã (chế độ CFB) hoặc ở chế độ nối khối mật mã (chế độ CBC), dẫn đến khối mật mã cuối cùng là chức năng của tất cả các bit văn bản gốc. Sau đó, thông báo chứa văn bản gốc có thể được truyền đi bằng cách sử dụng khối mật mã cuối cùng được tính toán, đóng vai trò là tổng kiểm tra mật mã.

Dữ liệu giống nhau có thể được bảo vệ bằng cả mã hóa và xác thực. Dữ liệu được bảo vệ khỏi sự truy cập bằng mã hóa và các thay đổi được phát hiện thông qua xác thực. Thuật toán xác thực có thể được áp dụng cho cả bản rõ và bản mã. Trong các giao dịch tài chính, trong hầu hết các trường hợp, cả mã hóa và xác thực đều được triển khai, điều sau cũng áp dụng cho giao dịch mở.

văn bản mu.

Mã hóa và xác thực được sử dụng để bảo vệ dữ liệu được lưu trữ trong máy tính. Trong nhiều máy tính, mật khẩu được mã hóa không thể đảo ngược và được lưu trong bộ nhớ của máy. Khi người dùng truy cập vào máy tính và nhập mật khẩu, mật khẩu sau sẽ được mã hóa và so sánh với giá trị được lưu trữ. Nếu cả hai giá trị được mã hóa giống nhau, người dùng sẽ có quyền truy cập vào máy, nếu không thì bị từ chối.

Thông thường, mật khẩu được mã hóa được tạo bằng thuật toán DES, với khóa bằng mật khẩu và bản rõ bằng mã nhận dạng người dùng.

Sử dụng thuật toán DES, bạn cũng có thể mã hóa các tệp máy tính để lưu trữ.

Một trong ứng dụng quan trọng nhất thuật toán DES là bảo vệ tin nhắn của hệ thống thanh toán điện tử (EPS) trong quá trình giao dịch với nhiều khách hàng và giữa các ngân hàng.

Thuật toán DES được triển khai trong máy ATM, thiết bị đầu cuối điểm bán hàng, máy trạm và máy tính lớn. Phạm vi dữ liệu mà nó bảo vệ rất rộng - từ khoản thanh toán 50 đô la đến chuyển khoản hàng triệu đô la. Tính linh hoạt của thuật toán DES cốt lõi cho phép nó được sử dụng trong nhiều ứng dụng hệ thống thanh toán điện tử.

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ố tính chất "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 các 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.