الگوریتم امضای دیجیتال

الگوریتم امضای دیجیتال یک استاندارد دولت فدرال ایالات متحده یا FIPS برای امضای دیجیتال است. این الگوریتم در آوت ۱۹۹۱ توسط موسسه ملی استاندارد و تکنولوژی (NIST) برای استفاده به عنوان استاندارد امضای دیجیتال (دی‌اس‌ای) پیشنهاد شد ودر ۱۹۹۳ FIPS پذیرفته شد. در سال ۱۹۹۶ نیز یک اصلاحیه کوچک با عنوان FIPS 186-1 انتشار یافت. این استاندارد بعدها در سال‌های ۲۰۰۰ و ۲۰۰۹ بسط داده شد و نام FITPS 186-2 و FITPS186-3 گرفت.

(دی اس ای) به واسطهٔ حق امتیاز اختراع ۵،۲۳۱،۶۶۸ ایالت متحده در ۲۶ جولای ۱۹۹۱ که منتسب به دیوید و. کراویتز یکی از کارمندان پیشین NSA می‌باشد، تحت پوشش قرار گرفته است. این حق امتیاز اختراع همانطور که توسط دبیر بازرگانی ایلت واشنگتن دی. سی بیان شده است، به ایالت متحده آمریکا واگذار شده وNIST آنرا در سر تا سر جهان به صورت حق امتیاز رایگان قرار داده است. دکتر کلوس پی. اشنور ادعا می‌کند که حق امتیاز اختراع (دی اس ای) با شماره ۴٬۹۹۵٬۰۸۲ (منقضی شده) متعلق به وی بوده است. اما این ادعا رد شده است. (دی اس ای) یک نوع دیگر از طرح امضای ELGamal می‌باشد.

تولید کلید

تولید کلید شامل دو مرحله است. مرحله اول انتخاب پارامترها الگوریتم است که می‌توانند بین کاربران مختلف سیستم به اشتراک گذاشته شوند، در حالیکه مرحلهٔ دوم به محاسبهٔ کلیدهای خصوصی و عمومی برای یک کاربر مجزا می‌پردازد.

انتخاب پارامترهای الگوریتم

• یک تابع پنهانی در هم تصویب شدهٔ H را انتخاب کنید

بر روی طول کلید N,Lتصمیم بگیرید. این اندازه گیری اولیهٔ قدرت پنهانی کلید است. دی اس اس اصلی ما را وادار می‌کند تا مضربی از ۶۴ بین ۵۱۲و ۱۰۲۴ باشد.

• یک بیت اولیه n را به گونه‌ای برگزینید که q. N کمتر یا مساوی با طول خروجی درهم باشد.
• یک بیت اولیهٔ l با مدول p را به گونه‌ای انتخاب کنید که p–۱ مضربی از q باشد.
• عددی را به عنوان g = h(p–۱)/q برگزینید.

پارامترهای الگوریتم (p, q, g) ممکن است بین کاربران سیستم به اشتراک گذاشته شود. به ازای هر کاربر یک مجموعه از پارامترها به کلیدها تخصیص میابد.

تخصیص کلید به کاربر

به ازای هر کاربر یک مجموعه از پارامترها به کلید تخصص میابد مرحله دوم کلیدهای عمومی و اختصاصی را برای یک کاربر مجزا محاسبه می‌کند.

• انتخاب x با روش‌های تصادفی
• محاسبهٔ باقیمانده y = g^x
• کلید عمومی (p, q, g, y)و کلید خصوصی x است.

الگوریتم تولید امضا

• تولید یک کلید تصادفی k باید بعد از یکبار استفاده از بین رفته و دیگر مورد استفاده قرار نگیرد.
• سپس زوج مرتب امضا (r,s)به صورت زیر محاسبه می‌شوند.

r = (g^k mod p) mod q s = [k^-1(H(M) + xr)] mod q

(r,s) به پیام M الحاق شده وفرستاده می‌شود.

درستی الگوریتم تصدیق امضا

گیرنده ^,M و (r^,,s^,) را دریافت می‌کنند. مقادیر زیر را محاسبه می‌کند:

• w = (s’)^-1 mod q
• u1= [H(M’)w] mod q
• u2= [(r’)w] mod q
• v = [(g^u1y^u2) mod p] mod q

اگر v=r^, امضا معتبر است.

حساسیت

با DSA پیش بینی ناپذیری و محرمانه بودن و منحصر به فردی مقدار تصادفی امضا K بسیار حائز اهمیت است. اهمیت این موارد به اندازه‌ای است که نقض هر یک از این سه لازمه می‌تواند کل کلید خصوصی شما را برای یک مهاجم آشکار نماید. دو بار استفاده از یک مقدار مشابه حتی با مخفی نگه داشتن K استفاده از یک مقدار قابل پیش بینی یا فاش شدن حتی چند بیت از K در هر یک چند امضا برای در هم شکستن DSA کافی است.