بررسی و بهبود الگوریتم‌های رمزنگاری كلید عمومی

بررسی و بهبود الگوریتم‌های رمزنگاری كلید عمومی

فهرست مطالب

عنوان صفحه

چكیده. 1

فصل اول(کلیات پژوهش). 2

1-1 مقدمه. 3

1-2 تعاریف و مقدمات جبر خطی.. 6

1-3 مشبكه‌ها، تعاریف و مشخصات اصلی.. 9

1-4 بردارهای كوتاه در مشبكه‌ها 13

1-4-1 مسئله‌ی كوتاه‌ترین و نزدیك‌ترین بردار 13

1-5 سیستم‌های رمزنگاری مبتنی بر مسائل دشوار مشبكه‌ها 15

1-6 سیستم رمزنگاری كلید عمومی GGH… 18

1-7 حلقه‌های چندجمله‌ای كوتاه‌شده 19

1-8 سیستم رمزنگاری كلید عمومی NTRU… 22

1-8-1 سیستم رمزنگار NTRU… 22

1-8-2 مسائل ریاضی بنیادی NTRU… 27

1-9 NTRU به منزله‌ی یك سیستم رمزنگار مشبكه‌ای.. 29

1-9-1 مشبكه‌ی NTRU… 29

1-9-2 ارزیابی امنیت مشبكه‌ی NTRU… 31

فصل دوم(مروری بر پژوهش‌های مشابه). 32

2-1 سیستم رمزنگاری CTRU… 33

2-1-1 نمادها 33

2-1-2 تولید كلید. 34

2-1-3 رمزنگاری و رمزگشایی.. 34

2-1-4 تحلیل امنیت CTRU توسط ابداع‌كنندگان آن.. 35

2-2 سیستم رمزنگاریMaTRU… 36

2-2-1 نمادها 36

2-2-2 تولید كلید. 37

2-2-3 رمزنگاری و رمزگشایی.. 38

2-2-4 تحلیل امنیت MaTRU… 39

2-3 پیاده سازی سخت افزاری NTRU… 39

2-3-1 ضرب كننده سخت افزاری و مقیاس پذیر NTRU… 40

2-3-2 عملیات پشتیبانی شده توسط ضرب‌كننده سخت‌افزاری و محدودیت‌های آن.. 42

2-4 شكسته‌شدن CTRU و معرفی NTRU با اعداد گاوسی.. 43

2-4-1 تحلیل امنیت CTRU و اثبات ناامنی آن.. 44

2-5 تحلیل امنیتی NTRU به همراه نتایج محاسباتی.. 46

2-5-1 نتایج محاسباتی زمان بازیابی كلید خصوصی NTRU… 46

2-6 مقایسه‌ی NTRU با دیگر سیستم‌های كلید عمومی.. 49

2-6-1 مقایسه‌ی طول كلید. 50

2-6-2 مقایسه‌ی كارآیی تولید كلید، رمزنگاری و رمزگشایی.. 51

فصل سوم(بهبود سیستم رمزنگاری NTRU)… 53

3-1 روش‌های نمایش چندجمله‌ای‌ها 55

3-1-1 روش نمایش با ضرایب… 55

3-1-2 روش نمایش نقطه- مقدار 55

3-2 ضرب سریع چندجمله‌ای‌ها با فرم نمایش با ضرایب با استفاده از FFT.. 57

3-2-1 ریشه‌های مختلط عدد یك… 58

3-2-2 تبدیل فوریه‌ی گسسته. 61

3-2-3 الگوریتم تبدیل فوریه‌ی سریع. 61

3-2-4 معكوس تبدیل فوریه‌ی گسسته. 65

3-3 اثبات درستی بكارگیری روش پیشنهادی UFFT در ضرب پیچشی NTRU… 67

3-4 بررسی امنیتی استفاده از FFT یا UFFT.. 70

3-5 نتایج پیاده‌سازی.. 72

نتیجه‌گیری و پیشنهادات… 79

3-6 جمع‌بندی مطالب… 80

3-7 پیشنهادات.. 81

3-7-1 محاسبه‌ی احتمال رمزگشایی‌های ناموفق.. 81

3-7-2 مطالعه و بهبود الگوریتم‌های كاهش مشبكه. 82

3-7-3 پیاده‌سازی سخت افزاری UFFT.. 82

فهرست شكل‌ها

عنوان صفحه

شکل ‏1-1 مشبكه‌ی L و ناحیه بنیادی ℱ.. 11

شکل1-2 انتقال‌های ℱ توسط بردارهای L، كه ℝ را بطور كامل می‌پوشاند. 12

شکل ‏2‑1 ضرب پیچشی دو چندجمله‌ای.. 41

شکل ‏2-2 لگاریتم مبنای 10 زمان‌های شكست به ازای N = 100…115 و خط رگرسیون.. 49

شکل ‏3‑1 نمایی گرافیكی از الگوی ضرب سریع چندجمله‌ای‌ها با استفاده از FFT.. 58

شکل ‏3-2 ریشه‌های هشتم مختلط عدد یك… 59

شکل ‏3-3 ضرب پیچشی چندجمله‌ای‌های NTRU با N = 251. 74

شکل ‏3-4 ضرب پیچشی چندجمله‌ای‌های NTRU با N = 347. 75

شکل ‏3-5 ضرب پیچشی چندجمله‌ای‌های NTRU با N = 503. 76

شکل ‏3-6 ضرب پیچشی چندجمله‌ای‌های NTRU با N = 839. 77

شکل ‏3-7 رشد زمان اجرای هر سه روش با افزایش N به ازای 5000 چندجمله‌ای.. 78

شکل الف‑1 بكارگیری ناحیه‌ی بنیادی داده شده برای حل CVP.. 84

شکل الف‑2 دو پایه‌ی متفاوت برای یك مشبكه. 85

شکل الف‑3 اگر پایه بد باشد الگوریتم Babai بخوبی كار نمی‌كند. 86

فهرست جداول

عنوان صفحه

جدول ‏2‑1 تعداد بلوك‌های لازم برای آشكارسازی كلید و زمان صرف شده پنج نمونه به ازای هر اندازه 48

جدول ‏2‑2 مجموعه پارامتر‌های NTRU… 50

جدول ‏2-3 اندازه كلید عمومی در ECC، RSA و NTRU… 50

جدول ‏2‑4 مقایسه‌ی كارایی NTRU و RSA… 51

جدول ‏2‑5 مقایسه‌ی كارایی NTRU و ECC.. 51

جدول 3-1 پارامترهای بكار رفته در ارزیابی ضرب چندجمله‌ای‌های NTRU… 73

جدول ‏3-2 زمان‌های حاصل از ضرب چندجمله‌ای‌ها با سه روش پیاده‌سازی شده (میلی‌ثانیه) 73