הצגת המקור של הדף "הצפנת תרמיל גב"

'''הצפנת תרמיל גב''' (באנגלית: 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]] ו-[[Digital Signature Algorithm|DSA]] המסתמכות על [[פירוק לגורמים של מספר שלם|בעיית פירוק לגורמים]] ו[[בעיית הלוגריתם הבדיד]], אותם ניתן יהיה לשבור בקלות בהינתן מחשב קוונטי באמצעות [[אלגוריתם שור]].

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

==בעיית תרמיל הגב==
{{הפניה לערך מורחב|בעיית תרמיל הגב}}
בעיית תרמיל הגב הנקראת גם [[בעיית הסכומים החלקיים]] - מהיבט קריפטוגרפי מוגדרת כדלהלן:

נתונה ה[[סדרה (מתמטיקה)|סדרה]] <math>A</math> המכילה <math>n</math> איברים שלמים, כאשר <math>n</math> הוא פרמטר ביטחון (למשל <math>n=300</math>):
:<math>A=\{a_1,a_2,...,a_n\}</math>
ונתון שלם חיובי <math>S</math> הנקרא 'תרמיל גב'. הבעיה היא לגלות האם קיימת תת-קבוצה של איברים ב-<math>A</math> שסכומה הוא <math>S</math>. במילים אחרות המטרה היא לגלות את ה[[וקטור (אלגברה)|ווקטור]] <math>\mathbf{e}=(e_1,e_2,...,e_n)\in \{0,1\}^n</math> המקיים:
:<math>\sum_{i=1}^n a_ie_i=S</math>.

===דוגמה במספרים קטנים===
נניח ש-<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>M=\{m_1,m_2,m_3,m_4,m_5,m_6\}</math> אז <math>S=m_3+m_4+m_5</math>.

אפשר לפתור את הבעיה ב[[כוח גס]], פשוט על ידי ניסוי כל האפשרויות של הווקטור <math>\mathbf{e}</math> עד למציאת הווקטור הנכון. סיבוכיות הפתרון היא מסדר גודל של <math>O(2^n)</math>, אולם אפשר לחתוך את סיבוכיות הפתרון בפקטור של שנים על ידי אלגוריתם ההתנגשות הבא.

===אלגוריתם התנגשות לפתרון בעיית תרמיל הגב הכללית===
אם נתונה בעיית תרמיל-גב עם הפרמטרים <math>M=(m_1,m_2,...,m_n)</math> באורך <math>n</math> ושלם <math>S</math> אפשר לפעול כדלהלן:
*מכינים קבוצת שלמים <math>I</math> כך שמתקיים <math>\textstyle I\subset\{i:1\le i\le \frac{1}{2}n\}</math>, כלומר קבוצת כל האיברים הנמוכים מחצי של <math>n</math> וכן,
*מכינים קבוצת שלמים <math>J</math> כך שמתקיים <math>\textstyle J\subset\{j:\frac{1}{2}n< j \le n\}</math>,
*מחשבים את רשימת הערכים הבאים: <math>\textstyle A_I=\sum_{i\in I} M_i</math> כלומר רשימת כל הסכומים האפשריים ב-<math>I</math>,
*באותו אופן מחשבים את רשימת הערכים: <math>\textstyle B_J=S-\sum_{j\in J} M_j</math>,
*ממיינים את הקבוצות לפי סדר מספרי ומחפשים התאמה כך שתתקבלנה שתי תת-רשימות <math>I_0</math> ו-<math>J_0</math> המקיימות: <math>A_{I_0}=B_{J_0}</math>. רשימות אילו נותנות למעשה את הפתרון לבעיית תרמיל הגב כי 
:<math>S=\sum_{i\in I_0}M_i+\sum_{j\in J_0} M_j</math>.
מספר האלמנטים ב-<math>I</math> וב-<math>J</math> הוא לכל היותר <math>2^{n/2}</math> כל אחת ולכן זמן הריצה של האלגוריתם הוא <math>O(2^{n/2+\epsilon})</math> כאשר <math>\epsilon</math> הוא ערך קטן המייצג את התקורה הנוספת הנובעת מחישוב הרשימות ומיונן.

===סדרה סוּפֶּר-עולה===
בעיקרון אם <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> מתקיים:
:<math>r_{k+1}\ge 2r_k</math> או <math>r_k+r_k>r_k+(r_{k-1}+\cdots r_2+r_1)</math>. 

במקרה זה פתרון בעיית תרמיל הגב קל מאוד לפי האלגוריתם הבא: מבצעים [[רקורסיה]] שמתחילה באיבר האחרון (<math>M_n</math>) כלפי מטה עד האיבר הראשון (<math>M_1</math>) ובודקים עבור כל <math>M_i</math>: אם <math>S\ge M_i</math> מציבים <math>x_i=1</math> ומחסרים <math>S=S-M_i</math> אחרת מציבים <math>x_i=0</math> וממשיכים עד ש-<math>S=0</math> (בהנחה שפתרון קיים).

לדוגמה הסדרה <math>M=(3,11,24,50,115)</math> היא סופר עולה, נניח שנתון השלם <math>S=142</math> מייצגים את <math>S</math> כסכום איברים בסדרה <math>M</math> כדלהלן: תחילה היות ש-<math>S\ge 115</math> לכן <math>x_5=1</math> ומחליפים את <math>S</math> ב-<math>S-115=27</math>. בשלב הבא היות ש-<math>27<50</math> מציבים <math>x_4=0</math>. בשלב הבא רואים ש-<math>S=27>24</math> לכן <math>x_3=1</math> ו-<math>S=S-24=3</math>. היות ש-<math>3<11</math> אנחנו יודעים ש-<math>x_2=0</math> ולבסוף <math>x_1=1</math> כי <math>3\ge3</math> ועוצרים כי <math>S=S-3=0</math>. לסיכום, הפתרון הוא
:<math>S=1\cdot 3 + 0\cdot 11+ 1\cdot 24+ 0 \cdot 50 + 1\cdot 115=142</math>

===הצפנת תרמיל גב של מרקל והלמן===
{{הפניה לערך מורחב|הצפנת תרמיל גב של מרקל והלמן}}
מרקל והלמן הציעו ב-1978 מערכת הצפנה המבוססת על בעיית תרמיל הגב עם סדרה סופר עולה שאותה מסתירים באמצעות [[יחס שקילות|שקילויות]]. כדי לייצר מפתח פרטי ומפתח ציבורי אליס בוחרת סדרה סופר עולה בעלת <math>n</math> איברים <math>r=(r_1,r_2,...,r_n)</math> כך שעבור כל <math>1 < i \le n</math> מתקיים <math>r_i\ge 2r_{i-1}</math> וכן בוחרת שני שלמים גדולים <math>A</math> ו-<math>B</math> המקיימים:
:<math>B>2r_n</math> וכן <math>\text{gcd}(A,B)=1</math> כאשר <math>\text{gcd}</math> היא פונקציית [[מחלק משותף מקסימלי]], בדרך זו מובטח של-<math>A</math> יהיה [[הופכי כפלי מודולרי|הופכי כפלי מודולו]] <math>B</math>.

אליס מכינה סדרה <math>M</math> שאינה סופר עולה על ידי הכפלה ב-<math>A</math> כך:
:<math>M_i\equiv Ar_i(\text{ mod }B)</math> כאשר <math>0\le M_i<B</math>.
הסדרה <math>M</math> היא המפתח הציבורי של אליס שהוסתר על ידי הכפל ב-<math>A</math> מודולו <math>B</math> ואילו המפתח הסודי כולל את הסדרה <math>r</math> והשלמים <math>A</math> ו-<math>B</math> בגלל ה[[חשבון מודולרי|חשבון המודולרי]] לא קל לנחש את <math>A</math> או <math>B</math> מתוך המפתח הציבורי. אם בוב רוצה להצפין את המסר <math>x</math> עבור אליס הוא משתמש במפתח הציבורי שלה ומחשב את 
:<math>S=x\cdot M=\sum_{i=1}^n x_iM_i</math>.
את הטקסט המוצפן <math>S</math> הוא שולח לאליס. לפענוח אליס פועלת כדלהלן, תחילה מחשבת את <math>S'\equiv A^{-1}S(\text{ mod }B)</math> דהיינו מכפילה את <math>S</math> [[הופכי כפלי מודולרי|בהופכי הכפלי]] של <math>A</math> מודולו <math>B</math> ואז משתמשת בסדרה הסופר עולה <math>r</math> כדי לפתור את בעיית תרמיל הגב עם <math>S'</math>. הסיבה שהפענוח נכון היא בשל הזהות הבאה:
:<math>S'\equiv A^{-1}S\equiv A^{-1}\sum_{i=1}^n x_iM_i\equiv A^{-1}\sum_{i=1}^n x_iAr_i\equiv\sum_{i=1}^n x_ir_i\text{ (mod }B)</math>.
היות ש-<math>S'<B</math> מובטח לאליס שתקבל תוצאה מדויקת ולא רק שקילות כלשהי מודולו <math>B</math>.


====דוגמה במספרים קטנים====
נניח שאליס בחרה סדרה סופר-עולה סודית מהדוגמה הקודמת <math>r=(3,11,24,50,115)</math> וכן <math>A=113, B=250</math>. כעת הסדרה המוסוות שלה <math>M</math> תהיה הכפלה של <math>r</math> ב-<math>A</math> כך שמתקבל:
:<math>M\equiv (113\cdot 3, 113\cdot 11, 113\cdot 24, 113\cdot 50, 113\cdot 115)\text{ (mod }250)</math>
:<math>=(89,243,212,150,245)</math>.
שימו לב שגם אם ממיינים את איברי M בסדר עולה הסדרה שהתקבלה רחוקה מלהיות סופר-עולה ולכן יהיה קשה לפתור את בעיית תרמיל הגב בסדרה זו לעומת הסדרה <math>r</math>. כעת אם בוב מעוניין לשלוח לאליס את המסר <math>x=(1,0,1,0,1)</math>, הוא מצפין אותו תחילה באמצעות הכפלה ב-<math>M</math> כך שמתקבל:
:<math>S=x\cdot M=1\cdot 89+0\cdot 243+1\cdot 212+0\cdot 150+1\cdot 245=546</math>.
ושולח לאליס את <math>S=546</math>. כאשר אליס מקבלת את הטקסט המוצפן <math>S</math> היא מכפילה אותו תחילה בהופכי של <math>113 </math> מודולו <math>250 </math> שהוא <math>A^{-1}=177</math> ומתקבל:
:<math>S'\equiv177\cdot 546=142\text{ (mod }250)</math>.
כעת נותר לאליס להשתמש באלגוריתם המתואר לעיל כדי לפתור את בעיית תרמיל הגב בסדרה <math>r</math> עם הערך <math>S'=x\cdot r=142</math> וכך מחלצת את הטקסט המקורי <math>x</math>.

==ביטחון==
בעיית תרמיל הגב הכללית נחשבת ל-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> מוגדרת כדלהלן:
:<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}} שמשפר את התוצאות האמורות מהיבט [[אסימפטוטי]].

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{קריפטוגרפיה}}

[[קטגוריה:הצפנה|תרמיל גב]]