رمزنگاری منحنی بیضوی

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

رمزنگاری منحنی بیضوی[ویرایش]

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

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

مقدمه[ویرایش]

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

موسسه ملی استاندارد و تکنولوژی ایالات متحده (NIST) رمزنگاری منحنی بیضوی را در مجموعه B الگوریتم های پیشنهاد شده توصیه کرده است ، به طور ویژه الگوریتم منحی بیضوی Diffie-Hellman برای تبادل کلید و الگوریتم امضای دیجیتال منحنی بیضوی برای امضای دیجیتال.آژانس امنیت ملی ایالات متحده استفاده از این الگوریتم ها با کلید به طول 348 بیت را برای محافظت از اطلاعاتی که به عنوان فوق سری طبقه بندی شده اند مجاز اعلام کرده است. اما در آگوست 2015 این آژانس اعلام کرد قصد دارد رمز های مجموعهB را به علتنگرانی از حملات کامپیوترهای کوانتومی، با رمز های جدید جایگزین کند.

اگرچه در سال 2000 گواهی RSA منقضی شد، ممکن است گواهی هایی برای تحتپوشش قرار دادن جنبه هایی از تکنولوژی ECC وجود داشته باشد. اما عده ای اظهار می کنند که امضای دیجیتال منحنی بیضوی متعلق به دولت ایالات متحده و برخی طرح های عملی تبادل کلید برپایه ی منحنی بیضوی بدون نقض آنها قابل پیاده سازی است از جمله RSA Laboratories و Daniel J. Bernstein.بزرگترین مزیتی که رمزنگاری منحنی بیضوی تضمین می کند، طول کوتاه تر کلید،کاهش حافظه مورد نیاز و الزامات انتقال می باشد به این معنا که منحنی بیضوی می تواند همان سطح امنتی را ارائه دهد که سیستم های برپایه RSA با یک عدد پایه بزرگتر و در نتیجه با کلید بزرگتر ارائه می دهد.به عنوان مثال یککلید عمومی منحنی بیضوی به طول 256 بیت امنیتی معادل با یک کلید عمومی RSA به طول 3072 بیت فراهم می کند.

تاریخچه[ویرایش]

استفاده از رمزنگاری منحنی بیضوی در سال 1985 مستقلا توسط Neal Koblitz و Victor S. Miller پیشنهاد شد.این الگوریتم از سال 2004 و 2005 مورد استفادهوسیع قرار گرفت.

تئوری[ویرایش]

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

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

طرح های رمزنگاری[ویرایش]

تعداد زیادی پروتکل های بر پایه ی لگاریتم گسسته برای منحنی بیضوی اتخاذ شده اند که را بایک منحنی بیضوی جایگزین می کند:

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

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

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

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

پارامترهای دامنه[ویرایش]

برای استفاده از این روش رمزنگاری،تمامی طرف ها باید روی تمامی عناصری که منحنی بیضوی را تعریف می کنند، توافق کنند که به این عناصر پارامتر های دامنه اطلاق می شود. میدان در حالت عدد اول با حرف P و در حالت دوتایی با حروف m , f تعریف می شود.منحنی نیز با ثابت های a , b تعریف می شود که در معادله تعریف منحنی به کار رفته است.نهایتا، زیرگروه حلقوی با G (تولیدکننده) تعریف می گردد.برای کاربرد های رمزنگاری order G کوچکترین عددصحیح مثبت n است که n.G=O ,معمولا، عدد اول می باشد.از آنجا که n سایز یک زیرگروه است، از قضیه لاگرانژ پیروی می کندکه بدین معناست باید عددی صحیح باشد. در کاربرد های رمزنگاری این عدد که h که cofactor نامیده می شود، باید کوچکتر یا مساوی 5 و در بهترین حالت 1 باشد.به طور خلاصه در حالت عدد اول، پارمترهای دامنه(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) مرحله نیاز دارد، اندازه میدان مربوطه باید حدود دو برابر پارامتر امنیت باشد.برای مثال، برای یک پارامتر امنیت 128 بیتی ما به میدان F_q با مقدار نیازمندیم.این امر می تواند درتناقض با رمزنگاری میدان محدود که در آن کلید عمومی به طول 3072 بیت و کلید خصوصی به طول 256 بیت بود و یا رمزنگاری عدد صحیح عامل بندی (factorization) که نیازمند عدد 3072 بیتی n است و کلید خصوصی نیز به همیناندازه است، باشد. اما کلید عمومی می تواند برای بازدهی بهتر به خصوص زمانیکه توان مصرفی محدود است ، کوتاه تر باشد.

دشوار ترین طرح ECC شکسته شده کلیدی به طول 112 بیت برای حالت میدان عدد اول و کلید به طول 109 بیت برای میدان دودویی داشت.اولی در سال 2009 و با استفاده از خوشه ای 200 تایی از کنسول بازی نسل سوم شکسته شد که می توانست در حالتی که به طور پیوستهدر حال اجرا باشد، ظرف مدت سه ماه و نیم این کار را انجام دهد. دومی در سال 2004 و با استفاده از 2400 رایانه طی 17 ماه شکسته شد.

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

کاهش سریع[ویرایش]

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

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

کاربرد ها[ویرایش]

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

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

  • پنج میدان عدد اول که در آنها p عدد اول مشخصی به طول های 192, 224, 256, 384, 521 هستند. برای هر کدام از این

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

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

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

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

حملات کانال جانبی[ویرایش]

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

راه فرار[ویرایش]

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

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

حملات محاسبات کوانتومی[ویرایش]

با استفاده از الگوریتم شور و به کمک محاسبه لگاریتم گسسته بر روی یک کامپیوتر کوانتومی فرضی می توان رمزنگاری منحنی بیضوی را شکست.آخرین منابع کوانتومی تخمین زده شده مورد نیاز برای شکستن منحنی به طول 256 بیت مدول 2330 کوبیت و 126 میلیار گیت توفولی است.به عنوان مقایسه، استفاده از الگوریتم شور برای شکستن الگوریتم RSA نیازمند 4098 کوبیت و 5.2 تریلیون گیت توفولی است در حالتی که طول کلید 2048 بیت باشد. این بدین معناست که منحنی بیضوی هدف ساده تری برای کامپیوتر های کوانتومی است در قیاس با RSA .تمامی این ارقام بسیار بیشتر از توانایی کامپیوتر های کوانتومی است که تا کنون ساخته شده است و تخمین زده می شود ساخته شدن این چنین کامپیوترهایی دهه ها به طول خواهد انجامید.

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

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

حملات منحنی نامعتبر[ویرایش]

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

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

  • ویکی‌پدیای انگلیسی