رمزنگاری ان‌تی‌آریو

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو


NTRU Encrypt یک سیستم رمزگذاری کلمات عمومی، که بیشتر به عنوان الگوریتم رمزنگاری NTRU شناخته می شود، بر پایه شبکه های رمزنگاری نامتقارن که مرتبط با RSA و ECC است که برای حل مشکل بردارهای کوچک در سیستم های شبکه ای ارائه شده است. (مشکل مورد نظر این است که رمزهایی ساخته شود تا بوسیله رایانه های کوانتومی شکسته نشود) عملیات این الگوریتم بر اساس عوامل ضرب چند جمله ای های  \ R=Z[X]/(X^N-1) همراه با ضرب پیچیده به گونه ای که همه چند جمله ای های موجود در حلقه با ضرایب صحیح و توان حداکثر N-1 باشند.

  \textbf{a} = a_0 + a_1 X + a_2 X^2 + \cdots + a_{N-2} X^{N-2} + a_{N-1} X^{N-1}

NTRU در واقع از خانواده Parameterised سیستم های رمزنگاری می باشد به گونه ای که هر سیستم توسط سه پارامتر صحیح (N,p،q) مشخص شده، که به ترتیب نشان دهنده بیشترین درجه  \ N-1 برای همه چند جمله ای ها در حلقه R و کمترین و بیشترین پیمانه است، با این شرایط که همواره N عدد اول، q بزرگتر از p و q و p نسبت به هم اول هستند.همچنین برای قرار دادن چند جمله ای های  \ \mathcal{L}_f, \mathcal{L}_g, \mathcal{L}_m و  \ \mathcal{L}_r ( چند جمله ای که قسمتی از کلید خصوصی است، چند جمله ای برای ساختن یک کلید عمومی، پیام و مقدار مخفی شده، چند جمله ای متناظر) درجه همه آنها باید حداکثر  \ N-1 باشد. این عمل، بستگی به انتخاب درجه سختی فاکتور گیری از چند جمله ای های خاص موجود در حلقه و تبدیل آن به دو چند جمله ای با ضرایب بسیار کوچک دارد.شکستن رمز به مقدار زیادی با مشکلات موجود در کاهش شبکه (به منظور حل مشکلات برداری کوچک) ارتباط مستقیم دارد.دقت در انتخاب پارامترهای مناسب برای خنثی کردن حملات بسیار مهم و ضروری می باشد. از آنجایی که هم قسمت رمزگذاری و هم قسمت رمزگشایی از ساده ترین ضرب چند جمله ای ها استفاده می کند، بنابراین این عملیات در مقایسه با دیگر سیستم های رمزگذاری نامتقارن، مانند RSA، ElGamal و Elliptic curve cryptography بسیار سریع تر عمل می کند. با این وجود هنوز این سیستم رمزگذاری توسط معیارهای دقیق رمزنگاری رتبه دهی نشده است.

تاریخچه[ویرایش]

سیستم رمزنگاری کلیدهای عمومی مربوط به سیستم رمزنگاری جدید می باشد. اولین ورژن از این سیستم، که به طور اختصار NTRU صدا زده می شد، در حدود سال 1996 توسط سه دانشمند ریاضی (ج.هافستین، ج.پیفر، ج.سیلورمن) ساخته شد. در سال 1996 این ریاضیدانان در کنار هم و با کمک د.لیمن توانستند الگوریتم رمزگذاری NTRU را بدست آورند و حق امتیاز ثبت اختراع را در سیستم رمزنگاری بدست آورند. در ابتدا سیستم رمزنگاری، در مواقعی پیام کد شده را، حتی با وجود این که پیام به طور صحیح و کامل رمزگذاری شده بود، به طور ناقص به پیام اصلی تبدیل می کرد و در مواردی به طور کل ناتوان بود و به هیچ وجه پیام اصلی بوجود نمی آمد. بنابرایم سازندگان این روش تصمیم گرفتند که از این الگوریتم برای رمزنگاری کلیدهای عمومی استفاده کنند و قسمت امنیت این سیستم را بر اساس این فرضیه که این الگوریتم برای رمزنگاری کلیدهای عمومی ساخته شده، بنا کردند. در ده سال گذشته افراد زیادی برای ارتقای سیستم رمزنگاری تلاش کردند تا زمانی که در اولین کنفرانس رسمی در مورد رمزنگاری تغییراتی برای افزایش کیفیت عملکرد خود سیستم و قسمت امنیت آن ایجاد شد. بیشتر تغییرات ایجاد شده در قسمت عملکرد، بیشتر بر روی افزایش سرعت رمزنگاری بود تا حل کردن مشکل رمزگشایی این سیستم. تا اینکه در سال 2005 مطبوعات توانستند مشکل این الگوریتم را در در رمزگشایی کشف و بیان کنند. به دلایل امنیتی، از زمان ارائه اولین ورژن این الگوریتم رمزنگاری، پارامترهای جدیدی تعیین شد که به نظر می رسید در برابر همه حملاتی که امروزه ما با آنها آشنا هستیم مقاوم و امن هستند و باعث افزایش قدرت محاسبات نیز می شوند. ولی اکنون این سیستم به طور کامل توسط استانداردهای IEEE P1363 که برای رمزنگاری کلمات عمومی بر پایه شبکه بوجود آمده بود تایید شده است. به دلیل سرعت بالای این روش در رمزنگاری کلیدهای عمومی و استفاده حافظه کمتر، می توان آن را در دستگاه های همراه و کارت های هوشمند به کار برد. در آوریل 2011، NTRUEncrypt به عنوان استاندارد X9.98 پذیرفته شد به گونه ای که اکنون می توان از آن در صنعت خدمات مالی مانند بانک ها استفاده کرد.

ساخت کلید عمومی[ویرایش]

ارسال یک پیام مخفی از آلیس به باب نیازمند ساخت یک کلید عمومی و یک کلید خصوصی است.کلید عمومی هم توسط آلیس و هم توسط باب و کلید خصوصی تنها توسط باب قابل شناسایی است. برای تولید جفت کلید دو چند جمله ای f و g، با ضرایب بسیار کوچکتر از q، با درجه حداکثر  \ N-1 و با ضرایب {1.0.1-} مورد نیاز است. آنها را می توان به عنوان باقی‌مانده همه کلاس های چند جمله ای ها به پیمانه  \ X^N-1 در R در نظر گرفت. چند جمله ای f باید نیاز دیگری مبنی بر جا به جا کردن پیمانه q و p (با استفاده از الگوریتم اقلیدسی) را برآورده کند که بدین معناست  \ \textbf{f} \cdot \textbf{f}_p = 1 \pmod p و  \ \textbf{f} \cdot \textbf{f}_q = 1 \pmod q باید ذخیره شوند. بنابراین وقتی f انتخاب شده قابل جا به جایی نباشد، باب باید از اول f دیگری را بدست آورد. هم f و هم  \ \mathbf{f}_p کلیدهای خصوصی باب هستند و کلید عمومی h هم محاسبات کمی را بوجود خواهد آورد.

 \textbf{h} = \textbf{f}_q \cdot \textbf{g} \pmod q.

مثال : در این مثال پارامترهای (N ، P، Q) مقادیر N = 11 ، p = 3 و q = 32 را دارند و هم چنین چند جمله ای های f و g دارای حداکثر درجه 10 می باشند. پارامترهای (N، P ، Q) برای همه آشنا هستند. چندجمله ای ها، همگی به طور تصادفی انتخاب شده است، بنابراین تصور می رود که آنها به صورت زیر نشان داده شوند:

 \textbf{f} = -1 + X + X^2 - X^4 + X^6 +X^9 - X^{10}
 \textbf{g} = -1 + X^2 +X^3 + X^5 -X^8 - X^{10}

با استفاده از الگوریتم اقلیدسی معکوس F به پیمانه p و پیمانه q، به ترتیب برابر است با :

 \textbf{f}_p = 1 + 2X + 2X^3 +2X^4 + X^5 +2X^7 + X^8+2X^9 \pmod 3
 \textbf{f}_q = 5 + 9X +6X^2+16X^3 + 4X^4 +15X^5 +16X^6+22X^7+20X^8+18X^9+30X^{10} \pmod {32}

که ایجاد کلید عمومی h (شناخته شده هم برای آلیس و هم برای باب) به این صورت محاسبه می شود:

 \textbf{h} = \textbf{f}_q \cdot \textbf{g} \pmod {32} = 8 + 25X +22X^2+20X^3 + 12X^4 +24X^5 +15X^6+19X^7+12X^8+19X^9+16X^{10} \pmod {32}

رمزگذاری[ویرایش]

آلیس، کسی که می خواهد یک پیام مخفی به باب ارسال کند، پیام خود را در یک چند جمله ای m با ضرایب {1،0،1-} قرار می دهد. در برنامه های پیشرفته رمزگذاری، پیام چند جمله ای می تواند به مبنای دو یا به مبنای سه ترجمه و ارائه شود. بعد از ساخت پیام چند جمله ای، آلیس به طور تصادفی یک چند جمله ای r که دارای ضرایب کوچک هستند را انتخاب می کند (که محدود به مجموعه {1،0،1-} نیستند)، که این کار به این معنی است که او می خواهد پیام خود را مخفی کند. با کمک کلید عمومی h که توسط باب ساخته شده است پیام e به این صورت محاسبه می شود:

 \textbf{e} =  p \textbf{r} \cdot \textbf{h} + \textbf{m} \pmod q

این متن سازنده رمز پیام آلیس را مخفی و به صورت کاملاً امن به باب ارسال میکند.

مثال : فرض کنید که آلیس می خواهد پیامی را ارسال کند که می توان آن را به صورت چند جمله ای زیر نوشت:

 \textbf{m} = -1 + X^3 - X^4-X^8+X^9+X^{10}

و چند جمله ای تصادفی انتخاب شده که دارای مقدار نامعلومی است نیز به این صورت است:

 \textbf{r} = -1+X^2+X^3+X^4-X^5-X^7

متن رمزنگاری شده e که به باب پیام رمزی آلیس را نشان می دهد به صورت زیر خواهد بود:

 \textbf{e} = 3 \textbf{r} \cdot \textbf{h} + \textbf{m} \pmod {32} = 14 + 11X+26X^2+24X^3+14X^4+16X^5+30X^6+7X^7+25X^8+6X^9+19X^{10} \pmod {32}

رمزگشایی[ویرایش]

هر کسی با دانستن R می تواند پیام m را پردازش و بدست آورد. بنابراین R نباید توسط آلیس فاش شود. همچنین علاوه بر اطلاعات قابل دسترس برای عموم، باب کلمه خصوصی ساخته شده توسط خودش را نیز می داند. اینجاست که باب می تواند m را بدست آورد. برای اینکار اول او پیام رمزی را در قسمتی از کلمه خصوصی f خود ضرب می کند.

 \textbf{a} = \textbf{f} \cdot \textbf{e} \pmod q

با بازنویسی چندجمله ای ها، این معادله نشان دهنده محاسبات زیر خواهد بود :

 \textbf{a} = \textbf{f} \cdot \textbf{e} \pmod q
 \textbf{a} = \textbf{f} \cdot (\textbf{r} \cdot p\textbf{h}+\textbf{m}) \pmod q
 \textbf{a} = \textbf{f} \cdot (\textbf{r} \cdot p\textbf{f}_q \cdot \textbf{g} + \textbf{m}) \pmod q
 \textbf{a} = p\textbf{r} \cdot \textbf{g} + \textbf{f} \cdot \textbf{m} \pmod q

به جای انتخاب ضرایب بین بازه 0 و 1-q آنها را در بازه [q/2, q/2-] انتخاب می کنیم تا از احتمال اینکه پیام اصلی به طور ناقص بازگردانی شود جلوگیری کنیم. زیرا ممکن است آلیس مقادیر m خود را در بازه [p/2,+p/2-] انتخاب کند. این حاکی از آن است که تمام ضرایب  \ p\textbf{r} \cdot \textbf{g} + \textbf{f} \cdot \textbf{m} در حال حاضر در داخل بازه [q/2,+q/2-] قرار دارد زیرا چندجمله ای های R ، G، F و M و عدد اول P همه ضرایب کوچکی در مقایسه با q هستند. این بدین معنی است که تمام ضرایب در حین کاهش پیمانه q ثابت مانده و پیام اصلی ممکن است به درستی بازگردانی شود. گام بعدی محاسبه a با پیمانه p است:

 \textbf{b} = \textbf{a} \pmod p = \textbf{f} \cdot \textbf{m} \pmod p

زیرا

 \ p\textbf{r} \cdot \textbf{g} \pmod p =0 .

با دانستن b توسط باب می توان بخش دیگری از کلید خصوصی او را  \ \left(\textbf{f}_p \right) برای بازگردانی پیام آلیس با ضرب کردن b و  \ \textbf{f}_p استفاده کرد.

 \textbf{c} = \textbf{f}_p \cdot \textbf{b} = \textbf{f}_p \cdot \textbf{f} \cdot \textbf{m} \pmod p
 \textbf{c} = \textbf{m} \pmod p

زیرا

 \ \textbf{f} \cdot \textbf{f}_p =1 \pmod p نیازمند است به  \ \textbf{f}_p

مثال : پیام رمزنگاری شده e از آلیس به باب در چند جمله ای f ضرب خواهد شد.

  \textbf{a} = \textbf{f} \cdot \textbf{e} \pmod {32} = 3 -7X-10X^2-11X^3+10X^4+7X^5+6X^6+7X^7+5X^8-9X^9-7X^{10} \pmod {32},

اینجاست که باب با استفاده از بازه [q/2,+q/2-] به جای بازه 0 تا 1-q برای ضرایب چند جمله ای a، از احتمال اینکه پیام به طور کامل بازگردانی نشود جلوگیری می کند. کاهش ضرایب a در پیمانه p نتیجه زیر را در بر خواهد داشت:

 \textbf{b} = \textbf{a} \pmod 3 = -X-X^2+X^3+X^4+X^5+X^7-X^8-X^{10} \pmod 3

که برابر است با

 \ \textbf{b} = \textbf{f} \cdot \textbf{m}\pmod 3

در آخرین مرحله نتیجه با  \ \textbf{f}_p که از کلید خصوصی باب است ضرب می شود تا بتوان به پیام اصلی m رسید.

 \textbf{c} = \textbf{f}_p \cdot \textbf{b} = \textbf{f}_p \cdot \textbf{f} \cdot \textbf{m} \pmod 3 = \textbf{m} \pmod 3
 \textbf{c} = -1+X^3-X^4-X^8+X^9+X^{10}

که در واقع پیام اصلی است که آلیس به باب فرستاده است!

منابع[ویرایش]

پیوندها[ویرایش]