CÁc hệ MẬt khoá CÔng khai kháC

  Zp là phần tử nguyên thuỷ ,   Zp^*

Mục tiêu:Hãy tìm một số nguyên duy nhất a, 0  a  p-2 sao cho:

^a   (mod p)

Ta sẽ xác định số nguyên a bằng log 


Hình 2.7 Hệ mật khoá công khai Elgamal trong Zp^*

Cho p là số nguyên tố sao cho bài toán logarithm rời rạc trong Zp là khó giải. Cho   Zp^* là phần tử nguyên thuỷ.Giả sử P = Zp^* ,

C = Zp^*  Zp^* . Ta định nghĩa:

K = {(p, ,a,):   ^a (mod p)}

Các giá trị p, , được công khai, còn a giữ kín

Với K = (p, ,a,) và một số ngẫu nhiên bí mật k  Zp-1, ta xác định:

e_k (x,k) = (y₁ ,y₂ )

trong đó

y₁ = ^k mod p

y₂ = x^k mod p

với y₁ ,y₂  Zp^* ta xác định:

d_k(y₁ ,y₂ ) = y₂ (y₁^a )^-1 mod p

Sau đây sẽ nmô tả sơ lược cách làm việc của hệ mật Elgamal .Bản rõ x được "che dấu" bằng cách nhân nó với ^k để tạo y_{2 .} Giá trị ^k cũng được gửi đi như một phần của bản mã. Bob -người biết số mũ bí mật a có thể tính được ^k từ ^k . Sau đó anh ta sẽ "tháo mặt nạ" bằng cách chia y₂ cho ^k để thu được x.

Cho p = 2579,  = 2, a = 765. Khi đó

 = 2⁷⁶⁵ mod 2579 = 949

Bây giờ ta giả sử Alice muốn gửi thông báo x = 1299 tới Bob. Giả sử số ngẫu nhiên k mà cô chọn là k = 853. Sau đó cô ta tính

= 435

= 2396
Khi đó Bob thu được bản mã y = (435,2396), anh ta tính

= 1299
Đó chính là bản rõ mà Alice đã mã hoá.

1. 
   Các thuật toán cho bài toán logarithm rời rạc.
   

• 
  Nếu cần, các bước 1 và 2 có thể tính toán trước ( tuy nhiên, điều này không ảnh hưởng tới thời gian chạy tiệm cận)
  
• 
  Tiếp theo cần để ý là nếu (j,y)  L₁ và (i,y)  L₂ thì
  

^mj = y = ^-i

Ví dụ 5.2.

Giả sử p = 809 và ta phải tìm log₃525. Ta có  = 3,  = 525 và m = 808 = 29. Khi đó:
²⁹ mod 809 = 99
Trước tiên tính các cặp được sắp (j,99^j mod 809) với 0  j28. Ta nhận được danh sách sau:
(0,1) (1,99) (2,93) (3,308) (4,559)

(5,329) (6,211) (7,664) (8,207) (9,268)

(10,644) (11,654) (12,26) (13,147) (14,800)

(15,727) (16,781) (17,464) (18,314) (19,275)

(20,582) (21,496) (22,564) (23,15) (24,676)

(25,586) (26,575) (27,295) (28,81)

(5,132) (6,44) (7,554) (8,724) (9,511)

(10,440) (11,686) (12,768) (13,256) (14,,355)

(15,388) (16,399) (17,133) (18,314) (19,644)

(20,754) (21,496) (22,564) (23,15) (24,676)

(25,356) (26,658) (27,489) (28,163)

Bây giờ nếu xử lý đồng thời qua cả hai danh sách, ta sẽ tìm được ( 10,644) trong L₁ và (19,644) trong L₂. Bây giờ ta có thể tính

= 309
Có thể kiểm tra thấy rằng quả thực 3³⁰⁹  525 (mod 809).

Thuật toán tiếp theo mà ta nghiên cứu là thuật toán Pohlig - Hellman. Giả sử

p_i là số nguyên tố đặc biệt. Giá trị a = log_ được xác định một cách duy nhất theo modulo p-1. Trước hết nhận xét rằng, nếu có thể tính a mod p_i^ci với mỗi i, 1  i  k, thì có thể tính a mod (p-1) theo định lý phần dư China. Để thực hiện diều đó ta giả sử rằng q là số nguyên tố.

p
-1  0 (mod q^c)

Ta sẽ chỉ ra cách tính giá trị

x = a mod q^c

0
 x  q^c-1. Ta có thể biểu diễn x theo cơ số q như sau:

trong đó 0  a_i  q-1 với 0  i  c-1. Cũng có thể biểu diễn như sau:

a = x + q^cs

với s là một số nguyên nào đó.
Bước đầu tiên của thuật toán tính a₀. Kết quả chính ở đây là:
^(p-1)/q  ^(p-1)a0/q(mod p)
Đ

ể thấy rõ điều đó cần chú ý rằng:
Điều này đủ để cho thấy:

K

ết quả này đúng khi và chỉ khi:

Tuy nhiên

Đó chính là điều cần chứng minh.

cho tới ⁱ  ^(p-1)/q (mod p).

với một giá trị i nào đó. Khi điều này xảy ra ta có a₀ =i.
Bây giờ nếu c = 1 thì ta đã thực hiện xong. Ngược lại, nếu c > 1 thì phải tiếp tục xác định a₁. Để làm điều đó ta phải xác định
₁ =  ^-ao

và kí hiệu

x₁ = log_₁ mod q^c

D
ễ dàng thấy rằng

Như vậy ta sẽ tính ₁^(p-1)/q2 mod p và rồi tìm i sao cho

K
hi đó a₁ = i.
Nếu c =2 thì công việc kết thúc; nếu không, phải lặp lại công việc này c-2 lần nữa để tìm a₂,. . .,a_c-1.
Hình 5.4 là mô tả giải mã của thuật toán Pohlig - Hellman. Trong thuật toán này,  là phần tử nguyên thuỷ theo modulo p, q là số nguyên tố .

p-1  0 (mod q^c)

v
à

Thuật toán tính các giá trị a₀, . . ., a_c-1 trong đó

log mod qc

H
ình 5.4. Thuật toán Pohlig - Hellman để tính log_ mod q^c.

Tính  = (p-1)/q mod p với 0  i  q-1 Đặt j = 0 và j =  While j  c-1 do Tính  = j(p-1)/q j+1 mod p Tìm i sao cho  = i aj = i j+1 = j -aj qj mod p j = j +1

Chúng ta minh hoạ thuật toán Pohlig - Hellman (P - H) qua một ví dụ nhỏ.

Giả sử p=29; khi đó

n = p-1 = 28 = 2².7¹

Giả sử  = 2 và  = 18. Ta phải xác định a = log₂18. Trước tiên tính a mod 4 rồi tính a mod 7.

Ta sẽ bắt đầu bằng việc đặt q = 2, c = 2. Trước hết

₀ = 1

và ₁ = ^28/2 mod 29

= 2¹⁴ mod 29

= 28

Tiếp theo

= 18¹⁴ mod 29

= 28

Vì a₀ = 1. Tiếp theo ta tính:

= 9

₁^28/4 mod 29 = 9⁷ mod 29

= 28

Vì

Ta có a₁ = 1. Bởi vậy a  3 ( mod 4).

Tiếp theo đặt q = 7 và c = 1, ta có

^28/7 mod 29 = 18⁴ mod 29

= 25

và ₁ = ^28/7 mod 29

= 16.

₃ = 7

₄ = 25

Bởi vậy a₀ = 4 và a  4 ( mod 7)

a  3 ( mod 4)

a  4 ( mod 7)

bằng định lý phần dư China, ta nhận được a  11( mod 28). Điều này có nghĩa là đã tính được log₂18 trong Z₂₉ là 11.

Phương pháp tính chỉ số khá giống với nhiều thuật toán phân tích thừa số tốt nhất. Trong phần này sẽ xét tóm tắt về phương pháp. Phương pháp này chỉ dùng một cơ sở nhân tử là tập B chứa các số nguyên tố nhỏ. Giả sử B = {p₁,p₂,. . ., p_B}. Bước đầu tiên ( bước tiền xử lý) là tìm các logarithm của B số nguyên tố trong cơ sở nhân tử. Bước thứ hai là tính các logarithm rời rạc của phần tử  bằng cách dùng các hiểu biết về các log của các phần tử trong cơ sở.

Trong quá trình tiền xử lý, ta sẽ xây dựng C = B +10 đồng dư thức theo modulo p như sau:
^xj  p₁^a1jp2^a2j. . . p_B^aBj(mod p)

1  j  C. Cần để ý rằng, các đồng dư này có thể viết tương đương như sau:

1  j  C. C đồng dư thức được cho theo B giá trị log_p_i (1  i  B) chưa biết. Ta hy vọng rằng, có một nghiệm duy nhất theo modulo p-1. Nếu đúng như vậy thì có thể tính các logarithm của các phần tử theo cơ sở nhân tử.

 =  ^s mod p

Bây giờ thử phân tích  theo cơ sở B. Nếu làm được điều này thì ta tính được đồng dư thức dạng:

^s = p₁^c1p₂^c2. . . p_B^cB (mod p)

Điều đó tương đương với

log_ + s  c₁log_p₁+ . . . + c_Blog_p_B ( mod p-1)

Vì mọi giá trị đều đả biết trừ giá trị log_ nên có thể dễ dàng tìm được log_.
Sau đây là một ví dụ minh hoạ 2 bước của thuật toán.
Ví dụ 5.4.

Giả sử p =10007 và  = 5 là một phần tử nguyên thuỷ được dùnglàm cơ sở của các logarithm theo modulo p. Giả sử lấy B = {2, 3, 5, 7} làm cơ sở. Hiển nhiên là log₅5 = 1 nên chỉ có 3 giá trị log của các phần tử trong cơ sở cần phải xác định. Để làm ví dụ, chọn một vài số mũ "may mắn" sau: 4063, 5136 và 985.

Với x = 4063, ta tính

5⁴⁰⁶³ mod 10007 = 237

ứng với đồng dư thức
log₅2 + log₅3 + log₅7  4063 ( mod 10006).

Tương tự, vì

và 5⁹⁸⁶⁵ mod 10007 = 189 = 3³7

3log₅3 + log₅7  9865 ( mod 10006)

94515⁷⁷³⁶ mod 10007 = 8400

log₅9451 = 4log₅2 + log₅3 + log₅5 + log₅7 - s mod 10006

= 46578 + 6190 + 21 + 1310 - 7736 mod 10006

= 6057.

và thời gian để tính một giá trị logarithm rời rạc riêng là khoảng

Bản chất của bài toán: I = (p, , , i) trong đó p là số nguyên tố , Zp* là phần tử nguyên thuỷ,   Zp* và i là một số nguyên sao cho 1  i  log2(p-1). Mục tiêu:Tính Li() là bít thấp nhất thứ i của log. (với  và p cho trước)

2. 
   Độ bảo mật tưng bít của các logarithm rời rạc.
   

khi và chỉ khi p | (w-x)(w+x)

^(p-1)/2  1 (mod p)

N
hư vậy, ta đã có công thức hữu hiệu sau để tính L₁():

Bây giờ xét việc tính L_i() với i > 1. Giả sử

p-1 = 2^s t

trong đó t là số lẻ. Khi đó có thể chỉ ra rằng, dễ dàng tính được L_i() nếu 1s. Mặt khác, việc tính L_s+1() chắc chắn là khó nếu dùng thuật toán giả định bất kì cho việc tính L_s+1() để tính các logarithm rời rạc trong Z_p.

L₁()  L₁(p-).

nếu p  3 (mod 4). Ta sẽ thấy điều đó như sau. Giả sử

^a   (mod p)

thì ^a+(p-1)/2  - (mod p)

Vì p  3 (mod 4) nên số nguyên (p-1)/2 là một số lẻ. Từ đây rút ra kết quả.

^(p+1)/4  ^a/2 (mod p)

hoặc

-^(p+1)/4  ^a/2 (mod p)

L₂() = L₁(^a/2)

Điều này được khai thác trong thuật toán được mô tả trong hình 5.6.
Ở cuối thuật toán, các giá trị x_i là các bít biểu diễn nhị phân của log_, nghĩa là:

Dưới đây là một ví dụ nhỏ để minh hoạ.

Giả sử p =19,  = 2 và  = 6. Vì trong ví dụ này, các giá trị quá nhỏ nên có thể lập bảng các giá trị của L₁() và L₂() với mọi mọi giá trị Z₁₉^*.( Nói chung L₁ có thể tính được một cách hiệu quả bằng tiêu chuẩn Euler, còn L₂ được tính theo thuật toán giả định). Các giá trị này được cho trên bảng 5.1. Thuật toán được tiến hành như trên hình 5.7.

Bởi vậy, log₂6 = 1110₂ = 14, ta có thể dễ dàng kiểm tra được giá trị này.
Hình 5.6. Tính các logarithm rời rạc trong Z_p với p  3 ( mod 4) khi biết trước thuật toán giả định L₂().

x0 = L1()  = /x0 mod p i =1 While   1 do xi = L2()  = (p+1)/4 (mod p) if L1() = xi then  =  9. else 10.  = p -  = /xi mod p i = i+1

Bảng 5.1. Các giá trị của L₁ và L₂ với p =19,  = 2

V
ới i  0, ta định nghĩa:

Y_i = x/2ⁱ⁺¹
Hình 5.7 Tính log₂6 trong Z₁₉

x0 = 0  =6 i =1 x1 = L2(6) = 1  = 5 L1(5) = 0  x1 10.  =14 11. i =2 12. i =2 5. x2 = L2(7) =1 6.  = 11 7. L1(11) = 0  x2 10.  =8 11.  =4 12. i = 3 5. x3 = L2(4) = 1 6.  =17 7. L1(17) = 0  x3 10.  = 2 11.  =1 12. i = 4 4. DONE

Cũng vậy ta xác định ₀ là giá trị của  ở bước 2 trong thuật toán; và với i1, ta xác định _i là giá trị của  ở bước 11 trong bước lặp thứ i của vòng While. Có thể chứng minh bằng phương pháp quy nạp rằng:

với mọi i0. Bây giờ để ý rằng: 2Y_i = Y_i-1 - x_i

điều này kéo theo
x_i+1 = L₂(_i) , i0
Vì rằng x_i+1 = L₂() nên thuật toán là đúng. Các chi tiết dành cho độc giả xem xét.

2. 
   TRƯỜNG HỮU HẠN VÀ CÁC HỆ THỐNG ĐƯƠNG CONG ELLIPTIC.
   

Chúng ta đã dành thời gian đáng kể để xét bài toán logarithm rời rạc (DL) vào việc phân tích số. Ta sẽ còn trở lại hai bài toán này trong các loại hệ mật và các giao thức mã khác nhau. Bài toán DL đã được nghiên cứu trong trương hữu hạn Z_p, tuy nhiên việc xét bài toán này theo các thiết lập khác nhau cũng rất có ích và là chủ đề của phần này.

Đặc trưng của bài toán: I = (G, , ), trong đó G là một nhóm hữu hạn với phép lấy nhóm o ,   G và   H, trong đó H = { i : i  0} là một nhóm con sinh bởi . Mục tiêu: Tìm một số nguyên duy nhất a sao cho 0  a  | H | -1 và a = , với kí hiệu a có nghĩa là  o . . . o  (a lần) Ta sẽ kí hiệu số nguyên a này bằng log

Bây giờ ta sẽ trở lại bài toán DL tổng quát hoá . Nhóm con H được sinh bởi phần tử  tuỳ ý  G dĩ nhiên phải là nhóm con cyclic cấp | H |. Bởi vậy, dạng bất kì của bài toán theo một nghĩa nào đó đều tương đương với bài toán DL trong một nhóm cyclic. Tuy nhiên, độ khó của bài toán DL dường như phụ thuộc vào cách biểu diễn nhóm được dùng.

a   (mod n)

Vì UCLN(,n) = 1 nên  có phần tử nghịch đảo nhân theo modulo n và ta có thể dễ dàng tính ^-1 mod n bằng thuật toán Euclide. Sau đó có thể giải để tìm a và nhận được

log_ =  ^-1 mod n

Ở phần trên ta đã nghiên cứu bài toán DL trong nhóm nhân Z_p^* vơi p là là số nguyên tố . Nhóm này là nhóm cyclic cấp p-1 và bởi vậy nó đẳng cấu với nhóm cộng Z_p-1. Theo thảo luận ở trên, ta đã biết cách tinh các logarithm rời rạc một cách hiệu quả trong nhóm cộng này. Điều đó gợi ý khả năng giải bài toán DL trong Z_p^* bằng cách quy nó về bài toán giải được dễ dàng trong Z_p-1.

Ta hãy xem xét điều này được thực hiện như thế nào?. Khi nói rằng, (Z_p^*, ) là đẳng cấu với (Z_p-1, +) có nghĩa là có một song ánh :

 : Z_p^*  Z_p-1

sao cho (xy mod p) = ((x) + (y)) mod (p-1)

Điều đó kéo theo:

(^a mod p) = a () mod (p-1)

Bởi vậy

Do đó nếu tìm a theo mô tả ở trên, ta có:

log_ = () (())^-1 mod (p-1)

Bây giờ, nếu có một phương pháp hữu hiệu để tính phép đẳng cấu  thì ta sẽ có một thuật toán hữu hiệu để tính các logarithm rời rạc trong Z_p^*. Khó khăn ở đây là không có một phương pháp chung đã biết nào để tính hiệu quả phép đẳng cấu  với số nguyên tố tuỳ ý. Ngay cả khi đã biết hai nhóm là đẳng cấu thì vẫn không thể biết một thuật toán hiệu quả để mo tả tương minh phép đẳng cấu.

1. 
   Nhóm nhân của trường Galois GF(pⁿ)
   
2. 
   Nhóm của một đường cong elliptic xác định trên một trương hữu hạn.
   

Ta đã biết rằng, nếu p là số nguyên tố thì Z_p sẽ là một trường. Tuy nhiên có nhiều trường hữu hạn khác không có dạng trên. Thực tế có các trường hữu hạn q phần tử nếu q = pⁿ, trong đó p là số nguyên tố , n  1là số nguyên. Bây giờ ta sẽ mô tả ngắn gọn cách xây dựng một trường như vậy. Trước tiên ta sẽ đưa ra một vài định nghĩa.

g(x) = q(x)f(x) + r(x)

và deg(r) < n.

Điều này có thể thực hiện theo cách chia các đa thức thông thường. Bởi vậy, một đa thứ bất kì trong Z_p[x] đều đồng dư theo modulo f(x) với một đa thức duy nhất có bậc  n-1.

Xây dựng một trường 8 phần tử. Điều này có thể thực hiện bằng cách tìm một đa thức bất khả quy bậc 3 trong Z₂[x]. Ta chỉ cần xem xét các đa thức có thành phần hằng số bằng 1 vì một đa thức bất kì có thành phần hằng số bằng 0 sẽ chia hết cho x và bởi vậy nó là một đa thức bất khả quy . Có tất cả 4 đa thức như vậy.

f₂(x) = x³ + x + 1

f₃(x) = x³ + x² + 1

f₄(x) = x³ + x² + x + 1

x⁴+x³+x+1 = (x+1)(x³+x+1) +x²+x

	001 010 011 100 101 110 111
001 010 011 100 101 110 111	001 010 011 100 101 110 111 010 100 110 011 001 111 101 011 110 101 111 100 001 010 100 011 111 110 010 101 001 101 001 100 010 111 011 110 110 111 001 101 011 010 100 111 101 010 001 110 100 011

Việc tính các phần tử nghịch đảo được tực hiện theo thuật toán Euclide mở rộng có biến đổi đôi chút.

x² =x²

x³ = x+1

x⁴ = x²+1

x⁵ = x²+ x+1

x⁶ = x²+1

x⁷ = 1

sẽ bao gồm tất cả các phần tử khác 0 của trường.

còn thời gian để tìm một giá trị logarithm rời rạc riêng khoảng

Tuy nhiên, với các giá trị n lớn (n > 800), bài toán DL trong GF(2ⁿ) được coi là khó cỡ 2ⁿ phải có ít nhất một thừa số nguyên tố "lớn" ( để gây khó khăn cho cách tấn công Pohlig - Hellman).

2. 
   Các đương cong Elliptic
   

[Phương trình (5.1) có thể dùng để xác định một đường cong elliptic trên một trường bất kì GF(pⁿ) với p - là số nguyên tố lớn hơn 3. Đường cong elliptic trên GF(2ⁿ) hoặc GF(3ⁿ) được xác định bằng một phương trình khác đôi chút)].

Giả sử

là các điểm trên E. Nếu x₂=x₁ và y₂=-y₁ thì P+Q = O; ngược lại P+Q = (x₃,y₃) trong đó:

x₃ = ²-x₁-x₂

y
₃ = (x₁-x₃)-y₁

P+O = O+P = P

đối với mọi P  E. Với định nghĩa phép cộng như vậy, có thể chỉ ra rằng, E là một nhóm Aben với phần tử đơn vị O. ( phần lớn các phép kiểm tra đều khá đơn giản song việc chứng minh tính kết hợp lại rất khó).
Cần để ý là các phần tử ngược (nghịch đảo) rất dễ tính toán. Phần tử nghịch đảo của (x,y) là (x,-y) với mọi (x,y)  E ( ta kí hiệu phần tử này là -(x,y) do phép nhóm là phép cộng)
Xét ví dụ sau.
Ví dụ 5.7

Giả sử E là một đường cong elliptic y² = x³+x+6 trên Z₁₁. Trước tiên ta xác định các điểm trên E. Để làm điều đó, xét mỗi giá trị có thể x  Z₁₁, tính x³+x+6 mod 11 và thử giải phương trình (5.1) đối với y. Với giá trị x cho trước, ta có thể kiểm tra xem liệu z = x³+x+6 mod 11 có phải là một thặng dư bình phương hay không bằng cách áp dụng tiêu chuẩn Euler. Ta đã có một công thức tường minh để tính các căn bậc hai của các thặng dư bình phương theo modulo p với các số nguyên tố p  3 (mod 4). Áp dụng công thức này, ta có các căn bậc hai của một thặng dư bình phương z là:

z^(11+1)/4 mod 11 = z³ mod 11

Kết quả của các phép tính này được nêu trên bảng 5.2

 = (32²+1)(27)^-1 mod 11

= 23^-1 mod 11

= 24 mod 11

= 8

Sau đó ta có: x₃ = 8²-2-2 mod 11

và y₃ = (8(2-5)-7) mod 11

= 2

Bởi vậy 2 = (5,2)

x	x3+x+6 mod 11	Có trong QR(11)?	y
0 1 2 3 4 5 6 7 8 9 10	6 8 5 3 8 4 8 4 9 7 4	Không Không Có Có Không Có Không Có Có Không Có	4,7 5,6 2,9 2,9 3,8 2,9

Bội tiếp theo là 3 = 2+ = (5,2) + (2,7). Ta lại bắt đầu bằng viẹc tính .

 = (7-2)(2-5)^-1 mod 11

= 58^-1 mod 11

= 57 mod 11

= 2

= 8

= 3

Tiếp tục theo cách tương tự, có thể tính được các bội còn lại như sau:

4 = (10,2) 5 = (3,6) 6 = (7,9)

7 = (7,2) 8 = (3,5) 9 = (10,9)

10 = (8,8) 11 = (5,9) 12 = (2,4)

Các thuật toán Shanks và Pohlig - Hellman có thể áp dụng cho bài toán rời rạc trên đường cong Elliptic song tới nay vẫn chưa có một thuật toán thích hợp cho phương pháp tính chỉ số đối với các đường cong Elliptic.Tuy nhiên, đã có một phương pháp khai thác đẳng cấu một cách tường minh giữa các đường cong Elliptic trong trường hữu hạn. Phương pháp này dẫn đến các thuật toán hữu hiệu đối với một số lớp các đường cong Elliptic. Kỹ thuật này do Menezes, Okamoto và Vanstone đưa ra và có thể áp dụng cho một số trường hợp riêng trong một lớp đặc biệt các đường cong Elliptic (được gọi là các đường cong siêu biến, chúng đã được kiến nghị sử dụng trong các hệ thống mật mã). Tuy nhiên, nếu tránh các đường cong siêu biến thì lại xuất hiện một đường cong Elliptic có một nhóm con cyclic cỡ 2¹⁶⁰ , đường cong này sẽ cho phép thiết lập an toàn một hệ mật miễn là bậc của nhóm con phải là bội của ít nhất một thừa số nguyên tố lớn ( nhằm bảo vệ hệ mật khỏi phương pháp tấn công của Pohlig - Hellman).

Giả sử  = (2,7) và số mũ mật của Bob là a = 7. Bởi vậy:

 = 7 = (7,2)

Phép mã hoá thực hiện như sau

e_K(x,k) = (k(2,7),x+k(7,2))

trong đó xE và 0  k  12 còn phép giải mã thực hiện như sau:

d_K(y₁,y₂) = y₂-7y₁

Giả sử Alice muốn mã bản tin x = (10,9) ( là một điểm trên E). Nếu cô chọn giá trị ngẫu nhiên k=3 thì cô tính

y1 = 3(2,7)

= (8,3)

= (10,9) + (3,5)

= (10,2)

Bởi vậy, y = ((8,3),(10,2)). Bây giờ nếu Bob nhận được bản mã y thì anh ta giải mã như sau:

x = (10,2) - 7(8,3)

= (10,2) - (3,5)

= (10,2) + (3,6)

= (10,9)

Ví dụ 5.9

Cũng như ví dụ trước, giả sử  = (2,7) và số mũ mật của Bob là 7. Khi đó

 = 7 = (7,2)

Giả sử Alice muốn mã hoá bản rõ sau:

x = (x₁,x₂) = (9,1)

(Cần chú ý là x không phải là một điểm trên E) và cô chọn giá trị ngẫu nhiên k = 6. Đầu tiên cô tính:
y₀ = k = 6(2,7) = (7,9)

và k = 6(7,2) = (8,3)

Như vậy, c₁ = 8 còn c₂ = 3.
Tiếp theo Alice tính:

y₁ = c₁x₁ mod p = 89 mod 11 = 6

và y₂ = c₂x₂ mod p = 31 mod 11 = 3

Bản mã mà cô giửi cho Bob là:

Khi Bob nhận được bản mã này, Trước tiên anh ta tính:

và sau đó tính:

x = (y₁c₁^-1 mod p, y₂c₂^-1 mod p)

= ((68^-1 mod 11, 33^-1 mod 11)

= (67 mod 11, 34 mod 11)

= (9,1).
H

Đặc trưng của bài toán: I = (s₁, s₂, . . . ,s_n, T) trong đó s₁, . . ., s_n và T là các số nguyên dương. Các s_i được gọi là các cỡ, T được gọi là tổng đích.
Vấn đề: Liệu có một véc tơ nhị phân x = (x₁, . . . , x_n) sao cho: