Link tải luận văn miễn phí cho ae Kết nối
TÓM TẮT NỘI DUNG
Hệ mật RSA được phát minh bởi Ron Rivest, Adi Shamir, và Len Adleman,
công bố lần đầu vào tháng 8 năm 1977. Hệ mật sử dụng trong lĩnh vực đảm bảo tính
riêng tư và cung cấp cơ chế xác thực của dữ liệu số. Ngày nay, RSA đã được phát
triển ứng dụng rộng rãi trong thương mại điện tử và đặc biệt nó là hạt nhân của hệ
thống thanh toán điện tử.
Ngay từ khi được công bố lần đầu, hệ RSA đã được phân tích hệ số an toàn bởi
nhiều nhà nghiên cứu. Mặc dù đã trải qua nhiều năm nghiên cứu và đã có một số cuộc
tấn công ấn tượng nhưng không mang lại kết quả là phá huỷ. Đa phần họ mới chỉ ra
được những mối nguy hiểm tiềm ẩn của RSA mà khi sử dụng RSA người dùng cần cải
thiện.
Thực tế vấn đề thám mã đối với hệ mật RSA hiện tại đang được các nhà nghiên
cứu tập trung khai thác các sơ hở của RSA như: tấn công vào số mũ công khai hay số
mũ bí mật thấp, tấn công vào các tham số nguyên tố p, q bé hay cách xa nhau lớn,
hay tập trung vào việc phân tích nhân tử số n(modul của RSA).
Luận văn của em sẽ trình bày các phương pháp tấn công RSA trong vòng 20
năm trở lại đây và lựa chọn môt phương pháp tấn công phổ biến để demo.
MỞ ĐẦU
Hệ mật mã khoá công khai RSA được sử dụng phổ biến trong lĩnh vực đảm bảo
tính riêng tư và cung cấp cơ chế xác thực của dữ liệu số. Ngày nay RSA được phát triển
và ứng dụng rộng rãi trong thương mại điện tử, được sử dụng trong việc tạo khoá và xác
thực của mail, trong truy cập từ xa, và đặc biệt nó là hạt nhân của hệ thống thanh toán
điện tử. RSA được ứng dụng rộng rãi trong các lĩnh vực nơi mà an ninh an toàn thông tin
được đòi hỏi.
Chính vì lý do được sử dụng rộng rãi trong thương mại điện tử cũng như có độ an
toàn cao mà đã có rất nhiều sự nhòm ngó cũng như các cuộc tấn công nhằm phá vỡ sự an
toàn của hệ mật RSA. Ngay từ khi được công bố lần đầu, hệ RSA đã được phân tích hệ
số an toàn bởi nhiều nhà nghiên cứu. Mặc dù trải qua nhiều năm nghiên cứu và đã có một
số cuộc tấn công ấn tượng nhưng không mang lại kết quả là phá huỷ. Đa phần họ mới chỉ
ra được những mối nguy hiểm tiềm ẩn của RSA.
Để phục vụ cho việc phân tích các tính chật của hệ mật RSA, em đã trình bày các khái
niệm cơ bản liên quan đến toán học, mật mã và thám mã , trình bày tổng quan về hệ mã
hoá khoá công khai, các bài toán liên quan đến hệ mã hoá khoá công khai
Trên cơ sở hiểu các khái niệm cơ bản, các cơ sở toán học, để có cái nhìn tổng quan
về vấn đề thám mã đối với hệ mật RSA trong những năm qua, em đã tổng kết lại các
phương pháp tấn công vào hệ mật RSA và kết quả thu được trong những năm qua. Trong
chương này em đã trình bày chi tiết các thuật toán tấn công vào hệ mật RSA như: các tấn
công cơ bản - modul chung, mù, tấn công vào số mũ công khai hay số mũ bí mật thấp,
tấn công dựa trên thời gian hay dựa vào các lỗi ngẫu nhiên. Ngoài ra, em cũng trình bày
các thuật toán tấn công RSA bằng nhân tử hoá số N với số N lớn như thuật toán Pollard,
tuy nhiên các thuật toán được giới thiệu ở đây mới chỉ giải quyết cho modul N của RSA
có độ dài hạn chế, còn mudul N có độ dài lớn thì cho đến nay chưa có phương pháp khả
thi nào được công bố.
Chương 1 - CÁC KHÁI NIỆM CƠ BẢN
1.1 Một số khái niệm toán học
1.1.1 Số nguyên tố và nguyên tố cùng nhau
Số nguyên tố là số nguyên dương chỉ chia hết cho 1 và chính nó.
Ví dụ: 2, 3, 5, 7, 11, 17, …
Hệ mật mã thường sử dụng các số nguyên tố ít nhất là lớn hơn 10150.
Hai số m và n được gọi là nguyên tố cùng nhau, nếu ước số chung lớn nhất của chúng
bằng Ký hiệu: gcd (m, n) = 1.
Ví dụ: 9 và 14 là hai số nguyên tố cùng nhau.
1.1.2 Đồng dư thức
Cho a và b là các số nguyên n là số nguyên dương. Khi đó a được gọi là đồng dư với b
theo modulo n, ký hiệu là a ≡ b (mod n), nếu a, b chia cho n có cùng số dư. n được gọi là
modulo của đồng dư.
Kí hiệu: a ≡ b (mod n)
Ví dụ: 5 ≡ 7 mod 2 vì: 5 mod 2 = 1 và 7 mod 2 = 1
Tính chất của đồng dư:
Cho a, a1, b, b1, c ∈ Z. Ta có các tính chất sau:
- a ≡ b mod n nếu và chỉ nếu a và b có cùng số dư khi chia cho n
- Tính phản xạ: a ≡ a mod n
- Tính đối xứng: Nếu a ≡ b mod n thì b ≡ a mod n
- Tính giao hoán: Nếu a ≡ b mod n và b ≡ c mod n thì a ≡ c mod n
- Nếu a ≡ a1 mod n, b ≡ b1 mod n
thì a + b ≡ (a1+b1) mod n và ab ≡ a1 b1 mod n
Lớp tương đương:
Lớp tương đương của số nguyên a là tập hợp các số nguyên đồng dư với a theo modulo n.
Cho n cố định đồng dư với n trong không gian Z vào các lớp tương đương. Nếu a = qn +
r, trong đó 0 ≤ r ≤ n thì a ≡ r mod n. Vì vậy mỗi số nguyên a là đồng dư theo modulo
n với duy nhất một số nguyên trong khoảng từ 0 đến n-1 và được gọi là thặng dư nhỏ
nhất của a theo modulo n. Cũng vì vậy, a và r cùng thuộc một lớp tương đương. Do
đó r có thể đơn giản được sử dụng để thể hiện lớp tương đương.
1.1.3 Không gian Zn và Zn*
Không gian Zn (các số nguyên theo modulo n)
Không gian các số nguyên theo modulo n: Zn là tập hợp các số nguyên không âm nhỏ hơn
n. Tức là: Z
n = {0, 1, 2, … n-1}.
Tất cả các phép toán trong Zn đều được thực hiện theo modulo n.
Ví dụ: Z11 = {0, 1, 2, 3, …, 10}
Trong Z11: 6 + 7 = 2, bởi vì 6 + 7 = 13 ≡ 2 (mod 11).
Không gian Zn*
Là tập hợp các số nguyên p ∈ Zn, nguyên tố cùng n.
Tức là: Z
n
*
= { p ∈ Zn | gcd (n, p) = 1}, Ф(n) là số phần tử của Zn*
Nếu n là một số nguyên tố thì: Zn* = { p ∈ Zn | 1 ≤ p ≤ n – 1}
Ví dụ: Z2 = {0, 1} thì Z2* = {1} vì gcd (1, 2) = 1.
1.1.4 Phần tử nghịch đảo
Định nghĩa:
Cho a ∈ Z
n. Nghịch đảo của a theo modulo n là số nguyên x ∈ Zn sao cho ax ≡ 1(mod
n). Nếu x tồn tại thì đó là giá trị duy nhất, và a được gọi là khả nghịch.
Nghịch đảo của a ký hiệu là a-1.
Tính chất:
• Cho a, b ∈ Zn. Phép chia a cho b theo modulo n là tích của a và b theo modulo
n, và chỉ được xác định khi b có nghịch đảo theo modulo n.
• Cho a ∈ Z
n, a là khả nghịch khi và chỉ khi gcd (a, n) = 1.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
TÓM TẮT NỘI DUNG
Hệ mật RSA được phát minh bởi Ron Rivest, Adi Shamir, và Len Adleman,
công bố lần đầu vào tháng 8 năm 1977. Hệ mật sử dụng trong lĩnh vực đảm bảo tính
riêng tư và cung cấp cơ chế xác thực của dữ liệu số. Ngày nay, RSA đã được phát
triển ứng dụng rộng rãi trong thương mại điện tử và đặc biệt nó là hạt nhân của hệ
thống thanh toán điện tử.
Ngay từ khi được công bố lần đầu, hệ RSA đã được phân tích hệ số an toàn bởi
nhiều nhà nghiên cứu. Mặc dù đã trải qua nhiều năm nghiên cứu và đã có một số cuộc
tấn công ấn tượng nhưng không mang lại kết quả là phá huỷ. Đa phần họ mới chỉ ra
được những mối nguy hiểm tiềm ẩn của RSA mà khi sử dụng RSA người dùng cần cải
thiện.
Thực tế vấn đề thám mã đối với hệ mật RSA hiện tại đang được các nhà nghiên
cứu tập trung khai thác các sơ hở của RSA như: tấn công vào số mũ công khai hay số
mũ bí mật thấp, tấn công vào các tham số nguyên tố p, q bé hay cách xa nhau lớn,
hay tập trung vào việc phân tích nhân tử số n(modul của RSA).
Luận văn của em sẽ trình bày các phương pháp tấn công RSA trong vòng 20
năm trở lại đây và lựa chọn môt phương pháp tấn công phổ biến để demo.
MỞ ĐẦU
Hệ mật mã khoá công khai RSA được sử dụng phổ biến trong lĩnh vực đảm bảo
tính riêng tư và cung cấp cơ chế xác thực của dữ liệu số. Ngày nay RSA được phát triển
và ứng dụng rộng rãi trong thương mại điện tử, được sử dụng trong việc tạo khoá và xác
thực của mail, trong truy cập từ xa, và đặc biệt nó là hạt nhân của hệ thống thanh toán
điện tử. RSA được ứng dụng rộng rãi trong các lĩnh vực nơi mà an ninh an toàn thông tin
được đòi hỏi.
Chính vì lý do được sử dụng rộng rãi trong thương mại điện tử cũng như có độ an
toàn cao mà đã có rất nhiều sự nhòm ngó cũng như các cuộc tấn công nhằm phá vỡ sự an
toàn của hệ mật RSA. Ngay từ khi được công bố lần đầu, hệ RSA đã được phân tích hệ
số an toàn bởi nhiều nhà nghiên cứu. Mặc dù trải qua nhiều năm nghiên cứu và đã có một
số cuộc tấn công ấn tượng nhưng không mang lại kết quả là phá huỷ. Đa phần họ mới chỉ
ra được những mối nguy hiểm tiềm ẩn của RSA.
Để phục vụ cho việc phân tích các tính chật của hệ mật RSA, em đã trình bày các khái
niệm cơ bản liên quan đến toán học, mật mã và thám mã , trình bày tổng quan về hệ mã
hoá khoá công khai, các bài toán liên quan đến hệ mã hoá khoá công khai
Trên cơ sở hiểu các khái niệm cơ bản, các cơ sở toán học, để có cái nhìn tổng quan
về vấn đề thám mã đối với hệ mật RSA trong những năm qua, em đã tổng kết lại các
phương pháp tấn công vào hệ mật RSA và kết quả thu được trong những năm qua. Trong
chương này em đã trình bày chi tiết các thuật toán tấn công vào hệ mật RSA như: các tấn
công cơ bản - modul chung, mù, tấn công vào số mũ công khai hay số mũ bí mật thấp,
tấn công dựa trên thời gian hay dựa vào các lỗi ngẫu nhiên. Ngoài ra, em cũng trình bày
các thuật toán tấn công RSA bằng nhân tử hoá số N với số N lớn như thuật toán Pollard,
tuy nhiên các thuật toán được giới thiệu ở đây mới chỉ giải quyết cho modul N của RSA
có độ dài hạn chế, còn mudul N có độ dài lớn thì cho đến nay chưa có phương pháp khả
thi nào được công bố.
Chương 1 - CÁC KHÁI NIỆM CƠ BẢN
1.1 Một số khái niệm toán học
1.1.1 Số nguyên tố và nguyên tố cùng nhau
Số nguyên tố là số nguyên dương chỉ chia hết cho 1 và chính nó.
Ví dụ: 2, 3, 5, 7, 11, 17, …
Hệ mật mã thường sử dụng các số nguyên tố ít nhất là lớn hơn 10150.
Hai số m và n được gọi là nguyên tố cùng nhau, nếu ước số chung lớn nhất của chúng
bằng Ký hiệu: gcd (m, n) = 1.
Ví dụ: 9 và 14 là hai số nguyên tố cùng nhau.
1.1.2 Đồng dư thức
Cho a và b là các số nguyên n là số nguyên dương. Khi đó a được gọi là đồng dư với b
theo modulo n, ký hiệu là a ≡ b (mod n), nếu a, b chia cho n có cùng số dư. n được gọi là
modulo của đồng dư.
Kí hiệu: a ≡ b (mod n)
Ví dụ: 5 ≡ 7 mod 2 vì: 5 mod 2 = 1 và 7 mod 2 = 1
Tính chất của đồng dư:
Cho a, a1, b, b1, c ∈ Z. Ta có các tính chất sau:
- a ≡ b mod n nếu và chỉ nếu a và b có cùng số dư khi chia cho n
- Tính phản xạ: a ≡ a mod n
- Tính đối xứng: Nếu a ≡ b mod n thì b ≡ a mod n
- Tính giao hoán: Nếu a ≡ b mod n và b ≡ c mod n thì a ≡ c mod n
- Nếu a ≡ a1 mod n, b ≡ b1 mod n
thì a + b ≡ (a1+b1) mod n và ab ≡ a1 b1 mod n
Lớp tương đương:
Lớp tương đương của số nguyên a là tập hợp các số nguyên đồng dư với a theo modulo n.
Cho n cố định đồng dư với n trong không gian Z vào các lớp tương đương. Nếu a = qn +
r, trong đó 0 ≤ r ≤ n thì a ≡ r mod n. Vì vậy mỗi số nguyên a là đồng dư theo modulo
n với duy nhất một số nguyên trong khoảng từ 0 đến n-1 và được gọi là thặng dư nhỏ
nhất của a theo modulo n. Cũng vì vậy, a và r cùng thuộc một lớp tương đương. Do
đó r có thể đơn giản được sử dụng để thể hiện lớp tương đương.
1.1.3 Không gian Zn và Zn*
Không gian Zn (các số nguyên theo modulo n)
Không gian các số nguyên theo modulo n: Zn là tập hợp các số nguyên không âm nhỏ hơn
n. Tức là: Z
n = {0, 1, 2, … n-1}.
Tất cả các phép toán trong Zn đều được thực hiện theo modulo n.
Ví dụ: Z11 = {0, 1, 2, 3, …, 10}
Trong Z11: 6 + 7 = 2, bởi vì 6 + 7 = 13 ≡ 2 (mod 11).
Không gian Zn*
Là tập hợp các số nguyên p ∈ Zn, nguyên tố cùng n.
Tức là: Z
n
*
= { p ∈ Zn | gcd (n, p) = 1}, Ф(n) là số phần tử của Zn*
Nếu n là một số nguyên tố thì: Zn* = { p ∈ Zn | 1 ≤ p ≤ n – 1}
Ví dụ: Z2 = {0, 1} thì Z2* = {1} vì gcd (1, 2) = 1.
1.1.4 Phần tử nghịch đảo
Định nghĩa:
Cho a ∈ Z
n. Nghịch đảo của a theo modulo n là số nguyên x ∈ Zn sao cho ax ≡ 1(mod
n). Nếu x tồn tại thì đó là giá trị duy nhất, và a được gọi là khả nghịch.
Nghịch đảo của a ký hiệu là a-1.
Tính chất:
• Cho a, b ∈ Zn. Phép chia a cho b theo modulo n là tích của a và b theo modulo
n, và chỉ được xác định khi b có nghịch đảo theo modulo n.
• Cho a ∈ Z
n, a là khả nghịch khi và chỉ khi gcd (a, n) = 1.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links