Định nghĩa

          Giả sử a và b là các số nguyên và m là một số nguyên dương. Khi đó ta viết a ºb (mod m) nếu m chia hết cho b-a. Mệnh đề a ºb (mod m) được gọi là " a đồng dư với b theo modulo m". Số nguyên m được gọi là mudulus.

          Giả sử chia a và b cho m và ta thu được thương nguyên và phần dư, các phần dư nằm giữa 0 và m-1, nghĩa là a = q₁m + r₁ và b = q₂m + r₂ trong đó 0£  r₁ £m-1và 0 £  r₂ £m-1. Khi đó có thể dễ dàng thấy rằng a ºb (mod m) khi và chỉ khi r₁ = r₂ . Ta sẽ dùng ký hiệu a mod m (không dùng các dấu ngoặc) để xác định phần dư khi a được chia cho m (chính là giá trị r₁ ở trên). Như vậy: a ºb (mod m) khi và chỉ khi a mod m = b mod m. Nếu thay a bằng a mod m thì ta nói rằng a được rút gọn theo modulo m.

Nhận xét:Nhiều ngôn ngữ lập trình của máy tính xác định a mod m là phần dư trong dải - m+1,.. ., m-1 có cùng dấu với a. Ví dụ -18 mod 7 sẽ là -4, giá trị này khác với giá trị 3 là giá trị được xác định theo công thức trên. Tuy nhiên, để thuận tiện ta sẽ xác định a mod m luôn là một số không âm.

          Bây giờ ta có thể định nghĩa số học modulo m: Z_m được coi là tập hợp {0,1,. . .,m-1} có trang bị hai phép toán cộng và nhân. Việc cộng và nhân trong Z_m được thực hiện giống như cộng và nhân các số thực ngoài trừ một điểm làcác kết quả được rút gọn theo modulo m.

          Ví dụ tính 11´13 trong Z₁₆ . Tương tự như với các số nguyên ta có 11 ´13 = 143. Để rút gọn 143 theo modulo 16, ta thực hiện phép chia bình thường: 143 = 8 ´16 + 15, bởi vậy 143 mod 16 = 15 trong Z₁₆ .

          Các định nghĩa trên phép cộng và phép nhân Z_m thảo mãn hầu hết các quy tắc quyen thuộc trong số học. Sau đây ta sẽ liệt kê mà không chứng minh các tính chất này:

1. Phép cộng là đóng, tức với bất kì a,b ÎZ_m ,a +b ÎZ_m
2. Phép cộng là giao hoán, tức là với  a,b bất kì ÎZ_m

a+b = b+a

1. Phép cộng là kết hợp, tức là với bất kì a,b,c ÎZ_m

(a+b)+c = a+(b+c)

1. 0 là phần tử đơn vị của phép cộng, có nghĩa là với a bất kì ÎZ_m

a+0 = 0+a = a

1. Phần tử nghịch đảo của phép cộngcủa phần tử bất kì (a ÎZ_m) là m-a, nghĩa là a+(m-a) = (m-a)+a = 0 với bất kì a ÎZ_m .
2. Phép  nhân là đóng , tức là với a,b bất kì ÎZ_m , ab ÎZ_m .
3. Phép nhân là gioa hoán , nghĩa là với a,b bất kì ÎZ_m , ab = ba
4. Phép nhân là kết hợp, nghĩa là với a,b,c ÎZ_m , (ab)c = a(cb)
5. 1 là phần tử đơn vị của phép nhân, tức là với bất kỳ a ÎZ_m

a´1 = 1´a = a

1. Phép nhân có tính chất phân phối đối với phép cộng, tức là đối với a,b,c ÎZ_m , (a+b)c = (ac)+(bc) và a(b+c) = (ab) + (ac)

Các tính chất 1,3-5 nói lên rằng  Z_m lâp nên một cấu trúc đại số được gọi là một nhóm theo phép cộng. Vì có thêm tính chất 4 nhóm được gọi là nhóm Aben (hay nhóm gioa hoán).

Các tính chất 1-10 sẽ thiết lập nên một vành  Z_m . Ta sẽ còn thấy nhiều ví dụ khác về các nhóm và các vành trong cuốn sách này. Một số ví dụ quên thuộc của vành là các số nguyên Z, các số thực R và các số phức C. Tuy nhiên các vành này đều vô hạn, còn mối quan tâm của chúng ta chỉ giới hạn trên các vành hữu hạn.

Vì phần tử ngược của phép cộng tồn tại trong  Z_m nên cũng có thể trừ các phần tử trong  Z_m . Ta  định nghĩa a-b trong  Z_m là a+m-b mod m. Một cách tương có thể tính số nguyên a-b rồi rút gon theo modulo m.

Ví dụ : Để tính 11-18 trong Z₃₁, ta tính 11+13 mod 31 = 24. Ngược lại, có thể lấy 11-18 được -7 rồid sau đó tính -7 mod 31 = 24.

Ta sẽ mô tả mã dịch vòng trên hình 1.2. Nó được xác định trên Z₂₆ (do có 26 chữ cái trên bảng chữ cái tiếng Anh) mặc dù có thể xác định nó trên Z_m với modulus m tuỳ ý. Dễ dàng thấy rằng, MDV sẽ tạo nên một hệ mật như đã xác định ở trên, tức là d_K (e_K(x)) = x với mọi xÎZ₂₆ .

Hình 1.2: Mã dịch vòng

Nhận xét:Trong trường hợp K = 3, hệ mật thường được gọi là mã Caesar đã từng được Julius Caesar sử dụng.

          Ta sẽ sử dụng MDV (với modulo 26) để mã hoá một văn bản tiếng Anh thông thường bằng cách thiết lập sự tương ứnggiữa các kí tự và các thặng dư theo modulo 26 như sau: A «0,B «1, . . ., Z «25. Vì phép tương ứng này còn dùng trong một vài ví dụ nên ta sẽ ghi lại để còn tiện dùng sau này:

Sau đây là một ví dụ nhỏ để minh hoạ

Ví dụ 1.1:

          Giả sử khoá cho MDV là K = 11 và bản rõ là:

wewillmeetatmidnight

          Trước tiên biến đổi bản rõ thành dãy các số nguyên nhờ dùng phép tương ứng trên. Ta có:

0

          22      4        22      8        11      11      12      4        4        19

          0        19      12      8        3        13      8        6        7        19

sau đó cộng 11 vào mỗi giá trị rồi rút gọn tổng theo modulo 26

          7        15      7        19      22      22      23      15      15      4

          11      4        23      19      14      24      19      17      18      4

          Cuối cùng biến đổi dãy số nguyên này thành các kí tự thu được bản mã sau:

HPHTWWXPPELEXTOYTRSE

          Để giả mã bản mã này, trước tiên, Bob sẽ biến đổi bản mã thành dãy các số nguyên rồi trừ đi giá trịcho 11 ( rút gọn theo modulo 26) và cuối cùng biến đổi lại dãy nàythành các ký tự.

Nhận xét: Trong ví dụ trên , ta đã dùng các chữ in hoa ch o bản mã, các chữ thường cho bản rõ đêr tiện phân biệt. Quy tắc này còn tiếp tục sử dụng sau này.

          Nếu một hệ mật có thể sử dụng được trong thực tế thì nó phảo thoả mãn một số tính chất nhất định. Ngay sau đây sé nêu ra hai trong số đó:

          1. Mỗi hàm mã hoá e_K và mỗi hàm giải mã d_K phải có khả năng tính toán được một cách hiệu quả.

          2. Đối phương dựa trên xâu bản mã phải không có khả năng xác định khoá K đã dùng hoặc không có khả năng xác định được xâu bản rõ x.

          Tính chất thứ hai xác định (theo cách khá mập mờ) ý tưởng ý tưởng "bảo mật". Quá trình thử tính khoá K (khi đã biết bản mã y) được gọi là mã thám (sau này khái niệm này sẽ đực làm chính xác hơn). Cần chú ý rằng, nếu Oscar có thể xác định được K thì anh ta có thể giải mã được y như Bob bằng cách dùng d_K. Bởi vậy, việc xác định K chí ít cũng khó như việc xác định bản rõ x.

          Nhận xét rằng, MDV (theo modulo 26) là không an toàn vì nó có thể bị thám theo phương pháp vét cạn. Do chỉ có 26 khoá nên dễ dàng thử mọi khoá d_K có thể cho tới khi nhận được bản rõ có nghĩa. Điều này được minh hoạ theo ví dụ sau:

Ví du 1.2

          Cho bản mã

JBCRCLQRWCRVNBJENBWRWN

ta sẽ thử liên tiếp các khoá giải mã d₀ ,d₁ .. . và y thu được:

j b c r c l q r w c r v n b j e n b w r w n

                   i a b q b k p q v b q u m a i d m a v q v m

                   h z a p a j o p u a p t l z h c l z u p u l

                   g y z o z i n o t z o s k y g b k y t o t k

                   j x y n y h m n s y n r j e x f a j x s n s j

                   e w x m x g l m r x m q i w e z i w r m r i

                   d v w l w f k l q w l p h v o d y h v q l q h

                   c u v k v e j k p v k o g u c x g u p k p g

                   b t u j u d i j o u j n f t b w f o j o f

                   a s t i t c h i n t i m e s a v e s n i n e

Tới đây ta đã xác định được bản rõ và dừng lại. Khoá tương ứng K = 9.

          Trung bình có thể tính được bản rõ sau khi thử 26/2 = 13 quy tắc giải mã.

          Như đã chỉ ra trong ví dụ trên , điều kiện để một hệ mật an toàn là phép tìm khoá vét cạn phải không thể thực hiện được; tức không gian khoá phải rất lớn. Tuy nhiên, một không gian khoá lớn vẫn chưa đủ đảm bảo độ mật. (Sưu tầm)

» Tin mới nhất:

• Ý nghĩa của hàm cận biện trong kinh tế. (17/07/2022)
• Xây dựng phương trình vi phân trong thực tiễn (16/07/2022)
• Một số ví dụ về công thức gần đúng (12/07/2022)
• Doanh thu lớn nhất. (11/07/2022)
• Xác định hàm lượng Cl- trong nước máy (18/06/2022)

» Các tin khác:

• Những nội dung cơ bản của chương 2,3,4 - Toán cao cấp C1 (15/06/2019)
• Những nội dung cơ bản của chương 1 - Toán cao cấp C1 (15/06/2019)
• Ma trận nghịch đảo (12/06/2019)
• Tích phân mặt (12/06/2019)
• Ứng dụng của tích phân trong việc tính thặng dư tiêu dùng. (11/06/2019)
• Ứng dụng của tích phân trong phân phối thu nhập - phần 1 (11/06/2019)
• bài ôn tập XSTK số 2 (30/05/2019)
• bài ôn tập số 1 (30/05/2019)
• Kết tủa phân đoạn (18/05/2019)
• Một số vấn đề lưu ý khi làm thí nghiệm (18/05/2019)