Giới thiệu lý thuyết Số-Mã

Phép chia (divisors)

b<>0, chúng ta nói a chia hết cho b nếu a=mb với m bất kỳ. a,b,m là các số nguyên. Nếu a chia hết cho b, chúng ta ký hiệu b|a. Nếu b|a ta nói b là ước số của a.

Chúng ta xem xét một số tính chất sau đây:

• Nếu a|1 thì a= ±1 size 12{ +- 1} {}
• nếu a|b và b|a thì a= ±b size 12{ +- b} {}
• b<>0=> b|0
• b|g và b|h thì b|(mg+nh) với m, n là các số nguyên tùy ý.

Số nguyên tố (prime)

Một số nguyên p>1 là số nguyên tố khi các ước số của nó là ±1 size 12{ +- 1} {} và ±p size 12{ +- p} {}.

Tính chất quan trọng:

Bất kỳ số nguyên a >1 có thể phân tích thành dạng duy nhất tích luỹ thừa của các số nguyên tố.

a= p1α1 size 12{p rSub { size 8{1} } rSup { size 8{α rSub { size 6{1} } } } } {}p2α2 size 12{p rSub { size 8{2} } rSup { size 8{α rSub { size 6{2} } } } } {}… ptαt size 12{p rSub { size 8{t} } rSup { size 8{α rSub { size 6{t} } } } } {}

Trong đó, p_i là các số nguyên tố và α size 12{α} {}_i>0.

Ví dụ: 91=7X13;11011=7X11²X13; 3600=2⁴3²5²

Ước số chung lớn nhất (greatest common divisor):

gcd(a, b)=max[k, sao cho k|a và k|a]

(xem thêm [12])

Giải thuật Euclid:

gcd(a, b)=gcd(b, a mod b)

Số nguyên tố cùng nhau (relatively prime)

a, b gọi là nguyên tố cùng nhau nếu gcd(a, b)=1

Phép toán Modulo

a=qn+r (0<=r<n, q=[n|a])

a, b là đồng dư modulo n nếu (a mod n)=(b mod n)

(xem thêm [12])

Định lý Fermat và định lý Euler

Định lý Fermat:

Nếu p là số nguyên tố và a là số nguyên dương không chia hết cho p, thì:

a^p-1 size 12{ equiv } {} 1 mod p

Định lý Euler:

Với mọi a và n nguyên tố cùng nhau, ta có:

a^{φ(n) size 12{φ ( n ) } {}} size 12{ equiv } {} 1 mod n

Trong đó, trường hợp đặc biệt nếu n là số nguyên tố: φ(n)=n−1 size 12{φ ( n ) =n - 1} {}

Bài toán logarit rời rạc

Bài toán logarit rời rạc trong Z_n:

Cho I = n,α,β size 12{ left (n,α,β right )} {}, trong đó n là số nguyên tố, α∈Zn size 12{α in Z rSub { size 8{n} } } {} là phần tử nguyên thủy và β∈Zn size 12{β in Z rSub { size 8{n} } rSup { size 8{*} } } {}. Tìm một số nguyên a, 0≤a≤n−2 size 12{0 <= a <= n - 2} {}, sao cho:

Chúng ta có: a=logαβ size 12{a="log" rSub { size 8{α} } β} {}

Định nghĩa sơ đồ chữ ký điện tử

Như chúng ta thấy, trong mô hình truyền thống [1], xác thực mã cung cấp một phương tiện để phát hiện ra các đoạn tin lừa dối đưa vào bởi tin tặc trung gian. Tuy nhiên, xác thực mã không đủ cung cấp bằng chứng cho đối tượng thứ 3 (trọng tài) đưa ra quyết định về việc A hay B đã gửi một bản tin nào đó khi có xảy ra tranh chấp. Vì vậy, xác thực mã được sử dụng rất hạn chế trong lĩnh vực thương mại điện tử [1] khi khách hàng cần được bảo đảm rằng các nhà buôn không thể làm giả các đơn hàng và các nhà buôn cần sự ràng buộc về mặt trách nhiệm khi khách hàng thực hiện các đơn hàng. Trong các trường hợp như vậy, một chữ ký điện tử là cần thiết.

Một sơ đồ chữ ký điện tử bao gồm một giải thuật chữ ký và một giải thuật kiểm chứng. Một chữ ký của một tài liệu là một giá trị phụ thuộc vào nội dung của tài liệu và bí mật lưu giữ bởi người ký (nghĩa là một khoá bí mật) kết hợp tài liệu với một thực thể (nghĩa là một khoá công khai để kiểm chứng). Giải thuật kiểm chứng thường sử dụng tài liệu và khoá kiểm chứng như đầu vào, tuy nhiên trong các trường hợp ngoại lệ, tài liệu hoặc các phần của tài liệu có thể được khôi phục từ chữ ký. Các tính chất của chữ ký điện tử được trình bày trong [12].

Chúng ta thấy rõ ràng mô hình mật mã khoá công khai là tự nhiên với sơ đồ chữ ký điện tử [11]. Định nghĩa hình thức sơ đồ chữ ký điện tử được giới thiệu trong [11] như sau:

Định nghĩa : Một sơ đồ chữ ký là một bộ 5 (P, A, K, S, V), thỏa mãn các điều kiện sau đây:

1. P là tập hữu hạn các bản tin
2. A là một tập hữu hạn các chữ ký
3. K là không gian khóa, là tập hữu hạn các khóa
4. Với mỗi K size 12{ in } {}K, tồn tại một giải thuật ký sigK∈S size 12{ ital "sig" rSub { size 8{K} } in S} {}và một giải thuật kiểm chứng liên đới verK∈V size 12{ ital "ver" rSub { size 8{K} } in V} {}. Mỗi sigK: size 12{ ital "sig" rSub { size 8{K} } :} {}P→ size 12{ rightarrow } {}A và verK: size 12{ ital "ver" rSub { size 8{K} } :} {}PxA→ size 12{ rightarrow } {}{true, false} là các hàm sao cho công thức sau thỏa mãn với mọi mọi x size 12{ in } {}P vàvới mọiy size 12{ in } {}A:

true nếu y=sig_K(x)false nếu y size 12{ <> } {}sig_K(x) verK(x,y) size 12{ ital "ver" rSub { size 8{K} } ( x,y ) } {} =

Sơ đồ chữ ký El Gamal

Chọn n là số nguyên tố sao cho bài toán logarit rời rạc trong Z_n không có lời giải và chọn một phần tử nguyên thủy α∈Zn size 12{α in Z rSub { size 8{n} } rSup { size 8{*} } } {}. Đặt P= Zn size 12{Z rSub { size 8{n} } rSup { size 8{*} } } {}, A= Zn size 12{Z rSub { size 8{n} } rSup { size 8{*} } } {} x Zn−1 size 12{Z rSub { size 8{n - 1} } } {} và định nghĩa:

K={ n,α,a,β:β≡αa(modn) size 12{ left (n,α,a,β right ):β equiv α rSup { size 8{a} } ( "mod"n ) } {}}

Công khai giá trị n,α,β size 12{ left (n,α,β right )} {}, giữ bí mật a.

Với K = n,α,a,β size 12{ left (n,α,a,β right )} {} và một giá trị ngẫu nhiên (bí mật) k∈Zn−1 size 12{k in Z rSub { size 8{n - 1} } rSup { size 8{*} } } {}, định nghĩa:

Trong đó: γ=αkmodn,δ=(x−aγ)k−1mod(n−1) size 12{γ=α rSup { size 8{k} } "mod"n,δ= ( x - aγ ) k rSup { size 8{ - 1} } "mod" ( n - 1 ) } {}

Với x,γ∈Zn size 12{x,γ in Z rSub { size 8{n} } rSup { size 8{*} } } {} và δ∈Zn−1 size 12{δ in Z rSub { size 8{n - 1} } } {}, định nghĩa: