داﺪﮑﺸﻧه ﻋ ﻮمرﯾﺎ ﯽو آﻣﺎر
ﺗﻬﯿﻪ ﻭ ﺗﻨﻈﯿﻢ :ﻣﺠﺘﺒﯽ ﺭﻓﯿﻌﯽ
ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ
ﻧﺴﺨﻪ ﺍﻭﻝ −ﺑﻬﺎﺭ ۱۴۰۲
ﺭﻣﺰﻧﮕﺎﺭﯼ
ﻭﯾﮋﮔﯽ ﭘﺎﯾﻪﺍﯼ ﮐﻪ ﺍﺯ ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ ۱ﺍﻧﺘﻈﺎﺭ ﺩﺍﺭﯾﻢ ﺑﻪ ﻗﺮﺍﺭ ﺯﯾﺮ ﺍﺳﺖ:
−ﺗﺎﻣﯿﻦ ﻭﯾﮋﮔﯽ ﺟﺎﻣﻌﯿﺖ ۲ﺑﺪﯾﻦ ﻣﻌﻨﺎ ﮐﻪ ﺍﻣﮑﺎﻥ ﺗﻐﯿﯿﺮ ﭘﯿﺎﻡ ﻭ ﺟﻌﻞ ﺑﺮﭼﺴﺒﯽ ﻣﻨﻄﺒﻖ ﺑﺎ ﭘﯿﺎﻡ ﺍﻣﮑﺎﻥﭘﺬﯾﺮ ﻧﺒﺎﺷﺪ.
ﺑﺎ ﺍﯾﻨﺤﺎﻝ ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ ﻭﯾﮋﮔﯽﻫﺎﯼ ﺩﯾﮕﺮﯼ ﻫﻢ ﺩﺍﺭﺩ ﮐﻪ ﺁﻥ ﺭﺍ ﻧﺴﺒﺖ ﺑﻪ ﮐﺪ ﺍﺻﺎﻟﺖﺳﻨﺠﯽ ﭘﯿﺎﻡ ﻣﺘﻤﺎﯾﺰ ﻣﯽﮐﻨﺪ:
−ﺗﺎﻣﯿﻦ ﻭﯾﮋﮔﯽ ﺍﻧﮑﺎﺭ ﻧﺎﭘﺬﯾﺮﯼ ۳ﺑﺪﯾﻦ ﻣﻌﻨﺎ ﮐﻪ ﺍﮔﺮ ﻓﺮﺩﯼ ﭘﯿﺎﻣﯽ ﺭﺍ ﺍﻣﻀﺎ ﮐﺮﺩ ﻧﺘﻮﺍﻧﺪ ﺁﻥ ﺭﺍ ﺍﻧﮑﺎﺭ ﮐﻨﺪ.
−ﺩﺍﺭﺍﯼ ﻭﯾﮋﮔﯽ ﺍﺛﺒﺎﺕﭘﺬﯾﺮﯼ ﻋﻤﻮﻣﯽ ۴ﺍﺳﺖ ﺑﺪﯾﻦ ﻣﻌﻨﺎ ﮐﻪ ﻻﺯﻡ ﻧﯿﺴﺖ ﺣﺘﻤﺎ ﯾﮏ ﮐﻠﯿﺪ ﺧﺼﻮﺻﯽ ﺩﺍﺷﺘﻪ ﺑﺎﺷﯿﻢ ﺗﺎ ﺑﺘﻮﺍﻧﯿﻢ ﺁﻥ ﺭﺍ ﺍﺛﺒﺎﺕ ﮐﻨﯿﻢ ﻭ
ﻫﺮ ﺷﺨﺼﯽ ﻣﯽﺗﻮﺍﻧﺪ ﺑﺮﺭﺳﯽ ﺍﺛﺒﺎﺕ ﺭﺍ ﺍﻧﺠﺎﻡ ﺩﻫﺪ.
−ﻗﺎﺑﻞ ﺍﻧﺘﻘﺎﻝ ۵ﺑﻪ ﻏﯿﺮ ﺍﺳﺖ ﺑﺪﯾﻦ ﻣﻌﻨﯽ ﮐﻪ ﺍﮔﺮ ﯾﮏ ﭘﯿﺎﻡ ﺑﻪ ﻣﺎ ﺑﺪﻫﻨﺪ ﻣﯽﺗﻮﺍﻥ ﺁﻥ ﺭﺍ ﻧﺰﺩ ﺷﺨﺺ ﺩﯾﮕﺮﯼ ﺑﺮﺩ ﻭ ﻧﺸﺎﻥ ﺩﺍﺩ ﮐﻪ ﺁﻥ ﺍﻣﻀﺎﯼ )ﺗﺎﯾﯿﺪ(
ﺷﺨﺺ ﻣﻮﺭﺩ ﻧﻈﺮ ﺍﺳﺖ.
ﺗﻌﺮﯾﻒ ) ۱ﻃﺮﺡ ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ( ﯾﮏ ﻃﺮﺡ ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ ) ،Π = (Gen, Sign, Vrfyﯾﮏ ﺳﻪ ﺗﺎﯾﯽ ﺍﺯ ﺍﻟﮕﻮﺭﯾﺘﻢﻫﺎﯼ ﺍﺣﺘﻤﺎﻻﺗﯽ ﮐﺎﺭﺍ ﺑﻪ
ﺷﺮﺡ ﺯﯾﺮ ﺍﺳﺖ:
−ﺍﻟﮕﻮﺭﯾﺘﻢ ﺗﻮﻟﯿﺪ ﮐﻠﯿﺪ ) :(Genﺑﻪ ﻋﻨﻮﺍﻥ ﻭﺭﻭﺩﯼ ﭘﺎﺭﺍﻣﺘﺮ ﺍﻣﻨﯿﺘﯽ λﺭﺍ ﺩﺭﯾﺎﻓﺖ ﻭ ﺩﻭ ﮐﻠﯿﺪ ) (pk, skﺑﺎ ﻃﻮﻝ nﺭﺍ ﺑﻪ ﺧﺮﻭﺟﯽ ﺑﺮ ﻣﯽﮔﺮﺩﺍﻧﺪ ﮐﻪ
pkﮐﻠﯿﺪ ﻋﻤﻮﻣﯽ ﻭ skﮐﻠﯿﺪ ﺧﺼﻮﺻﯽ ﺍﺳﺖ.
−ﺍﻟﮕﻮﺭﯾﺘﻢ ﺍﻣﻀﺎ ) :(Signﺑﻪ ﻋﻨﻮﺍﻥ ﻭﺭﻭﺩﯼ ﮐﻠﯿﺪ ﺧﺼﻮﺻﯽ skﻭ ﭘﯿﺎﻡ mﺭﺍ ﺩﺭﯾﺎﻓﺖ ﻭ ﺑﻪ ﻋﻨﻮﺍﻥ ﺧﺮﻭﺟﯽ ﺍﻣﻀﺎﯼ σﺭﺍ ﺑﺮ ﻣﯽﮔﺮﺩﺍﻧﺪ.
−ﺍﻟﮕﻮﺭﯾﺘﻢ ﺗﺼﺪﯾﻖ ) :(Vrfyﺑﻪ ﻋﻨﻮﺍﻥ ﻭﺭﻭﺩﯼ ﮐﻠﯿﺪ ﻋﻤﻮﻣﯽ pkﻭ ﭘﯿﺎﻡ mﻭ ﺍﻣﻀﺎﯼ σﺭﺍ ﺩﺭﯾﺎﻓﺖ ﻭ ﺧﺮﻭﺟﯽ ﺁﻥ ﯾﮏ ﺑﯿﺖ bﺍﺳﺖ ﺍﮔﺮ b = 1
ﺑﺎﺷﺪ ﯾﻌﻨﯽ ﺍﻣﻀﺎ ﻣﻌﺘﺒﺮ ﺍﺳﺖ ﻭ ﺍﮔﺮ b = 0ﺑﺎﺷﺪ ﺍﻣﻀﺎ ﻧﺎﻣﻌﺘﺒﺮ ﺍﺳﺖ.
1 Digital Signature
2 Integrity
3 Non-repudation
4 Publicly Verifiable
5 Transferable
۱
ﻻﺯﻡ ﺑﻪ ﺫﮐﺮ ﺍﺳﺖ ﮐﻪ ﯾﮏ ﻃﺮﺡ ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ ﻫﻤﻮﺍﺭﻩ ﻣﯽﺑﺎﯾﺴﺖ ﺩﺍﺭﺍﯼ ﻭﯾﮋﮔﯽ ﺻﺤﺖ ﺑﺎﺷﺪ:
.Vrfypk (m, Signsk (m)) = 1
ﺗﻌﺮﯾﻒ ) ۲ﺍﻣﻨﯿﺖ ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ( ﮔﻮﯾﯿﻢ ﺳﯿﺴﺘﻢ ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ ) Π = (Gen, Sign, Vrfyﺩﺍﺭﺍﺭﯼ ﺍﻣﻨﯿﺖ ﺟﻌﻞ ﻧﺎﭘﺬﯾﺮﯼ ﺍﺳﺖ ،ﺍﮔﺮ ﺑﺮﺍﯼ
ﻫﺮ ﻣﻬﺎﺟﻢ ﮐﺎﺭﺍﯼ ﺍﺣﺘﻤﺎﻻﺗﯽ ،ﺗﺎﺑﻊ ﻧﺎﭼﯿﺰ )( ϵﻭﺟﻮﺩ ﺩﺍﺷﺘﻪ ﺑﺎﺷﺪ ﺑﻪ ﻗﺴﻤﯽ ﮐﻪ:
Pr{SignforgeΠ,A (n) = 1} ≤ ϵ(n).
ﺟﺎﯾﯿﮑﻪ ﺁﺯﻣﺎﯾﺶ ) SignforgeΠ,A (nﺑﻪ ﺻﻮﺭﺕ ﺯﯾﺮ ﺗﻌﺮﯾﻒ ﻣﯽﺷﻮﺩ:
−ﭼﺎﻟﺸﮕﺮ ﺍﻟﮕﻮﺭﯾﺘﻢ ) (sk, pk) ← Gen(1nﺭﺍ ﺍﺟﺮﺍ ﻣﯽﮐﻨﺪ ﻭ ﮐﻠﯿﺪ ﻋﻤﻮﻣﯽ pkﺭﺍ ﺩﺭ ﺍﺧﺘﯿﺎﺭ ﻣﻬﺎﺟﻢ ﻗﺮﺍﺭ ﻣﯽﺩﻫﺪ.
−ﺑﻪ ﻣﻬﺎﺟﻢ ﺍﻣﮑﺎﻥ ﺩﺳﺘﺮﺳﯽ ﺍﻭﺭﺍﮐﻠﯽ ﺑﻪ ﺍﻟﮕﻮﺭﯾﺘﻢ ﺍﻣﻀﺎ ﺩﺍﺩﻩ ﻣﯽﺷﻮﺩ ،ﺑﺪﯾﻦ ﻣﻌﻨﺎ ﮐﻪ ﻫﺮ ﭘﯿﺎﻣﯽ ﺭﺍ ﮐﻪ ﺑﺨﻮﺍﻫﺪ ﻣﯽﺗﻮﺍﻧﺪ ﺍﻣﻀﺎﯼ ﻣﻌﺘﺒﺮ ﺁﻥ ﺭﺍ ﺩﺭﯾﺎﻓﺖ
ﮐﻨﺪ .ﺩﺭ ﻧﻬﺎﯾﺖ ﻣﻬﺎﺟﻢ ﻣﯽﺑﺎﯾﺴﺖ ﯾﮏ ﭘﯿﺎﻡ ﺭﺍ ﮐﻪ ﻗﺒﻼ ﺍﻣﻀﺎﯼ ﺁﻥ ﺭﺍ ﺩﺭﯾﺎﻓﺖ ﻧﮑﺮﺩﻩ ﺑﻪ ﻫﻤﺮﺍﻩ ﯾﮏ ﺍﻣﻀﺎﯼ ﻣﻌﺘﺒﺮ ﺑﺮﺍﯼ ﭼﺎﻟﺸﮕﺮ ﺍﺭﺳﺎﻝ ﻧﻤﺎﯾﺪ.
ﺩﺭ ﺍﯾﻦ ﻣﺮﺣﻠﻪ ﻓﺮﺽ ﮐﻨﯿﺪ ﺗﻤﺎﻣﯽ ﭘﯿﺎﻡﻫﺎﯼ ﺍﺭﺍﮐﻞ ﺷﺪﻩ ﺩﺭ ﻟﯿﺴﺖ Qﺍﺿﺎﻓﻪ ﺷﺪﻩﺍﻧﺪ.
∈ .m
−ﺧﺮﻭﺟﯽ ﺁﺯﻣﺎﯾﺶ ۱ﺍﺳﺖ )ﺑﺪﯾﻦ ﻣﻌﻨﺎ ﮐﻪ ﻣﻬﺎﺟﻢ ﻣﻮﻓﻖ ﺷﺪﻩ ﺍﺳﺖ( ﺍﮔﺮ ﻭ ﺗﻨﻬﺎ ﺍﮔﺮ Vrfypk (m, σ) = 1ﻭ / Q
ﺍﺳﺘﻔﺎﺩﻩ ﺍﺯ RSAﺑﺮﺍﯼ ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ ۱
ﺍﺑﺘﺪﺍ ﺑﻪ ﺳﺮﺍﻍ ﺍﺳﺘﻔﺎﺩﻩ ﺍﺯ ) RSAﮐﺘﺎﺑﯽ( ﺑﺮﺍﯼ ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ ۶ﻣﯽﺭﻭﯾﻢ .ﺑﺮﺍﯼ ﺍﯾﻦ ﻣﻨﻈﻮﺭ ﻣﯽﺑﺎﯾﺴﺖ ﺍﻟﮕﻮﺭﯾﺘﻢﻫﺎﯼ ﻃﺮﺡ ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ )ﺍﻟﮕﻮﺭﯾﺘﻢ
ﺗﻮﻟﯿﺪ ﮐﻠﯿﺪ ،ﺍﻟﮕﻮﺭﯾﺘﻢ ﺍﻣﻀﺎ ﻭ ﺍﻟﮕﻮﺭﯾﺘﻢ ﺗﺼﺪﯾﻖ ﺍﻣﻀﺎ( ﺭﺍ ﺑﻪ ﻃﻮﺭ ﺩﻗﯿﻖ ﻣﺸﺨﺺ ﮐﻨﯿﻢ:
:Gen −ﺭﻭﯼ ﻭﺭﻭﺩﯼ 1nﺍﻟﮕﻮﺭﯾﺘﻢ ) GenRSA(1nﺭﺍ ﺍﺟﺮﺍ ﮐﺮﺩﻩ ﻭ ﭘﺎﺭﺍﻣﺘﺮﻫﺎﯼ ) (N, e, dﺭﺍ ﺑﺪﺳﺖ ﻣﯽﺁﻭﺭﺩ .ﮐﻠﯿﺪ ﻋﻤﻮﻣﯽ ﺭﺍ ﺑﺎ ⟩ ⟨N, eﻭ
ﮐﻠﯿﺪ ﺧﺼﻮﺻﯽ ﺭﺍ ﺑﺎ ⟩ ⟨N, dﻣﻘﺪﺍﺭ ﺩﻫﯽ ﻣﯽﮐﻨﺪ.
∗
،mZNﺍﻣﻀﺎ ﺭﺍ ﺑﻪ ﺻﻮﺭﺕ ﺯﯾﺮ ﻣﺤﺎﺳﺒﻪ ﻣﯽﮐﻨﺪ: :Sign −ﺭﻭﯼ ﻭﺭﻭﺩﯼ ﮐﻠﯿﺪ ﺧﺼﻮﺻﯽ ⟩ sk = ⟨N, dﻭ ﭘﯿﺎﻡ
σ = [md mod N ].
∗ ∗
σ ∈ ZNﺧﺮﻭﺟﯽ ۱ﺭﺍ ﺗﻮﻟﯿﺪ ﻣﯽﮐﻨﺪ ﺍﮔﺮ ﻭ ﺗﻨﻬﺎ ﺍﮔﺮ : m ∈ ZNﻭ ﺍﻣﻀﺎﯼ :Vrfy −ﺭﻭﯼ ﻭﺭﻭﺩﯼ ﮐﻠﯿﺪ ﻋﻤﻮﻣﯽ ⟩ ،pk = ⟨N, eﭘﯿﺎﻡ
] m = [σ e mod N
ﻻﺯﻡ ﺑﻪ ﺫﮐﺮ ﺍﺳﺖ ﮐﻪ ﺳﺎﺧﺖ ﺍﺭﺍﯾﻪ ﺷﺪﻩ ﺑﺎﻻ ،ﺑﻪ ﺳﺒﺐ ﺩﺍﺷﺘﻦ ﺧﺼﯿﺼﻪ ﻫﻤﻮﻣﻮﺭﻓﯿﮏ ﺩﺍﺭﺍﯼ ﺍﻣﻨﯿﺖ ﺟﻌﻞ ﻧﺎﭘﺬﯾﺮﯼ ﻧﯿﺴﺖ .ﺑﺮﺍﯼ ﺍﻣﻦ ﮐﺮﺩﻥ ﺁﻥ ﻣﯽﺑﺎﯾﺴﺖ
ﺍﺯ ﺗﺎﺑﻊ ﺩﺭﻫﻢ ﺳﺎﺯ ﺍﺳﺘﻔﺎﺩﻩ ﮐﻨﯿﻢ ﮐﻪ ﺩﻭ ﻭﯾﮋﮔﯽ ﻣﻬﻢ ﺯﯾﺮ ﺭﺍ ﺑﺮﺍﯼ ﺁﻥ ﺗﺎﻣﯿﻦ ﻣﯽﮐﻨﺪ:
−ﺍﻣﻨﯿﺖ ﺟﻌﻞ ﻧﺎﭘﺬﯾﺮﯼ،
−ﺍﮔﺮ ﻃﻮﻝ ﭘﯿﺎﻡ ﺧﯿﻠﯽ ﺑﺰﺭﮒ ﺑﺎﺷﺪ ،ﺍﻣﻀﺎ ﺗﻮﻟﯿﺪﯼ ﻧﯿﺰ ﺧﯿﻠﯽ ﺑﺰﺭﮒ ﻣﯽﺷﻮﺩ .ﺑﺎ ﺍﯾﻨﺤﺎﻝ ﺑﺎ ﺍﺳﺘﻔﺎﺩﻩ ﺍﺯ ﺗﺎﺑﻊ ﺩﺭﻫﻢ ﺳﺎﺯ ﻣﯽﺗﻮﺍﻧﯿﻢ ﻃﻮﻝ ﺍﻣﻀﺎ ﺭﺍ
ﮐﺎﻫﺶ ﺩﻫﯿﻢ.
6 Textbook RSA digital signature
۲
ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ ﺑﺎ RSAﻭ ﺗﺎﺑﻊ ﺩﺭﻫﻢ ﺳﺎﺯﯼ ۲
ﺣﺎﻝ ﺑﺎ ﺍﺳﺘﻔﺎﺩﻩ ﺍﺯ ﺗﺎﺑﻊ ﺩﺭﻫﻢ ﺳﺎﺯ ﺩﺭ ﺍﻟﮕﻮﺭﯾﺘﻢ RSAﮐﺘﺎﺑﯽ ﻣﺒﺎﺩﺭﺕ ﺑﻪ ﺳﺎﺧﺖ ﺍﻣﻀﺎﯼ ﺟﻌﻞﻧﺎﭘﺬﯾﺮ ﻣﯽﮐﻨﯿﻢ:
:Gen −ﺭﻭﯼ ﻭﺭﻭﺩﯼ 1nﺍﻟﮕﻮﺭﯾﺘﻢ ) GenRSA(1nﺭﺍ ﺍﺟﺮﺍ ﮐﺮﺩﻩ ﻭ ﭘﺎﺭﺍﻣﺘﺮﻫﺎﯼ ) (N, e, dﺭﺍ ﺑﺪﺳﺖ ﻣﯽﺁﻭﺭﺩ .ﮐﻠﯿﺪ ﻋﻤﻮﻣﯽ ﺭﺍ ﺑﺎ ⟩ ⟨N, eﻭ
ﮐﻠﯿﺪ ﺧﺼﻮﺻﯽ ﺭﺍ ﺑﺎ ⟩ ⟨N, dﻣﻘﺪﺍﺭ ﺩﻫﯽ ﻣﯽﮐﻨﺪ.
∗
،mZNﺍﻣﻀﺎ ﺭﺍ ﺑﻪ ﺻﻮﺭﺕ ﺯﯾﺮ ﻣﺤﺎﺳﺒﻪ ﻣﯽﮐﻨﺪ: :Sign −ﺭﻭﯼ ﻭﺭﻭﺩﯼ ﮐﻠﯿﺪ ﺧﺼﻮﺻﯽ ⟩ sk = ⟨N, dﻭ ﭘﯿﺎﻡ
σ = [H(m)d mod N ].
∗ ∗
σ ∈ ZNﺧﺮﻭﺟﯽ ۱ﺭﺍ ﺗﻮﻟﯿﺪ ﻣﯽﮐﻨﺪ ﺍﮔﺮ ﻭ ﺗﻨﻬﺎ ﺍﮔﺮ : m ∈ ZNﻭ ﺍﻣﻀﺎﯼ :Vrfy −ﺭﻭﯼ ﻭﺭﻭﺩﯼ ﮐﻠﯿﺪ ﻋﻤﻮﻣﯽ ⟩ ،pk = ⟨N, eﭘﯿﺎﻡ
] H(m) = [σ e mod N
ﻻﺯﻡ ﺑﻪ ﺫﮐﺮ ﺍﺳﺖ ﮐﻪ ﺳﺎﺧﺖ ﻓﻮﻕ ﺑﺎ ﺍﯾﻦ ﻓﺮﺽ ﮐﻪ ﺗﺎﺑﻊ ﺩﺭﻫﻢﺳﺎﺯ ﺍﺳﺘﻔﺎﺩﻩ ﺷﺪﻩ ﺩﺭ ﻣﺪﻝ ﺍﻭﺭﺍﮐﻞ ﺗﺼﺎﺩﻓﯽ ﺩﺭ ﻧﻈﺮ ﮔﺮﻓﺘﻪ ﺷﺪﻩ ﺩﺍﺭﺍﯼ ﺍﻣﻨﯿﺖ ﺟﻌﻞﻧﺎﭘﺬﯾﺮﯼ
ﻣﯽﺑﺎﺷﺪ.
ﺳﯿﺴﺘﻢ ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ ﺍﺳﺘﺎﻧﺪﺍﺭﺩ ۳
ﺳﯿﺴﺘﻢ ﺩﯾﮕﺮﯼ ﮐﻪ ﺩﺭ ﻋﻤﻞ ﻣﻮﺭﺩ ﺍﺳﺘﻔﺎﺩﻩ ﻗﺮﺍﺭ ﻣﯽﮔﯿﺮﺩ ،ﺳﯿﺴﺘﻢ ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ ﺍﺳﺘﺎﻧﺪﺍﺭﺩ ۷ﻣﯽﺑﺎﺷﺪ .ﺳﯿﺴﺘﻢ ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ ﺍﺳﺘﺎﻧﺪﺍﺭﺩ ) (ⅮSSﯾﺎ
ﺍﻟﮕﻮﺭﯾﺘﻢ ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ ) (ⅮSAﺭﺍ NISTﺩﺭ ﺳﺎﻝ ۱۹۹۱ﻃﺮﺍﺣﯽ ﮐﺮﺩ ﮐﻪ ﻣﺒﺘﻨﯽ ﺑﺮ ﻓﺮﺽ ﻟﮕﺎﺭﯾﺘﻢ ﮔﺴﺴﺘﻪ ﺍﺳﺖ.
ﻓﺮﺽ ﮐﻨﯿﺪ Gﯾﮏ ﺍﻟﮕﻮﺭﯾﺘﻢ ﺍﺣﺘﻤﺎﻻﺗﯽ ﮐﺎﺭﺍ ﺑﺎﺷﺪ ﮐﻪ ﺭﻭﯼ ﻭﺭﻭﺩﯼ 1nﺧﺮﻭﺟﯽ ) (p, q, gﺭﺍ ﺗﻮﻟﯿﺪ ﻣﯽﮐﻨﺪ ،ﺟﺎﯾﯿﮑﻪ pﻭ qﻧﺴﺒﺖ ﺑﻪ ﻫﻢ ﺍﻭﻝ ﻫﺴﺘﻨﺪ ﻭ
gﻧﯿﺰ ﯾﮏ ﻣﻮﻟﺪ ﺍﺯ ﺯﯾﺮﮔﺮﻭﻩ ∗ Zpﺑﺎ ﺩﺭﺟﻪ ﯼ qﺍﺳﺖ .ﺷﺮﺡ ﻫﺮ ﯾﮏ ﺍﺯ ﺍﻟﮕﻮﺭﯾﺘﻢﻫﺎﯼ ﻃﺮﺡ ﺍﻣﻀﺎﯼ ﺩﯾﺠﯿﺘﺎﻝ ⅮSSﺩﺭ ﺍﺩﺍﻣﻪ ﺁﻭﺭﺩﻩ ﺷﺪﻩ ﺍﺳﺖ:
∗
:Gen −ﺭﻭﯼ ﻭﺭﻭﺩﯼ 1nﺍﻟﮕﻮﺭﯾﺘﻢ Gﺭﺍ ﺍﺟﺮﺍ ﮐﺮﺩﻩ ﻭ ﭘﺎﺭﺍﻣﺘﺮﻫﺎﯼ ) (p, q, gﺭﺍ ﺑﺪﺳﺖ ﻣﯽﺁﻭﺭﯾﻢ .ﻓﺮﺽ ﮐﻨﯿﺪ H : {0, 1} → Zqﯾﮏ
ﺗﺎﺑﻊ ﺩﺭﻫﻢﺳﺎﺯ ﺑﺎﺷﺪ .ﺍﺑﺘﺪﺍ ﯾﮏ x ← Zqﺑﻪ ﻃﻮﺭ ﯾﮑﻨﻮﺍﺧﺖ ﻭ ﺗﺼﺎﺩﻓﯽ ﺍﻧﺘﺨﺎﺏ ﮐﺮﺩﻩ ﻭ ] y = [g x mod pﺭﺍ ﻣﺤﺎﺳﺒﻪ ﻣﯽﮐﻨﯿﻢ .ﺳﭙﺲ
ﮐﻠﯿﺪ ﻋﻤﻮﻣﯽ ﺭﺍ ﺑﺎ ⟩ ⟨H, p, q, g, yﻭ ﮐﻠﯿﺪ ﺧﺼﻮﺻﯽ ﺭﺍ ﺑﺎ ⟩ ⟨H, p, q, g, xﻣﻘﺪﺍﺭ ﺩﻫﯽ ﻣﯽﮐﻨﯿﻢ.
∗
:Sign −ﺭﻭﯼ ﻭﺭﻭﺩﯼ ﮐﻠﯿﺪ ﺧﺼﻮﺻﯽ ⟩ ⟨H, p, q, g, xﻭ ﭘﯿﺎﻡ } m ∈ {0, 1ﺍﺑﺘﺪﺍ ∗ k ← Zqﺭﺍ ﺑﻪ ﻃﻮﺭ ﯾﮑﻨﻮﺍﺧﺖ ﻭ ﺗﺼﺎﺩﻓﯽ ﺍﻧﺘﺨﺎﺏ
ﮐﺮﺩﻩ ﻭ ﺳﭙﺲ ] r = [[g k mod p] mod qﻭ ] s = [(H(m) + xr).k −1 mod qﺭﺍ ﻣﺤﺎﺳﺒﻪ ﻣﯽﻧﻤﺎﯾﯿﻢ .ﺩﺭ ﺍﻧﺘﻬﺎ ﻧﯿﺰ ﺯﻭﺝ )(r, s
ﺭﺍ ﺑﻪ ﻋﻨﻮﺍﻥ ﺍﻣﻀﺎ ﺑﻪ ﺧﺮﻭﺟﯽ ﻣﯽﻓﺮﺳﺘﯿﻢ.
∗
:Vrfy −ﺭﻭﯼ ﻭﺭﻭﺩﯼ ﮐﻠﯿﺪ ﻋﻤﻮﻣﯽ ⟩ ،⟨H, p, q, g, yﭘﯿﺎﻡ } m ∈ {0, 1ﻭ ﺍﻣﻀﺎﯼ ) (r, sﮐﻪ r ∈ Zqﻭ ∗ s ∈ Zqﺍﺳﺖ ،ﻣﻘﺎﺩﯾﺮ
] u1 = [H(m).s−1 mod qﻭ ] u2 = [r.s−1 mod qﺭﺍ ﻣﺤﺎﺳﺒﻪ ﻣﯽﮐﻨﯿﻢ .ﺧﺮﻭﺟﯽ ۱ﺭﺍ ﺑﻪ ﻋﻨﻮﺍﻥ ﺧﺮﻭﺟﯽ ﺑﺮ ﻣﯽﮔﺮﺩﺍﻧﯿﻢ ﺍﮔﺮ ﻭ ﺗﻨﻬﺎ
ﺍﮔﺮ:
].r = [[g u1 y u2 mod p] mod q
7 Digital Signature Standard
۳