הצפנת תרמיל גב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 36:
בעיקרון אם <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>. לסיכום, הפתרון הוא
| |||