ויקיפדיה

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

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
מ סקריפט החלפות (ממדי, הווקטור)
שורה 1:
'''הצפנת תרמיל''' (Knapsack cryptosystem) היא מערכת [[הצפנה|הצפנת]] [[מפתח ציבורי]] שביטחונה מבוסס על הקושי המשוער שבפתרון [[בעיית תרמיל הגב]] שהיא בעיה [[NP-קשה]]. הצפנת תרמיל הייתה הניסיון הראשון לבסס מערכת הצפנה על בעיה NP-קשה ולמרותואף על פי שהרעיון קיים כבר מאז 1978 רוב המערכות הקיימות שפותחו על בסיס זה נפרצו ולכן אינן בשימוש מעשי כיום, אלא נחקרות לצורך אקדמי בלבד{{הערה|[http://www.dtc.umn.edu/~odlyzko/doc/arch/knapsack.survey.pdf The Rise and Fall of Knapsack Cryptosystems]}}.
 
השיטה הראשונה והמפורסמת ביותר היא [[הצפנת תרמיל של מרקל והלמן]] שפותחה ב-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}} שעדיין לא התגלתה קריפטואנליזה יעילה שלה.
 
העניין בהצפנת התרמיל כיום נובע מהעובדה שהיא נחשבת [[הצפנה פוסט-קוונטית|פוסט-קוונטית]] ולכן תהיה אטרקטיבית במידהאם ותמצאתמצא דרך בטוחה ליישמה. אם תמצא דרך כזו הרי שהמערכת אמורה לספק ביטחון גם לנוכח איום קריפטואנליזה על [[מחשב קוונטי]] כאשר יהיה מעשי. זאת בניגוד לשיטות כמו [[RSA]] ו-[[DSA]] המסתמכות על [[פירוק לגורמים של מספר שלם|בעיית פירוק לגורמים]] ו[[בעיית הלוגריתם הדיסקרטי|לוגריתם דיסקרטי]], אותם ניתן יהיה לשבור בקלות בהינתן מחשב קוונטי באמצעות [[אלגוריתם שור]].
 
בעיית התרמיל קשורה בקשר הדוק עם [[הצפנה מבוססת סריג|סריגים]]. לאחר פרסום אלגוריתם LLL התברר שמערכת הצפנה מבוססת בעיית תרמיל סובלת מבעיה מהותית. באופן כללי אם <math>n\le 300</math> כאשר <math>n</math> הוא פרמטר ביטחון (מפורט בהמשך) אז [[אלגוריתם לצמצום סריגים]] (Lattice reduction algorithm) מאפשר לגלות את הטקסט המקורי מתוך הטקסט המוצפן ללא ידיעת המפתח בזמן פולינומי. מאידך אם <math>n>300</math> אז המפתחות מגיעים למימדיםלממדים עצומים בערך 176KB למפתח מה שהופך את המערכת לבלתי יעילה.
 
==בעיית תרמיל הגב==
שורה 19:
נניח ש-<math>n=6</math> ונתונה הסדרה:
:<math>M=\{2,3,4,9,14,23\}</math> והתרמיל <math>S=27</math>
אפשר לראות ב[[ניסוי וטעייה]] שהפתרון הוא [[תת-סדרה|תת-הסדרה]] <math>\{4,9,14\}</math> וקל לראות שזהו הפתרון היחיד במקרה זה. דרך אחרת להציג את הפתרון היא ה[[מרחב וקטורי|ווקטור]] <math>\mathbf{e}=(0,0,1,1,1,0)</math> (כלומר הוקטורהווקטור מכיל אחדים בכניסות המתאימות לאיברים הנכללים בסכום התרמיל ובכל היתר אפסים) במילים אחרות <math>S=m_2+m_3+m_4</math>.
 
אפשר לפתור את הבעיה ב[[כוח גס]], פשוט על ידי ניסוי כל האפשרויות של הווקטור <math>\mathbf{e}</math> עד למציאת הוקטורהווקטור הנכון. סיבוכיות הפתרון היא מסדר גודל של <math>O(2^n)</math>, אולם אפשר לחתוך את סיבוכיות הפתרון בפקטור של שנים על ידי אלגוריתם ההתנגשות הבא.
 
===אלגוריתם התנגשות לפתרון בעיית התרמיל הכללית===
שורה 34:
 
===סדרה סוּפֶּר-עולה===
בעיקרון אם <math>n</math> גדול הפתרון המתואר אינו יעיל ולכן הבעיה הכללית מוגדרת קשה, אולם אינה מתאימה לקריפטוגרפיה כיוון שלא קיימת דלת מלכודת, אותו מידע סודי שהופך את פתרון הבעיה לקל מאוד למי שמחזיק בו ואילו עבור כל האחרים שאינם יודעים מהו הבעיה נותרת קשה. דרך אחת להכניס דלת מלכודת היא להשתמש בבעיית תרמיל עם תכונה מיוחדת שפתרונה קל. הרעיוןןהרעיון של מרקל והלמן היה להשתמש בתרמיל המורכב מסדרה מונוטונית עולה שבה כל איבר גדול לפחות פי שניים מקודמו. בניסוח רשמי זוהי סדרה של <math>n</math> איברים שלמים <math>r=(r_1,r_2,...,r_n)</math> עם התכונה הבאה:
:<math>r_{i+1}\ge 2r_i</math> עבור כל <math>1\le i\le n-1</math>.
היא נקראת סופר-עולה (superincreasing) כיוון שעבור כל <math>k</math> מתקיים:
שורה 62:
ב-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> מוגדרת כדלהלן:
:<math>d=n/(\log_2\text{ max }a_i)</math>.
אלגוריתם CJLOSS{{הערה|M. J. Coster, A. Joux, B. A. LaMacchia, A. M. Odlyzko, C. P. Schnorr, and J. Stern, Improved low-density subset sum algorithms, Computational Complexity, Vol.2 (1992) pp.111–128.}} משפר את החסם לגריאס-אודליצקו ל-<math>d<0.9408</math>. היות שהאלגוריתמים האמורים מסתמכים על צפיפות התרמיל הם נקראים באופן כללי "התקפת צפיפות נמוכה". אולם הבעיה הכללית, דהיינו אם צפיפות התרמיל גבוהה מהגבול האמור נותרה בעיה קשה. הרעיון של אלגוריתם LO הוא להמיר את הבעיה לבעיה אחרת מ[[הצפנה מבוססת סריג|תורת הסריגים]] הנקראת [[בעיית מציאת הווקטור הקצר ביותר]] (SVP) שהיא כידוע בעיה קשה מאוד. למרותאף על פי שלא קיים אלגוריתם פולינומי ל-SVP, מעשית אלגוריתם LLL של האחים לנסטרה ולובאז' מצליח לפתור את בעיית הווקטור הקצר בקירוב טוב, הרבה יותר ממה שמציע הגבול התאורטי. האמור הוא אם מתבצעת קריאה אחת לאורקל SVP. אולם במקרה של קריאות מרובות קיים שיפור שלו שנקרא אלגוריתם CJLOSS+{{D}} שמשפר את התוצאות האמורות מהיבט [[אסימפטוטי]].
 
==הערות שוליים==
אוחזר מתוך "https://he.wikipedia.org/wiki/הצפנת_תרמיל_גב"