Thuật toán mã hóa AES làm việc với các khối 128 bit. Với bản rõ \(p\) và khóa \(k\), hàm mã hóa \(E\) tạo ra bản mã \(c=E(p,k)\). Hàm giải mã \(D\) là hàm ngược tương ứng: \(D(E(p,k),k)=p\) và \(E(D(c,k),k)=c\).

Double AES dùng hai khóa độc lập \(k_1,k_2\) liên tiếp, trước tiên \(k_1\) rồi đến \(k_2\), tạo bản mã \(c_2=E(E(p,k_1),k_2)\).

Trong bài này, bạn còn được cho số nguyên \(s\). Chỉ \(4s\) bit ngoài cùng bên trái của mỗi khóa có thể khác 0; \(128-4s\) bit còn lại ở bên phải đều bằng 0. Bạn biết bản rõ \(p\), bản mã kép tương ứng \(c_2\) và số \(s\). Hãy khôi phục một cặp khóa phù hợp.

Đây là bài chỉ nộp kết quả: nộp các khóa tìm được, không nộp chương trình khôi phục khóa. Các thuật toán AES mã hóa và giải mã có trong thư viện của kỳ thi.

Dữ liệu vào

Có 10 bộ dữ liệu trong các tệp double1.in đến double10.in, được cung cấp trong tệp đính kèm double-inputs.zip. Mỗi tệp có ba dòng:

• Dòng đầu chứa \(s\), với \(1\le s\le5\).
• Dòng thứ hai chứa bản rõ \(p\).
• Dòng thứ ba chứa bản mã kép \(c_2\).

Mỗi khối được biểu diễn bằng đúng 32 chữ số thập lục phân từ 0 đến 9 và A đến F. Mọi bộ dữ liệu đều có lời giải.

Dữ liệu ra

Trên bản luyện tập này, chọn ngôn ngữ OUTPUT và nộp một tệp ZIP chứa 10 tệp kết quả ngay tại thư mục gốc của ZIP, không đặt trong thư mục con. Tên tệp kết quả được ánh xạ từ các tệp đầu vào gốc như sau:

Nội dung mỗi tệp giữ nguyên định dạng của kỳ thi gốc. Tệp ứng với đầu vào số \(I\), với \(1\le I\le10\), có ba dòng:

• Dòng đầu là #FILE double I, trong đó \(I\) là số thứ tự tệp đầu vào.
• Dòng thứ hai là khóa \(k_1\).
• Dòng thứ ba là khóa \(k_2\).

Mỗi khóa phải gồm đúng 32 chữ số thập lục phân in hoa, có các bit không liên quan bằng 0 như đã quy định, và thỏa mãn \(c_2=E(E(p,k_1),k_2)\). Nếu có nhiều cặp khóa, chỉ cần nộp một cặp.

Chẳng hạn, 01.out phải bắt đầu bằng #FILE double 1, còn 10.out bắt đầu bằng #FILE double 10. Số trong dòng #FILE là số bộ dữ liệu gốc, không thêm số 0 ở đầu như trong tên tệp ZIP.

Thư viện dùng thử

Tệp đính kèm double-aes-templates.zip cung cấp mã nguồn C/C++ tương thích với giao diện AES-128 của đề gốc, gồm aeslibc.h, aeslibc.c, chương trình gọi mẫu aestoolc.c và hướng dẫn README.md. Đây là bản cài đặt hiện đại, không phải thư viện nhị phân gốc. Sau khi giải nén, có thể biên dịch và chạy chương trình mẫu bằng:

gcc -std=c99 -O2 aestoolc.c aeslibc.c -o aestoolc
./aestoolc

Chương trình mẫu đọc từ đầu vào chuẩn một bản rõ và một khóa, mỗi khối gồm 32 chữ số thập lục phân in hoa, rồi in bản mã sau một lần mã hóa. Để mã hóa kép, gọi encrypt hai lần với hai khóa theo thứ tự \(k_1,k_2\). Chương trình mẫu chỉ minh họa cách gọi thư viện, không khôi phục khóa. Khi dùng thư viện trong chương trình của bạn, khai báo #include "aeslibc.h" và liên kết với phần cài đặt trong aeslibc.c.

Các tệp đối tượng và thư viện Pascal được mô tả trong phần giao diện gốc dưới đây chỉ thuộc môi trường kỳ thi năm 2001; chúng không nằm trong gói dùng thử hiện tại.

Thư viện gốc

Thư viện C/C++ dùng aeslibc.h và aeslibc.o, với các khai báo:

typedef char HexStr[33];
typedef unsigned char Block[16];
void hexstr2block(const HexStr hs, Block b);
void block2hexstr(const Block b, HexStr hs);
void encrypt(const Block p, const Block k, Block c);
void decrypt(const Block c, const Block k, Block p);

HexStr là chuỗi ký tự 0–9, A–F kết thúc bằng \0; Block chứa 128 bit. Hai hàm đầu chuyển đổi hai cách biểu diễn. encrypt ghi \(E(p,k)\) vào c; decrypt ghi \(D(c,k)\) vào p. Chương trình aestoolc.c minh họa cách dùng thư viện.

Thư viện FreePascal dùng aeslibp.p, aeslibp.ppu, aeslibp.o trên Linux, hoặc aeslibp.p, aeslibp.ppw, aeslibp.ow trên Windows:

type
  HexStr = String[32];
  Block = array[0..15] of Byte;
procedure HexStrToBlock(const hs: HexStr; var b: Block);
procedure BlockToHexStr(const b: Block; var hs: HexStr);
procedure Encrypt(const p, k: Block; var c: Block);
procedure Decrypt(const c, k: Block; var p: Block);

Chương trình aestoolp.pas minh họa cách dùng thư viện Pascal. Trong môi trường gốc, biên dịch bằng fpc aestoolp.pas, hoặc gcc -o aestoolc aestoolc.c aeslibc.o cho C. Trong IDE Pascal, mở tệp rồi chọn Run -> Run; trong RHIDE, mở aestoolc.c, thêm aeslibc.o ở Options -> Linker Options -> Parameter, rồi chọn Run -> Run.

Một chương trình tốt có thể khôi phục khóa trong ít hơn 10 giây cho mọi dữ liệu cho phép; đây là gợi ý của đề gốc, không phải giới hạn chạy của một bài nộp mã nguồn.

Chấm điểm

Bộ dữ liệu 1 tương ứng 1 điểm; mỗi bộ từ 2 đến 10 tương ứng 11 điểm. Tổng điểm tối đa là 100. Mỗi bộ chỉ nhận điểm nếu cặp khóa hợp lệ.

Ví dụ

1
00112233445566778899AABBCCDDEEFF
6323B4A5BC16C479ED6D94F5B58FF0C2

#FILE double 0
A0000000000000000000000000000000
70000000000000000000000000000000

Nguồn

Đề gốc IOI 2001. Bảng tổng quan ngày 2.