خواندن ۷ دقیقه·۵ سال پیش

توضیح امضای دیجیتال به نوجوان باهوش خود - قسمت اول: کلید‌های خصوصی و عمومی

امضای دیجیتال

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

یک امضای دیجیتال از سه الگوریتم زیر پیروی می‌کند:

الف) (sk, pk) := generateKeys( keysize )

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

ب) (sig := sign( sk , message

ورودی این تابع پیام شما و نیز کلید خصوصی شما می باشد و خروجی آن امضای شما با استفاده از کلید خصوصی sk پای آن پیام می‌باشد.

ج) (isValid := verify( pk , message , sig

مرحله بعد مرحله تایبد کردن اعتبار امضا می‌باشد. این تابع یک پیام، امضای پای آن پیام، و یک کلید عمومی را به عنوان ورودی دریافت می‌کند و یک مقدار boolean به عنوان خروجی می‌دهد. چنان‌چه امضای پای یک سند تحت آن کلید عمومی یک امضای معتبر باشد (پیام توسط دارنده واقعی آن کلید عمومی امضا شده باشد) آنگاه خروجی تابع true خواهد بود و در غیر این صورت false خواهد بود.

این طرح امضای دیجیتال باید دو شرط زیر را برآورده کند:

اول آنکه verify ( pk , message , sign ( sk , message )) == true

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

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

نکته مهم دیگر آنکه دو تابع اول می‌توانند تصادفی باشند. در واقع تابع اول خیلی بهتر است که تصادفی باشد چون که باید برای افراد مختلف کلید‌های مختلف تولید کند. از طرف دیگر اما تابع سوم باید همیشه غیرتصادفی باشد.

در بخش اول این مقاله می‌خواهیم در مورد الگوریتم اول یعنی generatekeys صحبت کنیم. اینکه کلید های عمومی و خصوصی چگونه ساخته می شوند؟

یک روش برای تولید کلیدهای رمزنگاری استفاده از elliptic curves است. روش دیگر استفاده از RSA است که عملکرد آن حول اعداد اول می‌باشد. بیشتر رمز‌ارز‌ها نظیر بیتکوین و اتریوم از eleptic curves استفاده می‌کنند چون که کلید خصوصی 256bit elliptic curve به اندازه کلید خصوصی 3072bit RSA امن می‌باشد ولی کلید‌های کوچکتر را راحت‌تر می‌توان مدیریت کرد.

منحنی های elliptic curve چگونه می‌باشند؟

این محنی ها مجموعه نقاطی می‌باشند که از معادله زیر پیروی می‌کنند:

y² = x³+ax+b

و همزمان شرط 4a³+27b² ≠ 0 برقرار می‌باشد.

چند مثال از منحنی های elliptic curve را در ادامه می‌بینید:

همان طور که مشاهده می‌کنید یک ویژگی مهم منحنی های elliptic curve آن است که حول محور x قرینه هستند.

منحنی های elliptic curve که توسط بیتکوین، اتریوم و برخی رمز‌ارزهای دیگر استفاده می‌شود secp256k1 نام دارد. معادله منحنی secp256k1 برابر با y² = x³+7 است و به شکل زیر می‌باشد:

ساتوشی دلیل خاصی برای استفاده از منحنی secp256k1 نداشته و تنها از منحنی رایج در زمان خود استفاده کرد. (اینجا را مشاهده کنید)

جمع نقاط روی منحنی

شما می‌توانید دو نقطه بر روی منحنی elliptic curve را جمع کنید و به نقطه دیگری بر روی همان منحنی برسید. برای جمع کردن دو نقطه بر روی منحنی باید ابتدا خطی را ترسیم کنید که از این دو نقطه می‌گذرد. سپس مشخص کنید که این خط در کجا منحنی را قطع می‌کند تا به نقطه سوم برسید. در قدم بعد قرینه نقطه سوم حول محور x را پیدا کنید تا به نقطه چهارم برسید. نقطه چهارم همان جمع نقطه اول و دوم می‌باشد.

بگذارید برای روشن شدن جمع دو نقطه یک مثال بزنم. فرض کنید می‌خواهیم نقطه P و Q را بر روی منحنی زیر جمع کنیم:

در قدم اول خط واصل این دو نقطه را رسم می‌کنیم:

سپس نقطه سوم که محل تقاطع خط و منحنی است را پیدا می‌کنیم:

سپس آن را حول محور x تصویر می‌کنیم:

نقطه R جمع دو نقطه P و Q است.

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

برای مثال فرض کنید نقطه شروع P است:

حال می‌خواهیم P را با خودش جمع کنیم. قدم اول آن است که خطی را ترسیم کنیم که از P و P بگذرد. بی‌نهایت خط وجود دارد که این شرط را برآورده می‌کنند اما ما از خط مماس استفاده می‌کنیم:

سپس محل تقاطع خط و منحنی و بعد قرینه آن حول محور x را پیدا می‌کنیم:

بنابراین در پایان این مراحل ما P را با خودش جمع کردیم و به 2•P رسیدیم.

اگر بار دیگر P را با نقطه بدست آمده در مرحله قبل جمع کنید آنگاه در واقع P را با خودش و سپس با خودش جمع کردیم. در نتیجه برای محاسبه 3•P تنها لازم است دو نقطه P و 2•P را جمع کنیم.

به همین ترتیب می‌توان ضرایب بالاتر P را بر روی منحنی بدست آورد.

نقطه آغازی، P، که توسط secp256k10 استفاده می‌شود دارای مختصات زیر است:

مختصات x:

55066263022277343669578718895168534326250603453777594175500187360389116729240

مختصات y:

32670510020758816978083085130507043184471273380659243275938904335757337482424

تعداد محاسبات لازم برای جمع نقاط

به چند مرحله محاسباتی برای محاسبه 10•P نیاز داریم؟ ساده ترین جواب آن است که به ۹ بار محاسبه نیاز داریم چون که P•10 برابر است با

P+P+P+P+P+P+P+P+P+P

که مستلزم ۹ بار محاسبه جمع بین نقاط است.

اما می‌توان نشان داد که 10•P را می‌توان تنها در ۴ مرحله محاسبه کرد:

P+P = 2•P

2•P+2•P = 4•P

4•P+4•P = 8•P

2•P+8•P=10•P

حال فرض کنید که یک عدد تصادفی ۲۵۶ بیتی داریم که با x نشانش می‌دهیم. در مثال ما x می‌تواند بین 0 تا 1.1579209e+77 نوسان کند. سوال آن است که به چند مرحله برای محاسبه x•P نیاز داریم؟

با همان استدلال چند سطر پیش می‌توان نشان داد که محاسبه x•P حداکثر به ۵۱۰ مرحله محاسباتی جمع نیاز دارد.

خسته‌مون کردی، پس کی فرایند تولید کلید عمومی و خصوصی را میگی؟

در حقیقت تمام آنچه تا کنون خواندید فرایند تولید کلید خصوصی و عمومی است. وقتی که x•P را محاسبه می‌کنیم x یک عدد صحیح تصادفی ۲۵۶ بیتی است و حاصل محاسبه x•P بک نقطه بر روی منحنی است که آن را X می‌نامیم.

اگر شما x را داشته باشید حداکثر در ۵۱۰ مرحله می‌توانید x•P یا X را محاسبه کنید. اما اگر X را داشته باشید آیا می‌توانید x را محاسبه کنید؟ به عبارت دیگر آیا می‌توانید مشخص کنید که چند بار نقطه P با خود جمع شده‌است تا به نقطه X بر روی منحنی برسیم؟

جواب آن است که به لحاظ توان محاسباتی ناممکن است که x را پیدا کنید حتی اگر به قوی‌ترین کامپیوتر دسترسی داشته باشید. هیچ الگوریتم مشخصی برای تعیین x وجود ندارد و تنها راه موجود آن است که آنقدر P را با خودش جمع کنیم تا به X برسیم. عدد x بین 0 تا 1-2²⁵⁶ است، بنابراین میانگین آن 2¹²⁸ است. در نتیجه بطور متوسط به 2¹²⁸ مرحله محاسبه جمع نقطه‌ای نیاز داریم تا x را پیدا کنیم. حتی اگر ابرکامپیوتر شما قادر به محاسبه یک تریلیون عملیات جمع نقطه‌ای در ثانیه باشد و ابرکامپیوتر شما از زمان آغاز پیدایش جهان مشغول محاسبه بوده باشد شما تنها 2⁹⁸ عملیات جمع نقطه‌ای تا به امروز انجام داده‌اید.

بنابراین چون کسی نمی‌تواند با فرض در اختیار داشتن X مقدار x را در معادله X=x•P پیدا کند بسیار مطلوب است که x کلید خصوصی و X کلید عمومی باشد. در نتیجه کلید خصوصی شما یک عدد صحیح تصادفی ۲۵۶ بیتی و کلید عمومی شما مختصات طول (۲۵۶ بیت) و عرض (۲۵۶ بیت) یک نقطه بر روی منحنی elliptic curve خواهد بود. با انتخاب این کلید ها ویژگی مهم زیر نیز برقرار خواهد بود:

به لحاظ توان محاسباتی ناممکن است که کلید خصوصی متناظر با یک کلید عمومی را پیدا کرد.

ضمیمه: بهبود توابع elliptic curves متناسب با نیاز رمزنگاری

یک مشکل با مدل فعلی آن است که ممکن است نتیجه محاسبه x•P مقدار بسیار بزرگی شود به طوری که مختصات محور x و y آن را نتوان در قالب کلید عمومی استاندارد ۵۱۲ بیتی ذخیره کرد. راه حل آن می‌باشد که elliptic curve مان را بر روی یک میدان محدود تعریف کنیم بنابراین برای مختصات نقاط حد تعریف می‌کنیم.

مشکل دیگر آن است که ما تنها به نقاطی علاقه‌مند هستیم که مختصات آن اعداد صحیح می‌باشند. بنابر این منحنی مورد نظر ما گسسته خواهد بود.

برای رفع این مشکلات ما معادله

y² = x³+ax+b

را به

y² mod p = (x³ + ax + b) mod p

تغییر می‌دهیم. در این معادله p یک عدد اول می‌باشد. در مدل secp256k1 عدد p بزرگترین عدد اولی است که از 2²⁵⁶ کوچکتر است.

حال شکل منحنی elliptic curve اینگونه خواهد بود: