رمزنگاری منحنی بیضوی (Elliptic Curve Cryptography)

رمزنگاری منحنی بیضوی (ECC) یک رمزنگاری به روش کلید عمومی است که بر اساس ساختاری جبری از منحنی‌های بیضوی بر روی میدانهای متناهی طراحی شده‌است. این رمزنگاری در مقایسه با بقیه رمزنگاری‌های مبتنی بر میدانهای گالوا برای ایجاد امنیت یکسان، به کلید کوچکتری نیازدارد.

منحنی‌های بیضوی برای تبادل کلید، امضاهای دیجیتال، تولیدکننده‌های شبه تصادفی و سایر وظایف کاربرد دارند. . به‌طور غیر مستقیم، آنها با ترکیب کلید تواقفی با طرح رمزنگاری متقارن می‌توانند برای رمزگذاری مورد استفاده قرار گیرند. منحنی‌های بیضوی همچنین در چندین تجزیه اعدادطبیعی نیز استفاده شده‌است که این الگوریتم‌ها دارای کاربردهایی در زمینهٔ رمزنگاری هستند، مانند فاکتور منحنی بیضوی Lenstra.

مقدمه

رمزنگاری کلید عمومی بر پایه غیرقابل حل بودن برخی از مسائل ریاضی است. . در اوایل سیستم‌های مبتنی بر کلید عمومی با این فرض که پیدا کردن دو یا بیشتر از دو عامل اول بزرگ برای یک عدد صحیح بزرگ مشکل است، امن تلقی می‌شدند. برای پروتکلهای مبتنی بر منحنی بیضوی، فرض بر این است که پیدا کردن لگاریتم گسسته از یک عنصر تصادفی منحنی بیضوی با توجه به یک نقطه پایهٔ عمومی شناخته شده غیرعملی می‌باشد که همان مسئله لگاریتم منحنی بیضوی یا ECDLP است. امنیت رمزنگاری منحنی بیضوی وابسته به توانایی محاسبهٔ ضرب نقطه ای است و عدم توانایی در محاسبهٔ ضرب شونده با داشتن ضرب‌کننده و حاصل ضرب نقطه ای است. اندازه منحنی بیضوی، میزان سختی مسئله رامشخص می‌نماید.

مؤسسه ملی استاندارد و تکنولوژی ایالات متحده (NIST) رمزنگاری منحنی بیضوی را در مجموعه B الگوریتم‌های پیشنهاد شده توصیه کرده‌است، به‌طور ویژه الگوریتم منحی بیضوی Diffie-Hellman برای تبادل کلید و الگوریتم امضای دیجیتال منحنی بیضوی برای امضای دیجیتال. آژانس امنیت ملی ایالات متحده استفاده از این الگوریتم‌ها با کلید به طول ۳۴۸ بیت را برای محافظت از اطلاعاتی که به عنوان فوق سری طبقه‌بندی شده‌اند مجاز اعلام کرده‌است. اما در اوت ۲۰۱۵ این آژانس اعلام کرد قصد دارد رمزهای مجموعهB را به علت نگرانی از حملات کامپیوترهای کوانتومی، با رمزهای جدید جایگزین کند.

اگرچه در سال ۲۰۰۰ گواهی RSA منقضی شد، ممکن است گواهی‌هایی برای تحتپوشش قرار دادن جنبه‌هایی از تکنولوژی ECC وجود داشته باشد. اما عده ای اظهار می‌کنند که امضای دیجیتال منحنی بیضوی متعلق به دولت ایالات متحده و برخی طرح‌های عملی تبادل کلید برپایهٔ منحنی بیضوی بدون نقض آنها قابل پیاده‌سازی است از جمله RSA Laboratories و Daniel J. Bernstein. بزرگترین مزیتی که رمزنگاری منحنی بیضوی تضمین می‌کند، طول کوتاه‌تر کلید، کاهش حافظه مورد نیاز و الزامات انتقال می‌باشد به این معنا که منحنی بیضوی می‌تواند همان سطح امنتی را ارائه دهد که سیستم‌های برپایه RSA با یک عدد پایه بزرگتر و در نتیجه با کلید بزرگتر ارائه می‌دهد. به عنوان مثال یککلید عمومی منحنی بیضوی به طول ۲۵۶ بیت امنیتی معادل با یک کلید عمومی RSA به طول ۳۰۷۲ بیت فراهم می‌کند.

تاریخچه

استفاده از رمزنگاری منحنی بیضوی در سال ۱۹۸۵ مستقلاً توسط Neal Koblitz و Victor S. Miller پیشنهاد شد. این الگوریتم از سال ۲۰۰۴ و ۲۰۰۵ مورد استفاده وسیع قرار گرفت.

تئوری

به منظور فراهم کردن نیازهای رمزنگاری امروز، منحنی بیضی یک صفحه منحنی است تا اینکه بر روی یک میدان محدود باشد که شامل نقطه هاییست که معادله زیررا برآورده می‌کند:

همراه یک نقطه مشخص در بینهایت ∞. این مجموعه در کنار گروهی از عملگرهای منحنی بیضوی تشکیل یک گروه آبلی می‌دهد که یک نقطه در بی‌نهایت به عنوان عنصر مشخص کننده دارد. ساختار این گروه از گروه تقسیم زیر به ارث رسیده‌است:

طرح‌های رمزنگاری

تعداد زیادی پروتکل‌های بر پایهٔ لگاریتم گسسته برای منحنی بیضوی اتخاذ شده‌اند که {\displaystyle (\mathbb {Z} _{p})^{\times }} را بایک منحنی بیضوی جایگزین می‌کند:

• طرح تبادل کلید منحنی بیضوی Diffie-Hellman که بر پایه طرح Diffie-Hellman است.
• طرح رمزنگاری مجتمع منحنی بیضوی که به طرح رمزنگاری منحنی بیضوی تکمیل شده یا به اختصار طرح رمزنگاری منحنی بیضوی شناخته می‌شود.
• الگوریتم‌های منحنی بیضوی امضای دیجیتال که برپایهٔ الگورتم‌های امضای دیجیتال است.
• طرح تغییرشکل که از متریک منهتن Harrison's p-adic استفاده می‌کند.
• الگوریتم امضای دیجیتال منحنی ادوارد که بر پایهٔ امضای شونر (Schnorr) است و از منحنی‌های به هم پیچیدهٔ ادوارد استفاده می‌کند.
• طرح تبادل کلید ECMQV که برپایه تبادل کلید MQV است.
• طرح گواهی ضمنی ECQVدر کنفرانس RSA در سال ۲۰۰۵ آژانس امنیت ملی مجموعه B را که منحصراً از ECC برای تولید امضای دیجیتال و تبادل کلید استفاده می‌کرد، معرفی کرد.

اخیراً تعداد زیادی رمزنگاری اولیه برپایهٔ نگاشت دوتایی بر روی منحنی‌های بیضوی متعدد مانند Weil و Tate pairings معرفی شده‌اند. طرح‌هایی که بر پایه آنها هستند، رمزنگاری‌های برپایه هویت کارامدی، در کنار امضاهای برپایهٔ جفت سازی، signcryption، تبادل کلید و بازرمزنگاری پروکسی فراهم می‌کنند.

پیاده‌سازی

برخی از ملاحظات پیاده‌سازی معمول عبارتند از:

پارامترهای دامنه

برای استفاده از این روش رمزنگاری، تمامی طرف‌ها باید روی تمامی عناصری که منحنی بیضوی را تعریف می‌کنند، توافق کنند که به این عناصر پارامترهای دامنه اطلاق می‌شود. میدان در حالت عدد اول با حرف P و در حالت دوتایی با حروف m , f تعریف می‌شود. منحنی نیز با ثابت‌های a , b تعریف می‌شود که در معادله تعریف منحنی به کار رفته‌است. نهایتاً، زیرگروه حلقوی با G (تولیدکننده) تعریف می‌گردد. برای کاربردهای رمزنگاری order G کوچکترین عددصحیح مثبت n است که n.G=O ,معمولاً، عدد اول می‌باشد. از آنجا که n سایز یک زیرگروه است، از قضیه لاگرانژ پیروی می کندکه بدین معناست باید عددی صحیح باشد. در کاربردهای رمزنگاری این عدد که h که cofactor نامیده می‌شود، باید کوچکتر یا مساوی ۵ و در بهترین حالت ۱ باشد. به‌طور خلاصه در حالت عدد اول، پارمترهای دامنه(p,a,b,G,n,h) و در حالت دوتایی (m,f,a,b,G,n,h)هستند.

پارمترهای دامنه می‌بایست پیش از استفاده اعتبارسنجی شوند مگر در حالتی که تضمینی وجود داشته باشد که توسط یکی از طرفین مورد اعتماد و بر مبنای کاربردشان، تولید شده‌است. تولید این پارامترها معمولاً توسط تمام شرکت کننده‌ها انجام نمی‌شود زیرا مستلزم محاسبهٔ تعداد نقاط روی منحنی می‌باشد که بسیار وقت گیر و مشکل برای پیاده‌سازی است. در نتیجه تعداد زیادی از افراد مورد تأیید، پارامترهای دامنه را برای تعداد زیادی از سایزهای میدان پرکاربرد محاسبه و منتشر کرده‌اند. این پارامترها به «منحنی استاندارد» یا «منحنی‌های معروف» شناخته می‌شوند. یک منحنی معروف می‌تواند توسط نام یا تشخیص دهندهٔ شی منحصر به فرد که در اسناد زیر موجود است، ارجاع داده شود:

• NIST, Recommended Elliptic Curves for Government Use
• SECG, SEC 2: Recommended Elliptic Curve Domain Parameters
• ECC Brainpool (RFC 5639), ECC Brainpool Standard Curves and Curve

Generation

بردار‌های تست SECG نیز در دسترس می‌باشند.NIST نیز تعداد زیادی از منحنی‌های SECG را تأیید کرده‌است درنتیجه هم پوشانی بزرگی بین مشخصه‌های منتشر شده توسط NIST و SECG وجود دارد. پارامترهای دامنهٔ EC می‌تواند توسطنام یا مقدار مشخص شود. اگر فردی بخواهد پارامترهای دامنهٔ خود را بسازد، باید میدان اساسی را انتخاب کند و از یکی از روش‌های زیر برای یافتن منحنی با تعداد نقاط مناسب استفاده کند:

• انتخاب یک منحنی تصادفی و یک الگوریتم شمارش نقطه مانند االگوریتم اسکوف یا اسکوف-الکین-آتکین
• انتخاب یک منحنی تصادفی از خانواده ای که محاسبهٔ تعداد نقاط آن آسان است.
• انتخاب تعدادی نقطه و تولید منحنی شامل این نقاط توسط تکنیک ضرب مختلط گروه منحنی‌های زیر ضعیف بوده و از آنها باید پرهیز شود:
• منحنی روی که n عدد صحیح نباشد زیرا در مقابل حمله‌های ویل دیسنت آسیب پذیرند.
• منحنی‌هایی که در آنها n بر قابل تقسیم است زیرا به ازای b کوچک در برابر حمله‌های MOV آسیب‌پذیر است. این حمله‌ها از مسئله لگاریتم گسسته در یک میدان افزونه برای حل ECDLP استفاده می‌کنند. حدود B باید به گونه ای انتخاب شود که لگاریتم گسسته در میدان حداقل به سختی محاسبه لگاریتم در منحنی بیضوی E(F) باشد.
• منحنی‌ها به گونه ای که در مقابل حملاتی که نقاط روی منحنی را به گروه‌های افزونه ای نگاشت می‌کند، آسیب‌پذیر است.

طول کلید

از آنجا که سریع‌ترین الگوریتم‌های شناخته شدهٔ حل ECDLP به O(√n) مرحله نیاز دارد، اندازه میدان مربوطه باید حدود دو برابر پارامتر امنیت باشد. برای مثال، برای یک پارامتر امنیت ۱۲۸ بیتی ما به میدان F_q با مقدار نیازمندیم. این امر می‌تواند درتناقض با رمزنگاری میدان محدود که در آن کلید عمومی به طول ۳۰۷۲ بیت و کلید خصوصی به طول ۲۵۶ بیت بود یا رمزنگاری عدد صحیح عامل بندی (factorization) که نیازمند عدد ۳۰۷۲ بیتی n است و کلید خصوصی نیز به همیناندازه است، باشد. اما کلید عمومی می‌تواند برای بازدهی بهتر به خصوص زمانیکه توان مصرفی محدود است، کوتاه‌تر باشد.

دشوارترین طرح ECC شکسته شده کلیدی به طول ۱۱۲ بیت برای حالت میدان عدد اول و کلید به طول ۱۰۹ بیت برای میدان دودویی داشت. اولی در سال ۲۰۰۹ و با استفاده از خوشه ای ۲۰۰ تایی از کنسول بازی نسل سوم شکسته شد که می‌توانست در حالتی که به‌طور پیوستهدر حال اجرا باشد، ظرف مدت سه ماه و نیم این کار را انجام دهد. دومی در سال ۲۰۰۴ و با استفاده از ۲۴۰۰ رایانه طی ۱۷ ماه شکسته شد.

پروژه فعلی معطوف به شکستن رمز ECC2K-130 است که چالشی از سوی Certicom است و از CPU‌ها، GPU ها و FPGA های متنوعی استفاده می‌کند. مختصات پروژه ای یک ارزیابی دقیق از قوانین جمع نشان می‌دهد که برای جمع دو نقطه در میدان Fنه تنها به تعداد زیادی عملیات جمع و ضرب بلکه به نقیض‌های زیادی نیز احتیاج داریم. عملیات نقیض یک الی دو برابر کندتر از ضرب است. اما نقاط منحنی در دستگاه‌های مختصات متنوعی می‌توانند نشان داده شوند که باعث می‌شود برای جمع نیاز به عملیات نقیض نداشته باشند. تعدادی از از این سیستم‌ها معرفی شده‌اند: در سیستم projective هر نقطه با سه مولفه X,Y,Z تحت رابطه نشان داده می‌شود. در سیستم ژاکوبین با همین مولفه‌ها اما تحت رابطه نشان داده می‌شود، در سیستم لوپز داهام رابطه به صورت است. در ژاکوبین تعمیم یافته همان روابط به کار رفته‌است اما مولفه‌های ذخیره شده و به کار رفته برای محاسبات می‌باشد. در سیستم زاکوبین-کدنفسکی پنج مولفه وجود دارند. توجه کنید که ممکن است عرف‌های نامگذاری مختلفی وجود داشته باشدبه عنوان مثال استاندارد، IEEE P1363-2000 از مولفه‌های projective برای اشاره به آنچه عموماً مولفه‌های ژاکوبین خوانده می‌شود، استفاده می‌کند.

کاهش سریع

باقیمانده‌گیری بر p می‌تواند خیلی سریع تر اتفاق بیفتد اگر عدد اول p یک عدد اول شبه مرسن باشد که یعنی به عنوان مثال در مقایسه با روش بارت، افزایش سرعتی در مقیاس اردری وجود دارد. این افزایش سرعت عملی می‌باشد از این حاصب می‌شود که باقی مانده بر اعداد اول تزدیک به توان دو نسبت به بقیه اعداد در کامپیوتر به علت وجود عملیات‌های دودویی سریع تر انجام می‌شود. منحنی روی میدان F_p با عدد اول شبه مرسن p توسط NIST توصیه شده‌است. امایکی دیگر از برتربی‌های منحنی‌های NIST استفاده از a=-۳ است که عملیات جمعرا در سیستم ژاکوبین تسهیل می‌کند.

با توجه به برنستین و لانژ بسیار از تصمیمات کارایی بهتر NIST FIPS 186-2 شبه بهینه هستند. بقیه منحنی‌ها ایمن ترند و به همین سرعت اجرا می‌شوند.

کاربردها

منحنی‌های بیضوی برای رمزنگاری، امضای دیجیتال و تولید شبه تصادفی و کاربردهای دیگر کارایی دارند. همین‌طور در الگوریتم‌های تجزیه اعداد صحیح نیز کاربرد دارند که در رمزنگاری‌هایی مانند Lenstra elliptic curve factorization به کار می‌رود.

در سال 1999 NIST 15 منحنی بیضوی را پیشنهاد داد. به‌طور خاص FIPS 186-4 ده میدان محدود توصیه شده دارد.

• پنج میدان عدد اول که در آنها p عدد اول مشخصی به طول‌های ۱۹۲, ۲۲۴, ۲۵۶, ۳۸۴, ۵۲۱ هستند. برای هر کدام از این

میدان‌ها یک منحنی بیضوی اراِئه شده‌است.

• پنج میدان دودویی برای مقادیر 163, 233, 283, 409,571 m. برای هر میدان باینری یک منحنی بیضوی و یک منحنی Koblitz انتخاب شده‌است؛ بنابراین پیشنهادهای NIST 5 میدان عدد اول و ۵ میدان دودیی را دربردارد. منحنی‌ها به منظور بهینه‌سازی امنیت و پیاده‌سازی انتخاب شده‌اند.

در سال ۲۰۱۳ نیویورک تایمز اعلام کرد که تولید تصادفی بیت منحنی بیضوی قطعی دوگانه به دلیل تأثیرات ناسا به استانداردهای NIST اضافه شده‌است که یک ضعف عمدی در الگوریتم و منحنی بیضوی داشت. RSA در سپتامبر ۲۰۱۳ توصیه ای منتشر کرد که از کاربرانش خواسته بود استفاده از نرم‌افزارهای برپایه تولید تصادفی بیت منحنی بیضوی قطعی دوگانه را قطع کنند. متخصصان رمزنگاری همچنین نگرانی خود را بابت امنیت منحنی‌های توصیه شده توسط NIST ابراز کرده‌اند و پیشنهاد بازگشت به رمزنگاری‌های مستقل از منحنی‌های بیضوی را داده اند. رمزنگاری بیضوی برای رمزنگاری‌های بیت کوین به کار می‌رود.

امنیت

حملات کانال جانبی

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

راه فرار

متخصصان رمزنگاری دربارهٔ این موضوع که NSA یک راه فرار kleptographic در حداقل یکی از تولیدکنندگان شبه تصادفی برپایه منحنی بیضوی قرار داده‌است، ابرازنگرانی کرده‌اند. اطلاعات درز کرده توسط کارمند پیشین NSA، ادوارد اسنودن، ادعا می‌کند NSA یک راه فرار استاندارد Dual EC DRBG قرا داده‌است. یک تحلیل بر روی راه‌های فرار احتمالی به این نتیچه رسید که یک حمله کننده در مقام الگوریتم رمز پنهان، تنها با داشتن ۳۲ بیت از خروجی PRNG می‌تواند کلیدهای رمزنگاری را بدست آورد.

پروژه منحنی امن به منظور فهرست کردن منحنی‌هایی که پیاده‌سازی ایمن آنها آسان است و به شکل کاملاً عمومی قابل بازبینی هستند اجرا شده‌است تا شانس وجود راه فرار را به حداقل برساند.

حملات محاسبات کوانتومی

با استفاده از الگوریتم شور و به کمک محاسبه لگاریتم گسسته بر روی یک کامپیوتر کوانتومی فرضی می‌توان رمزنگاری منحنی بیضوی را شکست. آخرین منابع کوانتومی تخمین زده شده مورد نیاز برای شکستن منحنی به طول ۲۵۶ بیت مدول ۲۳۳۰ کوبیت و ۱۲۶ میلیار گیت توفولی است. به عنوان مقایسه، استفاده از الگوریتم شور برای شکستن الگوریتم RSA نیازمند ۴۰۹۸ کوبیت و ۵٫۲ تریلیون گیت توفولی است در حالتی که طول کلید ۲۰۴۸ بیت باشد. این بدین معناست که منحنی بیضوی هدف ساده‌تری برای کامپیوترهای کوانتومی است در قیاس با RSA. تمامی این ارقام بسیار بیشتر از توانایی کامپیوترهای کوانتومی است که تا کنون ساخته شده‌است و تخمین زده می‌شود ساخته شدن این چنین کامپیوترهایی دهه‌ها به طول خواهد انجامید.

تبادل کلید Supersingular Isogeny Diffie–Hellman نسخه ای فراکوانتومی ایمن از رمزنگاری منحنی بیضوی فراهم می‌کند که از isogenies برای پیاده‌سازی تبادل کلید Diffie–Hellman استفاده می‌کند. این تبادل کلید ازبسیاری ازهمان ریضایت میدان موجود در منحنی بیضوی استفاده می‌کند و سربار محاسباتی وانتقالی مشابه سیستم‌ها ی کلید عمومی فعلی دارد.

در آگوست 2015 NSA اعلام کرد که برنامه ای برای انتقال به محیط رمزنگاری جدید دارد که در مقابل حملات کوانتومی ایمن است. متأسفانه استفاده از منحنی بیضوی با وجود پیشرفت در تحقیقات روی کامپیوترهای کوانتومی، گسترش یافته‌است که نیازمند بازارزیابی استراتژی‌های رمزنگاری است.

حملات منحنی نامعتبر

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

منبع: wikipedia