הצפנת תרמיל גב
ויקיפדיה האנציקלופדיה encyclopedia
הצפנת תרמיל גב (באנגלית: Knapsack cryptosystem) היא מערכת הצפנת מפתח ציבורי שביטחונה מבוסס על הקושי המשוער שבפתרון בעיית תרמיל הגב שהיא בעיה NP-קשה. הצפנת תרמיל הגב הייתה הניסיון הראשון לבסס מערכת הצפנה על בעיה NP-קשה ואף על פי שהרעיון קיים כבר מאז 1978 רוב המערכות הקיימות שפותחו על בסיס זה נפרצו ולכן אינן בשימוש מעשי, אלא נחקרות לצורך אקדמי בלבד[1].
השיטה הראשונה והמפורסמת ביותר היא הצפנת תרמיל גב של מרקל והלמן שפותחה ב-1978 על ידי רלף מרקל ומרטין הלמן[2]. היא הייתה מערכת מפתח ציבורי מהראשונות שפותחו ופורסמה באותה שנה שבה פורסמה RSA. מערכת זו נפרצה לחלוטין בכמה התקפות מפורסמות שהראשונה שבהן הייתה של שמיר[3], אחריו פיתחו אדלמן[4], אודליצקו ולגריאס[5] בנפרד קריפטואנליזה הנקראת התקפת צפיפות נמוכה לשבירת הצפנת מרקל-הלמן בזמן פולינומי. כל הגרסאות שהומצאו מאז כולל גרסת שור-ריבסט[6] המכילה צפיפות גבוהה יחסית (הגדרה בהמשך), נמצאו לא בטוחות וניתנות לשבירה בזמן פולינומי או בזמן שהוא נמוך בהרבה מכוח גס עם הפרמטרים שהומלצו על ידי המפתחים. במרבית המקרים שינוי הפרמטרים לא יועיל במידה ניכרת ולכן מערכות אילו לא נכנסו לשימוש מעשי כלל למעט מערכת חדשה יחסית של Nasako-Murakami מ-2006[7] שעדיין לא התגלתה קריפטואנליזה יעילה שלה.
העניין בהצפנת תרמיל הגב נובע מהעובדה שהיא נחשבת פוסט-קוונטית ולכן תהיה אטרקטיבית אם תמצא דרך בטוחה ליישמה. אם תמצא דרך כזו הרי שהמערכת אמורה לספק ביטחון גם לנוכח איום קריפטואנליזה על מחשב קוונטי כאשר יהיה מעשי. זאת בניגוד לשיטות כמו RSA ו-DSA המסתמכות על בעיית פירוק לגורמים ובעיית הלוגריתם הבדיד, אותם ניתן יהיה לשבור בקלות בהינתן מחשב קוונטי באמצעות אלגוריתם שור.
בעיית תרמיל הגב קשורה בקשר הדוק עם סריגים. לאחר פרסום אלגוריתם LLL התברר שמערכת הצפנה מבוססת בעיית תרמיל הגב סובלת מבעיה מהותית. באופן כללי אם כאשר הוא פרמטר ביטחון (מפורט בהמשך) אז אלגוריתם לצמצום סריגים (Lattice reduction algorithm) מאפשר לגלות את הטקסט המקורי מתוך הטקסט המוצפן ללא ידיעת המפתח בזמן פולינומי. מאידך אם אז המפתחות מגיעים לממדים עצומים בערך 176KB למפתח מה שהופך את המערכת לבלתי יעילה.