הצגת המקור של הדף "NTRU"

'''NTRU'''{{הערה|[http://grouper.ieee.org/groups/1363/lattPK/submissions/ntru.pdf NTRU: A PUBLIC KEY CRYPTOSYSTEM]}} היא מערכת [[קריפטוגרפיה|הצפנת]] [[הצפנת מפתח ציבורי|מפתח ציבורי]] ו[[חתימה דיגיטלית]] מבוססת [[הצפנה מבוססת סריג|סריגים]] מוגנת ב[[פטנט]] ו[[קוד פתוח]] ברישיון [[GPL]], שהומצאה ב-1996 והוצעה כתקן חלופי למערכות הקיימות [[RSA]] ו-[[הצפנה מבוססת עקום אליפטי|ECC]]. נכללת ברשימת האלגוריתמים ה[[הצפנה פוסט-קוונטית|פוסט-קוונטיים]] וידועה כמערכת האסימטרית המהירה והיעילה ביותר נכון לשנת 2016. למרות היותו בתהליך תיקנון Std 1363.1 של [[IEEE]] וכן X9.98 של [[ASC]], בשל [[קריפטואנליזה]] שלו ביטחונו אינו ברור והוא מוטל בספק. קיימת גרסה אחת של Damien Stehlé ו־Ron Steinfeld שנמצאת בתהליך תקנון וניתנת להוכחה כבטוחה לפי המודל הסטנדרטי, היא פחות יעילה ומסתמכת על [[R-LWE]]{{הערה|[https://www.iacr.org/archive/eurocrypt2011/66320027/66320027.pdf Making NTRU as Secure as Worst-Case Problems over Ideal Lattices]}}.

==היסטוריה==
הגרסה הראשונה הומצאה ב-1996 על ידי Jeffrey Hoffstein ,Joseph Silverman ו־Jill Pipher. מאוחר יותר באותה שנה חברו המפתחים ל-Daniel Lieman ויסדו את חברת NTRU Cryptosystems שנרכשה ב-2009 על ידי Security Innovation{{הערה|[https://www.securityinnovation.com/products/ntru-crypto NTRU Post Quantum Cryptography]}}.

שם הצופן הוא קיצור של Nth Degree Truncated Polynomial Ring Units כלומר [[חוג הפולינומים]] ממעלה <math>N-1</math> או בסימון מתמטי: <math>R[x]/(x^N-1)</math>. השם מבוטא: "אֶנְטרוּ".

ב-2013 פותחה גרסה של NTRU{{הערה|[https://eprint.iacr.org/2013/004 Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices]}} המוכחת כבטוחה ואשר נחקרת על ידי קבוצות המחקר של [[IEEE]] ופרויקט PQCRYPTO כמועמדת "פוסט-קוונטית" להחלפת האלגוריתמים התיקניים הנמצאים בשימוש מסחרי. ב-2016 הציעו [[דניאל ברנשטיין]] וחוקרים נוספים את NTRU Prime{{הערה|[https://ntruprime.cr.yp.to/ntruprime-20160511.pdf NTRU Prime]}} שהוא שיפור של NTRU המתמקד ב[[חוג פולינומים]] של המערכת ואמור לספק עמידות נגד קריפטואנליזה שמנצלת חולשות הנובעות ממבנה החוג.

בהשוואת ביצועים לעומת [[RSA]] ו-[[הצפנה מבוססת עקום אליפטי|ECC]] למשל (ראה טבלה), נמצא ש-NTRU מציגה תוצאות טובות בהרבה{{הערה|[http://homes.esat.kuleuven.be/~fvercaut/papers/ntru_gpu.pdf Speed records for NTRU]}}. זמן הביצוע של הפעולות הפרטיות בצד המקבל אינו גדל באופן ריבועי כמו ב-RSA. בניסויים שנעשו NTRU השיגה זמן ביצוע בחומרה של כ-200,000 הצפנות לשנייה ברמת ביטחון של 256 סיביות.

{| class="wikitable" align="center"
|- align="center"
! דרגת ביטחון !! colspan="2" | NTRU אורך מפתח !! ECC !! RSA !! colspan="2" | NTRU פעולות/שנייה !! ECC !! RSA
|- align="center"
| בסיביות || רגיל  || אופטימלי || colspan="2" | אורך מפתח  || רגיל || אופטימלי || colspan="2" | פעולות/שנייה
|- align="center"
| '''112''' || 5,951 || 4,411 || 224 || 2,048 || 2,284 || 10,638 || 951 || 156
|- align="center"
| '''128''' || 6,743 || 4,829 || 256 || 4,096 || 1,896 || 9,901 || 650 || 12
|- align="center"
| '''192''' || 9,757 || 6,523 || 384 || 7,680 || 1,034 || 6,849 || 285 || 8
|- align="center"
| '''256''' || 12,881 || 8,173 || 512 || 15,360 || 638 || 5,000 || 116 || 1
|}

חברת Security Innovation מציעה פרסים של עד 90,000 דולר למי שיצליח לפרוץ את אחד ממספרי האתגר מהרשימה שפורסמה{{הערה|[https://www.securityinnovation.com/products/ntru-crypto/ntru-challenge NTRU Challenge]}}.

==רקע מתמטי==
הצפנת NTRU{{הערה|1= [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.182.9999&rep=rep1&type=pdf An Introduction to Mathematical Cryptography, פרק 6 - Lattices and Cryptography, עמוד 392]}} משתמשת בטכניקת ערבוב המבוססת על [[מבנה אלגברי|אלגברה]] ב[[חוג הפולינומים]] והאינטראקציה שלה עם [[חשבון מודולרי]] ואילו הפענוח הוא הפעולה ההפוכה כלומר שחזור פעולת הערבוב במידה מסוימת בסיוע [[תורת ההסתברות]]. בדומה ל-[[GGH]] ביטחון מערכת ההצפנה NTRU נשען במידה ניכרת על הבעיה הקשה שבמציאת הווקטור הקרוב ביותר ב[[הצפנה מבוססת סריג|תורת הסריגים]] בקיצור [[בעיית הווקטור הקצר ביותר|SVP]]. מערכת זו נכללת בקטגוריה [[הצפנה הסתברותית]], שפירושה שהיא כוללת אלמנט אקראי שונה בכל הצפנה. מה שמייחד אותה היא העובדה שההצפנה והפענוח הם ב[[סיבוכיות]] של <math>O(N^2)</math> פעולות עבור בלוק מסר בגודל <math>N</math> בהשוואה ל-[[RSA]] שדורשת <math>N^3</math> פעולות ביישום רגיל לא ממוטב. אורך המפתח הוא <math>O(N)</math> והוא קטן במידה ניכרת בהשוואה לשיטות דומות כמו [[הצפנת מקאליס]] או GGH.

הגרסה המקורית של NTRU כוללת ארבעה פרמטרים בסיסיים <math>(N,p,q,d)</math> וכן ארבע קבוצות פולינומים <math>\mathcal{L}_f,\mathcal{L}_g,\mathcal{L}_{\phi},\mathcal{L}_m</math> ממעלה <math>N-1</math> עם מקדמים שלמים המייצגים את טווח המפתח הפרטי והציבורי, טווח האלמנט האקראי וטווח המסר בהתאמה (מפורטים בהמשך). <math>N</math> הוא [[מספר ראשוני]] ונקרא כאן פרמטר ביטחון והוא קובע את רמת הביטחון של המערכת בהתאם לדרישה, <math>d</math> מציין את מספר המקדמים החיוביים והשליליים (מפורט בהמשך). <math>p</math> ו-<math>q</math> נקראים מודולוס ומשמשים לצמצום המקדמים. הם לא חייבים להיות ראשוניים אך נדרש שיתקיים <math>\text{gcd}(p,q)=\text{gcd}(N,q)=1</math> (כאשר <math>\text{gcd}</math> היא פונקציית [[מכנה משותף מינימלי]]). וכן <math>q</math> צריך להיות גדול משמעותית מ-<math>p</math> למשל <math>q>(6d+1)p</math> (אם כי זה לא הכרחי ומסיבות של יעילות רצוי <math>q</math> פחות גדול). הפעולות של הצופן הן ב[[חוג הפולינומים]] <math>R=\mathbb{Z}[X]/(X^N-1)</math>. האלמנט <math>F\in R</math> הוא פולינום המיוצג על ידי הווקטור:
<center>
:<math>F=\sum_{i=0}^{N-1}F_ix^i</math> או בכתיב מקוצר <math>[F_0,F_1,...,F_{N-1}]</math>.
</center>
כאן מכפלת שני פולינומים (וקטורים ב-<math>R</math>) מיוצגת על ידי הסימן <math>\circledast</math>. היא נקראת גם [[קונבולוציה מעגלית]] והיא מוגדרת כך:
<center>
:<math>F\circledast G=H\text{ and }H_k=\sum_{i=0}^{k}F_iG_{k-i}+\sum_{i=k+1}^{N-1}F_iG_{N+k-i}=\sum_{i+j\equiv k\text{ (mod }N)}F_iG_j</math>.
</center>
בעיקרון פעולת כפל אלמנטים ב-<math>R</math> היא בסיבוכיות <math>N^2</math> פעולות כפל בסיסיות מודולו <math>q</math>, אם המקדמים קטנים שזה מה שקורה בממוצע, הפעולה תהיה מהירה. אם המקדמים גדולים ייתכן שיהיה יותר מהיר להפעיל את [[FFT]] בסיבוכיות זמן של <math>O(N\text{log}N)</math> פעולות.

לצורך NTRU משתמשים ב'''פולינום טרינארי''' שהוא פולינום שבו המקדמים <math>a_i\in\{-1,0,1\}</math>. מייצגים זאת על ידי הסימון <math>\mathcal{T}(d_1,d_2)</math> שפירושו שבפולינום <math>f(x)\in R</math> בסך הכול <math>d_1</math> מקדמים שווים <math>1</math>, בסך הכול <math>d_2</math> מקדמים שווים <math>-1</math> והיתר אפס. לדוגמה:
<center>
:<math>f(x)=x^{10}+x^8-x^3+x^2-1\in\mathcal{T}(3,2)</math>.
</center>
קיים מיפוי טבעי (הומומורפי) בין האלמנטים בחוג <math>R</math> לבין אלמנטים מהחוג <math>R_q</math> (מודולו <math>q</math>) המיפוי הוא פשוט צמצום המקדמים מודולו <math>q</math>. לפעמים דרוש מעבר בכיוון ההפוך, כלומר אם <math>a(x)\in R_q</math> הוא פולינום, אפשר לבצע "הגבהה" או "מרכוז" (center lift) שלו כך שיתקבל פולינום <math>a'(x)\in R</math> המקיים <math>a'(x)\text{ mod }q=a(x)</math>, בוחרים את המקדמים באופן כזה שהם יהיו בטווח:
:<math>-\frac{q}{2}<a_i'\le \frac{q}{2}</math>

כלומר אם לאחר צמצום ב-<math>q</math> מתקבל <math>a_i\ge q/2</math> ערכו יהיה <math>a_i=a_i-q</math>. לדוגמה אם <math>N=5, q=7</math> ונתון הפולינום <math>a(x)=4x^4+2x^3-6x^2+3x+5</math> ה-center lift שלו הוא הפולינום <math>a'(x)=-3x^4+2x^3+x^2 +3x-2</math> כשהמקדמים הם השלמים בטווח <math>[-3,3]</math>.

==תיאור האלגוריתם==
תיאור הפונקציה '''NTRUencrypt'''. להכנה המקבל '''בוב''' מכין בסוד שני פולינומים טרינאריים <math>f,g\in\mathcal{L}_g</math>. הפולינום <math>f</math> חייב להיות [[הופכי כפלי מודולרי|הפיך]] מודולו <math>p</math> ומודולו <math>q</math>. לכן הוא נבחר בצורה <math>\mathcal{T}(d+1,d)</math> (במקרה של <<math>\mathcal{T}(d,d)</math> לפולינום אף פעם אין הופכי ב<math>R_q</math>). חישוב ההופכי שלו נעשה עם [[אלגוריתם אוקלידס#אלגוריתם אוקלידס המורחב|אלגוריתם אוקלידס המורחב]]. ההופכיים שלו מסומנים כאן <math>f_p^{-1}</math> ו-<math>f_q^{-1}</math> כאשר מתקיים כרגיל:
<center>
:<math>f_q^{-1}\circledast f\equiv 1\text{ (mod }q), \ \ \ f_p^{-1}\circledast f\equiv 1\text{ (mod }p)</math>.
</center>
לאחר מכן בוב מחשב את מכפלת הפולינומים: <math>h\equiv f_q^{-1}\circledast g\text{ (mod }q)</math>.

המפתח הציבורי של בוב הוא <math>h</math> אותו הוא שולח לאליס בערוץ פתוח כלשהו (כמו בכל מערכת הצפנה חלה החובה לאמתו). המפתח הפרטי הוא הפולינום <math>f</math> (וכן ההופכיים שלו כאמור) והוא נשמר בסוד. הפולינום <math>g</math> אינו נחוץ להצפנה ופענוח ולכן יש להשמידו.

===הצפנה===
אם '''אליס''' רוצה להצפין עבור בוב את המסר <math>m\in\mathcal{L}_m</math>. (כלומר המסר צריך להיות ממופה לפולינום טרינארי מהקבוצה <math>\mathcal{L}_m</math> בדרך גלויה ומוסכמת על כל הצדדים). היא בוחרת פולינום אקראי חד-פעמי <math>\phi\in\mathcal{L}_{\phi}</math> המשמש להסתרת המסר ומשתמשת במפתח הציבורי של בוב כדי לחשב את:
<center>
:<math>c=p\phi\circledast h+m\text{ (mod }q)</math>.
</center>
ושולחת את <math>c</math> לבוב.

===פענוח===
לפענוח בוב משתמש במפתח הפרטי שלו <math>f</math> וההופכי שלו כדי לחשב את:
<center>
:<math>a\equiv f\circledast c\text{ (mod }q)</math>.
</center>
המקבל משנה את המקדמים של <math>a</math> כך שיהיו בטווח <math>[-q/2,q/2]</math> פעולה זו נקראת center-lift. כעת אם מתייחסים ל-<math>a</math> כאל פולינום עם מקדמים שלמים בוב יכול לחלץ את המסר על ידי:
<center>
:<math>m=f_p^{-1}\circledast a\text{ (mod }p)</math>.
</center>
הפענוח יצליח בהסתברות גבוהה מאוד, אם כי פרמטרים מסוימים עלולים לגרום בסבירות זניחה לכישלון בפענוח. מקרה זה נגרם כתוצאה מכך שהמסר אינו ממורכז כראוי, אפשר לנסות שוב עם מקדמים בהיסט קל מהטווח האמור למשל בין <math>-q/2+x</math> ל-<math>q/2+x</math> עבור <math>x</math> קטן כלשהו ואם גם זה נכשל לא ניתן לפענח את המסר כלל. כאמור אירוע כזה זניח ואפשר להתעלם ממנו בפועל. הוכחה לנכונות הפענוח היא:
<center>
{|
|-
|
<div class="mw-content-ltr">
:<math>a\equiv f\circledast c\equiv f\circledast p\phi\circledast h+f\circledast m\text{ (mod }q)</math>
:::::<math>=f\circledast p\phi\circledast f_q^{-1}\circledast g+f\circledast m\text{ (mod }q)</math>
:::::<math>=p\phi\circledast g+f\circledast m\text{ (mod }q)</math>.
</div>
|}
</center>

בבחירת פרמטרים נכונה מקדמי הפולינום האחרון כמעט תמיד בטווח <math>[-q/2,q/2]</math> ולכן אינו משתנה כשמצמצמים מודולו <math>q</math>. המשמעות היא שכאשר בוב מצמצם את המקדמים של <math>f\circledast c</math> מודולו <math>q</math> הוא מקבל את הפולינום <math>a=p\phi\circledast g+f\circledast m</math> בחוג <math>\mathbb{Z}[X]/(X^N-1)</math> וכאשר הוא מצמצם את המקדמים של <math>a</math> מודולו <math>p</math> הוא מבטל את <math>p\phi\circledast g</math> ומקבל את הפולינום <math>f\circledast m\text{ (mod }p)</math> אותו הוא יכול להכפיל ב-<math>f_p^{-1}</math> כדי לחלץ את <math>m</math>.

==חתימה דיגיטלית==
הרעיון של האלגוריתם '''NTRUsign''' הוא שהחתימה היא הוכחה שהחותם יכול פתור את בעיית הווקטור הקצר ביותר (SVP) בסריג NTRU של הנקודה המיוצגת על ידי המסמך או תמצית שלו. המפתח הפרטי (מפתח החתימה) שלו הוא בסיס קצר של הסריג NTRU והמפתח הציבורי (מפתח האימות) הוא בסיס הרבה יותר ארוך. המוודא יכול בקלות לראות שאכן החתימה היא באמת וקטור קרוב ביותר למסמך. אך עם המפתח הציבורי המוודא אינו יכול בעצמו או שזה קשה מאוד עבורו למצוא וקטור קרוב.

מאז המצאתו והצגתו ביורוקריפט 2001, אלגוריתם החתימה NTRUSign סובל מהיסטוריה של בעיות וכשלים רבים ובוצעו מספר תיקונים ותוספות טלאים. תחילה גילו Craig Gentry ו-Mike Szydlo{{הערה|[http://www.szydlo.com/ntru-revised-full02.pdf Cryptanalysis of the Revised NTRU Signature Scheme]}} בגרסה המקורית תקלה חמורה, עותקים של החתימה הדיגיטלית חושפים מידע לגבי המפתח הפרטי. המפתחים תקנו את הבעיה ופרסמו אלגוריתם משופר וכן הצעה לתקן R-NSS. ב-2006 פרסמו [[עודד רגב (מדען מחשב)|עודד רגב]] ו-Phong Nguyen
קריפטואנליזה{{הערה|[ftp://ftp.di.ens.fr/pub/users/pnguyen/FullLEARNING.pdf Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures]}} של חתימת NTRU המאפשרת לחשוף את המפתח הפרטי בזמן מאוד קצר תוך שימוש ב-400 חתימות בלבד. הפתרון שהוצע היה "הסטה" (perturbation) כלומר החותם מסיט את הנקודה המייצגת את המסר על ידי וקטור סודי קצר. שוב נמצא שהתיקון לא שיפר בהרבה את המצב, בהתקפה שפורסמה{{הערה|[http://www.di.ens.fr/~ducas/NTRUSign_Cryptanalysis/DucasNguyen_Learning.pdf Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures]}} אפשר לחשוף את המפתח הפרטי עם 300,000 חתימות בלבד. נכון לשנת 2016 לא ברור אם האלגוריתם ראוי לשימוש במתכונתו הנוכחית למרות התיקונים והטלאים שנוספו.

===תיאור האלגוריתם===
תחילה החותם בוב בוחר פרמטרים מתאימים <math>(N,q,d)</math> באופן כזה שבעיית הווקטור הקצר תהיה קשה לפתרון בסריג בעל מימד <math>2N</math> מודולו <math>q</math>. כמפתח הסודי הוא בוחר שני פולינומים טרינאריים <math>f(x)</math> ו-<math>g(x)</math> מהצורה <math> \mathcal{T}(d+1,d)</math> ומחשב את המפתח הציבורי <math>h(x)=f(x)^{-1}\circledast g(x)\text{ (mod }q)</math> בדיוק כמו בתהליך ההכנה של הצפנת NTRU. את <math>h(x)</math> הוא שולח כמפתח אימות לאליס ושומר בסוד את כל היתר.

כדי לחתום על מסמך <math>D=(d_1,d_2)</math> (המסמך מחולק לשני פולינומים שווים), תחילה באמצעות אלגוריתם אוקלידס המורחב מחשב שני פולינומים נוספים <math>F(x),G(x)</math> שנקראים "חצי בסיס משלים" לסריג NTRU כך שמתקיים <math>f(x)\circledast G(x)-g(x)\circledast F(x)=q</math>. ומחשב את שני הווקטורים:
:<math>v_1(x)=\left\lfloor\frac{d_1(x)\circledast G(x)-d_2(x)\circledast F(x)}{q}\right\rceil</math>
:<math>v_2(x)=\left\lfloor\frac{d_1(x)\circledast g(x)-d_2(x)\circledast f(x)}{q}\right\rceil</math>

כאשר הסימון <math>\left\lfloor p(x)\right\rceil</math> מייצג פולינום עם מקדמים המעוגלים לשלם הקרוב ביותר. החתימה של בוב על המסמך <math>d(x)</math> היא: <math>s(x)=v_1(x)\circledast f(x)+v_2(x)\circledast F(x)</math>. את החתימה והמסמך <math>(D, s)</math> הוא שולח לאליס.

המקבלת אליס המעוניינת לוודא את חתימתו של בוב משתמשת במפתח הציבורי שלו <math>h(x)</math> כדי לחשב את:
:<math>t(x)=h(x)\circledast s(x)\text{ (mod }q)</math>.

היא בוחרת את המקדמים שלו מודולו <math>q</math> כך שיהיו קרובים ככל האפשר למקדמים המקבילים של המסמך <math>d(x)</math> ומוודא שהווקטור <math>(s,t)</math> אכן קרוב למסמך <math>d_1,d_2</math> (כאמור קל לוודא זאת אך קשה למצוא וקטור כזה, מסיבה זו אליס עצמה או כל אחד אחר לא יוכל לחתום על המסמך מבלי שהדבר יתגלה כתרמית ללא המפתח הפרטי המתאים, כיוון שבהסתברות גבוהה מאוד התוצאה תהיה וקטור רחוק למדי).

==ביטחון==
*כדי לשבור את הצופן המתקיף יכול לנסות כמה דרכים. בשיטת [[כוח גס]] המתקיף יכול לנסות לנחש את המפתח הפרטי על ידי ניסוי כל האפשרויות של <math>f\in\mathcal{L}_f</math> ובדיקה אם המכפלה <math>f\circledast h</math> מודולו <math>q</math> מכילה כניסות קטנות. באותה שיטה אפשר לנסות לנחש את המסר. בעיקרון סודיות המפתח תלויה בגודל הקבוצה <math>\mathcal{L}_g</math> וביטחון מסר מוצפן ב-<math>\mathcal{L}_{\phi}</math>.
*אם זיכרון זמין [[התקפת ניפגש באמצע]] מאפשרת לקצר את זמן הניחוש של המפתח הפרטי בפקטור ריבועי. מחלקים את <math>f</math> לשני חצאים נניח <math>f=(f_1,f_2)</math> ואז משווים זוגות שונים של <math>f_1\circledast c</math> ו-<math>-f_2\circledast c</math> כן שמקדמיהם בעלי ערך דומה בקירוב. החיפוש מתבצע עם טבלה המכילה רשימה ממוינת של החצי האחד והחיפוש מתבצע על החצי השני עד שנמצא מועמד טוב. לאור זאת הטווח או מספר האלמנטים בקבוצה צריך להיות כפול כדי להגיע לרמת ביטחון נדרשת. לדוגמה עבור ביטחון מינימלי בסטנדרטים של ימינו <math>2^{80}</math> הטווח של <math>f</math>, <math>g</math> ו-<math>\phi</math> צריך להיות בסביבות <math>2^{160}</math>.
*אם אליס מצפינה מסרים רבים (נגיד ארבעה או חמישה) עם אותו מפתח ציבורי אך עם מספר אקראי שונה עבור כל מסר כנדרש, המתקיף יכול לנצל נתון זה כדי לשבור את המערכת ולנחש את המסר כדלהלן: נניח שאליס הצפינה את <math>c_i=\phi_i\circledast h + m\text{ (mod }q)</math> בסך הכול <math>r</math> פעמים עם <math>r</math> ערכי <math>\phi</math> שונים. המתקיפה איב יכולה לחשב את <math>(c_i-c_1)\circledast h^{-1}</math> ומתקבל <math>\phi_i-\phi_1</math> עבור <math>1\le i\le r</math>. היות שהמקדמים של <math>\phi_i</math> קטנים למעשה היא מקבלת בהסתברות גבוהה את <math>\phi_i-\phi_1</math> ממנו היא יכולה לגלות מקדמים רבים של <math>\phi_1</math> ואת היתר היא יכולה לנחש בכוח גס. אם <math>\phi_1</math> ידוע אפשר לגלות את <math>m</math>. מסיבה זו הצפנה חוזרת של מסר נתון אינה מומלצת מבלי להסתיר את המסר על ידי פעולת ערבוב נוספת כלשהי עם אקראיות. כמובן שההתקפה המתוארת יעילה רק עבור מסר אחד ואין בה כדי לסייע בפענוח מסרים אחרים.
*בעיית חישוב המפתח הפרטי מתוך המפתח הציבורי היא: בהינתן <math>h(x)</math> מצא שני פולינומים טרינאריים <math>f(x)</math> ו-<math>g(x)</math> המקיימים <math>f(x)\circledast g(x)\equiv h(x)\text{ (mod }q)</math>. הוכח שבעיה זו כמעט שקולה לבעיית הווקטור הקצר ביותר במחלקה מיוחדת של סריגים. תאורטית המתקיף יכול לנסות לשבור את המערכת על ידי ניסיון לפתור את בעיית הווקטור הקצר ביותר. אפשר למצוא וקטור כזה בחיפוש ממצא או עם אלגוריתם [[LLL]] אך סיבוכיות התקפה כזו לרוב אינה מעשית היות שבעיית הווקטור הקצר ביותר ידועה כבעיה קשה מאוד ולא ידוע על פתרון פולינומי.

===בחירת פרמטרים===
המפתחים הציעו שלוש קונפיגורציות של פרמטרים המציעות דרגות שונות של ביטחון מהקל אל הכבד:

'''אופציה 1.''' ביטחון נמוך המתאים למסרים בעלי חשיבות נמוכה או כאשר המפתחות מוחלפים בתדירות גובהה, כמו בהצפנת [[שיחה אלחוטית]] או [[ממיר טלוויזיה]].

<math>(N,p,q,d)=(107,3,64,5), \mathcal{L}_f=\mathcal{L}(15,14),\mathcal{L}_g=\mathcal{L}(12,12),\mathcal{L}_{\phi}=\mathcal{L}(5,5)</math>. הפולינום <math>\mathcal{L}_f=\mathcal{L}(15,14)</math> פירושו פולינום טרינארי שמכיל 15 מקדמים חיוביים (<math>1</math>) ו-14 מקדמים שליליים (<math>-1</math>).

המפתח הפרטי הוא באורך 340 סיביות והמפתח הציבורי באורך 642 סיביות. דרגת ביטחון של המפתח היא <math>2^{50}</math>.

'''אופציה 2.''' ביטחון בינוני.

<math>(N,p,q,d)=(167,3,128,18), \mathcal{L}_f=\mathcal{L}(61,60),\mathcal{L}_g=\mathcal{L}(20,20),\mathcal{L}_{\phi}=\mathcal{L}(18,18)</math>

המפתח הפרטי באורך 530 סיביות והציבורי 1169 סיביות. רמת ביטחון של <math>2^{82.9}</math>.

'''אופציה 3.''' ביטחון גבוה.

<math>(N,p,q,d)=(503,3,256,55), \mathcal{L}_f=\mathcal{L}(216,215),\mathcal{L}_g=\mathcal{L}(72,72),\mathcal{L}_{\phi}=\mathcal{L}(55,55)</math>

אורך מפתח פרטי 1595 סיביות וציבורי 4024 סיביות. רמת ביטחון של <math>2^{285}</math>.

==דוגמה במספרים קטנים==
הדוגמה הבאה ממחישה את הצפנת NTRU במספרים קטנים. כמובן שבפועל מערכת כזו צריכה להיות בקנה מידה הרבה יותר גדול כדי שתהיה בטוחה. נניח שהפרמטרים של המערכת הם:
:<math>(N,p,q,d)=(7,3,41,2)</math>

להכנה בוב בוחר את הפולינומים:
:<math>f(x)=x^6-x^4+x^3+x^2-1\in\mathcal{T}(3,2)</math> וכן
:<math>g(x)=x^6+x^4-x^2-x\in\mathcal{T}(2,2)</math>

ומחשב את ההופכיים שלהם:
:<math>f_q^{-1} = f(x)^{-1}\text{ mod }q= 8x^6+26x^5+31x^4+21x^3+40x^2+2x+37 \text{ (mod } 41)</math>
:<math>f_p^{-1} = f(x)^{-1}\text{ mod }p= x^6+2x^5+x^3+x^2+x+1 \text{ (mod } 3)</math>

בוב שומר את <math>f(x)</math> ואת ההופכי שלו <math>f_q^{-1}</math> כמפתח פרטי.

כעת בוב מחשב ומפרסם ברבים את המפתח הציבורי שלו:
:<math>h(x) = f_q^{-1}\circledast g(x)= 20x^6+40x^5+2x^4+38x^3+8x^2+26x+30 \text{ (mod } 41)</math>

נניח שאליס מעוניינת לשלוח לבוב את המסר: <math>m(x) = -x^5 + x^3 + x^2 - x + 1</math>

תחילה היא בוחרת מספר אקראי נניח: <math>r(x) = x^6-x^5+x-1</math> משתמשת במפתח הציבורי של בוב ומחשבת את:
:<math>c(x) = p\ r(x)\circledast h(x)+m(x)\equiv 31x^6+19x^5+4x^4+2x^3+40x^2+3x+25 \text{ (mod } 41)</math>

אותו היא שולחת לבוב. כאשר בוב מקבל את <math>c(x)</math> הוא פועל כדלהלן. תחילה מחשב את:
:<math>f(x)\circledast c(x)\equiv x^6+10x^5+33x^4+40x^3+40x^2+x+40 \text{ (mod } 41)</math>

ואז מבצע מרכוז (Centerlift) של מקדמי התוצאה מודולו <math>q</math> ומקבל את:
:<math>a(x) = x^6+10x^5-8x^4-x^3-x^2+x-1</math>

לבסוף מצמצם את מקדמי <math>a(x)</math> מודולו <math>p</math> ומכפיל בהופכי:
:<math>f_p^{-1}(x)\circledast a(x)\equiv 2x^5+x^3+x^2+2x+1 \text{ (mod } 3)</math>

ממרכז (Centerlift) את התוצאה האחרונה מודולו <math>p</math> ומקבל את:
:<math>m = -x^5 + x^3 + x^2 - x + 1 \text{ (mod } 3)</math>

==שיטות מתקדמות==
הצפנות מבוססות סריגים נכשלו לא אחת בגלל התקפות שניצלו מבנה מיוחד של הסריג למשל ב[[חוג הפולינומים]] או [[שדה (מבנה אלגברי)|שדה]] [[סדר (תורת החבורות)|מסדר]] [[מספר ראשוני|ראשוני]] גבוה. מסיבה זו הוצעו מספר מבנים שונים שנועדו לחזק את המערכת נגד קריפטואנליזה המנצלת חולשות הנובעות ממבנה החוג וכן נגד קריפטואנליזה קוונטית. כמה מבנים אפשריים הם:
*<math>(\mathbb{Z}/q)[x](x^p-1)</math> כאשר <math>p</math> ראשוני ו-<math>q</math> הוא חזקה של 2 כמו בגרסה המקורית של NTRU.
*<math>(\mathbb{Z}/q)[x](x^p+1)</math> כאשר <math>p</math> הוא חזקה של 2 ו-<math>q\in1+2p\mathbb{Z}</math> גם ראשוני. מבנה זה הוצע על ידי Damien Stehlé ו-Ron Steinfeld לשיפור NTRU כך שיהיה בעל ביטחון מוכח וכן נמצא בשימוש [[RingLWE]].
*<math>(\mathbb{Z}/q)[x](x^p-x-1)</math> כאשר <math>p</math> ראשוני. הוצע על ידי דניאל ברנשטיין ואחרים כתחליף טוב יותר למבנה החוג ב-NTRU.

ב-2011 הציעו Damien Stehlé ו-Ron Steinfeld גרסה משופרת{{הערה|[https://eprint.iacr.org/2013/004 Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices]}} בשינויים קלים של הצפנה/חתימה דיגיטלית NTRU המוכחת כבטוחה נגד [[התקפת מוצפן-נבחר]] במסגרת [[מודל אורקל אקראי]] או מודל [[סיבוכיות]] סטנדרטי, תחת הנחת הקושי שבפתרון בעיות סריגים (במחשב קלאסי או קוונטי) עם הגבלה לסוג מסוים של סריגים מעל [[שדה ציקלוטומי]]. הם הראו שאם בוחרים את הפולינומים הסודיים של המקבל כפונקציית [[גאוסיין]] בדידית אז המפתח הציבורי ייראה מבחינה סטטיסטית אחיד ובלתי ניתן להבחנה מעל הטווח שלה. תכונת [[ביטחון סמנטי#אי-יכולת הבחנה|אי-הבחנה]] בהקשר של מפתח ציבורי פירושה קושי בניחוש המפתח הפרטי מתוך המפתח הציבורי.

בתהליך ההכנה של NTRU. המפתח הפרטי הוא שני פולינומים "דלילים" ממעלה הנמוכה מ-<math>n</math> עם מקדמים <math>\{-1,0,1\}</math>. המפתח הציבורי הוא המנה שלהם בחוג <math>\mathbb{Z}_q[x]/(x^n-1)</math>. בחירת המפתח הפרטי נעשית כפונקציה גאוסיאנית בדידית באופן כזה שסטיית התקן תהיה בערך <math>q^{1/2}</math>. השינויים שהוצעו לעומת הגרסה המקורית הם כדלהלן:
# החלפת חוג הפולינומים ב-<math>R=\mathbb{Z}/(x^n+1)</math> כאשר <math>n</math> הוא חזקה של 2. כך מתקבל חוג שלמים מעל שדה ציקלוטומי.
# <math>q</math> הוא ראשוני כך שמתקיים <math>f=x^n+1</math> מתחלק ל-<math>n</math> גורמים ([[העתקה ליניארית|העתקות ליניאריות]]) שונים מודולו <math>q</math>.
# <math>f</math> ו-<math>g</math> נלקחים מתוך דגימה גאוסיאנית דיסקרטית מעל החוג <math>R</math>, בתנאי שהם הפיכים מודולו <math>q</math>. אם הם אינם הפיכים מתעלמים מהדגימה ומנסים דגימה אחרת עד שהתנאי מתקיים. כמו כן <math>f</math> הוא מהצורה <math>f=p\bar f+1</math> כאשר <math>\bar f </math> הוא הדגימה הגאוסיאנית האמורה. התוספת האחרונה מקלה על הפענוח כי אם מתקיים <math>f = 1\text{ mod }p</math> לא צריך את ההכפלה האחרונה בהופכי של <math>f</math>.
# מוסיפים וקטור שגיאה קטן <math>e</math> להצפנה כך שההצפנה כעת היא: <math>c=hs+pe + m\text{ (mod }q)</math>, כאשר <math>e</math> נבחר טווח השגיאה של בעיית RingLWE.

השינויים הללו מעלים מעט את סיבוכיות ההצפנה לעומת ההצעה המקורית, בעיקר בגלל התוספות האמורות, אך בתמורה מושג שיפור משמעותי בביטחון ההצפנה.

==תקנים==
NTRU נמצא בתהליך תקינה של שני גופים בינלאומיים:
* תקן [[IEEE]] 1363.1 שהחל ב-2008{{הערה|[http://grouper.ieee.org/groups/1363/ The IEEE P1363 Home Page]}}.
* תקן X9.98 של ASC X9 ([[מכון התקנים האמריקני]]){{הערה|[http://www.businesswire.com/news/home/20110411005309/en/Security-Innovation’s-NTRUEncrypt-Adopted-X9-Standard-Data Security Innovation’s NTRUEncrypt Adopted as X9 Standard for Data Protection]}}.

בנוסף האלגוריתם הוצע בטיוטת [[IETF]] כמועמד לפרוטוקול [[TLS (פרוטוקול)|TLS]]. ב-2009 הוזכר NTRU על ידי [[NIST]] כמועמד אפשרי לאלגוריתם הצפנה אסימטרי פוסט-קוונטי, שיחליף את האלגוריתמים הנוכחיים. במסגרת המאמץ להתכונן לקראת העידן הקוונטי{{הערה|[http://csrc.nist.gov/publications/drafts/nistir-8105/nistir_8105_draft.pdf Report on Post-Quantum Cryptography]}} ב-NIST מתכוונים לפרסם בסוף 2016 תחרות פתוחה{{הערה|[http://csrc.nist.gov/groups/ST/post-quantum-crypto/workshops.html POST-QUANTUM CRYPTO PROJECT]}} שבה יבחנו הצעות לאלגוריתם פוסט-קוונטי.

==יישומים==
NTRU זמינה כקוד פתוח תחת רישיון GPL ו-FOSS. בתנאי שכל שימוש בו יהיה זמין גם הוא כקוד פתוח. זאת במטרה להסיר מכשולים ולאפשר למפתחים להטמיע את האלגוריתם מהר ככל האפשר. כמו כן האלגוריתם ניתן לשימוש מסחרי תחת רישיון BSD. כיום ישנם ב-[[GitHub]] שני פרויקטי קוד פתוח ב-C וב-Java המיישמים את NTRU; פרויקט NTRU{{הערה|[https://github.com/NTRUOpenSourceProject/ntru-crypto Open Source NTRU Public Key Cryptography and Reference Code]}} תחת רישיון GPL וספריית NTRU{{הערה|[http://tbuktu.github.io/ntru The NTRU Project]}} ברישיון BSD.

==ראו גם==
* [[הצפנת מפתח ציבורי]]
* [[חתימה דיגיטלית]]
* [[GGH]]

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{קריפטוגרפיה}}

[[קטגוריה:ערכים שבהם תבנית אתר רשמי אינה מתאימה להוספה אוטומטית]]
[[קטגוריה:הצפנה]]
[[קטגוריה:מפתח ציבורי]]
[[קטגוריה:חתימה דיגיטלית]]