Tìm hiểu và cài đặt thuật toán mã hóa Elgamal

MỤC LỤC

Nhóm 01 – CNTT 2014_02


Tìm hiểu và cài đặt thuật toán mã hóa Elgamal

LỜI NÓI ĐẦU
Từ trước công nguyên con người đã phải quan tâm tới việc làm thế nào để đảm
bảo an toàn bí mật cho các tài liệu, văn bản quan trọng, đặc biệt là trong lĩnh vực quân
sự, ngoại giao. Ngày nay với sự xuất hiện của máy tính, các tài liệu văn bản giấy tờ và
các thông tin quan trọng đều được số hóa và xử lý trên máy tính, được truyền đi trong
một môi trường mà mặc định là không an toàn. Do đó yêu cầu về việc có một cơ chế,
giải pháp để bảo vệ sự an toàn và bí mật của các thông tin nhạy cảm, quan trọng ngày
càng trở nên cấp thiết. Mật mã học chính là ngành khoa học đảm bảo cho mục đích
này. Khó có thể thấy một ứng dụng Tin học có ích nào lại không sử dụng các thuật
toán mã hóa thông tin.
Chính vì nhu cầu cần thiết của mã hóa thông tin, nhóm chúng em với sự giúp đỡ
của thầy T.S Nguyễn Hữu Tuân đã tiến hành tìm hiểu về hệ mã hóa Elgamal từ đó tiến
hành cài đặt thuật toán mã hóa Elgamal. Hệ mã hóa Elgamal được biết đến là 1 hệ mã
hóa sử dụng bài toán Logarit rời rạc – một bài toán khó và chưa có phương pháp giải
hiệu quả. Chính vì vậy độ an toàn và khả năng ứng dụng của hệ Elgamal trong mã hóa
thông tin cũng rất cao và phổ biến.
Chân thành cảm ơn sự giúp đỡ của thầy đã giúp nhóm em hoàn thành báo cáo
này.
Nhóm 1_CNTT 2014_02

Nguyễn Xuân Bách
Đào Thị Thân

Nhóm 01 – CNTT 2014_02


CHƯƠNG I: TỔNG QUAN VỀ BẢO MẬT THÔNG TIN
1. An toàn bảo mật thông tin và mật mã học
Trải qua nhiều thế kỷ hàng loạt các giao thức (protocol) và các cơ chế
(mechanism) đã được tạo ra để đáp ứng nhu cầu an toàn bảo mật thông tin khi mà nó
được truyền tải trên các phương tiện vật lý (giấy, sách, báo …). Thường thì các mục
tiêu của an toàn bảo mật thông tin không thể đạt được nếu chỉ đơn thuần dựa vào các
thuật toán toán học và các giao thức, mà để đạt được điều này đòi hỏi cần có các kỹ
thuật mang tính thủ tục và sự tôn trọng các điều luật. Chẳng hạn sự bí mật của các bức
thư tay là do sự phân phát các lá thư đã có đóng dấu bởi một dịch vụ thư tín đã
được chấp nhận. Tính an toàn về mặt vật lý của các lá thư là hạn chế (nó có thể bị
xem trộm) nên để đảm bảo sự bí mật của bức thư pháp luật đã đưa ra qui định: việc
xem thư mà không được sự đồng ý của chủ nhân hoặc những người có thẩm quyền là
phạm pháp và sẽ bị trừng phạt. Đôi khi mục đích của an toàn bảo mật thông tin lại đạt
được nhờ chính phương tiện vật lý mang chúng, chẳng hạn như tiền giấy đòi hỏi phải
được in bằng loại mực và giấy tốt để không bị làm giả.
Về mặt ý tưởng việc lưu giữ thông tin là không có nhiều thay đổi đáng kể qua
thời gian. Ngày xưa thông tin thường được lưu và vận chuyển trên giấy tờ, trong khi
giờ đây chúng được lưu dưới dạng số hóa và được vận chuyển bằng các hệ thống viễn
thông hoặc các hệ thống không dây. Tuy nhiên sự thay đổi đáng kể đến ở đây chính
là khả năng sao chép và thay đổi thông tin. Người ta có thể tạo ra hàng ngàn mẩu tin
giống nhau và không thể phân biệt được nó với bản gốc. Với các tài liệu lưu trữ và
vận chuyển trên giấy điều này khó khăn hơn nhiều. Và điều cần thiết đối với một xã
hội mà thông tin hầu hết được lưu trữ và vận chuyển trên các phương tiện điện tử
chính là các phương tiện đảm bảo an toàn bảo mật thông tin độc lập với các phương
tiện lưu trữ và vận chuyển vật lý của nó. Phương tiện đó chính là mật mã học, một
ngành khoa học có lịch sử lâu đời dựa trên nền tảng các thuật toán toán học, số học,

xác suất và các môn khoa học khác.
2. Khái niệm hệ thống và tài sản của hệ thống
Khái niệm hệ thống: Hệ thống là một tập hợp các máy tính gồm các thành
phần phấn cứng, phần mềm và dữ liệu làm việc được tích luỹ qua thời gian.
Tài sản của hệ thống bao gồm:
• Phần cứng
• Phần mềm
• Dữ liệu
• Các truyền thông giữa các máy tính của hệ thống
• Môi trường làm việc
• Con người
3. Các mối đe doạ đối với một hệ thống và các biện pháp ngăn chặn
Có 3 hình thức chủ yếu đe dọa đối với hệ thống:
• Phá hoại: kẻ thù phá hỏng thiết bị phần cứng hoặc phần mềm hoạt động trên
hệ thống.

Nhóm 01 – CNTT 2014_02

Page 3


• Sửa đổi: Tài sản của hệ thống bị sửa đổi trái phép. Điều này thường làm cho
hệ thống không làm đúng chức năng của nó. Chẳng hạn như thay đổi mật khẩu,
quyền người dùng trong hệ thống làm họ không thể truy cập vào hệ thống để
làm việc.
• Can thiệp: Tài sản bị truy cập bởi những người không có thẩm quyền.
Các truyền thông thực hiện trên hệ thống bị ngăn chặn, sửa đổi.
Các đe dọa đối với một hệ thống thông tin có thể đến từ nhiều nguồn và được
thực hiện bởi các đối tượng khác nhau. Chúng ta có thể chia thành 3 loại đối tượng
như sau: các đối tượng từ ngay bên trong hệ thống (insider), đây là những người có

quyền truy cập hợp pháp đối với hệ thống, những đối tượng bên ngoài hệ thống
(hacker, cracker), thường các đối tượng này tấn công qua những đường kết nối với
hệ thống như Internet chẳng hạn, và thứ ba là các phần mềm (chẳng hạn như spyware,
adware …) chạy trên hệ thống.
Các biện pháp ngăn chặn:
Thường có 3 biện pháp ngăn chặn:
• Điều khiển thông qua phần mềm: dựa vào các cơ chế an toàn bảo mật của hệ
thống nền (hệ điều hành), các thuật toán mật mã học .
• Điều khiển thông qua phần cứng: các cơ chế bảo mật, các thuật toán mật mã
học được cứng hóa để sử dụng
• Điều khiển thông qua các chính sách của tổ chức: ban hành các qui định của tổ
chức nhằm đảm bảo tính an toàn bảo mật của hệ thống.
4. Mục tiêu và nguyên tắc chung của an toàn bảo mật thông tin
Ba mục tiêu của an toàn bảo mật thông tin:
− Tính bí mật: Tài sản của hệ thống chỉ được truy cập bởi những người có thẩm
quyền. Các loại truy cập gồm có: đọc (reading), xem (viewing), in ấn (printing),
sử dụng chương trình, hoặc hiểu biết về sự tồn tại của một đối tượng trong tổ
chức.Tính bí mật có thể được bảo vệ nhờ việc kiểm soát truy cập (theo nhiều kiểu
khác nhau) hoặc nhờ các thuật toán mã hóa dữ liệu. Kiếm soát truy cập chỉ có thể
được thực hiện với các hệ thống phần cứng vật lý. Còn đối với các dữ liệu công cộng
thì thường phương pháp hiệu quả là các phương pháp của mật mã học.
− Tính toàn vẹn dữ liệu: tài sản của hệ thống chỉ được thay đổi bởi những người
có thẩm quyền.
− Tính sẵn dùng: tài sản luôn sẵn sàng được sử dụng bởi những người có thẩm
quyền. Hai nguyên tắc của an toàn bảo mật thông tin:
− Việc thẩm định về bảo mật phải là khó và cần tính tới tất cả các tình
huống, khả năng tấn công có thể được thực hiện.
− Tài sản được bảo vệ cho tới khi hết gía trị sử dụng hoặc hết ý nghĩa bí mật.

Nhóm 01 – CNTT 2014_02


Page 4


CHƯƠNG II. TỔNG QUAN VỀ MẬT MÃ HỌC
1. Khái niệm
Mật mã học bao gồm hai lĩnh vực: mã hóa (cryptography) và thám mã
(cryptanalysis-codebreaking).
Mã hóa là phương pháp để biến thông tin (phim ảnh, văn bản, hình ảnh...) từ định
dạng bình thường sang dạng thông tin không thể hiểu được nếu không có phương
tiện giải mã.
-

Bản rõ (plaintext or cleartext)

Chứa các xâu ký tự gốc, thông tin trong bản rõ là thông tin cần mã hoá để giữ bí mật.
-

Bản mã (ciphertext)

Chứa các ký tự sau khi đã được mã hoá, mà nội dung được giữ bí mật.
-

Mật mã học (Crytography)

Là nghệ thuật và khoa học để giữ thông tin được an toàn.
-

Sự mã hoá (Encryption)


Quá trình che dấu thông tin bằng phương pháp nào đó để làm ẩn nội dung bên trong
gọi là sự mã hoá.
-

Sự giải mã (Decryption)

Quá trình biến đổi trả lại bản mã bản thành bản rõ gọi là giải mã.
-

Quá trình giải mã và mã hóa

2. Thành phần của 1 hệ thống mật mã
- Hệ mật mã : là một hệ bao gồm 5 thành phần (P, C, K, E, D) thỏa mãn các tính
chất sau:
P (Plaintext) là tập hợp hữu hạn các bản rõ có thể.
C (Ciphertext) là tập hợp hữu hạn các bản mã có thể.

Nhóm 01 – CNTT 2014_02

Page 5


K (Key) là tập hợp các bản khoá có thể.
E (Encrytion) là tập hợp các qui tắc mã hoá có thể.
D (Decrytion) là tập hợp các qui tắc giải mã có thể.
Quá trình mã hóa được tiến hành bằng cách áp dụng hàm toán học E lên thông
tin P, vốn được biểu diễn dưới dạng số, để trở thành thông tin đã mã hóa C.
Quá trình giải mã được tiến hành ngược lại: áp dụng hàm D lên thông tin C để
được thông tin đã giải mã P.
3. Khóa

3.1. Độ dài khóa
Độ an toàn của thuật toán mã hoá cổ điển phụ thuộc vào hai điều đó là độ dài
của thuật toán và độ dài của khoá. Nhưng độ dài của khoá dễ bị lộ hơn. Giả sử rằng
độ dài của thuật toán là lý tưởng, khó khăn lớn lao này có thể đạt được trong thực
hành. Hoàn toàn có nghĩa là không có cách nào bẻ gãy được hệ thống mã hoá trừ khi
8

cố gắng thử với mỗi khoá. Nếu khoá dài 8 bits thì có 2 = 256 khoá có thể. Nếu khoá
56

dài 56 bits, thì có 2 khoá có thể. Giả sử rằng siêu máy tính có thể thực hiện 1 triệu
phép tính một giây, nó cũng sẽ cần tới 2000 năm để tìm ra khoá thích hợp. Nếu khoá
dài 64 bits, thì với máy tính tương tự cũng cần tới xấp xỉ 600,000 năm để tìm ra
khoá trong số 2

64

khoá có thể. Nếu khoá dài 128 bits, nó cần tới 10
10

25

năm , trong

25

khi vũ trụ của chúng ta chỉ tồn tại cỡ 10 năm. Như vậy với 10 năm có thể là đủ
dài. Trước khi bạn gửi đi phát minh hệ mã hoá với 8 Kbyte độ dài khoá, bạn nên nhớ
rằng một nửa khác cũng không kém phần quan trọng đó là thuật toán phải an toàn
nghĩa là không có cách nào bẻ gãy trừ khi tìm được khóa thích hợp. Điều này không

dễ dàng nhìn thấy được, hệ thống mã hoá nó như một nghệ thuật huyền ảo. Một
điểm quan trọng khác là độ an toàn của hệ thống mã hoá nên phụ thuộc vào khoá,
không nên phụ thuộc vào chi tiết của thuật toán. Nếu độ dài của hệ thống mã hoá mới
tin rằng trong thực tế kẻ tấn công không thể biết nội dung bên trong c ủ a thuật toán.
Nếu bạn tin rằng giữ bí mật nội dung của thuật toán, tận dụng độ an toàn của hệ
thống hơn là phân tích những lý thuyết sở hữu chung thì bạn đã nhầm. Và thật ngây
thơ hơn khi nghĩ rằng một ai đó không thể gỡ tung mã nguồn của bạn hoặc đảo ngược
lại thuật toán.
Giả sử rằng một vài kẻ thám mã có thể biết hết tất cả chi tiết về thuật toán của
bạn. Giả sử rằng họ có rất nhiều bản mã, như họ mong muốn. Giả sử họ có một khối
lượng bản rõ tấn công với rất nhiều dữ liệu cần thiết. Thậm chí giả sử rằng họ có
thể lựa chọn bản rõ tấn công. Nếu như hệ thống mã hoá của có thể dư thừa độ an
toàn trong tất cả mọi mặt, thì bạn đã có đủ độ an toàn bạn cần.

Nhóm 01 – CNTT 2014_02

Page 6


3.2. Quản lý khóa công khai
Trong thực tế, quản lý khoá là vấn đề khó nhất của an toàn hệ mã hoá.. Để
thiết kế an toàn thuật toán mã hoá là một việc là không phải dễ dàng nhưng để tạo và
lưu trữ khoá bí mật là một điều khó hơn. Kẻ thám mã thường tấn công cả hai hệ mã
hoá đối xứng và công khai thông qua hệ quản lý khoá của chúng.
Đối với hệ mã hoá công khai việc quản lý khoá dễ hơn đối với hệ mã hoá đối
xứng, nhưng nó có một vấn đề riêng duy nhất Mỗi người chỉ có một khoá công
khai, bất kể số người ở trên mạng là bao nhiêu.
3.3. Chứng nhận khoá công khai
Chứng nhận khoá công khai là xác định khoá thuộc về một ai đó, được quản lý
bởi một người đáng tin cậy. Chứng nhận để sử dụng vào việc cản trở sự cố gắng

thay thế một khoá này bằng một khoá khác.
Nó lưu trữ thông tin về Bob như tên, địa chỉ, ... và nó được viết bởi ai đó mà Eva
tin tưởng, người đó thường gọi là CA(certifying authority). Bằng cách xác nhận cả
khoá và thông tin về Bob. CA xác nhận thông tin về Bob là đúng và khoá công
khai thuộc quyền sở hữu của Bob. Eva kiểm tra lại các dấu hiệu và sau đó cô ấy có
thể sử dụng khoá công khai, sự an toàn cho Bob và không một ai khác biết.
3.4. Quản lý khóa phân phối
Trong một vài trường hợp, trung tâm quản lý khoá có thể không làm việc. Có
lẽ không có một CA (certifying authority) nào mà Eva và Bob tin tưởng. Có lẽ họ chỉ
tin tưởng bạn bè thân thiết hoặc họ không tin tưởng bất cứ ai. Quản lý khoá phân
phối, sử dụng trong những chương trình miền công khai, giải quyết vấn đề này với
người giới thiệu (introducers). Người giới thiệu là một trong những người dùng khác
của hệ thống anh ta là người nhận ra khoá công khai của bạn anh ta.
4. Các hệ mật mã
4.1. Hệ mật mã đối xứng
Thuật toán đối xứng hay còn gọi thuật toán mã hoá cổ điển. Thuật toán này còn
có nhiều tên gọi khác như thuật toán khoá bí mật, thuật toán khoá đơn giản, thuật
toán một khoá.
Là thuật toán mà tại đó khoá mã hoá có thể tính toán ra được từ khoá giải mã.
Trong rất nhiều trường hợp, khoá mã hoá và khoá giải mã là giống nhau.
Thuật toán này yêu cầu người gửi và người nhận phải thoả thuận một khoá trước
khi thông báo được gửi đi, và khoá này phải được cất giữ bí mật. Độ an toàn của
thuật toán này vẫn phụ thuộc vào khoá, nếu để lộ ra khoá này nghĩa là bất kỳ
người nào cũng có thể mã hoá và giải mã hệ thống mật mã.

Nhóm 01 – CNTT 2014_02

Page 7



Sự mã hoá và giải mã của thuật toán đối xứng biểu thị bởi :
E K( P ) = C
DK( C ) = P

K1có thể trùng K2,
hoặc K1 có thể tính toán từ K2
hoặc K2 có thể tính toán từ K1
Ưu điểm:
-

Xử lý nhanh

Nhược điểm:
Các phương pháp mã hoá cổ điển đòi hỏi người mã hoá và người giải mã
phải cùng chung m ộ t khoá. Khi đó khoá phải được giữ bí mật tuyệt đối, do vậy ta
dễ dàng xác định một khoá nếu biết khoá kia.
Hệ mã hoá đối xứng không bảo vệ được sự an toàn nếu có xác suất cao khoá
người gửi bị lộ. Trong hệ khoá phải được gửi đi trên kênh an toàn nếu kẻ địch tấn
công trên kênh này có thể phát hiện ra khoá.
Vấn đề quản lý và phân phối khoá là khó khăn và phức tạp khi sử dụng hệ
mã hoá cổ điển. Người gửi và người nhận luôn luôn thông nhất với nhau về vấn đề
khoá. Việc thay đổi khoá là rất khó và dễ bị lộ.
Khuynh hướng cung cấp khoá dài mà nó phải được thay đổi thường
xuyên cho mọi người trong khi vẫn duy trì cả tín h an toàn lẫn hiệu quả chi phí sẽ
cản trở rất nhiều tới việc phát triển hệ mật mã cổ điển.
Thuật toán đối xứng có thể được chia ra làm hai thể loại, mật mã luồng (stream
ciphers) và mật mã khối (block ciphers). Mật mã luồng mã hóa từng bit của thông điệp
trong khi mật mã khối gộp một số bit lại và mật mã hóa chúng như một đơn vị. Cỡ

Nhóm 01 – CNTT 2014_02


Page 8


khối được dùng thường là các khối 64 bit. Thuật toán tiêu chuẩn mã hóa tân
tiến (Advanced Encryption Standard), được NIST công nhận tháng 12 năm 2001, sử
dụng các khối gồm 128 bit.
4.2. Hệ mật mã phi đối xứng
Vào những năm 1970 Diffie và Hellman đã phát minh ra một hệ mã hoá mới được
gọi là hệ mã hoá phi đối xứng hay hệ mã hoá công khai.
Thuật toán mã hóa phi đối xứng khác hoàn toàn so với thuật toán mã hóa đối xứng.
Khóa của hệ mã phi đối xứng được gửi trên những kênh thông tin không an toàn.
Chúng được thiết kế sao cho khoá sử dụng vào việc mã ho á là khác so với
khoá giải mã. Hơn nữa khoá giải mã không thể tính toán được từ khoá mã hoá.
Chúng được gọi với tên hệ thống mã hoá công khai bởi vì khoá để mã hoá có thể
công khai, một người bất kỳ có thể sử dụng khoá công khai để mã hoá thông báo,
nhưng chỉ một vài người có đúng khoá giải mã thì mới có thể giải mã. Trong
nhiều hệ thống, khoá mã hoá gọi là khoá công khai (public key), khoá giải mã
thường được gọi là khoá riêng (private key).

K1 không trùng K2 hoặc
K2 không thể tính toán từ K1
Diffie và Hellman đã xác định rõ các điều kiện của một hệ mã hoá công khai như
sau :
Việc tính toán ra cặp khoá công khai KB và bí mật kB dựa trên cơ sở các điều
kiện ban đầu phải được thực hiện mộ t cách dễ dàng nghĩa là thực hiện trong thời
gian đa thức.
1. Người gửi A có được khoá công khai của người nhận B và có bản tin P cần
gửi đi thì có thể dễ dàng tạo ra được bản mã C.
C = EKB (P) = EB (P)

Công việc này cũng trong thời gian đa thức.

Nhóm 01 – CNTT 2014_02

Page 9


2. Người nhận B khi nhận được bản tin mã hóa C với khoá bí mật k B thì có thể
giải mã bản tin trong thời gian đa thức.
P = DkB (C) = DB[EB(M)]
3. Nếu kẻ địch biết khoá công khai KB cố gắng tính toán khoá bí mật thì khi đó
chúng phải đương đầu với trường hợp nan giải, trường hợp này đòi hỏi
nhiều yêu cầu không khả thi về thời gian.
4. Nếu kẻ địch biết được cặp (KB,C) và cố gắng tính toán ra bản rõ P thì giải
quyết bài toán khó với số phép thử là vô cùng lớn, do đó không khả thi.
Ưu điểm:
-

Tính an toàn cao.

-

Có thể gửi khóa trên các kênh không an toàn mà không sợ bị lộ khóa giải mã
Nhược điểm:

-

Tốc độ chậm

-


Dung lượng dùng cho việc lưu trữ khóa lớn

Một số thuật toán mã hóa phi đối xứng
•

Diffie-Hellman

•

DSS (Tiêu chuẩn chữ ký số)

•

ElGamal

•

Các kỹ thuật Mã hóa đường cong elliptic

•

Các kỹ thuật Thỏa thuật khóa chứng thực bằng mật khẩu

•

Hệ thống mật mã Paillier

•


Thuật toán mã hóa RSA (PKCS)

Mỗi hệ thống mã hóa có ưu nhược điểm riêng. Mã hóa đối xứng xử lí nhanh nhưng
độ an toàn không cao. Mã hóa bất đối xứng xử lí chậm hơn, nhưng độ an toàn và tính
thuân tiện trong quản lí khóa cao. Trong các ứng dụng mã hóa hiện tại, người ta
thường kết hợp các ưu điểm của cả hai loại mã hóa này.
5. Thám mã
Mục tiêu của thám mã (phá mã) là tìm những điểm yếu hoặc không an toàn trong
phương thức mật mã hóa. Thám mã có thể được thực hiện bởi những kẻ tấn công ác ý,
nhằm làm hỏng hệ thống; hoặc bởi những người thiết kế ra hệ thống (hoặc những
người khác) với ý định đánh giá độ an toàn của hệ thống.

Nhóm 01 – CNTT 2014_02

Page 10


Có rất nhiều loại hình tấn công thám mã, và chúng có thể được phân loại theo
nhiều cách khác nhau. Một trong những đặc điểm liên quan là những người tấn công
có thể biết và làm những gì để hiểu được thông tin bí mật. Ví dụ, những người thám
mã chỉ truy cập được bản mã hay không? Hay anh ta có biết hay đoán được một phần
nào đó của bản rõ? Hoặc thậm chí: Anh ta có chọn lựa các bản rõ ngẫu nhiên để mật
mã hóa? Các kịch bản này tương ứng với tấn công bản mã, tấn công biết bản rõ và tấn
công chọn lựa bản rõ.
Trong khi công việc thám mã thuần túy sử dụng các điểm yếu trong các thuật
toán mật mã hóa, những cuộc tấn công khác lại dựa trên sự thi hành, được biết đến như
là các tấn công kênh bên. Nếu người thám mã biết lượng thời gian mà thuật toán cần
để mã hóa một lượng bản rõ nào đó, anh ta có thể sử dụng phương thức tấn công thời
gian để phá mật mã. Người tấn công cũng có thể nghiên cứu các mẫu và độ dài của
thông điệp để rút ra các thông tin hữu ích cho việc phá mã; điều này được biết đến như

là thám mã lưu thông.
Nếu như hệ thống mật mã sử dụng khóa xuất phát từ mật khẩu, chúng có nguy
cơ bị tấn công kiểu duyệt toàn bộ (brute force), vì kích thước không đủ lớn cũng như
thiếu tính ngẫu nhiên của các mật khẩu. Đây là điểm yếu chung trong các hệ thống mật
mã. Đối với các ứng dụng mạng, giao thức thỏa thuận khóa chứng thực mật khẩu có
thể giảm đi một số các giới hạn của các mật khẩu. Đối với các ứng dụng độc lập, hoặc
là các biện pháp an toàn để lưu trữ các dữ liệu chứa mật khẩu và/hoặc các cụm từ kiểm
soát truy cập thông thường được gợi ý nên sử dụng.
Thám mã tuyến tính và Thám mã vi phân là các phương pháp chung cho mật
mã hóa khóa đối xứng. Khi mật mã hóa dựa vào các vấn đề toán học như độ khó NP
(Non Polynomial), giống như trong trường hợp của thuật toán khóa bất đối xứng, các
thuật toán như phân tích ra thừa số nguyên tố trở thành công cụ tiềm năng cho thám
mã.
Có 6 phương pháp chung để phân tích tấn công, dưới đây là danh sách theo
thứ tự khả năng của từng phương pháp. Mỗi phương pháp trong số chúng giả sử
rằng kẻ thám mã hoàn toàn có hiểu biết về thuật toán mã hoá được sử dụng.
Chỉ có bản mã. Trong trường hợp này, người phân tích chỉ có một vài bản tin
của bản mã, tất cả trong số chúng đều đã được mã hoá và cùng sử dụng chung một
thuật toán. Công việc của người phân tích là tìm lại được bản rõ của nhiều bản mã
có thể hoặc tốt hơn nữa là suy luận ra được khoá sử dụng mã hoá, và sử dụng để
giải mã những bản mã khác với cùng khoá này.

Giả thiết : C1 = Ek(P1), C2= Ek(P2), . . .Ci = Ek(Pi)
Suy luận : Mỗi P 1,P2, . . Pi, k hoặc thuật toán kết luận Pi+1 từ Ci+1 = Ek(Pi+1)

Nhóm 01 – CNTT 2014_02

Page 11



Biết bản rõ. Người phân tích không chỉ truy cập được một vài bản mã mặt khác còn
biết được bản rõ. Công việc là suy luận ra khoá để sử dụng giải mã hoặc thuật toán
giải mã để giải mã cho bất kỳ bản mã nào khác với cùng khoá như vậy.
Giả thiết : P1, C1 = Ek(P1), P2, C2= Ek(P2), . . . Pi, Ci = Ek(Pi)
Suy luận : Mỗi k hoặc thuật toán kết luận P i+1 từ Ci+1 = Ek(Pi+1)
Lựa chọn bản rõ. Người phân tích không chỉ truy cập được bản mã và k ế t h ợ p
b ả n r õ cho một vài bản tin, n h ư n g mặt khác lựa chọn bản rõ đã m ã hoá.
Phương pháp này tỏ ra có khả năng hơn phương pháp biết bản rõ bởi vì người
phân tích có thể chọn cụ thể khối bản rõ cho mã hoá, một điều khác có thể là sản
lượng thông tin về khoá nhiều hơn.
Giả thiết : P1, C1 = Ek(P1), P2, C2= Ek(P2), . . . Pi, Ci = Ek(Pi) tại đây người phân
tích chọn P 1, P2,. . . Pi
Suy luận : Mỗi k hoặc thuật toán kết luận P i+1 từ Ci+1 = Ek(Pi+1)
Mô phỏng lựa chọn bản rõ. Đây là trường hợp đặc biệt của lựa chọn bản rõ. Không
chỉ có thể lựa chọn bản rõ đã mã hoá, nhưng họ còn có thể sửa đổi sự lựa chọn cơ
bản kết quả của sự mã hoá lần trước. Trong trường lựa chọn bản mã người phân
tích có thể đã chọn một khối lớn bản rõ đã mã hoá, nhưng trong trường hợp này có
thể chọn một khối nhỏ hơn và chọn căn cứ khác trên kết quả của lần đầu tiên.
Lựa chọn bản mã. Người phân tích có thể chọn bản mã khác nhau đã được mã hoá
và truy cập bản rõ đã giải mã. Trong ví dụ khi một người phân tích có một hộp chứng
cớ xáo trộn không thể tự động giải mã, công việc là suy luận ra khoá.
Giả thiết : C1, P1 = Dk(C1), C2, P2= Dk(C2), . . . Ci, Pi = Dk(Ci)
Suy luận : k
Lựa chọn khoá. Đây không phải là một cách tấn công khi mà bạn đã có khoá. Nó
không phải là thực hành thám mã mà chỉ là sự giải mã thông thường, bạn chỉ cần lựa
chọn khoá cho phù hợp với bản mã.
Một điểm đáng chú ý khác là đa số các kỹ thuật thám mã đều dùng phương pháp
thống kê tần suất xuất hiện của các từ, các ký tự trong bản mã. Sau đó thực hiện việc
thử thay thế với các chữ cái có tần suất xuất hiện tương đồng trong ngôn ngữ tự
nhiên. Tại đây chúng ta chỉ xem xét đối với ngôn ngữ thông dụng nhất hiện nay

đó là tiếng Anh. Việc thống kê tần suất xuất hiện của các ký tự trong trường hợp
này được tiến hành dựa trên các bài báo, sách, tạp chí và các văn bản cùng với một
số loại khác …

Nhóm 01 – CNTT 2014_02

Page 12


Sau đây là bảng thống kê tần suất xuất hiện của 26 chữ cái trong bảng cái
tiếng Anh theo tài liệu của Beker và Piper.

Ký tự

Xác Suất

Ký tự

Xác suất

Ký tự

Xác suất

A
B

0.082
0.015


J
K

0.002
0.008

S
T

0.063
0.091

C

0.028

L

0.040

U

0.028

D

0.043

M


0.024

V

0.010

E

0.127

N

0.067

W

0.023

F

0.022

O

0.075

X

0.001


G

0.020

P

0.019

Y

0.020

H

0.061

Q

0.001

Z

0.001

I

0.070

R


0.060

Cùng với việc thống kê các tần suất của các ký tự trong tiếng Anh, việc thống
kê tần suất xuất hiện thường xuyên của các dãy gồm 2 hoặc 3 ký tự liên tiếp nhau cũng
có một vai trò quan trọng trong công việc thám mã. Sysu Deck đưa ra 30 bộ đôi xuất
hiện thường xuyên của tiếng Anh được sắp theo thứ tự giảm dần như sau:
Tính hữu dụng của các phép thống kê ký tự và các dãy ký tự được người phân
tích mã khai thác triệt để trong những lần thám mã. Khi thực hiện việc thám mã người
phân tích thống kê các ký tự trong bản mã, từ đó so sánh với bản thống kê mẫu và đưa
ra các ký tự phỏng đo án tương tự. Phương pháp này được sử dụng thường xuyên và
đem lại hiệu quả khá cao.

Nhóm 01 – CNTT 2014_02

Page 13


CHƯƠNG III. HỆ ELGAMAL
1. Giới thiệu
Hệ Elgamal là 1 hệ mật mã công khai được Taher Elgamal (nhà mật mã học
người Ai Cập) đưa ra vào năm 1985.
Hệ Elgamal dựa trên bài toán logarit rời rạc. Tính an toàn của nó tùy thuộc vào
độ phức tạp của bài toán logarit.
-

Hệ Elgamal là 1 biến thể của sơ đồ phân phối khóa Diffie – Hellman.

-

So với RSA, hệ Elgamal không có nhiều rắc rối về vấn đề bản quyền sử dụng.


2. Mã hóa và giải mã hệ Elgamal
Ban đầu người ta sẽ chọn một số nguyên tố lớn p và hai số nguyên tuỳ ý nhỏ hơn
*
p là a (a là 1 phần tử nguyên thủy củ a Z P) và x (x là của người nhận xsau đó tính:
x
y = a mod p
Để mã hóa một thông điệp M (là một số nguyên trên ZP) thành bản mã C
người gửi chọn một số ngẫu nhiên k nhỏ hơn p và tính khóa mã hóa K:
k
K = y mod p=ax.k mod p
Sau đó tính cặp bản mã:
k
• C1 = a mod p
• C2 = (K.M) mod p
Và gửi bản mã C = (C1, C2) đi (chú ý là sau đó k sẽ bị huỷ).
Để giải mã thông điệp đầu tiên ta cần tính lại khóa mã hóa thông điệp K:
K = C1

x

mod p = a

k.x

mod p

Sau đó tính M bằng cách giải phương trình sau đây:
M = (C2 . K-1) mod p

Việc giải mã bao gồm việc tính lại khóa tạm thời K (rất giống với mô hình của Diffie
- Hellman đưa ra). Khóa công khai của hệ mã là (p, a, y), khóa bí mật là x
Vi dụ: Cho hệ mã El Gamal có P = 97, a = 5, x = 58.
Tìm khóa của hệ mã trên.

Nhóm 01 – CNTT 2014_02

Page 14


Mã hóa bản rõ M = 3 với k được chọn bằng 36.
Mã hóa
Trước hết ta tính y = 5
KS = (58)

58

mod 97 = 44, từ đó suy ra KP = (p, a, y) = (97, 5, 44) và
36

Để mã hóa thông điệp M = 3 ta tính khóa K = 44

36

C1 = 5

mod 97 = 75 sau đó tính:

mod 97 = 50.

C2 = 75.3 mod 97 = 31.
Vậy bản mã được gửi đi sẽ là C = (50, 31).
Giải mã
Ta tính lại K
x
58
K= C1 mod p = 50 mod 97 = 75.
Tìm K-1 trên Z97 là 22.
Bản rõ M:
M = (K-1.C2) mod p = (22.31) mod 97 = 3.
Trong đó:
P (Plaintext) là tập hợp hữu hạn các bản rõ có thể. (P)
C (Ciphertext) là tập hợp hữu hạn các bản mã.(C1,C2)
K (Key) là tập hợp các bản khoá có thể(KP, KS)
3. Ưu, nhược điểm
-

Ưu điểm:

+ Miễn phí.
+ Độ phức tạp của bài toán logarit lớn nên độ an toàn cao (tương đương RSA).
+ Bản mã phụ thuộc vào bản rõ và giá trị ngẫu nhiên nên từ 1 bản rõ ta có thể có nhiều
bản mã khác nhau.
-

Nhược điểm:

+ Tốc độ chậm (do phải xử lý số nguyên lớn)
+ Dung lượng bộ nhớ dành cho việc lưu trữ khóa cũng lớn.
+ Độ lớn của bản mã lớn gấp đôi so với bản rõ.

Nhóm 01 – CNTT 2014_02

Page 15


+ Phải có cơ sở dữ liệu các số nguyên tố và các phần tử dữ liệu nguyên thủy liên quan
khi triển khai thực tế.
4. Thám mã hệ Elgamal
Để thám mã hệ Elgamal, ta cần phải giải bài toán Logarit rời rạc. Chúng ta có 2
thuật toán để giải bài toán Logarit rời rạc là:
-

Thuật toán Shank

-

Thuật toán Pohlig – Hellman

Thuật toán Shank
Thuật toán này có tên gọi khác là thuật toán thời gian – bộ nhớ. Tư tưởng của thuật
toán là nếu ta có đủ bộ nhớ thì có thể sử dụng bộ nhớ đó để giảm thời gian thực hiện
của thuật toán.
*
Input: Số nguyên tố p, phầ n tử nguyên thủ y a củ a Z ,p số nguyên y.
x
Output: cầ n tìm x sao cho a mod p = y.
Thuật toán:
Gọi m = [(p-1)

1/2

Bước 1: Tính a

] (lấ y phầ n nguyên).

mj

mod p vớ i 0 ≤ j ≤ m-1.

Bước 2: Sắp xếp các cặp (j, a

mj

mod p) theo a

mj

mod p và lưu và o danh sá ch L1.

i
Bước 3: Tính ya mod p vớ i 0 ≤ i ≤ m-1.
-i
mj
Bước 4: Sắp xếp các cặp (i, ya mod p) theo a mod p và lưu và o danh sá ch L2.
Bước 5: Tìm trong hai danh sách L 1 và L2 xem có tồn tại cặp (j, a

mj

mod p) và (i,

-i
mj
i
ya mod p) nào mà a mod p = ya mod p (tọa độ thứ hai của hai cặp bằng nhau).
mj

Lưu ý: Vì a

i
mj-i
= ya => a
= y nên bước 5 luôn thành công.

Bước 6: x = (mj + i) mod (p-1). Kế t quả nà y có thể kiể m chứng từ công thức a
i
mj- i
mod p = ya mod p => a
mod p = y mod p => x = (mj - i) mod (p-1).
Ví dụ:
Với bài toán trên người thám mã chỉ có khóa công khai

Nhóm 01 – CNTT 2014_02

Page 16

mj


KP = (p, a, y) = (97, 5, 44)
m = [(p-1)1/2]= [(97-1)1/2]= 10

Bước 1: Tính a

mj

mod p vớ i 0 ≤ j ≤ m-1.

Bước 2: Sắp xếp các cặp (j, a

mj

mod p) theo a

j(0 ≤ j ≤ m-1)

mj

5

mod p và lưu và o danh sá ch L1.

10.j

0
1
2
3
4
5
6
7

8
9

mod 97(a
1
53
93
79
16
72
33
3
62
85

mj

mod p)

i
Bước 3: Tính ya mod p vớ i 0 ≤ i ≤ m-1.
-i
mj
Bước 4: Sắp xếp các cặp (i, ya mod p) theo a mod p và lưu và o danh sá ch L2.

i(0 ≤ i ≤ m-1)
0
1
2
3

4
5
6
7
8
9

i
i
44.5 mod 97(ya mod p)
44
26
33
68
49
51
61
14
70
59

Bước 5: Tìm trong hai danh sách L1 và L2 xem có tồn tại cặp (j, a

mj

mod p) và (i,

-i
mj
i

ya mod p) nào mà a mod p = ya mod p (tọa độ thứ hai của hai cặp bằng nhau).

Nhóm 01 – CNTT 2014_02

Page 17


Dựa vào 2 bảng danh sách L1 và thì có khi j =6 và i=2 thì a
33.

mj

i
mod p= ya mod p=

Bước 6: x = (mj + i) mod (p-1). Kế t quả nà y có thể kiể m chứng từ công thức a
i
mj- i
mod p = ya mod p => a
mod p = y mod p => x = (mj - i) mod (p-1).

mj

Vậy ta có x=(10 x 6 - 2) mod (97-1)= 58.(So sánh với kết quả bài toán giải mã thì x
cũng bằng 58).
5. Đánh giá độ an toàn
5.1. Bài toán Logarit rời rạc
Logarit rời rạc là sự tiếp nối của phép tính lôgarit trên trường số thực vào các nhóm
hữu hạn. Ta nhắc lại rằng với hai số thực x, y và cơ số a>0, a≠1,nếu ax=y thì x được
gọi là lôgarit cơ số a của y, ký hiệu x= logay.

Logarit rời rạc là bài toán khó (chưa biết một thuật toán hiệu quả nào), trong khi
bài toán ngược luỹ thừa rời rạc lại không khó (có thể sử dụng thuật toán bình phương
và nhân).
Ví dụ:
Cho p là một số nguyên tố. Xét nhóm nhân các số nguyên modulo
p:

với phép nhân modulo p.

Nếu ta tính luỹ thừa bậc k của một số trong nhóm rồi rút gọn theo modulo p thì ta được
một số trong nhóm đó. Quá trình này được gọi là luỹ thừa rời rạc modulo p. Chẳng hạn
với p=17, lấy a=3, k=4 ta có
.
Lôgarit rời rạc là phép tính ngược lại:
Biết :

hãy tìm k.

5.2. Độ an toàn
Hệ Elgamal dựa trên bài toán logarit rời rạc. Tính an toàn của nó tùy thuộc vào
độ phức tạp của bài toán logarit.
Trong bài toán về hệ Elgamal:
+

p là số nguyên tố, a là phần tử nguyên thủy của Z*p. p và a là cố định.

+

Bài toán logarit rời rạc có thể được phát biểu như sau: Tìm 1 số mũ x duy nhất,
x

0<=x<=p-2 sao cho a = y (mod p), với y thuộc Z*p cho trước.

Nhóm 01 – CNTT 2014_02

Page 18


+
Bài toán có thể giải được bởi phương pháp vét cạn( tức là duyệt tất cả phần từ
x) để tìm x thỏa mãn.
Bài toán có độ phức tạp là: O(p)(bỏ qua thừa số logarit). Vấn đề đặt ra là nếu p lớn, rất
lớn thì để thực hiện phương pháp này cần thời gian rất lớn. Suy ra không khả thi.
Xét thuật toán Shank để thám mã hệ mã hóa Elgamal
+
Người thám mã chỉ có khóa công khai (p,a,y).
+
Bài toán logarit rời rạc cũng được phát biểu như sau: Tìm 1 số mũ x duy nhất,
x
0<=x<=p-2 sao cho a = y (mod p), với y thuộc Z*p cho trước.
1/2
1/2
+
Độ phức tạp của bài toán là O([(p-1) ) và bộ nhớ O([(p-1) )(bỏ qua thừa số
logarit), giảm rất nhiều so với phương pháp vét cạn.
+
Chúng ta cần tính các phần tử thuộc 2 danh sách L1,L2 đều là các phép toán lũy
thừa phụ thuộc vào i,j. I và j lại phụ thuộc vào m nên ta nhận thấy bài toán chỉ áp dụng
với những trường hợp p nhỏ.
Đánh giá độ an toàn của hệ mã hóa Elgamal:
- Hệ mã hóa Elgamal áp dụng bài toán logarit rời rạc chính vì vậy độ an toàn của

hệ mã hóa là rất lớn vì bài toán logarit rời rạc chưa có phương pháp hiệu quả để
tính.
- Với 1 số p đủ lớn, thuật toán mã hóa Elgamal không có phương pháp thám mã
hiệu quả.

Nhóm 01 – CNTT 2014_02

Page 19


CHƯƠNG IV. CÀI ĐẶT HỆ MÃ HÓA ELGAMAL
1. Chuẩn bị
Công cụ:
C-Free 5
Hệ điều hành:
Windows 7
2. Lập trình
2.1. Thuật toán Ơclit mở rộng (tìm phần tử nghịch đảo)
a) Thuật toán
Input: N và a, GCD(a,N)=1
Output: a-1 ∈ ZN
Begin
g0=N, g1=a, v0=0, v1=1;
do{
y=g0/g1
temp1=g0 mod g1;
g0=g1;
g1=temp1;
temp2=v0-(v1*y);
v0=v1;

v1=temp2;
}
while (temp1!=0);
v1=v0;
if (v1<0)
v1=n+v1;
return v1;
End.
b) Ví dụ
Cho N=26, a=7, tìm a-1 ∈ ZN
g
v
0
26
0
1
7
1
5
-3
2
4
1
-11
0
-1
v1=-11<0 nên a =N+v1=26-11=15

Nhóm 01 – CNTT 2014_02

Page 20

y
3
1
2
2


c) Code chương trình
unsigned ptnd(unsigned n,unsigned a)
{
unsigned g0,g1,v0,v1,y,temp1,temp2;
v0=0;
v1=1;
g0=n;
g1=a;
do{
y=g0/g1;
temp1=g0 % g1;
g0=g1;
g1=temp1;
temp2=v0-(v1*y);
v0=v1;
v1=temp2;
}
while (temp1!=0);
v1=v0;
if (v1<0)
v1=n+v1;

return v1;
}

2.2. Thuật toán lũy thừa nhanh
a) Thuật toán
Input: a,m,N
Output: am mod N=?
Begin
Phân tích m thành dạng nhị phân m = m0m1…mk
kq=1; tam=1;
for i=0 to k
if i=0
tam=a;
else
tam=(tam*tam) mod N;
if (mk-i=1)
kq=(kq*tam) mod N;

Nhóm 01 – CNTT 2014_02

Page 21


return kq;
End.
b) Ví dụ
Cho N=15, a=3,m=12. Tính am mod N
Viết số mũ m=12 thành dạng nhị phân: m=12=1100
Bước
m

tam=1
1
0
tam=a=3
2
0
32 mod 15=9
3
1
92 mod 15=6
4
1
62 mod 15=6
Vậy: am mod N=312 mod 15=6

kq=1
1
1
(1*6) mod 15=6
(6*6) mod 15=6

c) Code chương trình
unsigned sodu(unsigned a,unsigned m,unsigned n)//Thuat toan luy thua nhanh
{
unsigned t,tam,kq,dem;
dem=0;
kq=1;
do
{
t=m%2;

if(dem==0)
tam=a;
else
tam=(tam*tam)%n;
if (t==1)
kq=(kq*tam)%n;
m=m/2;
dem++;
}
while(m>0);
return kq;
}
2.3. Kiểm tra số nguyên tố
a) Giải thuật
Input: a là số nguyên dương >1
Output: kết luận a là số nguyên tố hay không.
Begin
For i=2 to a/2 do

Nhóm 01 – CNTT 2014_02

Page 22


If a mod i=0 then
Kết luận a không là số nguyên tố;
Nếu a không chia hết cho bất kì số nào từ 2 đến a/2 thì kết luận: a là số nguyên
tố
End
b) Code chương trình

unsigned snt(unsigned a)//kiem tra so nguyen to
{
for (unsigned i=2;iif (a%i==0)
{ return 0; break;}
return 1;
}
2.4. Tạo khóa công khai
a) Thuật toán
input: p,a,x
output: khóa công khai Kp
Begin
Nhập số nguyên tố p;
Nhập số nguyên a (a là phần tử nguyên thủy của Z*p, aNhập mã bí mật x;
x
y = a mod p;
khóa công khai là: y=(p,a,y);
khóa bí mật là: x
End.
b) code chương trình
void CreatKey()
{
cout<<"nhap so nguyen to p: ";
do
cin>>p;
while (snt(p)==0 || p<2);

Nhóm 01 – CNTT 2014_02

Page 23


cout<<"nhap so nguyen a (nho hon p): ";
do
cin>>a;
while (a>=p || a<1);

cout<<"nhap ma cua nguoi nhan x (nho hon p): ";
do
cin>>x;
while (x>=p || x<1);
y=sodu(a,x,p);
cout<cout<}
2.5. Mã hóa Elgamal
a) Thuật toán
Input: khóa công khai (p,a,y), bản rõ m
Output: bản mã C=(C1,C2)
Begin
sinh k ngẫu nhiên;
k
K = y mod p;
k
C1 = a mod p;
C2 = (K.m) mod p;
bản mã C = (C1, C2);
End.
b) Code chương trình

void Elgamal(unsigned p, unsigned a, unsigned y, unsigned m)
{
unsigned k,K,c1,c2;
k=rand()% p;

Nhóm 01 – CNTT 2014_02

Page 24


K=sodu(y,k,p);
c1=sodu(a,k,p);
c2=(m*K)% p;
cout<}
c) Cách nhập
Elgamal(p,a,y,m)
Trong đó:
p: số nguyên tố lớn
a: số nguyên nhỏ hơn p (a là phần tử nguyên thủy của Z*p)
x:
d) Vi dụ
Elgamal(97,5,44,3)
Kết quả: Ban ma la: 50 – 31 //giả sử k ngẫu nhiên là 36
2.6. Giải mã Elgamal
a) Thuật toán
Input: C1, C2, p, x
Output: bản rõ m
(C1,C2: bản mã nhận được, p: số nguyên tố lớn, x: mã người nhận, m: bản rõ sau giải
mã)

Begin
K = C1

x

mod p = a

k.x

mod p

M = (C2 . K-1) mod p
Đưa ra bản rõ M
End.
b) Code chương trình
void Decrypt_Elgamal(unsigned c1, unsigned c2,unsigned x,unsigned p)
{
unsigned K,h,m;
K=sodu(c1,x,p);
h=ptnd(p,K);
m=(h*c2)% p;
cout<Nhóm 01 – CNTT 2014_02

Page 25