Elgamal là gì
Mã hóa Elgamal hoạt động thế nào?
Trong bài này mình sẽ giải thích cách hoạt động của hệ mật mã ElGamal. Bài có sử dụng một số tính toán được giải thích trong bài trước về RSA. Bạn có thể đọc lại tại đây https://viblo.asia/p/ma-hoa-rsa-hoat-dong-the-nao-3Q75w119ZWb Show Ý tưởng ban đầuNhư bạn đã biết, các hệ mã hóa bất đối xứng sử dụng tính chất của các bài toán mà việc tính xuôi rất dễ dàng nhưng việc tính ngược lại lại tốn nhiều thời gian, có thể đến hàng triệu năm. RSA sử dụng bài toán phân tích ra thừa số nguyên tố, bạn có thể dễ dàng tính Bài toán logarit rời rạcTrong bài viết về RSA mình đã trình bày cách nhanh chóng tính được Cách thực hiệnSinh khóaViệc sinh hệ mã hóa của ElGamal không khó như RSA. Chỉ đơn giản là chọn một số nguyên tố p, một hệ số alpha và một khóa bí mật a. Sau đó tính hệ số Ví dụ chọn luôn p = 11, alpha = 2, a = 3. Ta dễ dàng tính được beta = 2^3 = 8. Vậy ta có public key là p = 11, alpha = 2, beta = 8. Việc tính 8 là 2 mũ mấy ( Mã hóaGiả sử với public key ở trên ta muốn mã hóa số x = 10, ta chọn một số k = 6 chẳng hạn. Ta tính 2 số:
Ok giờ ta có bản mã cần gửi đi là e(y1, y2) = (9, 8). Số k thì bị bỏ đi, vụ này bàn sau. Giải mãViệc giải mã cũng dễ thôi, chỉ cần tính:
Giải thíchXem nào, ta sẽ thấy đc
Dễ mà, đơn giản chỉ thế thôi. Vấn đềNào quay lại vấn đề. Thế vấn đề ở đâu nhỉ. Như đã nói các phép toán trong modulo có số lượng kết quả giới hạn. Điều đơn giản nhất có thể nhìn ra là nếu cứ tính:
Thì rồi sớm hay muộn kết quả cũng lặp lại thành vòng. Ví dụ với p = 11 như trên nhưng chọn alpha = 4 thì ta có:
Đó giờ cứ tính tăng mũ lên thì kết quả cũng chỉ xoay quanh 4->5->9->3->1->4. Vậy thì việc duyệt các số kết quả của bài toán logarit rời rạc trở lên dễ hơn rất nhiều. Nên việc chọn alpha phải tìm cách để vòng kết quả này càng lớn càng tốt, lý tưởng nhất là bằng chính số p. |