הצפנת תרמיל גב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ Yossiea העביר את הדף הצפנת תרמיל לשם הצפנת תרמיל גב: תרגום יותר מדויק של השם באנגלית |
אין תקציר עריכה |
||
שורה 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}} שעדיין לא התגלתה קריפטואנליזה יעילה שלה.
העניין בהצפנת
בעיית
==בעיית תרמיל הגב==
שורה 13:
נתונה ה[[סדרה]] <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>\{4,9,14\}</math> וקל לראות שזהו הפתרון היחיד במקרה זה. דרך אחרת להציג את הפתרון היא ה[[מרחב וקטורי|ווקטור]] <math>\mathbf{e}=(0,0,1,1,1,0)</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> וכן,
שורה 29:
*מחשבים את רשימת הערכים הבאים: <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=(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>B>2r_n</math> וכן <math>\text{gcd}(A,B)=1</math> כאשר <math>\text{gcd}</math> היא פונקציית [[מחלק משותף מקסימלי]], בדרך זו מובטח של-<math>A</math> יהיה [[הופכי כפלי מודולרי|הופכי כפלי מודולו]] <math>B</math>.
שורה 53:
הסדרה <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'\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>.
שורה 66:
ושולח לאליס את <math>S=546</math>. כאשר אליס מקבלת את הטקסט המוצפן <math>S</math> היא מכפילה אותו תחילה בהופכי של <math>113 </math> מודולו <math>250 </math> שהוא <math>A^{-1}=177</math> ומתקבל:
:<math>S'\equiv177\cdot 546=152\text{ (mod }250)</math>.
כעת נותר לאליס להשתמש באלגוריתם המתואר לעיל כדי לפתור את בעיית
==ביטחון==
בעיית
ב-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) שמצליח לפתור את הבעיה כמעט תמיד בזמן פולינומי בתנאי שצפיפות
:<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>. היות שהאלגוריתמים האמורים מסתמכים על צפיפות
==הערות שוליים==
שורה 80:
{{קריפטוגרפיה}}
[[קטגוריה:הצפנה|תרמיל גב]]
|