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

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 صدا زده می‌شد، در حدود سال ۱۹۹۶ توسط سه دانشمند ریاضی (ج. هافستین، ج. پیفر، ج. سیلورمن) ساخته شد. در سال ۱۹۹۶ این ریاضیدانان در کنار هم و با کمک د. لیمن توانستند الگوریتم رمزگذاری NTRU را بدست آورند و حق امتیاز ثبت اختراع را در سیستم رمزنگاری بدست آورند. در ابتدا سیستم رمزنگاری، در مواقعی پیام کد شده را، حتی با وجود این که پیام به‌طور صحیح و کامل رمزگذاری شده بود، به‌طور ناقص به پیام اصلی تبدیل می‌کرد و در مواردی به‌طور کل ناتوان بود و به هیچ وجه پیام اصلی به وجود نمی‌آمد؛ بنابراین سازندگان این روش تصمیم گرفتند که از این الگوریتم برای رمزنگاری کلیدهای عمومی استفاده کنند و قسمت امنیت این سیستم را بر اساس این فرضیه که این الگوریتم برای رمزنگاری کلیدهای عمومی ساخته شده، بنا کردند. در ده سال گذشته افراد زیادی برای ارتقای سیستم رمزنگاری تلاش کردند تا زمانی که در اولین کنفرانس رسمی در مورد رمزنگاری تغییراتی برای افزایش کیفیت عملکرد خود سیستم و قسمت امنیت آن ایجاد شد. بیشتر تغییرات ایجاد شده در قسمت عملکرد، بیشتر بر روی افزایش سرعت رمزنگاری بود تا حل کردن مشکل رمزگشایی این سیستم. تا اینکه در سال ۲۰۰۵ مطبوعات توانستند مشکل این الگوریتم را در در رمزگشایی کشف و بیان کنند. به دلایل امنیتی، از زمان ارائه اولین ورژن این الگوریتم رمزنگاری، پارامترهای جدیدی تعیین شد که به نظر می‌رسید در برابر همه حملاتی که امروزه ما با آن‌ها آشنا هستیم مقاوم و امن هستند و باعث افزایش قدرت محاسبات نیز می‌شوند؛ ولی اکنون این سیستم به‌طور کامل توسط استانداردهای IEEE P1363 که برای رمزنگاری کلمات عمومی بر پایه شبکه به وجود آمده بود تأیید شده‌است. به دلیل سرعت بالای این روش در رمزنگاری کلیدهای عمومی و استفاده حافظه کمتر، می‌توان آن را در دستگاه‌های همراه و کارت‌های هوشمند به کار برد. در آوریل ۲۰۱۱، NTRUEncrypt به عنوان استاندارد X9.98 پذیرفته شد به گونه‌ای که اکنون می‌توان از آن در صنعت خدمات مالی مانند بانک‌ها استفاده کرد.

ساخت کلید عمومی

ارسال یک پیام مخفی از آلیس به باب نیازمند ساخت یک کلید عمومی و یک کلید خصوصی است. کلید عمومی هم توسط آلیس و هم توسط باب و کلید خصوصی تنها توسط باب قابل شناسایی است. برای تولید جفت کلید دو چندجمله‌ای f و g، با ضرایب بسیار کوچکتر از q، با درجه حداکثر $\ N-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 = ۱۱، p = ۳ و q = ۳۲ را دارند و هم چنین چندجمله‌ای‌های f و g دارای حداکثر درجه ۱۰ می‌باشند. پارامترهای (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 با ضرایب {۱٬۰٬۱-} قرار می‌دهد. در برنامه‌های پیشرفته رمزگذاری، پیام چندجمله‌ای می‌تواند به مبنای دو یا به مبنای سه ترجمه و ارائه شود. بعد از ساخت پیام چندجمله‌ای، آلیس به‌طور تصادفی یک چندجمله‌ای r که دارای ضرایب کوچک هستند را انتخاب می‌کند (که محدود به مجموعه {۱٬۰٬۱-} نیستند)، که این کار به این معنی است که او می‌خواهد پیام خود را مخفی کند. با کمک کلید عمومی 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}}

به جای انتخاب ضرایب بین بازه ۰ و 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-] به جای بازه ۰ تا 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}

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

منابع

NTRU: سیستم رمزنگاری کلید عمومی بر اساس حلقه. در نظریه اعداد الگوریتمی
بهینه‌سازی NTRU کلید عمومی رمزنویسی و تئوری اعداد محاسبه پذیر
پیاده‌سازی بهینه ی NTRU برای امنیت فراگیر.