קריפטוגרפיה
מונחים כלליים > הצפנה א-סימטרית

הצפנה סימטרית פועלת עם מפתח הצפנה זהה הן להצפנה והן לפענוח ובדרך כלל נדרש להחליפו מעת לעת. החיסרון העיקרי בשיטות הצפנה סימטריות הוא העובדה שיש לשמור את מפתח ההצפנה בסוד ואין לחשוף אותו בשום שלב לאף אחד מלבד המשתתפים הלגיטימיים, עובדה שיוצרת בעיה מהותית הנקראת בעיית הפצת מפתחות. כל זוג מתקשרים אפשרי צריכים לשתף ביניהם מפתח הצפנה סודי נפרד לצורך התקשרות אחת או מספר מוגבל של התקשרויות ולשם כך הם צריכים למצוא דרך להעבירו מאחד לשני בסודיות ולאחסנו במקום מוגן. בתקשורת מודרנית מספר המפתחות האפשריים שיש לנהל מבחינה פרקטית הופך לנטל כבד ולעיתים אינו מעשי. בעיה זו נקראת גם פרדוקס הביצה והתרנגולת כיוון שאם קיימת דרך בטוחה להעביר מפתח הצפנה סודי מלכתחילה הרי שאין צורך בהצפנה כי אפשר להשתמש בה להעברת המסר עצמו, מאידך אם אין דרך כזו כיצד יוכלו להעביר מסרים מוצפנים ביניהם ולפענח אותם אם המתקשרים מעולם לא נפגשו.
במאמר מפורסם משנת 1976 "כיוונים חדשים בהצפנה" הציעו ויטפילד דיפי ומרטין הלמן רעיון פורץ דרך ומהפכני לאותה עת לפתור את הבעיה באמצעות הצפנת מפתח ציבורי או באופן כללי יותר הצפנה אסימטרית. ההצפנה האסימטרית היא שיטת הצפנה שבה המקבל מכין לעצמו שני מפתחות, אחד הנקרא מפתח פרטי שנשמר בסוד ומשמש לפענוח ואילו השני נקרא מפתח ציבורי המפורסם לכל דורש ומיועד להצפנה בלבד. אף על פי שקיים קשר הדוק בין שני המפתחות למתבונן מהצד אמור להיות קשה מאוד לנחש מהו מפתח אחד בהינתן השני ולהפך. בדרך זו כל אחד יכול להצפין מידע עם המפתח הציבורי של המקבל כי הוא ידוע לכל, אך רק המקבל לבדו מסוגל לפענחו עם מפתח הפענוח המתאים שנשמר בסוד. השיטה האסימטרית מתגלה כשימושית במיוחד כאשר צד אחד רוצה להעביר לצד השני מפתח שיחה לצורך הצפנה/פענוח של מידע שהוא מעוניין לחלוק עמו. הוא עושה זאת על ידי הצפנתו באמצעות המפתח הציבורי של המקבל והמקבל מצידו יכול לפענח את המסר ולקבל את מפתח השיחה מבלי שיצטרך לשתף מידע כלשהו מראש עם השולח. עם מפתח זה שני הצדדים יכולים לבצע התקשרות מוצפנת בבטחה, באמצעות צופן סימטרי מהיר. ההיסטוריון דייוויד קאהן כינה את הצפנת המפתח הציבורי הקונספט המהפכני ביותר מאז המצאת צופן החלפה פולי-אלפביתי בתקופת הרנסאנס. דיפי והלמן הוכיחו שאפשר לעשות זאת על ידי מה שנקרא מאוחר יותר פרוטוקול דיפי הלמן הנמצא עד היום בשימוש נרחב ובכך מצאו למעשה פתרון יעיל לבעיית הפצת המפתחות. בנוסף העלו השניים לראשונה את רעיון החתימה הדיגיטלית המדמה חתימה קונבנציונלית על מסמך דיגיטלי אם כי לא הציעו פתרון מעשי.
המאמר של דיפי והלמן הצית את הדמיון הציבורי ועורר הדים רבים. הם ציינו במאמרם את העובדה שהרעיון שלהם שאב השראה בין היתר מרלף מרקל שעבד על רעיון משלו הנקרא חידות מרקל שלא זכה לפרסום. בעקבות פרסום המאמר ולאחר מאמצים רבים מצד האקדמיה התגלו ברבות הימים שיטות מפתח ציבורי רבות. כשנה לאחר מכן ב-1978 פיתחו עדי שמיר, רונלד ריבסט ולאונרד אדלמן את RSA שהיא שיטת מפתח ציבורי שלמה הראשונה אשר יכלה לשמש הן להצפנה והן לחתימה דיגיטלית והיא בשימוש עד ימינו. לאחריה התגלו שיטות נוספות כגון צופן אל-גמאל, הצפנת רבין, הצפנת קריימר-שופ, הצפנת תרמיל, NTRU, הצפנת מקאליס ועוד רבות.
מסמך שפורסם ב-1997 על ידי ממשלת בריטניה חשף כי המודיעין הבריטי (GCHQ) היה מודע כבר ב-1970 לרעיון ההצפנה האסימטרית. המתמטיקאים ג'יימס אליס וקילפורד קוקס שעבדו למען המודיעין הבריטי באותה עת פרסמו כל אחד בנפרד מאמרים בהם טענו שפיתחו שיטות דומות ל-RSA ודיפי-הלמן אך נשמרו בזמנו בסוד מטעמים של ביטחון לאומי.
העובדה שקיים קשר חד-חד ערכי בין המפתח הפרטי למפתח הציבורי של המקבל מאפשרת יישום חתימה דיגיטלית המקשרת באופן חד ערכי בין תוכן מסמך דיגיטלי כלשהו לבין ערך הנקרא חתימה באופן שלא ניתן "להעביר" חתימה ממסמך אחד לאחר. המפתח הפרטי של החותם משמש לחתימה ואילו המפתח הציבורי משמש לאימות החתימה. היות שהמפתח הציבורי ידוע לכל, כל אחד יכול לאמת את החתימה אולם כדי לזייפה במטרה לשכנע אחרים שהחותם הלגיטימי ביצע את החתימה יש צורך לדעת מהו המפתח הפרטי של אותו חותם. דוגמה לאלגוריתם חתימה דיגיטלית שהפך במהרה לתקן רשמי של ממשלת ארצות הברית ומשמש בתפקיד זה עד ימינו הוא DSA.
ביטחון הצפנת מפתח ציבורי מבוסס על הסיבוכיות החישובית של בעיות מתמטיות שונות הנקראות "קשות", חלקן מתורת המספרים וחלקן מתחומים מתמטיים אחרים. בעיות אילו מאפשרות הכנת פונקציה חד-כיוונית שמהווה בסיס להצפנת מפתח ציבורי. למשל הקושי בפתרון בעיית RSA והצפנת רבין מסתמך על ההנחה שקשה מאוד לפרק לגורמים מספרים שלמים גדולים. בעוד שקל לחשב העלאה בחזקה מודולרית, הרי שההפך, חישוב שורש מודולורי קשה מאוד אלא אם כן ידועים הגורמים הראשוניים. זוהי פונקציה חד-כיוונית עם "דלת צונחת" (מידע נוסף המאפשר פתרון הבעיה בזמן יעיל, במקרה זה המידע הנוסף הוא הגורמים הראשוניים). ביטחון פרוטוקול דיפי והלמן מסתמך על הקושי המשוער שבבעיית הלוגריתם הבדיד (גם היא מתורת המספרים). הצפנת NTRU היא דוגמה לאלגוריתם אסימטרי שביטחונו המסתמך על ההנחה שקשה לפתור את בעיית הווקטור הקצר ביותר בתורת הסריגים וכן הצפנת מקאליס היא דוגמה למערכת אסימטרית המבוססת על תורת הקודים.
המכנה המשותף של כל המערכות האסימטריות בימינו לעומת הצפנה סימטרית, הוא היעילות החישובית. מרבית האלגוריתמים נדרשים לבצע חישובים אריתמטיים ארוכים מאוד בשל העובדה שהבעיות המתמטיות האמורות ניתנות לפתרון באמצעות אלגוריתמים המסוגלים לתת פתרון בזמן ריצה תת-מעריכי שזה טוב יותר מכוח גס כלומר ניסוי כל האפשרויות או מחצית מהן במקרה הממוצע עד לגילוי מפתח ההצפנה. כדי לפצות על כך יש צורך להגדיל את מפתחות ההצפנה בהתאם כך שסיבוכיות הניסיון לשבור את ההצפנה עם מיטב האלגוריתמים הידועים תהיה מעבר ליכולת המחשוב הנוכחית. מסיבה זו השימוש בהצפנה אסימטרית בדרך כלל מוגבל לכמות מועטה של מידע והוא משולב במערכת היברדית עם הצפנה סימטרית לניצול מיטבי של היתרונות שבשתי השיטות. בדרך כלל מפתח ציבורי משמש להעברת מפתח הצפנה סודי, כאשר את ההצפנה בפועל מעדיפים לבצע עם אלגוריתם סימטרי מהיר כמו AES.