Căn nguyên thủy và ứng dụng

CĂN NGUYÊN THUỶ 4

Định lý Euler

1.1.1 Định nghĩa Cho n là số tự nhiên khác không Hàm số Euler (n) là hàm số số học có giá trị tại n bằng số các số tự nhiên khác 0, không vượt quá n và nguyên tố cùng nhau với n:

Từ định nghĩa trên đây, ta có ngay hệ quả:

2) Số tự nhiên p  1 là số nguyên tố khi và chỉ khi    p   p 1

Thật vậy, ta có m 1 1   và  m 1 m  ,     1 m ,  1 nên từ 1 tới m có ít nhất hai số nguyên tố cùng nhau với m, do đó    m  1

1.1.2 Định nghĩa Hệ thặng dư đầy đủ môđun n (viết tắt là modn) là một tập hợp gồm n số nguyên đôi một không đồng dư với nhau theo modn

Ví dụ Các tập hợp  0 1 2 3 4 , , , ,  ,  5 4 3 2 1 , , , ,      là các hệ thặng dư thu gọn mod5

1.1.3 Định lý Hàm số Euler    n là hàm có tính chất nhân, nghĩa là với m và n là hai số nguyên dương nguyên tố cùng nhau, ta có:        mn   m  n

Chứng minh Ta sắp xếp tất cả các số nguyên dương không vượt quá tích mn thành bảng số sau đây:

Giả sử \( r \) là số nguyên dương không vượt quá \( m \) và \( (m,r) = d > 1 \) Khi đó, trong hàng thứ \( r \) không có số nào nguyên tố cùng nhau với \( mn \) Để tính giá trị \( \phi(mn) \), ta chỉ cần xem xét các số trong hàng thứ \( r \) với \( (m,r) = 1 \), vì các số này đều nguyên tố cùng nhau với \( m \) Hơn nữa, các số trong hàng này tạo thành một hệ thặng dư đầy đủ mod \( n \), tức là có đúng \( \phi(n) \) số trong hàng này nguyên tố cùng nhau với \( n \) Do đó, trong mỗi hàng này có \( \phi(n) \) số nguyên tố cùng nhau với \( mn \) và tổng cộng có \( \phi(m) \) hàng như vậy Vì vậy, trong bảng số trên có \( \phi(m) \phi(n) \) số nguyên tố cùng nhau với \( mn \).

   Định lý được chứng minh ▄

1.1.4 Bổ đề Nếu p là số nguyên tố và k là số nguyên dương thì ta có:

  Chứng minh Theo định nghĩa hàm Euler   n , ta có

Ta thấy rằng, các số nguyên dương không vượt quá p k và chia hết cho p phải có dạng sp, ps p k  1 Do đó, có đúng p k  1 số như vậy Vì vậy, ta có

1.1.5 Công thức tính giá trị của hàm số Euler Giả sử số tự nhiên n 1 có dạng phân tích tiêu chuẩn là n p p 1  1 2  2 p k  k Khi đó, ta có công thức

Chứng minh Do hàm Euler có tính chất nhân, nên áp dụng Bổ đề 1.1.4, ta có

Ta có công thức cần chứng minh ▄

1.1.6 Hệ thức Gauss Giả sử n là số nguyên dương Khi đó, ta có công thức sau đây và được gọi là hệ thức Gauss   , d n n   d trong đó tổng được lấy theo mọi ước số tự nhiên d của n

Chứng minh Thật vậy, nếu n  1 thì công thức đúng Nếu n  1 có dạng phân tích tiêu chuẩn n p p 1  1 2  2 p k  k , thì áp dụng tính chất nhân của hàm số Euler ta được

Như vậy, hệ thức Gauss đã được chứng minh ▄

Ta xét các minh hoạ hệ thức Gauss bằng số cụ thể sau:

1.1.7 Định nghĩa Hệ thặng dư thu gọn modn là một tập hợp gồm    n số nguyên, đôi một không đồng dư với nhau theo modn và nguyên tố cùng nhau với n

Ví dụ Tập hợp  1 3 5 7 , , ,  là hệ thặng dư thu gọn mod8

1.1.8 Định lý Giả sử a là số nguyên sao cho a và n nguyên tố cùng nhau Khi đó, nếu r 1 , , r  ( ) n là một hệ thặng dư thu gọn modn thì ar 1 , , ar  ( ) n cũng là hệ thặng dư thu gọn modn

Giả sử có hai chỉ số i và j với 1 ≤ i ≠ j ≤ n, nếu ar_i ≡ ar_j (mod n), từ giả thiết a và n nguyên tố cùng nhau, ta suy ra r_i ≡ r_j (mod n) Điều này mâu thuẫn với giả thiết rằng r_1, , r_φ(n) là hệ thặng dư thu gọn Do đó, mỗi số nguyên trong hệ ar_1, , ar_φ(n) đều không đồng dư với nhau theo mod n Từ giả thiết a và n nguyên tố cùng nhau, ta cũng có những kết luận quan trọng khác.

 ar n i ,   ( , ) 1 r n i  (ar i ,n)(r i ,n)1 Vì vậy, hệ ar 1 , , ar  ( ) n là một hệ thặng dư thu gọn modn Định lý được chứng minh ▄

1.1.9 Định lý Euler [4,6] Giả sử a là một số nguyên và n là một số tự nhiên lớn hơn

1 Khi đó, nếu a và n nguyên tố cùng nhau thì

Giả sử r1, , rϕ(n) là một hệ thặng dư thu gọn modulo n Theo Định lý 1.1.8, hệ ar1, , arϕ(n) cũng là hệ thặng dư thu gọn modulo n Mỗi thặng dư của hệ này tương đương với một và chỉ một thặng dư của hệ kia theo modulo n.

Vì mỗi thặng dư r i nguyên tố cùng nhau với n, nên giản ước hai vế cho r i ta có:

  n  mod  a  1 n Định lý Euler được chứng minh ▄

1.1.10 Xác định nghiệm của phương trình đồng dư bậc nhất bằng cách vận dụng Định lý Euler Xét phương trình đồng dư bậc nhất ax  b  mod m  , với a và m nguyên tố cùng nhau và 1   a m Áp dụng Định lý Euler ta có

  m 1  mod  xa   b m là nghiệm của phương trình đồng dư bậc nhất đã cho

1.1.11 Tìm nghịch đảo của số nguyên a theo mod m Xét phương trình đồng dư bậc nhất đặc biệt ax  1  mod m  , với a và m nguyên tố cùng nhau và 1   a m Khi đó, theo 1.1.10 phương trình này có nghiệm duy nhất là x  a    m  1  mod m , hay số nguyên a có nghịch đảo mod m là a    m  1

Căn nguyên thuỷ và ứng dụng

1.2.1 Định nghĩa Giả sử m  1 là số nguyên và a là số nguyên, nguyên tố cùng nhau với m Khi đó, theo Định lý Euler ta có

Ta gọi cấp của a theo mod m , ký hiệu bởi ord m   a , là số nguyên dương d nhỏ nhất sao cho

Cấp của a theo mod m cũng được gọi là số mũ của a theo mod m

Nhận xét 1) ord m   a là ước của    m

2) Nếu a  b  mod m  thì ord m   a ord m   b

Ví dụ Giả sử m 7 a , 2 khi đó:

Do đó, 2 có cấp 3 theo mod 7 Tương tự 3 có cấp 6 theo mod7 bởi vì:

  mod , mod , mod , mod , mod , mod , mod

Ta lấy chẳng hạn m = 14, khi đó 3 cũng là một căn nguyên thủy mod14, vì ta có 3 2 ≡ 9, 3 3 ≡ 13, 3 4 ≡ 11, 3 5 ≡ 5 và 3 6 ≡ 1 (mod 14) Tương tự, 2 là căn nguyên thuỷ mod11

Số nguyên a được gọi là một căn nguyên thuỷ môđun m nếu a có cấp là    m tức là ord m     a  m

Như vậy, a là một căn nguyên thủy môđun m khi và chỉ khi:

Nhận xét Giả sử a là một căn nguyên thuỷ modm, khi đó:

1) Hệ    m số nguyên 1 a a , , , , 2 a  ( ) m  1 là một hệ thặng dư thu gọn modm

2) Lớp đồng dư a là phần tử sinh của nhóm nhân các lớp đồng dư khả nghịch của vành m

3) Nếu a  b  mod m  thì b cũng là một căn nguyên thuỷ môđun m

Ví dụ 3 là một căn nguyên thuỷ mod7 bởi vì ord 3 7     7 6

3 là một căn nguyên thuỷ mod10 bởi vì ord 3 7     10 4

Tồn tại những số nguyên không có căn nguyên thuỷ theo mod8, bởi vì

  và ord 1 8  ord 8   3 ord 8   5 ord 7 8  2 ord ; 8   a   4 , a

1.2.2 Bổ đề Mọi nhóm xyclic G cấp n đều có    n phần tử sinh, với  là hàm số số học Euler

Chứng minh Giả sử a  G là một phần tử sinh của nhóm xyclic G cấp n, khi đó ta có:

G  a  1 a a a  Với mỗi phần tử a m  G 1 ,   m n sao cho   n m ,  1 khi đó tồn tại các số nguyên k l , sao cho mknl 1 Ta có

Do đó, với mỗi phần tử a  bất kỳ của G ta có sự biểu diễn sau:

Từ đó suy ra mỗi phần tử a m  G 1 ,   m n sao cho   n m ,  1 là một phần tử sinh của

G Theo định nghĩa của hàm số Euler

  là số các số tự nhiên khác không, không vượt quá n và nguyên tố cùng nhau với n, ta suy ra nhóm G có ít nhất    n phần tử sinh

Ngược lại, giả sử nhóm G sinh bởi phần tử a m  G 1 ,   m n nào đó Ta sẽ chỉ ra rằng   n m ,  1 Thật vậy, ta có sự biểu diễn sau qua phần tử sinh

  m m , a  a   a   hay a m   1 1 Vì a là có cấp là n nên m    1 0  mod n  hay m   1  mod n  Theo tính chất của đồng dư thức ta có  m  , n     1 n ,  1 Do đó

  m n ,  1 Vậy, nhóm G có    n phần tử sinh Bổ đề được chứng minh ▄

Chú ý rằng, mọi nhóm xyclic cấp n đều đẳng cấu với nhóm cộng n các lớp đồng dư môđun n cho nên các lập luận trên có thể đưa về trên n

1.2.3 Định lý Giả sử G là một nhóm con hữu hạn của nhóm nhân của một trường

Khi đó, G là nhóm xyclic

Giả sử G là một nhóm hữu hạn với cấp m, thì mọi phần tử a thuộc G đều có cấp là ước của m Đối với mỗi ước d của m, ký hiệu ψ(d) đại diện cho số lượng các phần tử trong nhóm G.

Nếu nhóm G có cấp d và    d  0, thì tồn tại phần tử a cấp d, với mọi phần tử trong nhóm con xyclic a sinh bởi a đều thỏa mãn a d 1 Đa thức f x    x d  1 có tối đa d nghiệm, và tất cả các nghiệm này đều thuộc nhóm con xyclic a Đặc biệt, mỗi phần tử cấp d của G đều nằm trong a Theo Bổ đề 1.2.2, nhóm xyclic cấp d có đúng    d phần tử sinh, trong đó  là hàm số số học Euler.

  hoặc      d   d với mọi ước d của m Bởi vì mỗi phần tử của G có cấp dvới d là một ước nào đó của m, nên từ đó suy ra   d m d m

 và do đó      d   d với mọi ước d của m Đặc biệt,      m   m  1 và vì vậy trong G có ít nhất một phần tử cấp m G hay G là nhóm xyclic ▄

1.2.4 Hệ quả Với mỗi số nguyên tố p , nhóm nhân của trường p là nhóm xyclic và nhóm này có   p 1   phần tử sinh Nói khác đi, với mỗi số nguyên tố p , tồn tại

Chứng minh Hệ quả này được trực tiếp suy ra từ Định lý 1.2.3 bởi vì nhóm nhân của trường p là nhóm cấp p 1 ▄

Bảng các căn nguyên thuỷ p với p là 6 số nguyên tố đầu tiên:

Thứ tự p   p 1   Căn nguyên thuỷ môđun p

1.2.5 Chỉ số Giả sử p là số nguyên tố và g là một căn nguyên thuỷ môđun p Nếu a là một số nguyên không chia hết cho p thì tồn tại duy nhất một số nguyên k sao cho

 mod ,   , , ,  ag k p k 0 1 p2 Khi đó, số nguyên k được gọi là chỉ số củaa tương ứng với căn nguyên thuỷ g và được ký hiệu là k ind g   a

Nhận xét 1) Nếu k 1 k 2 là các số nguyên bất kỳ sao cho

2) ind g   ab ind g   a ind g   b Ánh xạ chỉ số ind g : a ind g   a được gọi là lôgarit rời rạc cơ sở g

1.2.6 Mệnh đề Nếu s > 1 là một số tự nhiên thì ( ) ( )

Chứng minh Đặt   ord m ( ), a v     , s ,    1 v s ,  s v 1 với ( , ) 1  1 s 1  , u  ord m ( a s )

Mặt khác ( )a s u a su 1 (mod )m nên  |su tức là  1 v|s 1 vu, do đó  1 |s 1 u, nhưng do ( , ) 1 1 s 1  nên  1 |u (**)

Từ (*) và (**) ta suy ra 1

Mệnh đề được chứng minh ▄

1.2.7 Hệ quả Nếu s > 1 là một số tự nhiên, nguyên tố cùng nhau với ord m ( )a , thì

( s ) ( ). m m ord a ord a Chứng minh Thật vậy, theo Mệnh đề 1.2.6 ta có

( ( ), ) 1 s m m m m m ord a ord a ord a ord a ord a s

1.2.8 Hệ quả Nếu g là căn nguyên thủy môđun m, thì g là căn nguyên thủy môđun s m khi và chỉ khi ( , ( )) 1s  m 

Chứng minh Áp dụng Mệnh đề 1.2.6 cho căn nguyên thủy g ta có

  Từ đó suy ra g s là căn nguyên thủy môđun m khi và chỉ khi

1.2.9 Mệnh đề Nếu có một căn nguyên thủy môđun m thì sẽ có tất cả  ( ( ))m căn nguyên thủy môđun m không đồng dư với nhau theo môđun m

Nếu g là một căn nguyên thủy môđun m, thì các số g, g², , g^φ(m) tạo thành một hệ thặng dư thu gọn môđun m Theo Hệ quả 1.2.8, số căn nguyên thủy môđun m bằng số các số tự nhiên s thỏa mãn (s, φ(m)) = 1 Do đó, có φ(φ(m)) số nguyên s như vậy, dẫn đến kết luận rằng có φ(φ(m)) căn nguyên thủy môđun m.

1.2.10 Mệnh đề Nếu  ord m ( ), a ord m ( ) b   1 thì

( ) ( ) ( ). m m m ord ab ord a ord b Chứng minh Đặt d 1 ord m ( ),a d 2 ord m ( ),b d ord m ( )a ord m ( )b , ta có

Từ đó suy ra d là một bội của ord m (ab)

Giả sử ta có (ab) d ' 1 (mod )m khi đó ta được (ab) d d ' 1 1 (mod )m từ đó ta có

1(mod ) b d d  m suy ra d 2 |d d' 1 , nhưng do ( ,d d 1 2 ) 1 nên d 2 | 'd Tương tự ta cũng chứng minh được d 1 | 'd do đó 'd là bội của d d d 1 2 Từ đó suy ra

Nếu theo môđun m cấp của b1, b2, , bn lần lượt là r1, r2, , rn, và các số này đôi một nguyên tố cùng nhau, thì cấp của tích b1, b2, , bn sẽ là tích các số mũ r1, r2, , rn.

Bài toán tồn tại căn nguyên thuỷ

Chúng ta đã nhận thấy rằng căn nguyên thuỷ không có mặt trong mọi môđun, ví dụ như môđun 8 Trong phần này, chúng ta sẽ khám phá bài toán về sự tồn tại của căn nguyên thuỷ Cụ thể, chúng ta sẽ chứng minh rằng một số nguyên m ≥ 2 có căn nguyên thuỷ nếu và chỉ nếu m = 2^k, hoặc m = 2^p*k, trong đó p là số nguyên tố lẻ và k là số nguyên dương.

1.3.1 Bổ đề Giả sử m là một số nguyên không phải là một luỹ thừa của 2 Nếu m có căn nguyên thuỷ thì m p k hoặc m2 p k , trong đó p là số nguyên tố lẻ và k là số nguyên dương

Chứng minh Giả sử m là một số nguyên sao cho   a m ,  1 và m  3 Giả thiết thêm rằng

Khi đó  a m , 1   a m , 2 1 Giá trị    m của hàm Euler là số chẵn khi m  3 Từ đó

Theo Định lý Euler có

Từ đó suy ra m       ord a m m

  Như vậy, ta có thể suy ra rằng nếu

Nếu m ≥ 3 và m là một số nguyên dương, thì không tồn tại căn nguyên thuỷ của môđun m Đặc biệt, nếu m chia hết cho hai số nguyên tố lẻ, thì m sẽ không có căn nguyên thuỷ Tương tự, nếu m = 2^p * l^k (với p ≥ 2), thì m cũng không có căn nguyên thuỷ Do đó, chỉ những môđun m khác 2^i mới có thể có căn nguyên thuỷ, cụ thể là m = p^k hoặc m = 2^p * k, trong đó p là số nguyên tố lẻ và k là số nguyên dương.

1.3.2 Bổ đề Nếu p là một số nguyên tố thì có căn nguyên thủy môđun p

Chứng minh Thật vậy, với p2 thì điều khẳng định hiển nhiên đúng vì ta có

1   1 1 (mod 2) nên 1 chính là căn nguyên thủy môđun 2

Giả sử p là số nguyên tố lẻ và ( ) p  p 1 có dạng phân tích tiêu chuẩn là

1 2 k k q  q  q  Vì phương trình đồng dư

   do đó với mỗi q i , luôn tồn tại a i , (a p i , )1 sao cho  

Ta sẽ chứng minh rằng cấp theo môđun p của b i là i q i  Theo Định lý Fermat bé, ta có i i i q b  = a i p  1 1 (mod) p, do đó cấp d i của b i là ước của i q i  Vì vậy, d i có dạng i q i  với 0 <  ≤  i Tuy nhiên, với mọi  <  i, ta có q i b i  1 i i p q a i.

1 (mod p), vậy nên   i  i nghĩa là i i i d q  Như vậy các số b b 1 , 2 , , b k có cấp theo môđun p lần lượt là

1 , 2 , , k k q  q  q  đôi một nguyên tố cùng nhau cho nên g b b 1 2 b k sẽ có cấp theo môđun p là q 1  1 q 2  2 q k  k   p 1 ( )p , nghĩa là g là căn nguyên thủy môđun p Vậy có căn nguyên thủy môđun p ▄

1.3.3 Bổ đề Có căn nguyên thủy theo môđun 4

Thật vậy 1 là căn nguyên thủy môđun 4 vì cấp của 1 là 2 và 2(4),

1.3.4 Bổ đề Nếu p là số nguyên tố lẻ thì có căn nguyên thủy mô đun p k với mọi số nguyên dương k

Chứng minh Giả sử g là một căn nguyên thủy môđun p, ta có thể giả thiết rằng

Thật vậy, nếu không như thế thì g 1  g p cũng là một căn nguyên thủy và có tính chất trên vì:

Từ đó vì g p  1 1 (modp 2 ) ta được

Vậy ta có thể giả thiết rằng căn nguyên thủy g môđun p thỏa mãn điều kiện

1 g p  1 (modp 2 ) Ta sẽ chứng minh rằng g là căn nguyên thủy môđun p k với 1 k

Thật vậy vì g p  1 1 (modp 2 ) nên g p  1 = 1 + pu với (u, p) =1 Do đó với mọi l1 thì ( 1) 1 1 ' p l p l g    p  u , với (u’, p) =1 Nghĩa là ta có

Từ đó ta được g p k  1 ( p  1) g  ( p k ) 1 (modp k ) và với mọi  | ( p k ),   (p k ) thì g  1 (modp k )

Vậy g là một căn nguyên thủy môđun p  ▄

1.3.5 Bổ đề Nếu p là số nguyên tố lẻ thì có căn nguyên thủy theo môđun 2p với k mọi số nguyên dương k

Chứng minh Ta có ( p k )(2p k ) và mọi số lẻ x thỏa mãn một trong hai đồng dư thức x  1 (modp k ) và x  1 (mod 2p k )thì cũng thỏa mãn đồng dư thức còn lại

Thật vậy, nếu x  1 (modp k ) mà x lẻ nên x  1 (mod 2)từ đó kết hợp với 2 và p  nguyên tố cùng nhau ta suy ra x  1 (mod 2p  )

Ngược lại, nếu x  1 (mod 2p  ) thì theo tính chất của đồng dư thức ta có ngay x  1 (modp  )

Giả sử g là một căn nguyên thủy môđun pk, thì một trong hai số g hoặc g + pk sẽ là căn nguyên thủy lẻ môđun pk Theo chứng minh đã nêu, điều này cho thấy g chính là căn nguyên thủy theo môđun 2pk.

Từ các Bổ đề trên ta có

1.3.6 Định lý Các số m2 4 p , , k hoặc m2 p k , trong đó p là số nguyên tố lẻ và klà số nguyên dương và chỉ các số đó mới có căn nguyên thủy.

ỨNG DỤNG CỦA CĂN NGUYÊN THUỶ TRONG MẬT MÃ 20

Giới thiệu về mật mã học

2.1.1 Mật mã học Lý thuyết mật mã là khoa học nghiên cứu cách viết bí mật, trong đó các bản rõ (plain text, clear text) được biến đổi thành các bản mã (cipher text, cryptogram) Quá trình biến đổi đó gọi là sự mã hoá (encipherment, encryption) Quá trình ngược lại biến đổi từ bản mã thành bản rõ được gọi là sự giải mã (decipherment, decryption) Cả hai quá trình nói trên đều được điều khiển bởi một (hay nhiều) khoá mật mã

Mật mã học là lĩnh vực kết hợp giữa ngôn ngữ và toán học nhằm bảo vệ an toàn thông tin, đặc biệt trong giao tiếp Lịch sử của mật mã học gắn liền với quá trình mã hóa, tức là chuyển đổi thông tin từ dạng có thể đọc được sang dạng không thể đọc được, bảo vệ thông tin khỏi những người không có kiến thức bí mật Quá trình mã hóa chủ yếu được áp dụng để bảo đảm tính bí mật cho thông tin quan trọng trong tình báo, quân sự, ngoại giao và các bí mật kinh tế, thương mại Ngoài ra, công nghệ mã hóa còn được sử dụng rộng rãi trong các hệ thống công nghệ thông tin và viễn thông, phục vụ cả những người không có nhu cầu bảo mật đặc biệt.

Mật mã học là một lĩnh vực liên ngành, phát triển từ nhiều lĩnh vực khác nhau, với những dạng cổ nhất chủ yếu liên quan đến mẫu ngôn ngữ Gần đây, tầm quan trọng của mật mã hóa đã chuyển hướng nhiều hơn về toán học, đặc biệt là toán học rời rạc, bao gồm lý thuyết số, lý thuyết thông tin, độ phức tạp tính toán, thống kê và tổ hợp Mặc dù mật mã hóa được xem như một nhánh của công nghệ, nhưng nó cũng được coi là không bình thường do liên quan đến các sự chống đối ngầm Mật mã hóa đóng vai trò quan trọng trong an ninh máy tính và mạng.

2.1.2 Phá mã Việc nghiên cứu tìm các phương thức để phá vỡ việc sử dụng mật mã được gọi là phân tích mật mã, hay phá mã Mật mã hóa và phân tích mật mã đôi khi được nhóm lại cùng nhau dưới tên gọi chung mật mã học, nó bao gồm toàn bộ các chủ đề liên quan đến mật mã Trong thực tế, thuật ngữ mật mã hóa thông thường được sử dụng để nói đến ngành này một cách tổng thể

Mật mã hóa là quá trình chuyển đổi thông tin thông thường thành dạng không thể đọc được, gọi là văn bản mã hóa, trong khi giải mật mã là quá trình phục hồi văn bản thường từ văn bản mã Mật mã là thuật toán dùng để thực hiện cả hai quá trình này, và hoạt động của nó được kiểm soát bởi các khóa bí mật Các giao thức mật mã quy định chi tiết cách thức sử dụng các phương pháp mã hóa để thực hiện các nhiệm vụ cụ thể Hệ thống mật mã bao gồm một bộ giao thức, thuật toán, quản lý khóa và các hành động được người sử dụng quy định, phối hợp chặt chẽ với nhau.

Trong mật mã học, "mã" bí mật không chỉ đơn thuần là "mật mã" mà có ý nghĩa kỹ thuật riêng Các mã là phương pháp thay thế các đơn vị văn bản lớn hơn như từ hoặc câu, ví dụ "qua tao" thay cho "tan cong luc rang dong" Ngược lại, mật mã hóa cổ điển thường liên quan đến việc thay thế hoặc sắp xếp lại các chữ cái riêng lẻ, như ví dụ "tan cong luc rang dong" trở thành "ubo dpoh mvd sboh epoh".

2.1.3 Sơ đồ khái quát về một hệ thống mật mã Trong một hệ thống mật mã khái quát sẽ có các thành phần sau (xem hình vẽ):

● Văn bản trơn (plaintext), tức là thông điệp nguyên gốc chưa được mã hóa

● Văn bản mã hóa (ciphertext), tức là thông điệp đã được mã hóa

Thuật toán mã hóa là các quy tắc chuyển đổi văn bản trơn thành văn bản mã hóa Trong các hệ thống mật mã truyền thống, chỉ người gửi mới biết thuật toán, trong khi ở hệ thống mật mã hóa khóa công khai (PKC), mọi người đều có thể biết thuật toán mà không làm giảm tính bảo mật của hệ thống.

Khóa mã hóa, hay còn gọi là enciphering key, là một hoặc nhiều đối tượng, thường là các con số hoặc hướng dẫn quan trọng, được sử dụng để mã hóa văn bản trơn Trong hầu hết các hệ thống, ngoại trừ hệ thống PKC, khóa mã hóa chỉ được người gửi biết để đảm bảo tính bảo mật an toàn cho thông tin.

Thuật toán giải mã là các giao thức hoặc hướng dẫn giúp chuyển đổi văn bản mã hóa trở lại thành văn bản gốc Để bảo đảm tính bảo mật, chỉ người nhận thông điệp mới biết được thuật toán giải mã.

Khóa giải mã là các đối tượng, thường là con số hoặc hướng dẫn quan trọng, được sử dụng để giải mã văn bản bị mã hóa Để bảo đảm tính bảo mật, chỉ người nhận thông điệp mới biết đến khóa giải mã này.

Sản phẩm mật mã bao gồm hệ thống thiết bị, module, mạch tích hợp và phần mềm mã hoá chuyên dụng, tích hợp các thuật toán mật mã nhằm bảo vệ thông tin giao dịch điện tử và lưu trữ dưới dạng số hoá Các sản phẩm này sử dụng "Thuật toán mã đối xứng" hoặc "Thuật toán mã không đối xứng" để đảm bảo an toàn cho dữ liệu.

2.2 Giao thức trao đổi khoá Diffie-Hellman

2.2.1 Trao đổi khóa Diffie – Hellman Trao đổi khóa Diffie – Hellman (D-H) là một phương pháp trao đổi khóa được phát minh sớm nhất trong mật mã học Phương pháp trao đổi khóa Diffie – Hellman cho phép hai bên (người, thực thể giao tiếp) thiết lập một khóa bí mật chung để mã hóa dữ liệu sử dụng trên kênh truyền thông không an toàn mà không cần có sự thỏa thuận trước về khóa bí mật giữa hai bên Khóa bí mật tạo ra sẽ được sử dụng để mã hóa dữ liệu với phương pháp mã hóa khóa đối xứng

Giao thức trao đổi khóa Diffie-Hellman được công bố lần đầu tiên bởi Whitfield Diffie và Martin Hellman vào năm 1976, mặc dù trước đó đã được phát minh độc lập bởi James H Ellis, Clifford Cocks và Malcolm J Williamson tại GCHQ, Anh, nhưng thông tin này được giữ bí mật Đến năm 2002, Hellman đã đề xuất thuật toán này nên được gọi là trao đổi khóa Diffie–Hellman–Merkle để ghi nhận sự đóng góp của Ralph Merkle trong lĩnh vực mật mã hóa khóa công khai.

Giao thức trao đổi khóa Diffie–Hellman, mặc dù không xác thực, đã tạo ra nền tảng cho nhiều giao thức xác thực khác nhau và đóng vai trò quan trọng trong việc thiết lập bí mật chuyển tiếp hoàn hảo trong chế độ ngắn hạn của giao thức Transport Layer Security (TLS), được biết đến với tên gọi EDH hoặc DHE tùy thuộc vào bộ mã hóa sử dụng.

2.2.2 Mô tả Trao đổi khóa Diffie – Hellman Diffie – Hellman thiết lập bí mật chung để sử dụng cho trao đổi dữ liệu an toàn trên một kênh truyền thông công cộng không an toàn Sơ đồ sau đây minh họa ý tưởng cơ bản của việc trao đổi khóa thông qua ví dụ về màu sơn Điểm chủ chốt của ý tưởng cơ bản này là Alice và Bob trao đổi màu sơn bí mật thông qua hỗn hợp sơn

- Đầu tiên Alice và Bob trộn màu đã biết chung (màu vàng) với màu bí mật riêng của mỗi người

- Sau đó, mỗi người chuyển hỗn hợp của mình tới người kia thông qua một kênh vận chuyển công cộng

- Khi nhận được hỗn hợp của người kia, mỗi người sẽ trộn thêm với màu bí mật của riêng mình và nhận được hỗn hợp cuối cùng

Một số ứng dụng của căn nguyên thuỷ trong mật mã

2.3.1 Định lý Giả sử p là số nguyên tố, a là một căn nguyên thuỷ môđun p Khi đó, ánh xạ f : p  p có quy luật xác định bởi f k    a k là một song ánh

Chứng minh Với 1k l ,  p 1, nếu f k      f l thì a k  a l hay a k  a l  mod p 

Nếu k l thì từ   a p ,  1 suy ra a k l   1  mod p  hay k  l chia hết cho

  Ta gặp phải một mâu thuẫn Như vậy, nếu f k      f l thì k  l hay

Một hàm số f : p  p xây dựng như vậy được gọi là hàm mũ đồng dư Trong trường hợp tổng quát, f được định nghĩa là f : m  m có quy luật xác định bởi f k    a k

Việc xác định số dư của \( a^x \mod m \) là đơn giản và khả thi, nhưng xác định hàm số ngược của \( f \) thì không phải lúc nào cũng thực hiện được Điều này chỉ khả thi khi \( f \) là một ánh, thể hiện ý nghĩa của định lý này Do đó, việc tìm tất cả các căn nguyên thủy của một số cho trước trở nên rất quan trọng, và định lý sau đây sẽ hỗ trợ chúng ta trong quá trình này.

2.3.2 Định lý Giả sử p là số nguyên tố, a là một căn nguyên thủy môđun p, khi đó mọi b thuộc p có thể viết được dưới dạng b  a i , trong đó 0 < i < p - 2

Từ định lý này suy ra:

* b là 1 căn nguyên thủy khi và chỉ khi (p - 1, i) = 1, hay nói cách khác, tập hợp các căn nguyên thủy của p là  a 0 i ,    i p 2 p 1 i ,   ,   1 

* Số căn nguyên thủy môđun p là   p 1  

* Nếu ta biết 1 căn nguyên thủy của p, khi đó chúng ta sẽ biết tất cả các căn nguyên thủy của p

Với một số điều kiện nhất định, hàm số mũ đồng dư f(k) = a^k trong m là một song ánh Tuy nhiên, việc tính hàm số ngược của nó lại phức tạp hơn rất nhiều, ngay cả khi đã biết giá trị của a Đây là một ví dụ điển hình cho lớp hàm số được gọi là "hàm số hướng duy nhất".

- phức tạp khi tính ngược lại

Hàm số mũ đồng dư không chỉ dễ dàng tính toán hàm số ngược mà còn giữ bí mật thông tin hiệu quả Những hàm số này đóng vai trò quan trọng trong lĩnh vực mật mã hóa.

Bây giờ chúng ta sẽ cùng tìm hiểu một số phương pháp mã hóa:

2.3.3 Chia sẻ chìa khóa A và B muốn có chung một chìa khóa, họ sẽ chọn:

- p là số nguyên tố và công khai p

- a căn nguyên thủy của p, và công khai a

- Mỗi nguời giữ một số bí mật Xa và Xb với 1 X a , X b  p 1

Khi đó, A và B sẽ cùng có chung một chìa khóa

2.3.4 Mã hóa "không chìa khóa" Cho một thông tin (dưới dạng số) M < p, A cần gửi M cho B

1 A chọn a < p, (a, p - 1) = 1 (a bí mật); B chọn b < p, (b, p - 1) = 1 (b bí mật)

3 B gửi lại cho A số D  C b  mod p 

4 A tính a' sao cho 0 < a' < p và a a ' 1(mod p1) (a' được gọi là nghịch đảo (mod p

- 1) của a), sau đó gửi cho B số

5 B tính nghịch đảo b' của b, sau đó tính

E M M p vì aa '  bb '  1  mod p  và theo định lý nhỏ Fermat

2.3.5 Mã hóa với chìa khóa công khai Xét p là số nguyên tố, công khai p

Có N người muốn chia sẻ thông tin một cách bí mật, họ sẽ chọn căn nguyên thủy của p, khi đó hàm số mũ đồng dư của a sẽ là song ánh Mỗi cá nhân tham gia vào quá trình này đều có vai trò quan trọng trong việc đảm bảo tính bảo mật của thông tin.

1 số bí mật X n , với 1 X n  p 1 Họ công khai

Y n a p Bây giờ giả sử rằng A, B là hai trong N người, A muốn gửi cho B thông tin M

3 A chuyển cho B cặp số  a KM k ,  C C 1 , 2 

Khi B nhận được cặp số  C C 1 , 2 , muốn có M, người B sẽ:

2 Chia C 2 cho K sẽ thu được thông tin M.