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

الگوریتم امضای دیجیتال یک استاندارد دولت فدرال ایالات متحده یا 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–1)/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 کافی است.