Mã công khai và quản lý khóa

Mã khoá công khai

Khoá công khai ra đời vào đầu những năm 1970. Có thể nói đây là bước tiến quan trọng nhất trong lịch sử 3000 năm mã hoá. Ở đây người ta sử dụng 2 khoá: một khoá riêng và một khoá công khai. Hai khoá này khác nhau, không đối xứng với nhau, do đó mã khoá công khai, còn được gọi là mã không đối xứng. Người ta đã ứng dụng một cách thông minh các kết quả của lý thuyết số về hàm số.

Khoá công khai ra đời hỗ trợ thêm để giải quyết một số bài toán an toàn, chứ không phải thay thế khoá riêng. Cả hai khoá cùng tồn tại, phát triển và bổ sung cho nhau.

Khoá công khai/hai khoá/không đối xừng bao gồm việc sử dụng 2 khoá:

• Khoá công khai, mà mọi người đều biết, được dùng để mã hoá mẩu tin và kiểm chứng chữ ký.
• Khoá riêng, chỉ người nhận biết, đề giải mã bản tin hoặc để tạo chữ ký.
• Là không đối xứng vì những người mã hoá và kiểm chứng chữ ký không thể giải mã hoặc tạo chữ ký.

Sơ đồ mã khóa công khai

Tại sao lại phải dùng mã khoá công khai?

Người ta muốn giải quyết hai vấn đề sau về khoá nảy sinh trong thực tế:

• Phân phối khoá - làm sao có thể phân phối khóa an toàn mà không cần trung tâm phân phối khoá tin cậy
• Chữ ký điện tử - làm sao có thể kiểm chứng được rằng mẩu tin gửi đến nguyên vẹn từ đúng người đứng tên gửi.

Nếu chỉ dùng khoá đối xứng, thì không có giải pháp cho hai bài toán trên. Mã khoá công khai được phát minh trước công chúng bởi hai nhà bác học Whitfield Diffie & Martin Hellman ở trường Đại học Stanford vào năm 1976. Tuy nhiên khái niệm ban đầu về nó đã được biết đến sớm hơn bởi cộng đồng các nhà khoa học.

Các đặc trưng của khoá công khai

Các thuật toán khoá công khai dùng 2 khoá với các đặc trưng sau:

• Không có khả năng tính toán để tìm khoá giải mã nếu chỉ biết thuật toán mã và khoá dùng để mã.
• Có thể dễ dàng mã hoá hoặc giải mã mẩu tin nếu biết khoá tương ứng
• Trong một số sơ đồ: một khoá bất kỳ trong hai khoá có thể dùng để mã, còn khoá kia dùng để giải mã. Chúng có vai trò đối ngược nhau.

Ứng dụng khoá công khai

Có thể phân loại các ứng dụng của khoá công khai thành 3 loại khác nhau:

• Mã/giải mã – cung cấp bảo mật. Đây là ứng dụng bảo mật truyền thống giống như ta vẫn thường dùng với khoá đối xứng.
• Chữ ký điện tử - cung cấp xác thực. Một trong các ứng dụng mới của khoá công khai mà khoá đối xứng không thể thực hiện được, đó là khoá công khai có đủ cơ sở để xác nhận người gửi và có thể là một lựa chọn để tạo chữ ký điện tử của người gửi.

Một số thuật toán mã công khai phù hợp với mọi ứng dụng, còn một số khác chuyên dùng cho ứng dụng cụ thể.

Tính an toàn của các sơ đồ khoá công khai

Cũng giống như khoá riêng việc tìm kiếm vét cạn luôn luôn có thể, tức là khi biết một trong hai khoá và thuật toán mã hoá về nguyên tắc ta có thể dò tìm khoá thứ hai bằng cách tính toán các giá trị liên quan. Nói chung khối lượng cần tính toán là rất lớn do độ phức tạp của bài toán xác định khoá. Nếu khoá sử dụng là rất lớn cỡ hơn 512 bit, thì hầu như bài toán tìm khoá thứ hai là không khả thi, không thể thực hiện được trong thời gian có nghĩa, cho dù nguồn lực có thể rất lớn.

Tính an toàn dựa trên sự khác biệt đủ lớn giữa các bài toán dễ là mã/giải mã khi biết khoá và bài toán khó là thám mã khi không biết khoá tương ứng. Vì bài toán thám mã nằm trong lớp các bài toán khó tổng quát hơn đã được biết đến và về mặt lý thuyết đã được chứng minh là nó rất khó có thể thực hiện trên thực tế. Bởi vì nó đòi hỏi sử dụng số rất lớn, nên số phép toán cần thực hiện là rất nhiều. Đây là ý tưởng chính để tạo nên một mã công khai. Ta tìm kiếm các bài toán mà nếu biết thông tin mật nào đó được che dấu thì nó rất dễ thực hiện, còn nếu không thì nó thuộc lớp bài toán rất khó giải, hầu như không thể giải trên thực tế.

Mã công khai thường chậm hơn khá nhiều so với mã đối xứng, nên nó thường được dùng mã những thông tin nhỏ quan trọng.

Khởi tạo khoá RSA

- Mỗi người sử dụng tạo một cặp khoá công khai – riêng như sau:

- Chọn ngẫu nhiên 2 số nguyên tố lớn p và q

- Tính số làm modulo của hệ thống: N = p.q

o Ta đã biết ФN)=(p-1)(q-1)

o Và có thể dùng Định lý Trung Hoa để giảm bớt tính toán

- Chọn ngẫu nhiên khoá mã e

o Trong đó 1<e< ФN), gcd(e,Ф(N))=1

- Giải phương trình sau để tìm khoá giải mã d sao cho

o e.d=1 mod Ф(N) với 0≤d≤ Ф(N)

- In khoá mã công khai KU={e,N}

- Giữ khoá riêng bí mật KR={d,p,q}

Sử dụng RSA

• Để tìm mã hóa mẩu tin,người gửi:

o lấy khoá công khai của người nhận KU={e,N}

o Tính C= Me size 12{M rSup { size 8{e} } } {} mod N, trong đó 0≤M<N

• Để giải mã hoá bản mã, người sở hữu nhận:

o Sử dụng khóa riêng KR={d,p,q}

o Tính M= Cd size 12{C rSup { size 8{d} } } {} mod N

• Lưu ý rằng bản tin M < N, do đó khi cần chia khối bản rõ.

Cơ sở của RSA

• Theo Định lý Ole

o trong đó gcd(a,N)=1

o Ta có N=p.q

o Ф(N)=(p-1)(q-1)

o e.d=1 mod Ф(N)

o e.d=1+k.Ф(N) đối với một giá trị k nào đó.

Suy ra:

Lũy thừa

Trong các bài toán mã hoá công khai, chúng ta sử dụng nhiều phép toán lũy thừa với số mũ lớn. Như vậy cần có thuật toán nhanh hiệu quả đối với phép toán này. Trước hết ta phân tích số mũ theo cơ số 2, xét biểu diễn nhị phân của số mũ, sau đó sử dụng thuật toán bình phương và nhân. Khái niệm được dựa trên phép lặp cơ sở bình phương và nhân để nhận đựơc kết quả mong muốn. Độ phức tạp của thuật toán là O(log2 n) phép nhân đối với số mũ n.

Mã hiệu quả:

Mã sử dụng lũy thừa của khoá công khai e, nếu giá trị của e nhỏ thì tính toán sẽ nhanh, nhưng dễ bị tấn công. Thường chọn e nhỏ hơn hoặc bằng 65537 ( 216 size 12{2 rSup { size 8{"16"} } } {}-1), tức là độ dài khoá công khai là 16 bit. Chẳng hạn trong ví dụ trên ta có thể lựa chọn e = 23 hoặc e = 7.

Ta có thể tính mã hoá nhanh, nếu biết n=pq và sử dụng Định lý phần dư Trung Hoa với mẩu tin M theo các Modulo p và q khác nhau. Nếu khoá công khai e cố định thì cần tin tưởng rằng khi chọn n ta luôn có gcd(e,Ф(n)) = 1. Loại bỏ mọi p, q mà làm cho Ф(n) không nguyên tố cùng nhau với e.

Giải mã hiệu quả:

Có thể sử dụng Định lý phần dư Trung Hoa để tính theo mod p và q, sau đó kết hợp lại để tìm ra bản rõ. Vì ở đây người sử dụng khoá riêng biết được p và q, do đó có thể sử dụng kỹ thuật này. Nếu sử dụng định lý phần dư Trung Hoa để giải mã thì hiệu quả là nhanh gấp 4 lần so với giải mã tính trực tiếp.

Sinh khoá RSA

Người sử dụng RSA cần phải xác định ngẫu nhiên 2 số nguyên tố rất lớn, thông thường khoảng 512 bit. Do đó việc sinh ra ngẫu nhiên p, q và kiểm tra xác suất tính nguyên tố của chúng có nhiều giải pháp khác nhau với độ tin cậy cao. Sau khi chọn được một khoá e hoặc d nguyên tố cùng nhau với Ф(n), dễ dàng tính được khoá kia chính là số nghịch đảo của nó qua thuật toán Euclide mở rộng.

An toàn của RSA

Trên thực té có nhiều cách tấn công khác nhau đối với mã công khai RSA như sau:

Tìm kiếm khoá bằng phương pháp vét cạn, phương pháp này không khả thi với kích thước đủ lớn của các số hoặc tấn công bằng toán học dựa vào độ khó việc tính Ф(n) bằng cách phân tích n thành hai số nguyên tố p và q hoặc tìm cách tính trực tiếp Ф(n). Trong quá trình nghiên cứu việc thám mã người ta đề xuất kiểu tấn công thời gian trong khi giải mã, tức là căn cứ vào tốc độ mã hoá và giải mã các mẩu tin cho trước mà phán đoán các thông tin về khoá. Cuối cùng có những nghiên cứu tấn công RSA với điều kiện biết trước bản mã cho trước. Cu thể như sau:

Bài toán phân tích

• Tấn công toán học có 3 dạng:

o Phân tích N = p.q, sau đó tính Ф(N) và d

o Tìm n trực tiếp Ф(N) và tính d

o Tìm d trực tiếp

- Hiện tại tin rằng tất cả đều tương đương với bài toán phân tích

o Có các bước tiến chậm theo thời gian

o Hiện tại cho rằng RSA 1024 hoặc 2048 là an toàn

- Tấn công thời gian

o Phát triển vào giữa năm 1990

o Paul Kocher chỉ ra rằng kẻ thám mã có thể xác định được khoá riêng nếu theo dõi thời gian máy tính cần để giải mã các bản tin.

o Tấn công thời gian không chỉ áp dụng cho RSA, mà cả với các hệ mã công khai khác.

o Tấn công thời gian giống như kẻ cướp đoán số điện thọai bằng cách quan sát một người nào đó trong bao lâu chuyển quay điện thoại từ số này sang số khác.

- Tấn công bản mã chọn trước

o RSA có điểm yếu với tấn công bản mã chọn trước

o Kẻ tấn công chọn bản mã và đoán bản rõ được giải mã

o Chọn bản mã để khám phá RSA cung cấp thông tin để thám mã

o Có thể tính với bộ đệm ngãu nhiên của bản rõ

o Hoặc sử dụng bộ đệm mã hoá phản xứng.

Phân phối khoá

Mã khoá công khai giúp giải bài toán phân phối khoá, đây là nhu cầu cấp bách cần phải tạo ra một cơ chế chia sẻ khoá trong môi trường thường xuyên trao đổi thông tin và thường xuyên thay đổi khoá. Nó bao gồm hai khía cạnh sau:

o Phân phối khoá một cách công khai nhưng đảm bảo được bí mật.

o Sử dụng mã khoá công khai để phân phối khoá mật (còn khoá mật dùng để mã hoá thông tin).

Phân phối khoá công khai có thể xem xét để được sử dụng vào một trong những việc sau:

o Thông báo công khai khoá của người sử dụng.

o Thư mục truy cập công cộng cho mọi người.

o Chủ quyền khoá công khai, người nắm giữ khoá công khai.

o Chứng nhận khoá công khai, khoá công khai của người sử dụng được nơi có thẩm quyền chứng nhận.

Thông báo công khai

- Người dùng phân phối khoá công khai cho người nhận hoặc thông báo rộng rãi cho cộng đồng. Chẳng hạn như người sử dụng có thể tự bổ sung khoá PGP vào thư điện

tử hoặc gửi cho nhóm chia sẻ tin hoặc một danh sách thư điện tử.

- Điểm yếu chính của thông báo công khai là mạo danh: một người nào đó có thể tạo khoá và tuyên bố mình là một người khác và gửi thông báo cho mọi người khác. Cho đến khi giả mạo bị phát hiện thì kẻ mạo danh đã có thể lừa trong vai trò người khác

Thư mục truy cập công cộng

- Dùng thư mục truy cập công cộng có thể đạt được tính an toàn cao hơn bằng cách

đăng ký khoá với thư mục công cộng để đăng tải và chia sẻ cho mọi người.

- Thư mục cần được đảm bảo tin cậy với các tính chất sau:

o Chứa việc nhập tên và khoá công khai

o Người dùng đăng ký mật với Thư mục

o Người dùng có thể thay khoá bất cứ lúc nào

o Thư mục được in định kỳ

o Thư mục có thể truy cập qua mạng

- Mô hình trên vẫn còn có các lỗ hổng để kẻ xâm nhập sửa hoặc giả mạo khi vào hệ thống.

Chủ quyền khoá công khai

Đây là bước cải thiện tính an toàn bằng kiểm soát chặt chẽ tập trung việc phân phối khoá

từ Thư mục. Nó bao gồm các tính chất của một Thư mục như đã nêu ở phần trước và đòi hỏi người dùng biết khoá công khai của Thư mục đó. Sau đó người dùng nhận được bất

kỳ khoá công khai mong muốn nào một cách an toàn, bằng cách truy cập thời gian thực đến Thư mục khi cần đến khoá. Tuy nhiên yêu cầu truy cập thời gian thực là một nhược điểm của cách phân phối khoá này. Cụ thể trong kịch bản sau hai người sử dụng chia sẻ khoá công khai của mình cho nhau thông qua việc sử dụng khoá công khai của .Chủ quyền để nhận được khoá công khai của đối tác và trao đổi qua lại để khẳng định người này đã biết thông tin của người kia.

Chứng nhận khoá công khai

Chứng nhận cho phép trao đổi khoá không cần truy cập thời gian thực đến Chủ quyền thư mục khoá công khai. Để làm việc đó chứng nhận trói danh tính của người sử dụng với khoá công khai của anh ta và “đóng dấu và giấy chứng nhận” đó để tránh giả mạo. Các thông tin đi kèm thông thường là chu kỳ kiểm định, quyền sử dụng, thời hạn,…

Nội dung trên được ký bởi khoá riêng tin cậy của Chủ quyền chứng nhận (CA, Certificate Authority). Do khoá công khai của CA được thông báo rộng rãi, nên chứng nhận đó có thể được kiểm chứng bới một người nào đó biết khoá công khai của Chủ quyền chứng nhận.

Phân phối công khai các khoá mật

Nói chung có thể sử dụng các phương pháp trên để nhận được khoá công khai của người định trao đổi thông tin. Khoá công khai đó dùng cho mục đích mã hoá, giải mã hoặc xác nhận thông tin là của đối tác. Nhưng các thuật toán khoá công khai chậm, nên giá để bảo mật thông tin là đắt. Do đó thông thường dùng khoá đối xứng để mã hoá và giải mã nội dung bản tin, mà còn được gọi là khoá phiên hay khóa kỳ (section key). Có một số cách thỏa thuận khoá phiên phù hợp giữa hai người sư dụng.

Phân phối khoá mật đơn giản

• Được đề xuất bởi Merkle vào năm 1979

o A tạo ra một cặp khoá công khai mới tạm thời

o A gửi B một khoá công khai và danh tính của họ

o B tạo ra khoá phiên và gửi nó cho A sử dụng khoá công khai được cung cấp

o A giải mã khoá phiên và cả hai cùng dùng nó.

• Vấn đề nằm ở chỗ, kẻ thù có thể ngăn hoặc đóng giả cả hai bên của thủ tục

Nếu có khoá công khai thì khoá phiên được trao đổi an toàn

Trao đổi khoá hỗn hợp:

Ta có thể kết hợp sử dụng Trung tâm phân phối khoá để phân phối khoá phiên như trên mô hình máy chủ của IBM. Trung tâm chia sẻ khoá chính (master key) với mỗi người sử dụng. Và phân phối khoá phiên sử dụng khoá chính với Trung tâm. Sơ đồ khoá công khai được dùng để phân phối khoá chính. Sơ đồ ba lớp này đặc biệt hữu ích khi người sử dụng phân tán rộng. Các yêu cầu căn bản của hệ thống là chất lượng thực hiện và sự tương thích nền tảng.

Yêu cầu

Trao đổi khoá Diffie Hellman là sơ đồ khoá công khai đầu tiên được đề xuất bởi Diffie và Hellman năm 1976 cùng với khái niệm khoá công khai. Sau này được biết đến bởi James Ellis (Anh), người đã đề xuất bí mật năm 1970 mô hình tương tự. Đây là phương pháp thực tế trao đổi công khai các khoá mật. Nó thúc đẩy việc nghiên cứu đề xuất các mã khoá công khai. Sơ đồ được sử dụng trong nhiều sản phẩm thương mại.

Là sơ đồ trao đổi khoá mật dùng khoá công khai:

o Không thể dùng để trao đổi mẩu tin bất kỳ.

o Tuy nhiên nó có thể thiết lập khoá chung.

o Chỉ có hai đối tác biết đến.

o Giá trị khoá phụ thuộc vào các đối tác (và các thông tin về khoá công khai và khoá riêng của họ).

o Dựa trên phép toán lũy thừa trong trường hữu hạn (modulo theo số nguyên tố hoặc đa thức) là bài toán dễ.

o Độ an toàn dựa trên độ khó của bài toán tính logarit rời rạc (giống bài toán phân tích ra thừa số) là bài toán khó.

Khởi tạo Diffie Hellman

• Mọi người dùng thỏa thuận dùng tham số chung:

o Số nguyên tố rất lớn q hoặc đa thức.

o α là căn nguyên tố của mod q.

• Mỗi người dùng (A chẳng hạn) tạo khoá của mình:

o Chọn một khoá mật (số) của A: xA < q

o Tính khoá công khai của A: yA = axA size 12{a rSup { size 8{ ital "xA"} } } {}mod q.

o Mỗi người dùng thông báo công khai khoá của mình yA

Trao đổi khoá Diffie Hellman

• Khoá phiên dùng chung cho hai người sử dụng A, B là KAB size 12{K rSub { size 8{ ital "AB"} } } {}

• KAB được sử dụng như khoá phiên trong sơ đồ khoá riêng giữa A và B
• A và B lần lượt trao đổi với nhau, họ có khoá chung KAB cho đến khi họ chọn khoá mới.
• Kẻ thám mã cần x, do đó phải giải tính logarit rời rạc

Mã đường cong Elip thực

• Đường cong Elip được định nghĩa bởi phương trình với 2 biến x, y và hệ số thực
• Xét đường cong Elip bậc 3 dạng:

trong đó x, y, a, b là các số thực và định nghĩa thêm điểm O.

• Có phép cộng đối với đường cong Elip

o Về hình học tổng của P và Q là điểm đối xứng của giao điểm R

o Điểm O đóng vai trò là đơn vị đối với phép cộng và nó là điểm vô cực.

Đường cong Elip hữu hạn

- Mã đường cong Elip sử dụng đường cong Elip mà các biến và hệ số là hữu hạn.

- Có hai họ được sử dụng nói chung:

o Đường cong nguyên tố Ep(a,b) được xác định trên Zp

- Sử dụng các số nguyên modulo số nguyên tố

- Tốt nhất trong phần mềm

o Đường cong nhị phân E2n(a,b)xác định trên GF( 2n size 12{2 rSup { size 8{n} } } {})

- Sử dụng đa thức với hệ số nhị phân

- Tốt nhất trong phần cứng

Đường cong Elip (ECC – Elliptic Curve Cryptography)

Trong ECC phép cộng giống phép nhân của modulo và phép cộng lặp trong ECC (tức là phép nhân một điểm với một hệ số) giống như phép lũy thừa của modulo.

Bài toán sau đây trong ECC là bài toán khó tương đương với bài toán logarit rời rạc:

o Giả sử cho Q = k.P, trong đó P, Q là 2 điểm của đường cong Elip

o Dễ dàng tính Q, nếu cho trước P, k

o Rất khó tìm k, nếu cho trước P, Q. Bài toán tìm hệ số k chính là bài toán khó bài toán logarit đường cong Elip. Mã đường cong Elip dựa trên bài toán khó một chiều này để dấu khoá riêng.

ECC Diffie Hellman

Chẳng hạn dựa trên cơ sở độ khó của bài toán tìm hệ số liên hệ giữa hai điểm như trên, người ta đưa ra sơ đồ trao đổi khoá ECC Diffie Hellman giồng như trao đổi khoá Diffie Helman thông thường. Ở đây phép lũy thừa trong Modulo thông thường được thay bằng phép nhân một điểm với hệ số trong ECC và phép logarit rời rạc được thay bằng phép toán cho 2 điểm tìm hệ số liên hệ giữa chúng. Bài toán sau là bài toán khó xác định độ an toàn của sơ đồ trao đổi công khai khoá chung.

- Nhóm người dùng chọn chung một đường cong Elip phù hợp Ep(a,b)

- Chọn điểm cơ sở G=(x1,y1) với bậc lớn, tức là n lớn sao cho nG = O

- Hai người sử dụng A và B chọn khoá riêng của mình: nA< n, nB< n

- Sau đó họ tính các khoá công khai của A và B: PA=nA×G,PB=nB×G. Và cho công bố công khai PA và PB.

- Hai người sử dụng dùng chung khoá mật: K=nA×nB×G.

- Mỗi người đều có cách tính khoá chung đó bằng cách lấy khoá riêng của mình nhân với khoá công khai của đối tác: K=nA×PB, K=nB×PA

ECC mã và giải mã

Có một số cách dùng đường cong Elip để tạo mã công khai, ta xét cách đơn giản nhất

sau:

Trước hết nhóm người sử dụng cần phải thống nhất chọn một đường cong Elip phù hợp và một điểm G giống như trong trao đổi khoá ECC Diffie – Hellman. Mỗi bản tin M được coi như một điểm PM trên đường cong Elip đó.

- Mỗi người sử dụng chọn một khoá riêng cho mình nA < n

- Và tính khoá công khai để công bố PA=nA×G

- ECC mã bản tin M tương ứng với điểm PM trên đường cong Elip bằng cách tạo bản mã CM là cặp điểm trên đường cong Elip đó như sau:

CM={kG, PM+k Pb}, k là số ngẫu nhiên

- Ta thực hiện phép toán trên hai điểm của CM để giải mã tìm PM

An toàn ECC

Dựa trên bài toán tìm hệ số liên hệ giữa hai điểm trên đường cong Elip gọi là bài toán logarit trên đường cong Elip. Phương pháp nhanh nhất giải bài toán trên đã biết là “Pollard rho method”. Bài toán này tương đương với bài toán phân tích ra thừa số, nhưng có thể sử dụng kích thước khoá nhỏ hơn nhiều, chảng hạn so với RSA. Người ta chứng minh được rằng với độ dài khoá bằng nhau các tính toán nói chung là tuơng đương. Vậy với độ an toàn như nhau ECC có nhiều ưu điểm về không gian lưu trữ và tính an toàn đi kèm.

Bài tập

- p=7, q=11, e = 3, NSD A chọn khoá riêng xA = 7, tính khoá công khai của A

- NSD B gửi bản tin M = 5 và mã bằng khoá công khai của A

- NSD A giải mã sử dụng định lý phần dư Trung Hoa

- p=11, q=13, e = 7, NSD A chọn khoá riêng xA = 9, tính khoá công khai của A

- NSD B gửi bản tin M = 7 và mã bằng khoá công khai của A

- NSD A giải mã sử dụng định lý phần dư Trung Hoa

- p=23, q=31, NSD A chọn khoá riêng xA = 13, tính khoá công khai của A

- NSD B gửi bản tin M = 20 và mã bằng khoá công khai của A

- NSD A giải mã sử dụng định lý phần dư Trung Hoa

－ Chọn số nguyên tố dung chung q = 131 và α = 7,

－ NSD A chọn khoá riêng xA = 11

－ NSD B chọn khoá riêng xB = 19

－ Tính khoá công khai của A và B

－ Nêu cách A va B tính khoá mật dùng chung giữa A và B

－ Chọn số nguyên tố dung chung q = 131 và α = 7,

－ NSD A chọn khoá riêng xA = 11

－ NSD B chọn khoá riêng xB = 19

－ Tính khoá công khai của A và B

－ Nêu cách A va B tính khoá mật dùng chung giữa A và B

• Cho hệ đường cong Elip y2 = (x3 + x + 1) mod 13

• Vẽ đồ thị đường cong trên.

• Cho G = (4, 2)

• NSD A chọn khoá riêng xA = 2

• NSD B chọn khoá riêng xB = 3

• Tính khoá công khai của A và B

• Nêu cách A va B tính khoá mật dùng chung giữa A và B

- Cho hệ (G, α, β) trong đó G là một nhóm với phép nhân và α, β là hai phần tử của G.

- Công khai G, α, β

- Giữ bí mật luỹ thừa nguyên a thoả mãn: αa size 12{α rSup { size 8{a} } } {} = β (để tìm được a phải giải bài toán logarit rời rạc là bài toán khó)

- Mã hoá mẫu tin M bằng cách chọn ngẫu nhiên số k và tính:

a) Áp dụng ví dụ trên cho p = 79, α = 5, a = 3, M = 19 và k = 4. Ở đây nhóm với phép nhân là Zp, tính β. Tìm bản mã C của bản rõ M và giải mã

b) Áp dụng ví dụ trên cho p = 191, α = 7, a = 5, M = 29 và k = 9. Ở đây nhóm với phép nhân là Zp, tính β. Tìm bản mã C của bản rõ M và giải mã.

c) Áp dụng ví dụ trên cho p = 191, α = 7, a = 5, M = 29 và k = 9. Ở đây nhóm với phép nhân là Zp, tính β. Tìm bản mã C của bản rõ M và giải mã.