Trong khóa học viết mã của tôi, tôi đã được giao bài tập sau:
ElGamal đã đề xuất sơ đồ chữ ký số sau sử dụng logarit rời rạc trên một trường $\mathbb{F}_p$, ở đâu $p$ là một số nguyên tố lớn.
Bước 1) Mọi người đều đồng ý về số nguyên tố $p$ và một máy phát điện
$g$ vì $\mathbb{F}_p^*$.
Bước 2) A (và tất cả các mục đích sử dụng khác) chọn một số mũ bí mật $d_A$, và công khai
$e_A\equiv g^{d_A}\mod p$ (giống như trong hệ thống mật mã ElGamal).
Bước 3) Để ký một tin nhắn, được mã hóa dưới dạng số nguyên $m$ với $0\le m\le
p-1$, A chọn một số nguyên ngẫu nhiên
$k$ tương đối nguyên tố để $p-1$ (I E. $\gcd(k,p-1)=1$). Sau đó tính toán $r\equiv g^k \mod p$ và giải phương trình
$g^m\equiv e_A^r r^s
\mod p$ trong những điều chưa biết $s$. Trong trường hợp $s=0$ (khá khó xảy ra), cô ấy bắt đầu lại với một cách khác $k$. Cuối cùng, A gửi cho B thông điệp $m$ cùng với cặp $(r,s)$, đó là chữ ký của cô ấy cho tin nhắn đó.
Bước 4) Beatriz kiểm tra xem $g^m \equiv
e_A^r r^s \mod p$. Nếu điều này đúng, B chấp nhận rằng chữ ký $(r,s)$ thực sự thuộc về A.
a) Kiểm tra xem Ana có biết tất cả những gì cô ấy cần tính toán không $s$.
b) Kiểm tra xem C không thể giả làm A mà không biết $d_A$, nghĩa là không thể giải bài toán logarit rời rạc, và do đó $B$ có thể chắc chắn rằng thông điệp thực sự đến từ A.
c) Tại sao A phải loại bỏ $k$ nếu nó chỉ ra rằng $s=0$?
Đây là những gì tôi có:
a) Kể từ khi $r\equiv g^k\mod p$ và $e_A=g^{d_A}\mod p$ sau đó:
$$g^m\equiv e_A^rr^s\equiv (g^{d_A})^{r}(g^k)^s=g^{d_Ar+ks}\mod p$$
Và, định lý nhỏ của Fermat ngụ ý rằng $m\equiv d_Ar+ks\mod p-1\Rightarrow ks\equiv m-d_Ar\mod p-1$. Do đó, kể từ khi $\gcd(k,p-1)=1$ chúng tôi có cái đó $k$ là nghịch đảo trong $\mathbb{F}^*_p$ và vì thế $s\equiv k^{-1}(m-d_Ar)\mod p-1$. Do đó, chúng tôi đã hoàn thành, vì Ana biết $p,k,m,d_A$ và $r$.
b) Nếu $C$ muốn giả vờ là $A$, nó cần gửi $m$ và $(r,s)$ như vậy mà $g^m\equiv e_A^rr^s\mod p$. Nhưng mà $s$ phụ thuộc $d_A$ như chúng ta đã thấy trong $a)$. Do đó, chúng ta không thể xây dựng $s$ không biết $d_A$, và như vậy, nếu $C$ muốn giả vờ là $B$, nó cần tìm $d_A$. Nhưng điều đó thật khó, vì điều duy nhất chúng ta biết về $d_A$ (nếu chúng ta không $A$) đó là $e_A\equiv g^{d_A}\mod p$ và vì vậy, giả vờ là $A$ tương đương với việc giải một bài toán logarit rời rạc.
c) Nếu $s=0$ sau đó $g^m\equiv e_A^r\equiv g^{d_Ar}\mod p$ và vì thế $m\equiv d_Ar\mod p-1$. Từ đây tôi bị mắc kẹt, vì đây là thông tin duy nhất tôi có, nhưng tôi không hiểu làm thế nào điều này cho phép chúng tôi xây dựng một chữ ký mà không cần biết $d_A$. Tất nhiên, chúng ta có thể giải quyết $m\equiv d_Ar\mod p-1$, sẽ có $\gcd(r,p-1)$ các giải pháp và sau đó kiểm tra xem cái nào là đúng $d_A$, nhưng $\gcd(r,p-1)$ có thể gần $p-1$ nếu chúng ta gặp xui xẻo, và điều đó có nghĩa là quá trình này diễn ra theo cấp số nhân, và nó không tốt hơn việc giải logarit rời rạc.
Nếu bạn có thể kiểm tra xem a) và b) có đúng không và cho tôi gợi ý về c) thì tôi sẽ rất biết ơn.
