حل مسائل کتاب Understanding Cryptography - فصل 6

برای سوالات با شماره فرد، به دفترچه حل رسمی مراجعه کنید. فصل های 5 و قبل، برای ویرایش قدیمی، توی این بلاگ حل شون گذاشته شده: Thomas Busby

فصل 6 - معرفی رمزنگاری کلید عمومی

• الگوریتم‌های کلید عمومی قابلیت‌هایی دارند که رمزهای متقارن فاقد آن هستند، به ویژه امضای دیجیتال و توابع برقراری کلید (Key Establishment Functions).

• الگوریتم‌های کلید عمومی از نظر محاسباتی فشرده (Computationally Intensive) هستند (که یک روش مؤدبانه برای گفتن این است که کند هستند) و از این رو برای رمزنگاری داده‌های حجیم (Bulk Data Encryption) مناسب نیستند.

• تنها سه خانواده از طرح‌های کلید عمومی امروزه به طور گسترده مورد استفاده قرار می‌گیرند. (این در تضاد با صدها الگوریتم متقارن موجود است.)

• اگر رایانه‌های کوانتومی در مقیاس بزرگ در آینده در دسترس قرار گیرند، سه طرح کلید عمومی تثبیت شده باید با الگوریتم‌های پسا کوانتومی (Post-Quantum Algorithms) جایگزین شوند.

• الگوریتم توسعه‌یافته اقلیدس (Extended Euclidean Algorithm) به ما امکان می‌دهد معکوس‌های پیمانه‌ای (Modular Inverses) را به سرعت محاسبه کنیم، که تقریباً برای تمام طرح‌های کلید عمومی مهم است.

• تابع فی اویلر (Euler’s Phi Function) تعداد عناصر کوچک‌تر از یک عدد صحیح n را که نسبت به n اول هستند، به ما می‌دهد. این یک تابع مهم برای طرح رمزنگاری RSA است.

فهرست مطالب

• سوال 6.2
• سوال 6.4
• سوال 6.6
• سوال 6.8
• سوال 6.10
• سوال 6.12
• سوال 6.14

سوال 6.2

سوال 6.4

1. پیچیدگی زمانی برای تولید امضای RSA (که شامل توان‌رسانی پیمانه‌ای با توان خصوصی است) معمولاً به صورت مکعبی نسبت به طول کلید k تقریب زده می‌شود. حالا با توجه به این موضوع:

2. $(\frac{15360}{1024}) ^ 3 = (15)^3 = 3375$

3. افزایش در زمان اجرا برای ECC معمولاً به صورت درجه دوم نسبت به طول کلید k تقریب زده می‌شود.

• از 160 به 256:

• از 160 به 512:

4. توصیفی از تفاوت بین RSA و ECC هنگام افزایش سطح امنیت

• RSA
  • پیچیدگی: زمان اجرا با توان مکعبی O(k3) نسبت به اندازه کلید k افزایش می‌یابد.
  • برابری امنیت: برای انتقال از امنیت ۸۰ بیت (۱۰۲۴ بیت) به امنیت ۱۲۸ بیت (۳۰۷۲ بیت) نیاز به سه برابر کردن اندازه کلید است که منجر به ۲۷ برابر کاهش عملکرد می‌شود.
• ECC
  • پیچیدگی: زمان اجرا با توان مربعی O(k2) نسبت به اندازه کلید k افزایش می‌یابد.
  • برابری امنیت: برای انتقال از امنیت ۸۰ بیت (۱۶۰ بیت) به امنیت ۱۲۸ بیت (۲۵۶ بیت) نیاز به افزایش ۱.۶ برابری در اندازه کلید است که تنها منجر به ۲.۵۶ برابر کاهش عملکرد می‌شود.

سوال 6.6

1. ۱۹۸ و ۲۴۳

2. ۱۸۱۹ و ۳۵۸۷

3. ۲۹۳۱ و ۵۴۵۱

gcd = 3, s = -1171, t = 2178

4. ۱۲۳۵۱ و ۴۲۳۴۳

سوال 6.8

محاسبه φ(m) برای m = 12, 15, 26:

m = 12: اعداد کوچک‌تر از ۱۲ که با آن اول هستند: ۱, ۵, ۷, ۱۱ φ(12) = 4

m = 15: اعداد کوچک‌تر از ۱۵ که با آن اول هستند: ۱, ۲, ۴, ۷, ۸, ۱۱, ۱۳, ۱۴ φ(15) = 8

m = 26: اعداد کوچک‌تر از ۲۶ که با آن اول هستند: ۱, ۳, ۵, ۷, ۹, ۱۱, ۱۵, ۱۷, ۱۹, ۲۱, ۲۳, ۲۵ φ(26) = 12

سوال 6.10

محاسبه معکوس a⁻¹ mod n:

a = 4, n = 7: از قضیه فرما: a^(n-1) ≡ 1 (mod n) 4⁶ ≡ 1 (mod 7) 4⁻¹ ≡ 4⁵ (mod 7) 4⁵ = 1024 = 146×7 + 2 4⁻¹ ≡ 2 (mod 7)

یا با الگوریتم اقلیدسی توسعه‌یافته: gcd(4,7) = 1, s = -1×7 + 2×4 = 1 4×2 ≡ 8 ≡ 1 (mod 7) معکوس = 2

a = 5, n = 12: gcd(5,12) = 1 از الگوریتم توسعه‌یافته: 5×5 = 25 = 2×12 + 1 5⁻¹ ≡ 5 (mod 12)

a = 6, n = 13: از قضیه فرما: 6⁻¹ ≡ 6¹¹ (mod 13) یا محاسبه مستقیم: 6×11 = 66 = 5×13 + 1 6⁻¹ ≡ 11 (mod 13)

سوال 6.12

اثبات a⁻¹ ≡ a¹¹ (mod 26):

قضیه اویلر می‌گوید: a^φ(n) ≡ 1 (mod n) وقتی gcd(a,n) = 1

φ(26) = φ(2×13) = φ(2)×φ(13) = 1×12 = 12

پس: a¹² ≡ 1 (mod 26)

بنابراین: a×a¹¹ ≡ a¹² ≡ 1 (mod 26)

در نتیجه: a⁻¹ ≡ a¹¹ (mod 26)

سوال 6.14

تست صافی (smoothness) برای اعداد مرکب:

۱. محاسبه P:

P برابر حاصل‌ضرب تمام توان‌های اول که شرایط را ارضا می‌کنند:

• اعداد اول ≤ 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
• توان‌ها ≤ 250

$P = 2^7 \times 3^5 \times 5^3 \times 7^2 \times 11^2 \times 13 \times 17 \times 19 \times 23 \times 29$

$P = 128 \times 243 \times 125 \times 49 \times 121 \times 13 \times 17 \times 19 \times 23 \times 29$

این عدد خیلی بزرگ است (حدود 10²⁰). برای محاسبات دقیق از نرم‌افزار مناسب استفاده کنید.

۲. محاسبه gcd(P, 29,716):

29716 = 2² × 11 × 677

gcd(P, 29716) = 2² × 11 = 44

۳. شرط smoothness:

N صاف است اگر gcd(P,N) = N

۴. آیا 29,716 صاف است؟

خیر، چون ۶۷۷ عدد اولی است که بزرگ‌تر از ۳۰ است.

۵. آیا 103,730 صاف است؟

103730 = 2 × 5 × 10373

۱۰۳۷۳ عدد اول است و > 30

عوامل اول بزرگ‌تر از B₁ = 30: 10373 توان‌های اول بزرگ‌تر از B₂ = 250: 10373¹

پس 103,730 صاف نیست.