tailieunhanh - Giáo trình tin học : Hệ mật mã và những khả năng tạo liên lạc tuyệt mật của nó phần 3

Điều cần thiết ở đây là có một thuật toán hữu hiệu để làm việc đó. Rất mayb là một số kết quả tiếp sau về số học modulo sẽ cung cấp một thuật toán giải mã hữu hiệu cần tìm. Định nghĩa Giả sử a ∈ Zm . | Vietebooks Nguyễn Hoàng Cương này có một nghiệm duy nhất trong Z26 . Tuy nhiên ta vẫn chua biết một phương pháp hữu hiệu để tìm nghiệm. Điều cần thiết ở đây là có một thuật toán hữu hiệu để làm việc đó. Rất mayb là một số kết quả tiếp sau về số học modulo sẽ cung cấp một thuật toán giải mã hữu hiệu cần tìm. Định nghĩa Giả sử a e Zm . Phần tử nghịch đảo theo phép nhân của a là phần tử ã11 e Zm sao cho aa1 a 1a 1 mod m . Bằng các lý luận tương tự như trên có thể chứng tỏ rằng a có nghịch đảo theo modulo m khi và chỉ khi UCLN a m 1 và nếu nghịch đảo này tồn tại thì nó phải là duy nhất. Ta cũng thấy rằng nếu b a-1 thì a b-1 . Nếu p là số nguyên tố thì mọi phần tử khác không của ZP đều có nghịch đảo. Một vành trong đó mọi phần tử đều có nghịch đảo được gọi là một trường. Trong phần sau sẽ mô tả một thuật toán hữu hiệu để tính các nghịch đảo của Zm với m tuỳ ý. Tuy nhiên trong Z26 chỉ bằng phương pháp thử và sai cũng có thể tìm được các nghịch đảo của các phần tử nguyên tố cùng nhau với 26 1-1 1 3-1 9 5-1 21 7-1 15 11-1 19 17-1 23 25-1 25. Có thể dễ dàng kiểm chứng lại điều này ví dụ 7 X 5 105 1 mod 26 bởi vậy 7-1 15 . Xét phương trình đồng dư y ax b mod 26 . Phương trình này tương đương với ax y-b mod 26 Vì UCLN a 26 1 nên a có nghịch đảo theo modulo 26. Nhân cả hai vế của đồng dư thức với a-1 ta có a-1 ax a-1 y-b mod 26 Áp dụng tính kết hợp của phép nhân modulo a-1 ax a-1a x 1x x. Kết quả là x a-1 y-b mod 26 . Đây là một công thức tường minh cho x. Như vậy hàm giải mã là d y a-1 y-b mod 26 Trang 11 Vietebooks Nguyễn Hoàng Cương Hình cho mô tả đầy đủ về mã Affine. Sau đây là một ví dụ nhỏ Hình Mật mã A ffine Cho P C Z26 và giả sử P a b e Z26 X Z26 UCLN a 26 1 Với K a b e K ta định nghĩa eK x ax b mod 26 và dK y a-1 y-b mod 26 x y e Z26 Ví dụ Giả sử K 7 3 . Như đã nêu ở trên 7-1 mod 26 15. Hàm mã hoá là eK x 7x 3 Và hàm giải mã tương ứng là dK x 15 y-3 15y-19 Ớ đây tất cả các phép toán đều thực hiện trên Z26. Ta sẽ kiểm tra liệu dK eK x x với mọi x e Z26