ElGamal, tin nhắn > p

Giả sử rằng chúng ta có:

p = 89
g = 5
khóa công khai: 17
khóa riêng: 73

Nếu chúng tôi cố gắng mã hóa thông báo M = 53 (M < p), thì chúng tôi nhận được (c1, c2) == (55, 67) và thông báo tiếp theo sẽ giải mã tốt.

Tuy nhiên, nếu chúng ta cố mã hóa tin nhắn M = 91 (M > p), thì chúng ta nhận được (c1, c2) == (44, 57) và các lần giải mã tin nhắn khác không thành công (kết quả là "2").

Có 3 câu hỏi:

• Tại sao nó xảy ra?
• Có thể khôi phục tin nhắn gốc M nếu chúng ta biết thực tế là (m > p) đã sử dụng, p, g, khóa công khai và có (c1, c2)?
• Có thể khôi phục tin nhắn gốc M nếu chúng ta biết sự thật rằng (m > p) đã sử dụng, p, g, khóa chung và có một số tin nhắn được mã hóa (c1, c2)?

Tại sao nó xảy ra?

Điều này xảy ra bởi vì, theo phương thức số học 89, các số $2$ và $91$ là tương đương: $91 \bmod 89 = 2$. Bạn thường sẽ thấy điều này được ký hiệu là $91 \equiv 2 \pmod{89}$.

Nếu bạn chưa quen với số học mô-đun - thì đây cũng giống như cách tính giờ $0$ và $12$ trên đồng hồ truyền thống là tương đương - nó "bao bọc".

Có thể khôi phục thông điệp gốc M nếu chúng ta biết thực tế là (m > p) đã sử dụng, p, g, khóa công khai và có (c1, c2)?

Không nói chung, trong khi vẫn cho phép giải mã tin nhắn $m < p$.

trong một cụ thể trường hợp, trong đó bạn có một bản mã và biết rằng thông điệp ban đầu đã có trong e.g. $[2p, 3p - 1]$, bạn có thể khôi phục nó bằng cách thêm phần bù thích hợp sau khi giải mã.

Trong thực tế, điều này không đặc biệt hữu ích, vì vậy như đã đề cập trong các nhận xét ở trên, người ta chia nhỏ thông báo $m$ vào trong $m_1, \ldots, m_n$ như vậy mà $m_i < p$. Mỗi tin nhắn một phần sau đó được mã hóa riêng lẻ.