TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TPHCM
BÀI TIỂU LUẬN MÔN BẢO MẬT
TÊN ĐỀ TÀI : GIỚI THIỆU VỀ LÝ THUYẾT SỐ BẢO MẬT
MÁY TÍNH
GIẢNG VIÊN: TH.S TRƯƠNG VĂN THÔNG
SINH VIÊN THỰC HIỆN:
NGUYỄN TRẦN THÙY DƯƠNG - 09261221
1
MỤC LỤC
TÊN ĐỀ TÀI : GIỚI THIỆU VỀ LÝ THUYẾT SỐ BẢO MẬT MÁY TÍNH 1
GIỚI THIỆU VỀ LÝ THUYẾT SỐ BẢo mẬt Máy Tính 2
I.SỐ Nguyên TỐ (Prime Number) 5
II.ĐỊnh Lý Fermat và Euler: 6
III.KiỂm tra tính nguyên tỐ 8
IV.ĐỊnh Lý Chinese Remainder: 12
VI.SỐ BIỂU TƯỢNG 16
GIỚI THIỆU VỀ LÝ THUYẾT SỐ BẢO MẬT MÁY TÍNH
Một hệ thống được cho là có tính toán an toàn nếu các thuật toán tốt nhất yêu
cầu một bất hợp lý số lượng thời gian để phá vỡ hệ thống.
Tương tự như vậy, một vấn đề mà các giải pháp sử dụng các thuật toán tốt
nhất yêu cầu một số tiền không hợp lý thời gian được cho là có tính toán không
khả thi.
Hệ thống RSA thảo luận trong phần tiếp theo là một ví dụ về một hệ thống
mà bảo mật là dựa trên những khó khăn của bao thanh toán các sản phẩm của hai
nguyên tố số lượng lớn. Một ví dụ khác là Diffie-Hellman trao đổi chính thức có
bảo mật dựa trên những khó khăn trong việc tính toán logarit rời rạc trong các
nhóm nhất định.
Tuy nhiên thông báo rằng cho đến ngày hôm nay không có hệ mật thiết thực
được biết đến đó là có thể chứng minh computa-tionally an toàn. Bao thanh toán ví
dụ được coi là một khó khăn trong vấn đề tính toán một số trường hợp, nhưng
không ai có thể chứng minh rằng không có phương pháp hiệu quả để giải quyết

Cuối cùng, chúng ta cần nhớ lại các đường cong elliptic. Nếu p là số nguyên
tố, sau đó là tập các điểm (x, y) Zp × Zp đáp ứng được các y phương trình 2 ≡ x3
+ Ax + B (mod p) cùng với O, gọi là điểm ở vô cực, là được gọi là một
đường cong elliptic trên trường Zp , Nếu Δ biệt = -16 (4A327 B2) ≡ 0 (mod
p).Nếu P là một điểm trên đường cong elliptic E, sau đó thứ tự của P được định
nghĩa là nhỏ nhất tích cực số nguyên x sao cho xP = O, biểu hiện bằng ORDEP.
3
RSA
RSA là một hệ thống mật mã khóa công khai được phát triển bởi Rivest,
hamir và Adleman vào năm 1977. Nó cho phép Alice thông báo công khai hoặc
cung cấp một khóa mà Bob hay bất kỳ ai khác có thể sử dụng để gửi một bí mật
tin nhắn cho Alice. Không ai, nhưng Alice sẽ có thể giải mã thông điệp bí
mật.
2.1 hệ thống RSA
Định nghĩa 1. Hãy để một ba của số nguyên (e, d, n) được cho như vậy mà ed
≡ 1 (mod φ (n)). Chúng tôi sẽ gọi số (e, d, n) là một hệ thống RSA, các tuple (e, n)
sẽ được gọi là khóa công khai và (d, n) bí mật chính cho các hệ thống RSA. n cũng
sẽ được gọi là môđun RSA.
Ý tưởng đằng sau định nghĩa là các khoá công khai sẽ được công bố, trong
khi các khóa bí mật sẽ được giữ bí mật. Chúng ta sẽ thấy rằng việc biết khóa công
khai là đủ để mã hóa một tin nhắn, và mà giải mã các tin nhắn được mã hóa đòi
hỏi các kiến thức của khóa bí mật. Một tin nhắn ở đây có nghĩa là một số mZn.
Cho (e, d, n) là một hệ thống RSA. Chúng ta thấy cách sử dụng Định lý Euler
(phương trình (1) và (2)) mà cho m bất kỳ tin nhắn Zn(Me)d ≡ m (mod n).
Trong một thế giới m kịch bản thực Zn là một số được tạo ra ngẫu nhiên, ∈
mà phục vụ như là chìa khóa cho một hệ thống mã hóa đối xứng được sử dụng để
mã hóa một tài liệu. Điều này đang được thực hiện cho hiệu quả lý do.
4
I. SỐ NGUYÊN TỐ (PRIME NUMBER)
Định Nghĩa: Số Nguyên Tố là số lớn hơn 1, chỉ có 2 ước là ± 1 và ± chính

Nó sẽ được rõ ràng rằng đối với một số nguyên tố p thì  (p) = p 1
Bây giờ giả sử rằng có hai số nguyên tố p và q, với p ≠ q. Sau đó, chúng ta có
thể thấy rằng đối với n = pq thì  (n) =  (pq) =  (p) x  (q) = (p 1) x (q x 1)
Để thấy rằng  (n) =  (p) x  (q), cho rằng các tập các số nguyên dương
nhỏ n mà là tập hợp {1, , (pq1)}.
Các số nguyên trong bộ này mà không phải là tương đối chính để n là tập hợp
{p,2, , p (q 1) p} và thiết lập {q, quý 2, , (p 1) q}
Do đó,
 (n) = (pq 1) [(q 1) + (p 1)]
= pq (p + q) + 1
= (p 1) x (q 1)
=  (p) x  (q)
 (21) =  (3) x  (7) = (3 1) x (7 1) = 2 x 6 = 12
(12 số đó là {1,2,4,5,8,10,11,13,16,17,19,20})
c. Định Lý Euler
Với mỗi một a và n
a
ø(n)
= 1 (mod n)
là đúng nếu n là số nguyên tố, bởi vì trong trường hợp đó 
(n) = (n 1). Tuy nhiên, nó cũng được dùng cho số nguyên bất
kỳ n. (  (n) là số các số nguyên dương nhỏ hơn n mà là tương
đối nguyên tố với n.)
a
ø(n) + 1
= a (mod n)
tương tự như trường hợp với định lý Fermat, hình thức đầu
tiên của định lý Euler yêu cầu được tương đối chính để n,
nhưng dạng này thì không.
7

= 1 đúng khi a mod p = 1
- Tính chất 2:
Cho p là một số nguyên tố lớn hơn 2. Ta có thể viết p 1 = 2
k
q, với k> 0 q lẻ. a là một số nguyên trong phạm vi 1 < a < p 1 thì một
trong hai điều kiện sau là đúng:
+ a
q
là đồng dư với 1 modulo p. Đó là, a
q
mod p = 1, hoặc tương
đương, a
q
≡1 (mod p).
8
+ Một trong số a
q
, a
2q
, a
4q
, , a
2k-1q
là đồng dư với 1 modulo p. Đó
là, có một số j số trong khoảng (1≤ j≤k) sao cho a
2j-
1q
mod p = 1 mod p = p 1, hoặc tương đương a
2j-1q
≡ 1 (mod p).

Làm thế nào chúng ta có thể sử dụng các thuật toán Miller-Rabin để xác
định với mộ tmức độ cao hay không một số nguyên là số nguyên tố? Nó có
thể được hiển thị đó được đưa ra một n số lẻ đó không phải là nguyên tố và một
chọn ngẫu nhiên số nguyên, a với 1 <a < n 1, xác suất mà TEST là ít hơn 1 /
9
4. Như vậy, nếu giá trị khác nhau của một được lựa chọn, xác suất rằng tất
cả chúng sẽ vượt qua TEST (inconclusive) cho n là ít hơn (4/1)
t

Ví dụ, với t = 10, xác suất mà một số nonprime sẽ vượt qua tất cả các bài
kiểm tra mười nhỏ hơn 10
6
.Vì vậy, đối với một giá trị đủ lớn của t, thì n là số
nguyên tố nếu thử nghiệm của Millerluôn luôn trả về inconclusive.
Điều này cho chúng ta một cơ sở để xác định một số nguyên lẻ n là số nguyên
tố vớimột mức độ hợp lý
sự tự tin. Thủ tục như sau: Liên tiếp gọi TEST (n) bằng cách sử dụng các giá
trị ngẫu nhiên chọn cho
a. Nếu tại bất kỳ điểm nào, TEST trả về tổng hợp, sau đó n được xác định
lànonprime. Nếu tiếp tục TEST
trở lại không thể kết luận cho bài kiểm tra t, cho một giá trị đủ lớn của t, giả
sử n rằnglà số nguyên tố.
• Thuật toán tất định tính nguyên tố
Trước năm 2002, không có phương pháp được biết đến về hiệu quả tính
nguyên tố của số rất lớn. Tất cả các thuật toán được sử dụng, bao gồm phổ biến
nhất (Miller-Rabin), tạo ra một kết quả xác suất. Trong năm
2002, Agrawal, Kayal, và Saxena đã phát triển một thuật toán tương đối đơn giản
và rõ rằng hiệu quả các quyết định có một số lượng lớn cho là một nguyên
tố. Các thuật toán, được gọi là thuật toán AKS, không xuất hiện để được hiệu quả
như các thuật toán Miller-Rabin.

nguyên x giải quyết hệ thống đồng thời đồng dư.
Hơn nữa, tất cả các giải pháp x để hệ thống này là đồng dư modulo sản
phẩm N = n
1
n
2
n
k.
Do đó:
cho tất cả ,
khi và chỉ khi
Đôi khi, các đồng dư đồng thời có thể được giải quyết ngay cả khi các
i
n
's không phải là cặp nguyên tố cùng nhau. Một giải pháp x tồn tại khi và chỉ khi:
Tất cả các giải pháp x này sau đó được đồng dư của ít nhất phổ biến
nhiều của i
n
12
Một phương pháp khác để giải quyết các hệ thống tương tự của phương trình
đã được mô tả bởi Aryabhata (thế kỷ thứ 6, xem Kak 1986 ). Trường hợp đặc biệt
của định lý phần còn lại Trung Quốc cũng được biết là Brahmagupta (thế kỷ 7), và
xuất hiện trong Fibonacci 's Liber Abaci (1202).
Một trình bày lại hiện đại của các định lý trong ngôn ngữ đại số là một n số
nguyên dương tính với thừa tướng chúng ta có đẳng cấu giữa một
vòng và sản phẩm trực tiếp của các bộ phận điện chính của nó:
Sự tồn tại: Sự tồn tại có thể được xem bởi một trình xây dựng rõ ràng
của x. Chúng tôi sẽ sử dụng ký hiệu là [a - 1] b để biểu thị các nghịch đảo
của a (mod b), nó được định nghĩa chính xác khia và b là nguyên tố cùng nhau -
xây dựng sau đây giải thích tại sao các điều kiện là cần thiết:

nữa, hai số nguyên có cùng tính chất đó với g là đồng dư theo modulo n. Chứng ta
định nghĩa một hàm
(trong đó Z
n
ký hiệu cho vành các số nguyên modulo n)
theo g là lớp các số nguyên k modulo n. Hàm này là một đồng cấu
nhóm, được gọi là logarit rời rạc theo cơ số b.
14
Sau đây là công thức đổi cơ số giống như logarith thông thường: Nếu c là
một phần tử sinh khác của G, thì:
15
VI. SỐ BIỂU TƯỢNG
Chúng tôi người sử dụng một hệ thống số được gọi là "căn cứ mười". Đó là
hệ thống sử dụng một số thiết lập của các biểu tượng đại diện cho một nhóm của
sự vật, và ở nhiều nước trên thế giới, số ký hiệu tiếng Ả Rập là những gì được sử
dụng. Những ký hiệu là 0 1 2 3 4 5 6 7 8 9.
Chúng tôi người sử dụng một hệ thống số mười bắt đầu với số không và các
công trình đó là cách để chín. Khi chúng ta đến chín chúng tôi bắt đầu một cột mới
bên trái chấm xuống một một, và sau đó đưa một số không ở bên phải của nó (09
+ 01 = 10).
May tinh nghĩ trong hệ nhị phân , nhưng hiển thị dữ liệu nhị phân của họ đối
với con người trong các định dạng khác nhau như bát phân hay thập lục
phân . 'Mười sáu cơ sở "Hệ thống bát phân cũng được gọi là' cơ sở tám" và được
gọi là thập lục phân.
Để thực hiện bất kỳ cuộc thảo luận của các hệ thống số có ý nghĩa, bạn phải
hiểu rằng tất cả các hệ số bao gồm các biểu tượng. Chúng con người ở các quốc
gia nói tiếng Anh nhất sử dụng các biểu tượng được gọi là 'không' qua 'chín' (0 -
9). Những biểu tượng được sắp xếp theo cột. Mỗi khi bạn di chuyển một cột bên
trái, đó là mười lần giá trị những gì nó sẽ có giá trị một cột bên phải. (100 là mười
lần lớn hơn 10). Chúng con người đã nhận để sử dụng để sử dụng các biểu tượng

người chúng ta sử dụng mười cơ sở, và các máy tính sử dụng hệ nhị phân (cơ sở
hai), bạn phải trở nên khá kỹ năng chuyển đổi giữa hai người. Một wanabe khoe
khoang về sự hiểu biết nhị phân. Một guru thật hacker có thể suy nghĩ và chuyển
đổi giữa chúng trong giấc ngủ của mình.Điều này là bởi vì họ đã học được để làm
điều này trong khi exhaused trở thành giai đoạn chuyển trong 72-giờ buổi hacking.
HEX (thập lục)
Hexadecimal tính từ số không đến mười lăm (0 - F), và sau đó lăn qua một
một theo sau là một số không (16 = 10). Khó khăn nhiều người có với hệ thập lục
17
phân là hệ thống số đếm tất cả các con đường lên đến biểu tượng cuối cùng chúng
tôi con người sử dụng (9), nhưng vẫn tiếp tục về sau đó sử dụng ký tự thay vì con
số. Điều này đơn giản chỉ vì con người chúng ta chỉ có mười ngón tay, và chúng
tôi không có số ký hiệu cho bất cứ điều gì qua 9. Chúng con người đếm 9-10 bằng
cách di chuyển đến một cột thứ hai, vẽ một một, và đưa một số không đằng sau nó.
Thiết bị giao diện mạng có một địa chỉ MAC đó là trong thập lục phân. Màu
sắc trongHTML được thực hiện trong thập lục phân. Hex-bãi đều được làm
bằng máy tính bộ nhớ khi một máy tính bị treo. Nếu bạn đang đọc một cái gì đó,
và đi qua một tập hợp các ký tự trước bằng "0" x, bạn có thể đối phó với cái gì đó
trong hệ thập lục phân.
Đây là biểu đồ hiển thị một số thông qua việc thiết lập đầu tiên của biểu
tượng trong mỗi hệ thống đánh số.
18
Thập phân Binary Bát phân Hex
00 0 0000 00 00
01 0 0001 01 01
02 0 0010 02 02
03 0 0011 03 03
04 0 0100 04 04
05 0 0101 05 05
06 0 0110 06 06