Giả sử p là số nguyên tố lớn và q =(p-1)/2 cũng là số nguyên tố. Cho α và β là hai phần tử nguyên thuỷ của Zp. Giá trị logαβ không công khai và giả sử rằng không có khả năng tính toán được giá trị của nó. | Vietebooks Nguyễn Hoàng Cương Giả sử p là số nguyên tố lớn và q p-1 2 cũng là số nguyên tố. Cho a và p là hai phần tử nguyên thuỷ của Zp. Giá trị logap không công khai và giả sử rằng không có khả năng tính toán được giá trị của nó. Hàm Hash h 0 . q-1 x 0 . q-1 Zp 0 được định nghĩa như sau h x1 x2 aX1px2 mod p . hàm hash logarithm rời rạc Trong phần này ta sẽ mô tả một hàm Hash do Chaum-Van Heyst và Pfĩtmann đưa ra. Hàm này an toàn do không thể tính được logarithm rời rạc. Hàm Hast này không đủ nhanh để dùng trong thực tế song nó đơn giản và cho một ví dụ tốt về một hàm Hash có thể an toàn dưới giả thuyết tính toán hợp lý nào số. Hàm Hash Caum-Van Heyst- Pfĩtmann được nêt trong hình . Sau đây sẽ chứng minh một định lý liên quan đến sự an toàn của hàm Hast này. Định lý . Nếu cho trước một va chạm với hàm Hash Chaum-Van Heyst-Pfĩtmann h cổ thể tính được logarithm rời rạc logafi một cách cổ hiệu quả. Chứng minh Giả sử cho trước va chạm h X1 X2 h x3 x4 trong đó x15x2 x3 x4 . Như vậy ta có đồng dư thức sau aX1pX2 ax3px4 hay ax1px2 ax3px4 mod p Ta kí hiệu D UCLN x4-x2 p-1 Trang 7 Vietebooks Nguyễn Hoàng Cương Vì p-1 2q q là số nguyên tố nên d e 1 2 q p-1 . Vì thế ta có 4 xác suất với d sẽ xem xét lần lượt dwois đây. Trước hết giả sử d 1 khi đó cho y X4-X2 -1 mod p-1 ta có p p x4-x2 y mod p a x1-x2 y mod p Vì thế có thể tính loarithm rời rạc logap như sau logap X1-X3 X4-X2 -1mod p-1 Tiếp theo giả sử d 2. Vì p-1 2q lẻ nên UCLN x4-x2 q 1. Giả sử y x4-x2 -1 mod q xét thấy x4-x2 y kq 1 với số nguyên k nào đó. Vì thế ta có p x4-x2 y pkq 1 mod p -1 k p mod p p mod p Vì pq -1 mod p Nên a x4-x2 y p x1-x3 mod p p mod p Từ đó suy ra rằng logap x1-x3 y mod p-1 logap xrx3 y mod p-1 Ta có thể dễ dàng kiểm tra thấy một trong hai xác suất trên là đứng. Vì thế như trong trường hợp d 1 ta tính được logap. Xác suất tiếp theo là d q. Tuy nhiên q-1 x1 0 và q-1 x3 0 nên q-1 x4-x2 - q-1 do vậy UCLN x4-x2 p-1 không thể bằng q nói cách khác trường hợp này không xảy ra. Xác suất cuối cùng
