- Trang Chủ
- An ninh - Bảo mật
- E-RISKE, một sơ đồ mật mã khóa bí mật dựa trên các phần tử khả nghịch và khả nghịch mở rộng trong các vành đa thức bậc hữu hạn hệ số nhị phân có hai lớp kề cyclic
Xem mẫu
- Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
E-RISKE, một sơ đồ mật mã khóa bí mật dựa
trên các phần tử khả nghịch và khả nghịch mở
rộng trong các vành đa thức bậc hữu hạn hệ số
nhị phân có hai lớp kề cyclic
Cao Minh Thắng∗ , Nguyễn Bình∗ , Hoàng Mạnh Thắng∗ , Nguyễn Ngọc Quân∗
∗Học Viện Công Nghệ Bưu Chính Viễn Thông
Email: {thangcm, nguyenbinh, thanghm, quannn}@ptit.edu.vn
Tóm tắt—Các phần tử khả nghịch trong vành đa thức dụng phổ biến trong mã sửa sai nhưng đã không được
bậc hữu hạn đã được khai thác để xây dựng một số hệ ứng dụng rộng rãi trong mật mã loại trừ lớp vành Rn,2
mật khóa công khai thú vị như NTRU và pNE. Trong bài với n = 2N |N ∈ Z + . Năm 2002, các nhóm nhân cyclic
báo này, sau khi đề xuất khái niệm "khả nghịch mở rộng",
chúng tôi sẽ giới thiệu một lớp đặc biệt của các vành đa
trong R2k ,2 đã được khai thác để để xây dựng một hệ
thức bậc hữu hạn hệ số nhị phân trong đó tất cả các đa mật khóa bí mật [7] và hệ mật này sau đó được để xuất
thức đều khả nghịch hoặc khả nghịch mở rộng. Bằng cách như là một phiên bản mới của DES [8].
khai thác các phần tử này, chúng tôi đề xuất một sơ đồ Mục II của bài báo trình bày một số khái niệm về
mật mã mới có tên là E-RISKE và chứng minh về mặt lý sơ đồ mật mã và độ an toàn chứng minh được. Trong
thuyết rằng hệ mật này không những tính toán hiệu quả mục III, với khái niệm "khả nghịch mở rộng", chúng
mà còn chống lại được tấn công phân biệt bằng bản bản tôi giới thiệu một lớp đặc biệt của Rn,2 trong đó có số
rõ được chọn (hay còn gọi là IND-CPA).
Từ khóa—Sơ đồ mật mã, khóa bí mật, vành đa thức các phần tử khả nghịch (và tương ứng là số các phần tử
bậc hữu hạn hệ số nhị phân, hai lớp kề cyclic, phần tử khả nghịch mở rộng) là rất lớn (Định lý 1). Bằng cách
khả nghịch mở rộng. khai thác tập phần tử đó, trong phần IV, chúng tôi đề
xuất một sơ đồ mật mã khóa bí mật xác suất có tên
I. GIỚI THIỆU là E-RISKE (Extended Random Invertible Secret-Key
Ứng dụng của các phần tử khả nghịch trên vành đa Encryption scheme) với tốc độ tính toán nhanh và được
thức Rn,q = Zq [x]/(xn − 1) trong mật mã rất phổ biến, chứng minh là an toàn với các tấn công nghe lén (IND-
điển hình là hệ mật khóa công khai xác suất nổi tiếng EAV) trong định lý 2 và tấn công phân biệt bằng bản
NTRU [2] và các biến thể như CTRU [3] và đặc biệt là rõ được chọn (IND-CPA) trong định lý 3. Kết luận và
pNE [6], một hệ mật dựa trên vành R2s ,q |s ∈ Z + , cho đề xuất hướng nghiên cứu tiếp theo được đề cập trong
đến nay có thể coi là biến thể duy nhật của NTRU có mục V.
độ an toàn chứng minh được.
Lợi ích của việc sử dụng các phần tử khả nghịch trong II. CÁC KHÁI NIỆM IND-EAV VÀ IND-CPA
mật mã là tốc độ tính toán. Cụ thể là, phép nhân modulo Trong phần này, ta sẽ nhắc lại một số khái niệm về
trong vành đa thức Rn,q chỉ cần O(n2 ) phép tính. Bằng sơ đồ mật mã có độ an toàn chứng minh được.
cách khai thác đặc điểm này, cùng với độ an toàn liên
Định nghĩa 1. Một sơ đồ mật mã Π(G, E, D, K, P, C),
quan tới một số bài toán khó trên dàn, NTRU có tốc
gồm 3 thuật toán là sinh khóa G, mã hóa E và giải mã
độ tính toán nhanh hơn các sơ đồ mật mã dựa trên số
D cùng với 3 không gian là không gian bản rõ P, không
nguyên và logarit rời rạc trên trường hữu hạn và đường
gian bản mã C, và không gian khóa K.
cong eliptic. Hệ quả là, hệ mật này đã được chuẩn hóa
bởi IEEE trong tiêu chuẩn P.1363.1 năm 2008 và được Định nghĩa 2. (Định nghĩa 3.4 trong [1]) Với n ∈ Z + ,
coi là một đề cử thay thế các hệ mật khoá công khai hàm f (n) được gọi là "không đáng kể" (negligible) với
truyền thống. biến n khi với mọi đa thức p(n) đều tồn tại một số tự
Vành đa thức bậc hữu hạn hệ số nhị phân Rn = nhiên N0 thỏa mãn ∀n > N0 ta đều có f (n) < p(n) 1
.
Z2 [x]/(xn + 1), một lớp của Rn,q , mặc dù được sử
ISBN: 978-604-67-0635-9 240
- Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
Định đề 1. 2−n và theo đó 1
2(n−1) −1
đều là các hàm IND-EAV-ATK thành công là không đáng kể hay
không đáng kể với biến n. 1
Pr[SecKeav
A,Π (n) = 1] ≤ + μ(n).
2
Định đề 2. Nếu p(n) là một đa thức của n và f (n) là
một hàm không đáng kể với biến n thì p(n).f (n) cũng với μ(n) là một hàm không đáng kể của n.
là một hàm không đáng kể với biến n. Định nghĩa 6. [1] Một sơ đồ mã hóa khóa bí mật Π
được gọi là an toàn với tấn công phân biệt bằng bản
Định nghĩa 3. Tấn công phân biệt bằng nghe lén (IND-
rõ được chọn, viết tắt là IND-CPA, nếu xác suất để thí
EAV-ATK: Eavesdropping Indistinghuisability Attack)
nghiệm IND-CPA-ATK thành công là không đáng kể hay
đối với một sơ đồ mã hóa khóa bí mật, ký hiệu là
SecKeav 1
A,Π (n), được mô tả như sau:[1] Pr[SecKcpa
A,Π (n) = 1] ≤ + μ(n).
2
1) Kẻ nghe lén (eavesdropper) A chọn một cặp bản với μ(n) là một hàm không đáng kể của n.
rõ m0 , m1 có cùng chiều dài trong không gian
bản rõ và gửi tới bộ mã hoá. Chú ý rằng độ dài Có thể thấy, loại hình tấn công IND-CPA-ATK, trong
của cặp bản tin m0 , m1 có thể khác độ dài n của đó kẻ tấn công có thể truy cập không giới hạn tới thủ
khoá bí mật k. tục mã hóa E, là mạnh hơn tấn công IND-EVA-ATK.
2) Bộ mã hoá chọn ngẫu nhiên một khóa k ∈ K có độ Do đó, ta có thể coi IND-CPA là an toàn hơn IND-EAV.
dài n bit và chọn ngẫu nhiên một bit b ← {0, 1} III. CÁC PHẦN TỬ KHẢ NGHỊCH VÀ KHẢ NGHỊCH MỞ
để tính một bản mã c ← Ek (mb ) được tính toán RỘNG TRÊN VÀNH ĐA BẬC HỮU HẠN HỆ SỐ NHỊ PHÂN
và trả lại cho A.
Trong phần này, chúng tôi sẽ tập trung vào các vành
3) Khi nhận được c, A thực hiện tính toán và đưa ra
đa thức nhị phân hữu hạn và các phân tử khả nghịch
giá trị b� .
cũng như khả nghịch mở rộng của nó. Để thuận tiện, ta
4) Kết quả của tấn công trả về là 1 nếu b� = b và 0
ký hiệu GF (2)[x]/(xn + 1)|n ∈ Z + là Rn với giá trị 2
trong trường hợp còn lại. Nếu SecKeavA,Π (n) = 1
là ngầm định.
thì có thể nói A đã thực hiện thành công loại tấn
công này. A. Các định nghĩa và ký hiệu
Định nghĩa 7. Vành đa thức bậc hữu hạn hệ số nhị phân
Định nghĩa 4. Thí nghiệm tấn công phân biệt bằng bản
Rn là tập các đa thức f có bậc nhỏ một số nguyên n
rõ được chọn (IND-CPA-ATK: Chosen Plain-text Attack
và các hệ số nằm trong GF (2).
Indistinghuishability Attack) đối với một sơ đồ mã hoá
khoá bí mật trong [1], ký hiệu là SecKcpa
A,Π (n), được mô Một phần tử f ∈ Rn có thể được biểu diễn là
tả như sau: [1] n−1
f= fi
1) Kẻ tấn công A được quyền truy cập không giới
i=0
hạn tới bộ mã hoá. A chọn một cặp bản rõ m0 , m1
có cùng chiều dài trong không gian bản rõ và gửi dưới định dạng đa thức hoặc
tới bộ mã hoá. Chú ý rằng độ dài của cặp bản tin f = (f0 , f1 , . . . , fn−1 )
m0 , m1 có thể khác độ dài n của khoá bí mật k.
2) Bộ mã hoá chọn ngẫu nhiên một khóa k ∈ K có độ dưới định dạng vector.
dài n bit và chọn ngẫu nhiên một bit b ← {0, 1} Trong Rn , toán tử nhân được ký hiệu là ∗, được hiểu
để tính một bản mã c ← Ek (mb ) và trả lại cho A. là phép nhân module xn + 1, nghĩa là nếu h = f ∗ g thì
3) A có thể tiếp tục truy nhập không giới hạn số lần h có hệ số
tới bộ mã hoá.
hk = ( fi .gj ) mod 2
4) Kết quả của thí nghiệm trả về là 1 nếu b� = b và
i+j=k mod n
0 trong trường hợp còn lại. Nếu SecKcpa
A,Π (n) = 1
thì có thể nói A đã thực hiện thành công loại tấn với 0 ≤ k ≤ n − 1.
công này. Bên cạnh đó, phép cộng trong Rn được ký hiệu là +
và như vậy nếu h = f + g thì
Định nghĩa 5. [1] Một sơ đồ mã hóa khóa bí mật Π n−1
được gọi là an toàn với tấn công phân biệt bằng nghe h= hi
lén, viết tắt là IND-EAV, nếu xác suất để thí nghiệm i=0
241
- Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
với hi = (fi + gi ) mod 2. Bổ đề 3. Trong Rn , tất cả các đa thức có trọng số
Hamming chẵn đều không khả nghịch.
Định nghĩa 8. Trọng số Hamming của đa thức f ∈ Rn
được ký hiệu là w(f ). Chứng minh: Giả sử f ∈ Rn là một đa thức có
trọng số Hamming chẵn. Theo bổ đề 2 thì ∀g ∈ Rn ,
Định nghĩa 9. Một đa thức f ∈ Rn được gọi là khả
w(f ∗ g) luôn chẵn hay nói cách khác không tồn tại
nghịch nếu tồn tại đa thức g ∈ Rn thỏa mãn f ∗ g = 1.
bất kỳ đa thức h nào thỏa mãn w(f ∗ h) lẻ. Mặt khác
Để thuận lợi, ta ký hiệu tập các đa thức khả nghịch w(1) = 1 là một số lẻ. Do đó, ta có thể kết luận không
trong Rn là In . tồn tại đa thức h thoả mãn w(f ∗ h) = 1 hay f không
khả nghịch.
Định nghĩa 10. Trong Rn , một đa thức e được gọi là
lũy đẳng nếu e2 = e. C. Lũy đẳng nuốt và khả nghịch mở rộng
n−1 i
Trong Rn , e1 = 1 là một lũy Bổ đề 4. Trong Rn , với e0n = i=0 x , ta luôn có
đẳng
n−1
tầm thường. Với n
f ∗ e0n = (w(f ) mod 2).e0n ∀f ∈ Rn .
lẻ ta có thể thấy rằng e0n = i=0 xi cũng là một lũy
n−1
đẳng. Chứng minh: Giả sử f = i=0 fi .xi ta có
Định nghĩa 11. Tỉ lệ số các phần tử khả nghịch trên
tổng số các đa thức trong Rn được ký hiệu là Kn . f.x0 = f0 + f1 .x + · · · + fn−1 .xn−1
Vì các đa thức khả nghịch luôn có trọng số Ham- f.x1 = fn−1 + f0 .x + · · · + fn−2 .xn−1
ming lẻ nên giá trị lớn nhất của Kn là max(Kn ) = ..
max(|In |)/|Rn | = 1/2. .
f.xn−1 = f1 + f2 .x + · · · + f0 .xn−1
B. Trọng số Hamming của các đa thức khả nghịch
và
Bổ đề 1. Trong Rn , nếu w(f ) = 2k, w(g) = 2l|k, l ∈
n−1
n−1
n−1
Z + thì w(f + g) chẵn.
f.e0n = fi .xi = (( fj ) mod 2).xi
Chứng minh: Với
i=0 i=0 j=0
N −1 N −1
i=0 fi x và g = i=0 gi x ta có
i i
f= n−1
n−1
N −1 = (w(f ) mod 2).xi = (w(f ) mod 2). xi
h=f +g = hi .xi i=0 i=0
i=0
= (w(f ) mod 2).e0n
với hi = (fi + gi ) mod 2.
Vì fi , gi ∈ GF (2) nên hi = 0 khi và chỉ khi fi = gi .
Gọi S là tập hợp chứa các giá trị i thỏa mãn fi = gi = 1. Bổ đề 5. Trong Rn với n lẻ, đa thức
Dễ thấy n−1
e0n = fi .xi
w(h) = w(f ) − |S| + w(g) − |S| = 2(k + l − |S|). i=0
là lũy đẳng.
Tổng quát hơn, nếu h là tổng của các đa thức có trọng Chứng minh: Ta có
số Hamming chẵn thì w(h) cũng chẵn. n−1
e20n = e0n ∗ (1 + fi .xi )
Bổ đề 2. Trong Rn , nếu w(f ) chẵn thì ∀g ∈ Rn , w(g ∗
i=1
f ) luôn chẵn. n−1
Chứng minh: Giả sử g có dạng = e0n + e0n ∗ fi .xi .
n−1
g = i=0 gi xi ta có i=1
n−1
N −1
Vì n lẻ, w( i=1 x ) luôn chẵn nên theo bổ đề 4,
i
i n−1
h=g∗f = gi .x ∗ f .
i=0 e0n ∗ =0
i=0
Vì w(gi .x ∗ f ) = gi .w(f ) và luôn chẵn do đó, theo bổ
i
đề 1, w(h) cũng chẵn. và e20n = e0n . Do đó, theo định nghĩa 10, e0n là lũy
đẳng trong Rn .
242
- Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
Định nghĩa 12. Trong Rn , một lũy đẳng e được gọi là Bổ đề 7. Trong Rn với n lẻ, chọn k ∈ En với nghịch
lũy đẳng nuốt khi đảo mở rộng là ke−1 , nếu biết c = m ∗ k và w(m) thì
ta có thể tính được
f ∗ e = (w(f ) mod 2).e
m = (w(m) mod 2).e0n + ke−1 ∗ c
∀f ∈ Rn .
n−1 Chứng minh: Do ke−1 ∗ k = e0n + 1, nên
Chú ý rằng, trong Rn với n lẻ thì e0n = i=0 x là
i
một lũy đẳng nuốt. ke−1 ∗ c = ke−1 ∗ c = ke−1 ∗ k ∗ m
= (e0n + 1) ∗ m = m + (w(m) mod 2).e0n
Định nghĩa 13. Trong Rn , một đa thức f � = f + e0n
được gọi là đa thức bù của f . Hệ quả là, m = (w(m) mod 2).e0n + ke−1 ∗ c
Ví dụ, trong R5 , k = x2 + x là nghịch đảo mở rộng
Như vậy, rõ ràng f cũng là một đa thức bù của f �
của ke−1 = x2 + 1.
trong Rn .
Với m = x3 + x ta có
Định nghĩa 14. Trong Rn với n lẻ, nếu một đa thức f
c = m ∗ ke−1 = x4 + x3 + x2 + 1
được gọi là khả nghịch mở rộng nếu tồn tại thức g ∈ Rn
thỏa mãn và vì w(m) mod 2 = 0 nên
f ∗ g = (e0n + 1). m = k ∗ c = (x2 + x) ∗ (x4 + x3 + x2 + 1)
Trong trường hợp này, g được gọi là nghịch đảo mở = (x3 + x).
rộng của f trong Rn .
Trong trường hợp m = x3 + x + 1, ta có
Để thuận tiện, ta ký hiệu tập các đa thức khả nghịch
c = m ∗ ke−1 = (x3 + x2 + x + 1)
mở rộng trong Rn là En .
và vì w(m) = 3 hay w(m) mod 2 = 1, nên
Bổ đề 6. Trong Rn với n lẻ, nếu đa thức f khả nghịch
với nghịch đảo g thì m = e05 + k ∗ c
f � = f + e0n = (x4 + x3 + x2 + x + 1)
+ (x2 + x) ∗ (x3 + x2 + x + 1)
là một đa thức khả nghịch mở rộng với nghịch đảo mở
= (x3 + x + 1).
rộng là
g � = g + e0n . D. Khả nghịch và khả nghịch mở rộng trên vành đa thức
hữu hạn có hai lớp kề cyclic
Chứng minh: Ta có
Định nghĩa 15. Tập của các số nguyên n thỏa mãn
n−1
f � ∗ g � = (f + e0n ) ∗ (g + e0n ) xn + 1 = (x + 1) ∗ T với T = i=0 xi là một đa thức
bất khả quy trong GF (2) được ký hiệu là N2C . Trong
= (f ∗ g + e20n + (f + g) ∗ e0n )
trường hợp này, Rn được gọi là vành đa thức bậc hữu
= (1 + e0n + (f + g) ∗ e0n ) hạn hệ số nhị phân có hai lớp kề cyclic.
Vì cả w(f ) và w(g) đều lẻ, nên w(f + g) luôn chẵn. Theo thuật toán trong [4], ta có thể tính được N2C .
Do đó, theo bổ đề 5, (f + g) ∗ e0n = 0. Hệ quả là, Một vài giá trị ví dụ của n ∈ N2C là
f � ∗ g � = e0n + 1 {3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, . . .
1019, 1061, 1091, 1109, 1117, 1123, 1171, 1187, . . .
Vì w(f ) và w(e0n ) luôn lẻ khi n lẻ nên w(f � ) = 2053, 2069, 2083, 2099, 2131, 2141, 2213, 2221, . . .
w(f + e0n ) luôn chẵn. Do đó, có thể thấy rằng trọng 4091, 4093, 4099, 4133, 4139, 4157, 4219, 4229, . . .}
số Hamming của một đa thức khả nghịch mở rộng luôn
[4] cũng chỉ ra rằng tất cả n ∈ N2C đều là nguyên tố
chẵn.
lẻ.
Ví dụ, trong R5 , f = x4 + x3 + 1 khả nghịch với
nghịch đảo làg = x4 + x3 + x. Đa thức f � = f + e05 = Định lý 1. Trong Rn |n ∈ N2C , tất cả các đa thức trong
x2 + x là khả nghịch mở rộng với nghịch đảo mở rộng In \T là khả nghịch. Do đó số phần tử khả nghịch trong
là g � = g + e05 = x2 + 1. những vành đa thức đó là 2n−1 − 1.
243
- Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
Bảng I
Chứng minh: Theo [4], nếu Rn |n ∈ N2C thì n lẻ, CẤU TRÚC ĐẠI SỐ NỀN TẢNG CỦA E-RISKE
do đó w(T ) cũng lẻ. Vì deg T = n−1 có giá trị lớn nhất
là max deg f |f ∈ Rn và T là bất khả quy trên GF (2) Tham số Giá trị
nên theo định nghĩa ??, gcd(f, T ) = 1 ∀f ∈ In \ T . Vành đa thức RL = Z2 [x]/(xL + 1)|L ∈ R2C
Hơn nữa, nếu f ∈ I2C [x] \ T thì gcd(f, xn + 1) =
Không gian bản
gcd(f, (x+1)∗T ) = 1. Theo định lý Euclid, luôn tồn tại rõ
P = {m ∈ RL , deg(m) < L − 1}
hai đa thức u, v ∈ Rn thỏa mãn u ∗ f + v ∗ (xn + 1) = 1
Không gian bản
hay u ∗ f = 1. Điều này chứng tỏ f là khả nghịch với mã
C = RL
phần tử nghịch đảo u nào đó. Chiều dài bản rõ,
Theo [5], m = 2n−1 − 1 là cấp lớn nhất của các đa L − 1, L
bản mã
thức trong In \T tức là, f m = 1 và u = f m−1 là nghịch Kích thước khóa N 0 để đảm bảo rằng ta không sử dụng và sau đó khôi phục (L − 1) bit bản rõ
hai đa thức tầm thường k = 0 và k = 1 làm khóa bí
mật trong E-RISKE, Do đó, m = ML−1 .xL−1 + M (7)
|K1 | = |K2 | = 2N −1 − 1 (1) Ở đây ML−1 là hệ số của đơn thức xL−1 trong biểu
diễn đa thức của M . Chú ý rằng k −1 là nghịch đảo của
và k khi k ∈ K1 và ke−1 là nghịch đảo mở rộng của k khi
|K| = |K1 | + |K2 | = 2N − 2 (2) k ∈ K2 .
244
- Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
D. Một ví dụ nhỏ với c−1 và c−1
e là lần lượt là nghịch đảo và nghịch đảo
Trong ví dụ này, ta chọn L = 5, N = 3 và sử dụng R5 mở rộng của c trong RL . Lưu ý rằng, trong RL , c luôn
để xây dựng E-RISKE. Giả sử rằng bên gửi muốn gửi là khả nghịch hoặc khả nghịch mở rộng.
4 bit bản tin 0011 tương đương với đa thức m = x + 1 Vì k được lựa chọn ngẫu nhiên phân bố đều trong K1
tới bên nhận. hoặc K2 trong khi M và c là cho trước. Như một hệ
1) Khi k ∈ K1 : Giả sử rằng bên gửi và bên nhận đều quả,
dùng khóa bí mật chung là k = x2 +x+1 với nghịch đảo 1
là k −1 = x4 + x2 + x. Để mã hóa m, đầu tiên bên gửi Pr[k −1 = M ∗ c−1 ] =
|K1 |
tính M = x4 +x+1 sau đó tính c = M ∗k = x4 +x3 +x
và gửi c tới bên nhận. và
Khi nhận được c, bên nhận đầu tiên sử dụng k −1 để
1
tính M = c ∗ k −1 = x4 + x + 1 sau đó khôi phục Pr[k −1 = e0L + (M + e0L ) ∗ c−1
e ]=
m = x4 + (x4 + x + 1) = x + 1. |K2 |
2) Khi k ∈ K2 : Giả sử rằng bên gửi và bên nhận đều
dùng khóa bí mật chung là một đa thức khả nghịch mở Cuối cùng, ta có
rộng
|K1 | 1 |K2 | 1 2
k = e05 + (x2 + x + 1) = x4 + x3 Pr[M � = M ] = . + . = .
|K| |K1 | |K| |K2 | |K|
với nghịch đảo mở rộng
ke−1 = e05 + (x4 + x2 + x) = x3 + 1. Trong tấn công IND-EAV-ATK, kẻ tấn công A có
thể đạt được b� = b bằng cách đoán đơn giản với xác
Để mã hoá m, đầu tiên bên gửi tính M = x4 + x + 1 suất đúng là 1/2 hoặc thử tất cả các khoá k ∈ K1 hoặc
sau đó tính k ∈ K2 và tính M � bằng thủ tục giải mã cho đến khi
c = e05 + M ∗ k = x2 + 1 M � = Mb . Giả sử A mất p(N ) lần thử k để thu được
M � = Mb , với p(N ) là một đa thức của N , ta có
và gửi c tới bên nhận.
Khi nhận được c, đầu tiên bên nhận sử dụng ke−1 để 1
Pr[SecKeav
A,Π = 1] = + p(N ). Pr[M � = Mb ]
tính 2
1
M = e05 + c ∗ ke−1 = + p(N ).(Pr[M � = M0 ]. Pr[b = 0]
2
= e05 + (x2 + 1) ∗ (x3 + 1) = x4 + x + 1 + Pr[M � = M1 ]. Pr[b = 1])
sau đó khôi phục m = x4 + (x4 + x + 1) = x + 1. 1 1 2 1 2
= + p(N ).( . + . )
2 2 |K| 2 |K|
E. Phân tích độ an toàn trên lý thuyết của E-RISKE
1 2 1 p(N )
1) Khả năng chống tấn công IND-EAV-ATK: = + p(N ). = + N −1
2 |K| 2 2 −1
Định lý 2. E-RISKE an toàn với tấn công IND-EAV-
ATK. Vì p(N ) là một đa thức (để đảm bảo tấn công là khả
thi trong thời gian đa thức), theo định lý 2,
Chứng minh: Nhớ lại rằng, với bản mã c bên nhận
có thể tìm được bản rõ M bằng công thức (5) hoặc (6) p(N )
nếu biết k. Mặc dù không có khoá, kẻ nghe lén có thể 2N −1 − 1
thử lần lượt các khoá k trong không gian khoá và giải
mã ra được một bản rõ M � ∈ P. Xác suất để kẻ nghe là một hàm không đáng kể của N . Kết quả là, theo định
lén giải mã thành công sẽ là nghĩa 5, E-RISKE được coi là an toàn với tấn công IND-
Pr[M � = M ] = Pr[k −1 ∗ c = M ]. Pr[k ∈ K1 ] EAV-ATK.
2) Khả năng chống tấn công IND-CPA-ATK:
+ Pr[e0L + ke−1 ∗ c = M ]. Pr[k ∈ K2 ]
|K1 | Định lý 3. E-RISKE an toàn với tấn công IND-CPA-
= Pr[k −1 = M ∗ c−1 ]. . ATK.
|K|
|K2 | Chứng minh: Với một bản rõ M và bản mã tương
+ Pr[ke−1 = e0L + (M + e0L ) ∗ c−1
e ].
|K| ứng c cho trước và nếu ta có c� là bản mã của M với
245
- Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
một khóa k nào đó thì F. Phân tích hiệu năng trên lý thuyết
�
Pr[c = c] = Pr[k −1
∗ M = c]. Pr[k ∈ K1 ] Lợi thế quan trọng nhất của E-RISKE là tốc độ tính
+ Pr[e0L + ke−1
∗ M = c]. Pr[k ∈ K2 ] toán, thuật toán mã hóa và giải mã của E-RISKE chỉ là
một phép cộng và một phép nhân đa thức trong RL và
|K1 |
= Pr[k −1 = M −1 ∗ c]. mất O(L2 ) phép tính bit. Dễ thấy L càng lớn so với N
|K| thì E-RISKE có hiệu quả mã hoá càng cao.
|K2 | Nhược điểm của E-RISKE là ta phải chọn k ∈ K
+ Pr[ke−1 = e0L + M −1 ∗ (c + e0L )].
|K| ngẫu nhiên và thống nhất giữa hai phía, mỗi phiên làm
với M −1 là nghịch đảo của M trong RL . Nhắc lại việc cần một khóa bí mật ngẫu nhiên mới được chia
rằng, theo công thức (3), w(M ) luôn lẻ nên M luôn sẻ giữa bên gửi và bên nhận. Vì lý do này, E-RISKE
khả nghịch trong RL . Vì k được lựa chọn ngẫu nhiên cần được sử dụng kết hợp với một hệ mật khóa công
phân bố đều trong K trong khi M và c cố định nên ta khai nào đó để xây dựng một hệ mật lai ghép theo mô
có hình KEM (Key Encapsulation Mechanism) với bản rõ
1 có kích thước lớn được mã hóa bởi E-RISKE còn khóa
Pr[k −1 = M −1 ∗ c] =
|K1 | bí mật ngẫu nhiên k trong mỗi một phiên của E-RISKE
và được mã hóa bởi hệ mật khóa công khai đó. Nếu chọn
1 được hệ mật khoá công khai có đặc tính IND-CPA thì,
Pr[ke−1 = e0L + M −1 ∗ (c + e0L )] = . theo [1], sơ đồ lai ghép được cấu thành vẫn kế thừa được
|K2 |
Hệ quả là, đặc tính IND-CPA của E-RISKE. Không những thế, do
hiệu quả mã hoá cao, nếu sử dụng sơ đồ lai ghép ta
1 |K1 | 1 |K2 | 2
Pr[c� = c] = . + . = . có E-RISKE để cải thiện hiệu quả của các hệ mật khoá
|K1 | |K| |K2 | |K| |K| công khai có hệ số mở rộng bản tin lớn như NTRU và
Trong tấn công IND-CPA-ATK, kẻ tấn công A có thể pNE (khoảng hơn 4 lần).
đạt được b� = b bằng một trong hai cách sau:
1) Sử dụng thuật toán để tìm b như trong tấn công G. Lựa chọn tham số
IND-EAV-ATK; Mặc dù xác suất để kẻ tấn công có thể phá được
2) Với c là bản mã của một trong hai bản rõ m0 , m1 E-RIKSE về lý thuyết là vô cùng nhỏ nhưng thực tế
nhận được từ bộ mã hoá. Kẻ tấn công lựa chọn để đảm bảo khả năng chống các tấn công vét cạn thì
ngẫu nhiên b ∈ {0, 1} và truy vấn bộ mã hóa q(N ) giá trị của N phải đủ lớn. Đối với ứng dụng thực tế,
lần với đầu vào mb cho đến khi có được bản rõ nhóm nghiên cứu đề xuất L ≥ N ≥ 1024. Trong trường
đầu ra c� = c. Lưu ý rằng q(N ) là một đa thức hợp đó, độ mật khoá (key-security) và độ mật bản tin
của N , ràng buộc này đảm bảo tấn công có thể (message-security) của E-RISKE là 2N − 2 = 21024 − 2.
được thực hiện trong thời gian đa thức. Đối với các ứng dụng yêu cầu độ mật cao hơn, chúng
Khi đó ta có tôi khuyến nghị L ≥ N ≥ 4096.
Pr[SecKcpa
A,Π = 1] V. KẾT LUẬN
= Pr[SecKeav
A,Π
�
= 1] + q(N ). Pr[c = c] Như đã đề cập, mặc dù E-RISKE có hiệu quả tính
2 toán cao tuy nhiên do phải sử dụng khoá phiên, việc
= Pr[SecKeav
A,Π = 1] + q(N ).
|K| lựa chọn một hệ mật khoá công khai phù hợp để mã
1 2 hoá và chia sẻ khoá bí mật ngẫu nhiên của E-RISKE
= + (p(N ) + q(N )). theo mô hình KEM như nêu trên là một vấn đề mở thú
2 |K|
1 p(N ) + q(N ) vị. Ngoài ra, do E-RISKE hoạt động dựa trên các phần
= + tử khả nghịch và khả nghịch mở rộng, tìm kiếm các lớp
2 2N −1 − 1
vành Rn có hệ số Kn lớn (tối đa hoặc gần tối đa) là
Vì g(N ) = p(N ) + q(N ) cũng là một đa thức, theo
một vấn đề mở khác cho các nghiên cứu trong tương lai
định đề 2,
g(N ) của chúng tôi.
2N −1 − 1 TÀI LIỆU THAM KHẢO
là hàm không đáng kể của N . Kết quả là, theo định
[1] Jonathan Katz, Yehuda Lindell (2007), Introduction to Modern
nghĩa 5, E-RISKE là IND-CPA. Cryptography: Principles and Protocols, Chapman Hall/CRC
Cryptography and Network Security Series.
246
- Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
[2] Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. NTRU: Alice rings, VICA-5, Hanoi, Vietnam.
ring-based public key cryptosystem. Lecture Notes in Computer [6] Stehle,D., Steinfeld,R.:Making NTRU as secure as worst-case
Science Volume 1423, pp 267-288, Springer Verlag 1998. problems over ideal lattices. In:Paterson,K.G.(ed.) EUROCRYPT
[3] Gaborit, P., Ohler, J., Sole, P.: CTRU, a Polynomial Analogue of 2011. LNCS, vol. 6632, pp. 27–47. Springer, Heidelberg (2011).
NTRU, INRIA. Rapport de recherche, N.4621 (November 2002), [7] Nguyen Binh. Crypto-system based on cyclic geometric progres-
(ISSN 0249-6399). sions over polynomial ring (Part I). REV’02.2002.
[4] Dang Hoai Bac, Nguyen Binh, Nguyen Xuan Quynh , Young [8] Ho Quang Buu, Ngo Duc Thien, Tran Duc Su. Constructing
Hoon Kim (2007). Polynomial rings with two cyclotomic cosets secret-cryptosystem based on cyclic multiplicative progress over
and their applications in Communication, MMU International polynomial rings, Journal of Science and Technology, Posts and
Symposium on Information and Communications Technologies Telecommunication Institute of Technology, 50 (2A), 2012, pp
2007, Malaysia, ISBN: 983-43160-0-3. 109-119. In Vietnamese.
[5] Nguyen Binh, Le Dinh Thich (2002), The order of polynomials [9] Menezes A. J, Van Oorchot P. C. (1998), Handbook of Applied
and algorithms for defining Oder of Polynomial over polynomial Cryptography, CRC Press.
247
nguon tai.lieu . vn
