מפתח ציבורי
היסטוריה

לאורך ההיסטוריה הקדומה של ההצפנה, מפתח הצפנה היה אמור להישמר בסוד מוחלט, כאשר על השולח והמקבל היה למצוא דרך בטוחה להסכים עליו מראש בשיטה לא קריפטוגרפית כלשהי, כגון במפגש אישי או באמצעות שליח מהימן. בימינו שיטה זו סובלת ממספר בעיות; בשל כמויות המידע הגדולות יש צורך ביצירה ותחזוקה של מספר גדול של מפתחות, ככל שמספר המפתחות שצריך לאחסן גדול יותר גדל החשש מפני חשיפתם. תחזוקה ושמירה בסוד של מספר גדול של מפתחות הצפנה ברשת מרובת משתתפים, לרוב אינו מעשי. הצפנת מפתח ציבורי הומצאה כדי להתמודד עם בעיות אלו. עם הצפנת מפתח ציבורי ניתן לתקשר גם מעל גבי ערוץ שאינו מאובטח וזאת מבלי שהצדדים יזדקקו לשתף ביניהם מפתח סודי מראש.
רעיון המפתח הציבורי החל לעלות כבר בסוף המאה השמונה-עשרה, בספר שנכתב על ידי ויליאמס סטנלי ג'בונס מתואר הקשר בין פונקציה חד-כיוונית להצפנה, בעיקר השימוש בבעיית פירוק לגורמים ליצירת פונקציה חד-כיוונית עם דלת צונחת. הכותב אמנם לא המציא את המושג הידוע כיום ואף לא הציע כל דרך מעשית ליישומו. ההמצאה המעשית הראשונה של רעיון המפתח הציבורי ארעה בראשית 1970 במטה התקשורת של סוכנות הביון הבריטית. ג'יימס אליס, קליפורד קוקס ומלקולם ויליאמס שעבדו בסוכנות באותה עת פיתחו מספר אלגוריתמים קריפטוגרפיים, שהיו דומים למדי למה שנודע לאחר מכן כפרוטוקול דיפי הלמן והצפנת RSA. אולם בזמנו הקריפטוגרפים הבריטיים לא פרסמו את ממצאיהם מאחר שהם הוגדרו כסוד צבאי. העובדה שאלגוריתמים אילו היו ידועים להם כבר אז נחשפה לציבור רק ב-1997. גם ה-NSA טען כי גילה את הרעיון כבר בשנת 1966 אולם לא סיפק כל הוכחות לכך. על כל פנים יש הסבורים כי לעובדות אילו אין ערך ממשי מאחר שממצאים אילו לא היו שימושיים ואף לא מעשיים באותה עת.
הצפנת מפתח ציבורי פורסמה לראשונה באופן מעשי על ידי ויטפילד דיפי ומרטין הלמן במאמרם "כיוונים חדשים בהצפנה" שפורסם ב-1976, בו תיארו את התפיסה המהפכנית של שימוש בפונקציה חד-כיוונית עם דלת צונחת כדי ליצור מערכת הצפנה וחתימה דיגיטלית. הם אף הציעו לראשונה שיטה מעשית בטוחה להעברת מפתח, שנודעה לאחר מכן בשמה פרוטוקול דיפי-הלמן. דיפי והלמן הושפעו בעיקר מעבודתו של רלף מרקל שפיתח טכניקה דומה להעברת מפתח הצפנה מעל גבי ערוץ פתוח המבוססת על סדרה של חידות שנודעה לאחר מכן כחידות מרקל.
מאמרם המהפכני של דיפי והלמן היווה ציון דרך בתולדות ההצפנה המודרנית ועורר הדים רבים בקרב הציבור והוא שהוביל לאחת ההמצאות החשובות בתולדות ההצפנה בשנת 1977. ריבסט, שמיר ואדלמן ששהו במכון הטכנולוגי של מסצ'וסטס באותה עת, פרסמו לראשונה אלגוריתם מעשי שהמציאו המבוסס על הרעיונות של דיפי והלמן, אותו כינו RSA (ראשי תיבות של שמותיהם). האלגוריתם משתמש בהעלאה בחזקה מודולו כפולה של שני מספרים ראשוניים גדולים ובטיחותו נשענת על הקושי המשוער של פירוק מספרים גדולים לגורמים, בעיה שטרם נמצא לה פתרון יעיל עד לימינו. RSA היה לאלגוריתם ההצפנה המעשי הראשון המיישם טכניקת מפתח ציבורי ויכול לשמש הן להצפנה והן לחתימה דיגיטלית.
מאז 1970 הומצאו אלגוריתמים נוספים מבוססי מפתח ציבורי, הן להצפנה והן לחתימה דיגיטלית, חלקם התגלה מאוחר יותר כלא בטוח וחלקם לא היה מעשי, כמו הצפנת התרמיל של רלף מרקל ומרטין הלמן המבוססת על בעיית התרמיל. ב-1978 הומצאה הצפנת מקאליס המבוססת על קוד תיקון שגיאות שחסרונה העיקרי הוא בגודל מפתח ההצפנה, ב-1979 פרסם פרופסור מיכאל רבין שיטת הצפנה הנקראת על שמו הצפנת רבין, שיטה מבוססת מפתח ציבורי בדומה ל-RSA הנשענת על בעיית שורש ריבועי מודולו שלם פריק, היכולה לשמש גם כחתימה דיגיטלית. ב-1984 הומצא אלגוריתם אל-גמאל, (על ידי טאהר אלגמאל), המבוסס על בעיית לוגריתם בדיד בדומה לדיפי-הלמן, שיטה זו היוותה בסיס להמצאת אלגוריתם DSA לחתימה דיגיטלית על ידי ממשלת ארצות הברית מספר שנים לאחר מכן. בסוף שנות השמונים ניל קובליץ ובמקביל ויקטור מילר הציגו לראשונה מערכת מפתח ציבורי המבוססת על עקום אליפטי ומכונה בקיצור ECC, למרות היותה מסובכת התפרסמה השיטה בעיקר בזכות מפתח ההצפנה הקצר שהציעה והיא בשימוש כיום במרבית מערכות אבטחת המידע המסחריות. עם המצאת הצפנה הסתברותית ב-1983 התפתח ענף פופולרי של הצפנה בטוחה סמנטית כמו הצפנת בלום-גולדווסר וכן סכימות חדשות כמו הצפנת פאיי.