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

תוכן שנמחק תוכן שנוסף
אין תקציר עריכה
שורה 55:
 
==ביטחון==
בעיית התרמיל הכללית נחשבת ל-NP-קשה והיא מהווה מועמדת טובה ל[[פונקציה חד-כיוונית]]. אולם לצורך קריפטוגרפי יש צורך גם ב[[דלת מלכודת]] או דלת צונחת שהיא המידע הנסתר המאפשר למקבל הלגיטימי לפתור את הבעיה בזמן פולינומי. הגרסה הראשונה של הצפנת התרמיל שהסתמכה על סדרה סופר-עולה הכילה כמה חסרונות מהותיים שהעיקרית שבהן היא העובדה שההצפנהשהתרמיל מכילהמכיל צפיפות נמוכה מדי מה שדיוצר נקודת תורפה. במרוצת הזמן הוצעו מספר רב של גרסאות משופרות שנועדו להתמודד עם הבעיות הללו בין היתר על ידי שימוש בתרמילים מרובים או הסתרה של התרמיל באמצעות [[חשבון מודולרי]] ואלגברה ב[[חוג הפולינומים]].
 
ב-1985 פורסם בנפרד על ידי בריקל{{הערה|E. F. Brickell, Breaking iterated knapsacks, Advances in Cryptology: Proceedings of CRYPTO’84 (G. R. Blakley and D. Chaum, eds.), Lecture Notes in Computer Science, Springer-Verlag, New York, 196 (1985) pp.342–358}}, לגריאס ואודליצקו{{הערה|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.}} אלגוריתם LO המסתמך על [[אלגוריתם צמצום סריגים]] (LLL) שמצליח לפתור את הבעיה כמעט תמיד בזמן פולינומי בתנאי שצפיפות התרמיל נמוכה מ-0.6463. צפיפות התרמיל <math>d</math> מוגדרת כדלהלן: