הצפנת תרמיל

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

הצפנת תרמיל (Knapsack cryptosystem) היא מערכת הצפנת מפתח ציבורי שביטחונה מבוסס על הקושי המשוער שבפתרון בעיית תרמיל הגב שהיא בעיה NP-קשה. הצפנת תרמיל הייתה הניסיון הראשון לבסס מערכת הצפנה על בעיה NP-קשה ואף על פי שהרעיון קיים כבר מאז 1978 רוב המערכות הקיימות שפותחו על בסיס זה נפרצו ולכן אינן בשימוש מעשי, אלא נחקרות לצורך אקדמי בלבד[1].

השיטה הראשונה והמפורסמת ביותר היא הצפנת תרמיל של מרקל והלמן שפותחה ב-1978 על ידי רלף מרקל ומרטין הלמן[2]. היא הייתה מערכת מפתח ציבורי מהראשונות שפותחו ופורסמה באותה שנה שבה פורסמה RSA. מערכת זו נפרצה לחלוטין בכמה התקפות מפורסמות שהראשונה שבהן הייתה של שמיר[3], אחריו פיתחו אדלמן[4], אודליצקו ולגריאס[5] בנפרד קריפטואנליזה הנקראת התקפת צפיפות נמוכה לשבירת הצפנת מרקל-הלמן בזמן פולינומי. כל הגרסאות שהומצאו מאז כולל גרסת שור-ריבסט[6] המכילה צפיפות גבוהה יחסית (הגדרה בהמשך), נמצאו לא בטוחות וניתנות לשבירה בזמן פולינומי או בזמן שהוא נמוך בהרבה מכוח גס עם הפרמטרים שהומלצו על ידי המפתחים. במרבית המקרים שינוי הפרמטרים לא יועיל במידה ניכרת ולכן מערכות אילו לא נכנסו לשימוש מעשי כלל למעט מערכת חדשה יחסית של Nasako-Murakami מ-2006[7] שעדיין לא התגלתה קריפטואנליזה יעילה שלה.

העניין בהצפנת התרמיל נובע מהעובדה שהיא נחשבת פוסט-קוונטית ולכן תהיה אטרקטיבית אם תמצא דרך בטוחה ליישמה. אם תמצא דרך כזו הרי שהמערכת אמורה לספק ביטחון גם לנוכח איום קריפטואנליזה על מחשב קוונטי כאשר יהיה מעשי. זאת בניגוד לשיטות כמו RSA ו-DSA המסתמכות על בעיית פירוק לגורמים ולוגריתם דיסקרטי, אותם ניתן יהיה לשבור בקלות בהינתן מחשב קוונטי באמצעות אלגוריתם שור.

בעיית התרמיל קשורה בקשר הדוק עם סריגים. לאחר פרסום אלגוריתם LLL התברר שמערכת הצפנה מבוססת בעיית תרמיל סובלת מבעיה מהותית. באופן כללי אם כאשר הוא פרמטר ביטחון (מפורט בהמשך) אז אלגוריתם לצמצום סריגים (Lattice reduction algorithm) מאפשר לגלות את הטקסט המקורי מתוך הטקסט המוצפן ללא ידיעת המפתח בזמן פולינומי. מאידך אם אז המפתחות מגיעים לממדים עצומים בערך 176KB למפתח מה שהופך את המערכת לבלתי יעילה.

בעיית תרמיל הגב[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – בעיית תרמיל הגב

בעיית תרמיל הגב הנקראת גם בעיית הסכומים החלקיים - מהיבט קריפטוגרפי מוגדרת כדלהלן:

נתונה הסדרה המכילה איברים שלמים, כאשר הוא פרמטר ביטחון (למשל ):

ונתון שלם חיובי הנקרא 'תרמיל'. הבעיה היא לגלות האם קיימת תת-קבוצה של איברים ב- שסכומה הוא . במילים אחרות המטרה היא לגלות את הווקטור המקיים:

.

דוגמה במספרים קטנים[עריכת קוד מקור | עריכה]

נניח ש- ונתונה הסדרה:

והתרמיל

אפשר לראות בניסוי וטעייה שהפתרון הוא תת-הסדרה וקל לראות שזהו הפתרון היחיד במקרה זה. דרך אחרת להציג את הפתרון היא הווקטור (כלומר הווקטור מכיל אחדים בכניסות המתאימות לאיברים הנכללים בסכום התרמיל ובכל היתר אפסים) במילים אחרות .

אפשר לפתור את הבעיה בכוח גס, פשוט על ידי ניסוי כל האפשרויות של הווקטור עד למציאת הווקטור הנכון. סיבוכיות הפתרון היא מסדר גודל של , אולם אפשר לחתוך את סיבוכיות הפתרון בפקטור של שנים על ידי אלגוריתם ההתנגשות הבא.

אלגוריתם התנגשות לפתרון בעיית התרמיל הכללית[עריכת קוד מקור | עריכה]

אם נתונה בעיית תרמיל-גב עם הפרמטרים באורך ושלם אפשר לפעול כדלהלן:

  • מכינים קבוצת שלמים כך שמתקיים , כלומר קבוצת כל האיברים הנמוכים מחצי של וכן,
  • מכינים קבוצת שלמים כך שמתקיים ,
  • מחשבים את רשימת הערכים הבאים: כלומר רשימת כל הסכומים האפשריים ב-,
  • באותו אופן מחשבים את רשימת הערכים: ,
  • ממיינים את הקבוצות לפי סדר מספרי ומחפשים התאמה כך שתתקבלנה שתי תת-רשימות ו- המקיימות: . רשימות אילו נותנות למעשה את הפתרון לבעיית התרמיל כי
.

מספר האלמנטים ב- וב- הוא לכל היותר כל אחת ולכן זמן הריצה של האלגוריתם הוא כאשר הוא ערך קטן המייצג את התקורה הנוספת הנובעת מחישוב הרשימות ומיונן.

סדרה סוּפֶּר-עולה[עריכת קוד מקור | עריכה]

בעיקרון אם גדול הפתרון המתואר אינו יעיל ולכן הבעיה הכללית מוגדרת קשה, אולם אינה מתאימה לקריפטוגרפיה כיוון שלא קיימת "דלת צונחת", אותו מידע סודי שהופך את פתרון הבעיה לקל מאוד למי שמחזיק בו ואילו עבור כל האחרים שאינם יודעים מהו הבעיה נותרת קשה. דרך אחת להכניס דלת צונחת היא להשתמש בבעיית תרמיל עם תכונה מיוחדת שפתרונה קל. הרעיון של מרקל והלמן היה להשתמש בתרמיל המורכב מסדרה מונוטונית עולה שבה כל איבר גדול לפחות פי שניים מקודמו. בניסוח רשמי זוהי סדרה של איברים שלמים עם התכונה הבאה:

עבור כל .

היא נקראת סופר-עולה (superincreasing) כיוון שעבור כל מתקיים:

או .

במקרה זה פתרון בעיית התרמיל קל מאוד לפי האלגוריתם הבא: מבצעים לולאה שמתחילה באיבר האחרון () כלפי מטה עד האיבר הראשון () ובודקים עבור כל : אם מציבים ומחסרים אחרת מציבים וממשיכים עד ש- (בהנחה שפתרון קיים).

לדוגמה הסדרה היא סופר עולה, נניח שנתון השלם מייצגים את כסכום איברים בסדרה כדלהלן: תחילה היות ש- לכן ומחליפים את ב-. בשלב הבא היות ש- מציבים . בשלב הבא רואים ש- לכן ו-. היות ש- אנחנו יודעים ש- ולבסוף כי ועוצרים כי . לסיכום, הפתרון הוא

הצפנת תרמיל של מרקל והלמן[עריכת קוד מקור | עריכה]

מרקל והלמן הציעו ב-1978 מערכת הצפנה המבוססת על בעיית התרמיל עם סדרה סופר עולה שאותה מסתירים באמצעות שקילויות. כדי לייצר מפתח פרטי ומפתח ציבורי אליס בוחרת סדרה סופר עולה בעלת איברים כך שעבור כל מתקיים וכן בוחרת שני שלמים גדולים ו- המקיימים:

וכן כאשר היא פונקציית מחלק משותף מקסימלי, בדרך זו מובטח של- יהיה הופכי כפלי מודולו .

אליס מכינה סדרה שאינה סופר עולה על ידי הכפלה ב- כך:

כאשר .

הסדרה היא המפתח הציבורי של אליס שהוסתר על ידי הכפל ב- מודולו ואילו המפתח הסודי כולל את הסדרה והשלמים ו- בגלל החשבון המודולרי לא קל לנחש את או מתוך המפתח הציבורי. אם בוב רוצה להצפין את המסר עבור אליס הוא משתמש במפתח הציבורי שלה ומחשב את

.

את הטקסט המוצפן הוא שולח לאליס. לפענוח אליס פועלת כדלהלן, תחילה מחשבת את דהיינו מכפילה את בהופכי הכפלי של מודולו ואז משתמשת בסדרה הסופר עולה כדי לפתור את בעיית התרמיל עם . הסיבה שהפענוח נכון היא בשל הזהות הבאה:

.

היות ש- מובטח לאליס שתקבל תוצאה מדויקת ולא רק שקילות כלשהי מודולו .


דוגמה במספרים קטנים[עריכת קוד מקור | עריכה]

נניח שאליס בחרה סדרה סופר-עולה סודית מהדוגמה הקודמת וכן . כעת הסדרה המוסוות שלה תהיה הכפלה של ב- כך שמתקבל:

.

שים לב שגם אם ממיינים את איברי M בסדר עולה הסדרה שהתקבלה רחוקה מלהיות סופר-עולה ולכן יהיה קשה לפתור את בעיית תרמיל הגב בסדרה זו לעומת הסדרה . כעת אם בוב מעוניין לשלוח לאליס את המסר , הוא מצפין אותו תחילה באמצעות הכפלה ב- כך שמתקבל:

.

ושולח לאליס את . כאשר אליס מקבלת את הטקסט המוצפן היא מכפילה אותו תחילה בהופכי של מודולו שהוא ומתקבל:

.

כעת נותר לאליס להשתמש באלגוריתם המתואר לעיל כדי לפתור את בעיית התרמיל בסדרה עם הערך וכך מחלצת את הטקסט המקורי .

ביטחון[עריכת קוד מקור | עריכה]

בעיית התרמיל הכללית נחשבת ל-NP-קשה והיא מהווה מועמדת טובה לפונקציה חד-כיוונית. אולם לצורך קריפטוגרפי יש צורך גם בדלת צונחת שהיא המידע הנסתר המאפשר למקבל הלגיטימי לפתור את הבעיה בזמן פולינומי. הגרסה הראשונה של הצפנת התרמיל שהסתמכה על סדרה סופר-עולה הכילה כמה חסרונות מהותיים שהעיקרית שבהן היא העובדה שהתרמיל מכיל צפיפות נמוכה מדי מה שגורם לנקודת תורפה היות שבמקרה של תרמיל בעל תכונה זו קיימים אלגוריתמים יעילים לפתרון הבעיה. במרוצת הזמן הוצעו מספר רב של גרסאות משופרות שנועדו להתמודד עם הבעיות הללו בין היתר על ידי שימוש בתרמילים מרובים או הסתרה של התרמיל באמצעות חשבון מודולרי ואלגברה בחוג הפולינומים.

ב-1985 פורסם בנפרד על ידי בריקל[8], לגריאס ואודליצקו[9] אלגוריתם LO המסתמך על אלגוריתם צמצום סריגים (LLL) שמצליח לפתור את הבעיה כמעט תמיד בזמן פולינומי בתנאי שצפיפות התרמיל נמוכה מ-0.6463. צפיפות התרמיל מוגדרת כדלהלן:

.

אלגוריתם CJLOSS[10] משפר את החסם לגריאס-אודליצקו ל-. היות שהאלגוריתמים האמורים מסתמכים על צפיפות התרמיל הם נקראים באופן כללי "התקפת צפיפות נמוכה". אולם הבעיה הכללית, דהיינו אם צפיפות התרמיל גבוהה מהגבול האמור נותרה בעיה קשה. הרעיון של אלגוריתם LO הוא להמיר את הבעיה לבעיה אחרת מתורת הסריגים הנקראת בעיית מציאת הווקטור הקצר ביותר (SVP) שהיא בעיה קשה מאוד. אף על פי שלא קיים אלגוריתם פולינומי ל-SVP, מעשית אלגוריתם LLL של האחים לנסטרה ולובאז' מצליח לפתור את בעיית הווקטור הקצר בקירוב טוב, הרבה יותר ממה שמציע הגבול התאורטי. האמור הוא אם מתבצעת קריאה אחת לאורקל SVP. אולם במקרה של קריאות מרובות קיים שיפור שלו שנקרא אלגוריתם CJLOSS+‎ שמשפר את התוצאות האמורות מהיבט אסימפטוטי.

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ The Rise and Fall of Knapsack Cryptosystems
  2. ^ 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.
  3. ^ A. Shamir, A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystems, Proc. Crypto’82, LNCS, pp.279–288, Springer-Verlag, Berlin, 1982.
  4. ^ L. M. Adleman, On breaking the titrated Merkle-Hellman public-key cryptosystem, Plenum Press. Crypto’82, pp.303–308. 1982.
  5. ^ 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
  6. ^ 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.
  7. ^ 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
  8. ^ 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
  9. ^ 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.
  10. ^ 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.