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

תוכן שנמחק תוכן שנוסף
שורה 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> מתקיים: