رمزنگاری مقدماتی :رمزنگاری منحنی بیضوی یا Elliptic-Curve

در این قسمت میرسیم به بررسی الگریتم رمزنگاری منحنی بیضوی Elliptic-curve cryptography (ECC)

چرا ما به الگریتم منحنی بیضوی نیاز داریم؟ مگر RSA یا DH چش بود؟

اول برسیم به فرمول های الگریتم های RSA که یادتون هست P×Q=N و گفتیم توی مقاله قبلی که امنیتش وابستس به Semi Prime Factorization و امنیت DH هم که یادتونه وابسته بود به Discrete Logarithm Problem ، الگریتم های امضا دیجیتال هم مثل DH هستن !

• اصطلاحا توی رمزنگاری وقتی امنیت یه الگریتیم وابستس به یه چیزی ، ما به اون چیز میگیم Trap Door Function ، یا درب تله یک الگریتم

چرا ما به ECC نیاز داریم؟ مگر این Trap Door ها چقد فجیعن ؟

اگر یادتون باشه گفتم که تنها راه افشا و حمله به یک الگریتم ، Brute Force هست که اون مقدار رو پیدا کنیم؛چون قدرت پردازش در کامپیوتر ها روز افزون زیاد میشه ، زمان Brute Force به مراتب کاهش پیدا کرده و خیلی سریع شده ، و این Trap Door ها سریع تر حل میشن ! پس آمدن گفتن ما باید بریم سراغ اعداد بزرگتر !!

از دهه 70 میلادی تا اواخر سال 2000 ، رقمی که برای کلید RSA پیشنهاد شد 2048 بود و چون قدرت کامپیوتر ها از اون موقع خیلی بیشتر شده ، پس باید روی کلید بیشتر از 2048 حساب کنیم که نیاز به پردازش سنگینی برای محسبات رمزنگاری و همچنین شکستنش داره !

مشکلی که هست اینه که اگر ما بخوایم یک فایل رو الگریتم RSA یا DH رو با کلید 4096 بیتی یا 7680 بیتی توی یک گوشی موبایل رمز کنیم ، خیلی فرایند فرسایشی و کندی میشه ! حالا فکر کنید ما IOT هم داریم و قراره حتی تستر و یخچالمون هم به اینترنت وصل شه ، پس قراره اون هم بیاد و این محاسباتو انجام بده ، پردازشگر های OT یا همون Embedded Device ها هم جون خاصی که ندارن ! پس به مشکل میخوریم !

مشکلی که الگریتم های منحنی بیضوی حل کردن اینه که با سایز کلید های کوچک ولی الگریتم های ریاضی متفاوت ، همون امنیت رو برامون فراهم کردن !

تو عکس 1 میبینید که کلید 2048 بیت ما که الان امن فرض میشه در معماری RSA ، اگر بریم رو ECC ما نیاز به کلید 224 بیتی داریم ، یعنی 10 برابر کوچیکتر ! یعنی 10 برابر سرعت پردازش بیشتر !

اگر دقت کنید توی RSA -DH طول کلید ها از هر مرحله به مرحله بعدی دوبرابر میشه ولی توی ECC ما سه چهار مرحله بعد طول کلید هامون دوبرابر میشه

این سایتو باز کنید چون باهاش کار داریم

ما اصلا اینجا سراغ حل کردن منحنی ها نمیریم و باهاشون کاری نداریم ، صرفا میخوایم از دید رمزنگاری بگیم که بحث چی هست :

ما یه چیزی داریم تحت عنوان محور y ها که عمودیه و نارنجی و یه محور x ها که سبزه و افقیه ، ما طبق فرمولی که داریم میاییم و عدد گذاری میکنیم و طبق جواب های بدست امده نقطه میزاریم و نقاط رو بهم وصل میکنیم و این منحنی بیضوی قرمز حاصل میشه ، ما برای رسم هر منحنی نیاز به فرمول ریاضی داریم ، فرمول این منحنی اینه :

y^2=ax+b

که در اون ما y رو به توان دو رسوندیم و یه عدد a رو ضربدر x کردیم و بعلاوه عدد ثابت b کردیم ، در اینجا a=-1 و b= 1 در نظر گرفته شدن

y^2=-1x+1

حالا بریم سراغ یه پیچیده ترشون و چند تا نکته :

عکس 3 از فرمول زیر به دست امده :

y^2=x^3-ax+b
y^2=x^3-4x+9

وقتی که ترسیم میشه ، اگر ما موس روی روی نقاط ترسیمی ببریم میرسیم به دوتا مقدار ، سمت چپی مقدار x و سمت راستی مقدار y هست ، اگر این دوتارو توی معادله قرار بدیم ، معادله برابر میشه ، الان شما جای x یبار 0 بزارید و جای y بزارید 3، میبینید که اینطوری میشه :

y^2= 9 

9=(0^3)-(4×0)+9

و میبینید که 9=9 میشه، پس میبینید که 0 و 3 جواب درست برای فرمول بالا هستن، همچنین 2 و 3 ، خودتون یه بار تست کنید ! درواقع هر نقطه ای روی این منحنی همچین جواب درستی رو میده !

ویژگی های منحنی چیست ؟

1 - اگر بیاییم و از محور x نصف کنیم منحنی رو ، جفتشون باید موازی هم باشن ، به بیان دیگه اگر ما زیر یا بالای محور x یه چیزی بکشیم و اونو برگردونیم ، دقیقا شکل ما حاصل میشه :

اگر محور x رو یادتون باشه از عکس 2 توی عکس 4 ما نصف پایین منحنی رو فقط داریم و با برگردوندن اون روی محور بالایی ، شکل رو کامل کردیم !

2 - هر نقطه روی این منحنی قرمزه یه نقطه عددی هست که با x وy نظیرش نشونش میدیم، توی عکس 3 ما مثلا میگیم نقطه 2و3 ، یعنی نقطه ای که x اش 2 باشه و y اش 3 باشه

3 - ما روی هر نقطه ای که میبینیم میتونیم عملیات های خاصی انجام بدیم که اینجا سه تاشو معرفی میکنیم که این ها قراره Trap Door های الگریتم های ECC باشن ، این عملیات ها خیلی مهمن :

1. Inverse : (این مسئله برای محور X ها فقط صادقه)

ببینید ما اگر یه نقطه در نظر بگیریم ، مثلا نقطه P ، دقیقا در نظیرش در اونو محور ، ما یه نقطه داریم که معکوس و نظیر همین نقطس ، پس ما میگیم معکوس نقطه P میشه P-

و دقیقا معکوسشم صادقه که بگیم نقطه معکوس P- میشه P

2. Doubling :

دوبرابر کردن ویژگی دومه ، اگر ما بخوایم یه نقطه رو دوبرابر کنیم میاییم و یه خط غیر عمودی از اون میکشیم که یه جارو قطع کنه ، به این خط تو ریاضی میگن مماس ، زاویشم مهم نیست و من دوتا کشیدم و در دوجا الان -R داریم، شما میتونید توی 20 جای دیگه هم -R داشته باشید؛ الان خط مشکی که از P به R- کشیده شده خط مماس نام داره ، به این ویژگی میگن Doubling یا دوبرابر کردن؛ و ما اینطوری میگیم :

P+P= -R or 2P = R 

حالا ما اگر بیاییم این R- رو برعکس کنیم (روی محورX) ، همونطور که بلدید یه خط میکشیم مستقیم به اونور محور x ها و همونطور که میدونید میشه R ، حالا ما تو بحث منحنی به این میگیم P dot P = R یا عملیات "دات" کردن

3. Addition :

سومین ویژگی افزونگی هست :

افزونگی خیلی سادست ، ما در Doubling امدیم و عملیات "دات" رو روی P و P (یا خودش) انجام دادیم ، حالا فرض کنید ما دوتا نقطه انتخاب کردیم ، یکی P و دیگری Q ، حالا جفتشون رو بهم وصل میکنیم و ادامه میدیم ، مثلا در عکس سمت چپ نقطه از خط میگذره و اسمشو میزاریم R- ، حالا ما بلدیم که چطوری R- رو مثبت کنیم ، R- رو عملیات Inverse رو روش انجام میدیم و میرسیم به R ، حالا ما نقطه جدید داریم ، میاییم دوباره این عملیات رو اینبار با نقطه جدید انجام میدیم ، این بار P رو به R وصل میکنیم ، عکس وسطی ما این کارو کردیم و نقطه حاصل شد S- ، اون Inverse میکنیم و میرسیم به S ، اگر ادامه بدیم و P رو به S وصل کنیم میرسیم به F و برعکسش کنیم میرسیم به F- و همینطور تا بی نهایت

ما میگیم P dot Q = -R و همینطوری ادامه میدیم : P dot R = -S و...

به گیف زیر توجه کنید :

این گیف (عکس8) که از وبلاگ Cloud Flare اوردمش خیلی روون و راحت توضیح میده که چقد ما میتونیم ادامه بدیم این عملیات رو

اولش با Doubling شروع میشه و بقیش با Addition و Inverse ادامه پیدا میکنه و اینطوری میشه :

A dot B = C

A dot A = B

A dot B = C

A dot C = D

A dot D = E

...

A dot Y = Z

این عملیات 25 بار طور میکشه (اگر ما اندازه حروف الفبا ادامه بدیم) در نهایت به سه تا چیز میرسیم :

نقطه شروع مون که A بود ، نقطه پایان که Z بود و 25 بار عملیات مون ، حالا بریم سراغ اصل Trap door مون :

اگر به شما A رو بدن و بگن 25 بار عملیات "دات" رو انجام بده ، راحته که برسیم به Z ، آمـــــــا اگر بهتون A و Z رو بدن و بگن چند بار باید عملیات "دات" رو انجام داد برای اینکه از A به Z برسیم ، نمیتونید ! و اینه که سخته !

چه چیزی حالا اینو سخت و امنش کرد؟ مهاجم میتونه Brute Force بکنه و از A برسه به Z ، حالا هرچقدر که طول بکشه ، چه چیزی اینو غیر ممکن میکنه ؟

فرض کنید به ما گفتن از A برس به Z ، اگر ندونیم چند تا dot باید انجام بدیم ، باید دونه دونه بیاییم و dot رو انجام بدیم که برسیم به Z (تعدادش رو نمیدونم ولی توی این مثال 25 تا بود و خیلی عدد کوچیکیه)

ولی توی الگریتم های ECC این تعداد رو میدونن ، در الگریتم های ECC میان و از روش کوتاه شده یا Shortcut میرن ، وقتی میدونن قراره 25 بار این عملیات انجام بشه ، اول میان یه A dot A انجام میدن که میشه 2A ، حالا یه 2A dot A و وقتی جواب شد سه تا 3A dot 3A و همینطوری تا اعداد بزرگ بشن و برسیم به 25 تا (شما میتونید از همون اول 2A dot 2A انجام بدید یا هرچی دوست داشتید) و در نهایت سریع میرسن به جواب !

نکته اینجاست که اگر بگیم یک الگریتم ECC یک کلید نرمال 224 بیتی انتخاب کنه که مطابق تصویر میبینید ، چند صد سال طول میکشه که بخوایم دستی بیاییم عملیات dot رو دونه دونه انجام بدیم و برسیم به این عدد ، ولی خود ECC وقتی بخواد اینو انجام بده ، چون تعداد dot رو میدونی خیلی سریع میرسه به جواب.

نکات پایانی :

• الگریتم های DH و DSA هم ورژن منحنی بیضوی دارن : ECDSA و ECDH ، این دوتا اگر یادتون باشه Trap door شون یکی بود و مبتنی بر Discrete Logarithm Problem بود.
• اما برای RSA هم ما ورژن منحنی بیضوی داریم ولی امنیتش فرق آنچنانی نکرده و ارزش استفاده نداره ، بهش میگن ECRSA ولی استفاده ای نمیشه ازش !!

درک مبحث ECC و امنیتش راحت نیست و شاید اونچنان به دردتون نخوره؛ منم که اولش خوندم نفهمیدم و بعد دوسه بار خوندن و سوال پرسیدن فهمیدمش، اگر برای شما هم ابهام بود حتما بپرسید ، اگر میبینید زیاد به دردتون نمیخوره فقط ازش رد بشید ، توی سری پیشرفته یکم عمیق تر و همچنین عملی تر بررسیش میکنیم :)

در مقاله بعدی میریم سراغ پروتوکول های شبکه و امنیتشون و دوتا مفهوم مهم تو امنیت

سوال یا ابهام یا انتقادی بود در خدمتم، یاعلی ;)