ויקיפדיה

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

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
שורה 53:
 
==ביטחון==
בעיית התרמיל הכללית נחשבת ל-NP-קשה והיא מהווה מועמדמועמדת טובטובה ל[[פונקציה חד-כיוונית]]. אולם לצורך קריפטוגרפי יש צורך גם ב[[דלת מלכודת]] או דלת צונחת שהיא המידע הנסתר המאפשר למקבל הלגיטימי לפתור את הבעיה בזמן פולינומי. הגרסה הראשונה של הצפנת התרמיל שהסתמכה על תרמיל Super-increasing הכילה כמה חסרונות מהותיים שהעיקרית שבהן היא העובדה שההצפנה מכילה צפיפות נמוכה מדי. במרוצת הזמן הוצעו מספר רב של גרסאות משופרות שנועדו להתמודד עם הבעיות הללו בין היתר על ידי שימוש בתרמילים מרובים או הסתרה של התרמיל באמצעות [[חשבון מודולרי]] ואלגברה ב[[חוג הפולינומים]].
 
ב-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> מוגדרת כדלהלן:
אוחזר מתוך "https://he.wikipedia.org/wiki/הצפנת_תרמיל_גב"