סוד כמוס בהחלט: מאז ומעולם היו לבני אדם סודות שהם רצו להסתיר מחלק מסביבתם ולהעביר לאחרים. צפנים סייעו לזוגות אוהבים שביקשו לשמור את הרומן שלהם בסוד, מפקדים נעזרו בהם להעברת פקודות ומרגלים שלחו למפעילים דוחות שאיש לא יוכל לפענח בלי המפתח הנכון. בימינו הגיעה ההצפנה לשיא חשיבותה: כמעט כל פעולה אינטרנטית כיום כרוכה בהצפנה, החל בהזנת סיסמאות, דרך שליחת הודעות צ'ט וכלה בתשלום בכרטיס אשראי. כל אלה מחייבים אותנו לבנות מערכת שרק השולח והמקבל של ההודעה יכולים לקרוא את המסרים העוברים בה. במשימה הזאת יכולת החישוב הגבוהה של המחשב היא ידיד חשוב – אך לפעמים גם אויב.
קיצור תולדות ההצפנה
הצפנים הראשונים הופיעו כבר לפני אלפי שנים, כשבני אדם השתמשו בשיטות פשוטות יחסית להפיכת הטקסט לטקסט אחר. למשל היו מחליפים כל אות באות אחרת, שנמצאת מספר מסוים של מקומות אחריה באלפבית, או שהכינו מפתח מוסכם שקבע איזו אות תחליף כל אות.
השיטות האלה היה נוחות לשימוש על דף פשוט וכלי כתיבה, והמצפין והמפענח יכלו לזכור אותן בקלות, ולכן היו נפוצות למדי, אך לפני כ-1,100 שנה מצא המלומד הערבי יוסוף אל-כינדי דרך קלה למדי לפצח אותן. השיטה, שנקראת ניתוח תדירות, מבוססת על חולשה משמעותית של שיטות ההצפנה הללו: גם אם נחליף כל אות בסמל אחר, עדיין השכיחות של כל אות בשפה נשארת בעינה.
5 צפייה בגלריה
שיטה קלה לפענח צפנים פשוטים: ניתוח תדירות ההופעה של אותיות מסוימות, במקרה זה באנגלית
(איור: Nandhp, ויקיפדיה, נחלת הכלל)
לדוגמה, האות הנפוצה ביותר בעברית היא י'. לכן, אם אנחנו יודעים שלפנינו טקסט שכל אות בו הוחלפה באות עברית אחרת, והאות הנפוצה ביותר בטקסט המוצפן שלפנינו היא ח', יהיה סביר לנחש שהח' בטקסט המוצפן מייצגת את י' בטקסט המקורי. גם אם שכיחות האותיות בטקסט המוצפן שונה מעט מהנורמה המקובלת בשפה, סביר להניח שלפחות האות השנייה או השלישית בשכיחותן בטקסט תייצג את האות י'. בעזרת שלבים נוספים כאלה וכמה ניחושים מושכלים נוכל לזהות מילים קצרות ובסופו של דבר לפצח את הצופן כולו ולגלות איזו אות מייצג כל סמל בטקסט המוצפן. התהליך יהיה כמובן יותר ויותר פשוט ככל שנתקדם ונפענח יותר אותיות.
במשך השנים פותחו צפנים יותר ויותר מורכבים, אך את כולם היה אפשר ליצור ולפענח באמצעות עט ונייר. במאה ה-20 המצב הסתבך, כשהחלו לייצר מכונות הצפנה מכניות, שאי אפשר היה לפענח ללא מכונה דומה. המפורסמת מכולן היא ללא ספק מכונת האניגמה ששימשה את הצבא הגרמני בשנות ה-30 ובמהלך מלחמת העולם השנייה. הפולנים, ובעקבותיהם הבריטים, בעזרת צוות שכלל מתמטיקאים רבים ובראשם חלוץ מדעי המחשב אלן טיורינג (Turing), הצליחו למצוא חולשות באופן פעולת המנגנון המכני המתוחכם של המכונה ולפצח את הצופן. מקובל לחשוב שהגישה שהשיגו כך לתשדורות גרמניות סודיות רבות תרמה מאוד לניצחון בעלות הברית במלחמה.
אניגמה בישראל. ריאיון באולפן ynet. ארכיון
(צלמים: יוגב אטיאס ואסי כהן)
כיום, צפני הדף והעט אינם נחשבים בטוחים, ואת כולם אפשר לפרוץ בקלות יחסית בעזרת מחשב. יוצאת הדופן היחידה היא המערכת הקרויה מפתח חד-פעמי או פנקס חד-פעמי, שהוכח מתמטית כי היא חסינה לכל ניסיון פיצוח. הבעיה איתה היא שדרוש בה מפתח אקראי לחלוטין, שיהיה באורך של הטקסט שאותו רוצים להצפין, ואפשר להשתמש בכל מפתח פעם אחת בלבד. לפיכך השיטה מחייבת ייצור שוטף והפצה של מפתחות אקראיים לחלוטין וארוכים מאוד. לכן היא נחשבת לא מעשית וכמעט שלא משתמשים בה כיום.
5 צפייה בגלריה
כל אחד יכול להצפין הודעה, אבל לא כל אחד יכול לקרוא אותה. עדי שמיר, ממפתחי שיטת RSA
(צילום: Erik Tews, ויקיפדיה)
הצפנה בעידן המחשב
מה קורה כיום, בעידן המחשב? ראשית, יש להמיר כל מסר שרוצים להצפין למספרים, שכן הנתונים בזיכרון המחשב שמורים בתור מספרים בינאריים, המורכבים מצירופים של אפס ואחת בלבד. לכן, יש לקחת את המסר, להמיר בו כל אות או סמל בו למספר. כך הופכת ההודעה שרוצים לשלוח לרצף של ספרות שקל למדי לפענח. כעת עלינו למצוא דרך לשלוח את הספרות האלה לאדם אחר, כך שהוא יוכל לקרוא את ההודעה אבל כל מי שיירט אותה בדרך לא יוכל להסיק מה היא הייתה.
בשנות ה-60 של המאה ה-20 החלו להופיע צפנים שנועדו להצפנת תקשורת אלקטרונית. הצפנים הללו דורשים חישובים רבים ולכן לא מעשי ליישם אותם עם עט ונייר בלבד. הם התבססו על קיומו של מפתח – מעין מילת קוד סודית הידועה רק לשולח ולמקבל ההודעה. המפתח משמש ליצירת הודעה מוצפנת ולאחר מכן לפענוח ההודעה המקורית מהקוד המוצפן.
הצפנים הישנים יחסית מהסוג הזה, למשל DES, אינם נחשבים בטוחים כיום, כיוון שהמחשב החזקים שקיימים בימינו יכולים לפרוץ אותם בקלות יחסית עד ידי בדיקה שיטתית של כמעט כל האפשרויות לפענוח. במקומם יש צפנים חדישים שנחשבים בטוחים מאוד, כמו AES.
השלב הבא: הצפנה אסימטרית
לכל הצפנים שדיברנו עליהם עד כה, מצפני ההחלפה הפשוטים העתיקים, דרך האניגמה ועד לצפני המחשה הנפוצים יש בעיה משותפת: כדי שאוכל לשלוח למישהו אחר הודעה מוצפנת, שנינו צריכים את המפתח. אבל איך אוכל להעביר לצד השני את המפתח מלכתחילה? אם יש לנו ערוץ תקשורת מאובטח, נוכל להשתמש בו לשידור המסר בלי צורך בהצפנה; בהיעדר ערוץ כזה, המפתח שיישלח יהיה גלוי לכל מי שייחשף לתקשורת הזאת.
חישבו על התרחיש הבא: אתם קונים מוצר באינטרנט ורוצים לשלוח את פרטי כרטיס האשראי שלכם לאתר. תרצו כמובן להצפין אותם, כדי שלא ייגנבו בדרך ומישהו ישתמש בהם כדי לקנות בכספכם מכם. אבל איך אתם והאתר תיצרו מפתח משותף? אם האתר ישלח לכם מפתח הצפנה, ייתכן שהוא יתגלה בדרך, ושוב יוכלו פורצים לפענח את פרטי האשראי המוצפנים. שיטות ששימשו בעבר לפתרון בעיות כאלה, כמו שימוש בבלדרים אמינים שימסרו את המפתח פנים אל פנים, אינן רלוונטיות לתרחיש הזה, כמובן.
פריצת הדרך הגיעה ב-1977 עם פיתוח שיטת ההצפנה האסימטרית הראשונה, RSA, שנקראה כך על שם ממציאיה: רון ריווסט (Rivest), עדי שמיר (כיום ממכון ויצמן למדע) ולאונרד אדלמן (Adelman). עד לשיטה הזאת, הצפנה נעשתה תמיד באופן סימטרי, כך שכדי לפענח את המסר הייתם צריכים לעשות את הפעולה ההפוכה לזאת שעשיתם כשהמרתם את המסר לצופן. לעומת זאת, בהצפנה אסימטרית יש שני מפתחות: אחד להצפנת הודעות ואחד לפענוחן. לפיכך, אי אפשר להשתמש במפתח ההצפנה כדי לפענח הודעות.
בדרך הזאת, אתר אינטרנט יכול לפרסם את מפתח ההצפנה שלו בפומבי, וכל אדם יכול להצפין את פרטי האשראי שלו ולשלוח אותם לאתר. אולם מפתח הפענוח ידוע רק לאתר – לכן הוא קרוי מפתח פרטי – ורק הוא יוכל לפענח את המידע. במצב הזה, לא רק שמי שיירט את ההודעה לא יוכל לגלות את פרטי האשראי המוצפנים, אלא אפילו השולח עצמו לא יכול להפוך את ההליך – לשניהם חסר מפתח הפענוח. כך מתקבלת מערכת שההצפנה בה קלה והפענוח קשה מאוד למי שלא מכיר את המפתח הפרטי וקל למי שכן.
מבוקשת: הוכחה
הרעיון אכן נשמע יפה, אך האם אפשר למצוא מערכת כזאת? מבחינה מתמטית, אין כיום הוכחה שמערכת כזאת אכן קיימת, אם כי מקובל להניח שכן. אולם בפועל יש מערכות שעונות על התנאים: קל להצפין בעזרתן, קל לפענח את ההודעה בעזרת המפתח, ולא ידועה דרך פשוטה לפענח אותה בלעדיו. מה שלא הוכח עד כה הוא שאף אחד לא יוכל לעולם להמציא דרך קלה לפרוץ את ההצפנה ולפענח הודעות בלי המפתח הפרטי. שיטות ההצפנה האסימטריות הנפוצות כיום, ובראשן RSA, מסתמכות על בעיות שמאמינים כי הן מקיימות את התנאי הזה, ובעשורים הרבים מאז שהוצגו לא נמצאו קיצורי דרך או חורים אחרים בהצפנה.
גם הבעיה המתמטית המפורסמת P=NP?, אחת משבע הבעיות המתמטיות שהוכרזו כבעיות המילניום בשנת 2000, קשורה לנושא: בלי להיכנס לתוכן הבעיה, אם יוכח כי P=NP, משמעות הדבר היא כי לפחות תיאורטית קיימת דרך מהירה לפרוץ כל צופן אסימטרי, אם כי לא בהכרח באופן מעשי. כיום כמעט כל העוסקים במדעי המחשב סבורים שמאוד לא סביר להניח שזה יקרה, וגם תהיה הוכחה כזו, קשה להאמין שהיא תצביע על דרך מעשית לפענח במהירות צפנים אסימטריים. אפילו אם נמצא אלגוריתם שעונה על ההגדרה המתמטית ל"קל", עדיין ייתכן הוא יהיה איטי מדי לכל צורך מעשי.
מספרים ארוכים מאוד
לא ניכנס כאן לפרטי הפרטים של שיטת RSA, אלא רק נסביר את העיקרון הבסיסי. ראשית, מקבל הנתונים בוחר שני מספרים ראשוניים גדולים, כל אחד מהם בן כמה מאות ספרות לפחות. לאחר מכן הוא מכפיל אותם זה בזה, ומפרסם את המכפלה לשימושם של השולחים. כדי להצפין, מספיק לדעת את המכפלה. בעזרתה יוצרים מההודעה המקורית, שהיא כאמור מספר בינארי, מספר חדש, שהוא ההודעה המוצפנת.
עבור המפתח הפרטי צריך לדעת מהם הגורמים הראשוניים של המספר, ובעזרתם לשחזר את ההודעה המקורית מההודעה המוצפנת. הבעיה היא שלא ידועה דרך פשוטה לפרק לגורמים מספר כל כך גדול, כלומר לקחת את המכפלה ולקבל ממנה בקלות את שני הראשוניים שהכפלנו. בהיעדר דרך כזאת, איננו יכולים לפענח בקלות את ההודעה המוצפנת.
ייתכן שיש גם דרכים לפרוץ את הצופן בלי פירוק לגורמים, אולם ב-44 השנים שחלפו מאז המצאת ה-RSA, לא נמצאה דרך קלה יותר לפצח אותה. מקובל להניח שאין דרך מהירה וקלה לבצע פירוק לגורמים של מספרים גבוהים מאוד, גם אם זה לא הוכח מתמטית עד כה.
כמה קשה לפרק לגורמים? זה תלוי בעיקר בגודל המספר. מחשב אישי מסוגל כיום למצוא את כל המחלקים הראשוניים של מספר בן 60 ספרות תוך כמה שניות, אך אם יהיו בו 80 ספרות נזדקק כבר ללא מעט דקות. יש ברשת אפליקציות שמאפשרות לשחק עם מספרים בגדלים שונים ולראות כמה זמן נדרש לפרק אותם לגורמים. מספר של 200 ספרות כבר דורש משאבי מחשוב עצומים כדי שאולי יהיה אפשר לפרק אותו לגורמים, ואילו מספרים של 400 ספרות כבר נמצאים מעבר לקצה גבול היכולת, אפילו של סוכנויות ביון עם מחשבי על. בימינו משתמשים בדרך כלל במפתחות של 600 ספרות ויותר.
חתימה טובה
ל-RSA יש יתרון נוסף וחשוב: הוא מאפשר לחתום על הודעות בצורה אמינה.
שיטת ההצפנה פועלת בשני הכיוונים. היא מאפשרת לא רק להצפין טקסט ואז לפענח אותו, אלא גם הפוך. אם ננסה "לפענח" טקסט אמיתי, כלומר נריץ עליו את אלגוריתם הפענוח, ולאחר מכן נצפין את התוצר, נקבל בחזרה את הטקסט המקורי.
כשאנו מצפינים טקסט, אנחנו יוצרים קוד שרק גורם אחד יכול לקרוא אותו – מי שמחזיק במפתח הפענוח. כשאנו "מפענחים" טקסט אמיתי, מתקבל טקסט שכל אחד יכול לקרוא, כי כל אחד יכול להצפין אותו בעזרת מפתח ההצפנה הציבורי, אבל רק אדם אחד היה יכול ליצור אותו – מי שמחזיק במפתח הפענוח. כך אפשר ליצור חתימה אמינה שאי אפשר לזייף.
שילוב שתי התכונות הללו מאפשר ליצור הודעה שהיא גם מוצפנת וגם חתומה: להצפין אותה בעזרת מפתח ההצפנה הציבורי ואז לפענח את ההודעה המתקבלת בעזרת המפתח הפרטי. כך יתקבל טקסט שרק הנמען יוכל לקרוא, והוא יוכל גם לדעת בוודאות שהמקור שלו אמין. בפועל התהליך קצת יותר מסובך ממה שתואר כאן, ויש עוד שיטות לחתימה דיגיטלית, אך זה עדיין מאפיין חשוב של RSA.
ההצפנה האסימטרית עדיין איננה הפתרון האולטימטיבי לבעיית ההצפנה, משום שהיא סובלת מחיסרון משמעותי – הצורך להתעסק עם מספרים גדולים מאוד. חישובים אריתמטיים על מפתח הצפנה של מאות ספרות יכולים להאט מאוד את פעולת המחשב, במיוחד במעבדים קטנים עם זיכרון מוגבל כמו אלה שמותקנים בטלפונים סלולריים פשוטים.
אחד הפתרונות הנפוצים לקושי הזה הוא להשתמש בהצפנה אסימטרית כדי לשלוח בצורה מאובטחת מפתחות הרבה יותר קצרים של הצפנה סימטרית רגילה. לאחר מכן אפשר להצפין בה את כל התשדורות. כך מתגברים על בעיית הפצת המפתחות ועדיין מצפינים מהר וביעילות מהיר.
חיפוש ראשוני
מציאת מספרים ראשוניים גדולים כל כך להצפנה ב-RSA אינה אתגר גדול במיוחד: נניח שאנו רוצים למצוא שני ראשוניים בני 300 ספרות כל אחד. ממשפט המספרים הראשוניים אפשר להסיק שאם נבחר באקראי 1,500 מספרים בגודל כזה, יש סיכוי גבוה ששניים מהם יהיו ראשוניים, שכן בערך 1 מכל 700 מספרים באורך הזה הוא ראשוני.
הבדיקה אם מספר הוא ראשוני מהירה מאוד, אפילו כשמדובר במספרים של מאות ספרות, ונמשכת פחות משנייה במחשב אישי. אם המספר אינו ראשוני, הבדיקה שלנו לא תגיד מהם הגורמים שלו, שכן כבר ציינו שפירוק לגורמים של מספר ארוך הוא משימה קשה מאוד. אבל אפשר להוכיח שמספר הוא פריק גם בלי למצוא מחלק שלו.
האלגוריתמים המתוחכמים שעושים זאת מהירים הרבה יותר מאלה שמשמשים לפירוק לגורמים. לשם המחשה, אם ניקח שני מספרים ראשוניים של 300 ספרות ונכפיל אותם, נקבל תוצאה של 600 ספרות. אפשר להוכיח כהרף עין שהמספר הזה אינו ראשוני, אך פירוקו לגורמים בשיטות הטובות ביותר שיש לנו כיום, צפוי להימשך מיליוני שנים לפחות גם אם נגייס למאמץ את כל המחשבים בעולם.
5 צפייה בגלריה
גם למחשב-על יידרשו מיליוני שנים לפענח הצפנה מודרנית. מחשב העל "אינטרפיד" של IBM
(צילום: Argonne National Laboratory, ויקיפדיה)
העתיד: מחשבים קוונטיים?
ההתפתחות החשובה ביותר הצפויה כיום בתחום ההצפנה היא פיתוח מחשבים קוונטיים. שיטת הפעולה של מחשבים כאלה שונה מאוד מזאת של המחשבים הדיגיטליים הקיימים, והוכח שהם יוכלו לפרוץ את RSA מאחר שהם יהיו מסוגלים לבצע פירוק לגורמים במהירות רבה יחסית.
עד כה לא נעשה דבר כזה על שום מספר ראשוני המשמש להצפנה בפועל, מכיוון שהמחשבים הקוונטיים הניסיוניים שנבנו עד כה אינם חזקים מספיק. מעריכים כי בעוד שנים לא רבות כבר יהיו מחשבים קוונטיים חזקים מספיק לפירוק מהיר של מספרים בני אלפי ספרות. זה גם יהיה סופה של שיטת RSA. גם שיטת ההצפנה האסימטרית העיקרית האחרת, הקרויה "הצפנה בעזרת עקומים אליפטיים", תיפרץ בידי מחשבים קוונטיים.
לא נוכל כאן לתאר כאן לעומק את אופן הפעולה של מחשבים קוונטיים. נוכל לומר כי סוד הצלחתם נובע מכך שהעקרונות הפיזיקליים שעליהם מבוססים הרכיבים הבסיסיים ביותר של המחשב הקוונטי שונים מהותית מאלה של המחשב הרגיל, ומאפשרים למחשבים קוונטיים לבצע פעולות מסוימות הרבה יותר מהר. נכון להיום אתגרים פיזיקליים משמעותיים מקשים מאוד על פיתוח מחשבים קוונטיים חזקים, ועד כה כל המחשבים הקוונטיים שנבנו היו קטנים מאוד ומוגבלים.
כיצד תשפיע הופעתם של מחשבים קוונטיים על ההצפנה? כבר עתה יש מי שפועלים לפתח שיטות הצפנה חדשות שיהיו חסינות גם למחשבים כאלה, מה שמכונה הצפנה פוסט-קוונטית. הפתרונות המוצעים מתחלקים לשתי גישות. הראשונה היא שימוש באלגוריתמים אסימטריים החסינים בפני מחשב קוונטי. ידועים כמה אלגוריתמים כאלה, כגון NTRU, אך הם נחשבים פחות טובים מ-RSA או מעקומים אליפטיים, או שלא נצבר די ניסיון בשימוש בהם. אם ישודרגו וישופרו עוד, יש סיכוי שהם יתפסו את מקומן של רוב שיטות ההצפנה הקיימות. נעשים גם מאמצים לקבוע תקן חדש להצפנה, שיהיה חסין למחשבים קוונטיים.
הגישה השנייה מכונה לעתים הצפנה קוונטית, אם כי השם מטעה מעט, מכיוון שהיא אינה קשורה כלל למחשבים קוונטיים. הרעיון הוא להשתמש בתכונות של מכניקת הקוונטים כדי ליצור ערוץ תקשורת שאי אפשר לצותת לו בחשאי. כלומר, אם גורם שלישי מאזין למידע העובר בערוץ תקשורת, הצדדים המתקשרים יידעו את זה. ברגע שהם יודעים שאיש לא מאזין להם, הם יכולים להשתמש בערוץ הזה כדי לשדר מפתחות שישמשו להצפנה בעזרת פנקס חד-פעמי, שאמור להיות חסין גם לכוח החישוב של מחשבים קוונטיים.
הצפנה קוונטית היא שיטה בטוחה יותר מהגישה הראשונה שהוזכרה כאן, אך גם יקרה יותר ומסורבלת. בניגוד לגישה הראשונה היא גם לא יושמה עדיין בקנה מידה רחב, אלא רק באופן ניסיוני, ונראה שפיתוחה ידרוש התגברות על כמה אתגרים פיזיקליים. הנושא נחקר כעת בכמה מקומות בעולם, למשל בסין.
5 צפייה בגלריה
גם למחשב-על יידרשו מיליוני שנים לפענח הצפנה מודרנית. מחשב העל "אינטרפיד" של IBM
(צילום: Argonne National Laboratory, ויקיפדיה)
בתחום ההצפנה יש גם זווית מקומית משמעותית. רבים מהחוקרים המובילים בתחום הקריפטוגרפיה, כלומר חקר ההצפנה ואבטחת המידע, הם ישראלים, העובדים בארץ או בחו"ל, בהם עדי שמיר, מיכאל רבין, שפרירה (שפי) גולדווסר ורבים אחרים. לא מעט פריצות דרך חשובות בתחום נעשו בידי ישראלים, לבד או בשיתוף חוקרים אחרים, בהן כאמור RSA, המצאת הרעיון של הוכחה באפס ידיעה, אחד האלגוריתמים הנפוצים ביותר כיום לבדיקת ראשוניות (מילר-רבין) ועוד.
אין ספק שזהו אחד מתחומי המחקר שבהם ישראל בולטת, הן במספר החוקרים לנפש והן במספר החוקרים המוחלט, כך שבהחלט יש פה מקור לגאווה. לאור מעמדו המבוסס של ענף ההייטק בישראל ויוקרתן של יחידות המודיעין הצבאי העוסקות בתחומים הללו, יש סיבות טובות לקוות שישראל תישאר גם בעתיד מרכז חשוב למחקרים בנושאי הצפנה ומדעי המחשב.
אורי טייכמן, מכון דוידסון לחינוך מדעי
