مسئله بزرگترین مقسومعلیه مشترک
Greatest Common Divisor (GCD) دو عدد صحیح، بزرگترین عدد صحیحی است که هر دو را بدون باقیمانده تقسیم میکند. محاسبه کارآمد GCD یک بلوک سازنده برای بسیاری الگوریتم، شامل سادهکردن کسرها و رمزنگاری RSA که بعداً در این مقاله بحث میشود، است.
الگوریتم اقلیدس
Euclidean Algorithm (الگوریتم اقلیدسی) باستانی، GCD را با یک بینش بازگشتی بهطور قابلتوجه ساده محاسبه میکند: GCD دو عدد تغییر نمیکند اگر عدد بزرگتر با باقیماندهاش هنگام تقسیم بر کوچکتر جایگزین شود.
EUCLID(a, b):
اگر b == 0:
a را برگردان
EUCLID(b, a mod b) را برگردانردیابی یک مثال سادگی ظریف این کاهش را نشان میدهد:
EUCLID(48, 18):
48 mod 18 = 12 → EUCLID(18, 12)
18 mod 12 = 6 → EUCLID(12, 6)
12 mod 6 = 0 → EUCLID(6, 0)
b == 0، 6 را برگردان
GCD(48, 18) = 6چرا الگوریتم بهسرعت پایان مییابد
یک قضیه کلاسیک بیان میکند الگوریتم اقلیدس در زمان O(log(min(a, b))) اجرا میشود — بهطور قابلتوجه سریع حتی برای اعداد بسیار بزرگ. این میتواند با نشاندادن اینکه پس از دو فراخوانی بازگشتی، آرگومان کوچکتر حداقل نصف میشود اثبات شود، که به یک ارتباط عمیقتر با اعداد فیبوناچی مرتبط است: ورودی بدترینحالت برای الگوریتم اقلیدس (نیازمند بیشترین گامها نسبت به اندازه ورودی) یک جفت از اعداد فیبوناچی پیاپی است.
الگوریتم اقلیدسی توسعهیافته
Extended Euclidean Algorithm (الگوریتم اقلیدسی توسعهیافته) نهتنها GCD، بلکه ضرایب صحیح x و y برآوردهکننده هویت بزوت را نیز محاسبه میکند: ax + by = gcd(a, b). این توسعه برای محاسبه Modular Multiplicative Inverses (معکوسهای ضربی پیمانهای)، یک بلوک سازنده حیاتی برای الگوریتم RSA که بعداً در این مقاله بحث میشود، ضروری است.
EXTENDED-EUCLID(a, b):
اگر b == 0:
(a, 1, 0) را برگردان
(d, x', y') = EXTENDED-EUCLID(b, a mod b)
(d, x, y) = (d, y', x' - ⌊a/b⌋ · y')
(d, x, y) را برگردانتوانرسانی پیمانهای سریع
بسیاری الگوریتمهای رمزنگاری نیازمند محاسبه aᵇ mod n هستند جایی که b ممکن است یک عدد عظیم، بهطور بالقوه صدها رقم طولانی باشد. محاسبه این به روش ساده — ضرب a در خودش b بار — برای چنین توانهای بزرگی بهطور فاجعهباری کند خواهد بود. تکنیک Repeated Squaring (مربعکردن تکراری) این را بهطور چشمگیری سریعتر حل میکند.
MODULAR-EXPONENTIATION(a, b, n):
result = 1
a = a mod n
تا زمانی که b > 0:
اگر b فرد باشد:
result = (result · a) mod n
b = b >> 1 // تقسیم صحیح بر 2
a = (a · a) mod n // a را برای بیت بعدی مربع کن
result را برگرداناین الگوریتم نمایش باینری توان را بهرهبرداری میکند، که پیشتر در این مجموعه درباره نمایش اعداد بحث شد: بهجای ضرب در a در مجموع b بار، یک مقدار در حال اجرا را یکبار بهازای هر بیت b مربع میکند، و آن مقدار مربعشده را فقط وقتی بیت متناظر تنظیمشده باشد در نتیجه ضرب میکند.
مثال: محاسبه 3^13 mod 7
13 در باینری 1101 است
result=1, a=3, b=13(1101): بیت=1, result=3, a=9mod7=2
b=6(110): بیت=0, a=4
b=3(11): بیت=1, result=3·4mod7=5, a=16mod7=2
b=1(1): بیت=1, result=5·2mod7=3, a=4
b=0: تمام
3^13 mod 7 = 3 (بررسی: 3^13 = 1594323, 1594323 mod 7 = 3 ✓)از آنجا که تعداد تکرارها برابر با تعداد بیتهای b است، این الگوریتم در O(log b) ضرب اجرا میشود، یک سرعتبخشی نمایی در مقایسه با b ضرب ساده — تفاوت بین محاسبه چیزی بهطور آنی در مقابل چیزی که برای اعداد به اندازه رمزنگاری، زمانی بیشتر از عمر جهان میگرفت.
RSA: رمزنگاری کلید-عمومی ساختهشده روی این عناصر پایه
RSA Cryptosystem (سیستم رمزنگاری RSA)، یکی از پراستفادهترین طرحهای رمزگذاری کلید-عمومی، مستقیماً روی الگوریتمهای نظریه اعداد پوششدادهشده در این مقاله، ترکیبشده با دشواری محاسباتی فاکتورگیری اعداد بزرگ، ساخته میشود.
تولید کلید
۱. دو عدد اول بزرگ و متمایز p و q را انتخاب کن
۲. n = p · q را محاسبه کن (پیمانه، عمومی میشود)
۳. φ(n) = (p-1)(q-1) را محاسبه کن (تابع توتینت اویلر)
۴. یک توان عمومی e، هماول با φ(n)، انتخاب کن
۵. توان خصوصی d، معکوس پیمانهای
e پیمانه φ(n)، را با استفاده از الگوریتم اقلیدسی
توسعهیافته که پیشتر در این مقاله پوشش داده شد محاسبه کن:
d · e ≡ 1 (mod φ(n))
کلید عمومی: (n, e)
کلید خصوصی: (n, d)رمزگذاری و رمزگشایی
برای رمزگذاری یک پیام m (بهعنوان یک عدد کمتر از n):
c = m^e mod n (با استفاده از توانرسانی پیمانهای سریع)
برای رمزگشایی متن رمزشده c:
m = c^d mod n (با استفاده از توانرسانی پیمانهای سریع)ریاضیاتی که تضمین میکند این طرح بهدرستی کار میکند به Euler's Theorem (قضیه اویلر)، تعمیمی از یک نتیجه کلاسیک نظریه اعداد، متکی است، که تضمین میکند بهتوانرساندن یک عدد به توان ed پیمانه n عدد اصلی را بازمیگرداند، چون ed ≡ 1 (mod φ(n)) طبق ساخت.
چرا RSA امن در نظر گرفته میشود
امنیت RSA بر فرضی استوار است که Integer Factorization (فاکتورگیری عدد صحیح) — یافتن p و q با داشتن فقط حاصلضربشان n — از نظر محاسباتی برای اعداد اول بهاندازه کافی بزرگ (معمولاً ۱۰۲۴ بیت یا بیشتر در عمل مدرن) غیرقابلاجرا است، با وجود اینکه خود n عمومی است. هیچ الگوریتم کلاسیک کارآمدی برای فاکتورگیری اعداد صحیح بزرگ شناختهشده نیست، و دشواری این مسئله (هرچند NP-complete اثباتنشده، برخلاف مسائلی که پیشتر در این مجموعه بحث شد) در برابر دههها تلاش برای راهحل کارآمد مقاومت کرده، که پایه امنیت عملی برای کل طرح را فراهم میکند.
بدون دانستن p و q بهطور جداگانه، یک مهاجم
نمیتواند φ(n) را محاسبه کند، و بنابراین نمیتواند
کلید خصوصی d را محاسبه کند، حتی با دانش کامل
کلید عمومی (n, e)چرا این ترکیب الگوریتمهای ساده اینترنت را امن میکند
یک واقعیت قابلتوجه است که امنیت زیربنای بیشتر ارتباطات دیجیتال مدرن — اتصالات HTTPS، امضاهای دیجیتال، ایمیل امن — بر ترکیب تعداد کمی الگوریتم نظریه اعداد ظریف و قرنها-تا-دههها-قدیمی پوششدادهشده در این مقاله استوار است: الگوریتم باستانی GCD اقلیدس، نسخه توسعهیافته برای محاسبه معکوسهای پیمانهای، توانرسانی پیمانهای سریع برای محاسبه عملی با اعداد عظیم، و سختی فرضشده فاکتورگیری عدد صحیح. این یک جمعبندی مناسب برای مجموعهای است که الگوریتمها را در سراسر علوم کامپیوتر کاوش کرده: حتی یکی از تبعاتدارترین کاربردهای دنیای واقعی تفکر الگوریتمی از بلوکهای سازنده ریاضی بهطور شگفتآور ساده و بهخوبیدرکشده ساخته شده، هرکدام بهطور منفرد قابلتوضیح، که در چیزی بسیار قدرتمندتر از هر قطعه منفرد بهتنهایی ترکیب شدهاند.