BỘ GIÁO DỤC VÀ ĐÀO TÀO
TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG
———————————
ĐỒ ÁN TỐT NGHIỆP
NGÀNH: ĐIỆN TỬ VIỄN THÔNG
Người hướng dẫn : Thạc sỹ Nguyễn Văn Dương
Sinh viên
: Lê Thế Trị
HẢI PHÒNG – 2018
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG
————————–
XÂY DỰNG CHƯƠNG TRÌNH MÃ HÓA VÀ GIẢI MÃ RSA
ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC CHÍNH QUY
NGÀNH: ĐIỆN TỬ VIỄN THÔNG
Người hướng dẫn
: Thạc sỹ Nguyễn Văn Dương
Sinh viên
: Lê Thế Trị
HẢI PHÒNG – 2018
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG
—————————–
NHIỆM VỤ ĐỀ TÀI TỐT NGHIỆP
Sinh viên : Lê Thế Trị.
Mã sinh viên: 1212103004.
Lớp
: ĐT1601.
Ngành : Điện tử viễn thông.
Tên đề tài : Xây dựng chương trình mã hóa và giải mã RSA
NHIỆM VỤ ĐỀ TÀI
1. Nội dung và các yêu cầu cần giải quyết trong nhiệm vụ đề tài tốt
nghiệp ( về lý luận, tính thực tiễn, tính học và các sơ đồ ).
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
2. Các định lý toán học và thuật toán để xây dựng chương trình
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
3. Địa điểm
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
……………………………………………………………………………………………………..
CÁN BỘ HƯỚNG DẪN ĐỀ TÀI TỐT NGHIỆP
Người hướng dẫn :
Họ và tên: Nguyên Văn Dương.
Học hàm, học vị: Thạc sỹ.
Cơ quan công tác: Trường Đại học Dân lập Hải Phòng.
Nội dung hướng dẫn:
………………………………………..…………………………………………………………………………………
…………………..………………………………………..…………………………………………………………….
……………………………………….………………………………………..………………………………………..
……………………………………………………………………………………………………..…………………………
……………………………………………………………………………..………………………………………..……….
……………………………………………………………………………………………..…………………………………
.………………………..……………………………………………………………………………………………………..
………………………………………..…………………………………………………………………………………
…………………..………………………………………..…………………………………………………………….
……………………………………….………………………………………..………………………………………..
……………………………………………………………………………………………………..…………………………
.……………………………………………………………………………..………………………………………..………
…………………………………………………………………………………………………………………………………………..
Đề tài tốt nghiệp được giao ngày …… tháng …… năm 2018.
Yêu cầu phải hoàn thành xong trước ngày …… tháng …… năm 2018.
Đã nhận nhiệm vụ ĐTTN
Đã giao nhiệm vụ ĐTTN
Sinh viên
Người hướng dẫn
Hải Phòng, ngày …… tháng ….. năm 2018.
HIỆU TRƯỞNG
GS.TS.NGƯT Trần Hữu Nghị
PHẦN NHẬN XÉT TÓM TẮT CỦA CÁN BỘ HƯỚNG DẪN
1. Tinh thần thái độ của sinh viên trong quá trình làm đề tài tốt nhiệp:
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
2. Đánh giá chất lượng của đồ án:
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
3. Cho điểm của cán bộ hướng dẫn. (Điểm ghi cả chữ và số)
Hải Phòng, ngày…..tháng….năm 2018
Cán bộ hướng dẫn
PHẦN NHẬN XÉT TÓM TẮT CỦA NGƯỜI CHẤM PHẢN BIỆN
1. Đánh giá chất lượng đề tài tốt nghiệp:
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
2. Cho điểm của cán bộ phản biện. (Điểm ghi cả chữ và số).
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
…………………………………………………………………………………………………………………..
Hải Phòng, ngày ….. tháng …. năm 2018.
Người chấm phản biện.
MỤC LỤC
LỜI NÓI ĐẦU.
Chương 1. Tổng quan về mật mã học.
1.1 Giới thiệu về mật mã học.
1.2 Tổng quan về mã hóa.
Chương 2. Mã hóa RSA.
2.1 Lý thuyết số
2.1.1 Thuật toán Euclid
2.1.2 Số nguyên tố
2.1.3 Định lý Fermat và định lý Euler
2.1.3.1
Định lý Fermat
2.1.3.2
Hàm số Euler
2.1.4 Kiểm tra số nguyên tố
2.1.4.1
Thuật toán Miller-Rabin
2.1.4.2
Hai tính chất của số nguyên tố
2.1.4.3
Chi tiết về thuật toán
2.1.4.4
Sử dụng thuật toán Miller-Rabin lặp đi lặp lại
2.1.4.5
Thuật toán xác định số nguyên tố
2.1.4.6
Sự phân bố của hai số nguyên tố
2.1.5 Định lý còn lại của Trung Hoa
2.1.5.1
Hai khẳng định của CRT
2.1.5.2
Chứng minh khẳng định đầu tiên
2.1.5.3
Chứng minh khẳng định thứ hai
2.1.6 Logarithms rời rạc
2.1.6.1
Khả năng của một số nguyên (mod n )
2.1.6.2
Logarithms cho mô đun số học
2.1.6.3
Tính toán logarithms rời rạc
2.2 Mật mã khóa công khai
2.2.1 Nguyên tắc của các hệ thống mã hóa khóa công khai
2.2.1.1
Hệ thống mật mã khóa công khai
2.2.1.2
Các bước cần thiết
2.2.1.3
Ứng dụng của các hệ thống mật mã khóa công khai
2.2.1.4
Yêu cầu đối với mật mã khóa công khai
2.2.1.5
Phân thích mã hóa khóa công khai
2.2.2 Thuật toán RSA
2.2.2.1
Mô tả thuật toán
2.2.2.2
Các khía cạnh tính toán
2.2.2.3
Hoạt động hiệu quả dùng khóa công khai
2.2.2.4
Tạo khóa
Chương 3. Chương trình mã hóa và giải mã RSA
3.1. Mô tả thuật toán
3.2. Mã chương trình
3.2.1
Cryptomath.py
3.2.2
RabinMiller.py
3.2.3
MakeRsaKeys.py
3.2.4
Encrypted.py
3.2.5
Decrypted.py
LỜI NÓI ĐẦU
Trước đây khi công nghệ máy tính chưa phát triển, khi nói đến vấn đề an toàn
bảo mật thông tin, chúng ta thường hay nghĩ đến các biện pháp nhằm đảm bảo cho
thông tin được trao đổi hay cất giữ một cách an toàn và bí mật, chẳng hạn là các biện
pháp như: Đóng dấu và ký niêm phong một bức thư để biết rằng lá thư có được
chuyển nguyên vẹn đến người nhận hay không, dùng mật mã mã hóa thông điệp để
chỉ có người gửi và người nhận hiểu được thông điệp, lưu giữ tài liệu trong các két
sắt có khóa tại nơi được bảo vệ nghiêm ngặt.
Ngày nay với sự phát triển của khoa học công nghệ, đặt biệt là sự phát triển
của Internet, việc sử dụng máy tính và điện thoại cá nhân càng trở lên rộng rãi, dẫn
đến càng nhiều thông tin được lưu trữ trên máy tính và gửi đi trên mạng Internet. Do
đó nhu cầu về an toàn và bảo mật thông tin trên máy tính càng nhiều và việc sử dụng
mật mã mã hóa càng được phổ biến. Trong đồ án này, em thực hiện xây dựng chương
trình mã hóa và giải mã mật mã hóa công khai RSA. Đồ án này gồm 3 chương:
Chương 1 : Tổng quan về mật mã học.
Chương 2 : Mật mã hóa công khai RSA.
Chương 3 : Chương trình RSA.
Em xin cám ơn thầy Nguyễn Văn Dương, giảng viên hướng dẫn, đã rất nhiệt
tình chỉ bảo em hoàn thành đề tài này, cũng như các thầy cô khác trong bộ môn đã
tạo điều kiện cho em trong suốt thời gian làm đề tài.
Hải Phòng, ngày …. tháng …. năm 2018
Sinh viên
Trị
Lê Thế Trị
Chương 1.
Tổng quan về mật mã học
1.1. Giới thiệu về mật mã học.
An toàn thông tin là bảo vệ các đặc tính riêng tư (confidentialy), toàn vẹn
(intergrity) và khả dụng (availabity) của thông tin.
– C: (Confidentialy) bảo vệ tính riêng tư của dữ liệu thông qua các cơ chế
chứng thực và mã hóa, ngăn ngừa những người không hợp lệ sẽ không được đọc
những thông tin. Giống như các bì thư khi phát lương thưởng được dán chữ
Confidentialy, chúng ta có thể hình dung trong môi trường công nghệ thông tin là
một người chưa đăng nhập vào Domain sẽ không được truy cập những dữ liệu chỉ
chia sẻ cho các Domain User.
– I: (Intergrity) bảo vệ tính toàn vẹn của dữ liệu thông qua các thuật toán RSA,
SHA, MD5 … ngăn ngừa attacker thay đổi các thông tin nhạy cảm trong quá trình
truyền.
– A: (Available) bảo đảm dữ liệu luôn ở trong trạng thái sẵn sằng đáp ứng nhu
cầu của người dùng.
– Non-Repudiation: Tính không thể chối bỏ, nghĩa là dữ liệu người nào gửi đi
thì họ phải có trách nhiệm với các thông tin của mình thông qua các xác nhận nguồn
gốc như chữ kí điện tử.
Để thực hiện điều này chúng ta áp dụng các biện pháp xác thực và mã hóa.
Và mật mã học là nghiên cứu về vấn đề mã hóa. Mã hóa là một tiến trình biến đổi
dữ liệu từ dạng plaintext (văn bản thuần túy dễ dàng nhận biết) thành kết quả
ciphertext, dạng dữ liệu không thể đọc được nếu không được giải mã bằng các khóa
thích hợp. Mục tiêu của mã hóa là ngăn ngừa việc tấn công đánh cắp dữ liệu trái
phép hoặc phòng ngừa việc mất mát dữ liệu khi bị tấn công vật lý như trộm đĩa cứng,
máy tính xách tay hay thậm chí đột nhập vào hệ thống vẫn không thể xem được dữ
liệu riêng tư, bí mật đã được bảo vệ bằng các thuật toán mã hóa mạnh mẽ.
1.2. Khái niệm cơ bản về mật mã học
Kỹ thuật mật mã thông qua việc biến đổi hoặc mã hoá thông tin, biến đổi
những thông tin nhạy cảm, vấn đề cơ mật thành những văn tự mã hoá có dạng hỗn
loạn, làm cho tin tặc khó lòng mà đọc hiểu được, từ đó sẽ đạt được hai mục đích:
một là, làm cho tin tặc không biết làm thế nào để giải mã nên cũng không thể thu
được những thông tin có bất kỳ ý nghĩa nào trong chuỗi mật mã hỗn loạn đó; hai là
làm cho tin tặc không có khả năng làm giả thông tin với chuỗi mật mã hỗn loạn như
thế. Khoa học nghiên cứu kỹ thuật mật mã gọi là mật mã học.
Mật mã học bao gồm hai nhánh, là mật mã học lập mã và mật mã học phân
tích. Mật mã học lập mã với ý là tiến hành mã hoá thông tin để thực hiện việc che
giấu thông tin, còn mật mã học phân tích là ngành học nghiên cứu phân tích giải dịch
mật mã. Hai cái đối lập với nhau, nhưng lại thúc đẩy lẫn nhau.
Dùng phương pháp mật mã có thể che dấu và bảo hộ những thông tin cơ mật,
làm cho người chưa được uỷ quyền không thể lấy được thông tin, những thông tin
được giấu kín kia được gọi là văn bản rõ, mật mã có thể đem văn bản rõ biến đổi
thành một loại hình khác, gọi là văn bản mật. Sự biến đổi văn bản rõ thành văn bản
mật gọi là mã hoá bảo mật, quá trình người thu nhận hợp pháp khôi phục từ văn bản
mật trở thành văn bản rõ được gọi là quá trình giải mã (hoặc giải mật). Người thu
nhận phi pháp có ý đồ phân tích từ văn bản mật ra thành văn bản rõ, gọi là giải dịch.
1.3. Các thành phần của một hệ mật mã
Một hệ mật là một bộ 5 (P, C, K, E, D) thoả mãn các điều kiện sau:
+ P là một tập hữu hạn các bản rõ có thể
+ C là tập hữu hạn các bản mã có thể
+ K (không gian khoá) là tập hữu hạn các khoá có thể
+ Đối với mỗi kK có một quy tắc mã ek: P -> C và một quy tắc giải
mã tương ứng dkD. Mỗi ek: P -> C và dk: C -> P là những hàm mà: dk(ek(x)) = x
với mọi bản rõ xP.
Điều kiện thứ 4 là tính chất chủ yếu. Nội dung của nó là nếu một bản rõ x
được mã hoá bằng ek và bản mã nhận được sau đó được giải mã bằng dk thì ta phải
thu được bản rõ ban đầu x. Trong trường hợp này hàm mã hoá ek phải là hàm đơn
ánh, nếu không việc giải mã sẽ không thể thực hiện được một cách tường minh.
1.4. Phân loại các hệ mật mã
Hiện nay người ta đã thiết kế ra nhiều loại hệ thống mật mã, nếu như lấy khoá
mật mã làm tiêu chuẩn có thể phân các hệ mật mã thành hai loại:
+ Hệ mật mã đối xứng (còn gọi là mật mã khoá đơn hoặc là mật mã khoá riêng):
Trong các hệ mật mã này, khoá mật mã mã hoá bảo mật giống với khoá giải mã hoặc
trên thực tế là cùng đẳng cấp. Lúc này khoá mật mã cần phải có một đường truyền
an toàn để truyền đưa khoá mật mã từ phía người truyền cho phía người nhận. Đặc
điểm của mật mã đối xứng là bất luận khi gia công bảo mật hay là khi giải mã đều
sử dụng cùng một khoá mật mã. Do đó tính an toàn của mật mã này là sự an toàn
của khoá mật mã. nếu như khoá mật mã bị tiết lộ, thì hệ thống mật mã này sẽ bị phá
vỡ. Mật mã đối xứng có ảnh hưởng nhất là phép tính DES do cục tiêu chuẩn quốc
gia Mỹ công bố vào năm 1977.
– Ưu điểm: Tính an toàn cao, tốc độ giải mã nhanh.
– Nhược điểm:
Theo sự mở rộng của quy mô mạng lưới, việc quản lý khoá mật mã trở
thành một việc khó khăn.
Không có cách nào giải quyết vấn đề xác nhận thông tin.
Thiếu năng lực kiểm tra tự động sự tiết lộ khoá mật mã.
+ Hệ mật mã bất đối xứng (còn gọi là mật mã khoá công khai hoặc mật mã khoá
đôi):
Trong các hệ mật mã này quá trình mã hoá và giải mã có chìa khoá khác nhau,
lúc này không cần có đường truyền an toàn để truyền đưa khoá mật mã mà chỉ cần
bộ phát sinh khoá mã tại chỗ để tạo ra khoá giải mã đồng thời lấy đó để khống chế
các thao tác giải mã. Mật mã bất đối xứng là một thể chế mật mã loại mới do W.Diffie
và M.E Hellman đề xuất năm 1976. Do quá trình mã hoá và giải mã của thể chế mật
mã bất đối xứng không như nhau và khoá mã bảo mật là công khai, hơn nữa, chỉ yêu
cầu bảo mật khoá giải mã, cho nên mật mã bất đối xứng không tồn tại vấn đề quản
lý khoá mật mã. Mật mã bất đối xứng còn một ưu điểm nữa là có thể có khả năng ký
tên chữ số và một số chức năng mới. Mật mã bất đối xứng nổi tiếng nhất là thể chế
mật mã RSA do ba người là Rivest, Shamir và Adleman đề xuất năm 1977. Khuyết
điểm của mật mã bất đối xứng là: phép tính mật mã là tương đối phức tạp, tốc độ
giải mã chậm.
Do đó, việc bảo mật dữ liệu trên mạng nên dùng cơ chế bảo mật hỗn hợp kết
hợp giữa mật mã đối xứng và mật mã bất đối xứng, tức là khi giải mã thì dùng mật
mã đối xứng, khi truyền đưa khoá mật mã thì dùng mật mã bất đỗi xứng. Như thế
tức là đã giải quyết được khó khăn trong việc quản lý khoá mật mã, lại vừa giải quyết
được vấn đề tốc độ giải mã. Không còn hoài nghi gì nữa, nó là một phương pháp
tương đối tốt để giải quyết vấn đề an toàn thông tin khi truyền đưa trên mạng hiện
nay.
1.5. Một số phương pháp mã hóa
1.5.1. Mã hóa cổ điển
Mã hoá cổ điển là phương pháp mã hoá đơn giản nhất xuất hiện đầu tiên trong
lịch sử ngành mã hoá. Thuật toán đơn giản và dễ hiểu. Những phương pháp mã hoá
này là cở sở cho việc nghiên cứu và phát triển thuật toán mã hoá đối xứng được sử
dụng ngày nay.
Trước khi mã hoá một bản rõ thành bản mã bằng các phương pháp mã hoá, ta
xét một sự thiết lập tương ứng giữa các ký tự và các thặng dư theo modulo 26 như
sau: A0, B1, …, Z25 hoặc theo bảng
+ Mật mã CAESAR
Một trong số những người sử dụng mật mã được biết sớm nhất, đó là Julias
Caesar (Xê-Da). Ông đã làm cho các bức thư trở nên bí mật bằng cách dịch mỗi chữ
cái đi ba chữ cái về phía trước trong bảng chữ cái (và ba chữ cái cuối cùng thành ba
chữ cái đầu tiên). Đây là 1 ví dụ về sự mã hoá, tức là quá trình làm cho bức thư trở
nên bí mật. Phương pháp mã hoá của CAESAR có thể được biểu diễn bởi hàm f,
hàm này gán cho số nguyên không âm p, p 25, số nguyên f(p) trong tập 0, 1, 2,
… , 25 sao cho: f(p) = (p+3) mod 26.
Như vậy, trong phiên bản mã hoá của bức thư, chữ cái được biểu diễn bởi p
sẽ được thay bằng chữ cái được biểu diễn bởi: (p+3) mod 26
Để phục hồi lại bức thư gốc đã được mã hoá theo mật mã của CAESAR, ta
cần phải dùng hàm ngược f-1 của f: f-1(p) = (p-3) mod 26. Nói cách khác, để tìm lại
bức thư gốc, mỗi một chữ cái lùi lại ba chữ trong bảng chữ cái, với ba chữ cái đầu
tiên chuyển thành ba chữ cái cuối cùng tương ứng của bảng chữ cái.
Nhận xét: phương pháp mã hoá của CAESAR không có độ an toàn cao.
Phương pháp mã hoá này dễ bị khám phá bằng cách dựa vào tần xuất xuất hiện của
các chữ cái trong bức thư.
+ Mã thay thế
Mã thay thế có thể được mô tả như sau: Cho P = C = Z26. K chứa mọi hoán
vị có thể của 26 kí hiệu 0, 1, …, 25. với mỗi hoán vị K, ta định nghĩa:
e(x) = (x) và d(y) = -1(y)
trong đó -1 là hoán vị ngược của
Ví dụ: mã hoá bản rõ: illustrate sử dụng mã thay thế với khoá là 1 hoán vị bất kì sau:
Với khoá là một hoán vị bất kì ở trên thì bản rõ: illustrate sẽ tương ứng với bản mã
sau (sử dụng hàm mã hoá e(x) = (x)): ZBBUVMCXMH
Hàm giải mã là phép hoán vị ngược, điều này được thực hiện bằng cách viết
hàng thứ hai lên trước rồi sắp xếp theo thứ tự chữ cái. Ta nhận được:
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
0
1
2
3
4
5
6
7
8
9
1
0
1
1
12
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
22
2
3
2
4
2
5
Sử dụng phép hoán vị ngược này ta biến đổi bản mã: ZBBUVMCXMH thành
bản rõ là: illustrate
Nhận xét: Với mã thay thế, ta có một không gian khoá tương đối lớn (mỗi
khoá là một hoán vị của 26 kí hiệu 0, 1, …, 25) do đó nó khó có thể bị thám theo
phương pháp tìm khóa vét cạn, thậm chí cả bằng máy tính.
+ Mã vigenere
Sử dụng mã vigenere, ta có thể gán cho mỗi khoá k một chuỗi kí tự có độ dài
m được gọi là từ khoá. Mật mã vigenere sẽ mã hoá đồng thời m kí tự: mỗi phần tử
của bản rõ tương đương với m kí tự. Mã vigenere có thể được mô tả như sau:
Cho m là một số nguyên dương cố định nào đó. định nghĩa P=C=K=(Z)m với
khoá k = (k1, k2, …, km), ta xác định:
ek(x1, x2, …, xm) = (x1+k1, x2+k2, …, xm+km) và
dk(y1, y2, …, ym) = (y1-k1, y2-k2, …, ym-km)
trong đó tất cả các phép toán được thực hiện trong Z26
Ví dụ: Mã hoá bản rõ: thiscryptosystemisnotsecure với m=6 và từ khoá là CIPHER
bằng mã vigenere.
Từ khóa CIPHER tương ứng với dãy số k=(2, 18, 15, 7, 4, 17)
Biến đổi các phần tử của bản rõ thành các thặng dư theo modulo 26, viết chúng thành
các nhóm 6 rồi cộng với từ khoá theo modulo 26 như sau:
Dãy kí tự: 21, 15, 23, 25, 6, 8, 0, 23, 8, 21, 22, 15, 20, 1, 19, 19, 12, 9, 15, 22, 8, 25,
8, 19, 22, 25, 19. Sẽ tương ứng với xâu bản mã là:
VPXZGIAXIVWPUBTTMJPWIZITWZT
Để giải mã ta biến đổi các phần tử của bản mã thành các thặng dư theo modulo
26, viết chúng thành các nhóm 6 rồi trừ với từ khoá theo modulo 26. Kết quả ta sẽ
ra được bản rõ như sau: thiscryptosystemisnotsecure
Nhận xét: Ta thấy rằng số các từ khoá có thể với số độ dài m trong mật mã
vigenere là 26m , bởi vậy, nó khó có thể bị thám theo phương pháp tìm khoá vét cạn,
thậm chí với các giá trị m khá nhỏ, phương pháp tìm khoá vét cạn cũng phải yêu cầu
thời gian khá lớn.
+ Mã hoán vị
Ý tưởng của mã hoán vị là giữ các ký tự của bản rõ không thay đổi nhưng sẽ
thay đổi vị trí của chúng bằng cách sắp xếp lại các ký tự này. Mã hoán vị có thể được
mô tả như sau:
Cho m là một số nguyên dương xác định nào đó. Cho P=C=(Z26)m và K gồm
tất cả các hoán vị của 1, …, m. Đối với một khoá (tức là một hoán vị) ta xác
định: e(x1, …, xm)=(x(1), …, x(m)) và
d(y1, …, ym)=(y-1(1) , … , y-1(m) )
trong đó -1 là hoán vị ngược của .
Ví dụ: Mã hoá bản rõ: shesellsseashellsbytheseashore, sử dụng mã hoán vị, với m=6
và khoá là phép hoán vị sau:
Trước tiên ta nhóm bản rõ thành các nhóm 6 ký tự:
shesel / lsseas / hellsb / ythese / ashore
Bây giờ mỗi nhóm 6 chữ cái được sắp xếp lại theo hoán vị , ta có:
EESLSH / SALSES / LSHBLE / HSYEET / HRAEOS
Như vậy bản mã là: EESLSHSALSESLSHBLEHSYEETHRAEOS
Để giải mã ta sử dụng phép hoán vị ngược của là -1 có dạng:
Ta cũng nhóm bản mã thành nhóm 6 ký tự:
EESLSH / SALSES / LSHBLE / HSYEET / HRAEOS
Mỗi nhóm 6 chữ cái được sắp xếp lại theo hoán vị ngược -1 ta có:
shesel / lsseas / hellsb / ythese / ashore
Cuối cùng ta thu được bản rõ là: shesellsseashellsbytheseashore
+ DES (Data Encryption Standard)
Lược đồ mã hoá được sử dụng phổ biến nhất dựa trên cơ sở của DES được
phát triển vào năm 1977 bởi cục tiêu chuẩn quốc gia Mỹ, bây giờ là học viện tiêu
chuẩn và công nghệ quốc gia (NIST), chuẩn xử lý thông tin liên bang. Đối với DES,
dữ liệu được mã hoá trong khối 64 bit sử dụng khoá 56 bit. Thuật toán chuyển 64 bit
đầu vào, biến đổi và đưa ra 64 bit đầu ra. DES được sử dụng phổ biến. Nó cũng là
chủ đề của rất nhiều cuộc tranh luận về mức độ an toàn. Để hiểu rõ giá trị của những
cuộc tranh luận về DES chúng ta xem qua lại lịch sử của DES.
Cuối những năm 1960, IBM đã đưa ra dự án nghiên cứu trong bảo mật máy tính. Dự
án kết thúc vào năm 1971 với việc cho ra đời thuật toán gọi là LUCIFER, hệ mật
LUCIFER đã được sử dụng trong hệ thống phân phát tiền, cũng được phát triển bởi
IBM. LUCIFER là một khối mã hoá Feistel được thực hiện trên khối 64 bit, sử dụng
khoá có độ dài 128 bit. Những kết quả đầy hứa hẹn đưa ra bởi dự án LUCIFER, IBM
đã bắt tay vào công việc đầy nỗ lực để phát triển thành một sản phẩm mã hoá thương
mại có thể bán được, đó là một sản phẩm lý tưởng có thể thực hiện được trên một
chíp đơn. Công đầu phải kể đến Walter Tuchman và Carl Meyer, nó không chỉ làm
rắc rối cho những nhà thiết kế mà còn cần phải có những lời khuyên của những nhà
kỹ thuật và tư vấn ở bên ngoài đó là NSA. Kết quả của nỗ lực này là một phiên bản
LUCIFER có chọn lọc kỹ lưỡng, phiên bản này có thể chống lại các phương pháp
giải dịch, nhưng nó cũng làm giảm độ dài khoá xuống còn 56 bit, để phù hợp trên
một chip đơn. Năm 1973 cục tiêu chuẩn quốc gia Mỹ (NBS) đưa ra một yêu cầu đề
nghị cho một chuẩn mã hoá quốc tế. IBM đã đưa ra xem xét những kết quả của dự
án Tuchman-Meyer. Kết quả nó được đề nghị là thuật toán tốt nhất và được công
nhận vào năm 1977 như là một chuẩn mã hoá dữ liệu.
Trước khi được công nhận như là một chuẩn mã hoá dữ liệu, DES đã trở thành
chủ đề của nhiều cuộc phê bình mạnh mẽ, và sự phê bình này vẫn chưa lắng xuống
cho đến ngày hôm nay. Có hai vấn đề được đưa ra không làm hài lòng những nhà
phê bình. Đầu tiên, chiều dài khoá của thuật toán LUCIFER nguyên thuỷ của IBM
là 128 bit nhưng hệ thống được đề nghị chỉ dùng 56 bit, một sự giảm rất lớn trong
độ dài khoá 72 bit. Những nhà phê bình lo sợ rằng (và vẫn sợ) chiều dài khoá quá
nhỏ để chống lại những cuộc tấn công quy mô lớn. Mặt thứ 2 cần quan tâm là tiêu
chuẩn thiết kế cho cấu trúc bên trong của DES, những hộp S phải được coi là mật.
Như vậy, những người sử dụng không thể chắc chắn rằng cấu trúc bên trong của
DES là tự do cho bất kỳ những điểm yếu được che dấu, điều này sẽ cho phép NSA
hướng tới những thông báo giải mã không có lợi cho khoá. Những sự kiện xảy ra
sau, đặc biệt gần đây làm việc trên những sự giải dịch khác nhau, dường như chỉ rõ
rằng DES có một cấu trúc bên trong rất mạnh.
1.5.2. Thuật toán mã hóa công khai
+ Hệ mật RSA
Ý tưởng về một hệ mật khoá công khai đã được Diffie và Hellman đưa ra vào
1976. Còn việc hiện thực hóa hệ mật khoá công khai thì do Rivest, Shamir và
Adleman đưa ra đầu tiên vào 1977, họ đã tạo nên hệ mật RSA nổi tiếng.
Hệ mật này sử dụng các tính toán trong Zn, trong đó n là tích của 2 số nguyên tố
phân biệt p và q. Ta có thể mô tả hệ mật RSA như sau:
Cho n = p.q trong đó p và q là các số nguyên tố. Đặt P=C=Zn và định nghĩa:
K=(n,p,q,a,b):n=pq, p, q là các số nguyên tố, ab 1(mod (n))
Với K =(n,p,q,a,b) ta xác định
ek(x)=xb mod n
dk(y)=ya mod n
(x,y Zn) các giá trị n và b được công khai và các giá trị p, q, a được giữ kín,
(n)=(p-1)(q-1)
Quá trình thực hiện hệ mật RSA: (người gửi: Alice; người nhận: Bob)
+ Bob tạo hai số nguyên tố lớn p và q
+ Bob tính n = pq và (n) = (p-1)(q-1)
+ Bob chọn một số ngẫu nhiên b (0
và thương số nguyên q1. Nếu r2 = 0 thì dừng lại, nếu r2 khác không, chia r1 cho r2
được số dư r3 ….. Vì dãy các ri là giảm thực sự nến sau hữu hạn bước ta được số dư
rm+2 = 0.
ro = q1 × r1 + r2,0 < r2 < r1;
r1 = q2 × r2 + r3,0 < r3 < r2;
....;
rm − 1 = qm × rm + rm + 10 < rm + 1 < rm
rm = qm + 1 × rm + 1
trong đó số dư cuối cùng khác 0 là rm + 1 = d. Bài toán đặt ra là tìm x, y sao cho
a × x + b × y = rm + 1( = d)
Để làm điều này, ta tìm x, y theo công thức truy hồi, nghĩa là sẽ tìm xi và yi sao cho:
a × xi + b × yi = ri với i = 0,1,....
Ta có
a × 1 + b × 0 = a = ro và a × 0 + b × 1 = b = r1,
Nghĩa là:
xo = 1,x1 = 0 và yo = 0,y1 = 1.
(2.1)
Tổng quát, giả sử có
a × xi + b × yi = ri với i = 0,1,....
a × xi + 1 + b × yi + 1 = ri + 1 với i = 0,1,....
Khi đó từ
ri = qi + 1 × ri + 1 + ri + 2
Suy ra
ri − qi + 1 × ri + 1 = ri + 2
(a × xi + b × yi) − qi + 1 × (a × xi + 1 + b × yi + 1) = ri + 2
a × (xi − qi + 1 × xi + 1) + b × (yi − qi + 1 × yi + 1) = ri + 2
từ đó, có thể chọn
xi + 2 = xi − qi + 1 × xi + 1
(2.2)
yi + 2 = yi − qi + 1 × yi + 1
(2.3)
Khi i = m − 1 ta có được xm + 1 và ym + 1. Các công thức (1), (2), (3) là công thức truy
hồi để tính x,y.
Áp dụng giải thuật Euclid mở rộng tìm số nghịch đảo trong vành Zm
Số nghịch đảo trong vành Zm
Trong lý thuyết số, vành Zm được định nghĩa là vành thương của với quan
hệ đồng dư theo môđun m (là quan hệ tương đương) mà các phần tử của nó là các
lớp đồng dư theo mođun m (m là số nguyên dương lớn hơn 1). Ta cũng có thể
xét Zm chỉ với các đại diện của nó. Khi đó
Zm ={0, 1, ........, m – 1}
Phép cộng và nhân trong Zm là phép toán thông thường được rút gọn theo mođun m:
a + b = (a + b ) mod m
(2.4)
a ×b = (a × b ) mod m
(2.5)
Phần tử a của Zm được gọi là khả nghịch trong Zm hay khả nghịch theo mođun m nếu
tồn tại phần tử a' trong Zm sao cho a × a' = 1 trong Zm hay a × a’ ≡ 1(mod m). Khi
đó a' được gọi là nghịch đảo modulo m của a. Trong lý thuyết số đã chứng minh
rằng, số a là khả nghịch theo mođun m khi và chỉ khi GCD của a và m bằng 1.
Khi đó tồn tại các số nguyên x, y sao cho
m × x + a × y = 1
Đẳng thức này lại chỉ ra x là nghịch đảo của a theo mođun m. Do đó có thể tìm được
phần tử nghịch đảo của a theo mođun m nhờ thuật toán Euclid mở rộng khi chia m
cho a.
2.1.2. Số nguyên tố
Một số nguyên tố p > 1 là số nguyên tố khi và chỉ khi số chia của nó là 1 và
p. Số nguyên tố đóng vai trò quan trọng trong lý thuyết số và trong các kỹ thuật. Bất
cứ số nguyên a>1 đều đươc tính theo cách duy nhất.
a = 𝑞1
𝑎1 × 𝑞2
𝑎2 ×. . .× 𝑞𝑡
𝑎𝑡
(2.6)
trong đó : q1
(2.7)
Một dạng thay thế của định lý Fermat: Nếu p là số nguyên tố, a là một số nguyên
dương thì:
ap ≡ a (mod p)
(2.8)
Lưu ý rằng hình thức đầu của định lý Fermat: ap-1 ≡ 1(mod p) yêu cầu rằng a tương
đối nguyên tố với p, nhưng dạng này không đúng.
p=5; a = 3; ap = 35 = 243 ≡ 3(mod 5) = a(mod p)
p=5; a=10; ap = 105 = 100000 ≡ 10 (mod 5) ≡ 0(mod 5) = a(mod 5)
2.1.3.2. Định lý Euler
Trước khi trình bày định lý Euler, ta cần cần giới thiệu một điều quan trọng
gọi là hàm số của Euler, được viết ∅(𝑛) và được định nghĩa là số lượng các số
nguyên dương nhở hơn n và tương đối nguyên tố với n. Theo quy ước ∅(1)=1
Ví dụ: Xác định ∅(37) và ∅(35)
Bởi vì 37 là số nguyên tố, suy ra các số nguyên từ 1 đến 36 đều tương đối
nguyên tố với 37. Như vậy ∅(37)=36.
Với ∅(35), ta có một danh sách những số nguyên dương nhỏ hơn 35 và tương
đối nguyên tố với 35 là:
{1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,26,27,28,29,31,32,33,34}
có 24 số trong danh sách. Như vậy ∅(35)=24.
Bảng 2.2. Một số giá trị hàm số của Euler
n
∅(𝑛) n
∅(𝑛) n
∅(𝑛)
1
1
11
10
21
12
2
1
12
4
22
10
3
2
13
12
23
22
4
2
14
6
24
8
5
4
15
8
25
20
6
2
16
8
26
12
7
6
17
16
27
18
8
4
18
6
28
12
9
6
19
18
29
28
10
4
20
8
30
8
Trong bảng 2.2. là danh sách 30 giá trị đầu tiên của ∅(𝑛). Giá trị ∅(1) là
không có nghĩa nhưng định nghĩa có một giá trị 1. Cần phải rõ ràng rằng, đối với
một số nguyên tố p: ∅(𝑝) = p – 1. Bây giờ giả sử ta có hai số nguyên tố p và q khác
nhau. Sau đó chúng ta có thể thấy rằng:
Với: n = p×q.
Ta có: ∅(𝑛)= ∅(𝑝𝑞) = ∅(𝑝) × ∅(𝑞)= ( p – 1 ) × ( q – 1 )
Để thấy rằng: ∅(𝑛)= ∅(𝑝) × ∅(𝑞).
Hãy xét rằng tập hợp các số nguyên dương ít hơn n là tập {1, 2, …, (pq–1)}. Tập các
số nguyên không tương đối nguyên tố với n là tập {p, 2p, …, (q–1)p} và tập {q, 2q,
…, (p–1)q}.
Suy ra: ∅(𝑛) = (pq–1) – [(p–q)+(q–1)]
= pq – (p+q)+1
= (p–1)×(q–1)
= ∅(𝑝) × ∅(𝑞)
Ví dụ: ∅(21) = ∅(3) × ∅(7) = (3–1)×(7–1) = 2×6 =12. Mười hai số nguyên trong
đó là: {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}
