הגרסה המקורית של NTRU כוללת ארבעה פרמטרים בסיסיים formula_7 וכן ארבע קבוצות פולינומים formula_8 ממעלה formula_1 עם מקדמים שלמים המייצגים את טווח המפתח הפרטי והציבורי, טווח האלמנט האקראי וטווח המסר בהתאמה (מפורטים בהמשך). formula_4 הוא מספר ראשוני ונקרא כאן פרמטר ביטחון והוא קובע את רמת הביטחון של המערכת בהתאם לדרישה, formula_11 מציין את מספר המקדמים החיוביים והשליליים (מפורט בהמשך). formula_12 ו-formula_13 נקראים מודולוס ומשמשים לצמצום המקדמים. הם לא חייבים להיות ראשוניים אך נדרש שיתקיים formula_14 (כאשר formula_15 היא פונקציית מכנה משותף מינימלי). וכן formula_13 צריך להיות גדול משמעותית מ-formula_12 למשל formula_18 (אם כי זה לא הכרחי ומסיבות של יעילות רצוי formula_13 פחות גדול). הפעולות של הצופן הן בחוג הפולינומים formula_20. האלמנט formula_21 הוא פולינום המיוצג על ידי הווקטור:
כאן מכפלת שני פולינומים (וקטורים ב-formula_24) מיוצגת על ידי הסימן formula_25. היא נקראת גם קונבולוציה מעגלית והיא מוגדרת כך:
בעיקרון פעולת כפל אלמנטים ב-formula_24 היא בסיבוכיות formula_28 פעולות כפל בסיסיות מודולו formula_13, אם המקדמים קטנים שזה מה שקורה בממוצע, הפעולה תהיה מהירה. אם המקדמים גדולים ייתכן שיהיה יותר מהיר להפעיל את FFT בסיבוכיות זמן של formula_30 פעולות.
לצורך NTRU משתמשים בפולינום טרינארי שהוא פולינום שבו המקדמים formula_31. מייצגים זאת על ידי הסימון formula_32 שפירושו שבפולינום formula_33 בסך הכול formula_34 מקדמים שווים formula_35, בסך הכול formula_36 מקדמים שווים formula_37 והיתר אפס. לדוגמה:
קיים מיפוי טבעי (הומומורפי) בין האלמנטים בחוג formula_24 לבין אלמנטים מהחוג formula_40 (מודולו formula_13) המיפוי הוא פשוט צמצום המקדמים מודולו formula_13. לפעמים דרוש מעבר בכיוון ההפוך, כלומר אם formula_43 הוא פולינום, אפשר לבצע "הגבהה" או "מרכוז" (center lift) שלו כך שיתקבל פולינום formula_44 המקיים formula_45, בוחרים את המקדמים באופן כזה שהם יהיו בטווח:
כלומר אם לאחר צמצום ב-formula_13 מתקבל formula_48 ערכו יהיה formula_49. לדוגמה אם formula_50 ונתון הפולינום formula_51 ה-center lift שלו הוא הפולינום formula_52 כשהמקדמים הם השלמים בטווח formula_53.
תיאור האלגוריתם.
תיאור הפונקציה NTRUencrypt. להכנה המקבל בוב מכין בסוד שני פולינומים טרינאריים formula_54. הפולינום formula_55 חייב להיות הפיך מודולו formula_12 ומודולו formula_13. לכן הוא נבחר בצורה formula_58 (במקרה של &lt;formula_59 לפולינום אף פעם אין הופכי בformula_40). חישוב ההופכי שלו נעשה עם אלגוריתם אוקלידס המורחב. ההופכיים שלו מסומנים כאן formula_61 ו-formula_62 כאשר מתקיים כרגיל:
לאחר מכן בוב מחשב את מכפלת הפולינומים: formula_64.
המפתח הציבורי של בוב הוא formula_65 אותו הוא שולח לאליס בערוץ פתוח כלשהו (כמו בכל מערכת הצפנה חלה החובה לאמתו). המפתח הפרטי הוא הפולינום formula_55 (וכן ההופכיים שלו כאמור) והוא נשמר בסוד. הפולינום formula_67 אינו נחוץ להצפנה ופענוח ולכן יש להשמידו.
הצפנה.
אם אליס רוצה להצפין עבור בוב את המסר formula_68. (כלומר המסר צריך להיות ממופה לפולינום טרינארי מהקבוצה formula_69 בדרך גלויה ומוסכמת על כל הצדדים). היא בוחרת פולינום אקראי חד-פעמי formula_70 המשמש להסתרת המסר ומשתמשת במפתח הציבורי של בוב כדי לחשב את:
ושולחת את formula_72 לבוב.
פענוח.
לפענוח בוב משתמש במפתח הפרטי שלו formula_55 וההופכי שלו כדי לחשב את:
המקבל משנה את המקדמים של formula_75 כך שיהיו בטווח formula_76 פעולה זו נקראת center-lift. כעת אם מתייחסים ל-formula_75 כאל פולינום עם מקדמים שלמים בוב יכול לחלץ את המסר על ידי:
הפענוח יצליח בהסתברות גבוהה מאוד, אם כי פרמטרים מסוימים עלולים לגרום בסבירות זניחה לכישלון בפענוח. מקרה זה נגרם כתוצאה מכך שהמסר אינו ממורכז כראוי, אפשר לנסות שוב עם מקדמים בהיסט קל מהטווח האמור למשל בין formula_79 ל-formula_80 עבור formula_81 קטן כלשהו ואם גם זה נכשל לא ניתן לפענח את המסר כלל. כאמור אירוע כזה זניח ואפשר להתעלם ממנו בפועל. הוכחה לנכונות הפענוח היא:
בבחירת פרמטרים נכונה מקדמי הפולינום האחרון כמעט תמיד בטווח formula_76 ולכן אינו משתנה כשמצמצמים מודולו formula_13. המשמעות היא שכאשר בוב מצמצם את המקדמים של formula_84 מודולו formula_13 הוא מקבל את הפולינום formula_86 בחוג formula_87 וכאשר הוא מצמצם את המקדמים של formula_75 מודולו formula_12 הוא מבטל את formula_90 ומקבל את הפולינום formula_91 אותו הוא יכול להכפיל ב-formula_61 כדי לחלץ את formula_93.
חתימה דיגיטלית.
הרעיון של האלגוריתם NTRUsign הוא שהחתימה היא הוכחה שהחותם יכול פתור את בעיית הווקטור הקצר ביותר (SVP) בסריג NTRU של הנקודה המיוצגת על ידי המסמך או תמצית שלו. המפתח הפרטי (מפתח החתימה) שלו הוא בסיס קצר של הסריג NTRU והמפתח הציבורי (מפתח האימות) הוא בסיס הרבה יותר ארוך. המוודא יכול בקלות לראות שאכן החתימה היא באמת וקטור קרוב ביותר למסמך. אך עם המפתח הציבורי המוודא אינו יכול בעצמו או שזה קשה מאוד עבורו למצוא וקטור קרוב.
מאז המצאתו והצגתו ביורוקריפט 2001, אלגוריתם החתימה NTRUSign סובל מהיסטוריה של בעיות וכשלים רבים ובוצעו מספר תיקונים ותוספות טלאים. תחילה גילו Craig Gentry ו-Mike Szydlo בגרסה המקורית תקלה חמורה, עותקים של החתימה הדיגיטלית חושפים מידע לגבי המפתח הפרטי. המפתחים תקנו את הבעיה ופרסמו אלגוריתם משופר וכן הצעה לתקן R-NSS. ב-2006 פרסמו עודד רגב ו-Phong Nguyen
קריפטואנליזה של חתימת NTRU המאפשרת לחשוף את המפתח הפרטי בזמן מאוד קצר תוך שימוש ב-400 חתימות בלבד. הפתרון שהוצע היה "הסטה" (perturbation) כלומר החותם מסיט את הנקודה המייצגת את המסר על ידי וקטור סודי קצר. שוב נמצא שהתיקון לא שיפר בהרבה את המצב, בהתקפה שפורסמה אפשר לחשוף את המפתח הפרטי עם 300,000 חתימות בלבד. נכון לשנת 2016 לא ברור אם האלגוריתם ראוי לשימוש במתכונתו הנוכחית למרות התיקונים והטלאים שנוספו.
תיאור האלגוריתם.
תחילה החותם בוב בוחר פרמטרים מתאימים formula_94 באופן כזה שבעיית הווקטור הקצר תהיה קשה לפתרון בסריג בעל מימד formula_95 מודולו formula_13. כמפתח הסודי הוא בוחר שני פולינומים טרינאריים formula_97 ו-formula_98 מהצורה formula_99 ומחשב את המפתח הציבורי formula_100 בדיוק כמו בתהליך ההכנה של הצפנת NTRU. את formula_101 הוא שולח כמפתח אימות לאליס ושומר בסוד את כל היתר.
כדי לחתום על מסמך formula_102 (המסמך מחולק לשני פולינומים שווים), תחילה באמצעות אלגוריתם אוקלידס המורחב מחשב שני פולינומים נוספים formula_103 שנקראים "חצי בסיס משלים" לסריג NTRU כך שמתקיים formula_104. ומחשב את שני הווקטורים:
כאשר הסימון formula_107 מייצג פולינום עם מקדמים המעוגלים לשלם הקרוב ביותר. החתימה של בוב על המסמך formula_108 היא: formula_109. את החתימה והמסמך formula_110 הוא שולח לאליס.
המקבלת אליס המעוניינת לוודא את חתימתו של בוב משתמשת במפתח הציבורי שלו formula_101 כדי לחשב את:
היא בוחרת את המקדמים שלו מודולו formula_13 כך שיהיו קרובים ככל האפשר למקדמים המקבילים של המסמך formula_108 ומוודא שהווקטור formula_115 אכן קרוב למסמך formula_116 (כאמור קל לוודא זאת אך קשה למצוא וקטור כזה, מסיבה זו אליס עצמה או כל אחד אחר לא יוכל לחתום על המסמך מבלי שהדבר יתגלה כתרמית ללא המפתח הפרטי המתאים, כיוון שבהסתברות גבוהה מאוד התוצאה תהיה וקטור רחוק למדי).
ביטחון.
בחירת פרמטרים.
המפתחים הציעו שלוש קונפיגורציות של פרמטרים המציעות דרגות שונות של ביטחון מהקל אל הכבד:
אופציה 1. ביטחון נמוך המתאים למסרים בעלי חשיבות נמוכה או כאשר המפתחות מוחלפים בתדירות גובהה, כמו בהצפנת שיחה אלחוטית או ממיר טלוויזיה.
formula_147. הפולינום formula_148 פירושו פולינום טרינארי שמכיל 15 מקדמים חיוביים (formula_35) ו-14 מקדמים שליליים (formula_37).
המפתח הפרטי הוא באורך 340 סיביות והמפתח הציבורי באורך 642 סיביות. דרגת ביטחון של המפתח היא formula_151.
אופציה 2. ביטחון בינוני.
formula_152
המפתח הפרטי באורך 530 סיביות והציבורי 1169 סיביות. רמת ביטחון של formula_153.
אופציה 3. ביטחון גבוה.
formula_154
אורך מפתח פרטי 1595 סיביות וציבורי 4024 סיביות. רמת ביטחון של formula_155.
דוגמה במספרים קטנים.
הדוגמה הבאה ממחישה את הצפנת NTRU במספרים קטנים. כמובן שבפועל מערכת כזו צריכה להיות בקנה מידה הרבה יותר גדול כדי שתהיה בטוחה. נניח שהפרמטרים של המערכת הם:
להכנה בוב בוחר את הפולינומים:
ומחשב את ההופכיים שלהם:
בוב שומר את formula_97 ואת ההופכי שלו formula_62 כמפתח פרטי.
כעת בוב מחשב ומפרסם ברבים את המפתח הציבורי שלו:
נניח שאליס מעוניינת לשלוח לבוב את המסר: formula_164
תחילה היא בוחרת מספר אקראי נניח: formula_165 משתמשת במפתח הציבורי של בוב ומחשבת את:
אותו היא שולחת לבוב. כאשר בוב מקבל את formula_167 הוא פועל כדלהלן. תחילה מחשב את:
ואז מבצע מרכוז (Centerlift) של מקדמי התוצאה מודולו formula_13 ומקבל את:
לבסוף מצמצם את מקדמי formula_171 מודולו formula_12 ומכפיל בהופכי:
ממרכז (Centerlift) את התוצאה האחרונה מודולו formula_12 ומקבל את:
שיטות מתקדמות.