הצפנת תרמיל גב

הצפנת תרמיל גב (באנגלית: Knapsack cryptosystem) היא מערכת הצפנת מפתח ציבורי שביטחונה מבוסס על הקושי המשוער שבפתרון בעיית תרמיל הגב שהיא בעיה NP-קשה. הצפנת תרמיל הגב הייתה הניסיון הראשון לבסס מערכת הצפנה על בעיה NP-קשה ואף על פי שהרעיון קיים כבר מאז 1978 רוב המערכות הקיימות שפותחו על בסיס זה נפרצו ולכן אינן בשימוש מעשי, אלא נחקרות לצורך אקדמי בלבד^[1].

השיטה הראשונה והמפורסמת ביותר היא הצפנת תרמיל גב של מרקל והלמן שפותחה ב-1978 על ידי רלף מרקל ומרטין הלמן^[2]. היא הייתה מערכת מפתח ציבורי מהראשונות שפותחו ופורסמה באותה שנה שבה פורסמה RSA. מערכת זו נפרצה לחלוטין בכמה התקפות מפורסמות שהראשונה שבהן הייתה של שמיר^[3], אחריו פיתחו אדלמן^[4], אודליצקו ולגריאס^[5] בנפרד קריפטואנליזה הנקראת התקפת צפיפות נמוכה לשבירת הצפנת מרקל-הלמן בזמן פולינומי. כל הגרסאות שהומצאו מאז כולל גרסת שור-ריבסט^[6] המכילה צפיפות גבוהה יחסית (הגדרה בהמשך), נמצאו לא בטוחות וניתנות לשבירה בזמן פולינומי או בזמן שהוא נמוך בהרבה מכוח גס עם הפרמטרים שהומלצו על ידי המפתחים. במרבית המקרים שינוי הפרמטרים לא יועיל במידה ניכרת ולכן מערכות אילו לא נכנסו לשימוש מעשי כלל למעט מערכת חדשה יחסית של Nasako-Murakami מ-2006^[7] שעדיין לא התגלתה קריפטואנליזה יעילה שלה.

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

בעיית תרמיל הגב קשורה בקשר הדוק עם סריגים. לאחר פרסום אלגוריתם LLL התברר שמערכת הצפנה מבוססת בעיית תרמיל הגב סובלת מבעיה מהותית. באופן כללי אם ${\displaystyle n\leq 300}$ כאשר ${\displaystyle n}$ הוא פרמטר ביטחון (מפורט בהמשך) אז אלגוריתם לצמצום סריגים (Lattice reduction algorithm) מאפשר לגלות את הטקסט המקורי מתוך הטקסט המוצפן ללא ידיעת המפתח בזמן פולינומי. מאידך אם ${\displaystyle n>300}$ אז המפתחות מגיעים לממדים עצומים בערך 176KB למפתח מה שהופך את המערכת לבלתי יעילה.

ערך מורחב – בעיית תרמיל הגב

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

נתונה הסדרה ${\displaystyle A}$ המכילה ${\displaystyle n}$ איברים שלמים, כאשר ${\displaystyle n}$ הוא פרמטר ביטחון (למשל ${\displaystyle n=300}$):

${\displaystyle A=\{a_{1},a_{2},...,a_{n}\}}$

ונתון שלם חיובי ${\displaystyle S}$ הנקרא 'תרמיל גב'. הבעיה היא לגלות האם קיימת תת-קבוצה של איברים ב-${\displaystyle A}$ שסכומה הוא ${\displaystyle S}$. במילים אחרות המטרה היא לגלות את הווקטור ${\displaystyle \mathbf {e} =(e_{1},e_{2},...,e_{n})\in \{0,1\}^{n}}$ המקיים:

${\displaystyle \sum _{i=1}^{n}a_{i}e_{i}=S}$.

נניח ש-${\displaystyle n=6}$ ונתונה הסדרה:

${\displaystyle M=\{2,3,4,9,14,23\}}$ ותרמיל הגב ${\displaystyle S=27}$

אפשר לראות בניסוי וטעייה שהפתרון הוא תת-הסדרה ${\displaystyle \{4,9,14\}}$ וקל לראות שזהו הפתרון היחיד במקרה זה. דרך אחרת להציג את הפתרון היא הווקטור ${\displaystyle \mathbf {e} =(0,0,1,1,1,0)}$ (כלומר הווקטור מכיל אחדים בכניסות המתאימות לאיברים הנכללים בסכום התרמיל ובכל היתר אפסים) במילים אחרות, אם ממספרים את כל האיברים בסדרה משמאל לימין ${\displaystyle M=\{m_{1},m_{2},m_{3},m_{4},m_{5},m_{6}\}}$ אז ${\displaystyle S=m_{3}+m_{4}+m_{5}}$.

אפשר לפתור את הבעיה בכוח גס, פשוט על ידי ניסוי כל האפשרויות של הווקטור ${\displaystyle \mathbf {e} }$ עד למציאת הווקטור הנכון. סיבוכיות הפתרון היא מסדר גודל של ${\displaystyle O(2^{n})}$, אולם אפשר לחתוך את סיבוכיות הפתרון בפקטור של שנים על ידי אלגוריתם ההתנגשות הבא.

אם נתונה בעיית תרמיל-גב עם הפרמטרים ${\displaystyle M=(m_{1},m_{2},...,m_{n})}$ באורך ${\displaystyle n}$ ושלם ${\displaystyle S}$ אפשר לפעול כדלהלן:

• מכינים קבוצת שלמים ${\displaystyle I}$ כך שמתקיים ${\displaystyle \textstyle I\subset \{i:1\leq i\leq {\frac {1}{2}}n\}}$, כלומר קבוצת כל האיברים הנמוכים מחצי של ${\displaystyle n}$ וכן,
• מכינים קבוצת שלמים ${\displaystyle J}$ כך שמתקיים ${\displaystyle \textstyle J\subset \{j:{\frac {1}{2}}n<j\leq n\}}$,
• מחשבים את רשימת הערכים הבאים: ${\displaystyle \textstyle A_{I}=\sum _{i\in I}M_{i}}$ כלומר רשימת כל הסכומים האפשריים ב-${\displaystyle I}$,
• באותו אופן מחשבים את רשימת הערכים: ${\displaystyle \textstyle B_{J}=S-\sum _{j\in J}M_{j}}$,
• ממיינים את הקבוצות לפי סדר מספרי ומחפשים התאמה כך שתתקבלנה שתי תת-רשימות ${\displaystyle I_{0}}$ ו-${\displaystyle J_{0}}$ המקיימות: ${\displaystyle A_{I_{0}}=B_{J_{0}}}$. רשימות אילו נותנות למעשה את הפתרון לבעיית תרמיל הגב כי

${\displaystyle S=\sum _{i\in I_{0}}M_{i}+\sum _{j\in J_{0}}M_{j}}$.

מספר האלמנטים ב-${\displaystyle I}$ וב-${\displaystyle J}$ הוא לכל היותר ${\displaystyle 2^{n/2}}$ כל אחת ולכן זמן הריצה של האלגוריתם הוא ${\displaystyle O(2^{n/2+\epsilon })}$ כאשר ${\displaystyle \epsilon }$ הוא ערך קטן המייצג את התקורה הנוספת הנובעת מחישוב הרשימות ומיונן.

בעיקרון אם ${\displaystyle n}$ גדול הפתרון המתואר אינו יעיל ולכן הבעיה הכללית מוגדרת קשה, אולם אינה מתאימה לקריפטוגרפיה כיוון שלא קיימת "דלת צונחת", אותו מידע סודי שהופך את פתרון הבעיה לקל מאוד למי שמחזיק בו ואילו עבור כל האחרים שאינם יודעים מהו הבעיה נותרת קשה. דרך אחת להכניס דלת צונחת היא להשתמש בבעיית תרמיל הגב עם תכונה מיוחדת שפתרונה קל. הרעיון של מרקל והלמן היה להשתמש בתרמיל גב המורכב מסדרה מונוטונית עולה שבה כל איבר גדול לפחות פי שניים מקודמו. בניסוח רשמי זוהי סדרה של ${\displaystyle n}$ איברים שלמים ${\displaystyle r=(r_{1},r_{2},...,r_{n})}$ עם התכונה הבאה:

${\displaystyle r_{i+1}\geq 2r_{i}}$ עבור כל ${\displaystyle 1\leq i\leq n-1}$.

היא נקראת סופר-עולה (superincreasing) כיוון שעבור כל ${\displaystyle k}$ מתקיים:

${\displaystyle r_{k+1}\geq 2r_{k}}$ או ${\displaystyle r_{k}+r_{k}>r_{k}+(r_{k-1}+\cdots r_{2}+r_{1})}$.

במקרה זה פתרון בעיית תרמיל הגב קל מאוד לפי האלגוריתם הבא: מבצעים רקורסיה שמתחילה באיבר האחרון (${\displaystyle M_{n}}$) כלפי מטה עד האיבר הראשון (${\displaystyle M_{1}}$) ובודקים עבור כל ${\displaystyle M_{i}}$: אם ${\displaystyle S\geq M_{i}}$ מציבים ${\displaystyle x_{i}=1}$ ומחסרים ${\displaystyle S=S-M_{i}}$ אחרת מציבים ${\displaystyle x_{i}=0}$ וממשיכים עד ש-${\displaystyle S=0}$ (בהנחה שפתרון קיים).

לדוגמה הסדרה ${\displaystyle M=(3,11,24,50,115)}$ היא סופר עולה, נניח שנתון השלם ${\displaystyle S=142}$ מייצגים את ${\displaystyle S}$ כסכום איברים בסדרה ${\displaystyle M}$ כדלהלן: תחילה היות ש-${\displaystyle S\geq 115}$ לכן ${\displaystyle x_{5}=1}$ ומחליפים את ${\displaystyle S}$ ב-${\displaystyle S-115=27}$. בשלב הבא היות ש-${\displaystyle 27<50}$ מציבים ${\displaystyle x_{4}=0}$. בשלב הבא רואים ש-${\displaystyle S=27>24}$ לכן ${\displaystyle x_{3}=1}$ ו-${\displaystyle S=S-24=3}$. היות ש-${\displaystyle 3<11}$ אנחנו יודעים ש-${\displaystyle x_{2}=0}$ ולבסוף ${\displaystyle x_{1}=1}$ כי ${\displaystyle 3\geq 3}$ ועוצרים כי ${\displaystyle S=S-3=0}$. לסיכום, הפתרון הוא

${\displaystyle S=1\cdot 3+0\cdot 11+1\cdot 24+0\cdot 50+1\cdot 115=142}$

מרקל והלמן הציעו ב-1978 מערכת הצפנה המבוססת על בעיית תרמיל הגב עם סדרה סופר עולה שאותה מסתירים באמצעות שקילויות. כדי לייצר מפתח פרטי ומפתח ציבורי אליס בוחרת סדרה סופר עולה בעלת ${\displaystyle n}$ איברים ${\displaystyle r=(r_{1},r_{2},...,r_{n})}$ כך שעבור כל ${\displaystyle 1<i\leq n}$ מתקיים ${\displaystyle r_{i}\geq 2r_{i-1}}$ וכן בוחרת שני שלמים גדולים ${\displaystyle A}$ ו-${\displaystyle B}$ המקיימים:

${\displaystyle B>2r_{n}}$ וכן ${\displaystyle {\text{gcd}}(A,B)=1}$ כאשר ${\displaystyle {\text{gcd}}}$ היא פונקציית מחלק משותף מקסימלי, בדרך זו מובטח של-${\displaystyle A}$ יהיה הופכי כפלי מודולו ${\displaystyle B}$.

אליס מכינה סדרה ${\displaystyle M}$ שאינה סופר עולה על ידי הכפלה ב-${\displaystyle A}$ כך:

${\displaystyle M_{i}\equiv Ar_{i}({\text{ mod }}B)}$ כאשר ${\displaystyle 0\leq M_{i}<B}$.

הסדרה ${\displaystyle M}$ היא המפתח הציבורי של אליס שהוסתר על ידי הכפל ב-${\displaystyle A}$ מודולו ${\displaystyle B}$ ואילו המפתח הסודי כולל את הסדרה ${\displaystyle r}$ והשלמים ${\displaystyle A}$ ו-${\displaystyle B}$ בגלל החשבון המודולרי לא קל לנחש את ${\displaystyle A}$ או ${\displaystyle B}$ מתוך המפתח הציבורי. אם בוב רוצה להצפין את המסר ${\displaystyle x}$ עבור אליס הוא משתמש במפתח הציבורי שלה ומחשב את

${\displaystyle S=x\cdot M=\sum _{i=1}^{n}x_{i}M_{i}}$.

את הטקסט המוצפן ${\displaystyle S}$ הוא שולח לאליס. לפענוח אליס פועלת כדלהלן, תחילה מחשבת את ${\displaystyle S'\equiv A^{-1}S({\text{ mod }}B)}$ דהיינו מכפילה את ${\displaystyle S}$ בהופכי הכפלי של ${\displaystyle A}$ מודולו ${\displaystyle B}$ ואז משתמשת בסדרה הסופר עולה ${\displaystyle r}$ כדי לפתור את בעיית תרמיל הגב עם ${\displaystyle S'}$. הסיבה שהפענוח נכון היא בשל הזהות הבאה:

${\displaystyle S'\equiv A^{-1}S\equiv A^{-1}\sum _{i=1}^{n}x_{i}M_{i}\equiv A^{-1}\sum _{i=1}^{n}x_{i}Ar_{i}\equiv \sum _{i=1}^{n}x_{i}r_{i}{\text{ (mod }}B)}$.

היות ש-${\displaystyle S'<B}$ מובטח לאליס שתקבל תוצאה מדויקת ולא רק שקילות כלשהי מודולו ${\displaystyle B}$.

נניח שאליס בחרה סדרה סופר-עולה סודית מהדוגמה הקודמת ${\displaystyle r=(3,11,24,50,115)}$ וכן ${\displaystyle A=113,B=250}$. כעת הסדרה המוסוות שלה ${\displaystyle M}$ תהיה הכפלה של ${\displaystyle r}$ ב-${\displaystyle A}$ כך שמתקבל:

${\displaystyle M\equiv (113\cdot 3,113\cdot 11,113\cdot 24,113\cdot 50,113\cdot 115){\text{ (mod }}250)}$

${\displaystyle =(89,243,212,150,245)}$.

שימו לב שגם אם ממיינים את איברי M בסדר עולה הסדרה שהתקבלה רחוקה מלהיות סופר-עולה ולכן יהיה קשה לפתור את בעיית תרמיל הגב בסדרה זו לעומת הסדרה ${\displaystyle r}$. כעת אם בוב מעוניין לשלוח לאליס את המסר ${\displaystyle x=(1,0,1,0,1)}$, הוא מצפין אותו תחילה באמצעות הכפלה ב-${\displaystyle M}$ כך שמתקבל:

${\displaystyle S=x\cdot M=1\cdot 89+0\cdot 243+1\cdot 212+0\cdot 150+1\cdot 245=546}$.

ושולח לאליס את ${\displaystyle S=546}$. כאשר אליס מקבלת את הטקסט המוצפן ${\displaystyle S}$ היא מכפילה אותו תחילה בהופכי של ${\displaystyle 113}$ מודולו ${\displaystyle 250}$ שהוא ${\displaystyle A^{-1}=177}$ ומתקבל:

${\displaystyle S'\equiv 177\cdot 546=142{\text{ (mod }}250)}$.

כעת נותר לאליס להשתמש באלגוריתם המתואר לעיל כדי לפתור את בעיית תרמיל הגב בסדרה ${\displaystyle r}$ עם הערך ${\displaystyle S'=x\cdot r=142}$ וכך מחלצת את הטקסט המקורי ${\displaystyle x}$.

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

ב-1985 פורסם בנפרד על ידי בריקל^[8], לגריאס ואודליצקו^[9] אלגוריתם LO המסתמך על אלגוריתם צמצום סריגים (LLL) שמצליח לפתור את הבעיה כמעט תמיד בזמן פולינומי בתנאי שצפיפות תרמיל הגב נמוכה מ-0.6463. צפיפות תרמיל הגב ${\displaystyle d}$ מוגדרת כדלהלן:

${\displaystyle d=n/(\log _{2}{\text{ max }}a_{i})}$.

אלגוריתם CJLOSS^[10] משפר את החסם לגריאס-אודליצקו ל-${\displaystyle d<0.9408}$. היות שהאלגוריתמים האמורים מסתמכים על צפיפות תרמיל הגב הם נקראים באופן כללי "התקפת צפיפות נמוכה". אולם הבעיה הכללית, דהיינו אם צפיפות תרמיל הגב גבוהה מהגבול האמור נותרה בעיה קשה. הרעיון של אלגוריתם LO הוא להמיר את הבעיה לבעיה אחרת מתורת הסריגים הנקראת בעיית מציאת הווקטור הקצר ביותר (SVP) שהיא בעיה קשה מאוד. אף על פי שלא קיים אלגוריתם פולינומי ל-SVP, מעשית אלגוריתם LLL של האחים לנסטרה ולובאז' מצליח לפתור את בעיית הווקטור הקצר בקירוב טוב, הרבה יותר ממה שמציע הגבול התאורטי. האמור הוא אם מתבצעת קריאה אחת לאורקל SVP. אולם במקרה של קריאות מרובות קיים שיפור שלו שנקרא אלגוריתם CJLOSS+‎ שמשפר את התוצאות האמורות מהיבט אסימפטוטי.