Even-Mansour là một mô hình lý thuyết để chứng minh kết quả bảo mật. Người ta sẽ cần lấy mẫu hoán vị của $n$ bit, nói cho $n=128,$ vì không gian kết quả của $N=2^n$ các đối tượng sẽ quá lớn để lưu trữ hoặc thao tác. Điều này tương tự như thực tế là không ai sử dụng i.i.d và i.i.d hoàn toàn ngẫu nhiên. chuỗi bit dưới dạng dòng khóa trong chế độ OTP trong mật mã hiện đại. Nó quá chậm.
Tuy nhiên, thuật toán sau đưa ra một hoán vị ngẫu nhiên trên $\{1,2,\ldots, N\}.$ Không có yêu cầu về hiệu quả tối ưu được thực hiện ở đây.
MÃ CHO PHÉP NGẪU NHIÊN CỦA DANH SÁCH NHỎ
Đầu vào: Danh sách $A=[1,2,\ldots, N]$ của $N=2^n$ mặt hàng.
Nhiệm vụ: hoán vị các giá trị trong $A$ ngẫu nhiên.
Để cho $S:=\{u: u \in A\}.$ Để cho $B:=A$
cho mỗi $i=1,\ldots,N$ làm
$\quad$ Chọn một số nguyên ngẫu nhiên $j \in S$
$\quad$ Thay đổi mảng $B$ qua $B[j]:=A[i]$
$\quad$ Gỡ bỏ $j$ từ bộ $S$
kết thúc cho
Thuật toán này chọn $N,$ sau đó $N-1$, sau đó $N-2$ v.v. các đối tượng một cách thống nhất và có thể tạo ra từng hoán vị với khả năng như nhau, vì nó tạo ra $N\!$ sự lựa chọn.
Đầu ra: Danh sách $A$ bây giờ là ngẫu nhiên.
Có nhiều cách hiệu quả hơn để lấy mẫu hoán vị ngẫu nhiên, xem ví dụ Jens Gustedt, "Efficient sampling of Random permutations", Tạp chí thuật toán rời rạc, Tập. 6, Số 1, 2006. Ngoài ra, hãy xem Fisher-Yates shuffle và Knuth Shuffle, google là bạn của bạn.
Thuật toán bên dưới không hoàn toàn đạt được điều đó, cảm ơn @kelalaka đã sửa lỗi
Đầu vào: Danh sách $A=\{1,2,\ldots, N\}$ của $N=2^n$ mặt hàng.
Nhiệm vụ: hoán vị các giá trị trong $A$ ngẫu nhiên.
cho mỗi $i=0,\ldots,N-1$ làm
$\quad$ Chọn một số nguyên ngẫu nhiên $j$ với $i<j<N.$
$\quad$ Hoán đổi các mục $A[i]$ và $A[j].$
kết thúc cho
Đầu ra: Danh sách $A$ bây giờ là ngẫu nhiên.
