הצפנת תרמיל גב – הבדלי גרסאות

השיטה הראשונה והמפורסמת ביותר היא [[#הצפנת תרמיל של מרקל והלמן|הצפנת תרמיל של מרקל והלמן]] שפותחה ב-1978 על ידי [[רלף מרקל]] ו[[מרטין הלמן]]{{הערה|R. C. Merkle and M. E. Hellman, Hiding information and signatures in trapdoor knapsacks, IEEE Transactions on Information Theory, Vol.24 (1978) pp.525–534.}}. היא הייתה מערכת מפתח ציבורי מהראשונות שפותחו ופורסמה באותה שנה שבה פורסמה [[RSA]]. מערכת זו נפרצה לחלוטין בכמה התקפות מפורסמות שהראשונה שבהן הייתה של [[עדי שמיר|שמיר]]{{הערה|A. Shamir, A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystems, Proc. Crypto’82, LNCS, pp.279–288, Springer-Verlag, Berlin, 1982.}}, אחריו פיתחו [[לאונרד אדלמן|אדלמן]]{{הערה|L. M. Adleman, On breaking the titrated Merkle-Hellman public-key cryptosystem, Plenum Press. Crypto’82, pp.303–308. 1982.}}, [[אנדרו אודליצקו|אודליצקו]] ו[[ג'פרי לגריאס|לגריאס]]{{הערה| J. C. Lagarias, and A. M. Odlyzko, Solving low-density subset sum problems, Journal of the Association for Computing Machinery, Vol.32, No.1 (1985) pp.229–246}} בנפרד [[קריפטואנליזה]] הנקראת '''התקפת צפיפות נמוכה''' לשבירת הצפנת מרקל-הלמן ב[[זמן פולינומי]]. כל הגרסאות שהומצאו מאז כולל גרסת [[בני שור|שור]]-[[רונלד ריבסט|ריבסט]]{{הערה|B. Chor, and R. L. Rivest, A knapsack-type public key cryptosystem based on arithmetic in finite fields, IEEE Transactions on Information Theory, Vol.34, No.5 (1988) pp.901–909.}} המכילה צפיפות גבוהה יחסית (הגדרה בהמשך), נמצאו לא בטוחות וניתנות לשבירה בזמן פולינומי או בזמן שהוא נמוך בהרבה מ[[כוח גס]] עם הפרמטרים שהומלצו על ידי המפתחים. במרבית המקרים שינוי הפרמטרים לא יועיל במידה ניכרת ולכן מערכות אילו לא נכנסו לשימוש מעשי כלל למעט מערכת חדשה יחסית של Nasako-Murakami מ-2006{{הערה|T. Nasako and Y. Murakami, A high-density knapsack cryptosystem using combined trapdoor, the Japan Society for Industrial and Applied Mathematics, Vol.16, No.4, pp.519-605, 2006}} שעדיין לא התגלתה קריפטואנליזה יעילה שלה.

 

 

בעיית התרמיל קשורה בקשר הדוק עם [[הצפנה מבוססת סריג|סריגים]]. לאחר פרסום אלגוריתם LLL התברר שמערכת הצפנה מבוססת בעיית תרמיל סובלת מבעיה מהותית. באופן כללי אם <math>n\le 300</math> כאשר <math>n</math> הוא פרמטר ביטחון (מפורט בהמשך) אז [[אלגוריתם לצמצום סריגים]] (Lattice reduction algorithm) מאפשר לגלות את הטקסט המקורי מתוך הטקסט המוצפן ללא ידיעת המפתח בזמן פולינומי. מאידך אם <math>n>300</math> אז המפתחות מגיעים לממדים עצומים בערך 176KB למפתח מה שהופך את המערכת לבלתי יעילה.