hana_tieuconuongq6
New Member
Download miễn phí Đề tài Sinh tham số an toàn cho hệ mật Elgamal
Mục lục
chương iư vai trò của số nguyên tố dạng p=2q+1 TRONG MậT Mã
mở đầu
1.1 BàI TOáN logarit rời rạc và các ứng dụng trong
mật mã
1.1.1 Bài toán logarit rời rạc trên trường GF(p)
1.1.2 Hệ mật Elgamal
1.1.3 Chữ ký số Elgamal
1.1.4 Sơ đồ phân phối khoá DiffieưHellman
1.2 các thuật toán tìm logarit rời rạc
1.2.1 Thuật toán Shanks
1.2.2 Thuật toán Pohlig ư Hellman
1.2.3 Thuật toán sàng bậc q
1.2.4 Thuật toán sàng trường số
Tài liệu dẫn
chương iiưsinh số nguyên tố lớn bằng phương
pháp tăng dần độ dài
mở đầu
2.1 Một số kết quả trong lý thuyết số
2.2 Thuật toán Pocklington
2.2.1 Thuật toán kiểm tra tính nguyên tố Pocklington trên lớp LF
2.2.2 Đánh giá xác suất sai lầm của thuật toán PockưtestF
2.2.3 Thuật toán sinh số nguyên tố trên lớp LF
2.2.3.1 Mở đầu
2.2.3.2 Một số phân tích về khả năng tồn tại số nguyên tố độ dài n trong lớp sốLF
2.3 Thuật toán sinh các số nguyên tố =n bit từ
thuật toán sinh các số nguyên tố
2.3.2 Thuật toán
2.3.3 Phân tích khả năng sinh các số nguyên tố dộ dài n của thuật toán
2.3.4 Phân tích thời gian thực hiện việc sinh một số nguyên tố độ dài n
2.3.5 Sự tồn tại thuật toán nhanh sinh được toàn bộ các số nguyên tố
2.3.5.1 Thuật toán
2.3.5.2 Kết luận
Tài liệu dẫn
chương iiiưchương trình sinh số nguyên tố
mạnh cho hệ mật elgamal
mở đầu
3.1 lớp Lpvà số lượng số nguyên tố trong lớp lp
3.1.1 Lớp Lp(k)
3.1.2 Số các số nguyên tố độ dài n=?3klogp?bit có trong lớp Lp(k)
3.1.3 Thuật toán sinh số nguyên tố n bit trên các lớp Lp(k) với p nhỏ
3.1.4 Trường hợp p=2
3.2 Việc sinh các số nguyên tố mạnh và gần mạnh
3.2.1 Khái niệm số nguyên tố mạnh và gần mạnh
3.2.2 Số nguyên tố Sophie
3.2.3 Thuật toán sinh số nguyên tố gần mạnh
3.2.3.1 Thuật toán
3.2.4 Thuật toán sinh nhanh các nhân nguyên tố lớn được gài đặt
3.2.4.1 Phương pháp sinh nhanh từ số nguyên tố nhỏ
3.2.4.2 Phương pháp gấp đôi độ dài từ số nguyên tố lớn
3.3 tính toán trên các số lớn
3.3.1 Phép nhân số lớn
3.3.2 Phép chia hai số lớn
3.3.3 Phép luỹ thừa modulo các số lớn
3.3.3.1 Công thức luỹ thừa theo khai triển nhị phân của số mũ
3.3.3.2 Công thức luỹ thừa theo khai triển a phân của số mũ
3.3.3.3 Phương pháp khai triển số mũ theo cơ số thay đổi (cơ số động)
tài liệu dẫn
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
t(n)≤Cαn4lnn. (2-8)2.2.3 Thuật toán sinh số nguyên tố trên lớp LF
2.2.3.1 Mở đầu
Nh− phần tr−ớc chúng ta đã xây dựng đ−ợc một thuật toán kiểm tra
nhanh tính nguyên tố của các số trên lớp LF, đó là thuật toán Pock-testF. Tại
phần này chúng ta tiến hành việc sinh các số nguyên tố trong lớp LF dựa vào
thuật toán kiểm tra pocklington đã nêu. Từ đặc thù của lớp LF là ch−a chắc
với mọi n là độ dài của các số thuộc lớp này đã tồn tại số nguyên tố có độ dài
t−ơng ứng trong lớp đó do vậy việc sinh các số nguyên tố có độ dài cho tr−ớc
là không luôn luôn đ−ợc do vậy thuật toán sinh của chúng ta xây dựng ở đây
chỉ cần đạt đ−ợc chỉ tiêu sau:
Nếu đầu vào là độ dài số nguyên tố cần sinh n thì đầu ra phải là một
số nguyên tố có độ dài không nhỏ hơn n.
Thuật toán sinh số nguyên tố trên LF ký hiệu là POCK-GENF đ−ợc
thực hiện nh− sau.
Thuật toán 2.5
Đầu vào n (length(F)
B−ớc 1. Xác định R0n là số nhỏ nhất và R1n là số lớn nhất để RF+1 có độ dài n
B−ớc 2. Lấy ngẫu nhiên số y=random[R0n;R1n];tính x=yF+1.
B−ớc 3. Xét Pock-testF(x)=1.
Nếu đúng. Đầu ra của thuật toán là x. Thuật toán dừng.
Ng−ợc lại. Chuyển sang 4.
B−ớc 4. y=y+1; x=yF+1; Chuyển về 3.
Khi này ta ký hiệu x=POCK-GENF(n).
đề tài: sinh 6ham số cho hệ mật elgamal. 24
ch−ơng ii. sinh số nguyên tố.bằng ph−ơng pháp tăng dần độ dài
2.2.3.2 Một số phân tích về khả năng tồn tại số nguyên tố độ dài n trong
lớp số LF
Định lý 2.6. Ký hiệu m=lnF thì với m đủ lớn ta có với mọi y≥1 thì trong∆ số
nguyên liên tiếp của dãy aF+1 bắt đầu từ yF+1 luôn tồn tại ít nhất một số
nguyên tố. với ∆= m(lnm+6) (2-9)
Chứng minh.
Xét giá trị x=yF+1 và x'=(y+∆)F+1 với 1≤y
có dạng aF+1 nằm trong khoảng [x;x'] là
π =πF(x')-πF(x)
~
F
F
y
y F
yF
yFϕ ( ) ln(( ) ) ln( )
+
+ −
∆
∆
>
y
y F
yF
yF
+
+ −
∆
∆ln(( ) ) ln( )
=
∆ ∆
∆
ln( ) [ln(( ) ) ln( )]
ln( ) ln(( ) )
yF y y F yF
yF y F
− + −
+
=
∆ ∆
∆
ln( ) ln( )
ln( ) ln(( ) )
yF y
y
yF y F
− +
+
1
(2-11).
Nếu lấy y=y(m) và ∆=∆(m) sao cho ∆( )
( )
m
y m
là vô cùng bé khi m→∞ (2-12)
ta có ln t−ơng đ−ơng với ( )1+ ∆
y
∆
y
. Thay vào (2.11) ta đ−ợc
π t−ơng đ−ơng với
∆ ∆
∆
ln( )
ln( ) ln(( ) )
yF y
y
yF y F
−
+ =
∆
∆
(ln( ) )
ln( ) ln(( ) )
yF
yF y F
−
+
1
(2-13)
Từ điều kiện (2.10) là y+∆≤F2 nên ln((y+∆)F)≤3m (2-14)
thêm vào nữa ta có lim
ln( )
ln( )m
yF
yF→∞
−1
=1 (2-15).
đề tài: sinh 6ham số cho hệ mật elgamal. 25
ch−ơng ii. sinh số nguyên tố.bằng ph−ơng pháp tăng dần độ dài
Thay (2-14) và (2-15) vào vế phải của (2-13) thì từ (2-11) ta có π t−ơng
đ−ơng với một đại l−ợng > ∆
3m
. Bây giờ chỉ cần lấy ∆(m)=6m còn
y(m)≥mlnm, hiển nhiên điều kiện (2.12) đ−ợc thỏa mãn và do đó π t−ơng
đ−ơng với một đại l−ợng >2 khi m→∞.
Nh− vậy với m đủ lớn thì π>1, tức là trong khoảng [x;x'] nếu
y≥y0=mlnm luôn tồn tại số nguyên tố dạng aF+1, nếu y
cũng tồn tại số nguyên tố. Rõ ràng chúng ta đã chứng minh đ−ợc rằng với mọi
x=yF+1∈LF luôn tồn tại số nguyên tố dạng aF+1 với a-y≤m(lnm+6) và đây là
điều cần chứng minh.
Từ định lý trên chúng ta thu đ−ợc định lý quan trọng sau.
Định lý 2.7. Với m=lnF đủ lớn thì:
(1). Thuật toán sinh số nguyên tố POCK-GENF trên lớp L
F luôn sinh đ−ợc số
nguyên tố độ dài n bit trong thời gian ký hiệu là TPOCK-GEN(n)≤C0n6 (2-16).
(2). Thêm nữa, nếu đầu vào của thuật toán là n thì số nguyên tố sinh đ−ợc tại
đầu ra có độ dài là l không quá n+
m
3
(2-17).
Chứng minh.
Ta biết, theo công thức (2-8) (định lý 2.4) thì để kiểm tra tính nguyên
tố của số tự nhiên độ dài n bit bằng thuật toán Pock-test là TTest(n)≤Cαn4lnn.
Lại từ công thức (2-9) (định lý 2.6) thì số lần lấy và kiểm tra trong thuật toán
POCK-GEN là không quá ∆=m(lnm+6)≤n(lnn+6) nh− vậy ta có ngay thời
gian thực hiện thuật toán này là
TPOCK-GEN(n)≤ Cαn4lnn n(lnn+6) (2-18).
Do ln2n là vô cùng lớn bậc thấp hơn n nên với n đủ lớn, tồn tại hằng số
C0 sao cho Cαln2n≤C0n (2-19).
Thay (2-18) vào (2-19) ta có ngay TPOCK-GEN(n)≤C0n6 và công thức (2-
16) của định lý đã đ−ợc chứng minh.
đề tài: sinh 6ham số cho hệ mật elgamal. 26
ch−ơng ii. sinh số nguyên tố.bằng ph−ơng pháp tăng dần độ dài
Giả sử y là giá trị đầu tiên đ−ợc chọn trong thuật toán với đầu vào là n
thì rõ ràng độ dài của y là k≈n-m (do số đ−ợc thử đầu tiên là x=yF+1 có độ
dài n) nh− vậy số nguyên tố tìm đ−ợc trong thuật toán giả sử là p=y'F+1 thì
theo công thức (2-9) (định lý 2.6) ta có y'≤y+∆=y+m(lnm+6). Rõ ràng
y
y
y m m
y
m m
' (ln )
(ln )≤ + + < +6 6 +1 nên độ dài của p là
l≤n+log(m(lnm+6)+1) (2-20).
Trong công thức (2-20), với m đủ lớn ta sẽ có log(m(lnm+6)+1)≤m
3
và công
thức (2-17) đã đ−ợc chứng minh.
2.3 Thuật toán sinh các số nguyên tố ≥n bit từ thuật
toán sinh các số nguyên tố
Trong mục này chúng tui giải quyết vấn đề sau:
Biết thuật toán sinh toàn bộ các số nguyên tố độ dài không đến n.
Hãy xây dựng thuật toán sinh các số nguyên tố độ dài không d−ới n sao
cho có thể sinh toàn bộ các số nguyên tố độ dài n.
ý t−ởng chủ đạo để giải quyết vấn đề trên của chúng tui là từ khả năng
có thể sinh đ−ợc toàn bộ các số nguyên tố độ dài không đến n của thuật toán
đã có chúng tui sinh ngẫu nhiên các số F thoả mãn hai điều kiện sau:
(F1). n>length(F)≥n
3
.
(F2). Biết đ−ợc phân tích của F ra thừa số nguyên tố.
Tiếp đến sử dụng thuật toán sinh Pocklington để sinh các số nguyên tố
độ dài không d−ới n trong lớp LF.
Việc giải quyết vấn đề đ−ợc thể hiện qua sơ đồ ở trang sau:
2.3.2 Thuật toán
Sơ đồ thuật toán 2.8.
đề tài: sinh 6ham số cho hệ mật elgamal. 27
ch−ơng ii. sinh số nguyên tố.bằng ph−ơng pháp tăng dần độ dài
F
T
F
T
length(p)≥n
output p
p=POCK-GENF(n)
F=F*ξ
nr=random[2;m)
length(F)
nr=random[2;n)
input n
đề tài: sinh 6ham số cho hệ mật elgamal. 28
ch−ơng ii. sinh số nguyên tố.bằng ph−ơng pháp tăng dần độ dài
2.3.3 Phân tích khả năng sinh các số nguyên tố dộ dài n của thuật toán
Chúng ta biết rằng nếu p là một số nguyên tố có độ dài n bit, không
giảm tổng quát ta giả sử n>2 do đó nó là số lẻ nên có dạng p=2x+1 trong đó x
là số có độ dài
toán và do đó p sẽ thuộc lớp LF hay p có thể đ−ợc sinh từ thuật toán. Tóm lại
chúng ta đã thu đ−ợc kết quả sau.
Định lý 2.9. Mọi số nguyên tố độ dài n bit đều có thể đ−ợc sinh từ thuật toán
ξn xây dựng ở trên.
Chú ý: Thuật toán ξn có một số đặc điểm sau.
Thứ nhất: Đầu ra của thuật toán chỉ là những số nguyê...