الگوریتم امضای دیجیتال منحنی بیضوی

از ویکیپدیا، دانشنامه آزاد
پرش به ناوبری پرش به جستجو

در رمزنگاری ، الگوریتم امضای دیجیتال منحنی بیضوی ( ECDSA ) گونه‌ای از الگوریتم امضای دیجیتال (DSA) را ارائه می‌دهد که از رمزنگاری منحنی بیضوی استفاده می‌کند .

اندازه کلید و امضا [ ویرایش ]

همانطور که با رمزنگاری بیضوی منحنی به طور کلی، کمی اندازه از کلید عمومی بر این باور بودند مورد نیاز برای ECDSA است حدود دو برابر اندازه از سطح امنیتی ، در بیت. [1] به عنوان مثال، در سطح امنیتی 80 بیت - به این معنی که یک مهاجم حداکثر نیاز به حدودعملیات برای یافتن کلید خصوصی - اندازه یک کلید خصوصی ECDSA 160 بیت است، در حالی که اندازه یک کلید خصوصی DSA حداقل 1024 بیت است. از سوی دیگر، اندازه امضا برای DSA و ECDSA یکسان است: تقریباً بیت ها، کجا سطح امنیتی است که در بیت اندازه گیری می شود، یعنی حدود 320 بیت برای سطح امنیتی 80 بیت.

الگوریتم تولید امضا [ ویرایش ]

فرض کنید آلیس می خواهد یک پیام امضا شده برای باب بفرستد . در ابتدا، آنها باید بر روی پارامترهای منحنی توافق کنند. علاوه بر میدان و معادله منحنی، نیاز داریمیک نقطه پایه از ترتیب اول روی منحنی. ترتیب ضرب نقطه است .

پارامتر
منحنی میدان منحنی بیضوی و معادله استفاده شده
جی نقطه پایه منحنی بیضوی، نقطه ای روی منحنی که زیر گروهی از مرتبه اول بزرگ n ایجاد می کند.
n ترتیب عدد صحیح G به این معنی است که، جایی که عنصر هویت است.
کلید خصوصی (به طور تصادفی انتخاب شده)
کلید عمومی (محاسبه شده توسط منحنی بیضوی)
متر پیام برای ارسال

سفارش از نقطه پایه باید اول باشد . در واقع، ما فرض می کنیم که هر عنصر غیر صفر حلقه معکوس است، به طوری که باید یک میدان باشد دلالت بر آن داردباید اول باشد (ر.ک. هویت بزوت ).

آلیس یک جفت کلید متشکل از یک عدد صحیح کلید خصوصی ایجاد می کند ، به طور تصادفی در فاصله انتخاب شده است ; و یک نقطه منحنی کلید عمومی. ما استفاده می کنیمبرای نشان دادن ضرب نقطه منحنی بیضوی در یک اسکالر .

برای اینکه آلیس پیامی را امضا کند ، او این مراحل را دنبال می کند:

  1. محاسبه . (در اینجا HASH یک تابع هش رمزنگاری است ، مانند SHA-2 ، که خروجی آن به یک عدد صحیح تبدیل شده است.)
  2. اجازه دهید باشد سمت چپ ترین بیت های ، جایی که طول بیت ترتیب گروه است . (توجه داشته باشید کهمی تواند بیشتر ازاما نه بیشتر . [2] )
  3. یک عدد صحیح تصادفی امن از نظر رمزنگاری انتخاب کنید از جانب .
  4. نقطه منحنی را محاسبه کنید .
  5. محاسبه . اگر، به مرحله 3 برگردید.
  6. محاسبه . اگر، به مرحله 3 برگردید.
  7. امضای جفت است . همچنین یک امضای معتبر است.)


همانطور که استاندارد اشاره می کند، نه تنها برای آن لازم است مخفی بودن، اما انتخاب متفاوت نیز بسیار مهم است برای امضاهای مختلف، در غیر این صورت معادله مرحله 6 قابل حل است ، کلید خصوصی: با دو امضا و ، از همان مجهول استفاده می کند برای پیام های مختلف شناخته شده و ، یک مهاجم می تواند محاسبه کند و ، و از (تمام عملیات در این پاراگراف به صورت مدول انجام می شود ) مهاجم می تواند پیدا کند . از آنجا که، مهاجم اکنون می تواند کلید خصوصی را محاسبه کند .

به عنوان مثال، از این شکست پیاده سازی برای استخراج کلید امضای مورد استفاده برای کنسول بازی پلی استیشن 3 استفاده شد. [3]

یکی دیگر از راه‌هایی که امضای ECDSA ممکن است کلیدهای خصوصی را نشت کند، این است که چه زمانی توسط یک مولد اعداد تصادفی معیوب تولید می شود . چنین شکستی در تولید اعداد تصادفی باعث شد که کاربران کیف پول بیت کوین اندروید وجوه خود را در آگوست 2013 از دست بدهند. [4]

برای اطمینان از آن برای هر پیام منحصر به فرد است، می توان تولید اعداد تصادفی را به طور کامل دور زد و با استخراج امضاهای قطعی تولید کرد. هم از پیام و هم از کلید خصوصی. [5]

الگوریتم تأیید امضا [ ویرایش ]

برای اینکه باب بتواند امضای آلیس را تأیید کند، باید یک کپی از نقطه منحنی کلید عمومی او داشته باشد. . باب می تواند تأیید کند یک نقطه منحنی معتبر به شرح زیر است:

  1. آن را بررسی کنید با عنصر هویت O برابر نیست و مختصات آن در غیر این صورت معتبر است
  2. آن را بررسی کنید روی منحنی قرار دارد
  3. آن را بررسی کنید

پس از آن، باب این مراحل را دنبال می کند:

  1. بررسی کنید که r و s اعداد صحیح هستند. در غیر این صورت امضا نامعتبر است.
  2. محاسبه ، که در آن HASH همان تابع مورد استفاده در تولید امضا است.
  3. بگذارید z باشدسمت چپ ترین بیت های e .
  4. محاسبه و .
  5. نقطه منحنی را محاسبه کنید . اگر در این صورت امضا نامعتبر است
  6. امضا در صورتی معتبر است که ، در غیر این صورت نامعتبر است.

توجه داشته باشید که یک پیاده سازی کارآمد معکوس را محاسبه می کند فقط یک بار. همچنین با استفاده از ترفند شامیر، مجموع دو ضرب اسکالررا می توان سریعتر از دو ضرب اسکالر که به طور مستقل انجام می شود محاسبه کرد. [6]

درستی الگوریتم [ ویرایش ]

بلافاصله مشخص نیست که چرا تأیید حتی به درستی عمل می کند. برای اینکه بفهمید چرا، نقطه منحنی محاسبه شده در مرحله 5 تأیید صحت را به صورت C نشان دهید ،

از تعریف کلید عمومی به عنوان ،

از آنجا که ضرب اسکالر منحنی بیضوی بر جمع توزیع می شود،

بسط تعریف و از مرحله تأیید 4،

جمع آوری اصطلاح رایج ،

گسترش تعریف s از مرحله 6 امضا،

از آنجایی که معکوس یک عنصر، عنصر اصلی است، و حاصلضرب معکوس یک عنصر و عنصر، هویت است، ما باقی می‌مانیم.

از تعریف r ، این مرحله تأیید 6 است.

این فقط نشان می دهد که یک پیام به درستی امضا شده به درستی تأیید می شود. بسیاری از خواص دیگر [ کدام؟ ] برای یک الگوریتم امضای امن مورد نیاز است.

بازیابی کلید عمومی [ ویرایش ]

با دادن پیام m و امضای آلیسدر آن پیام، باب می تواند (به طور بالقوه) کلید عمومی آلیس را بازیابی کند: [7]

  1. بررسی کنید که r و s اعداد صحیح هستند. در غیر این صورت امضا نامعتبر است.
  2. یک نقطه منحنی را محاسبه کنید جایی که یکی از ، ، و غیره (ارائه شده است برای یک عنصر فیلد خیلی بزرگ نیست) و مقداری است که معادله منحنی برآورده شود. توجه داشته باشید که ممکن است چندین نقطه منحنی وجود داشته باشد که این شرایط را برآورده کند و هر مقدار R مختلف منجر به یک کلید بازیابی شده مجزا می شود.
  3. محاسبه ، که در آن HASH همان تابع مورد استفاده در تولید امضا است.
  4. بگذارید z باشدسمت چپ ترین بیت های e .
  5. محاسبه و .
  6. نقطه منحنی را محاسبه کنید .
  7. امضا در صورتی معتبر است که ، با کلید عمومی آلیس مطابقت دارد.
  8. اگر تمام نقاط R ممکن امتحان شده باشد و هیچ کدام با کلید عمومی آلیس مطابقت نداشته باشد، امضا نامعتبر است .

توجه داشته باشید که یک امضای نامعتبر، یا امضای یک پیام دیگر، منجر به بازیابی کلید عمومی نادرست می شود. الگوریتم بازیابی تنها در صورتی می تواند برای بررسی اعتبار یک امضا استفاده شود که کلید عمومی امضاکننده (یا هش آن) از قبل شناخته شده باشد.

درستی الگوریتم بازیابی [ ویرایش ]

با تعریف شروع کنید از مرحله بازیابی 6،

از تعریف از امضای مرحله 4،

از آنجا که ضرب اسکالر منحنی بیضوی بر جمع توزیع می شود،

بسط تعریف و از مرحله ریکاوری 5،

گسترش تعریف s از مرحله 6 امضا،

از آنجایی که حاصلضرب معکوس یک عنصر و عنصر همان هویت است، ما مانده ایم

ترم اول و دوم یکدیگر را خنثی می کنند،

از تعریف ، این کلید عمومی آلیس است.

این نشان می دهد که یک پیام به درستی امضا شده کلید عمومی صحیح را بازیابی می کند، مشروط بر اینکه اطلاعات اضافی برای محاسبه منحصر به فرد نقطه منحنی به اشتراک گذاشته شده باشد. از مقدار امضا r .

امنیت [ ویرایش ]

در دسامبر 2010، گروهی که خود را fail0verflow می‌نامند ، بازیابی کلید خصوصی ECDSA مورد استفاده سونی را برای امضای نرم‌افزار کنسول بازی پلی‌استیشن 3 اعلام کردند . با این حال، این حمله تنها به این دلیل کار می کند که سونی الگوریتم را به درستی پیاده سازی نکرده است، زیرابه جای تصادفی ثابت بود. همانطور که در بخش الگوریتم تولید امضا در بالا اشاره شد، این امر باعث می شودقابل حل است و کل الگوریتم را بی فایده می کند. [8]

در 29 مارس 2011، دو محقق یک مقاله IACR [9] را منتشر کردند که نشان می‌دهد می‌توان کلید خصوصی TLS یک سرور را با استفاده از OpenSSL بازیابی کرد که با منحنی‌های بیضوی DSA در یک میدان باینری از طریق حمله زمان‌بندی احراز هویت می‌شود . [10] این آسیب‌پذیری در OpenSSL 1.0.0e رفع شد. [11]

در آگوست 2013، مشخص شد که اشکالات در برخی از پیاده سازی های کلاس جاوا SecureRandom گاهی اوقات باعث ایجاد برخورد درارزش. این به هکرها این امکان را می‌دهد تا کلیدهای خصوصی را بازیابی کنند و به آن‌ها کنترلی مشابه بر معاملات بیت‌کوین داشته باشند که صاحبان کلیدهای قانونی داشتند، با استفاده از همان سوءاستفاده‌ای که برای فاش کردن کلید امضای PS3 در برخی از برنامه‌های اندرویدی که از جاوا استفاده می‌کنند و برای احراز هویت به ECDSA متکی هستند، استفاده می‌شود. معاملات [12]

این موضوع می تواند توسط یک نسل غیرقابل پیش بینی جلوگیری شود به عنوان مثال، یک روش قطعی همانطور که توسط RFC 6979 توضیح داده شده است.

نگرانی ها [ ویرایش ]

برخی از نگرانی های بیان شده در مورد ECDSA:

  1. نگرانی‌های سیاسی : قابل اعتماد بودن منحنی‌های تولید شده توسط NIST پس از افشای این موضوع که NSA می‌خواهد درهای پشتی را در نرم‌افزار، قطعات سخت‌افزاری و استانداردهای منتشر شده قرار دهد، زیر سؤال رفت . رمزنگاران معروف [13] در مورد نحوه طراحی منحنی های NIST تردیدهایی [14] [15] ابراز کرده اند و آلودگی داوطلبانه قبلاً در گذشته اثبات شده است. [16] [17] (همچنین به مقدمه libssh curve25519 مراجعه کنید . [18] ) با این وجود، مدرکی مبنی بر اینکه منحنی‌های NIST نام‌گذاری شده از یک ضعف نادر بهره‌برداری می‌کنند، هنوز وجود ندارد.
  2. نگرانی‌های فنی : دشواری اجرای صحیح استاندارد، کندی آن و نقص‌های طراحی که باعث کاهش امنیت در پیاده‌سازی‌های دفاعی ناکافی می‌شود. [19]

پیاده سازی ها [ ویرایش ]

در زیر فهرستی از کتابخانه های رمزنگاری که از ECDSA پشتیبانی می کنند، آمده است:

مثال استفاده [ ویرایش ]

Wikipedia.org از ECDSA در مجموعه رمزنگاری TLS برای احراز هویت خود در مرورگرهای وب استفاده می کند، که رونوشت کوتاه شده زیر نشان می دهد.

تاریخ
 $ چهارشنبه 4 مارس 10:24:52 EST 2020 
$ openssl s_client -connect wikipedia.org:443   # خروجی زیر دارای DELETIONS برای اختصار 
CONNECTED(00000003) 
عمق = 2 O = Digital Signature Trust Co., 
CNCA = DST Root verify return:1 
depth=1 C = US, O = Let's Encrypt, CN = Let's Encrypt Authority X3 
verify return:1 
depth=0 CN = *.wikipedia.org 
verify return:1 
--- 
Certificate chain 
0 s:/CN =*.wikipedia.org 
   i:/C=US/O=Let's Encrypt/CN=Let's Encrypt Authority X3 
1 s:/C=US/O=Let's Encrypt/CN=Let's Encrypt Authority X3 
   i:/O=امضای دیجیتال Trust Co./CN=DST Root CA X3 
--- 
گواهی سرور
----- BEGIN گواهی ----- 
MIIHOTCCBiGgAwIBAgISA4srJU6bpT7xpINN6bbGO2 / mMA0GCSqGSIb3DQEBCwUA 
     ... بسیاری از خطوط حذف شده .... 
kTOXMoKzBkJCU8sCdeziusJtNvWXW6p8Z3UpuTw = 
----- END CERTIFICATE ----- 
موضوع = / CN = *. wikipedia.org 
صادر کننده =/C=US/O=بیایید رمزگذاری کنیم/CN=بیایید 
مرجع X3 را رمزگذاری کنیم --- 
هیچ گواهی مشتری نام های CA ارسال نشد 
خلاصه امضای همتا: SHA256 
کلید دمای سرور: ECDH، P-256، 256 بیت 
--- 
SSL handshake خوانده شده است 3353 بایت و 431 بایت نوشته شده 
--- 
جدید، TLSv1/SSLv3، رمز ECDHE-ECDSA-AES256-GCM-SHA384 
کلید عمومی سرور 256 بیتی است. 
مذاکره مجدد ایمن پشتیبانی می شود 
فشرده سازی: هیچکدام 
گسترش: هیچ
بدون مذاکره ALPN 
SSL-Session: 
    Protocol : TLSv1.2 
    رمز : ECDHE-ECDSA-AES256-GCM-SHA384 
    Session-ID: ... DELETED ... 
    Session-ID-ctx: 
    Master-Key: ... DELETED .. . 
    کلید ارگ: هیچ 
    هویت PSK: هیچ 
    اشاره هویت PSK: هیچ 
    نام کاربری SRP: هیچ 
    زمان شروع: 1583335210 
    اتمام مهلت: 300 (ثانیه) 
    تأیید کد بازگشت: 0 (خوب) 
--- 
انجام

همچنین ببینید [ ویرایش ]

منابع [ ویرایش ]

  1. ^ جانسون، دان؛ منزز، آلفرد (1999). "الگوریتم امضای دیجیتال منحنی بیضوی (ECDSA)" . CiteSeerX . CiteSeerX  10.1.1.38.8014 . بازبینی شده در 9 مه 2021 .
  2. NIST FIPS 186-4، ژوئیه 2013، صفحات 19 و 26
  3. هک کنسول 2010 - PS3 Epic Fail بایگانی شده در 15 دسامبر 2014، در ماشین Wayback ، صفحه 123–128
  4. «آسیب‌پذیری امنیتی اندروید» . بازبینی شده در 24 فوریه 2015 .
  5. «RFC 6979 - استفاده قطعی از الگوریتم امضای دیجیتال (DSA) و الگوریتم امضای دیجیتال منحنی بیضی (ECDSA)» . بازبینی شده در 24 فوریه 2015 .
  6. «سیستم اعداد دو پایه در رمزنگاری منحنی بیضوی» (PDF) . بازبینی شده در 22 آوریل 2014 .
  7. ^ Daniel RL Brown SECG SEC 1: Eliptic Curve Cryptography (نسخه 2.0) https://www.secg.org/sec1-v2.pdf
  8. بندل، مایک (۲۹ دسامبر ۲۰۱۰). "هکرها امنیت PS3 را به عنوان Epic Fail، دسترسی نامحدود توصیف می کنند" . Exophase.com . بازیابی شده در 5 ژانویه 2011 .
  9. «آرشیو ePrint Cryptology: گزارش 2011/232» . بازبینی شده در 24 فوریه 2015 .
  10. «نکته آسیب‌پذیری VU#536044 - OpenSSL کلید خصوصی ECDSA را از طریق یک حمله زمان‌بندی از راه دور افشا می‌کند» . www.kb.cert.org .
  11. «ChangeLog» . پروژه OpenSSL . بازبینی شده در 22 آوریل 2014 .
  12. «باگ اندروید کیف پول بیت کوین را خراب می کند» . ثبت نام. 12 آگوست 2013.
  13. اشنایر، بروس (۵ سپتامبر ۲۰۱۳). "NSA در حال شکستن بیشتر رمزگذاری در اینترنت است" . اشنایر در امنیت .
  14. "SafeCurves: انتخاب منحنی های ایمن برای رمزنگاری منحنی بیضوی" . 25 اکتبر 2013.
  15. برنشتاین، دانیل جی. Lange, Tanja (31 مه 2013). "خطرات امنیتی منحنی های NIST" (PDF) .
  16. اشنایر، بروس (15 نوامبر 2007). "داستان عجیب Dual_EC_DRBG" . اشنایر در امنیت .
  17. گرین مایر، لری (18 سپتامبر 2013). "تلاش های NSA برای فرار از فناوری رمزگذاری به استاندارد رمزنگاری ایالات متحده آسیب رساند" . علمی آمریکایی.
  18. «curve25519-sha256@libssh.org.txt\doc - projects/libssh.git» . libssh مخزن مشترک .
  19. برنشتاین، دانیل جی. (۲۳ مارس ۲۰۱۴). "نحوه طراحی یک سیستم امضای منحنی بیضوی" . وبلاگ cr.yp.to .

ادامه مطلب [ ویرایش ]


پیوندهای خارجی [ ویرایش ]