(LUẬN văn THẠC sĩ) nghiên cứu một số chữ ký đặc biệt trên đường cong elliptic

CÁC KHÁI NIỆM CƠ BẢN

MỘT SỐ KHÁI NIỆM TRONG SỐ HỌC

Số nguyên a > 1 đƣợc gọi là số nguyên tố, nếu a chỉ có ƣớc số là 1 và a

Một số nguyên lớn hơn 1 không là số nguyên tố thì đƣợc gọi là hợp số

Ví dụ các số 2, 3, 5, 7 là số nguyên tố; các số 6, 8, 10, 12, 14, 15 là hợp số

Hai số a và b đƣợc gọi là nguyên tố cùng nhau, nếu chúng có ƣớc số chung là 1, tức là nếu gcd (a,b) = 1

Một số nguyên n > 1 bất kỳ đều có thể viết dưới dạng n = p 1 a1 p 2 a2 p k ak trong đó p 1 , p 2 , ,p k là các số nguyên tố khác nhau, a 1 , a 2 , a k là các số mũ nguyên dương

Dạng khai triển chính tắc của một số nguyên dương n là duy nhất nếu không xét thứ tự các thừa số nguyên tố Chẳng hạn, dạng khai triển chính tắc của số 1800 là

Các số nguyên tố đóng vai trò quan trọng trong số học và có ứng dụng lớn trong lý thuyết mã hóa Định lý 1.1 trình bày thuật toán Euclid để tìm ước số chung lớn nhất, một vấn đề quan trọng trong nghiên cứu số nguyên tố.

Với mọi a, b  Z, b  0, tồn tại duy nhất q, r  Z để: a = bq + r, 0   r | | b

Nếu r = 0 thì b|a, nghĩa là b là ƣớc số của a

Ngƣợc lại thì b a Với a 1 , …, a k  Z, nếu b|a i (i = 1,…, k) thì b gọi là ƣớc chung của a 1 ,…,a k .Ƣớc chung lớn nhất của a 1 , …, a k ký hiệu là gcd(a 1 , …, a k ) Định lý 1.2

Nếu a, b  Z và khác 0 thì d = gcd(a, b) là phần tử nhỏ nhất trong tất cả các số nguyên dương có dạng ax + by (x, y  Z)

Giả sử C = {c ∈ N | c = ax + by, x, y ∈ Z} và C ≠ ф, với e = ax₀ + by₀ là phần tử nhỏ nhất của C Chúng ta cần chứng minh rằng d = e Nếu a = eq + r, với 0 ≤ r < e, thì r = a - eq = a(1 - qx₀) + b(-qy₀) Nếu r ≠ 0, r phải thuộc C, điều này dẫn đến mâu thuẫn với việc chọn e Do đó, e chia hết cho a.

Tương tự, e|b; do đó e  d Mặt khác, e = ax 0 + by 0 và d|a, d|b, suy ra d|e

Tồn tại x, y  Z thỏa mãn: ax + by = c khi và chỉ khi d|c với d = gcd(a, b)

Nếu a = ed, b = fd, thì rõ ràng d|c Mặt khác nếu d|c, đặt kd = c Vì tồn tại x 0 , y 0

 Z để ax 0 + by 0 = d, nên a(kx 0 ) + b(ky 0 ) = kd = c

Với mọi a, b, m  Z ta định nghĩa a  b mod m khi và chỉ khi m|(a - b)

Với một số m cố định, Z tạo thành một quan hệ tương đương, dẫn đến việc phân hoạch Z thành các lớp tương đương Z_m = {[a] | a ∈ Z}, trong đó [a] = {b ∈ Z | a ≡ b mod m} Mỗi lớp tương đương [a] được xác định bởi các phần tử của nó, minh họa qua ví dụ trong Định lý 1.4.

Với a, m  Z, tồn tại x  Z thỏa mãn ax  1 mod m khi và chỉ khi gcd(a, m) = 1

Chứng minh x  Z để ax  1 mod m  có x, y  Z thỏa mãn ax – my = 1

Theo hệ quả 1.3, định lý hoàn toàn đƣợc chứng minh p  N đƣợc gọi là nguyên tố khi và chỉ khi p > 1 và a p với mọi a  Z, 1 < a

< p Nói cách khác, p  N, p > 1, p là nguyên tố khi và chỉ khi với mọi a, b  Z, p|ab

 p|a hoặc p|b Định lý 1.5 (Định lý phần dƣ Trung Quốc)

Giả sử m 1, …, m r  N đôi một nguyên tố cùng nhau, gcd(m i , m j ) = 1 với mọi i j Có a 1 , …, a r  Z Khi đó, hệ phương trình x  a i (mod m i ) (1  i  r ) có một nghiệm duy nhất theo modulo M = m 1 x …xm r là x = 

1 mod M trong đó M i = M/m i và M i y i 1 mod m i

Chú ý rằng M i là tích của tất cả các m j với j  i Vì vậy, nếu j  i thì

M i  0 mod m j Chú ý, gcd(M i , m i ) = 1, theo định lý 1.4, M i y i  1 mod m i có một nghiệm y i Do đó, x = 

 a i M i y i  a i mod m i với mọi i, 1  i  r Vì vậy, x là nghiệm của hệ phương trình đồng dư

Hàm Euler ф: N  N đƣợc định nghĩa là ф(m) = #{k  N | 1  k  m , gcd(k, m) = 1} Định lý 1.6 ф(m) = #{a  Z m | ab  1 mod m với b  Z m }

Chứng minh Dựa vào định lý 1.1, ta có điều phải chứng minh

Nếu p là một số nguyên tố, ф(p) = p – 1 và với a bất kỳ thuộc Z p , p a, tồn tại b

Giả sử p là một số nguyên tố lẻ và x thuộc Z với điều kiện 1 ≤ x ≤ p - 1, thì x được gọi là thặng dư bậc 2 theo modulo p nếu phương trình y² ≡ x mod p có ít nhất một nghiệm y thuộc Zp Ngược lại, x được gọi là bậc 2 không có thặng dư nếu nó không phải là thặng dư bậc 2 theo modulo p và x khác 0 mod p Đây là nội dung của Định lý 1.7 (Euler).

Theo định lý 1.1 G m = {a  Z m | gcd(a, m) = 1} tạo thành nhóm nhân bậc ф(m) Định lý 1.8 (Fermat)

Cho p là số nguyên tố và a  Z Khi đó, ta có:

(1) Vì ф(p) = p – 1 nên đây là trường hợp đặc biệt của định lý Euler

(2) Dễ dàng thấy nếu a  0 mod p là hiển nhiên, ngƣợc lại theo (1).

MỘT SỐ KHÁI NIỆM TRONG ĐẠI SỐ

1.2.1 Khái niệm Nhóm, Vành, Trường

Nhóm là cấu trúc bao gồm tập G và toán tử hai ngôi * trên G Với a, b  G, a * b

 G đƣợc định nghĩa nhƣ sau:

2 Tồn tại e  G thỏa mãn e * a = a * e = a với mọi a  G, (e đƣợc gọi là phần tử trung hòa)

3 Với mỗi a  G, tồn tại một phần tử b  G thỏa mãn b * a = a * b = e

(b là duy nhất và đƣợc gọi là phần tử nghịch đảo của a)

Trong toán học, ký hiệu G,* đại diện cho nhóm nhân, trong khi G,+ biểu thị nhóm cộng Trong nhóm cộng, phần tử trung hòa là 0 và phần tử nghịch đảo của a là -a Ngược lại, trong nhóm nhân, phần tử trung hòa là 1 và phần tử nghịch đảo của a là a^-1.

G đƣợc gọi là nhóm Abel nếu a * b = b * a với mọi a, b thuộc G

Giả G,* là nhóm và H là tập con của G Cấu trúc H, đƣợc gọi là nhóm con của G,* nếu là một thu hẹp của * tới H x H và H, là một nhóm

Nếu G,* là một nhóm hữu hạn, thì số lượng phần tử của G,* được gọi là bậc của G, ký hiệu là |G| Đối với nhóm nhân hữu hạn, bậc của một phần tử a thuộc G là số nguyên dương nhỏ nhất m sao cho a^m = 1 Trong nhóm nhân, với mọi phần tử thuộc nhóm, giá trị m luôn tồn tại.

G là nhóm nhân hữu hạn bậc n Nếu bậc của phần tử a  G là m thì a k  1 khi và chỉ khi m|k

Nếu k = mq, thì a k = (a m ) q =1 Ngƣợc lại, k = mq + r, 0  r  m Khi đó a r = a k (a -1 ) mq = 1 Vì vậy, r phải bằng 0

Nếu G ,* là nhóm nhân hữu hạn bậc n, thì:

(2) Bậc của mọi phần tử a  G chia hết cho |G|

Nếu a  G có bậc m thì H = {a k | k  Z }là nhóm con của G và có bậc m Nếu

Nhóm G được gọi là nhóm cyclic nếu tồn tại một phần tử a có bậc n = |G|, trong đó G = {a^k | k ∈ Z}, và a là phần tử sinh của G Một ví dụ điển hình là tập hợp Z_n = {0, 1, 2,…, n – 1}, tạo thành một nhóm cyclic bậc n với phép cộng modulo n.

Vành là tập R với 2 toán tử cộng (+) và nhân (.) với các điều kiện sau:

Trường F là vành với phần tử đơn vị e   0 } là một nhóm nhân Định lý 1.11

Vành Z p là một trường khi và chỉ khi p là số nguyên tố

Với a, b  Z, ta có: p là số nguyên tố p|ab tức là p|a hoặc p|b

Nếu Z p là trường thì Z * p tạo thành nhóm nhân Nếu p a thì a 0 mod p Điều này nghĩa là a Z * p và tồn tại a -1 Do đó nếu p|ab và p a thì p|(ab) -1 = b

Vậy p là số nguyên tố

Nếu p là một số nguyên tố, để chứng minh rằng Z * p là nhóm nhân, ta cần chỉ ra rằng với mọi x thuộc Z * p, luôn tồn tại nghịch đảo x -1 Đối với a, b thuộc Z p, điều này khẳng định tính chất của nhóm nhân trong bội số nguyên tố.

Trong tập hợp Zp, nếu xa ≡ xb mod p thì a ≡ b mod p, dẫn đến a - b ≡ 0 mod p Điều này có nghĩa là p chia hết cho x(a - b), tức là p chia hết cho x hoặc p chia hết cho a - b, với x thuộc Z*p, nghĩa là x khác 0 mod p Do đó, tập hợp xZp = {xa | a ∈ Zp} = Zp, trong đó xa = 1 với a ∈ Zp, vì luôn tồn tại phần tử 1 trong Zp Kết luận, mỗi x ∈ Z*p đều có phần tử nghịch đảo.

Cho F là một trường Tập con K của F cũng là một trường với các toán tử của

F, được gọi là trường con của F, hay F là một trường mở rộng của K Nếu K  F thì K được gọi là một trường con hợp lệ của F Trường là tối giản nếu nó không có trường con hợp lệ nào Với trường F bất kỳ, giao F 0 của tất cả các trường con hợp lệ là trường tối giản Trường F được gọi là có đặc số 0 nếu F 0  Q nghĩa là F chứa Q như một trường con Trường F được gọi là có đặc số p nếu F 0 Z p

Trường hữu hạn là loại trường chỉ chứa một số lượng hữu hạn các phần tử Mỗi trường hữu hạn đều có một số nguyên tố, được gọi là đặc số của trường Đối với một trường F có đặc số p, mọi phần tử a thuộc F sẽ thỏa mãn điều kiện pa = 0.

Trường K với phần tử đơn vị nhân là 1

(Các trường hữu tỷ Q, số thực R, số phức C có đặc số là 0 )

Với p là nguyên tố thì GF(p n ) có đặc số p

Nếu H là trường con của K thì H và K có cùng đặc số

Trường F là trường mở rộng của trường K, được ký hiệu là F = K(α), trong đó F là trường mở rộng nhỏ nhất của K chứa α Nếu F là trường hữu hạn với đặc số p, thì nhóm nhân F* = F \ {0} là nhóm cyclic, và F có thể biểu diễn dưới dạng F = Zp(α), với α là phần tử sinh của nhóm F* Phần tử α được gọi là phần tử nguyên thủy của trường F.

K là trường và V là nhóm cộng Abel V được xem là không gian vector trên trường K khi có một toán tử ánh xạ từ K x V đến V, và toán tử này phải thỏa mãn các điều kiện nhất định.

Các phần tử trong không gian vector V được gọi là vector, trong khi các phần tử của trường K được gọi là vô hướng Không gian vector V được xác định trên trường K, với các vector v1, v2, , vm thuộc V.

V có dạng c 1 v 1 + c 2 v 2 + …+ c m v m với c i  K (i = 1, …, m) là tổ hợp tuyến tính của v 1 , …, v m

Tập hợp tất cả các tổ hợp tuyến tính gọi là span của v 1 , …, v m và ký hiệu là span(v 1 , …, v m )

Tập S = {u 1 , u 2 ,…,u n } của các vector tạo thành cơ sở của V khi và chỉ khi

Các vector (u1, u2,…, un) là độc lập tuyến tính và tạo thành span của không gian vector V Nếu S là một cơ sở của V, thì mọi phần tử trong V có thể được biểu diễn duy nhất dưới dạng tổ hợp tuyến tính của các phần tử trong S Đối với không gian vector V có cơ sở là một tập hợp hữu hạn các vector, bất kỳ cơ sở nào của V cũng sẽ có số phần tử giống nhau, từ đó xác định chiều của V trên trường K.

Nếu F là trường mở rộng của trường K thì F là một không gian vector trên K

Chiều của F trên K đƣợc gọi là bậc mở rộng của F trên K

Cho F là một vành Một đa thức bậc n trên F có dạng:

) ( với n là số nguyên dương, các hệ số a i  F (0  i  n )

) ( ta định nghĩa tổng của f(x) và g(x) là 

) ( ta định nghĩa tích của f(x) và g(x) là  

Vành đa thức trên trường F, được ký hiệu là F[x], bao gồm tất cả các đa thức với phép cộng và phép nhân thông thường Định lý 1.12 trình bày thuật toán chia cho F[x], cung cấp một phương pháp hiệu quả để thực hiện phép chia giữa các đa thức trong vành này.

Giả sử f(x) và g(x)  F[x] có bậc nguyên dương, tồn tại duy nhất đa thức q(x), r(x)  F[x] thỏa mãn f(x) = g(x) q(x) + r(x) với bậc của r(x) nhỏ hơn bậc của g(x)

Nếu r(x) là đa thức 0, thì g(x) được xem là ước của f(x) Đa thức f(x) trong F[x] được gọi là tối giản nếu không tồn tại ước nào có bậc thấp hơn f(x) trong F[x] Một số a thuộc F là nghiệm của f(x) trong F[x] khi f(a) = 0.

Phần tử a F là nghiệm của đa thức f(x) F[x] khi và chỉ khi x – a là ƣớc của f(x) trong F[x]

Vì a là nghiệm nên f(a) = 0 Vì f(x) = (x –a).g(x) + r(x) nên bậc của r(x) nhỏ hơn 1, tức là r(x) = c  F Vì vậy, c = f(a) = 0 Ngƣợc lại, nếu f(x) = (x – a) q(x) thì f(a) = 0

Một đa thức khác không f(x)  F[x] bậc n có nhiều nhất n nghiệm trong F

Trường hữu hạn là trường có hữu hạn các phần tử ký hiệu là F q hoặc GF(q) với q là số các phần tử Định lý 1.14

F là trường mở rộng bậc n trên trường hữu hạn K Nếu K có q phần tử thì F có q n phần tử

Giả sử { 1 , , n }là cơ sở của F nhƣ là một không gian vector trên K Mọi

 sẽ có dạng  c 1  1  c n  n trong đó c i K(i = 1,…, n) Vì mỗi c i có thể là một trong q phần tử của K nên số các tổ hợp tuyến tính là q n Định lý

Nếu F là trường hữu hạn có đặc số p thì F có p n phần tử với n nguyên dương

Vì vậy, mọi trường hữu hạn là một mở rộng của trường đẳng cấu Z p với p là đặc số của F Định lý 1.15

Trường hữu hạn F = F p n là một trường mở rộng của Z p bậc n và mọi phần tử của F p n là một nghiệm của đa thức x p n x trên Z p

Chứng minh Đặc số của F p n là p Tập hợp F* = F \ {0} tạo thành nhóm nhân bậc p n -1 Với

 , bậc của trong nhóm chia hết cho bậc của F*, p n – 1 Vì vậy, với mọi  F *, chúng ta có  p n  1 1 hay  p n  Vì x p n x có nhiều nhất p n nghiệm, F p n gồm tất cả các nghiệm của x p n x trên Z p

Không gian vector F₂ᵖ chứa F₂ (hoặc Z₂) được định nghĩa với phép cộng như phép cộng vector và phép nhân k và v (k, v ∈ F₂ᵖ) được coi là tích vô hướng của k ∈ F₂ và v ∈ F₂ᵖ F₂ᵖ được xem là không gian vector với chiều r, ký hiệu d là chiều của không gian này Có thể thực hiện ánh xạ 1-1 giữa các phần tử trong không gian vector d chiều và các d-tuple của các phần tử trong F₂, dẫn đến việc có 2ᵈ phần tử trong không gian vector Do đó, khi d = r, F₂ᵖ trở thành không gian vector r chiều.

F là một mở rộng của F q Hai phần tử  và  thuộc F q m được gọi là liên hợp trên F q nếu chúng là nghiệm của cùng một đa thức tối giản bậc m trong F q Các phần tử ,  q ,  q 2 , ,  q m − 1 là các liên hợp của  trong F q m với F q.

F là một mở rộng của F q Một cơ sở của F q m (không gian vector trên F q ) của

KHÁI NIỆM VỀ ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

Thuật toán là một dãy hữu hạn các thao tác được bố trí theo một trình tự xác định nhằm giải quyết một bài toán

An operation, also known as a task, command, or instruction, refers to an action that must be executed by the algorithm's execution mechanism.

Mỗi thao tác trong quá trình giải bài toán chuyển đổi từ trạng thái nhập sang trạng thái xuất, sử dụng các đối tượng nhập và tạo ra các đối tượng xuất mới Quan hệ giữa hai trạng thái này phản ánh tác động của thao tác Dãy các thao tác của thuật toán được thực hiện liên tiếp để biến đổi bài toán từ trạng thái ban đầu đến trạng thái kết quả.

Mỗi thao tác có thể phân tích thành các thao tác đơn giản hơn

Trình tự thực hiện các thao tác trong thuật toán cần được xác định rõ ràng, vì cùng một tập hợp thao tác nhưng nếu sắp xếp theo trình tự khác nhau sẽ dẫn đến kết quả khác nhau.

1.3.2 Độ phức tạp của thuật toán

Lý thuyết thuật toán và các hàm số tính đƣợc ra đời từ những năm 30 của thế kỷ

Lý thuyết về độ phức tạp tính toán đã được hình thành và phát triển từ giữa những năm 60 của thế kỷ trước, đóng vai trò quan trọng trong việc nghiên cứu các vấn đề "tính được" và "giải được" trong toán học Mặc dù khái niệm "tính được" có thể được hiểu một cách trừu tượng, nhưng việc áp dụng nó vào thực tế khoa học tính toán bằng máy tính điện tử gặp nhiều thách thức do yêu cầu về không gian và thời gian Lý thuyết này cung cấp những hiểu biết sâu sắc về bản chất phức tạp của các thuật toán và bài toán, từ những vấn đề lý thuyết đến những bài toán thực tiễn thường gặp Bài viết này sẽ giới thiệu một số khái niệm cơ bản và kết quả quan trọng của lý thuyết độ phức tạp tính toán.

Để hiểu độ phức tạp tính toán của một tiến trình, cần xem xét số ô nhớ sử dụng và số phép toán sơ cấp thực hiện trong quá trình đó.

Dữ liệu đầu vào cho một thuật toán thường được thể hiện dưới dạng các từ trong một bảng ký tự Độ dài của một từ được xác định bởi số ký tự có trong từ đó.

Thuật toán A trên bảng ký tự  có độ phức tạp tính toán được xác định bởi hàm số f A (n), trong đó f A (n) biểu thị số ô nhớ hoặc số phép toán sơ cấp tối đa mà A cần để xử lý dữ liệu đầu vào có độ dài không vượt quá n Nếu tồn tại một đa thức P(n) sao cho với mọi n đủ lớn, f A (n) nhỏ hơn hoặc bằng P(n), thì thuật toán A được coi là có độ phức tạp thời gian đa thức.

Về sau khi nói đến các bài toán, ta hiểu đó là các bài toán quyết định, mỗi bài toán Q nhƣ vậy đƣợc xác định bởi:

- Một tập các dữ liệu vào I (trong một bảng ký tự  nào đó),

- Một câu hỏi q trên các dữ liệu vào, sao cho với mỗi dữ liệu vào x 1, câu hỏi q có một trả lời đúng hoặc sai

Bài toán quyết định Q được coi là giải được nếu tồn tại thuật toán có khả năng xử lý mọi dữ liệu đầu vào và cho ra kết quả đúng hoặc sai dựa trên câu hỏi q Nếu thuật toán này có độ phức tạp thời gian đa thức, thì bài toán Q được xem là giải được trong thời gian đa thức.

Thuật toán lại chia làm 2 loại: đơn định( tất định) và đa định( không tất định) Sau đây là vài ví dụ về các bài toán quyết định:

Bài toán SATISFIABILYTY (viết tắt là SAT):

- Mỗi dữ liệu vào là một graph G và một số nguyên k

- Mỗi câu hỏi là: Graph G có một clique với ≥ k đỉnh hay không? (một clique của G là một graph con đầy đủ của G)

- Mỗi dữ liệu là một bộ n + 1 số nguyên dương I = (s 1 , s n ; T)

- Câu hỏi là: có hay không một vectơ Boole (x 1 , ,x n ) sao cho  n    i xi si T

(vectơ Boole là vectơ có các thành phần là 0 hoặc 1)

Bài toán thặng dƣ bậc hai:

- Mỗi dữ liệu gồm hai số nguyên dương (a, n)

- Câu hỏi là: a có là thặng dƣ bậc hai theo mod n hay không?

- Mỗi dữ liệu là một số nguyên dương N

- Câu hỏi: N là hợp số không? Tức có hay không hai số m, n >1 sao cho N = m.n?

Nếu đặt câu hỏi "N có phải là số nguyên tố không?", ta sẽ có bài toán số nguyên tố Đến nay, đối với tất cả các bài toán liên quan, ngoại trừ bài toán về hợp số và số nguyên tố, vẫn chưa có thuật toán nào được phát hiện để giải quyết chúng trong thời gian đa thức.

1.3.3 Một số lớp bài toán

Lớp P bao gồm tất cả các bài toán có thể giải quyết bằng thuật toán trong thời gian đa thức, phản ánh mức độ phức tạp tính toán của chúng.

Giả sử có hai bài toán A và B với các tập dữ liệu tương ứng là  1 và  2 Một thuật toán f:  * 1 →  * 2 được gọi là phép quy dẫn bài toán A về bài toán B nếu nó chuyển đổi mỗi dữ liệu x của A thành dữ liệu f(x) của B, sao cho câu hỏi của A trên x có đáp án đúng khi và chỉ khi câu hỏi của B trên f(x) cũng có đáp án đúng Chúng ta nói rằng bài toán A quy dẫn được về bài toán B trong thời gian đa thức, ký hiệu là A  B, nếu tồn tại thuật toán f với độ phức tạp thời gian đa thức quy dẫn A về B Nếu A  B và B thuộc lớp P, thì A cũng thuộc lớp P.

Một lớp bài toán quan trọng đã được nghiên cứu nhiều là các bài toán NP, thường gặp trong thực tế nhưng chưa có khả năng chứng minh chúng có thể giải quyết trong thời gian đa thức.

Thuật toán không đơn định, khác với thuật toán tất định, cho phép một trạng thái và ký tự đầu vào xác định một tập hợp hữu hạn các hành động kế tiếp thay vì chỉ một hành động duy nhất Cụ thể, trong máy Turing không đơn định, khi máy ở trạng thái q và đọc ký tự a, cặp (q, a) có thể dẫn đến nhiều hành động khác nhau Do đó, với một dữ liệu đầu vào x, thuật toán không đơn định có thể thực hiện nhiều tiến trình tính toán khác nhau, tạo ra sự linh hoạt trong quá trình xử lý thông tin.

Thuật toán không đơn định T chấp nhận dữ liệu x khi nó cho kết quả đúng Một bài toán A được xem là có thể giải quyết bởi thuật toán không đơn định trong thời gian đa thức nếu tồn tại một thuật toán không đơn định T và một đa thức p(n) sao cho với mọi dữ liệu vào x có độ dài n, thuật toán T sẽ trả về kết quả đúng.

Tất cả các bài toán trong các ví dụ đã nêu và nhiều bài toán tổ hợp phổ biến khác đều thuộc lớp NP, mặc dù hầu hết chưa được chứng minh thuộc lớp P Một bài toán A được gọi là NP-đầy đủ nếu nó đáp ứng các tiêu chí cụ thể trong lý thuyết tính toán.

A  NP và với mọi B  NP đều có B A

Lớp NP có một số tính chất sau đây:

2) Nếu P 1  P 2 và P 2 NP, thì P 1 NP

3) Nếu P 1 , P 2 NP, P 1  P 2, và P 1 là NP- đầy đủ, thì P 2 cũng là NP-đầy đủ

4) Nếu có A sao cho A là NP-đầy đủ và AP, thì P=NP

Từ các tính chất đó có thể xem rằng trong lớp NP, P là lớp con các bài toán

MỘT SỐ KHÁI NIỆM TRONG MẬT MÃ

1.4.1.1 Khái niệm hệ mã hóa Để bảo đảm an toàn thông tin lưu trữ trong máy tính (VD giữ gìn thông tin cố định) hay bảo đảm an toàn thông tin trên đường truyền tin (VD trên mạng máy tính, điện thoại), người ta phải “ Che Giấu ” các thông tin này

“ Che ” thông tin (dữ liệu) hay “ Mã hóa ” thông tin là thay đổi hình dạng thông tin gốc, và người khác “khó” nhận ra

“ Giấu ” thông tin (dữ liệu) là cất giấu thông tin trong bản tin khác, và người khác cũng “khó” nhận ra

Việc mã hoá phải theo quy tắc nhất định, quy tắc đó gọi là Hệ mã hóa

Hệ mã hóa đƣợc định nghĩa là bộ năm (P, C, K, E, D), trong đó:

P là 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 là tập hữu hạn các khoá có thể

E là tập các hàm lập mã

D là tập các hàm giải mã

Với khóa lập mã ke  K , có hàm lập mã e ke  E, e ke : P C ,

Với khóa giải mã kd  K , có hàm giải mã d kd  D, d kd : C P, sao cho d kd (e ke (x)) = x ,  x  P Ơ đây x đƣợc gọi là bản rõ , e ke (x) đƣợc gọi là bản mã

Trên đường truyền tin, thông tin được mã hoá để bảo đảm bí mật:

Người gửi G   e ke (T)   Người nhận N

(có khóa lập mã ke) (có khóa giải mã kd)

 Tin tặc có thể trộm bản mã e ke (T)

Người gửi G muốn gửi bản tin T cho người nhận N Để đảm bảo tính bảo mật, G tiến hành mã hóa bản tin bằng khóa lập mã ke, tạo ra bản mã e ke (T) và gửi cho N.

Tin tặc có thể trộm bản mã e ke (T), nhƣng cũng “ khó ” hiểu đƣợc bản tin gốc

T nếu không có khoá giải mã kd

Người N nhận được bản mã, họ dùng khoá giải mã kd, để giải mã e ke (T), sẽ nhận đƣợc bản tin gốc T = d kd (e ke (T))

Theo cách sử dụng khóa ta có thể phân loại có hai loại mã hóa chính: Mã hóa khóa đối xứng và Mã hóa khoá bất đối xứng

Mã hóa khóa đối xứng sử dụng cùng một khóa cho cả quá trình mã hóa và giải mã, nghĩa là nếu biết khóa này, dễ dàng tính được khóa kia Vì vậy, việc bảo mật cả hai khóa là rất quan trọng.

Mã hóa khóa bất đối xứng sử dụng hai loại khóa khác nhau: khóa lập mã và khóa giải mã, trong đó khóa lập mã (ke) không giống với khóa giải mã (kd) Việc biết một khóa không giúp tính toán được khóa kia, đảm bảo tính bảo mật cho khóa giải mã Hệ thống mã hóa này khác với mã hóa khóa đối xứng, nơi cùng một khóa được sử dụng cho cả hai chức năng.

Mã hóa khóa đối xứng là một phương pháp mã hóa trong đó khóa lập mã và khóa giải mã giống nhau, nghĩa là nếu biết khóa này thì dễ dàng tính được khóa kia Đặc biệt, một số hệ thống mã hóa thuộc loại này có khóa lập mã và khóa giải mã hoàn toàn trùng nhau (ke = kd).

Hệ mã hóa khóa đối xứng, hay còn gọi là hệ mã hóa khóa bí mật, yêu cầu cả hai bên giữ bí mật về khóa sử dụng Trước khi áp dụng, người gửi và người nhận cần thống nhất về thuật toán mã hóa và một khóa chung để mã hóa hoặc giải mã, và khóa này phải được bảo mật Độ an toàn của hệ thống mã hóa này phụ thuộc chủ yếu vào tính bảo mật của khóa.

Các đặc điểm của Hệ mã hóa khóa đối xứng Ưu điểm :

Mã hóa khóa đối xứng mã hóa và giải mã nhanh hơn mã hóa khóa công khai

- Mã hóa khóa đối xứng chƣa thật an toàn với lý do đơn giản:

Người mã hoá và người giải mã cần có một khoá chung để đảm bảo an toàn thông tin Khoá này phải được giữ bí mật tuyệt đối, vì nếu một bên biết khoá này thì bên kia cũng dễ dàng xác định được khoá của mình.

Khi hai người (lập mã, giải mã) cùng biết “chung” một bí mật, thì khó giữ đƣợc bí mật !

Vấn đề thỏa thuận và quản lý khóa chung là một thách thức phức tạp, đòi hỏi sự thống nhất giữa người gửi và người nhận Việc thay đổi khóa gặp nhiều khó khăn và có nguy cơ bị lộ Do đó, khóa chung cần được truyền đạt qua các kênh an toàn để đảm bảo tính bảo mật.

Hệ mã hóa cổ điển thuộc loại mã hóa khóa đối xứng, dễ hiểu và dễ thực thi, nhưng độ an toàn không cao Hệ thống này giới hạn tính toán trong phạm vi bảng chữ cái, ví dụ như Z26 cho chữ cái tiếng Anh và Z256 cho bảng mã ASCII.

Với hệ mã hóa cổ điển, việc biết khoá lập mã hoặc thuật toán lập mã giúp người ta dễ dàng xác định bản rõ, bởi vì khoá giải mã cũng dễ dàng tìm ra.

Hệ mã hóa khóa đối xứng hiện đại có độ an toàn cao nhƣ DES (1973),

Hệ mã hóa khóa đối xứng được sử dụng để mã hóa các bản tin lớn nhờ vào tốc độ mã hóa và giải mã nhanh hơn so với hệ mã hóa khóa công khai Trong khi đó, hệ mã hóa khóa bất đối xứng cũng có những ứng dụng riêng trong việc bảo mật thông tin.

Mã hóa khóa bất đối xứng là hệ thống mã hóa sử dụng hai loại khóa khác nhau: một khóa để mã hóa và một khóa để giải mã (ke ≠ kd) Việc biết một khóa không giúp dễ dàng tính toán khóa kia, tạo ra mức độ bảo mật cao cho thông tin.

Hệ mã hóa này còn đƣợc gọi là Hệ mã hoá khóa công khai, vì:

Khoá lập mã cho công khai , gọi là khoá công khai (Public key)

Khóa giải mã giữ bí mật, còn gọi là khóa riêng (Private key)

Bất kỳ ai cũng có thể sử dụng khóa công khai để mã hóa tin nhắn, tuy nhiên chỉ những người sở hữu khóa giải mã đúng mới có thể truy cập nội dung bản rõ.

Hệ mã hóa bất đối xứng hay Hệ mã hóa khoá công khai do Diffie và Hellman phát minh vào những năm 1970

Các đặc điểm của Hệ mã khoá bất đối xứng Ưu điểm :

Người mã hoá dùng khóa công khai, người giải mã giữ khóa bí mật Khả năng lộ khóa bí mật khó hơn vì chỉ có một người gìn giữ

Nếu kẻ phá hoại biết khoá công khai, cố gắng tìm khoá bí mật, thì chúng phải đương đầu với bài toán “khó”

Khi đã nắm rõ các tham số ban đầu của hệ mã hóa, việc tính toán cặp khóa công khai và khóa bí mật cần phải được thực hiện một cách dễ dàng, tức là trong khoảng thời gian đa thức.

Người gửi có bản rõ P và khoá công khai, thì “dễ” tạo ra bản mã C

Người nhận có bản mã C và khoá bí mật, thì “dễ” giải được thành bản rõ P

Nếu kẻ phá hoại nắm vững khóa công khai và bản mã C, việc xác định bản rõ P sẽ trở thành một bài toán "khó" với số lượng phép thử cực kỳ lớn, khiến cho việc giải quyết trở nên không khả thi.

SƠ ĐỒ CHỮ KÝ TRÊN ĐƯỜNG CONG ELLIPTIC

Đường cong Elliptic trên trường Galois

Nhóm E trên trường Galois Ep(a,b) được xác định bằng cách tính p mod b ax^3 + x + 3 với 0 ≤ x < p Các hằng số a và b là các số nguyên không âm, nhỏ hơn số nguyên tố p, và phải thỏa mãn điều kiện 4a^3 + 27b^2 mod p ≠ 0.

Đối với mỗi giá trị x, cần xác định xem nó có phải là thặng dư bậc hai hay không Nếu x là thặng dư bậc hai, sẽ có hai giá trị thuộc nhóm Elliptic.

Nếu x không là thặng dƣ bậc 2 thì điểm này không nằm trong nhóm Ep  a,b

Ví dụ: (Cấu trúc của một nhóm E)

Trước tiên ta kiểm tra lại:

Sau đó ta xác định các thặng dƣ bậc 2 Q23 từ Z23 p mod x2 p x 2modp

Với 0xp ta tính y 2 x 3 x1 và xác định xem liệu y 2 có nằm trong tập các thặng dƣ bậc 2 Q23 không x 0 1 2 3 4 5 6 7 8 9 10 11 y2 1 3 11 8 0 16 16 6 15 3 22 9

Nhóm Elliptic Ep  a,b E23  1,1 sẽ gồm các điểm sau:

Đường cong Elliptic trên trường hữu hạn

Đường cong elliptic được phát triển trên các trường hữu hạn, trong đó hai loại trường hữu hạn phổ biến là Fq, với q là số nguyên tố, hoặc q là 2^m, trong đó m là một số nguyên.

Tùy thuộc vào trường hữu hạn F_q, có nhiều đường cong elliptic cho mỗi bậc của q Vì vậy, với một trường hữu hạn cố định có q phần tử và giá trị q lớn, có nhiều lựa chọn cho nhóm đường cong elliptic.

2.1.3.1 Đường cong elliptic trên trường F P (p là số nguyên tố)

Cho p là số nguyên tố (p > 3) và a, b thuộc Fp sao cho 4a³ + 27b² ≠ 0, một đường cong elliptic E(Fp) trên Fp được xác định bởi các tham số a và b là tập hợp các cặp giá trị (x, y) thuộc Fp thỏa mãn phương trình y² = x³ + ax + b, cùng với một điểm O gọi là điểm tại vô cực Số lượng điểm của E(Fp) được xác định bởi định lý Hasse: #E(Fp).

Các phép toán trên đường cong elliptic E(Fp) tương tự như trên E(R), và tập hợp các điểm trên E(Fp) tạo thành một nhóm với các tính chất quan trọng Nhóm này có tính đóng, nghĩa là nếu a và b thuộc G thì a + b cũng thuộc G Tính kết hợp được thỏa mãn khi (a + b) + c = a + (b + c) Ngoài ra, tồn tại phần tử trung hòa là 0 trong G, sao cho a + 0 = 0 + a = a với mọi a thuộc G Cuối cùng, mỗi phần tử a trong G đều có phần tử đối -a cũng thuộc G, thỏa mãn -a + a = a + (-a) = 0 Bậc của một điểm A trên E(Fp) được định nghĩa là một số nguyên dương r.

2.1.3.2 Đường cong elliptic trên trường F 2 m

Một đường cong elliptic E(F 2 m ) trên F 2 m được định nghĩa bởi các tham số a, b

 F 2 m (với b ≠ 0) là tập các điểm (x, y) với x  F 2 m , y  F 2 m thỏa công thức: y 2 + xy = x 3 + ax 2 + b cùng với điểm O là điểm tại vô cực Số lƣợng các điểm thuộc E(F 2 m ) ký hiệu

1 2 # m 1 2 q   q  E F    q q trong đó q = 2 m Ngoài ra, #E(F 2 m ) là số chẵn

Tập hợp các điểm thuộc E(F 2 m ) tạo thành một nhóm thỏa các tính chất sau:

(x, y) + (x, x + y) = O,  (x, y)  E(F 2 m ) Khi đó, (x, x + y) là điểm đối của (x, y) trên E(F 2 m ))

Việc xử lý được thực hiện trên hai hệ tọa độ khác nhau: hệ tọa độ affine và hệ tọa độ quy chiếu Mỗi hệ tọa độ sẽ dẫn đến cách tính toán khác nhau trên đường cong.

CÁC PHÉP TOÁN TRÊN ĐƯỜNG CONG ELLIPTIC

Phép cộng điểm đƣợc định nghĩa trên tập E(R) của các điểm (x, y) Điểm tại vô cực O là điểm cộng với bất kỳ điểm nào cũng sẽ ra chính điểm đó

Như vậy, tương ứng với một giá trị x ta sẽ có hai giá trị tọa độ y Điểm (x, –y) ký hiệu là –P  E(R), đƣợc gọi là điểm đối của P với:

Phép cộng trên E(R) đựợc định nghĩa theo phương diện hình học Giả sử có hai điểm phân biệt P và Q, P, Q  E(R) Phép cộng trên nhóm đường cong elliptic là:

Để xác định điểm R trên đường cong elliptic, ta vẽ đường thẳng L nối hai điểm P và Q Đường thẳng này sẽ cắt đường cong E tại ba điểm: P, Q và -R(x, y) Điểm R sẽ có tọa độ là R(x, -y), với tung độ là giá trị đối của y.

Thể hiện phép cộng đường cong elliptic dưới dạng đại số, ta có:

Thuật toán cộng trên đường cong elliptic được thể hiện như sau:

Input: Đường cong elliptic E(R)với các tham số a4, a6  E(R) , Điểm P = (x1, y1)  E(R) và Q = (x2, y2)  E(R)

(1) If P = O then R := Q và trả về giá trị R

(2) If Q = O then R := P và trả về giá trị R

Hình 2.4 Phép nhân đôi trên đường cong elliptic

Xét phép nhân đôi: nếu cộng hai điểm P, Q  E(R) với P = Q thì đường thẳng

L sẽ là tiếp tuyến của đường cong elliptic tại điểm P Trường hợp này điểm –R sẽ là giao điểm còn lại của L với E Lúc đó R = 2P

Phép nhân trên nhóm Ep  a,b thực hiện tương tự như phép lũy thừa modulo trong RSA

Giả sử P3,10E23  1,1 , khi đã 2 P   x 3 , y 3  bằng:

Vì P = Q và x2 x1 nên các giá trị , x 3 và y 3 là:

2 2.10 20 mod 6 3 3mod 23 30 mod 23 7 mod 6 3 7 10 mod 23 34 mod 23 12 x a y p x x x p y x x y p

Phép nhân kP nhận đƣợc bằng cách thực hiện lặp k lần phép cộng

* Thuật toán nhân điểm cho hệ tọa độ Affine

(3) for i = n-1 downto 0 (3.1) Gán Q ← Q + Q (3.2) if b i = 1 then

* Thuật toán nhân điểm cho hệ tọa độ quy chiếu

(2) Biểu diễn P trong hệ tọa độ chiếu: P'

(5) Biểu diễn Q' trong hệ tọa độ affine, ta đƣợc Q

SỐ ĐIỂM TRÊN ĐƯỜNG CONG ELLIPTIC VỚI TRƯỜNG F Q

Việc xây dựng hệ mật mã trên đường cong elliptic bắt đầu bằng cách lựa chọn một đường cong E phù hợp cùng với một điểm cơ sở G trên E Trong bối cảnh này, trường K được xác định là F q Định lý Hasse đóng vai trò quan trọng trong việc đảm bảo tính toán chính xác trong các hệ thống mã hóa này.

N là số điểm của E trên trường F q (trường hữu hạn q phần tử) Khi đó:

|N – (q + 1)|2 q Từ định lý Hasse suy ra #E(F q ) = q + 1 – t trong đó |t|2 q Định nghĩa Bậc của một đường cong elliptic là số điểm của đường cong đó

Bậc của điểm G thuộc E là số k sao cho kG = O; khi k = #E(F q ) thì G là điểm cơ sở của E

2.2 MỘT SỐ SƠ ĐỒ CHỮ KÝ TRÊN ĐƯỜNG CONG

Năm 1976, Diffie và Hellman đã giới thiệu hệ mã hóa khóa công khai đầu tiên, dựa trên độ khó của bài toán DLP, cùng với khái niệm hàm cửa sập một chiều (TOF) Đến năm 1985, Lenstra đã thành công trong việc áp dụng các đường cong elliptic cho các số nguyên, mở ra khả năng sử dụng các đường cong elliptic trong hệ mật mã khóa công khai.

Miller và Koblitz là những người tiên phong trong việc giới thiệu hệ mật mã elliptic, không phát minh ra thuật toán mới nhưng đã chỉ ra ứng dụng của các đường cong elliptic trong hệ thống khóa công khai Vào năm 1985, Miller đề xuất một giao thức trao đổi khóa tương tự như Diffie-Hellman, với tốc độ nhanh hơn 20% so với giao thức này.

Vào năm 1987, Koblitz phát triển một thuật toán mã hóa tương tự như hệ Elgamal và Massey-Omura Năm 1991, Koyama, Maurer, Okamoto và Vanstone giới thiệu sơ đồ mã hóa dựa trên các đường cong Elliptic, có tốc độ thực hiện nhanh gấp 6 lần so với RSA Đồng thời, Kaliski chứng minh rằng các hàm một chiều có cửa sập yêu cầu thời gian hàm mũ để thực hiện phép tính nghịch đảo Menezes, Okamoto và Vanstone đề xuất phương pháp tấn công MOV để giải quyết bài toán EDLP trong một số trường hợp cụ thể Ngay sau đó, Miyaji tìm ra các điều kiện để tránh bị tấn công MOV và đề xuất ứng dụng thực tế của các đường cong elliptic cho sơ đồ chữ ký và định danh trên Smart Card.

Năm 1993, Demytko giới thiệu một thuật toán mới tương tự RSA cho các đường cong Elliptic trên vành Zn, khắc phục những hạn chế của các phiên bản trước Đồng thời, Menezes và Vanstone phát triển phương pháp thực thi trên các thiết bị cứng, nâng cao hiệu suất và tính khả thi trong ứng dụng.

NHÚNG BẢN RÕ VÀO ĐƯỜNG CONG ELLIPTIC

Nhúng bản rõ lên E cho phép biểu diễn các điểm trên E, từ đó thực hiện các tính toán cần thiết Có nhiều phương pháp để thực hiện điều này, trong đó hai phương pháp chính là "nhúng" (embedding) và "mặt nạ" (mask).

Cách 1 Để nhúng m lên E(Z p ) với p là số nguyên tố, chẳng hạn p 3 (mod 4)

Giả sử E(Z p ) được cho bởi phương trình y 2 = x 3 + ax 2 + b và giả sử m là số nguyên thỏa mãn 0  m  p / 1000  1

Thêm 3 chữ số vào m đƣợc x thỏa mãn 1000 m  x  1000 ( m  1 )  p Chúng ta sẽ bổ sung các chữ số khác nhau cho đến khi tìm đƣợc x sao cho f(x) = x 3 + ax + b là một số chính phương trong Z p và y (với f(x) = y 2 mod p ) thỏa mãn y   1 mod p Điểm P m đƣợc tạo thành khi nhúng m lên E là:

Có thể dễ dàng khôi phục lại m từ P m E(Z p )bằng cách loại bỏ 3 chữ số cuối của tọa độ x của điểm P m

Bước đầu tiên là sử dụng bảng chữ cái với N ký tự và chia nó thành các khối có độ dài cố định l Các ký tự được đánh số từ 0 đến N-1, trong đó một khối văn bản w cùng với các số từ 0 đến N-l tạo thành một ánh xạ.

Bước 2 Chọn một giá trị k thích hợp sao cho kN l < q Với mỗi j là phần tử của

F q tính kx w + j Lấy điểm P w đầu tiên mà tọa độ x  kx w , j0 , ví dụ

Bước 3 Khôi phục lại khối bản rõ từ P w bằng cách tính     k x w x

2.2.1.2 Phép mặt nạ (Mask) Để biểu diễn lại bản rõ dạng (m 1 , m 2 ) thành các điểm P m trên E có thể áp dụng phương pháp masking bằng cách nhân m 1 và m 2 với các tọa độ x, y của các điểm trên

E Giả sử có điểm G  E có tọa độ (x G , y G ) thì P m = (m 1 x G , m 2 y G ).

SƠ ĐỒ CHỮ KÝ TRÊN ĐƯỜNG CONG ELLIPTIC

2.2.2.1 Sơ đồ chữ ký ECDSA Để thiết lập sơ đồ chữ ký ECDSA(Elliptic Curve Digital Signature Algorithm), cần xác định các tham số: lựa chọn đường cong E trên trường hữu hạn F q với đặc số p sao cho phù hợp, điểm cơ sở G  E(F q )

Một số khuyến nghị khi lựa chọn các tham số:

1 Kích thước q của trường, hoặc q = p (p > 2) hoặc q = 2 m

2 Hai phần tử a, b thuộc F q xác định phương trình đường cong elliptic: y 2 = x 3 + ax + b (p>2) hoặc y 2 + xy = x 3 + ax 2 + b (p =2)

3 Hai phần tử x G và y G thuộc F q xác định điểm cơ sở G = (x G , y G )

4 Bậc n của điểm G với n > 2 160 và n4 q

1 Chọn số ngẫu nhiên d trong khoảng [2, n – 1] làm khóa bí mật

2 Tính Q = dG làm khóa công khai

1 Chọn một số ngẫu nhiên k, 2  k  n  1

3 Tính r = x 1 mod n Nếu r = 0, quay lại bước 1

1 Kiểm tra r và s có là các số tự nhiên trong khoảng [2, n – 1] không

3 Tính u 1 = mw mod n và u 2 = rw mod n.

5 Nếu X = O thì phủ nhận chữ ký Ngƣợc lại tính v = x X mod n.

6 Chữ ký chỉ đƣợc chấp nhận nếu v = r

Nếu chữ ký (r, s) trên m là đúng thì s = k -1 (m + dr) mod n k  s -1 (m + dr)  s -1 m + s -1 rd  wm + wrd  u 1 + u 2 d (mod n)

Vì vậy, u 1 G + u 2 Q = (u 1 + u 2 d)G = kG, và vì vậy v = r

2.2.2.2 Sơ đồ chữ ký Nyberg - Rueppel

Giả sử E là một đường cong Elliptic trên trường Z p (p>3 và nguyên tố) sao cho

E chứa một nhóm con cyclic H trong đó bài toán logarith rời rạc là “khó”

Với P * p x * p , CExZ * p xZ * p , ta định nghĩa: K  { ( E Q a R , , , ) :  R a Q với }

QE Các giá trị và R là công khai, a là bí mật

Với K  ( , , , ) E Q a R , chọn một số ngẫu nhiên kZ |H | Khi đó, với

(x x Z p xZ p x  ta định nghĩa sig K (x,k)(c,d), trong đó:

Tất cả các sơ đồ chữ ký yêu cầu băm văn bản trước khi thực hiện ký Chuẩn P1363 của IEEE khuyến nghị sử dụng các hàm băm như SHA-1, được định nghĩa bởi NIST, hoặc RIPEMD-160, theo tiêu chuẩn ISO-IEC Việc sử dụng các hàm băm này giúp giảm khả năng tìm thấy hai văn bản có cùng giá trị băm, đồng thời làm cho chữ ký trên văn bản gốc trở nên gọn nhẹ hơn.

2.2.2.3 Sơ đồ chữ ký mù Harn trên EC

Năm 1994, Harn đã công bố một sơ đồ chữ ký mù tựa nhƣ sơ đồ ECDSA Chữ

Chọn các tham số cho đường cong Elliptic

(1) Chọn số nguyên tố p và số nguyên n

(2) Với 2 phần tử a 1 , a 2 của GF(p n ), xác định phương trình của E trên GF(p n ) (y 2 x 3 a 1 xa 2 trong trường hợp p>3) với 4 a 1 3  27 a 2 2  0

(3) Với 2 phần tử x G và y G trong GF(p n ) xác định một điểm G = (x G , y G ) trên

E(GF(p n )) (G O với O là điểm gốc)

(4) Giả sử điểm G có bậc q

Việc sinh khóa bao gồm:

(1) Chọn một khóa bí mật d là số nguyên ngẫu nhiên trong [2, q – 1]

(2) Tính khóa công khai Q, là một điểm trên E sao cho Q = dG

Giả sử Bob yêu cầu Alice ký một văn bản m 0, trong đó m là đại diện của văn bản này (m = H(m 0 ) với H là một hàm băm) Giao thức ký được thực hiện thông qua việc Alice sử dụng khóa riêng của mình để ký lên giá trị băm m, tạo ra chữ ký số Chữ ký này sau đó được gửi cho Bob, cho phép Bob xác minh tính toàn vẹn và xác thực của văn bản m 0 bằng cách sử dụng khóa công khai của Alice.

(1) Alice sinh ra cặp khóa (k,R) theo cách sau: chọn ngẫu nhiên k[2,q1]và tính R kG(x k ,y k ) Đặt r = x k , rồi gửi rvà Rcho Bob

(2) Bob chọn các tham số làm mù a , b  [ 1 , q  1 ] , tính R trên E sao cho

R = aR+ bG = (x k, y k ) và tính r = c(x k ) và m(mr)a 1 r Sau đó gửi mcho Alice (m là m sau khi đã bị làm mù)

(3) Alice tính s d(mr)k(modq), rồi gửi scho Bob

(4) Bob nhận đƣợc s , xóa mù để có đƣợc chữ ký s trên m bằng cách tính s  a s  b

Cặp (r, s) là chữ ký trên m

Cặp (r, s) là một chữ ký Harn của thông điệp m và sơ đồ ký trên là một sơ đồ chữ ký mù trên đường cong elliptic

(1) Tìm một điểm V trên E sao cho sG – (m + r)Q = (x v , y v )

Nếu q, x, r, v thỏa mãn phương trình q x r = v, thì (r, s) được coi là chữ ký hợp lệ Để chứng minh rằng giao thức này tạo ra chữ ký “mù”, chúng ta chỉ ra rằng mỗi người ký có một cặp duy nhất (a, b) làm tham số mù, trong đó a, b thuộc đoạn [1, q - 1] Với các tham số R, k, r, m, s và chữ ký hợp lệ (r, s) của m, chúng ta có thể xác nhận tính hợp lệ của chữ ký.

Ta phải chứng minh: R  a R  bG Thực vậy,

G r ad r a r m adG sG k r d m d aG sG G k a G s a sG G k a bG

Xét việc tạo chữ ký mù Harn trên đường cong elliptic y² = x³ + x + 13 trong trường nguyên tố Z₃₁ với điểm cơ sở G = (9, 10) Tổng số điểm trên đường cong E(Z₃₁) là 34, và G là phần tử có bậc 34, do đó q = 34 Các điểm trên E được liệt kê trong bảng 3.3.2.

Khóa bí mật d = 11, khi đó khóa công khai Q = dG = 11G = (22, 22)

Giả sử Bob có thông điệp m 0 với đại diện là m = 17 và cần Alice ký lên m sao cho

Alice không biết nội dung m

(1) Khi nhận đƣợc yêu cầu ký từ Bob, Alice chọn ngẫu nhiên k[2,q1]= 20 và tính R  k G = 20G = (26, 10), r = 26 Alice gửi rvà Rcho Bob

(2) Bob chọn các tham số làm mù a,b[1,q1] với a = 5, b = 7 Tính R trên E với

R = aR + bG = 5R + 7G = 5G = (25, 16), r = 25 Bob làm mù m thành mvới r a r m m (  ) 1  = (17 + 25)5 -1 – 26 (mod 34) = 30 Bob gửi m = 30 cho Alice

Xác minh tính hợp lệ của chữ ký

Bob muốn xác nhận rằng anh có chữ ký của Alice trên m = 17 và chữ ký này thuộc dạng (25, 25) Các bước chứng minh được thực hiện như sau:

(1) Tìm một điểm V trên E sao cho sG – (m + r)Q = (x v , y v ) = 25G – (17 + 25)Q 25G – 8Q = 25G – 88G = 5G (mod 34) = (25, 16)

? x v Nếu Bob cung cấp một chữ ký giả (r‟, s‟)  (r, s) thì điều kiện kiểm tra r  ? x v không thỏa mãn nên chữ ký sẽ bị phủ nhận

2.2.2.4 Sơ đồ chữ ký mù bội Harn trên EC Đa chữ ký hiểu là chữ ký được tạo thành bởi nhiều người ký Có văn bản cần được ký bởi một số người thay vì một người nhằm bảo đảm tính an toàn Những người ký không biết về nội dung văn bản ký

Việc lựa chọn các tham số cho đường cong elliptic trong sơ đồ chữ ký Harn có sự tương đồng nhất định Giả sử có t người ký, được ký hiệu là U_i với i = 1, 2, , t Quá trình sinh khóa được thực hiện thông qua một số bước cụ thể.

(1) Mỗi người ký U i chọn ngẫu nhiên một khóa bí mật d i là một số nguyên thuộc

(2) Khóa công khai của người ký U i là điểm: Q i = d i G = ( i i d d y x , ), i  1  , t

(3) Khóa công khai cho tất cả người ký là: Q = Q 1 +…+ Q t = dG = (x d , y d ) với d = d 1 + …+ d t (mod q)

(1) Người ký U i sinh một lần cặp (k i ,R i ) bằng cách chọn ngẫu nhiên k i [2,q1] và tính ( , ) i i k k i i kG x y

R   U i đặt r i k i x , i = 1,…, t rồi gửi r i và R i cho Ban thƣ ký

(2) Ban thƣ ký chọn các tham số làm mù a , b  [ 1 , q  1 ], tìm điểm R trên E sao cho

R   trong đó R R R và Q = Q1 +…+ Qt Ban thƣ ký tính rc(x k )(modq)và m (mrb)a 1 r Sau đó, gửi m và r đến cho từng người ký U i

(3) U i tính chữ ký s i  d i ( m  r )  k i (mod q ), i=1,…, t , gửi s i tới Ban thƣ ký

(4) Ban thƣ ký tính ( ) ( , ) i i e e i i G m r Q x y s    và kiểm tra (mod )

Chữ ký mù nhóm ECC là cặp (r, s) trong đó s  s a (mod q ) và

Cặp (r, s) là chữ ký đa thành viên trên thông điệp m Để xác minh tính hợp lệ của chữ ký đa (r, s) trên m, cần thực hiện các bước xác minh cụ thể.

(1) Tìm một điểm trên E sao cho sG(mr)Q(x e ,y e )

? q x r  e Nếu đúng thì (r, s) đƣợc chấp nhận

Để chứng minh rằng giao thức ký tạo ra chữ ký “mù”, cần xác minh rằng với mỗi người ký, tồn tại duy nhất một cặp tham số (a, b) làm mù, từ đó dễ dàng thấy rằng sG - (m + r)Q = R.

, b  q  a Với các R i ,k i ,r i ,s i ,m,r và cặp chữ ký hợp lệ (r, s) của thông điệp m, chúng ta có: a ss  1 (modq), b  ( m  r ) a  m  r (mod q )

Ta phải chỉ ra rằng RaRbQ

MỘT SỐ PHƯƠNG PHÁP TẤN CÔNG CHỮ KÝ ECC

2.3.1 Phương pháp tấn công “baby-step giant - step” Đây là phương pháp tấn công đầu tiên lên hệ mật mã ECC do Shanks đưa ra, và thực hiện với thời gian là hàm mũ Nó giải bài toán DLP trong trường nguyên tố Z p đƣợc mở rộng cho bài toán EDLP

Bài toán Tìm k sao cho kG = Q trên E(F q ) với #E(F q ) = N, giả sử k tồn tại thực sự

3 Với i = 0 đến i = m-1 tính (và lưu lại) iG

4 Với j = 0 đến j = m-1 tính (và lưu lại) Q – jmG

5 Sắp xếp danh sách trong bước 3 và 4 theo một thứ tự nhất định

6 So sánh các danh sách ở các bước 3 và 4 cho đến khi tìm được cặp i, j thỏa mãn iG = Q – jmG

7 Kết quả trả lại là k i + jm (mod N)

Vì chúng ta chọn m thỏa mãn m 2 > N nên sẽ có k < m 2 Đặt k 0 k (mod m), 0k 0 m Đặt k 1 = (k – k 0 ) / m Ta sẽ có: k = k 0 + mk 1 , với 0k 1 m

Trong thuật toán, chúng ta tìm tất cả các giá trị i trong khoảng k0 và j trong khoảng k1 cho đến khi tìm được i, j thỏa mãn điều kiện iG = Q – jmG Điều này dẫn đến (i + jm)G = Q, hay k = i + jm Sự tồn tại của k cho thấy k0 và k1 cũng tồn tại Thời gian thực hiện của thuật toán này phụ thuộc vào độ phức tạp tính toán.

Bước 1 cần O(log N) Bước 2 và bước 3 cần O(m+1) = O( N ) Bước 4 cần

Thuật toán sắp xếp trong bước 5 có độ phức tạp thời gian O(log(N) N), trong khi bước 6 và bước 7 đều thực hiện trong O(N) thời gian Đối với N đủ lớn, các yếu tố logarith sẽ được bỏ qua.

DLP là một bài toán khó giải, và thời gian thực hiện của thuật toán phụ thuộc vào N theo hàm mũ Điều này khiến cho thuật toán trở nên quá chậm, vì thời gian xử lý tăng theo hàm mũ với độ dài dữ liệu đầu vào N.

2.3.2 Phương pháp tấn công MOV

Phương pháp tấn công MOV (Menezes, Okamoto, và Vanstone) chuyển đổi bài toán logarit rời rạc trên đường cong elliptic E(F q ) thành bài toán logarit rời rạc trên trường F q m, với m nhỏ, tạo điều kiện cho việc tấn công bằng phương pháp chỉ số Bài viết sẽ bắt đầu bằng việc định nghĩa cặp Weil cho các đường cong elliptic E(F).

Xét đường cong elliptic E(F) với N là một số nguyên không chia hết cho đặc số của F Tập hợp các điểm trên đường cong E được ký hiệu là E[N] Nhóm các nghiệm thứ N trong F được định nghĩa là  N = { x ∈ F | x N = 1 } Do đó,  N là nhóm các nghiệm thứ N trong F, trong khi đặc số của F không chia hết cho N.

= 1 không có nghiệm kép, nghĩa là có N nghiệm phân biệt trong F Định nghĩa 3.1

Một cặp Weil là một ánh xạ: e N :E[N]xE[N]   n thỏa mãn:

1 e N là song tuyến tính với mọi biến

2 eN là không suy biến với mọi biến Nghĩa là, nếu e N (S, T) = 1 với mọi S, thì

T = O, và nếu e N (S, T) = 1 với mọi T thì S = O

5 Nếu  là một phần tử đặc biệt của F đóng vai trò là các hệ số của E, thì e N ( S,

Tìm k thỏa mãn kG = Q trên E(F q ) với #E(F q ) = N và giả sử k tồn tại

Sử dụng phép làm yếu bài toán logarith rời rạc trên đường cong E(F q ) thành bài toán logarith rời rạc trên F q m

Khi (d 1 , d 2 , …,d k ) = N, thực hiện các bước sau, sau mỗi bước tăng i lên 1

1 Chọn một điểm ngẫu nhiên S i E(F q m )

5 Giải bài toán logarith rời rạc  1 k i i =  2 i trong trường F q m và tìm được k i (mod d i )

Sử dụng giá trị k i (mod d i ) để tìm k (mod N) với k k i (mod d i )  i

Giá trị k chính là kết quả cần tìm

Chứng minh Ở bước 1 và 2, ta chọn một điểm và tính bậc của nó Bước 3 tìm T i Đặt )

 với R là một điểm tùy ý trên E(F q m )

  trong F q m Đặt kG = Q, và định nghĩa l i thỏa mãn k l i (mod d i )

Ta có: e N (kG, T i ) = e N (Q, T i ) e N (G, T i ) k = e N (Q, T i )   1 k i  2 i Vì  1 d i 1 nên  2 i  1 k i i (mod d i )  l i  k i (mod d i ) và k phải bằng k i (mod d i ) Nhƣ vậy, việc tìm k i sẽ giúp cho việc tìm k Độ phức tạp thời gian

Thời gian chạy của thuật toán phụ thuộc vào việc tìm kiếm k i, điều này trở nên dễ dàng khi có các k i Thời gian tìm kiếm k i lại phụ thuộc vào kích thước của trường F q m; khi m càng lớn, độ phức tạp tính toán càng tăng Hiện tại, không có tiêu chuẩn chung nào để lựa chọn giá trị m phù hợp cho tất cả các đường cong elliptic.

Quay trở lại bài toán tính độ phức tạp, dựa trên đặc điểm E(F q m ) 

Z  với n 1 , n 2 thỏa mãn n 1 |n 2 B 1 , B 2 là các điểm trên E(F q m ) với các bậc n 1 và n 2 Bất kỳ điểm

Mỗi số nguyên tố p e ||N có thể biểu diễn dưới dạng a 1 B 1 + a 2 B 2, với a 1 và a 2 là các hệ số bất kỳ Nếu p là một số nguyên tố và p e |n 2, thì điều này dẫn đến p e |M i, trong đó M i là bậc của S i Do đó, p e |d i = gcd(M i , N) Vì S i được chọn ngẫu nhiên, nên a 2 cũng được chọn ngẫu nhiên, dẫn đến xác suất p không nguyên tố cùng nhau với a 2 là 1 – 1/p Từ đó, xác suất để p e |d i là ít nhất 1 – 1/p cho mọi i và mọi p e ||N.

Xác suất này đủ thấp để chỉ có một vài d i cần cho p e |lcm(d 1 , d 2 ,…, d k ) đúng với mọi p

Vì vậy chúng ta không cần lặp các bước của thuật toán quá nhiều lần

MOV là thuật toán hàm mũ nhỏ đầu tiên để giải bài toán EDLP với k nhỏ

Tính hiệu quả của tấn công MOV dựa vào sự đẳng cấu giữa đường cong elliptic và trường hữu hạn khi gcd(#E(F_q), q) = 1 Tấn công này chỉ áp dụng hiệu quả cho lớp các đường cong supersingular, nơi tồn tại k ≤ 6 Đối với các đường cong elliptic nonsupersingular, giá trị k quá lớn, khiến tấn công MOV không khả thi.

Miyaji đã chứng minh rằng phép làm yếu có hiệu quả đối với các đường cong elliptic trên trường F2r, nhưng các đường cong elliptic trên trường Fp (với p là số nguyên tố lớn) lại không bị ảnh hưởng bởi phương pháp tấn công này Hơn nữa, ông cũng đề xuất một phương pháp xây dựng đường cong elliptic nhằm đảm bảo rằng việc làm yếu EDLP về DLP là không thể thực hiện được Do đó, không phải tất cả các hệ mật mã dựa trên đường cong elliptic đều dễ bị tấn công bởi phương pháp MOV.

2.3.3 Các thuật toán tấn công khác

Nhiều thuật toán tấn công đã được chứng minh là không hiệu quả với hệ mật mã trên đường cong elliptic Trong khi thuật toán tấn công chỉ số có thể giải bài toán DLP, nó lại không áp dụng được cho EDLP Giao thức trao đổi khóa trên đường cong elliptic, tương tự như giao thức Diffie-Hellman, có khả năng chống lại các cuộc tấn công của Western, Miller, và các tấn công thời gian hàm mũ nhỏ của Adleman Ngoài ra, thuật toán tương tự RSA của Demytko cũng được coi là an toàn trước các tấn công đẳng cấu.

LỰA CHỌN ĐƯỜNG CONG ELLIPTIC PHÙ HỢP

Việc chọn đường cong elliptic ảnh hưởng đến tốc độ, hiệu quả, độ dài khóa và tính an toàn của hệ mật mã Mặc dù các tham số E, K và điểm cơ sở G là cố định và công khai, nhưng lựa chọn chúng một cách phù hợp là bước quan trọng nhất trong quá trình thiết lập hệ thống mã hóa.

Trước hết chúng ta xem xét sự ảnh hưởng của trường K đến cấu trúc nhóm của

E(K) và các hệ mật mã trên E(K)

Đường cong elliptic trên trường hữu hạn tạo thành nhóm Abel, được ứng dụng trong mật mã học, với F2r là một ví dụ cho phép tính nhanh và dễ triển khai trên thiết bị cứng Tuy nhiên, các đường cong trên F2r dễ bị tấn công bởi MOV, trong khi các đường cong trên trường nguyên tố Fp (với p là số nguyên tố lớn) có khả năng chống lại kiểu tấn công này Do đó, đường cong elliptic trên trường nguyên tố Fp và trường Fqn sở hữu các tính chất giúp chúng thực thi an toàn trên các thiết bị.

Một điểm quan trọng cần lưu ý là việc tính số điểm trên #E(K) Số điểm #E(K) thích hợp có thể là điều kiện cho phép thực hiện tấn công Pohlig – Hellman Để tính số điểm #E trên trường hữu hạn F_q với đặc số khác 2, có thể sử dụng thuật toán đơn định thời gian đa thức Schoof.

Khi r nhỏ, việc tính toán #E(F 2r) có thể nhanh hơn so với #E(F p) khi p lớn hơn đáng kể so với 2r Tuy nhiên, khi giá trị của r tăng lên, thời gian tính toán #E(F 2r) sẽ lâu hơn so với #E(F p).

2.4.2 Dạng của đường cong elliptic

Đường cong elliptic trên trường F q được chia thành hai loại chính: supersingular và non-supersingular Đối với trường F q có đặc số 2 (g = 2 m), đường cong supersingular được hình thành từ tất cả các cặp nghiệm (x, y) của phương trình y 2 + ax = x 3 + bx + c với a, b, c thuộc F q và a = 0 (mod q), cùng với điểm trung hòa O Ngược lại, đường cong non-supersingular được xác định bởi các cặp nghiệm (x, y) của cùng phương trình với b = 0 (mod q) và điểm trung hòa O.

Menezes và Vanstone đã phát hiện ra những lợi ích của các đường cong elliptic supersingular trong các hệ mật mã, đặc biệt là trên trường F 2 r Tuy nhiên, cần lưu ý rằng các đường cong supersingular có thể bị tấn công thông qua phương pháp MOV.

Các đường cong nonsupersingular mang lại ưu điểm vượt trội trong việc cung cấp độ bảo mật tương đương với các đường cong supersingular nhưng sử dụng các trường nhỏ hơn Độ dài khóa ngắn của chúng cho phép triển khai hiệu quả trên các thiết bị như smart card Hơn nữa, các đường cong này có khả năng chống lại các cuộc tấn công MOV, chẳng hạn như với nhóm con cyclic cỡ 2^160.

Có nhiều phương pháp để lựa chọn các đường cong elliptic, trong đó phương pháp tự nhiên và đơn giản nhất là chọn ngẫu nhiên Việc chọn ngẫu nhiên một đường cong elliptic E trên trường giúp đảm bảo tính ngẫu nhiên và đa dạng trong các ứng dụng toán học và mật mã học.

K và một điểm cơ sở P  E K được chọn và cố định trước Phương pháp chọn ngẫu nhiên Koblitz cho các đường cong elliptic trên trường F q (với q lớn ) như sau:

1 Chọn ngẫu nhiên 3 phần tử từ F q là x, y, a

3 Kiểm tra 4a 3 27b 2 0để đảm bảo phương trình x 3 + ax + b = 0 không có nghiệm kép

4 Nếu điều kiện trên không thỏa mãn quay lại bước 1

5 Còn lại, đặt P = (x, y) và đường cong y 2 = x 3 + ax + b là đường cong cần chọn

Phương pháp chọn ngẫu nhiên Koblitz

Phương pháp này có thể tạo ra các đường cong không đáp ứng một số yêu cầu nhất định Một kỹ thuật cải tiến là xây dựng các đường cong với các tính chất đã được xác định trước Ngoài ra, có thể lựa chọn những đường cong để phát triển các hệ mã hóa không phụ thuộc vào bài toán EDLP, chẳng hạn như các hệ elliptic dựa trên RSA.

Các hệ mật mã elliptic hoạt động dựa trên các nhóm con cyclic của E, với điểm P là phần tử sinh Do đó, việc lựa chọn điểm P phù hợp là vô cùng quan trọng để đảm bảo tính bảo mật và hiệu quả của hệ thống.

MỘT SỐ CHUẨN SỬ DỤNG HỆ MẬT ECC

Việc thiết lập một tiêu chuẩn chung cho các hệ thống mã hóa, giao thức và giao diện là rất cần thiết Chuẩn hóa mang lại ba lợi ích chính: nâng cao tính tương thích, cải thiện khả năng bảo mật và giảm thiểu chi phí phát triển.

(1) Cho phép kết hợp phần cứng và phần mềm của nhiều nhà cung cấp khác nhau

(2) Đưa ra chuẩn cho việc đảm bảo an toàn các hệ thống dưới khía cạnh mật mã học

(3) Cho phép có thiết kế chuẩn cho các môi trường ứng dụng khác nhau

Các đường cong elliptic đã được các nhà toán học nghiên cứu kỹ lưỡng trong hơn 10 năm và đã được các tổ chức chuẩn hóa khảo sát từ năm 1995, đảm bảo tính tin cậy của chúng đã được kiểm chứng.

Nỗ lực chuẩn hóa các hệ mật mã khóa công khai đã được Viện nghiên cứu điện và điện tử IEEE khởi xướng từ nhiều năm trước với phiên bản P1363, cung cấp định dạng và thủ tục cho ba hệ thống mã hóa khác nhau bao gồm xác thực, toàn vẹn và tin cậy ISO/IEC SC27 cũng đã bắt đầu xem xét các chuẩn cho ECC, trong khi ANSI X9.25 giới thiệu sơ đồ chữ ký ECC ECDSA (Elliptic Curve Digital Signature Algorithm) và ANSI X9.63 quy định các chuẩn về thỏa thuận và truyền khóa ECC được tích hợp vào các chuẩn mới của Internet cho bảo mật tầng IP như IPSEC, ISAKMP và Oakley, cũng như trong các chuẩn công nghiệp như SET (Secure Electronic Transaction).

ANSI X9 ECC đã đƣợc thử nghiệm trong 2 lĩnh vực bởi ANSI ASC X9

The article discusses financial services and highlights key standards such as ANSI X9.62, which pertains to ECDSA digital signatures, and ANSI X9.63, which focuses on the ECC Key Agreement protocol (ECKA) It also addresses transport protocols under ECTP and references ANSI TG-17, which provides technical guidelines on mathematical principles.

ATM Forum cung cấp các cơ chế bảo mật cho mạng ATM (Chế độ Truyền thông Không đồng bộ) Các dịch vụ bảo mật này bao gồm tính tin cậy, tính xác thực, toàn vẹn dữ liệu và điều khiển truy cập Hệ thống ECC là một trong những công nghệ được hỗ trợ trong các giải pháp bảo mật này.

Certicom đã phát hành tài liệu về mã hóa ECC, trong đó mô tả cách sử dụng khóa ECC trong khung X.509 Tài liệu này định nghĩa định dạng chứng chỉ và danh sách thu hồi chứng chỉ Các tiêu chuẩn SEC 1 cho mã hóa ECC bao gồm các sơ đồ mã hóa khóa công khai, đặc biệt là các sơ đồ chữ ký điện tử, mã hóa và thỏa thuận khóa SEC 2 cung cấp các tham số khuyến nghị cho mã hóa ECC, cùng danh sách các tham số tương ứng với các cấp độ bảo mật khác nhau.

FSTC (Financial Services Technology Consortium) tập trung vào các hệ thống thanh toán điện tử và dịch vụ tài chính liên quan Các hình thức thanh toán điện tử có thể được thực hiện qua nhiều thiết bị như máy tính cá nhân, điện thoại thông minh, máy ATM và các hệ thống kiểm toán Để bảo mật thông tin, ECC được sử dụng để mã hóa email trong quá trình gửi các chứng từ điện tử.

IEEE P1363 ECC đã đƣợc đƣa ra trong chuẩn phác thảo IEEE P 1363

Các chuẩn cho mật mã khóa công khai bao gồm mã hóa, chữ ký số và các cơ chế thỏa thuận khóa Đường cong Elliptic có thể được định nghĩa theo modulo p hoặc trên trường F2^m, nơi có 2^m phần tử.

IETF (Internet Engineering Task Force) mô tả giao thức thỏa thuận khóa là một biến thể của giao thức thỏa thuận khóa Diffie-Hellman Giao thức này cho phép sử dụng nhiều nhóm khác nhau, bao gồm cả nhóm đường cong Elliptic Đặc biệt, các nhóm trên đường cong Elliptic được khuyến nghị sử dụng là các trường F2^155 và F2^210.

ISO/IEC Bản phác thảo ISO/IEC 14888, trong phụ lục 3, các cơ chế dựa trên chứng chỉ, các thuật toán ký tương tự như DSA

NIST (Viện nghiên cứu chuẩn quốc tế - National Institue of Standards)

NIST cũng có các đặc tả cho ECC trong MISPC

OTP 0.9 Open Trading Protocol là một framework các giao thức thanh toán

OTP cung cấp bản sao điện tử an toàn cho các tài liệu giấy phục vụ cho thương mại, mua bán Hệ thống này sử dụng ECDSA để hỗ trợ các sơ đồ chữ ký điện tử trong OTP, đảm bảo tính bảo mật và xác thực cho giao dịch.

Chuẩn SET (Secure Electronic Transactions) được phát triển nhằm bảo vệ các giao dịch thẻ tín dụng trực tuyến ECC đang được xem xét như một tiêu chuẩn mới cho thương mại điện tử, mang lại nhiều lợi ích đáng kể cho các ứng dụng quan trọng trong lĩnh vực này.

WAP (Wireless Application Protocol) cung cấp cơ chế truy cập Internet an toàn cho các thiết bị không dây như điện thoại và thiết bị đầu cuối Kiến trúc mạng của WAP cho phép các ứng dụng sử dụng nhiều lựa chọn giao thức truyền khác nhau, tương thích giữa các thiết bị Bên cạnh đó, WAP cũng hỗ trợ mã hóa ECC trong tầng bảo mật WTLS (Wireless Transport Layer Security).

CHỮ KÝ ECC TRONG TIỀN ĐIỆN TỬ

CHƯƠNG TRÌNH MÔ PHỎNG GIẢI THUẬT CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG