موضوع مقاله: رمزنگاری ان‌تی‌آریو | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # رمزنگاری ان‌تی‌آریو | مقدمه: (مشکل مورد نظر این است که رمزهایی ساخته شود تا به وسیلهٔ رایانه‌های کوانتومی شکسته نشود) عملیات این الگوریتم بر اساس عوامل ضرب چندجمله‌ای‌های همراه با ضرب پیچیده به گونه‌ای که همه چندجمله‌ای‌های موجود در حلقه با ضرایب صحیح و توان حداکثر N-1 باشند. | ## بخش 1: رمزنگاری ان‌تی‌آریو | همچنین برای قرار دادن چندجمله‌ای‌های و (چندجمله‌ای که قسمتی از کلید خصوصی است، چندجمله‌ای برای ساختن یک کلید عمومی، پیام و مقدار مخفی شده، چندجمله‌ای متناظر) درجه همه آن‌ها باید حداکثر باشد. این عمل، بستگی به انتخاب درجه سختی فاکتورگیری از چندجمله‌ای‌های خاص موجود در حلقه و تبدیل آن به دو چندجمله‌ای با ضرایب بسیار کوچک دارد. شکستن رمز به مقدار زیادی با مشکلات موجود در کاهش شبکه (به منظور حل مشکلات برداری کوچک) ارتباط مستقیم دارد. با این وجود هنوز این سیستم رمزگذاری توسط معیارهای دقیق رمزنگاری رتبه دهی نشده‌است. اولین ورژن از این سیستم، که به‌طور اختصار NTRU صدا زده می‌شد، در حدود سال ۱۹۹۶ توسط سه دانشمند ریاضی (ج. لیمن توانستند الگوریتم رمزگذاری NTRU را بدست آورند و حق امتیاز ثبت اختراع را در سیستم رمزنگاری بدست آورند. در ابتدا سیستم رمزنگاری، در مواقعی پیام کد شده را، حتی با وجود این که پیام به‌طور صحیح و کامل رمزگذاری شده بود، به‌طور ناقص به پیام اصلی تبدیل می‌کرد و در مواردی به‌طور کل ناتوان بود و به هیچ وجه پیام اصلی به وجود نمی‌آمد؛ بنابراین سازندگان این روش تصمیم گرفتند که از این الگوریتم برای رمزنگاری کلیدهای عمومی استفاده کنند و قسمت امنیت این سیستم را بر اساس این فرضیه که این الگوریتم برای رمزنگاری کلیدهای عمومی ساخته شده، بنا کردند. در ده سال گذشته افراد زیادی برای ارتقای سیستم رمزنگاری تلاش کردند تا زمانی که در اولین کنفرانس رسمی در مورد رمزنگاری تغییراتی برای افزایش کیفیت عملکرد خود سیستم و قسمت امنیت آن ایجاد شد. بیشتر تغییرات ایجاد شده در قسمت عملکرد، بیشتر بر روی افزایش سرعت رمزنگاری بود تا حل کردن مشکل رمزگشایی این سیستم. تا اینکه در سال ۲۰۰۵ مطبوعات توانستند مشکل این الگوریتم را در در رمزگشایی کشف و بیان کنند. به دلایل امنیتی، از زمان ارائه اولین ورژن این الگوریتم رمزنگاری، پارامترهای جدیدی تعیین شد که به نظر می‌رسید در برابر همه حملاتی که امروزه ما با آن‌ها آشنا هستیم مقاوم و امن هستند و باعث افزایش قدرت محاسبات نیز می‌شوند؛ ولی اکنون این سیستم به‌طور کامل توسط استانداردهای IEEE P1363 که برای رمزنگاری کلمات عمومی بر پایه شبکه به وجود آمده بود تأیید شده‌است. | ## بخش 2: رمزنگاری ان‌تی‌آریو | به دلیل سرعت بالای این روش در رمزنگاری کلیدهای عمومی و استفاده حافظه کمتر، می‌توان آن را در دستگاه‌های همراه و کارت‌های هوشمند به کار برد. ساخت کلید عمومی ارسال یک پیام مخفی از آلیس به باب نیازمند ساخت یک کلید عمومی و یک کلید خصوصی است. کلید عمومی هم توسط آلیس و هم توسط باب و کلید خصوصی تنها توسط باب قابل شناسایی است. برای تولید جفت کلید دو چندجمله‌ای f و g، با ضرایب بسیار کوچکتر از q، با درجه حداکثر و با ضرایب {۱٫۰٫۱-} مورد نیاز است. آن‌ها را می‌توان به عنوان باقی‌مانده همه کلاس‌های چندجمله‌ای‌ها به پیمانه در R در نظر گرفت. چندجمله‌ای f باید نیاز دیگری مبنی بر جابه‌جا کردن پیمانه q و p (با استفاده از الگوریتم اقلیدسی) را برآورده کند که بدین معناست و باید ذخیره شوند؛ بنابراین وقتی f انتخاب شده قابل جا به جایی نباشد، باب باید از اول f دیگری را بدست آورد. هم f و هم کلیدهای خصوصی باب هستند و کلید عمومی h هم محاسبات کمی را به وجود خواهد آورد. مثال: در این مثال پارامترهای (N , P، Q) مقادیر N = ۱۱، p = ۳ و q = ۳۲ را دارند و هم چنین چندجمله‌ای‌های f و g دارای حداکثر درجه ۱۰ می‌باشند. چندجمله‌ای‌ها، همگی به‌طور تصادفی انتخاب شده‌است، بنابراین تصور می‌رود که آن‌ها به صورت زیر نشان داده شوند: با استفاده از الگوریتم اقلیدسی معکوس F به پیمانه p و پیمانه q، به ترتیب برابر است با: که ایجاد کلید عمومی h (شناخته شده هم برای آلیس و هم برای باب) به این صورت محاسبه می‌شود: رمزگذاری آلیس، کسی که می‌خواهد یک پیام مخفی به باب ارسال کند، پیام خود را در یک چندجمله‌ای m با ضرایب {۱٬۰٬۱-} قرار می‌دهد. در برنامه‌های پیشرفته رمزگذاری، پیام چندجمله‌ای می‌تواند به مبنای دو یا به مبنای سه ترجمه و ارائه شود. بعد از ساخت پیام چندجمله‌ای، آلیس به‌طور تصادفی یک چندجمله‌ای r که دارای ضرایب کوچک هستند را انتخاب می‌کند (که محدود به مجموعه {۱٬۰٬۱-} نیستند)، که این کار به این معنی است که او می‌خواهد پیام خود را مخفی کند. | ## بخش 3: رمزنگاری ان‌تی‌آریو | با کمک کلید عمومی h که توسط باب ساخته شده‌است پیام e به این صورت محاسبه می‌شود: این متن سازنده رمز پیام آلیس را مخفی و به صورت کاملاً امن به باب ارسال می‌کند. مثال: فرض کنید که آلیس می‌خواهد پیامی را ارسال کند که می‌توان آن را به صورت چندجمله‌ای زیر نوشت: و چندجمله‌ای تصادفی انتخاب شده که دارای مقدار نامعلومی است نیز به این صورت است: متن رمزنگاری شده e که به باب پیام رمزی آلیس را نشان می‌دهد به صورت زیر خواهد بود: رمزگشایی هر کسی با دانستن R می‌تواند پیام m را پردازش و بدست آورد؛ بنابراین R نباید توسط آلیس فاش شود. همچنین علاوه بر اطلاعات قابل دسترس برای عموم، باب کلمه خصوصی ساخته شده توسط خودش را نیز می‌داند. با بازنویسی چندجمله ای‌ها، این معادله نشان دهنده محاسبات زیر خواهد بود: به جای انتخاب ضرایب بین بازه ۰ و 1-q آن‌ها را در بازه [q/2, q/2-] انتخاب می‌کنیم تا از احتمال اینکه پیام اصلی به‌طور ناقص بازگردانی شود جلوگیری کنیم؛ زیرا ممکن است آلیس مقادیر m خود را در بازه [p/2,+p/2-] انتخاب کند. این حاکی از آن است که تمام ضرایب در حال حاضر در داخل بازه [q/2,+q/2-] قرار دارد زیرا چندجمله ای‌های R , G، F و M و عدد اول P همه ضرایب کوچکی در مقایسه با q هستند. این بدین معنی است که تمام ضرایب در حین کاهش پیمانه q ثابت مانده و پیام اصلی ممکن است به درستی بازگردانی شود. با دانستن b توسط باب می‌توان بخش دیگری از کلید خصوصی او را برای بازگردانی پیام آلیس با ضرب کردن b و استفاده کرد. زیرا نیازمند است به مثال: پیام رمزنگاری شده e از آلیس به باب در چندجمله‌ای f ضرب خواهد شد. اینجاست که باب با استفاده از بازه [q/2,+q/2-] به جای بازه ۰ تا 1-q برای ضرایب چندجمله‌ای a، از احتمال اینکه پیام به‌طور کامل بازگردانی نشود جلوگیری می‌کند. کاهش ضرایب a در پیمانه p نتیجه زیر را در برخواهد داشت: که برابر است با در آخرین مرحله نتیجه با که از کلید خصوصی باب است ضرب می‌شود تا بتوان به پیام اصلی m رسید. | ## جمع‌بندی | در نظریه اعداد الگوریتمی بهینه‌سازی NTRU کلید عمومی رمزنویسی و تئوری اعداد محاسبه پذیر پیاده‌سازی بهینه ی NTRU برای امنیت فراگیر.