NTRU

NTRUהיא מערכתהצפנתמפתח ציבוריוחתימה דיגיטליתמבוססתסריגיםמוגנת בפטנטוקוד פתוחברישיוןGPL,שהומצאה ב-1996 והוצעה כתקן חלופי למערכות הקיימותRSAו-ECC.נכללת ברשימת האלגוריתמים הפוסט-קוונטייםוידועה כמערכת האסימטרית המהירה והיעילה ביותר נכון לשנת 2016. למרות היותו בתהליך תיקנון Std 1363.1 שלIEEEוכן X9.98 שלASC,בשלקריפטואנליזהשלו ביטחונו אינו ברור והוא מוטל בספק. קיימת גרסה אחת של Damien Stehlé ו- Ron Steinfeld שנמצאת בתהליך תקנון וניתנת להוכחה כבטוחה לפי המודל הסטנדרטי, היא פחות יעילה ומסתמכת עלR-LWE.

היסטוריה

הגרסה הראשונה הומצאה ב-1996 על ידי Jeffrey Hoffstein,Joseph Silverman ו- Jill Pipher. מאוחר יותר באותה שנה חברו המפתחים ל-Daniel Lieman ויסדו את חברת NTRU Cryptosystems שנרכשה ב-2009 על ידי Security Innovation.

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

ב-2013 פותחה גרסה של NTRUהמוכחת כבטוחה ואשר נחקרת על ידי קבוצות המחקר שלIEEEופרויקט PQCRYPTO כמועמדת "פוסט-קוונטית" להחלפת האלגוריתמים התיקניים הנמצאים בשימוש מסחרי. ב-2016 הציעודניאל ברנשטייןוחוקרים נוספים את NTRU Primeשהוא שיפור של NTRU המתמקד בחוג פולינומיםשל המערכת ואמור לספק עמידות נגד קריפטואנליזה שמנצלת חולשות הנובעות ממבנה החוג.

בהשוואת ביצועים לעומתRSAו-ECCלמשל (ראה טבלה), נמצא ש-NTRU מציגה תוצאות טובות בהרבה.זמן הביצוע של הפעולות הפרטיות בצד המקבל אינו גדל באופן ריבועי כמו ב-RSA. בניסויים שנעשו NTRU השיגה זמן ביצוע בחומרה של כ-200,000 הצפנות לשנייה ברמת ביטחון של 256 סיביות.

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

חברת Security Innovation מציעה פרסים של עד 90,000 דולר למי שיצליח לפרוץ את אחד ממספרי האתגר מהרשימה שפורסמה.

רקע מתמטי

הצפנת NTRUמשתמשת בטכניקת ערבוב המבוססת עלאלגברהבחוג הפולינומיםוהאינטראקציה שלה עםחשבון מודולריואילו הפענוח הוא הפעולה ההפוכה כלומר שחזור פעולת הערבוב במידה מסוימת בסיועתורת ההסתברות.בדומה ל-GGHביטחון מערכת ההצפנה NTRU נשען במידה ניכרת על הבעיה הקשה שבמציאת הווקטור הקרוב ביותר בתורת הסריגיםבקיצורSVP.מערכת זו נכללת בקטגוריההצפנה הסתברותית,שפירושה שהיא כוללת אלמנט אקראי שונה בכל הצפנה. מה שמייחד אותה היא העובדה שההצפנה והפענוח הם בסיבוכיותשל$O(N^{2})$פעולות עבור בלוק מסר בגודל$N$בהשוואה ל-RSAשדורשת$N^{3}$פעולות ביישום רגיל לא ממוטב. אורך המפתח הוא$O(N)$והוא קטן במידה ניכרת בהשוואה לשיטות דומות כמוהצפנת מקאליסאו GGH.

הגרסה המקורית של NTRU כוללת ארבעה פרמטרים בסיסיים$(N,p,q,d)$וכן ארבע קבוצות פולינומים${\mathcal {L}}_{f},{\mathcal {L}}_{g},{\mathcal {L}}_{\phi },{\mathcal {L}}_{m}$ממעלה$N-1$עם מקדמים שלמים המייצגים את טווח המפתח הפרטי והציבורי, טווח האלמנט האקראי וטווח המסר בהתאמה (מפורטים בהמשך).$N$הואמספר ראשוניונקרא כאן פרמטר ביטחון והוא קובע את רמת הביטחון של המערכת בהתאם לדרישה,$d$מציין את מספר המקדמים החיוביים והשליליים (מפורט בהמשך).$p$ו-$q$נקראים מודולוס ומשמשים לצמצום המקדמים. הם לא חייבים להיות ראשוניים אך נדרש שיתקיים${\text{gcd}}(p,q)={\text{gcd}}(N,q)=1$(כאשר${\text{gcd}}$היא פונקצייתמכנה משותף מינימלי). וכן$q$צריך להיות גדול משמעותית מ-$p$למשל$q>(6d+1)p$(אם כי זה לא הכרחי ומסיבות של יעילות רצוי$q$פחות גדול). הפעולות של הצופן הן בחוג הפולינומים$R=\mathbb {Z} [X]/(X^{N}-1)$.האלמנט$F\in R$הוא פולינום המיוצג על ידי הווקטור:

$F=\sum _{i=0}^{N-1}F_{i}x^{i}$או בכתיב מקוצר$[F_{0},F_{1},...,F_{N-1}]$.

כאן מכפלת שני פולינומים (וקטורים ב-$R$) מיוצגת על ידי הסימן$\circledast$.היא נקראת גםקונבולוציה מעגליתוהיא מוגדרת כך:

$F\circledast G=H{\text{ and }}H_{k}=\sum _{i=0}^{k}F_{i}G_{k-i}+\sum _{i=k+1}^{N-1}F_{i}G_{N+k-i}=\sum _{i+j\equiv k{\text{ (mod }}N)}F_{i}G_{j}$.

בעיקרון פעולת כפל אלמנטים ב-$R$היא בסיבוכיות$N^{2}$פעולות כפל בסיסיות מודולו$q$,אם המקדמים קטנים שזה מה שקורה בממוצע, הפעולה תהיה מהירה. אם המקדמים גדולים ייתכן שיהיה יותר מהיר להפעיל אתFFTבסיבוכיות זמן של$O(N{\text{log}}N)$פעולות.

לצורך NTRU משתמשים בפולינום טרינארישהוא פולינום שבו המקדמים$a_{i}\in \{-1,0,1\}$.מייצגים זאת על ידי הסימון${\mathcal {T}}(d_{1},d_{2})$שפירושו שבפולינום$f(x)\in R$בסך הכול$d_{1}$מקדמים שווים$1$,בסך הכול$d_{2}$מקדמים שווים$-1$והיתר אפס. לדוגמה:

$f(x)=x^{10}+x^{8}-x^{3}+x^{2}-1\in {\mathcal {T}}(3,2)$.

קיים מיפוי טבעי (הומומורפי) בין האלמנטים בחוג$R$לבין אלמנטים מהחוג$R_{q}$(מודולו$q$) המיפוי הוא פשוט צמצום המקדמים מודולו$q$.לפעמים דרוש מעבר בכיוון ההפוך, כלומר אם$a(x)\in R_{q}$הוא פולינום, אפשר לבצע "הגבהה" או "מרכוז" (center lift) שלו כך שיתקבל פולינום$a'(x)\in R$המקיים$a'(x){\text{ mod }}q=a(x)$,בוחרים את המקדמים באופן כזה שהם יהיו בטווח:

$-{\frac {q}{2}}<a_{i}'\leq {\frac {q}{2}}$

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

תיאור האלגוריתם

תיאור הפונקציהNTRUencrypt.להכנה המקבלבובמכין בסוד שני פולינומים טרינאריים$f,g\in {\mathcal {L}}_{g}$.הפולינום$f$חייב להיותהפיךמודולו$p$ומודולו$q$.לכן הוא נבחר בצורה${\mathcal {T}}(d+1,d)$(במקרה של <${\mathcal {T}}(d,d)$לפולינום אף פעם אין הופכי ב$R_{q}$). חישוב ההופכי שלו נעשה עםאלגוריתם אוקלידס המורחב.ההופכיים שלו מסומנים כאן$f_{p}^{-1}$ו-$f_{q}^{-1}$כאשר מתקיים כרגיל:

$f_{q}^{-1}\circledast f\equiv 1{\text{ (mod }}q),\ \ \ f_{p}^{-1}\circledast f\equiv 1{\text{ (mod }}p)$.

לאחר מכן בוב מחשב את מכפלת הפולינומים:$h\equiv f_{q}^{-1}\circledast g{\text{ (mod }}q)$.

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

הצפנה

אםאליסרוצה להצפין עבור בוב את המסר$m\in {\mathcal {L}}_{m}$.(כלומר המסר צריך להיות ממופה לפולינום טרינארי מהקבוצה${\mathcal {L}}_{m}$בדרך גלויה ומוסכמת על כל הצדדים). היא בוחרת פולינום אקראי חד-פעמי$\phi \in {\mathcal {L}}_{\phi }$המשמש להסתרת המסר ומשתמשת במפתח הציבורי של בוב כדי לחשב את:

$c=p\phi \circledast h+m{\text{ (mod }}q)$.

ושולחת את$c$לבוב.

פענוח

לפענוח בוב משתמש במפתח הפרטי שלו$f$וההופכי שלו כדי לחשב את:

$a\equiv f\circledast c{\text{ (mod }}q)$.

המקבל משנה את המקדמים של$a$כך שיהיו בטווח$[-q/2,q/2]$פעולה זו נקראת center-lift. כעת אם מתייחסים ל-$a$כאל פולינום עם מקדמים שלמים בוב יכול לחלץ את המסר על ידי:

$m=f_{p}^{-1}\circledast a{\text{ (mod }}p)$.

הפענוח יצליח בהסתברות גבוהה מאוד, אם כי פרמטרים מסוימים עלולים לגרום בסבירות זניחה לכישלון בפענוח. מקרה זה נגרם כתוצאה מכך שהמסר אינו ממורכז כראוי, אפשר לנסות שוב עם מקדמים בהיסט קל מהטווח האמור למשל בין$-q/2+x$ל-$q/2+x$עבור$x$קטן כלשהו ואם גם זה נכשל לא ניתן לפענח את המסר כלל. כאמור אירוע כזה זניח ואפשר להתעלם ממנו בפועל. הוכחה לנכונות הפענוח היא:

$a\equiv f\circledast c\equiv f\circledast p\phi \circledast h+f\circledast m{\text{ (mod }}q)$ $=f\circledast p\phi \circledast f_{q}^{-1}\circledast g+f\circledast m{\text{ (mod }}q)$ $=p\phi \circledast g+f\circledast m{\text{ (mod }}q)$.

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

חתימה דיגיטלית

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

מאז המצאתו והצגתו ביורוקריפט 2001, אלגוריתם החתימה NTRUSign סובל מהיסטוריה של בעיות וכשלים רבים ובוצעו מספר תיקונים ותוספות טלאים. תחילה גילו Craig Gentry ו-Mike Szydloבגרסה המקורית תקלה חמורה, עותקים של החתימה הדיגיטלית חושפים מידע לגבי המפתח הפרטי. המפתחים תקנו את הבעיה ופרסמו אלגוריתם משופר וכן הצעה לתקן R-NSS. ב-2006 פרסמועודד רגבו-Phong Nguyen קריפטואנליזהשל חתימת NTRU המאפשרת לחשוף את המפתח הפרטי בזמן מאוד קצר תוך שימוש ב-400 חתימות בלבד. הפתרון שהוצע היה "הסטה" (perturbation) כלומר החותם מסיט את הנקודה המייצגת את המסר על ידי וקטור סודי קצר. שוב נמצא שהתיקון לא שיפר בהרבה את המצב, בהתקפה שפורסמהאפשר לחשוף את המפתח הפרטי עם 300,000 חתימות בלבד. נכון לשנת 2016 לא ברור אם האלגוריתם ראוי לשימוש במתכונתו הנוכחית למרות התיקונים והטלאים שנוספו.

תיאור האלגוריתם

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

כדי לחתום על מסמך$D=(d_{1},d_{2})$(המסמך מחולק לשני פולינומים שווים), תחילה באמצעות אלגוריתם אוקלידס המורחב מחשב שני פולינומים נוספים$F(x),G(x)$שנקראים "חצי בסיס משלים" לסריג NTRU כך שמתקיים$f(x)\circledast G(x)-g(x)\circledast F(x)=q$.ומחשב את שני הווקטורים:

$v_{1}(x)=\left\lfloor {\frac {d_{1}(x)\circledast G(x)-d_{2}(x)\circledast F(x)}{q}}\right\rceil$

$v_{2}(x)=\left\lfloor {\frac {d_{1}(x)\circledast g(x)-d_{2}(x)\circledast f(x)}{q}}\right\rceil$

כאשר הסימון$\left\lfloor p(x)\right\rceil$מייצג פולינום עם מקדמים המעוגלים לשלם הקרוב ביותר. החתימה של בוב על המסמך$d(x)$היא:$s(x)=v_{1}(x)\circledast f(x)+v_{2}(x)\circledast F(x)$.את החתימה והמסמך$(D,s)$הוא שולח לאליס.

המקבלת אליס המעוניינת לוודא את חתימתו של בוב משתמשת במפתח הציבורי שלו$h(x)$כדי לחשב את:

$t(x)=h(x)\circledast s(x){\text{ (mod }}q)$.

היא בוחרת את המקדמים שלו מודולו$q$כך שיהיו קרובים ככל האפשר למקדמים המקבילים של המסמך$d(x)$ומוודא שהווקטור$(s,t)$אכן קרוב למסמך$d_{1},d_{2}$(כאמור קל לוודא זאת אך קשה למצוא וקטור כזה, מסיבה זו אליס עצמה או כל אחד אחר לא יוכל לחתום על המסמך מבלי שהדבר יתגלה כתרמית ללא המפתח הפרטי המתאים, כיוון שבהסתברות גבוהה מאוד התוצאה תהיה וקטור רחוק למדי).

ביטחון

• כדי לשבור את הצופן המתקיף יכול לנסות כמה דרכים. בשיטתכוח גסהמתקיף יכול לנסות לנחש את המפתח הפרטי על ידי ניסוי כל האפשרויות של$f\in {\mathcal {L}}_{f}$ובדיקה אם המכפלה$f\circledast h$מודולו$q$מכילה כניסות קטנות. באותה שיטה אפשר לנסות לנחש את המסר. בעיקרון סודיות המפתח תלויה בגודל הקבוצה${\mathcal {L}}_{g}$וביטחון מסר מוצפן ב-${\mathcal {L}}_{\phi }$.
• אם זיכרון זמיןהתקפת ניפגש באמצעמאפשרת לקצר את זמן הניחוש של המפתח הפרטי בפקטור ריבועי. מחלקים את$f$לשני חצאים נניח$f=(f_{1},f_{2})$ואז משווים זוגות שונים של$f_{1}\circledast c$ו-$-f_{2}\circledast c$כן שמקדמיהם בעלי ערך דומה בקירוב. החיפוש מתבצע עם טבלה המכילה רשימה ממוינת של החצי האחד והחיפוש מתבצע על החצי השני עד שנמצא מועמד טוב. לאור זאת הטווח או מספר האלמנטים בקבוצה צריך להיות כפול כדי להגיע לרמת ביטחון נדרשת. לדוגמה עבור ביטחון מינימלי בסטנדרטים של ימינו$2^{80}$הטווח של$f$,$g$ו-$\phi$צריך להיות בסביבות$2^{160}$.
• אם אליס מצפינה מסרים רבים (נגיד ארבעה או חמישה) עם אותו מפתח ציבורי אך עם מספר אקראי שונה עבור כל מסר כנדרש, המתקיף יכול לנצל נתון זה כדי לשבור את המערכת ולנחש את המסר כדלהלן: נניח שאליס הצפינה את$c_{i}=\phi _{i}\circledast h+m{\text{ (mod }}q)$בסך הכול$r$פעמים עם$r$ערכי$\phi$שונים. המתקיפה איב יכולה לחשב את$(c_{i}-c_{1})\circledast h^{-1}$ומתקבל$\phi _{i}-\phi _{1}$עבור$1\leq i\leq r$.היות שהמקדמים של$\phi _{i}$קטנים למעשה היא מקבלת בהסתברות גבוהה את$\phi _{i}-\phi _{1}$ממנו היא יכולה לגלות מקדמים רבים של$\phi _{1}$ואת היתר היא יכולה לנחש בכוח גס. אם$\phi _{1}$ידוע אפשר לגלות את$m$.מסיבה זו הצפנה חוזרת של מסר נתון אינה מומלצת מבלי להסתיר את המסר על ידי פעולת ערבוב נוספת כלשהי עם אקראיות. כמובן שההתקפה המתוארת יעילה רק עבור מסר אחד ואין בה כדי לסייע בפענוח מסרים אחרים.
• בעיית חישוב המפתח הפרטי מתוך המפתח הציבורי היא: בהינתן$h(x)$מצא שני פולינומים טרינאריים$f(x)$ו-$g(x)$המקיימים$f(x)\circledast g(x)\equiv h(x){\text{ (mod }}q)$.הוכח שבעיה זו כמעט שקולה לבעיית הווקטור הקצר ביותר במחלקה מיוחדת של סריגים. תאורטית המתקיף יכול לנסות לשבור את המערכת על ידי ניסיון לפתור את בעיית הווקטור הקצר ביותר. אפשר למצוא וקטור כזה בחיפוש ממצא או עם אלגוריתםLLLאך סיבוכיות התקפה כזו לרוב אינה מעשית היות שבעיית הווקטור הקצר ביותר ידועה כבעיה קשה מאוד ולא ידוע על פתרון פולינומי.

בחירת פרמטרים

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

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

$(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)$.הפולינום${\mathcal {L}}_{f}={\mathcal {L}}(15,14)$פירושו פולינום טרינארי שמכיל 15 מקדמים חיוביים ($1$) ו-14 מקדמים שליליים ($-1$).

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

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

$(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)$

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

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

$(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)$

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

דוגמה במספרים קטנים

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

$(N,p,q,d)=(7,3,41,2)$

להכנה בוב בוחר את הפולינומים:

$f(x)=x^{6}-x^{4}+x^{3}+x^{2}-1\in {\mathcal {T}}(3,2)$וכן

$g(x)=x^{6}+x^{4}-x^{2}-x\in {\mathcal {T}}(2,2)$

ומחשב את ההופכיים שלהם:

$f_{q}^{-1}=f(x)^{-1}{\text{ mod }}q=8x^{6}+26x^{5}+31x^{4}+21x^{3}+40x^{2}+2x+37{\text{ (mod }}41)$

$f_{p}^{-1}=f(x)^{-1}{\text{ mod }}p=x^{6}+2x^{5}+x^{3}+x^{2}+x+1{\text{ (mod }}3)$

בוב שומר את$f(x)$ואת ההופכי שלו$f_{q}^{-1}$כמפתח פרטי.

כעת בוב מחשב ומפרסם ברבים את המפתח הציבורי שלו:

$h(x)=f_{q}^{-1}\circledast g(x)=20x^{6}+40x^{5}+2x^{4}+38x^{3}+8x^{2}+26x+30{\text{ (mod }}41)$

נניח שאליס מעוניינת לשלוח לבוב את המסר:$m(x)=-x^{5}+x^{3}+x^{2}-x+1$

תחילה היא בוחרת מספר אקראי נניח:$r(x)=x^{6}-x^{5}+x-1$משתמשת במפתח הציבורי של בוב ומחשבת את:

$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)$

אותו היא שולחת לבוב. כאשר בוב מקבל את$c(x)$הוא פועל כדלהלן. תחילה מחשב את:

$f(x)\circledast c(x)\equiv x^{6}+10x^{5}+33x^{4}+40x^{3}+40x^{2}+x+40{\text{ (mod }}41)$

ואז מבצע מרכוז (Centerlift) של מקדמי התוצאה מודולו$q$ומקבל את:

$a(x)=x^{6}+10x^{5}-8x^{4}-x^{3}-x^{2}+x-1$

לבסוף מצמצם את מקדמי$a(x)$מודולו$p$ומכפיל בהופכי:

$f_{p}^{-1}(x)\circledast a(x)\equiv 2x^{5}+x^{3}+x^{2}+2x+1{\text{ (mod }}3)$

ממרכז (Centerlift) את התוצאה האחרונה מודולו$p$ומקבל את:

$m=-x^{5}+x^{3}+x^{2}-x+1{\text{ (mod }}3)$

שיטות מתקדמות

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

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

ב-2011 הציעו Damien Stehlé ו-Ron Steinfeld גרסה משופרתבשינויים קלים של הצפנה/חתימה דיגיטלית NTRU המוכחת כבטוחה נגדהתקפת מוצפן-נבחרבמסגרתמודל אורקל אקראיאו מודלסיבוכיותסטנדרטי, תחת הנחת הקושי שבפתרון בעיות סריגים (במחשב קלאסי או קוונטי) עם הגבלה לסוג מסוים של סריגים מעלשדה ציקלוטומי.הם הראו שאם בוחרים את הפולינומים הסודיים של המקבל כפונקצייתגאוסייןבדידית אז המפתח הציבורי ייראה מבחינה סטטיסטית אחיד ובלתי ניתן להבחנה מעל הטווח שלה. תכונתאי-הבחנהבהקשר של מפתח ציבורי פירושה קושי בניחוש המפתח הפרטי מתוך המפתח הציבורי.

בתהליך ההכנה של NTRU. המפתח הפרטי הוא שני פולינומים "דלילים" ממעלה הנמוכה מ-$n$עם מקדמים$\{-1,0,1\}$.המפתח הציבורי הוא המנה שלהם בחוג$\mathbb {Z} _{q}[x]/(x^{n}-1)$.בחירת המפתח הפרטי נעשית כפונקציה גאוסיאנית בדידית באופן כזה שסטיית התקן תהיה בערך$q^{1/2}$.השינויים שהוצעו לעומת הגרסה המקורית הם כדלהלן:

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

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

תקנים

NTRU נמצא בתהליך תקינה של שני גופים בינלאומיים:

• תקןIEEE1363.1 שהחל ב-2008.
• תקן X9.98 של ASC X9 (מכון התקנים האמריקני).

בנוסף האלגוריתם הוצע בטיוטתIETFכמועמד לפרוטוקולTLS.ב-2009 הוזכר NTRU על ידיNISTכמועמד אפשרי לאלגוריתם הצפנה אסימטרי פוסט-קוונטי, שיחליף את האלגוריתמים הנוכחיים. במסגרת המאמץ להתכונן לקראת העידן הקוונטיב-NIST מתכוונים לפרסם בסוף 2016 תחרות פתוחהשבה יבחנו הצעות לאלגוריתם פוסט-קוונטי.

יישומים

NTRU זמינה כקוד פתוח תחת רישיון GPL ו-FOSS. בתנאי שכל שימוש בו יהיה זמין גם הוא כקוד פתוח. זאת במטרה להסיר מכשולים ולאפשר למפתחים להטמיע את האלגוריתם מהר ככל האפשר. כמו כן האלגוריתם ניתן לשימוש מסחרי תחת רישיון BSD. כיום ישנם ב-GitHubשני פרויקטי קוד פתוח ב-C וב-Java המיישמים את NTRU; פרויקט NTRUתחת רישיון GPL וספריית NTRUברישיון BSD.

ראו גם

• הצפנת מפתח ציבורי
• חתימה דיגיטלית
• GGH